Meet the Hexaly team at OR 2024

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 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 is a new kind of global optimization solver that combines exact and heuristic methods designed to tackle large-scale industrial problems. Several approaches have been developed by the operations research community to solve these large problems (e.g., heuristics, column generation, model decomposition, etc.). One of the main challenges for a model & run solver is to offer a modeling formalism, both generic and sparse. The genericity ensures that most of the problems can be modeled in the formalism while the sparsity ensures that the model stays linear in the size of the input. While SAT and MIP formalisms offer genericity, certain models require a quadratic or an exponential number of decisions and constraints (e.g. traveling salesman problem, bin packing or scheduling). Conversely, CP models offer global constraints that ensure sparsity but may lack genericity (e.g. non overlap with complex setup times for instance). To overcome these issues, Hexaly added set-based models to its formalism. Intervals, sets, and lists can be used as decision variables, and functions can be used to derive numerical expressions that can later be constrained or optimized. Vehicle routing problems, scheduling problems, and most variants of bin packing can be easily modeled with a combination of sets, lists, and intervals. The resolution of these problems is done using heuristics and exact techniques. This presentation will describe Hexaly models for packing, routing, and scheduling and give benchmark results on large instances with hundreds of thousands of items, clients, or tasks.

This talk describes an industrial application that helps schedule employees in a call center. The schedules are optimized for a week and aim to plan the activities of 30 to 200 employees, considering 2 to 5 different activities. Each employee has a weekly hourly contract and a skill level for each activity. The demand for the number of employees needed to perform each activity for a given week is determined by 30-minute periods. The goal is to meet this demand, and two penalty objectives are used to achieve this: minimizing understaffing and minimizing overstaffing.

A rule formalism has been defined to cater to each company’s specific needs. These rules allow different situations to be modeled, such as “Every employee must perform this activity for a maximum of 3 hours during the day.” They are included in the optimization model by adding an objective minimizing the penalty of non-respect for each rule. Furthermore, the employees’ preferences and wishes are considered when creating schedules to improve the quality of work life and retain employees.

This highly combinatorial optimization problem involving complex business constraints has been efficiently modeled using Hexaly. The solver optimized this problem with optimality guarantees for medium-sized instances within 30 seconds of running time. Based on this optimization problem, an industrial web application for workforce planning has been developed and will be demonstrated during the talk.

Hexaly is a mathematical optimization solver based on various operations research techniques, combining both exact and approximate methods such as linear programming, non-linear programming, constrained programming, primal heuristics. Its modeling formalism can be used to express a wide range of academic and industrial routing problems using list decision variables and lambda functions. These models are very compact, allowing the solver to handle even large-scale problems.

The Traveling Salesman Problem (TSP) is a classic combinatorial optimization problem, but it doesn’t capture some operational aspects like temporal dependencies. Unlike the classic TSP where distances between cities are constant, the Time-Dependent TSP (TDTSP) incorporates variable travel times, modeling real-world conditions where travel times depend on the time of day, traffic, or other temporal factors.

Traditionally, this problem is modeled with a discretization of the time horizon and a time matrix for each time step. This matrix can be constructed in various ways, and from it, the rest of the model can be created straightforwardly using Hexaly’s list based model. Other problems follow, such as the Time-Dependent Traveling Salesman Problem with Time Windows (TDTSPTW), where points have time windows for visits, and the Time-Dependent Capacitated Vehicle Routing Problem with Time Windows, where multiple capacitated vehicles are available to serve a set of points with demands.

We compare Hexaly’s results for the TDTSP and TDTSPTW with those from the literature. Hexaly improves nearly 25% of instances of up to 100 points while maintaining a gap close to 0% on the remaining instances.