Technology Showcases

Computing Dual Bounds of Set-based Models Using Column Generation and Column Elimination in Hexaly

Presented by: Julien Darlay

Hexaly is a model-and-run solver that integrates heuristics and exact methods. A set-based modeling formalism was introduced to simplify the modeling of some combinatorial problems, like routing or packing problems. For instance, in a routing problem, list variables can be used to model the sequence of visits made by each truck. These decision variables are well suited for a heuristic search but are much more challenging to integrate into a mathematical programming approach to compute lower bounds. A direct MILP reformulation introduces a quadratic number of binary decisions with several big M constraints, leading to poor scalability and bounds. Hexaly automatically detects such structures in a user model and reformulates them in an extended MILP model to compute lower bounds parallel to a heuristic search. This model is solved efficiently using the literature’s state-of-the-art branch-and-cut-and-price techniques and column elimination algorithms. This talk will present the general approach, the algorithms used for the resolution, and some benchmarks on the classical vehicle routing and packing problems.