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

Kuo-Ling Huang and Sanjay Mehrotra ()

Computational Optimization and Applications, 2013, vol. 55, issue 3, 545-570

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). Copyright Springer Science+Business Media New York 2013

Keywords: Mixed integer programs; Heuristics; Hit-and-run random walk; Dikin random walk; Geometric random walk (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10589-013-9540-0 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:55:y:2013:i:3:p:545-570

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-013-9540-0

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().