Share This Article:

On Merging Cover Inequalities for Multiple Knapsack Problems

Abstract Full-Text HTML XML Download Download as PDF (Size:530KB) PP. 141-155
DOI: 10.4236/ojop.2015.44014    3,152 Downloads   3,665 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.

Conflicts of Interest

The authors declare no conflicts of interest.

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.

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 © 2019 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.