×

Dual-feasible functions for integer programming and combinatorial optimization: algorithms, characterizations, and approximations. (English) Zbl 1483.90081

Summary: Within the framework of the superadditive duality theory of integer programming, we study two types of dual-feasible functions of a single real variable [C. Alves et al., Dual-feasible functions for integer programming and combinatorial optimization. Basics, extensions and applications. Cham: Springer (2016; Zbl 1354.90101)]. We introduce software that automates testing piecewise linear functions for maximality and extremality, enabling a computer-based search. We build a connection to cut-generating functions in the Gomory-Johnson and related models, complete the characterization of maximal functions, and prove analogues of the Gomory-Johnson 2-slope theorem and the Basu-Hildebrand-Molinaro approximation theorem.

MSC:

90C10 Integer programming
90C46 Optimality conditions and duality in mathematical programming

Citations:

Zbl 1354.90101
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alves, C.; Clautiaux, F.; de Carvalho, J. V.; Rietz, J., Dual-feasible functions for integer programming and combinatorial optimization: basics, extensions and applications, (EURO Advanced Tutorials on Operational Research (2016), Springer) · Zbl 1354.90101
[2] Aráoz, J.; Evans, L.; Gomory, R. E.; Johnson, E. L., Cyclic group and knapsack facets, Math. Program. B, 96, 377-408 (2003) · Zbl 1082.90094
[3] Bachem, A.; Johnson, E. L.; Schrader, R., A characterization of minimal valid inequalities for mixed integer programs, Oper. Res. Lett., 1, 2, 63-66 (1982) · Zbl 0486.90066
[4] Basu, A.; Conforti, M.; Di Summa, M.; Paat, J., Extreme functions with an arbitrary number of slopes, (Louveaux, Q.; Skutella, M., Integer Programming and Combinatorial Optimization: 18th International Conference, IPCO 2016, Liège, Belgium, June 1-3, 2016, Proceedings (2016), Springer International Publishing: Springer International Publishing Cham), 190-201 · Zbl 1419.90116
[5] Basu, A.; Hildebrand, R.; Köppe, M., Equivariant perturbation in Gomory and Johnson’s infinite group problem. I. The one-dimensional case, Math. Oper. Res., 40, 1, 105-129 (2014) · Zbl 1308.90106
[6] Basu, A.; Hildebrand, R.; Köppe, M., Light on the infinite group relaxation I: foundations and taxonomy, 4OR, 14, 1, 1-40 (2016) · Zbl 1353.90089
[7] Basu, A.; Hildebrand, R.; Köppe, M., Light on the infinite group relaxation II: sufficient conditions for extremality, sequences, and algorithms, 4OR, 14, 2, 107-131 (2016) · Zbl 1362.90294
[8] Basu, A.; Hildebrand, R.; Köppe, M.; Molinaro, M., A \(( k + 1 )\)-slope theorem for the \(k\)-dimensional infinite group relaxation, SIAM J. Optim., 23, 2, 1021-1040 (2013) · Zbl 1300.90017
[9] Basu, A.; Hildebrand, R.; Molinaro, M., Minimal cut-generating functions are nearly extreme, (Louveaux, Q.; Skutella, M., Integer Programming and Combinatorial Optimization: 18th International Conference, IPCO 2016, Liège, Belgium, June (2016) 1-3, Proceedings (2016), Springer International Publishing: Springer International Publishing Cham), 202-213 · Zbl 1419.90117
[10] Blair, C. E., Minimal inequalities for mixed integer programs, Discrete Math., 24, 2, 147-151 (1978) · Zbl 0399.90061
[11] Bruns, W.; Ichim, B.; Söger, C., The power of pyramid decomposition in normaliz, J. Symbolic Comput., 74, C, 513-536 (2016) · Zbl 1332.68298
[12] Conforti, M.; Cornuéjols, G.; Daniilidis, A.; Lemaréchal, C.; Malick, J., Cut-generating functions and s-free sets, Math. Oper. Res., 40, 2, 253-275 (2013)
[13] Gomory, R. E., Some polyhedra related to combinatorial problems, Linear Algebra Appl., 2, 451-558 (1969) · Zbl 0184.23103
[14] Gomory, R. E.; Johnson, E. L., Some continuous functions related to corner polyhedra, I, Math. Program., 3, 23-85 (1972) · Zbl 0246.90029
[15] Gomory, R. E.; Johnson, E. L., Some continuous functions related to corner polyhedra, II, Math. Program., 3, 359-389 (1972) · Zbl 0254.90036
[16] R. Hildebrand, M. Köppe, Y. Zhou, Equivariant perturbation in Gomory and Johnson’s infinite group problem. VIII. Grid-free extremality test—general algorithm and implementation, manuscript, 2018.
[17] R. Hildebrand, M. Köppe, Y. Zhou, On perturbation spaces of minimal valid functions: Inverse semigroup theory and equivariant decomposition theorem, in: Proc. IPCO 2019, 2018, 13 pages (in press). · Zbl 1436.90084
[18] Hildebrand, R.; Köppe, M.; Zhou, Y., Equivariant perturbation in Gomory and Johnson’s infinite group problem. VII. Inverse semigroup theory, closures, decomposition of perturbations (2018), e-print, 61 pages, arXiv:181106189
[19] Hong, C. Y.; Köppe, M.; Zhou, Y., Software for cut-generating functions in the Gomory-Johnson model and beyond, (Greuel, G.-M.; Koch, T.; Paule, P.; Sommese, A., Mathematical Software - ICMS 2016: 5th International Conference, Berlin, Germany, July 11-14, 2016, Proceedings (2016), Springer International Publishing), 284-291, Software available from https://github.com/mkoeppe/cutgeneratingfunctionology · Zbl 1434.68706
[20] Hong, C. Y.; Köppe, M.; Zhou, Y., Equivariant perturbation in Gomory and Johnson’s infinite group problem (V). Software for the continuous and discontinuous 1-row case, Optim. Methods Softw., 33, 3, 475-498 (2018) · Zbl 1397.90273
[21] Jeroslow, R. G., Minimal inequalities, Math. Program., 17, 1, 1-15 (1979) · Zbl 0437.90063
[22] Kılınç-Karzan, F.; Yang, B., Sufficient conditions and necessary conditions for the sufficiency of cut-generating functions (2015), http://www.andrew.cmu.edu/user/fkilinc/files/draft-sufficiency-web.pdf
[23] Köppe, M.; Zhou, Y., An electronic compendium of extreme functions for the Gomory-Johnson infinite group problem, Oper. Res. Lett., 43, 4, 438-444 (2015) · Zbl 1408.90002
[24] Köppe, M.; Zhou, Y., Toward computer-assisted discovery and automated proofs of cutting plane theorems, (Cerulli, R.; Fujishige, S.; Mahjoub, A. R., Combinatorial Optimization: 4th International Symposium, ISCO 2016, Vietri sul Mare, Italy, May 16-18, 2016, Revised Selected Papers (2016), Springer International Publishing: Springer International Publishing Cham), 332-344 · Zbl 1445.68329
[25] Köppe, M.; Zhou, Y., New computer-based search strategies for extreme functions of the Gomory-Johnson infinite group problem, Math. Program. Comput., 9, 3, 419-469 (2017) · Zbl 1387.90138
[26] Köppe, M.; Zhou, Y., Equivariant perturbation in Gomory and Johnson’s infinite group problem. VI. The curious case of two-sided discontinuous minimal valid functions, Discrete Optim., 30, 51-72 (2018) · Zbl 1454.90034
[27] Köppe, M.; Zhou, Y.; Hong, C. Y.; Wang, J., Cutgeneratingfunctionology: sage code for computation and experimentation with cut-generating functions, in particular the Gomory-Johnson infinite group problem (2019), https://github.com/mkoeppe/cutgeneratingfunctionology, (Version 13)
[28] Lueker, G. S., Bin packing with items uniformly distributed over intervals [a, b], (Proceedings of the 24th Annual Symposium on Foundations of Computer Science (Washington, DC, USA), SFCS ’83 (1983), IEEE Computer Society), 289-297
[29] Stein, W. A., Sage mathematics software (version 71) (2016), The Sage Development Team, http://www.sagemath.org
[30] Vanderbeck, F., Exact algorithm for minimising the number of setups in the one-dimensional cutting stock problem, Oper. Res., 48, 6, 915-926 (2000) · Zbl 1106.90373
[31] Yıldız, S.; Cornuéjols, G., Cut-generating functions for integer variables, Math. Oper. Res., 41, 4, 1381-1403 (2016) · Zbl 1349.90638
[32] Zhou, Y., Infinite-dimensional relaxations of mixed-integer optimization problems (2017), University of California, Davis, Graduate Group in Applied Mathematics, Available from https://search.proquest.com/docview/1950269648
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.