Improving branch-and-cut performance by random sampling
Tóm tắt
We discuss the variability in the performance of multiple runs of branch-and-cut mixed integer linear programming solvers, and we concentrate on the one deriving from the use of different optimal bases of the linear programming relaxations. We propose a new algorithm exploiting more than one of those bases and we show that different versions of the algorithm can be used to stabilize and improve the performance of the solver.
Tài liệu tham khảo
Achterberg, T.: Constraint integer programming. Ph.D. thesis, ZIB (2007)
Achterberg, T.: LP basis selection and cutting planes (2010). MIP 2010 workshop in Atlanta
Achterberg, T., Wunderling, R.: Mixed integer programming: Analyzing 12 years of progress. In: Facets of Combinatorial Optimization, pp. 449–481 (2013)
Berthold, T.: Measuring the impact of primal heuristics. Oper. Res. Lett. 41(6), 611–614 (2013)
Carvajal, R., Ahmed, S., Nemhauser, G., Furman, K., Goel, V., Shao, Y.: Using diversification, communication and parallelism to solve mixed-integer linear programs. Oper. Res. Lett. 42(2), 186–189 (2014)
Cornuéjols, G.: Valid inequalities for mixed integer linear programs. Math. Progr. 112, 3–44 (2008)
Danna, E.: Performance variability in mixed integer programming (2008). MIP 2008 workshop in New Work. http://coral.ie.lehigh.edu/~jeff/mip-2008/talks/danna.pdf
FICO: FICO XPRESS Optimization Suite (2013). http://www.fico.com
Fischetti, M., Glover, F., Lodi, A.: The feasibility pump. Math. Progr. 104(1), 91–104 (2005)
Fischetti, M., Monaci, M.: Exploiting erraticism in search. Oper. Res. 62(1), 114–122 (2014)
Gomes, C.P., Sellmann, B., Kautz, H.: Boosting combinatorial search through randomization. In: Proceedings of the National Conference on Artificial Intelligence, pp. 431–437. AAAI Press (1998)
GUROBI: GUROBI Optimizer (2013). http://www.gurobi.com
IBM: IBM ILOG CPLEX Optimization Studio (2013). http://www.cplex.com
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—Mixed Integer Programming Library version 5. Math. Progr. Comput. 3, 103–163 (2011)
Linderoth, J.T., Lodi, A.: MILP software. In: Cochran, J.J. (ed.) Wiley Encyclopedia of Operations Research and Management Science, vol. 5, pp. 3239–3248. Wiley, Chichester (2011)
Lodi, A.: Mixed integer programming computation. In: Jünger, M., Liebling, T.M., Naddef, D., Nemhauser, G.L., Pulleyblank, W.R., Reinelt, G., Rinaldi, G., Wolsey, L.A. (eds.) 50 Years of Integer Programming 1958–2008, pp. 619–645. Springer, Heidelberg (2009)
Lodi, A.: The heuristic (dark) side of MIP solvers. In: Talbi, E.G. (ed.) Hybrid Metaheuristics, pp. 273–284. Springer, Heidelberg (2012)
Lodi, A., Tramontani, A.: Performance variability in mixed-integer programming. In: Topaloglu, H. (ed.) TutORials in Operations Research: Theory Driven by Influential Applications, pp. 1–12. INFORMS, Catonsville, MD (2013)
Mitra, G., Hai, I., Hajian, M.T.: A distributed processing algorithm for solving integer programs using a cluster of workstations. Parallel Comput. 23(6), 733–753 (1997)
Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1988)
Shinano, Y., Achterberg, T., Berthold, T., Heinz, S., Koch, T., Winkler, M.: Solving hard MIPLIB2003 problems with ParaSCIP on supercomputers: An update. Tech. Rep. 13-66, ZIB (2013)