A Hybrid MIP-based Large Neighborhood Search Heuristic for Solving the Machine Reassignment Problem

by Wojciech Jaśkowski, Marcin Szubert, Piotr Gawron
Abstract:
We present a hybrid metaheuristic approach for the machine reassignment problem, which was proposed for ROADEF/EURO Challenge 2012. The problem is a combinatorial optimization problem, which can be viewed as a highly constrained version of the multidimensional bin packing problem. Our algorithm, which took the third place in the challenge, consists of two components: a fast greedy hill climber and a large neighborhood search, which uses mixed integer programming to solve subproblems. We show that the hill climber, although simple, is an indispensable component that allows us to achieve high quality results especially for large instances of the problem. In the experimental part we analyze two subproblem selection methods used by the large neighborhood search algorithm and compare our approach with the two best entries in the competition, observing that none of the three algorithms dominates others on all available instances.
Reference:
A Hybrid MIP-based Large Neighborhood Search Heuristic for Solving the Machine Reassignment Problem (Wojciech Jaśkowski, Marcin Szubert, Piotr Gawron), In Annals of Operations Research, volume 242, 2016.
Bibtex Entry:
@Article{Jaskowski2016hybrid,
  Title                    = {A Hybrid {MIP}-based Large Neighborhood Search Heuristic for Solving the Machine Reassignment Problem},
  Author                   = {Wojciech Jaśkowski and Marcin Szubert and Piotr Gawron},
  Journal                  = {Annals of Operations Research},
  Year                     = {2016},
  Volume                   = {242},
  Number                   = {1},
  Pages                    = {33--62},
  issn="1572-9338",
  url="http://dx.doi.org/10.1007/s10479-014-1780-6",

  Abstract                 = {We present a hybrid metaheuristic approach for the machine reassignment problem, which was proposed for ROADEF/EURO Challenge 2012. The problem is a combinatorial optimization problem, which can be viewed as a highly constrained version of the multidimensional bin packing problem. Our algorithm, which took the third place in the challenge, consists of two components: a fast greedy hill climber and a large neighborhood search, which uses mixed integer programming to solve subproblems. We show that the hill climber, although simple, is an indispensable component that allows us to achieve high quality results especially for large instances of the problem. In the experimental part we analyze two subproblem selection methods used by the large neighborhood search algorithm and compare our approach with the two best entries in the competition, observing that none of the three algorithms dominates others on all available instances.},
  Doi                      = {10.1007/s10479-014-1780-6},
  Keywords                 = {hybrid metaheuristics, large neighborhood search, local search, mixed integer programming, machine reassignment},
  Owner                    = {Wojciech},
  Timestamp                = {2014.01.18},
}

This entry was posted by . Bookmark the permalink.