OJOp  Vol.4 No.4 , December 2015
On Merging Cover Inequalities for Multiple Knapsack Problems

This paper describes methods to merge two cover inequalities and also simultaneously merge multiple cover inequalities in a multiple knapsack instance. Theoretical results provide conditions under which merged cover inequalities are valid. Polynomial time algorithms are created to find merged cover inequalities. A computational study demonstrates that merged inequalities improve the solution times for benchmark multiple knapsack instances by about 9% on average over CPLEX with default settings.

Cite this paper
Hickman, R. and Easton, T. (2015) On Merging Cover Inequalities for Multiple Knapsack Problems. Open Journal of Optimization, 4, 141-155. doi: 10.4236/ojop.2015.44014.
[1]   Ahuja, R. and Cunha, C. (2005) Very Large-Scale Neighborhood Search for the K-Constraint Multiple Knapsack Problem. Journal of Heuristics, Special Issue: Supply Chain and Distribution Management, 11, 465-481.

[2]   Chang, P. and Lee, J. (2012) A Fuzzy DEA and Knapsack Formulation Integrated Model for Project Selection. Computers and Operations Research, 39, 112-125.

[3]   Dawande, M., Kalagnanam, J., Keskinocak, P., Ravi, R. and Salman, F.S. (2000) Approximation Algorithms for the Multiple Knapsack Problem with Assignment Restrictions. Journal of Combinatorial Optimization, 4, 171-186.

[4]   Dizdar, D., Gershkov, A. and Moldovanu, B. (2011) Revenue Maximization in the Dynamic Knapsack Problem. Theoretical Economics, 6, 157-184.

[5]   Kellerer, H. and Strusevich, V.A. (2010) Fully Polynomial Approximation Schemes for a Symmetric Quadratic Knapsack Problem and its Scheduling Applications. Algorithmica, 57, 769-795.

[6]   Martello, S. and Toth, P. (1987) Algorithms for Knapsack Problems. Annals of Discrete Mathematics, 31, 213-257.

[7]   Shachnai, H. and Tamir, T. (2001) On Two Class-Constrained Versions of the Multiple Knapsack Problem. Algorithmica, 29, 442-467.

[8]   Szeto, K.Y. and Lo, M.H. (2004) An Application of Adaptive Genetic Algorithm in Financial Knapsack Problem. In: Innovations in Applied Artificial Intelligence, Lecture Notes in Computer Science, Springer, Berlin/Heidelberg, 1220-1228. http://dx.doi.org/10.1007/978-3-540-24677-0_125

[9]   Nemhauser, G. and Wolsey, L. (1988) Integer and Combinatorial Optimization. John Wiley and Sons, New York.

[10]   Balas, E and Zemel, E. (1978) Facets of the Knapsack Polytope from Minimal Covers. SIAM Journal of Applied Mathematics, 34, 119-148.

[11]   De Farias Jr., I., Johnson, E. and Nemhauser, G. (2002) Facets of the Complementarity Knapsack Polytope. Mathematics of Operations Research, 27, 210-227.

[12]   Louveaux, Q. and Weismantel, R. (2010) Polyhedral Properties for the Intersection of Two Knapsacks. Mathematical Programming Series A, 113, 15-37.

[13]   Nemhauser, G. and Vance, P. (1994) Lifted Cover Facets of the 0-1 Knapsack Polytope with GUB Constraints. Operations Research Letters, 16, 255-263.

[14]   Park, K. (1997) Lifting Cover Inequalities for the Precedence-Constrained Knapsack Problem. Discrete Applied Mathematics, 72, 219-241.

[15]   Benichou, M., Gauthier, J.M., Girodet, P., Hentges, G., Ribiere, G. and Vincent. O. (1971) Experiments in Mixed-Integer Linear Programming. Mathematical Programming, 1, 76-94.

[16]   Gauthier, J.M. and Ribiere, G. (1977) Experiments in Mixed-Integer Linear Programming Using Pseudo-Costs. Mathematical Programming, 12, 26-47.

[17]   Refalo, P. (2004) Impact-Based Search Strategies for Constraint Programming. In: Wallace, M., Ed., Principles and Practice of Constraint Programming—CP 2004, Lecture Notes in Computer Science, Vol. 3258, Springer, Berlin, 557-571.

[18]   Achterberg, T., Koch, T. and Martin, A. (2005) Branching Rules Revisited. Operations Research Letters, 33, 42-54.

[19]   Gomory, R. (1969) Some Polyhedra Related to Combinatorial Problems. Linear Algebra and Its Applications, 2, 451-558.

[20]   Cho, C., Padberg, D. and Rao, M. (1983) On the Uncapacitated Plant Location Problem. II. Facets and Lifting Theorems. Mathematics of Operations Research, 8, 590-612.

[21]   Easton, T. and Gutierrez, T. (2015) Sequential Lifting of General Integer Variables. Industrial Engineering and Management, 4, 158.

[22]   Hammer, P.L., Johnson, E.L. and Peled, U.N. (1975) Facets of Regular 0-1 Polytopes. Mathematical Programming, 8, 179-206.

[23]   Wolsey, L. (1975) Faces for a Linear Inequality in 0-1 Variables. Mathematical Programming, 8, 165-178.

[24]   Easton, T. and Hooker, K. (2008) Simultaneously Lifting Sets of Binary Variables into Cover Inequalities for Knapsack Polytopes. Discrete Optimization, 5, 254-261.

[25]   Kubik, L. (2009) Simultaneously Lifting Multiple Sets in Binary Knapsack Integer Programs. MS Thesis, Department of Industrial and Manufacturing Systems Engineering, Kansas State University, Manhattan.

[26]   Zemel, E. (1978) Lifting the Facets of 0-1 Polytopes. Mathematical Programming, 15, 268-277.

[27]   Atamtürk, A. (2003) On the Facets of the Mixed-Integer Knapsack Polyhedron. Mathematical Programming, 98, 145-175.

[28]   Gu, Z., Nemhauser, G. and Savelsbergh, M. (1998) Lifted Cover Inequalities for 0-1 Integer Programs: Computation. INFORMS Journal on Computing, 10, 427-437.

[29]   Gu, Z., Nemhauser, G. and Savelsbergh, M. (1999) Lifted Cover Inequalities for 0-1 Integer Programs: Complexity. INFORMS Journal on Computing, 11, 117-123.

[30]   Gu, Z., Nemhauser, G. and Savelsbergh, M. (2000) Sequence Independent Lifting in Mixed Integer Programming. Journal of Combinatorial Optimization, 4, 109-129.

[31]   Shebalov, S. and Klabjan, D. (2006) Sequence Independent Lifting for Mixed Integer Programs with Variable Upper Bounds. Mathematical Programming, 105, 523-561.

[32]   Balas, E. (1975) Facets of the Knapsack Polytope. Mathematical Programming, 8, 146-164.

[33]   Weismantel, R. (1997) On the 0/1 Knapsack Polytope. Mathematical Programming, 77, 49-68.

[34]   Hickman, R. and Easton, T. (2015) Merging Valid Inequalities over the Multiple Knapsack Polyhedron. International Journal of Operations Research, 24, 214-227. http://dx.doi.org/10.1504/IJOR.2015.071495

[35]   Wolsey, L. (1976) Facets and Strong Valid Inequalities for Integer Programs. Operations Research, 24, 367-372.

[36]   Chvátal, V. (1973) Edmonds Polytopes and a Hierarchy of Combinatorial Problems. Discrete Mathematics, 4, 305-337.

[37]   Gomory, R. (1958) Outline of an Algorithm for Integer Solutions to Linear Programs. Bulletin of the American Mathematical Society, 64, 275-278.

[38]   Balas, E. and Perregaard, M. (2003) A Precise Correspondence Between Lift-and-Project Cuts, Simple Disjunctive Cuts, and Mixed Integer Gomory Cuts for 0-1 Programming. Mathematical Programming, 94, 221-245.

[39]   Gomory, R. and Johnson, E.L. (1972) Some Continuous Functions Related to Corner Polyhedra 1. Mathematical Programming, 3, 23-85.

[40]   Wolsey, L. (1977) Valid Inequalities and Superadditivity of 0/1 Integer Programs. Mathematics of Operations Research, 2, 66-77.

[41]   OR Library Webpage (2013).

[42]   Chu, P.C. and Beasley, J.E. (1998) A Genetic Algorithm for the Multidimensional Knapsack Problem. Journal of Heuristics, 4, 63-86.

[43]   Hickman, R. (2014) Generating Cutting Planes through Inequality Merging for Integer Programming Problems. PhD Dissertation, Department of Industrial and Manufacturing Systems Engineering, Kansas State University, Manhattan.

[44]   IBM (2013) ILOG CPLEX Optimizer, Version 12.5.1.

[45]   Fischetti, M., Lodi, A., Monaci, M., Salvagnin, D. and Tramontani, A. (2013) Tree Search Stabilization by Random Sampling. Technical Report OR/13/5, DEI, University of Bologna, Bologna.

[46]   Ju, L., Huynh, B.K., Chakraborty, S. and Roychoudhury, A. (2009) Context-Sensitive Timing Analysis of Esterel Programs. Proceedings of the 46th Annual Design Automation Conference, San Francisco, 26-31 July 2009, 870-873.