Hexaly 13.5

Announcement

Marion Technical Writer February 4, 2025

We are pleased to announce the release of Hexaly 13.5, which includes many new features and performance enhancements. The “gaps” mentioned below are the relative gaps in % between the solutions computed by Hexaly within 1 minute on a standard server (AMD Ryzen 7 7700 processor, 8 cores, 3.8 GHz, 32MB cache, 32GB RAM) and the best known solutions available by the research, computed using dedicated algorithms within days of running times on much more powerful hardware.

Routing

Hexaly 13.5 brings significant performance improvements for Vehicle Routing Problems (VRP) with various types of constraints and objectives:

• Dial-a-Ride Problem (DARP): 93 new records over the 96 instances of the realistic Chassaing dataset with up to 128 points obtained within 1 minute, with an average improvement of 4.9% of the best known solutions in the research; average gap of 2.4% in 1 minute for the classical Cordeau dataset with up to 144 points.
• Team Orienteering Problem (TOP): average gap of 0.4% within 1 minute for instances with up to 401 points.
• Prize Collecting Vehicle Routing Problem (PCVRP): average gap of 1.29% within 1 minute for instances with up to 1,000 points.
• Prize Collecting Vehicle Routing Problem with Time Windows (PCVRPTW): average gap of 4.4% within 1 minute for instances with 1,000 points.
• Pickup and Delivery Problem with Time Windows (PDPTW): average gap of 0.7% in 1 minute on the Li & Lim dataset with up to 1,000 points.
• Split Delivery Vehicle Routing Problem (SDVRP): average gap of 1.7% in 1 minute on the instances from the 2021 DIMACS challenge with up to 280 points.
• Very Large-Scale Capacitated Vehicle Routing Problem (CVRP): average gap of 3.9% in 1 minute on Arnold, Gendreau, and Sörensen instances from 3,000 to 30,000 points.

The lower bounds delivered by Hexaly 13.5 are significantly improved for Vehicle Routing problems using automated reformulations and Branch-Cut-Price techniques:

• Traveling Salesman Problem (TSP): average optimality gap below 0.5% after 1 minute for all TSPLIB instances with up to 8,000 points.
• Capacitated Vehicle Routing with Time Windows (CVRPTW): average optimality gap below 2.4% after 1 minute for all instances with up to 200 points.
• Heterogenous Vehicle Routing Problem (HVRP): average optimality gap below 2.7% after 1 minute for a subset of the realistic dataset from Duhamel, Lacomme, and Prodhon with up to 183 points.

Scheduling

Hexaly 13.5 brings significant performance improvements for Batch Scheduling Problems and very large-scale Job Shop Scheduling Problems:

• Job Shop Scheduling Problem (JSSP): average gap of 1.2% on very large-scale instances with up to 1,000,000 activities within 1 minute of running time.
• Batch Scheduling Problem: average gap of 4.5% on instances with up to 100,000 activities within 1 minute of running time.

Packing

Hexaly 13.5 introduces performance improvements for Bin Packing Problems With Conflicts (BPPC) using the intersection operator. The average gap after 1 minute on the Muritiba et al. instances reaches 0.5% using the following model:

binContainingItem = find(bins, i);
constraint count(intersection(binContainingItem , incompatible_items_with_i)) == 0;

Modeler & APIs

Hexaly 13.5 introduces a const_array operator to offer a compact way to store your arrays of numbers:

// compact representation of a constant array
w <- constArray({1, 3, 5, 2});
constraint sum[i in 0...4] (w[i] * x[i]) <= 8;

Hexaly 13.5 also introduces a union operator to describe the union of two sets:

set1 <- set(10);
set2 <- set(10);
setUnion <- union(set1, set2);
constraint count(intersection(setUnion, {4, 5, 6})) <= 0; // values 4, 5, 6 cannot be in set1 or set2

Interval operator introduced in the previous version of Hexaly now supports equality and inequality:

interval1 <- interval(0, 100);
interval2 <- interval(0, 100);
constraint interval1 == interval2;

Templates

New templates are available for Routing, Scheduling, and Packing problems to help you get started effortlessly with Hexaly: