EURO 2025 Leeds

Hexaly is a new kind of global optimization solver. Hexaly APIs unify modeling concepts from mixed-linear programming, nonlinear programming, and constraint programming. Its modeling interface is nonlinear and set-oriented. It also supports user-coded functions, thus enabling black-box optimization and, more particularly, simulation optimization. Under the hood, Hexaly combines various exact and heuristic optimization methods: spatial branch-and-bound, simplex methods, interior-point methods, automatic Dantzig-Wolfe reformulation, column and row generation, propagation methods, local search, population-based methods, and surrogate modeling techniques for black-box optimization. We illustrate these new modeling concepts on the seminal Traveling Salesman Problem (TSP), thus offering natural and compact modeling of the problem and performance on par with Concorde, the renowned TSP solver.      

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 (problems with precedence constraints and disjunctive or cumulative resources, minimizing makespan, weighted sum of tardiness, etc.). Hexaly’s nonlinear and set-based modeling formalism makes it very straightforward to express many academic and industrial scheduling problems using only generic operators. These models combine two kinds of decision variables: intervals and lists. On the one hand, we use interval decisions to model the time span of the tasks. Besides, we use list decisions (decisions whose values are permutations) to represent the order in which the tasks are scheduled on each disjunctive resource.

These interval and list-based models 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 one minute with up to 2,000 tasks on classical problems such as the Job Shop Scheduling Problem, Flexible Job Shop Scheduling Problem, Open Shop Scheduling Problem, or Resource-Constrained Project Scheduling Problem. We will also show that models written in Hexaly’s set-based formalism are more compact than their equivalents in the linear or constraint programming formalisms used by other classical solvers, such as Gurobi or CP Optimizer.

Given a scheduling problem expressed in the Hexaly framework (a model and run mathematical optimization solver based on various exact and heuristic methods), we aim to quickly compute a reasonable lower bound within a negligible time compared to the problem’s total solving time. To address this challenge, our approach employs classical scheduling algorithms with logarithmic-linear complexity on single-machine subproblems.

We handle various objective functions, such as the (weighted) number of late jobs, weighted completion times, and maximum lateness, by leveraging well-known algorithms like Moore-Hodgson, Potts-Wassenhove, Smith, and Jackson. The main idea lies in detecting these expressions and exploiting the precedence constraints of the scheduling problem.

The precedence constraints allow us to distribute due dates or weights across machines, enabling more tasks to be considered in the lower bound computation. This distribution allows us to compute lower bound values for each machine and ultimately select the most promising one. Experimental results on Job-Shop Scheduling Problems demonstrate significant improvements across different objective types. We achieved mean gap reductions of up to 31%, validating the effectiveness of our approach in quickly providing reasonable lower bounds.

Hexaly is a “model and run” mathematical optimization solver based on various exact and heuristic methods. In this talk, we will focus on how its modeling formalism can be used to express batch scheduling problems using interval and set decision variables. Batch scheduling problems are scheduling problems where tasks can be grouped into batches and made synchronously. These models are intuitive and compact, thanks to high-level decision variables and set-based operators. A set variable represents a subset of tasks using their indices, representing a batch’s content. Interval variables will represent the position in time of the batches.

The algorithms implemented within the solver take advantage of these compact formulations based on interval and set decision variables. For example, the solver’s local search component comprises various local neighborhoods working on set decision variables. We adapted these existing moves to batch scheduling problems by making them efficiently work on the interval variables as well: whenever the value of a set variable is changed, the value of the interval variable corresponding to the same batch is changed accordingly. These algorithms, as well as other methods implemented, enable Hexaly to achieve very good performances on batch scheduling problems: an average of 4.5% in one minute with up to 100,000 tasks.

Vehicle routing problems aim to determine efficient routes for one or more vehicles to visit a set of locations. In classic cases, every point must be visited exactly once. However, several industrial applications require models with some locations being optional. The choice of points to visit adds a new layer of combinatorial decisions.

This presentation focuses on two such problems: the Team Orienteering Problem (TOP) and the Prize-Collecting VRP (PCVRP). In the TOP, the goal is to maximize collected benefits while respecting distance constraints, whereas PCVRP seeks a balance between minimizing travel distance and uncollected benefits. We explore how to model and solve these problems using Hexaly, an optimization solver combining exact and heuristic methods.

Hexaly adopts a compact set-oriented modeling formalism. For routing problems the decision variables manipulated by the solver are lists, they are handled as permutations on dynamic subsets of the points. Each vehicle’s route is represented as a list. The solver provides built-in set-based operators to manage constraints and objectives. This approach allows for concise and scalable formulations, making it easy to incorporate additional constraints and objectives as needed.

Hexaly’s solutions, after 1 minute of running time, are within 1% of the best known solutions on the academic instances for those two problems. We will also show that the solver scales to industrial cases with more than 10,000 points.