You are here

Constraint-Based Very Large-Scale Neighborhood Search

TitleConstraint-Based Very Large-Scale Neighborhood Search
Publication TypeConference Proceedings
Year of Conference2009
AuthorsMouthuy, Sébastien, Deville Yves, and Van Hentenryck Pascal
Conference Name23rd national conference of the Belgian Operations Research Society (ORBEL2009)

We describe here our generic abstractions for Very Large-Scale Neighborhoods (VLSN). These neighborhoods are used in local search. Their size is exponential but the best neighbor can be computed in polynomial time. VLSN have proven to be very efficient on a large set of problems. However designing such neighborhoods requires high development efforts. We studied abstractions for VLSN where the moves are defined as the composition of several simpler operators. The majority of VLSN proposed in the litterature falls into this category. The crucial point behind these VLSN is the definition of a notion of independance: we want to select a set of operators such that they do not have any side-effect on each other. This allows to compute a priori the effect of each operators on the current solution and to ensure that this effect will remain unchanged if we apply a set of \emph{independant} operators. The notion of independance has been abstracted in our implementation into the constraints and objectives. This has the great advantage that the notion of independance has not to be defined for each problem tackled by VLSN. This leads to the ability of defining a combinatorial optimization problem in Comet by means of high-level constraints and objectives and to efficiently solve it by VLSN technology without any additional implementation. One could add any constraint or modify the objective function without having to change anything to the implementation of the VLSN search algorithm. Our implementation also has generic support for meta-heuritics such as Tabu mechanisms and simulated annealing.

Full text: