Program > By author > Dupin Nicolas

Integer Linear Programming (ILP) solvers made recent progress with heuristics based on the linear relaxation and variable fixing.
On one hand, it allowes to cut off earlier branches of the Branch&Bound tree, and on an other hand, very good solutions are found quickly, that allowes to uses an ILP solver in a heuristic mode with a time limit.
Most of the resolution time in a Branch& Bound algorithm is devoted to prove the optimality of the solution.

Local search heuristics improve a given solution, with modification allowed in a defined neighbourhood.
Difficulties come with local extrema, where no local improvement is possible. Variable Neighbourhood Search (VNS) basic idea is to consider different types of neighbourhoods, and to change systematicaly of neighbourhood within a local search, to have less local extrema. A VNS local extremum is thus is local extremum for all considered neighbourhoods.

This paper shows how an ILP solver in a heuristic mode can be very useful and effective in a VNS scheme, considering for neighbourhoods small Integer Linear Programs. This algorithm can naturally be parallelized. These concepts are applied on short term Unit Commitment Problems with discrete dynamic constraints, long term scheduling of nuclear power plants and to the classical Vehicle Routing Problem with Time Windows.

For these applications, solutions found with an ILP formulation in a defined time limit were imprioved with our VNS scheme.