On the exact separation of mixed integer knapsack cuts. (English) Zbl 1218.90126
Summary: During the last decades, much research has been conducted on deriving classes of valid inequalities for mixed integer knapsack sets, which we call knapsack cuts. Bixby et al. (2004) empirically observe that, within the context of branch-and-cut algorithms to solve mixed integer programming problems, the most important inequalities are knapsack cuts derived by the mixed integer rounding (MIR) procedure. In this work we analyze this empirical observation by developing an algorithm to separate over the convex hull of a mixed integer knapsack set. The main feature of this algorithm is a specialized subroutine for optimizing over a mixed integer knapsack set which exploits dominance relationships. The exact separation of knapsack cuts allows us to establish natural benchmarks by which to evaluate specific classes of them. Using these benchmarks on MIPLIB 3.0 and MIPLIB 2003 instances we analyze the performance of MIR inequalities. Our computations, which are performed in exact arithmetic, are surprising: In the vast majority of the instances in which knapsack cuts yield bound improvements, MIR cuts alone achieve over 87% of the observed gain.
MSC:
| 90C10 | Integer programming |
| 90C11 | Mixed integer programming |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
References:
| [1] | Achterberg, T., Koch, T., Martin, A.: MIPLIB 2003. Oper. Res. Lett. 34(4), 1–12 (2006). doi: 10.1016/j.orl.2005.07.009 . http://www.zib.de/Publications/abstracts/ZR-05-28/ . See http://miplib.zib.de |
| [2] | Andonov R., Poirriez V., Rajopadhye S.: Unbounded knapsack problem: dynamic programming revisited. Eur. J. Oper. Res. 123, 394–407 (2000) · Zbl 0961.90123 · doi:10.1016/S0377-2217(99)00265-9 |
| [3] | Applegate D., Bixby R.E., Chvátal V., Cook W.: TSP cuts which do not conform to the template paradigm. In: (eds) Computational Combinatorial Optimization, Optimal or Provably Near-Optimal Solutions [based on a Spring School], pp. 261–304. Springer-Verlag GmbH, London (2001) · Zbl 1052.90060 |
| [4] | Applegate D., Cook W., Dash S., Espinoza D.: Exact solutions to linear programming problems. Oper. Res. Lett. 35, 693–699 (2007) · Zbl 1177.90282 · doi:10.1016/j.orl.2006.12.010 |
| [5] | Atamtürk A.: On the facets of the mixed–integer knapsack polyhedron. Math. Program. 98, 145–175 (2003) · Zbl 1082.90073 · doi:10.1007/s10107-003-0400-z |
| [6] | Atamtürk A.: Sequence independent lifting for mixed–integer programming. Oper. Res. 52, 487–490 (2004) · Zbl 1165.90576 · doi:10.1287/opre.1030.0099 |
| [7] | Avella, P., Boccia, M., Vasilyev, I.: A computational study of exact knapsack separation for the generalized assignment problem. Technical report available at Optimization Online (2006) · Zbl 1190.90153 |
| [8] | Balas E., Perregaard M.: A precise correspondence between lift-and-project cuts, simple disjuntive cuts, and mixed integer Gomory cuts for 0–1 programming. Math. Program. 94, 221–245 (2003) · Zbl 1030.90068 · doi:10.1007/s10107-002-0317-y |
| [9] | Balas E., Saxena A.: Optimizing over the split closure. Math. Program. 113(2), 219–240 (2008) · Zbl 1135.90030 · doi:10.1007/s10107-006-0049-5 |
| [10] | Balas E., Zemel E.: Facets of knapsack polytope from minimal covers. SIAM J. Appl. Math. 34(1), 119–148 (1978) · Zbl 0385.90083 · doi:10.1137/0134010 |
| [11] | Bellman R.E.: Dynamic Programming. Princeton University Press, Princeton (1957) · Zbl 0077.13605 |
| [12] | Bixby, R., Gu, Z., Rothberg, E., Wunderling, R.: Mixed integer programming: a progress report. In: The sharpest cut: the impact of Manfred Padberg and his work. MPS/SIAM Series on Optimization, pp. 309–326 |
| [13] | Bixby R.E., Ceria S., McZeal C.M., Savelsbergh M.W.P.: An updated mixed integer programming library: MIPLIB 3.0. Optima 58, 12–15 (1998) |
| [14] | Bonami P., Cornuéjols G., Dash S., Fischetti M., Lodi A.: Projected Chvátal Gomory cuts for mixed integer linear programs. Math. Program. 113(2), 241–257 (2008) · Zbl 1135.90031 · doi:10.1007/s10107-006-0051-y |
| [15] | Boyd A.E.: Fenchel cutting planes for integer programs. Oper. Res. 42, 53–64 (1992) · Zbl 0809.90104 · doi:10.1287/opre.42.1.53 |
| [16] | Cook W., Kannan R., Schrijver A.: Chvátal closures for mixed integer programming problems. Math. Program. 47, 155–174 (1990) · Zbl 0711.90057 · doi:10.1007/BF01580858 |
| [17] | Cornuéjols G., Li Y., Vanderbussche D.: K-cuts: a variation of Gomory mixed integer cuts from the LP tableau. INFORMS J. Comput. 15(4), 385–396 (2003) · Zbl 1238.90105 · doi:10.1287/ijoc.15.4.385.24893 |
| [18] | CPLEX: http://www.ilog.com/products/cplex |
| [19] | Crowder H., Johnson E., Padberg M.: Solving large-scale zero-one linear-programming problems. Oper. Res. 31(5), 803–834 (1983) · Zbl 0576.90065 · doi:10.1287/opre.31.5.803 |
| [20] | Dantzig G.B.: Discrete variable extremum problems. Oper. Res. 5(2), 266–277 (1957) · doi:10.1287/opre.5.2.266 |
| [21] | Dash, S., Günlük, O.: On the strength of gomory mixed-integer cuts as group cuts. IBM research report RC23967 (2006) · Zbl 1209.90277 |
| [22] | Dash, S., Günlük, O., Lodi, A.: On the MIR closure of polyhedra. In: Fischetti, M., Williamson, D. (eds.). IPCO, Lecture notes in computer science, vol. 4513, pp. 337–351 (2007) · Zbl 1136.90417 |
| [23] | Dolan E., Moré J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201–213 (2001) · Zbl 1049.90004 · doi:10.1007/s101070100263 |
| [24] | Eisenbrand F., Laue S.: A linear algorithm for integer programming in the plane. Math. Program. 102(2), 249–259 (2005) · Zbl 1079.90581 · doi:10.1007/s10107-004-0520-0 |
| [25] | Fischetti, M., Lodi, A.: On the knapsack closure of 0–1 integer linear problems. In: Presentation at 10th International Workshop on Combinatorial Optimization, Aussois (2006). Available at http://www-id.imag.fr/IWCO2006/slides/Fischetti.pdf · Zbl 1274.90240 |
| [26] | Fischetti M., Lodi A.: Optimizing over the first Chvátal closure. Math. Programm. B 110(1), 3–20 (2007) · Zbl 1192.90125 · doi:10.1007/s10107-006-0054-8 |
| [27] | Fischetti, M., Salvagnin, D.: A local dominance procedure for mixed-integer linear programming. http://www.dei.unipd.it/\(\sim\)fisch/papers/MIPdominance.pdf · Zbl 1285.90017 |
| [28] | Fischetti M., Toth P.: A new dominance procedure for combinatorial optimization problems. Oper. Res. Lett. 7, 181–187 (1988) · Zbl 0655.90064 · doi:10.1016/0167-6377(88)90025-9 |
| [29] | Fukasawa, R.: Single-row mixed-integer programs: Theory and computations. Ph.D. thesis, Georgia Institute of Technology (2008) |
| [30] | Gomory R.E.: Early integer programming (reprinted). Oper. Res. 50(1), 78–81 (2002) · Zbl 1163.90663 · doi:10.1287/opre.50.1.78.17793 |
| [31] | Gomory R.E., Johnson E.: Some continuous functions related to corner polyhedra I. Math. Program. 3, 23–85 (1972) · Zbl 0246.90029 · doi:10.1007/BF01584976 |
| [32] | Goycoolea, M.: Cutting planes for large mixed integer programming models. Ph.D. thesis, Georgia Institute of Technology (2006) |
| [33] | Granlund, T.: The GNU multiple precision arithmetic library. Available on-line at http://www.swox.com/gmp/ |
| [34] | Gu Z., Nemhauser G.L., Savelsbergh M.W.P.: Lifted cover inequalities for 0–1 integer programs: computation. INFORMS J. Comput. 10, 427–437 (1998) · doi:10.1287/ijoc.10.4.427 |
| [35] | Gu Z., Nemhauser G.L., Savelsbergh M.W.P.: Sequence independent lifting in mixed integer programming. J. Combin Optimiz. 4(1), 109–129 (2000) · Zbl 0964.90030 · doi:10.1023/A:1009841107478 |
| [36] | Horowitz E., Sahni S.: Computing partitions with applications to the knapsack problem. J. ACM 21, 277–292 (1974) · Zbl 0329.90046 · doi:10.1145/321812.321823 |
| [37] | Ibaraki T.: The power of dominance relations in branch-and-bound algorithms. J. ACM 24, 264–279 (1977) · Zbl 0357.90043 · doi:10.1145/322003.322010 |
| [38] | Kannan R.: A polynomial algorithm for the two-variable integer programming problem. J. ACM 27, 118–122 (1980) · Zbl 0423.90052 · doi:10.1145/322169.322179 |
| [39] | Kaparis, K., Letchford, A.: Separation algorithms for 0–1 knapsack polytopes. Technical report available at Optimization Online (2007) · Zbl 1198.90297 |
| [40] | Kellerer H., Pferschy U., Pisinger D.: Knapsack Problems. Springer, Berlin (2004) · Zbl 1103.90003 |
| [41] | Marchand H., Wolsey L.: Aggregation and mixed integer rounding to solve MIPs. Oper. Res. 49, 363–371 (2001) · Zbl 1163.90671 · doi:10.1287/opre.49.3.363.11211 |
| [42] | Martello S., Toth P.: Knapsack Problems: Algorithms and Computer Implementations. Wiley, New York (1990) · Zbl 0708.68002 |
| [43] | Nemhauser G.L., Wolsey L.A.: A recursive procedure for generating all cuts for 0-1 mixed integer programs. Math. Program. 46, 379–390 (1990) · Zbl 0735.90049 · doi:10.1007/BF01585752 |
| [44] | Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Discrete Mathematics and Optimization. Wiley, New York (1999) · Zbl 0944.90001 |
| [45] | Savelsbergh M.: Preprocessing and probing for mixed integer programming problems. ORSA J. Comput. 6, 445–454 (1994) · Zbl 0814.90093 · doi:10.1287/ijoc.6.4.445 |
| [46] | Scarf H.E.: Production sets with indivisibilities–part II: the case of two activities. Econometrica 49, 395–423 (1981) · Zbl 0458.90008 · doi:10.2307/1913318 |
| [47] | Wolsey L.: Facets and strong valid inequalities for integer programs. Oper. Res. 24(2), 367–372 (1976) · Zbl 0339.90036 · doi:10.1287/opre.24.2.367 |
| [48] | Yan X.Q., Boyd E.A.: Cutting planes for mixed-integer knapsack polyhedra. Math. Program. 81(2), 257–262 (1998) · Zbl 0919.90115 |
| [49] | Zemel E.: Lifting the facets of zero-one polytopes. Math. Program. 15(1), 268–277 (1978) · Zbl 0428.90042 · doi:10.1007/BF01609032 |
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.
