Meet Hexaly at SOAK 2024

Hexaly Optimizer is a global mathematical solver combining exact and heuristic techniques. It offers an innovative set-based and nonlinear modeling formalism, that enables users to build simple and compact models for many types of combinatorial problems. These set-based modeling features also provide the solver with higher-level structures, that it can exploit by applying various techniques from the literature to obtain state-of-the-art results on routing, scheduling, and packing problems. In this workshop, we will see how to take advantage of this modeling formalism to model and solve routing problems. For that, we will invite participants to use Hexaly Studio, a specialized online code editor enhanced with dashboards and widgets to visualize the solutions.

Hexaly Optimizer is a “model and run” mathematical optimization solver based on various exact and heuristic methods. The presentation will introduce the different components of Hexaly Optimizer’s primal heuristics through disjunctive scheduling problems.

We will first show how its modeling formalism can be used to express various academic and industrial scheduling problems using interval and list decision variables. These models are very compact, which enables the solver to handle even large-scale problems.

Detecting non-overlap constraints in the model provides the solver with valuable information, which can be exploited through various scheduling-specific movements implemented in Hexaly Optimizer’s neighborhood search. However, due to the tightness of precedence and non-overlap constraints in good solutions to disjunctive scheduling problems (Job Shop Scheduling Problem, for example), such a small-neighborhood search alone struggles to obtain good performance.

Hexaly Optimizer overcomes this issue by reinforcing its neighborhood search component with a solution repair algorithm based on constraint propagation. When a move renders the solution infeasible, it is gradually repaired, one constraint at a time, by heuristically shifting the variables just enough to repair. To extend the transformation rather than cancel it, and to ensure the procedure is fast, we impose never to backtrack on a previous decision to increase or decrease a variable’s value.

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 certain 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 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 13.0 automatically detects such structures in a user model and reformulates them in an extended MILP model to compute lower bounds. This model is solved efficiently using state of the art branch-cut-and-price technics from the literature. This talk will present the general approach and the algorithms used for the resolution and some benchmarks on the classical CVRP library.