×

A polyhedral approach to bisubmodular function minimization. (English) Zbl 1525.90380

Summary: We consider minimization problems with bisubmodular objective functions. We propose valid inequalities, namely the poly-bimatroid inequalities, and provide a complete linear description of the convex hull of the epigraph of a bisubmodular function. Furthermore, we develop a cutting plane algorithm for constrained bisubmodular minimization based on the poly-bimatroid inequalities. Our computational experiments on the minimization subproblem in robust coupled sensor placement show that our algorithm can solve highly non-linear problems that do not admit compact mixed-integer linear formulations.

MSC:

90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ahmed, S.; Atamtürk, A., Maximizing a class of submodular utility functions, Math. Program., 128, 1, 149-169 (2011) · Zbl 1218.90221
[2] Ando, K.; Fujishige, S., On structures of bisubmodular polyhedra, Math. Program., 74, 3, 293-317 (1996) · Zbl 0855.68107
[3] Ando, K.; Fujishige, S.; Naitoh, T., A characterization of bisubmodular functions, Discrete Math., 148, 1-3, 299-303 (1996) · Zbl 0838.05025
[4] Atamtürk, A.; Narayanan, V., Polymatroids and mean-risk minimization in discrete optimization, Oper. Res. Lett., 36, 5, 618-622 (2008) · Zbl 1210.90127
[5] Atamtürk, A.; Narayanan, V., Submodular function minimization and polarity (2019), arXiv preprint arXiv:1912.13238
[6] Bilbao, J. M.; Fernández, J. R.; Jiménez, N.; López, J. J., A survey of bicooperative games, (Pareto Optimality, Game Theory and Equilibria (2008), Springer), 187-216 · Zbl 1152.91318
[7] Bodik, P.; Hong, W.; Guestrin, C.; Madden, S.; Paskin, M.; Thibaux, R., Intel lab data (2004), Online dataset, http://db.csail.mit.edu/labdata/labdata.html
[8] Bouchet, A., Greedy algorithm and symmetric matroids, Math. Program., 38, 2, 147-159 (1987) · Zbl 0633.90089
[9] Bouchet, A.; Cunningham, W. H., Delta-matroids, jump systems, and bisubmodular polyhedra, SIAM J. Discrete Math., 8, 1, 17-32 (1995) · Zbl 0821.05010
[10] Chandrasekaran, R.; Kabadi, S. N., Pseudomatroids, Discrete Math., 71, 3, 205-217 (1988) · Zbl 0656.05023
[11] Church, R. L.; Garfinkel, R. S., Locating an obnoxious facility on a network, Transp. Sci., 12, 2, 107-118 (1978)
[12] Fujishige, S., A min-max theorem for bisubmodular polyhedra, SIAM J. Discrete Math., 10, 2, 294-308 (1997) · Zbl 0873.52012
[13] Fujishige, S.; Iwata, S., Bisubmodular function minimization, SIAM J. Discrete Math., 19, 4, 1065-1073 (2005) · Zbl 1122.90067
[14] Laporte, G.; Louveaux, F. V., The integer L-shaped method for stochastic integer programs with complete recourse, Oper. Res. Lett., 13, 3, 133-142 (1993) · Zbl 0793.90043
[15] McCormick, S. T.; Fujishige, S., Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization, Math. Program., 122, 1, 87 (2010) · Zbl 1190.65099
[16] Nemhauser, G.; Wolsey, L., Maximizing submodular set functions: Formulations and analysis of algorithms, (Hansen, P., Annals of Discrete Mathematics (11) Studies on Graphs and Discrete Programming. Annals of Discrete Mathematics (11) Studies on Graphs and Discrete Programming, North-Holland Mathematics Studies, vol. 59 (1981), North-Holland Mathematics Studies), 279-301 · Zbl 0469.90052
[17] Ohsaka, N.; Yoshida, Y., Monotone k-submodular function maximization with size constraints, (Advances in Neural Information Processing Systems (2015)), 694-702
[18] Plastria, F.; Carrizosa, E., Undesirable facility location with minimal covering objectives, European J. Oper. Res., 119, 1, 158-180 (1999) · Zbl 0934.90051
[19] Qi, L., Directed submodularity, ditroids and directed submodular flows, Math. Program., 42, 1-3, 579-599 (1988) · Zbl 0665.90075
[20] Singh, A.; Guillory, A.; Bilmes, J., On bisubmodular maximization, (Artificial Intelligence and Statistics (2012)), 1055-1063
[21] Svitkina, Z.; Fleischer, L., Submodular approximation: Sampling-based algorithms and lower bounds, SIAM J. Comput., 40, 6, 1715-1737 (2011) · Zbl 1234.68468
[22] Wu, H.; Küçükyavuz, S., A two-stage stochastic programming approach for influence maximization in social networks, Comput. Optim. Appl., 69, 3, 563-595 (2018) · Zbl 1400.90238
[23] Wu, H.; Küçükyavuz, S., Probabilistic partial set covering with an oracle for chance constraints, SIAM J. Optim., 29, 1, 690-718 (2019) · Zbl 1414.90250
[24] Yu, J.; Ahmed, S., Maximizing a class of submodular utility functions with constraints, Math. Program., 162, 1-2, 145-164 (2017) · Zbl 1358.90085
[25] Yu, Q.; Küçükyavuz, S., An exact method for bisubmodular function maximization (2020), arXiv preprint https://arxiv.org/abs/2008.00988
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.