An empirical evaluation of walk-and-round heuristics for mixed integer linear programs

Kuo Ling Huang, Sanjay Mehrotra*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

Feasibility pump is a general purpose technique for finding feasible solutions of mixed integer programs. In this paper we report our computational experience on using geometric random walks and a random ray approach to provide good points for the feasibility pump. Computational results on MIPLIB2003 and COR@L test libraries show that the walk-and-round approach improves the upper bounds of a large number of test problems when compared to running the feasibility pump either at the optimal solution or the analytic center of the continuous relaxation. In our experiments the hit-and-run walk (a specific type of random walk strategy) started from near the analytic center is generally better than other random search approaches, when short walks are used. The performance may be improved by expanding the feasible region before walking. Although the upper bound produced in the geometric random walk approach are generally inferior than the best available upper bounds for the test problems, we managed to prove optimality of three test problems which were considered unsolved in the COR@L benchmark library (though the COR@L bounds available to us seem to be out of date).

Original languageEnglish (US)
Pages (from-to)545-570
Number of pages26
JournalComputational Optimization and Applications
Volume55
Issue number3
DOIs
StatePublished - Jul 1 2013

Keywords

  • Dikin random walk
  • Geometric random walk
  • Heuristics
  • Hit-and-run random walk
  • Mixed integer programs

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Applied Mathematics

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

Cite this