Section: New Results

Convergent methods based on aggregation in mathematical models

Participant : François Clautiaux

We designed several algorithms to aggregate variables in integer linear programs. Our methods first solve aggregated models, and converge to the optimal solution of the initial problem by iteratively refining the model.

The first method applies on a large network flow models that use a pseudo-polynomial number of variables. It is based on an initial aggregation of the vertices of the model and its iterative refinement using different optimization techniques. This led to dramatical improvements for a special case of vehicle routing problem. We proposed several theoretical results regarding convergence, suitable discretizations, wort-case analysis and approximation algorithms [44] .

The second method applies on column generation approaches for the cutting-stock problem. Our algorithm links groups of dual variables by linear constraints, leading to a problem of smaller dimension, whose solutions are dual-feasible for the initial problem. The corresponding "inner approximation" is iteratively refined by splitting the groups into smaller groups until an optimal dual solution is found. This method allows to produce a valid lower bound at each iteration, which is not the case for classical column-generation schemes [58] .