OJOp  Vol.4 No.4 , December 2015
On Merging Cover Inequalities for Multiple Knapsack Problems
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.


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

 
 
Top