Principles for the Design of Large Neighborhood Search |
| |
Authors: | Tom Carchrae J Christopher Beck |
| |
Institution: | (1) Actenum Corporation, 10th Floor, 675 West Hastings Street, Vancouver, British Columbia, V6B 1N2, Canada;(2) Department of Mechanical & Industrial Engineering, University of Toronto, Toronto, Canada |
| |
Abstract: | Large neighborhood search (LNS) is a combination of constraint programming (CP) and local search (LS) that has proved to be
a very effective tool for solving complex optimization problems. However, the practice of applying LNS to real world problems
remains an art which requires a great deal of expertise. In this paper, we show how adaptive techniques can be used to create
algorithms that adjust their behavior to suit the problem instance being solved. We present three design principles towards
this goal: cost-based neighborhood heuristics, growing neighborhood sizes, and the application of learning algorithms to combine
portfolios of neighborhood heuristics. Our results show that the application of these principles gives strong performance
on a challenging set of job shop scheduling problems. More importantly, we are able to achieve robust solving performance
across problem sets and time limits.
This material is based upon works supported by the Science Foundation Ireland under Grant No. 00/PI.1/C075, the Embark Initiative
of the Irish Research Council of Science Engineering and Technology under Grant PD2002/21, and ILOG, S.A. |
| |
Keywords: | Constraint programming Large neighborhood search Optimization Machine learning Scheduling |
本文献已被 SpringerLink 等数据库收录! |
|