An empirical evaluation of a walk-relax-round heuristic for mixed integer convex programs
Tóm tắt
Recently, a walk-and-round heuristic was proposed by Huang and Mehrotra (Comput Optim Appl, 2012) for generating high quality feasible solutions of mixed integer linear programs. This approach uses geometric random walks on a polyhedral set to sample points in this set. It subsequently rounds these random points using a heuristic, such as the feasibility pump. In this paper, the walk-and-round heuristic is further developed for the mixed integer convex programs (MICPs). Specifically, an outer approximation relaxation step is incorporated. The resulting approach is called a walk-relax-round heuristic. Computational results on problems from the CMU-IBM library show that the points generated from the random walk steps bring additional value. Specifically, the walk-relax-round heuristic using a long step Dikin walk found an optimal solution for 51 out of the 58 MICP test problems. In comparison, the feasibility pump heuristic starting at a continuous relaxation optimum found an optimal solution for 45 test problems. Computational comparisons with a commercial software Cplex 12.1 on mixed integer convex quadratic programs are also given. Our results show that the walk-relax-round heuristic is promising. This may be because the random walk points provide an improved outer approximation of the convex region.
Tài liệu tham khảo
Abhishek, K., Leyffer, S., Linderoth, J.: Feasibility Pump Heuristics for Mixed Integer Nonlinear Programs. Unpublished working paper (2008)
Achterberg, T., Berthold, T.: Improving the feasibility pump. Discret. Optim. 4(1), 77–86 (2007)
AMPL: A modeling language for mathematical programming. www.ampl.com
Andersen, E., Ye, Y.: A computational study of the homogeneous algorithm for large-scale convex optimization. Comput. Optim. Appl. 10(3), 243–269 (1998)
Andersen, E., Ye, Y.: On a homogeneous algorithm for the monotone complementarity problem. Math. Program. 84, 375–399 (1999)
Baena, D., Castro, J.: Using the analytic center in the feasibility pump. Oper. Res. Lett. 39(5), 310–317 (2011)
Balas, E., Ceria, S., Dawande, M., Margot, F., Pataki, G.: Octane: a new heuristic for pure 0–1 programs. Oper. Res. 49(2), 207–225 (2001)
Baumert, S., Ghate, A., Kiatsupaibul, S., Shen, Y., Smith, R.L., Zabinsky, Z.B.: Discrete hit-and-run for sampling points from arbitrary distributions over subsets of integer hyper-rectangles. Oper. Res. 57, 727–739 (2009)
Bertacco, L., Fischetti, M., Lodi, A.: A feasibility pump heuristic for general mixed-integer problems. Discret. Optim. 4(1), 63–76 (2007)
Bertsimas, D., Vempala, S.: Solving convex programs by random walks. J. ACM 51(4), 540–556 (2004)
Bonami, P., Gonçalves, J.: Heuristics for convex mixed integer nonlinear programs. Comput. Optim. Appl. 51(2), 729–747 (2012)
Bonami, P., Kilinç, M., Linderoth, J.: Algorithms and software for convex MINLP. Discret. Optim. 5, 186–204 (2008)
Bonami, P., Cornuéjols, G., Lodi, A., Margot, F.: A feasibility pump for mixed integer nonlinear programs. Math. Program. 119, 331–352 (2009)
CMU-IBM open source MINLP project. http://egon.cheme.cmu.edu/ibm/page.htm
COIN-OR Ipopt. http://www.coin-or.org/ipopt/
D’Ambrosio, C., Frangioni, A., Liberti, L., Lodi, A.: Experiments with a Feasibility Pump Approach for Nonconvex MINLPs. Lecture Notes in Computer Science, vol. 6049, pp. 350–360 (2010)
D’Ambrosio, C., Frangioni, A., Liberti, L., Lodi, A.: A storm of feasibility pumps for nonconvex minlp. Math. Program. 136(2), 375–402 (2012)
Danna, E., Rothberg, E., Pape, C.: Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Program. 102(1), 71–90 (2005)
Dolan, E., Moré, J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002)
Fischetti, M., Lodi, A.: Local branching. Math. Program. 98(1), 23–47 (2003)
Fischetti, M., Salvagnin, D.: Feasibility pump 2.0. Math. Program. Comput. 1, 201–222 (2009)
Fischetti, M., Glover, F., Lodi, A.: The feasibility pump. Math. Program. 104(1), 91–104 (2005)
Hans D. Mittelmann’s MIQP test problems. http://plato.asu.edu/ftp/miqp.html
Huang, K.-L., Mehrotra, S.: An empirical evaluation of walk-and-round heuristics for mixed integer linear programs. Comput. Optim. Appl. 55(3), 545–570 (2013)
Huang, K.-L., Mehrotra, S.: Solution of Monotone Complementarity and General Convex Programming Problems Using a Modified Potential Reduction Interior Point Method. http://www.optimization-online.org/DB_HTML/2012/04/3431.html (2012)
IBM Cplex optimizer. http://www.ibm.com/
Kannan, R., Narayanan, H.: Random walks on polytopes and an affine interior point method for linear programming. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pp. 561–570 (2009)
Kannan, R., Vempala, S.: Sampling lattice points. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 696–700 (1997)
Lovász, L.: Hit-and-run mixes fast. Math. Program. 86(3), 443–461 (1999)
Lovász, L., Vempala, S.: Hit-and-run from a corner. SIAM J. Comput. 35(4), 985–1005 (2006)
Mehrotra, S.: On the implementation of a primal-dual interior point method. SIAM J. Optim. 2(4), 575–601 (1992)
Mehrotra, S., Huang, K.-L.: Computational experience with a modified potential reduction algorithm for linear programming. Optim. Methods Softw. 27(4–5), 865–891 (2012)
Naoum-Sawaya, J.: Recursive central rounding heuristic for mixed integer programs. Comput. Oper. Res. 43, 191–200 (2014)
Narayanan, H.: Randomized Interior Point Methods for Sampling and Optimization. http://arxiv.org/abs/arXiv:0911.3950 (2009)
Smith, R.: Efficient Monte Carlo procedures for generating points uniformly distributed over bounded regions. Oper. Res. 32(6), 1296–1308 (1984)
Vempala, S.: Geometric random walks: a survey. Comb. Comput. Geom. 52, 573–612 (2005)
Ye, Y.: Interior Point Algorithms: Theory and Analysis. Wiley, New York (1997)
Zabinsky, Z., Smith, R., McDonald, J., Romeijn, H., Kaufman, D.: Improving hit-and-run for global optimization. J. Glob. Optim. 3(2), 171–192 (1993)