Pivot-and-reduce cuts: an approach for improving Gomory mixed-integer cuts. (English) Zbl 1218.90138
Summary: Gomory mixed-integer cuts are of crucial importance in solving large-scale mixed-integer linear programs. Recently, there has been considerable research particularly on the strengthening of these cuts. We present a new heuristic algorithm which aims at improving Gomory mixed-integer cuts. Our approach is related to the reduce-and-split cuts. These cuts are based on an algorithm which tries to reduce the coefficients of the continuous variables by forming integer linear combinations of simplex tableau rows. Our algorithm is designed to achieve the same result by performing pivots on the simplex tableau. We give a detailed description of the algorithm and its implementation. Finally, we report on computational results with our approach and analyze its performance. The results indicate that our algorithm can enhance the performance of the Gomory mixed-integer cuts.
MSC:
| 90C11 | Mixed integer programming |
Software:
MIPLIB; CPLEX; Benchmarks for Optimization Software; SCIP; MOPS; MIPLIB2003; Decision tree for optimization softwareReferences:
| [1] | Achterberg, T., SCIP: solving constraint integer programs, Mathematical Programming Computation, 1, 1, 1-41 (2009) · Zbl 1171.90476 |
| [2] | Achterberg, T.; Koch, T.; Martin, A., MIPLIB 2003, Operations Research Letters, 34, 4, 1-12 (2006) · Zbl 1133.90300 |
| [3] | Andersen, K.; Cornuéjols, G.; Li, Y., Reduce-and-split cuts: Improving the performance of mixed-integer Gomory cuts, Management Science, 51, 11, 1720-1732 (2005) · Zbl 1232.90310 |
| [4] | Balas, E., Intersection cuts - a new type of cutting planes for integer programming, Operations Research, 19, 1, 19-39 (1971) · Zbl 0219.90035 |
| [5] | Balas, E.; Bonami, P., Generating lift-and-project cuts from the LP simplex tableau: open source implementation and testing of new variants, Mathematical Programming Computation, 1, 2-3, 165-199 (2009) · Zbl 1180.90206 |
| [6] | Balas, E.; Perregaard, M., A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer Gomory cuts for 0-1 programming, Mathematical Programming, 94, 2-3, 221-245 (2003) · Zbl 1030.90068 |
| [7] | Balas, E.; Ceria, S.; Cornuéjols, G., A lift-and-project cutting plane algorithm for mixed 0-1 programs, Mathematical Programming, 58, 1-3, 295-324 (1993) · Zbl 0796.90041 |
| [8] | Balas, E.; Ceria, S.; Cornuéjols, G., Mixed 0-1 programming by lift-and-project in a branch-and-cut framework, Management Science, 42, 9, 1229-1246 (1996) · Zbl 0880.90105 |
| [9] | Balas, E.; Ceria, S.; Cornuéjols, G.; Natraj, N., Gomory cuts revisited, Operations Research Letters, 19, 1-9 (1996) · Zbl 0865.90098 |
| [10] | Bixby, R. E.; Rothberg, E., Progress in computational mixed integer programming - a look back from the other side of the tipping point, Annals of Operations Research, 149, 1, 37-41 (2007) · Zbl 1213.90011 |
| [11] | Bixby, R.E., Ceria, S., McZeal, C.M., Savelsbergh, M.W.P., 1998. An updated mixed integer programming library: MIPLIB 3.0. Optima 58, pp.12-15, <http://www.caam.rice.edu/bixby/miplib/miplib.html>; Bixby, R.E., Ceria, S., McZeal, C.M., Savelsbergh, M.W.P., 1998. An updated mixed integer programming library: MIPLIB 3.0. Optima 58, pp.12-15, <http://www.caam.rice.edu/bixby/miplib/miplib.html> |
| [12] | Cook, W. J.; Kannan, R.; Schrijver, A., Chvátal closures for mixed integer programming problems, Mathematical Programming, 47, 1-3, 155-174 (1990) · Zbl 0711.90057 |
| [13] | Cornuéjols, G., Revival of the Gomory cuts in the 1990’s, Annals of Operations Research, 149, 1, 63-66 (2007) · Zbl 1213.90015 |
| [14] | Gomory, R.E., 1960. An algorithm for the mixed integer problem. Technical Report RM-2597, The RAND Cooperation.; Gomory, R.E., 1960. An algorithm for the mixed integer problem. Technical Report RM-2597, The RAND Cooperation. |
| [15] | ILOG Inc., 2010. Cplex. <http://www.ibm.com/software/integration/optimization/cplex/>; ILOG Inc., 2010. Cplex. <http://www.ibm.com/software/integration/optimization/cplex/> |
| [16] | Koberstein, A., Progress in the dual simplex method for solving large scale LP problems: techniques for a fast and stable implementation, Computational Optimization and Applications, 41, 2, 185-204 (2008) · Zbl 1168.90555 |
| [17] | Koberstein, A.; Suhl, U. H., Progress in the dual simplex method for large scale LP problems: practical dual phase 1 algorithms, Computational Optimization and Applications, 37, 1, 49-65 (2007) · Zbl 1161.90438 |
| [18] | Linderoth, J. T.; Ralphs, T. K., Noncommercial software for mixed-integer linear programming, (Karlof, J. K., Integer Programming: Theory and Practice. Operations Research Series (2005), CRC Press), 253-303 · Zbl 1137.90622 |
| [19] | Mittelmann, H., 2010. Decision tree for optimization software: Benchmarks for optimization software. <http://plato.asu.edu/bench.html>; Mittelmann, H., 2010. Decision tree for optimization software: Benchmarks for optimization software. <http://plato.asu.edu/bench.html> |
| [20] | Suhl, U. H., MOPS - mathematical optimization system, European Journal of Operational Research, 72, 312-322 (1994) · Zbl 0800.90690 |
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.
