Lifting for the integer knapsack cover polyhedron. (English) Zbl 1518.90051
Summary: We consider the integer knapsack cover polyhedron which is the convex hull of the set consisting of \(n\)-dimensional nonnegative integer vectors that satisfy one linear constraint. We study the sequentially lifted (SL) inequality, derived by the sequential lifting from a seed inequality containing a single variable, and provide bounds on the lifting coefficients, which is useful in solving the separation problem of the SL inequalities. The proposed SL inequality is shown to dominate the well-known mixed integer rounding (MIR) inequality under certain conditions. We show that the problem of computing the coefficients for an SL inequality is \(\mathcal{NP}\)-hard but can be solved by a pseudo-polynomial time algorithm. As a by-product of analysis, we provide new conditions to guarantee the MIR inequality to be facet-defining for the considered polyhedron and prove that in general, the problem of deciding whether an MIR inequality defines a facet is \(\mathcal{NP}\)-complete. Finally, we perform numerical experiments to evaluate the performance and impact of using the proposed SL inequalities as cutting planes in solving mixed integer linear programming problems. Numerical results demonstrate that the proposed SL cuts are much more effective than the MIR cuts in terms of strengthening the problem formulation and improving the solution efficiency. Moreover, when applied to solve random and real application problems, the proposed SL cuts demonstrate the benefit in reducing the solution time.
Keywords:
integer programming; cutting plane; sequential lifting; MIR inequality; separation algorithmReferences:
| [1] | Achterberg, T.: Constraint integer programming. Ph.D. Thesis, Technische Universität Berlin (2007) · Zbl 1430.90427 |
| [2] | Achterberg, T.; Raack, C., The MCF-separator: detecting and exploiting multi-commodity flow structures in MIPs, Math. Program. Comput., 2, 2, 125-165 (2010) · Zbl 1200.65042 |
| [3] | Achterberg, T.; Wunderling, R.; Jünger, M.; Reinelt, G., Mixed integer programming: analyzing 12 years of progress, Facets of Combinatorial Optimization: Festschrift for Martin Grötschel, 449-481 (2013), Berlin: Springer, Berlin · Zbl 1317.90206 |
| [4] | Agra, A.; Constantino, MF, Lifting two-integer knapsack inequalities, Math. Program., 109, 1, 115-154 (2007) · Zbl 1278.90453 |
| [5] | Andreello, G.; Caprara, A.; Fischetti, M., Embedding \(\{0,\frac{1}{2}\} \)-cuts in a branch-and-cut framework: a computational study, Informs J. Comput., 19, 2, 229-238 (2007) · Zbl 1241.90181 |
| [6] | Angulo, A.; Espinoza, D.; Palma, R., Sequence independent lifting for mixed knapsack problems with GUB constraints, Math. Program., 154, 1, 55-80 (2015) · Zbl 1327.90123 |
| [7] | Atamtürk, A., Sequence independent lifting for mixed-integer programming, Oper. Res., 52, 3, 487-490 (2004) · Zbl 1165.90576 |
| [8] | Atamtürk, A., Cover and pack inequalities for (mixed) integer programming, Ann. Oper. Res., 139, 1, 21-38 (2005) · Zbl 1091.90053 |
| [9] | Atamtürk, A.; Günlük, O., Mingling: mixed-integer rounding with bounds, Math. Program., 123, 2, 315-338 (2010) · Zbl 1190.90104 |
| [10] | Atamtürk, A.; Kianfar, K., N-step mingling inequalities: new facets for the mixed-integer knapsack set, Math. Program., 132, 1-2, 79-98 (2012) · Zbl 1247.90202 |
| [11] | Atamtürk, A.; Rajan, D., On splittable and unsplittable flow capacitated network design arc-set polyhedra, Math. Program. Ser. B, 92, 2, 315-333 (2002) · Zbl 1094.90005 |
| [12] | Caprara, A.; Fischetti, M., \(\{0,\frac{1}{2}\} \)-Chvátal-Gomory cuts, Math. Program., 74, 3, 221-235 (1996) · Zbl 0855.90088 |
| [13] | Ceria, S.; Cordier, C.; Marchand, H.; Wolsey, LA, Cutting planes for integer programs with general integer variables, Math. Program. Ser. B, 81, 2, 201-214 (1998) · Zbl 0919.90113 |
| [14] | Chen, W.-K., Dai, Y.-H.: Combinatorial separation algorithms for the continuous knapsack polyhedra with divisible capacities. Technical report (2019). https://arxiv.org/abs/1907.03162 |
| [15] | Chen, W-K; Dai, Y-H, On the complexity of sequentially lifting cover inequalities for the knapsack polytope, Sci. China Math., 64, 1, 211-220 (2021) · Zbl 1467.90022 |
| [16] | Christophel, P.M.: Separation algorithms for cutting planes based on mixed integer row relaxations. Ph.D. Thesis, Universität Paderborn, Paderborn (2009) |
| [17] | Crowder, H.; Johnson, EL; Padberg, M., Solving large-scale zero-one linear programming problems, Oper. Res., 31, 5, 803-834 (1983) · Zbl 0576.90065 |
| [18] | Dash, S.; Günlük, O., Valid inequalities based on simple mixed-integer sets, Math. Program., 105, 1, 29-53 (2006) · Zbl 1085.90034 |
| [19] | Easton, T.; Gutierrez, T., Sequential lifting of general integer variables for integer programs, Ind. Eng. Manag, 4, 2, 158 (2015) |
| [20] | Eisenbrand, F.; Laue, S., A linear algorithm for integer programming in the plane, Math. Program., 102, 2, 249-259 (2005) · Zbl 1079.90581 |
| [21] | Fukasawa, R.: Single-row mixed-integer programs: theory and computations. Ph.D. Thesis, Georgia Institute of Technology (2008) |
| [22] | Gleixner, A.; Hendel, G.; Gamrath, G.; Achterberg, T.; Bastubbe, M.; Berthold, T.; Christophel, P.; Jarck, K.; Koch, T.; Linderoth, J.; Lübbecke, M.; Mittelmann, HD; Ozyurt, D.; Ralphs, TK; Salvagnin, D.; Shinano, Y., MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library, Math. Program. Comput., 13, 3, 443-490 (2021) · Zbl 1476.90191 |
| [23] | Gleixner, A., Maher, S. J., Fischer, T., Gally, T., Gamrath, G., Gottwald, R. L., Hendel, R. L., Koch, T., Lübbecke, M. E., Miltenberger, M., Müller, B., Pfetsch, M. E., Puchert, C., Rehfeldt, D., Schenker, S., Schwarz, R., Serrano, F., Shinano, Y., Weninger, D., Witt, J. T., Witzig, J.: The SCIP optimization suite 6.0. ZIB-Report (2018). https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6936 |
| [24] | Gu, Z.; Nemhauser, GL; Savelsbergh, MWP, Lifted cover inequalities for 0-1 integer programs: computation, Informs J. Comput., 10, 4, 427-437 (1998) |
| [25] | Gu, Z.; Nemhauser, GL; Savelsbergh, MWP, Sequence independent lifting in mixed integer programming, J. Comb. Optim., 4, 1, 109-129 (2000) · Zbl 0964.90030 |
| [26] | Hirschberg, DS; Wong, CK, A polynomial-time algorithm for the knapsack problem with two variables, J. ACM, 12, 1, 147-154 (1976) · Zbl 0345.90048 |
| [27] | Hojny, C.; Gally, T.; Habeck, O.; Lüthen, H.; Matter, F.; Pfetsch, ME; Schmitt, A., Knapsack polytopes: a survey, Ann. Oper. Res., 292, 1, 469-517 (2020) · Zbl 1456.90133 |
| [28] | Kannan, R., A polynomial algorithm for the two-variable integer programming problem, J. ACM, 27, 1, 118-122 (1980) · Zbl 0423.90052 |
| [29] | Kaparis, K.; Letchford, AN, Separation algorithms for 0-1 knapsack polytopes, Math. Program., 124, 1-2, 69-91 (2010) · Zbl 1198.90297 |
| [30] | Kellerer, H.; Pferschy, U.; Pisinger, D., Knapsack Problems (2004), Berlin: Springer, Berlin · Zbl 1103.90003 |
| [31] | Kianfar, K., On n-step MIR and partition inequalities for integer knapsack and single-node capacitated flow sets, Discret. Appl. Math., 160, 10, 1567-1582 (2012) · Zbl 1245.90065 |
| [32] | Kianfar, K.; Fathi, Y., Generalized mixed integer rounding inequalities: facets for infinite group polyhedra, Math. Program., 120, 2, 313-346 (2009) · Zbl 1176.90424 |
| [33] | Koch, T.; Achterberg, T.; Andersen, E.; Bastert, O.; Berthold, T.; Bixby, RE; Danna, E.; Gamrath, G.; Gleixner, AM; Heinz, S.; Lodi, A.; Mittelmann, H.; Ralphs, T.; Salvagnin, D.; Steffy, DE; Wolter, K., MIPLIB 2010, Math. Program. Comput., 3, 2, 103 (2011) |
| [34] | Koster, AMCA; Zymolka, A.; Kutschka, M., Algorithms to separate \(\{0,\frac{1}{2}\} \)-Chvátal-Gomory cuts, Algorithmica, 55, 2, 375-391 (2009) · Zbl 1189.90132 |
| [35] | Malaguti, E.; Durán, RM; Toth, P., A metaheuristic framework for nonlinear capacitated covering problems, Optim. Lett., 10, 1, 169-180 (2016) · Zbl 1339.90284 |
| [36] | Marchand, H.; Wolsey, LA, The 0-1 knapsack problem with a single continuous variable, Math. Program., 85, 1, 15-33 (1999) · Zbl 0956.90021 |
| [37] | Marchand, H.; Wolsey, LA, Aggregation and mixed integer rounding to solve MIPs, Oper. Res., 49, 3, 363-371 (2001) · Zbl 1163.90671 |
| [38] | Marcotte, O., The cutting stock problem and integer rounding, Math. Program., 33, 1, 82-92 (1985) · Zbl 0584.90063 |
| [39] | Martello, S., Knapsack Problems: Algorithms and Computer Implementations (1990), Chichester: Wiley, Chichester · Zbl 0708.68002 |
| [40] | Martin, A.: Integer Programs with Block Structure. Ph.D. Thesis, Technische Universität Berlin (1998) |
| [41] | Mazur, D. R.: Integer programming approaches to a multifacility location problem. Ph.D. Thesis, The Johns Hopkins University (1999) |
| [42] | Nemhauser, GL; Trotter, LE, Properties of vertex packing and independence system polyhedra, Math. Program., 6, 1, 48-61 (1974) · Zbl 0281.90072 |
| [43] | Nemhauser, GL; Wolsey, LA, Integer and Combinatorial Optimization (1988), New York: Wiley, New York · Zbl 0652.90067 |
| [44] | Nemhauser, GL; Wolsey, LA, A recursive procedure to generate all cuts for 0-1 mixed integer programs, Math. Program., 46, 1-3, 379-390 (1990) · Zbl 0735.90049 |
| [45] | Padberg, MW, On the facial structure of set packing polyhedra, Math. Program., 5, 1, 199-215 (1973) · Zbl 0272.90041 |
| [46] | Pochet, Y.; Wolsey, LA, Integer knapsack and flow covers with divisible coefficients: polyhedra, optimization and separation, Discret. Appl. Math., 59, 1, 57-74 (1995) · Zbl 0835.90052 |
| [47] | Richard, J-PP; de Farias Jr, IR; Nemhauser, GL, Lifted inequalities for 0-1 mixed integer programming: basic theory and algorithms, Math. Program., 98, 1, 89-113 (2003) · Zbl 1047.90033 |
| [48] | Richard, J-PP; de Farias Jr, IR; Nemhauser, GL, Lifted inequalities for 0-1 mixed integer programming: superlinear lifting, Math. Program., 98, 1, 115-143 (2003) · Zbl 1082.90065 |
| [49] | Richard, J.-P.P.: Lifting techniques for mixed integer programming. In: Wiley Encyclopedia of Operations Research and Management Science (2011) |
| [50] | Shebalov, S.; Klabjan, D., Sequence independent lifting for mixed integer programs with variable upper bounds, Math. Program., 105, 2, 523-561 (2006) · Zbl 1085.90037 |
| [51] | Van Hoesel, SPM; Koster, AMCA; Van De Leensel, RLMJ; Savelsbergh, MWP, Polyhedral results for the edge capacity polytope, Math. Program., 92, 2, 335-358 (2002) · Zbl 1046.90079 |
| [52] | Weismantel, R., On the 0/1 knapsack polytope, Math. Program., 77, 3, 49-68 (1997) · Zbl 0891.90130 |
| [53] | Wolsey, LA, Faces for a linear inequality in 0-1 variables, Math. Program., 8, 1, 165-178 (1975) · Zbl 0314.90063 |
| [54] | Wolsey, LA, Facets and strong valid inequalities for integer programs, Oper. Res., 24, 2, 367-372 (1976) · Zbl 0339.90036 |
| [55] | Wolsey, LA, Valid inequalities and superadditivity for 0-1 integer programs, Math. Oper. Res., 2, 1, 66-77 (1977) · Zbl 0402.90066 |
| [56] | Wolsey, LA; Yaman, H., Continuous knapsack sets with divisible capacities, Math. Program., 156, 1-2, 1-20 (2016) · Zbl 1333.90081 |
| [57] | Wolter, K.: Implementation of cutting plane separators for mixed integer programs. Diploma thesis, Technische Universität Berlin, Berlin (2006) |
| [58] | Yaman, H., Formulations and valid inequalities for the heterogeneous vehicle routing problem, Math. Program., 106, 2, 365-390 (2006) · Zbl 1134.90527 |
| [59] | Yaman, H., The integer knapsack cover polyhedron, SIAM J. Discret. Math., 21, 3, 551-572 (2007) · Zbl 1177.90298 |
| [60] | Yaman, H.; Şen, A., Manufacturer’s mixed pallet design problem, Eur. J. Oper. Res., 186, 2, 826-840 (2008) · Zbl 1138.90388 |
| [61] | Zemel, E., Easily computable facets of the knapsack polytope, Math. Oper. Res., 14, 4, 760-764 (1989) · Zbl 0689.90057 |
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.
