To search, Click below search items.


All Published Papers Search Service


A Monte Carlo Iterative Optimization Algorithm for Integer Linear Programming Problems


Takeshi Tengan, Takeo Yoshida, and Morikazu Nakamura


Vol. 18  No. 11  pp. 60-67


In this paper, we present a new optimization technique for integer linear programming problems. The proposed method is a metaheuristic algorithm and improves solutions by iterating the problem reduction and solving the reduced problem. The algorithm is a hybrid approach in which we use a Metropolis-Hastings algorithm and an exact solver and has a good characteristic such that the reduced problem at each iteration has better or equal quality feasible solutions. The experimental evaluation shows that our method can obtain a good quality of solutions within reasonable execution time for hard problems specified in MIPLIB2010.


Integer Programming, Iterative Optimization, Problem Reduction, Monte Carlo Method, Metaheuristics