On Merging Cover Inequalities for Multiple Knapsack Problems

DOI: 10.4236/ojop.2015.44014   PDF   HTML   XML   3,320 Downloads   4,018 Views   Citations

Abstract

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.

Share and Cite:

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.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[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.
http://dx.doi.org/10.1007/s10732-005-2634-9
[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.
http://dx.doi.org/10.1016/j.cor.2010.10.021
[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.
http://dx.doi.org/10.1023/A:1009894503716
[4] Dizdar, D., Gershkov, A. and Moldovanu, B. (2011) Revenue Maximization in the Dynamic Knapsack Problem. Theoretical Economics, 6, 157-184.
http://dx.doi.org/10.3982/TE700
[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.
http://dx.doi.org/10.1007/s00453-008-9248-1
[6] Martello, S. and Toth, P. (1987) Algorithms for Knapsack Problems. Annals of Discrete Mathematics, 31, 213-257.
http://dx.doi.org/10.1016/s0304-0208(08)73237-7
[7] Shachnai, H. and Tamir, T. (2001) On Two Class-Constrained Versions of the Multiple Knapsack Problem. Algorithmica, 29, 442-467.
http://dx.doi.org/10.1007/s004530010057
[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.
http://dx.doi.org/10.1002/9781118627372
[10] Balas, E and Zemel, E. (1978) Facets of the Knapsack Polytope from Minimal Covers. SIAM Journal of Applied Mathematics, 34, 119-148.
http://dx.doi.org/10.1137/0134010
[11] De Farias Jr., I., Johnson, E. and Nemhauser, G. (2002) Facets of the Complementarity Knapsack Polytope. Mathematics of Operations Research, 27, 210-227.
http://dx.doi.org/10.1287/moor.27.1.210.335
[12] Louveaux, Q. and Weismantel, R. (2010) Polyhedral Properties for the Intersection of Two Knapsacks. Mathematical Programming Series A, 113, 15-37.
http://dx.doi.org/10.1007/s10107-006-0045-9
[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.
http://dx.doi.org/10.1016/0167-6377(94)90038-8
[14] Park, K. (1997) Lifting Cover Inequalities for the Precedence-Constrained Knapsack Problem. Discrete Applied Mathematics, 72, 219-241.
http://dx.doi.org/10.1016/0166-218X(95)00113-6
[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.
http://dx.doi.org/10.1007/BF01584074
[16] Gauthier, J.M. and Ribiere, G. (1977) Experiments in Mixed-Integer Linear Programming Using Pseudo-Costs. Mathematical Programming, 12, 26-47.
http://dx.doi.org/10.1007/BF01593767
[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.
http://dx.doi.org/10.1007/978-3-540-30201-8_41
[18] Achterberg, T., Koch, T. and Martin, A. (2005) Branching Rules Revisited. Operations Research Letters, 33, 42-54.
http://dx.doi.org/10.1016/j.orl.2004.04.002
[19] Gomory, R. (1969) Some Polyhedra Related to Combinatorial Problems. Linear Algebra and Its Applications, 2, 451-558.
http://dx.doi.org/10.1016/0024-3795(69)90017-2
[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.
http://dx.doi.org/10.1287/moor.8.4.590
[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.
http://dx.doi.org/10.1007/BF01580442
[23] Wolsey, L. (1975) Faces for a Linear Inequality in 0-1 Variables. Mathematical Programming, 8, 165-178.
http://dx.doi.org/10.1007/BF01580441
[24] Easton, T. and Hooker, K. (2008) Simultaneously Lifting Sets of Binary Variables into Cover Inequalities for Knapsack Polytopes. Discrete Optimization, 5, 254-261.
http://dx.doi.org/10.1016/j.disopt.2007.05.003
[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.
http://dx.doi.org/10.1007/BF01609032
[27] Atamtürk, A. (2003) On the Facets of the Mixed-Integer Knapsack Polyhedron. Mathematical Programming, 98, 145-175.
http://dx.doi.org/10.1007/s10107-003-0400-z
[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.
http://dx.doi.org/10.1287/ijoc.10.4.427
[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.
http://dx.doi.org/10.1287/ijoc.11.1.117
[30] Gu, Z., Nemhauser, G. and Savelsbergh, M. (2000) Sequence Independent Lifting in Mixed Integer Programming. Journal of Combinatorial Optimization, 4, 109-129.
http://dx.doi.org/10.1023/A:1009841107478
[31] Shebalov, S. and Klabjan, D. (2006) Sequence Independent Lifting for Mixed Integer Programs with Variable Upper Bounds. Mathematical Programming, 105, 523-561.
http://dx.doi.org/10.1007/s10107-005-0664-6
[32] Balas, E. (1975) Facets of the Knapsack Polytope. Mathematical Programming, 8, 146-164.
http://dx.doi.org/10.1007/BF01580440
[33] Weismantel, R. (1997) On the 0/1 Knapsack Polytope. Mathematical Programming, 77, 49-68.
http://dx.doi.org/10.1007/BF02614517
[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.
http://dx.doi.org/10.1287/opre.24.2.367
[36] Chvátal, V. (1973) Edmonds Polytopes and a Hierarchy of Combinatorial Problems. Discrete Mathematics, 4, 305-337.
http://dx.doi.org/10.1016/0012-365X(73)90167-2
[37] Gomory, R. (1958) Outline of an Algorithm for Integer Solutions to Linear Programs. Bulletin of the American Mathematical Society, 64, 275-278.
http://dx.doi.org/10.1090/S0002-9904-1958-10224-4
[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.
http://dx.doi.org/10.1007/s10107-002-0317-y
[39] Gomory, R. and Johnson, E.L. (1972) Some Continuous Functions Related to Corner Polyhedra 1. Mathematical Programming, 3, 23-85.
http://dx.doi.org/10.1007/BF01584976
[40] Wolsey, L. (1977) Valid Inequalities and Superadditivity of 0/1 Integer Programs. Mathematics of Operations Research, 2, 66-77.
http://dx.doi.org/10.1287/moor.2.1.66
[41] OR Library Webpage (2013).
http://people.brunel.ac.uk/~mastjjb/jeb/info.html
[42] Chu, P.C. and Beasley, J.E. (1998) A Genetic Algorithm for the Multidimensional Knapsack Problem. Journal of Heuristics, 4, 63-86.
http://dx.doi.org/10.1023/A:1009642405419
[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.
http://www-01.ibm.com/software/info/ilog/
[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.
http://dx.doi.org/10.1145/1629911.1630132

  
comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.