×

zbMATH — the first resource for mathematics

An empirical evaluation of a walk-relax-round heuristic for mixed integer convex programs. (English) Zbl 1326.90055
Summary: Recently, a walk-and-round heuristic was proposed by K.-L. Huang and S. Mehrotra [Comput. Optim. Appl. 55, No. 3, 545–570 (2013; Zbl 1275.90045)] 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.

MSC:
90C11 Mixed integer programming
90C25 Convex programming
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abhishek, K., Leyffer, S., Linderoth, J.: Feasibility Pump Heuristics for Mixed Integer Nonlinear Programs. Unpublished working paper (2008) · Zbl 1235.90098
[2] Achterberg, T; Berthold, T, Improving the feasibility pump, Discret. Optim., 4, 77-86, (2007) · Zbl 1170.90443
[3] AMPL: A modeling language for mathematical programming. www.ampl.com · Zbl 1163.90654
[4] Andersen, E; Ye, Y, A computational study of the homogeneous algorithm for large-scale convex optimization, Comput. Optim. Appl., 10, 243-269, (1998) · Zbl 0914.90212
[5] Andersen, E; Ye, Y, On a homogeneous algorithm for the monotone complementarity problem, Math. Program., 84, 375-399, (1999) · Zbl 0972.90078
[6] Baena, D; Castro, J, Using the analytic center in the feasibility pump, Oper. Res. Lett., 39, 310-317, (2011) · Zbl 1235.90098
[7] Balas, E; Ceria, S; Dawande, M; Margot, F; Pataki, G, Octane: a new heuristic for pure 0-1 programs, Oper. Res., 49, 207-225, (2001) · Zbl 1163.90654
[8] Baumert, S; Ghate, A; Kiatsupaibul, S; Shen, Y; Smith, RL; Zabinsky, ZB, Discrete hit-and-run for sampling points from arbitrary distributions over subsets of integer hyper-rectangles, Oper. Res., 57, 727-739, (2009) · Zbl 1228.60081
[9] Bertacco, L; Fischetti, M; Lodi, A, A feasibility pump heuristic for general mixed-integer problems, Discret. Optim., 4, 63-76, (2007) · Zbl 1169.90415
[10] Bertsimas, D; Vempala, S, Solving convex programs by random walks, J. ACM, 51, 540-556, (2004) · Zbl 1204.90074
[11] Bonami, P; Gonçalves, J, Heuristics for convex mixed integer nonlinear programs, Comput. Optim. Appl., 51, 729-747, (2012) · Zbl 1241.90189
[12] Bonami, P; Kilinç, M; Linderoth, J, Algorithms and software for convex MINLP, Discret. Optim., 5, 186-204, (2008) · Zbl 1151.90028
[13] Bonami, P; Cornuéjols, G; Lodi, A; Margot, F, A feasibility pump for mixed integer nonlinear programs, Math. Program., 119, 331-352, (2009) · Zbl 1163.90013
[14] CMU-IBM open source MINLP project. http://egon.cheme.cmu.edu/ibm/page.htm · Zbl 1228.60081
[15] COIN-OR Ipopt. http://www.coin-or.org/ipopt/ · Zbl 1235.90098
[16] 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)
[17] D’Ambrosio, C; Frangioni, A; Liberti, L; Lodi, A, A storm of feasibility pumps for nonconvex MINLP, Math. Program., 136, 375-402, (2012) · Zbl 1257.90056
[18] Danna, E; Rothberg, E; Pape, C, Exploring relaxation induced neighborhoods to improve MIP solutions, Math. Program., 102, 71-90, (2005) · Zbl 1131.90036
[19] Dolan, E; Moré, J, Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213, (2002) · Zbl 1049.90004
[20] Fischetti, M; Lodi, A, Local branching, Math. Program., 98, 23-47, (2003) · Zbl 1060.90056
[21] Fischetti, M; Salvagnin, D, Feasibility pump 2.0., Math. Program. Comput., 1, 201-222, (2009) · Zbl 1180.90208
[22] Fischetti, M; Glover, F; Lodi, A, The feasibility pump, Math. Program., 104, 91-104, (2005) · Zbl 1077.90039
[23] Hans D. Mittelmann’s MIQP test problems. http://plato.asu.edu/ftp/miqp.html
[24] 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) · Zbl 1275.90045
[25] 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) · Zbl 0946.90116
[26] IBM Cplex optimizer. http://www.ibm.com/ · Zbl 0773.90047
[27] 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) · Zbl 1304.90138
[28] Kannan, R., Vempala, S.: Sampling lattice points. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 696-700 (1997) · Zbl 0963.68206
[29] Lovász, L, Hit-and-run mixes fast, Math. Program., 86, 443-461, (1999) · Zbl 0946.90116
[30] Lovász, L; Vempala, S, Hit-and-run from a corner, SIAM J. Comput., 35, 985-1005, (2006) · Zbl 1103.52002
[31] Mehrotra, S, On the implementation of a primal-dual interior point method, SIAM J. Optim., 2, 575-601, (1992) · Zbl 0773.90047
[32] Mehrotra, S; Huang, K-L, Computational experience with a modified potential reduction algorithm for linear programming, Optim. Methods Softw., 27, 865-891, (2012) · Zbl 1260.90123
[33] Naoum-Sawaya, J, Recursive central rounding heuristic for mixed integer programs, Comput. Oper. Res., 43, 191-200, (2014) · Zbl 1348.90493
[34] Narayanan, H.: Randomized Interior Point Methods for Sampling and Optimization. http://arxiv.org/abs/arXiv:0911.3950 (2009) · Zbl 1345.65045
[35] Smith, R, Efficient Monte Carlo procedures for generating points uniformly distributed over bounded regions, Oper. Res., 32, 1296-1308, (1984) · Zbl 0552.65004
[36] Vempala, S, Geometric random walks: a survey, Comb. Comput. Geom., 52, 573-612, (2005)
[37] Ye, Y.: Interior Point Algorithms: Theory and Analysis. Wiley, New York (1997) · Zbl 0943.90070
[38] Zabinsky, Z; Smith, R; McDonald, J; Romeijn, H; Kaufman, D, Improving hit-and-run for global optimization, J. Glob. Optim., 3, 171-192, (1993) · Zbl 0784.90084
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.