Meet the Hexaly team at ISMP 2024

Hexaly Optimizer, formerly known as LocalSolver, 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 in a mathematical programming approach to compute lower bounds. A direct reformulation in a Mixed Integer Linear Programming (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 CVRP (capacitated vehicle routing problem) library.

Hexaly is a new kind of global optimization solver. Its modeling interface is nonlinear and set-oriented. It also supports user-coded functions, thus enabling black-box optimization and simulation optimization. Thus, Hexaly APIs unify modeling concepts from mixed-linear, nonlinear, and constraint programming. Under the hood, Hexaly combines various exact and heuristic optimization methods: spatial branch-and-bound, simplex methods, interior point methods, augmented Lagrangian methods, automatic Dantzig-Wolfe reformulation, column and row generation, propagation methods, local search, direct search, population-based methods, and surrogate modeling techniques. 

Regarding performance benchmarks, Hexaly distinguishes itself against the leading solvers in the market, like Gurobi, IBM Cplex, and Google OR Tools, by delivering fast and scalable solutions to problems in the spaces of Supply Chain and Workforce Management like Routing, Scheduling, Packing, Clustering, Matching, Assignment, and Location problems. For example, on notoriously hard problems like the Pickup and Delivery Problem with Time Windows or Flexible Job Shop Scheduling with Setup Times, Hexaly delivers solutions with a gap to the best solutions known in the literature smaller than 1% in a few minutes of running times on a basic computer.

Hexaly is a new kind of global optimization solver that combines exact and heuristic methods. Heuristics like local search are known for delivering quality primal solutions to large-scale combinatorial optimization problems in short running times. However, these are difficult to apply when continuous decisions are involved, as in inventory routing, nuclear power plant outage scheduling, portfolio optimization with limited assets, and sparse regression. To address these problems, Hexaly automatically decomposes them into a pure combinatorial problem and a continuous subproblem parametrized by the combinatorial decisions. The combinatorial space is explored by applying local search techniques. Once a new feasible solution is found for integer decisions, an exact continuous algorithm is launched to determine continuous decisions optimally: simplex methods when the continuous subproblem is linear and interior point methods when it is nonlinear. Sensitivity analysis is performed to guide the heuristic search in the combinatorial space. The talk will present the overall approach and illustrate it on the problems previously mentioned.