Computational aspects of relaxation complexity. (English) Zbl 1497.90223
Singh, Mohit (ed.) et al., Integer programming and combinatorial optimization. 22nd international conference, IPCO 2021, Atlanta, GA, USA, May 19–21, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12707, 368-382 (2021).
This article considers the relaxation complexity of a set of integer points that are contained inside the facets of a linear polyhedron. This is of importance for integer programming as good relaxation methods result in more efficient solution algorithms. The authors begin with an introduction to the problem and a number of definitions and background theorems. They then derive estimations of the relaxation complexity, that is the smallest number of facets which coincide with the integer points of the polyhedron, including a variant where the relaxation complexity is calculated using rational polyhedra. Several interesting theorems are presented with proof and detailed examples help to understand the propositions. Some numerical experiments on the calculation of the number of facets are presented at the end of the article.
For the entire collection see [Zbl 1476.90004].
For the entire collection see [Zbl 1476.90004].
Reviewer: Efstratios Rappos (Aubonne)
MSC:
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 90C10 | Integer programming |
| 90C27 | Combinatorial optimization |
| 90C11 | Mixed integer programming |
| 90C25 | Convex programming |
| 52B05 | Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) |
| 52B12 | Special polytopes (linear programming, centrally symmetric, etc.) |
Software:
relaxation_complexityReferences:
| [1] | Averkov, G., Schymura, M.: Complexity of linear relaxations in integer programming. Mathematical Programming (2021). doi:10.1007/s10107-021-01623-4, (online first) · Zbl 1497.90223 |
| [2] | Castryck, W., Moving out the edges of a lattice polygon, Discrete Comput. Geom., 47, 3, 496-518 (2012) · Zbl 1237.52002 · doi:10.1007/s00454-011-9376-2 |
| [3] | van der Corput, JG, Verallgemeinerung einer Mordellschen Beweismethode in der Geometrie der Zahlen II, Acta Arith., 2, 145-146 (1936) · Zbl 0015.29404 · doi:10.4064/aa-2-1-145-146 |
| [4] | Edelsbrunner, H.: Algorithms in Combinatorial Geometry. Monographs in Theoretical Computer Science, vol. 10. Springer-Verlag, Berlin Heidelberg (1987). doi:10.1007/978-3-642-61568-9 · Zbl 0634.52001 |
| [5] | Edelsbrunner, H.; Preparata, FP, Minimum polygonal separation, Inform. Comput., 77, 218-232 (1988) · Zbl 0642.52004 · doi:10.1016/0890-5401(88)90049-1 |
| [6] | Gamrath, G., et al.: The SCIP Optimization Suite 7.0. Technical report, Optimization Online, March 2020. http://www.optimization-online.org/DB_HTML/2020/03/7705.html |
| [7] | Hammer, P.L., Ibaraki, T., Peled, U.N.: Threshold numbers and threshold completions. In: Studies on Graphs and Discrete Programming (Brussels, 1979), Annals of Discrete Mathematics, vol. 11, pp. 125-145. North-Holland, Amsterdam-New York (1981) · Zbl 0482.05060 |
| [8] | Hojny, C., Polynomial size IP formulations of knapsack may require exponentially large coefficients, Oper. Res. Lett., 48, 5, 612-618 (2020) · Zbl 1479.90136 · doi:10.1016/j.orl.2020.07.013 |
| [9] | Hojny, C.: Strong IP formulations need large coefficients. Discrete Optim. 39, 100624 (2021). doi:10.1016/j.disopt.2021.100624 · Zbl 1474.90293 |
| [10] | Jeroslow, RG, On defining sets of vertices of the hypercube by linear inequalities, Discrete Math., 11, 119-124 (1975) · Zbl 0297.52009 · doi:10.1016/0012-365X(75)90003-5 |
| [11] | Kaibel, V., Weltge, S.: Lower bounds on the sizes of integer programs without additional variables. Math. Program. 154(1-2, Ser. B), 407-425 (2015) · Zbl 1338.52013 |
| [12] | Lee, C.; Lee, D., On a circle-cover minimization problem, Inf. Process. Lett., 18, 2, 109-115 (1984) · Zbl 0534.68049 · doi:10.1016/0020-0190(84)90033-4 |
| [13] | Maher, S.; Miltenberger, M.; Pedroso, JP; Rehfeldt, D.; Schwarz, R.; Serrano, F.; Greuel, G-M; Koch, T.; Paule, P.; Sommese, A., PySCIPOpt: mathematical programming in Python with the SCIP optimization suite, Mathematical Software - ICMS 2016, 301-307 (2016), Cham: Springer, Cham · Zbl 1434.90005 · doi:10.1007/978-3-319-42432-3_37 |
| [14] | Megiddo, N., On the complexity of polyhedral separability, Discrete Comput. Geom., 3, 325-337 (1988) · Zbl 0669.68035 · doi:10.1007/BF02187916 |
| [15] | Pokutta, S.; Van Vyve, M., A note on the extension complexity of the knapsack polytope, Oper. Res. Lett., 41, 4, 347-350 (2013) · Zbl 1286.90168 · doi:10.1016/j.orl.2013.03.010 |
| [16] | Schrijver, A.: Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics, A Wiley-Interscience Publication, John Wiley & Sons Ltd, Chichester (1986) · Zbl 0665.90063 |
| [17] | Taylor, AD; Zwicker, WS, Simple Games: Desirability Relations, Trading, Pseudoweightings (1999), Princeton: Princeton University Press, Princeton · Zbl 0943.91005 |
| [18] | The Sage Developers: SageMath, the Sage Mathematics Software System (Version 9.1) (2020). https://www.sagemath.org |
| [19] | Weltge, S.: Sizes of Linear Descriptions in Combinatorial Optimization. Ph.D. thesis, Otto-von-Guericke-Universität Magdeburg (2015). doi:10.25673/4350 |
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.
