Binary extended formulations of polyhedral mixed-integer sets. (English) Zbl 1391.90425
Summary: We analyze different ways of constructing binary extended formulations of polyhedral mixed-integer sets with bounded integer variables and compare their relative strength with respect to split cuts. We show that among all binary extended formulations where each bounded integer variable is represented by a distinct collection of binary variables, what we call “unimodular” extended formulations are the strongest. We also compare the strength of some binary extended formulations from the literature. Finally, we study the behavior of branch-and-bound on such extended formulations and show that branching on the new binary variables leads to significantly smaller enumeration trees in some cases.
MSC:
| 90C11 | Mixed integer programming |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
Keywords:
mixed-integer programming; binarization; extended formulations; cutting planes; branch-and-boundSoftware:
CPLEXReferences:
| [1] | Angulo, A; Vyve, M, Fixed-charge transportation problems on trees, OR Lett., 45, 275-281, (2017) · Zbl 1409.90030 |
| [2] | Atamtürk, A, On the facets of the mixed-integer knapsack polyhedron, Math. Program. B, 98, 145-175, (2003) · Zbl 1082.90073 · doi:10.1007/s10107-003-0400-z |
| [3] | Balas, E, Disjunctive programming, Ann. Discrete Math., 5, 3-51, (1979) · Zbl 0409.90061 · doi:10.1016/S0167-5060(08)70342-X |
| [4] | Balas, E; Ceria, S; Cornuéjols, G, A lift-and-project cutting plane algorithm for mixed 0-1 programs, Math. Program., 58, 295-323, (1993) · Zbl 0796.90041 · doi:10.1007/BF01581273 |
| [5] | Bodur, M; Dash, S; Günlük, O, Cutting planes derived from extended LP formulations, Math. Program., 161, 159-192, (2017) · Zbl 1356.90089 · doi:10.1007/s10107-016-1005-7 |
| [6] | Bodur, M; Dash, S; Günlük, O; Luedtke, J, Strengthened benders cuts for stochastic integer programs with continuous recourse, INFORMS J. Comput., 29, 77-99, (2016) · Zbl 1364.90220 · doi:10.1287/ijoc.2016.0717 |
| [7] | Bonami, P; Margot, F, Cut generation through binarization, Math. Program. B, 154, 197-223, (2015) · Zbl 1327.90128 · doi:10.1007/s10107-015-0924-z |
| [8] | Conforti, M., Cornuejols, G., Zambelli, G.: Integer Programming. Springer, New York (2014) · Zbl 1307.90001 · doi:10.1007/978-3-319-11008-0 |
| [9] | Cook, WJ; Kannan, R; Schrijver, A, Chvátal closures for mixed integer programming problems, Math. Program., 47, 155-174, (1990) · Zbl 0711.90057 · doi:10.1007/BF01580858 |
| [10] | IBM ILOG-CPLEX. Cplex 12.7 User’s Manual (2017) |
| [11] | Dash, S; Günlük, O; Lodi, A, MIR closures of polyhedral sets, Mathem. Program., 121, 33-60, (2010) · Zbl 1184.90107 · doi:10.1007/s10107-008-0225-x |
| [12] | Dey, SS; Louveaux, Q, Split rank of triangle and quadrilateral inequalities, Mathem. Oper. Res., 26, 432-461, (2011) · Zbl 1242.90127 · doi:10.1287/moor.1110.0496 |
| [13] | Pia, A; Weismantel, R, On convergence in mixed integer programming, Math. Program., 135, 397-412, (2012) · Zbl 1254.90123 · doi:10.1007/s10107-011-0476-9 |
| [14] | Gomory, RE; Graves, RL (ed.); Wolfe, P (ed.), An algorithm for integer solutions to linear programs, 269-302, (1963), New York · Zbl 0235.90038 |
| [15] | Glover, F, Improved linear integer programming formulations of nonlinear integer problems, Manag. Sci., 22, 455-460, (1975) · Zbl 0318.90044 · doi:10.1287/mnsc.22.4.455 |
| [16] | Gupte, A; Ahmed, S; Cheon, M; Dey, S, Solving mixed integer bilinear problems using MILP formulations, SIAM J. Optim., 23, 721-744, (2013) · Zbl 1300.90021 · doi:10.1137/110836183 |
| [17] | Hildebrand, R., Weismantel, R., Zenklusen, R.: Extension complexity lower bounds for mixed-integer extended formulations. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2342-2350 (2017) · Zbl 1422.90028 |
| [18] | Laurent, M; Sassano, A, A characterizatoin of knapsacks with the MAX-flow MIN-cut property, Oper. Res. Lett., 11, 105-110, (1992) · Zbl 0773.90053 · doi:10.1016/0167-6377(92)90041-Z |
| [19] | Lovász, L; Schrijver, A, Cones of matrices and set-functions and 0-1 optimization, SIAM J. Optim., 1, 166-190, (1991) · Zbl 0754.90039 · doi:10.1137/0801013 |
| [20] | Owen, JH; Mehrotra, S, A disjunctive cutting plane procedure for general mixed-integer linear programs, Math. Program., 89, 437-448, (2001) · Zbl 1017.90066 · doi:10.1007/PL00011407 |
| [21] | Owen, JH; Mehrotra, S, On the value of binary expansions for general mixed-integer linear programs, Oper. Res., 50, 810-819, (2002) · Zbl 1163.90673 · doi:10.1287/opre.50.5.810.370 |
| [22] | Roy, JS, “binarize and project” to generate cuts for general mixed-integer programs, Algorithmic Oper. Res., 2, 37-51, (2007) · Zbl 1186.90081 |
| [23] | Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1986) · Zbl 0665.90063 |
| [24] | Sherali, HD; Adams, WP, A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM J. Discrete Math., 3, 411-430, (1990) · Zbl 0712.90050 · doi:10.1137/0403036 |
| [25] | Sherali, H.D., Adams, W.P.: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer Academic Publishers, Norwell (1999) · Zbl 0926.90078 · doi:10.1007/978-1-4757-4388-3 |
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.
