On the strength of Gomory mixed-integer cuts as group cuts. (English) Zbl 1209.90277
Summary: Gomory mixed-integer (GMI) cuts generated from optimal simplex tableaus are known to be useful in solving mixed-integer programs. Further, it is well-known that GMI cuts can be derived from facets of Gomory’s master cyclic group polyhedron and its mixed-integer extension studied by Gomory and Johnson. In this paper we examine why cutting planes derived from other facets of master cyclic group polyhedra (group cuts) do not seem to be as useful when used in conjunction with GMI cuts. For many practical problem instances, we numerically show that once GMI cuts from different rows of the optimal simplex tableau are added to the formulation, all other group cuts from the same tableau rows are satisfied.
References:
| [1] | Achterberg, T., Kock, T., Martin, A.: MIPLIB 2003. ZIB Technical report 05-28 |
| [2] | Araoz J., Gomory R.E., Johnson E.L. and Evans L. (2003). Cyclic group and knapsack facets. Math. Programm. 96: 377–408 · Zbl 1082.90094 · doi:10.1007/s10107-003-0390-x |
| [3] | Atamtürk A. (2003). On the facets of the mixed-integer knapsack polyhedron. Math. Programm. 98: 145–175 · Zbl 1082.90073 · doi:10.1007/s10107-003-0400-z |
| [4] | Balas E., Ceria S., Cornuéjols G. and Natraj G. (1996). Gomory cuts revisited. Oper. Res. Lett. 19: 1–9 · Zbl 0865.90098 · doi:10.1016/0167-6377(96)00007-7 |
| [5] | Bixby R.E., Ceria S., McZeal C.M. and Savelsbergh M.W.P. (1998). An updated mixed integer programming library: MIPLIB 3.0. Optima 58: 12–15 |
| [6] | Bixby R.E., Fenelon M., Gu Z., Rothberg E. and Wunderling R. (2000). MIP: Theory and practice–closing the gap. In: Powell, M.J.D. and Scholtes, S. (eds) System Modelling and Optimization: Methods, Theory, and Applications., pp 19–49. Kluwer Academic, Dordrecht · Zbl 0986.90025 |
| [7] | Cornuejols G., Li Y. and Vandenbussche D. (2003). K-Cuts: a variation of Gomory mixed integer cuts from the LP tableau. INFORMS J. Comput. 15: 385–396 · Zbl 1238.90105 · doi:10.1287/ijoc.15.4.385.24893 |
| [8] | Dash S. and Günlük O. (2006). Valid inequalities based on simple mixed-integer sets. Math. Programm. 105: 29–53 · Zbl 1085.90034 · doi:10.1007/s10107-005-0599-y |
| [9] | Dash S. and Günlük O. (2006). Valid inequalities based on the interpolation procedure. Math. Programm. 106: 111–136 · Zbl 1134.90446 · doi:10.1007/s10107-005-0600-9 |
| [10] | Dash, S., Günlük, O., Goycoolea, M.: Two step MIR inequalities for mixed-integer programs. Manuscript (2005) · Zbl 1243.90146 |
| [11] | Fischetti M., Glover F. and Lodi A. (2004). Feasibility pump. Math. Programm. 104: 91–104 · Zbl 1077.90039 · doi:10.1007/s10107-004-0570-3 |
| [12] | Fischetti, M., Lodi, A.: Local branching, mathematical programming (in press) · Zbl 1060.90056 |
| [13] | Fischetti, M., Saturni, C.: Mixed integer cuts from cyclic groups. Math. Programm. (in press) · Zbl 1278.90274 |
| [14] | Forrest, J.J.: CLP, an open source code for solving linear programming problems, http://www.coin-or.org/clp/index.html |
| [15] | Gomory R.E. (1969). Some polyhedra related to combinatorial problems. J. Linear Algebra Appl. 2: 451–558 · Zbl 0184.23103 · doi:10.1016/0024-3795(69)90017-2 |
| [16] | Gomory R.E. and Johnson E. (1972). Some continuous functions related to corner polyhedra I. Math. Programm. 3: 23–85 · Zbl 0246.90029 · doi:10.1007/BF01584976 |
| [17] | Gomory R.E. and Johnson E. (1972). Some continuous functions related to corner polyhedra II. Math. Programm. 3: 359–389 · Zbl 0254.90036 · doi:10.1007/BF01585008 |
| [18] | Gomory R.E., Johnson E.L. and Evans L. (2003). Corner polyhedra and their connection with cutting planes. Math. Programm. 96: 321–339 · Zbl 1082.90145 · doi:10.1007/s10107-003-0388-4 |
| [19] | http://miplib.zib.de |
| [20] | http://www.or.deis.unibo.it/research_pages/ORinstances/MIPs.html |
| [21] | Marchand H. and Wolsey L. (2001). Aggregation and mixed integer rounding to solve MIPs. Oper. Res. 49: 363–371 · Zbl 1163.90671 · doi:10.1287/opre.49.3.363.11211 |
| [22] | Mittelmann, H.: MILPLib. http://plato.asu.edu/topics/testcases.html |
| [23] | Schrijver A. (1986). Theory of Linear and Integer Programming. Wiley, New York · Zbl 0665.90063 |
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.
