Testing cut generators for mixed-integer linear programming. (English) Zbl 1171.90478
Summary: A methodology for testing the accuracy and strength of cut generators for mixed-integer linear programming is presented. The procedure amounts to random diving towards a feasible solution, recording several kinds of failures. This allows for a ranking of the accuracy of the generators. Then, for generators deemed to have similar accuracy, statistical tests are performed to compare their relative strength. An application on eight Gomory cut generators and six Reduce-and-Split cut generators is given. The problem of constructing benchmark instances for which feasible solutions can be obtained is also addressed.
MSC:
| 90C11 | Mixed integer programming |
| 90-04 | Software, source code, etc. for problems pertaining to operations research and mathematical programming |
| 90-08 | Computational methods for problems pertaining to operations research and mathematical programming |
References:
| [1] | Achterberg T., Koch T., Martin A.: MIPLIB 2003. Oper. Res. Lett. 34, 361–372 (2006) · Zbl 1133.90300 · doi:10.1016/j.orl.2005.07.009 |
| [2] | Amini M.M., Barr R.S.: Network reoptimization algorithms: A statistical design comparison. ORSA J. Comput. 5, 395–408 (1993) · Zbl 0800.90755 |
| [3] | Amini M.M., Racer M.: A rigorous computational comparison of alternative solution methods for the generalized assignment problem. Manage. Sci. 40, 868–890 (1994) · Zbl 0816.90096 · doi:10.1287/mnsc.40.7.868 |
| [4] | Anderson K., Cornuéjols G., Li Y.: Reduce-and-split cuts: Improving the performance of mixed integer Gomory cuts. Manage. Sci. 51, 1720–1732 (2005) · Zbl 1232.90310 · doi:10.1287/mnsc.1050.0382 |
| [5] | Applegate D.L., Cook W., Dash S., Espinoza D.G.: Exact solutions to linear programming problems. Oper. Res. Lett. 35, 693–699 (2007) · Zbl 1177.90282 · doi:10.1016/j.orl.2006.12.010 |
| [6] | Balas E. et al.: Disjunctive programming: Cutting planes from logical conditions. In: Mangasarian, O.L. (eds) Nonlinear Programming, pp. 279–312. Academic Press, New York (1975) · Zbl 0349.90117 |
| [7] | Bixby, R.E., Ceria, S., McZeal, C.M., Savelsbergh, M.W.P.: MIPLIB 3.0, http://www.caam.rice.edu/\(\sim\)bixby/miplib/miplib.html |
| [8] | Cohen P.R.: Empirical Methods for Artificial Intelligence. Vol. 2. MIT Press, Cambridge (1995) · Zbl 0850.68260 |
| [9] | COIN-OR, http://www.coin-or.org |
| [10] | Cook, W., Dash, S., Fukasawa, R., Goycoolea, M.: Numerically Safe Gomory Mixed-Integer Cuts. Working paper (2008) · Zbl 1243.90135 |
| [11] | Danna E., Rothberg E., Le Pape C.: Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Program. 102, 71–90 (2005) · Zbl 1131.90036 · doi:10.1007/s10107-004-0518-7 |
| [12] | Dhiflaoui, M., Funke, S., Kwappik, C., Mehlhorn, K., Seel, M., Schömer, E., Schulte, R., Weber, D.: Certifying and Repairing Solutions to Large LPs. How Good are LP-solvers? In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, MD, 2003), pp. 255–256. ACM, New York (2003) · Zbl 1176.90395 |
| [13] | Fischetti M., Lodi A.: Local branching. Math. Program. Ser. B 98(1–3), 23–47 (2003) · Zbl 1060.90056 · doi:10.1007/s10107-003-0395-5 |
| [14] | Gomory, R.: An Algorithm for the Mixed Integer Problem, Technical Report RM-2597. The RAND Corporation (1960) · Zbl 0095.14502 |
| [15] | Hoaglin D.C., Klema V.C., Peters S.C.: Exploratory data analysis in a study on the performance of nonlinear optimization routines. ACM Trans. Math. Softw. 8, 145–162 (1982) · Zbl 0497.65038 · doi:10.1145/355993.355996 |
| [16] | Hooker J.N.: Needed: An empirical science of algorithms. Oper. Res. 42, 201–212 (1994) · Zbl 0805.90119 · doi:10.1287/opre.42.2.201 |
| [17] | Hooker J.N.: Testing heuristics: We have it all wrong. J. Heuristics 1, 33–42 (1995) · Zbl 0853.68155 · doi:10.1007/BF02430364 |
| [18] | ILOG CPLEX 10.1 User’s Manual (2006) |
| [19] | Jeroslow R.: Cutting plane theory: Disjunctive methods. Ann. Discrete Math. 1, 293–330 (1972) · doi:10.1016/S0167-5060(08)70741-6 |
| [20] | Koch T.: The final netlib results. Oper. Res. Lett. 32, 138–142 (2004) · Zbl 1137.90613 · doi:10.1016/S0167-6377(03)00094-4 |
| [21] | Lin B.W., Rardin R.L.: Controlled experimental design for statistical comparison of integer programming algorithms. Manage. Sci. 25, 1258–1271 (1979) · doi:10.1287/mnsc.25.12.1258 |
| [22] | Marchand H., Martin A., Weismantel R., Wolsey L.: Cutting planes in integer and mixed integer programming, workshop on discrete optimization, DO’99 (Piscataway, NJ). Discrete Appl. Math. 123, 397–446 (2002) · Zbl 1130.90370 · doi:10.1016/S0166-218X(01)00348-1 |
| [23] | Margot, F.: BAC: A BCP Based Branch-and-cut Example. IBM Research Report RC22799 (W0305-064) (2003), revised August (2008) |
| [24] | Margot F.: Testing cut generators for MILP. Optima 77, 6–9 (2008) |
| [25] | http://wpweb2.tepper.cmu.edu/fmargot/ |
| [26] | McGeoch C.C.: Toward an experimental method for algorithm simulation. INFORMS J. Comput. 8, 1–15 (1996) · Zbl 0854.68038 · doi:10.1287/ijoc.8.1.1 |
| [27] | McGeoch C.C.: Experimental analysis of algorithms. Notices Am. Math. Assoc. 48, 304–311 (2001) · Zbl 0981.68187 |
| [28] | McGeoch C.C.: Experimental Analysis of Optimization Algorithms. Handbook of Applied Optimization, pp. 1044–1052. Oxford University Press, Oxford (2002) |
| [29] | McGeoch, C.C.: Experimental Analysis of Algorithms. Handbook of Global Optimization. pp. 489–513. Vol. 2, Kluwer, Boston (2002) · Zbl 1050.90028 |
| [30] | McGeoch C.C., Sanders P., Fleischer R., Cohen P.R., Precup D. et al.: Using finite experiments to study asymptotic performances. In: Fleischer, R. (eds) Experimental Algorithmics: From Algorithm Design to Robust and Efficient Software. Lecture Notes in Computer Science, pp. 93–126. Springer, Berlin (2002) · Zbl 1026.68796 |
| [31] | Mittelmann, H.: http://plato.asu.edu/topics/testcases.html , no longer available |
| [32] | Nance R.E., Moose R.L., Foutz R.V.: A statistical technique for comparing heuristics: An example from capacity assignment strategies in computer network design. Commun. ACM 30, 430–442 (1987) · doi:10.1145/22899.22907 |
| [33] | Nemhauser G.L., Wolsey L.A.: A recursive procedure to generate all cuts for 0–1 mixed integer programs. Math. Program. 46, 379–390 (1990) · Zbl 0735.90049 · doi:10.1007/BF01585752 |
| [34] | Neumaier A., Shscherbina O.: Safe bounds in linear and mixed-integer linear programming. Math. Program. 99, 283–296 (2004) · Zbl 1098.90043 · doi:10.1007/s10107-003-0433-3 |
| [35] | R statistical software, http://www.r-project.org/ |
| [36] | Sheskin D.J.: Parametric and nonparametric statistical procedures. Vol. 2547, 2nd edn. Chapman & Hall/CRC, London (2000) · Zbl 0955.62003 |
| [37] | Stuart G.W.: Matrix algorithms, vol. I: Basic decompositions. SIAM, Philadelphia (1998) |
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.
