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.
Citation
Dept. of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL, 60208, October 2010, revised February 2011.
Article
View An Empirical Evaluation of Walk-and-Round Heuristics for Mixed-Integer Linear Programs