Paper Info
Title
An empirical evaluation of a walk-relax-round heuristic for mixed integer convex programs
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.
Year
DOI
Venue
2015
10.1007/s10589-014-9693-5
Computational Optimization and Applications
Keywords
Field
DocType
Mixed integer convex programs,Geometric random walk,Feasibility pump,Primal heuristic
Integer,Mathematical optimization,Heuristic,Random walk,Luus–Jaakola,Quadratic equation,Regular polygon,Commercial software,Mathematics,Consistent heuristic
Journal
Volume
Issue
ISSN
60
3
0926-6003
Citations 
PageRank 
References 
2
0.39
28
Authors
2
Name
Order
Citations
PageRank
Kuo-Ling Huang1804.95
Sanjay Mehrotra252177.18