An empirical evaluation of a walk-relax-round heuristic for mixed integer convex programs

Kuo Ling Huang, Sanjay Mehrotra*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)559-585
Number of pages27
JournalComputational Optimization and Applications
Volume60
Issue number3
DOIs
StatePublished - Apr 2015

Keywords

  • Feasibility pump
  • Geometric random walk
  • Mixed integer convex programs
  • Primal heuristic

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'An empirical evaluation of a walk-relax-round heuristic for mixed integer convex programs'. Together they form a unique fingerprint.

Cite this