On the safety of Gomory cut generators

Gérard Cornuéjols1, François Margot1, Giacomo Nannicini2
1Carnegie Mellon University
2Singapore University of Technology and Design

Tóm tắt

Từ khóa


Tài liệu tham khảo

Achterberg, T.: SCIP: solving constraint integer programs. Math. Program. Comput. 1(1), 1–41 (2009)

Achterberg, T., Koch, T., Martin, A.: MIPLIB 2003. Oper. Res. Lett. 34(4), 361–372 (2006)

Ailon, N.: Aggregation of partial rankings, $$p$$ p -ratings and top- $$m$$ m lists. Algorithmica 57, 284–300 (2010)

Applegate, D.L., Cook, W., Dash, S., Espinoza, D.G.: Exact solutions to linear programming problems. Oper. Res. Lett. 35(6), 693–699 (2007)

Balas, E., Ceria, S., Cornuéjols, G., Natraj, N.: Gomory cuts revisited. Oper. Res. Lett. 19(1), 1–9 (1996)

Bixby, R., Rothberg, E.: Progress in computational mixed integer programming—a look back from the other side of the tipping point. Ann. Oper. Res. 149(1), 37–41 (2007)

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)

COIN-OR Branch-and-Cut 2.7 stable r1676. https://projects.coin-or.org/Cbc/

COIN-OR Linear Programming 1.14 stable r1753. https://projects.coin-or.org/Clp/

COIN-OR Cut Generation Library 0.57 stable r1033. https://projects.coin-or.org/Cgl/

Conover, W.J.: Practical Nonparametric Statistics, 3rd edn. Wiley, New York (1999)

Cook, W., Dash, S., Fukasawa, R., Goycoolea, M.: Numerically safe Gomory mixed-integer cuts. INFORMS J. Comput. 21(4), 641–649 (2009)

Cook, W., Koch, T., Steffy, D.E., Wolter, K.: An exact rational mixed-integer programming solver. In: Günlük, O., Woeginger, G.J. (eds.) Proceedings of IPCO 2011. Lecture Notes in Computer Science, vol. 6655, pp. 104–116. Springer, Berlin (2011)

Espinoza, D.G.: On linear programming, integer programming and cutting planes. PhD thesis, School of Industrial and Systems Engineering, Georgia Institute of Technology (2006)

Gomory, R.E.: An algorithm for the mixed-integer problem. Technical Report RM-2597, RAND Corporation (1960)

Gutmann, H.-M.: A radial basis function method for global optimization. J. Glob. Optim. 19, 201–227 (2001). doi: 10.1023/A:1011255519438

Hemker, T.: Derivative free surrogate optimization for mixed-integer nonlinear black-box problems in engineering. Master’s thesis, Technischen Universität Darmstadt (2008)

Holmström, K., Quttineh, N.H., Edvall, M.M.: An adaptive radial basis algorithm (ARBF) for expensive black-box mixed-integer constrained global optimization. Optim. Eng. 9(4), 311–339 (2008)

Ibm, ILOG CPLEX 12.2 User’s Manual. http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/

Kahan, W.: Pracniques: further remarks on reducing truncation errors. Commun. ACM 8(1), 40 (1965)

Koch, T., Achterberg, T., Andersen, E., Bastert, O., Berthold, T., Bixby, R.E., Danna, E., Gamrath, G., Gleixner, A.M., Heinz, S., Lodi, A., Mittelmann, H., Ralphs, T., Salvagnin, D., Steffy, D.E., Wolter, K.: MIPLIB 2010. Math. Program. Comput. 3(2), 103–163 (2011)

Litzkow, M., Livny, M., Mutka, M.: Condor—a hunter of idle workstations. In: Proceedings of the 8th International Conference on Distributed Computing System, pp. 104–111 (1998)

Margot, F.: Testing cut generators for mixed-integer linear programming. Math. Program. Comput. 1(1), 69–95 (2009)

Neumaier, A., Shscherbina, O.: Safe bounds in linear and mixed-integer linear programming. Math. Program. A 99, 283–296 (2004)

R Development Core Team: R: a language and environment for statistical computing. R Foundation for Statistical Computing, Vienna, Austria. ISBN: 3-900051-07-0 (2008)

Regis, R., Shoemaker, C.: Improved strategies for radial basis function methods for global optimization. J. Glob. Optim. 37, 113–135 (2007). doi: 10.1007/s10898-006-9040-1

Sheskin, D.J.: Handbook of Parametric and Nonparametric Statistical Procedures. Chapman & Hall/CRC, London (2007)

van Zuylen, A., Williamson, D.P.: Deterministic algorithms for rank aggregation and other ranking and clustering problems. Math. Oper. Res. 34, 594–620 (2009)