New release: LocalSolver 12.0

Announcement

Frédéric Senior Optimization Scientist June 19, 2023

Vehicle Routing

Vehicle Routing problems with 1,000 deliveries are now solved to near-optimality within 1 minute of running time. The “gap” mentioned below is the relative gap in % between the solutions computed by LocalSolver 12.0 within 1 minute of running time on a standard server (Intel Xeon E3-1230 processor, 4 cores, 3.6 GHz, 8MB 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.

• Capacitated Vehicle Routing Problem with Time Windows (CVRPTW): average gap of 2.3% for instances with up to 1,000 deliveries.
• Pickup and Delivery Problem with Time Windows (PDPTW): average gap of 1.7% for instances with up to 1,000 deliveries.

In addition, LocalSolver 12.0 brings significant performance improvements in solving real-life route optimization problems involving preassignments, mutual exclusion of clients delivered by the same truck, site restrictions, precedences, transhipments, split deliveries, and objectives related to resource usage costs (ex: driving hours or working hours).

Scheduling

LocalSolver 12.0 introduces Interval decisions and related operators: start, end, length, contains. Intervals simplify the modeling of scheduling problems, as they can be used to represent the time span of the tasks. Thanks to interval variables, many problems can be modeled in a concise, straightforward, and natural way, such as:

• Job Shop Problem (JSP)
• Job Shop Problem with Intensity
• Flexible Job Shop (FJSP)
• Flexible Job Shop with Setup Times
• Open Shop
• Resource Constrained Project Scheduling Problem (RCPSP)
• Flexible Resource Constrained Project Scheduling Problem (Flexible RCPSP)

The use of interval variables is illustrated in the following example:

    // Interval decisions: time range of each task
    tasks[i in 0...nbTasks] <- interval(0, horizon);

    // Task duration constraints
    for [i in 0...nbTasks]
        constraint length(tasks[i]) == duration[i];

    // Precedence constraints between the tasks
    for[i in 0...nbTasks][s in 0...nbSuccessors[i]] {
        constraint tasks[i] < tasks[successors[i][s]];
    }

    makespan <- max[i in 0...nbTasks] (end(tasks[i]));

    minimize makespan;

LocalSolver 12.0 improves lower bounds computed on multiple scheduling problems with various objectives. The results below show the average dual gap to best known solutions reported within 1 minute of running time by LocalSolver for a variety of problems:

Facility Location

Single Source Capacitated Facility Location Problem: average gap to best known solutions of 3.8% within 1 minute on networks with up to 1,500 customers. The benchmark comes from the paper by P. Avella and M. Boccia (2009): A cutting plane algorithm for the capacitated facility location problem. Computational Optimization and Applications, vol. 43, pp. 39–65.

Mixed-Integer Nonlinear Optimization (MINLP)

Combinatorial Portfolio Optimization is a variant of the traditional Markowitz portfolio selection problem with a cardinality constraint on the number of selected assets. On this Mixed-Integer Nonlinear Optimization problem (MINLP), LocalSolver 12.0 delivers near-optimal solutions in 10 seconds on instances with up to 2,000 assets.

Simulation Optimization

• LocalSolver 12.0 extends its lexicographic multiobjective capability to Simulation Optimization.
• Best known solutions achieved in less than 150 function evaluations for 134 instances over the 199 instances in our internal benchmark, composed of industrial and academic, unconstrained and constrained instances (+10 compared to LocalSolver 11.5). The average number of evaluations to reach the best solution found with LocalSolver 12.0 is 70.8 (compared to 75.0 for LocalSolver 11.5).

Modeling APIs and language (LSP)

• LocalSolver 12.0 introduces a Geodata module for fast computation of distance and time matrices, which are crucial data for Route Optimization: our module computes 1,000 x 1,000 matrices within 1 second of running time.
• LSP modeling language now supports the syntax “M…N” to create ranges from M (inclusive) to N (exclusive).
• LocalSolver 12.0 is available for Linux arm64 architecture.

LocalSolver Studio

LocalSolver Studio provides developers with the perfect low-code SaaS platform for developing, debugging, and running optimization applications written with the LocalSolver modeling language. Among its many features, the studio offers:

• A powerful code editor with advanced features like syntax checking and auto-completion to help you write concise and error-free models.
• Secure file storage in the cloud, providing ample disk space for unlimited projects accessible from any device.
• An integration with LocalSolver Cloud, enabling you to run your LocalSolver models directly from the browser without installation or configuration.
• Intuitive visualization tools for building user interfaces, so you can easily input data and visualize your optimization results.
• LocalSolver No-Code Modeler, generating mathematical optimization models and interfaces for you, in a few clicks.

Try LocalSolver Studio right now by registering here.

Code Templates

New Code Templates are available for Vehicle Routing and Scheduling problems to help you get started effortlessly with LocalSolver:

We are at your disposal to accompany you in discovering LocalSolver 12.0. Register here to get free trial licenses. Don’t hesitate to contact us for further information or support.