Optimization Online


An Empirical Evaluation of Walk-and-Round Heuristics for Mixed-Integer Linear Programs

Kuo-Ling Huang (jupiters1117***at***northwestern.edu)
Sanjay Mehrotra (mehrotra***at***iems.northwestern.edu)

Abstract: Geometric random walks have been proposed and analyzed for solving optimization problems. In this paper we report our computational experience with generating feasible integer solutions of mixed-integer linear programs using geometric random walks, and a random ray approach. A feasibility pump is used to heuristically round the generated points. Computational results on MIPLIB2003 and COR@L test library show that the walk-and-round approach improves the upper bound of a large number of test problems. In our experiments the hit-and-run 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.

Keywords: Mixed Integer Programs, Heuristics, Hit-and-Run Random Walk, Dikin Random Walk, Geometric Random Walk

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Dept. of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL, 60208, October 2010, revised February 2011.

Download: [PDF]

Entry Submitted: 09/15/2010
Entry Accepted: 09/16/2010
Entry Last Modified: 01/23/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society