CIGI QUALITA MOSIM 2025

Hexaly is a global optimization solver that combines exact and heuristic methods. A set-based modeling formalism was introduced to simplify the modeling of combinatorial problems like routing or packing problems.

For instance, in a Vehicle Routing Problem (VRP), 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 difficult to integrate into a mathematical programming approach to compute lower bounds. A direct reformulation in a MILP model 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 state-of-the-art Branch-Cut-and-Price techniques from the literature. This talk will present the general approach, the algorithms used for the resolution, and some benchmarks for the classical CVRP and CVRPTW library.

Hexaly is a global optimization solver based on exact and heuristic techniques. In this talk, we will focus on its performance on scheduling problems in general, that is, problems with precedence constraints and disjunctive or cumulative resources, minimizing makespan, weighted sum of tardiness, etc.

Hexaly’s modeling formalism makes it straightforward to express many academic and industrial scheduling problems using only algebraic operators. These models, based on interval and list decision variables, have the advantage of being compact, enabling the solver to handle large-scale problems. Indeed, the algorithms implemented within Hexaly exploit this modeling and enable it to achieve very good performance on various scheduling problems: less than 2% optimality gap in 1 minute with up to 2,000 tasks on problems such as Job Shop, Flexible Job Shop, Open Shop, and Resource-Constrained Project Scheduling Problems.

It will also be shown that models written in Hexaly’s set-based formalism are more compact than their equivalents in the linear or constraint programming formalisms used by traditional solvers, such as Gurobi, Cplex, CP Optimizer, and OR-Tools CPSAT.