LocalSolver sponsors OR 2022

LocalSolver is a global solver combining heuristic techniques and exact search to find good solutions and provide bounds quickly. In previous versions, LocalSolver introduced set and list decisions to easily model problems coming from the supply chain, such as vehicle routing, production scheduling, and packing. This talk will introduce the performance improvements coming with LocalSolver 11.0, released in early 2022.

A list can be used to model the sequence of clients visited by a truck in a routing application. LocalSolver 11.0 focused on performance improvements for routing problems with time windows (CVRPTW, PDPTW). In classical instances from the literature, the gap to the best-known solution is reduced to less than 4% in one minute of running time for CVRPTW and less than 3% for PDPTW.

List decisions can also be used to model scheduling problems and represent the sequence of tasks performed on a single disjunctive machine. LocalSolver 11.0 introduced a new heuristic search to find competitive solutions for scheduling problems quickly. This new technic allows LocalSolver to have solutions with a gap to the best-known solution smaller than 5% for the job-shop scheduling problem and smaller than 1% for the flexible job-shop problem with or without setup times on classical instances in less than one minute.

LocalSolver is a global optimization solver that combines exact and heuristic methods to solve all optimization problems. Its model-and-run approach allows users to solve combinatorial, continuous, or mixed variables problems even for large instances. A recent solver evolution was to implement a dedicated method for mixed variables problems in which the continuous part is linear. This paper aims to show how efficient this method can be when applied to large-scale industrial instances of the Split Delivery Vehicle Routing Problem (SDVRP).

The method’s main idea exploits the existing local search algorithm within the solver. It runs in two steps. First, a local search movement is applied to the combinatorial variables only (ie all variables that are not continuous). Then, once all the combinatorial variables have been fixed, the corresponding subproblem is assumed linear regarding the continuous variables. This subproblem is solved with a dual simplex algorithm. This method is then sped up with simplex warm start between two iterations and Farkas rays analysis.

The Split Delivery Vehicle Routing Problem (SDVRP) falls within the scope of the above algorithm. Structural constraints and customers order can be represented with combinatorial variables and the delivered quantities with continuous variables.

This approach proved extremely efficient for an SDVRP-like problem coming from one of LocalSolver Japanese customers. This method was benchmarked against pure local search in LocalSolver 10.5 and a compact MIP model solved with Gurobi 9.1. Instances have up to 100 customers and 120 trucks. The presented method was the only one capable of providing non-trivial solutions to the biggest instances in less than 15 minutes.

Black-box functions are functions for which the analytical formula is not available: only an oracle can evaluate them. These functions are usually computationally expensive and the number of evaluations of the oracle is often limited, so each point to be evaluated must be chosen carefully.

In LocalSolver, a global optimization solver using exact and heuristic methods, the approach implemented is based on surrogate modeling. This method approximates the objective function by a radial basis function (RBF). The algorithm alternates between exploitation phases, where the surrogate model is optimized, and exploration phases, allowing to explore the search space and avoid local optima. The resulting submodels are then solved with the LocalSolver nonlinear solver to generate a new point to evaluate.

Constraint handling has been added for black-box models in recent versions of LocalSolver. There are two types of constraints:

• Analytical constraints, for which the analytical formula is available. They can be written directly in the solver formalism. As the solver gains more knowledge about spatial search, it can avoid evaluating points that do not satisfy the analytical constraints, thus saving the limited evaluation budget at our disposal.

• Concerning black-box constraints, they are also approximated by an RBF surrogate. A margin criterion is defined at each constraint to help satisfy the feasibility of the model. This criterion is adjusted at each iteration according to the feasibility of the previously evaluated point, which increases the chances of obtaining the optimum even if it is located at the limits of the solution space.

The implemented approach generates good results comparable to those obtained by state-of-the-art black-box optimization solvers.

Hierarchical multi-objective optimization deals with problems that have several objective functions that are ordered by decreasing priority. Solving these problems exactly requires several steps: one optimization problem is solved per objective, where that objective is optimized and every previous objective is constrained to be equal to its optimal value (“optimality constraints”). All numerical optimization solvers rely on numerical tolerances. The optimality tolerance limits the computation time: the solver stops when the gap between the solution and the lower bound is small enough. This work explores the mixing of the two concepts, i.e. when each step of the multi-objective problem resolution is solved up to an optimality tolerance. We describe the impact of this tolerance on the solving process, the optimal solutions, and practical implementation requirements. We illustrate these phenomena with examples and experiments with various solvers. First, the optimality constraints must be relaxed by only enforcing a one-sided bound, either by its primal value or by shifting its dual value. We show neither approach is satisfactory: the solutions tend to take suboptimal values, especially when contradictory objectives are. Commercial solvers often run several algorithms in parallel. Depending on the run, this can add uncertainty and lead to different optimal solutions. This effect is amplified in a multi-objective setting and may lead to disjoint primal-dual intervals for the same objective. Moreover, exact optimal solutions may be proven sub-optimal and the gap between the true optimal value and its approximate counterpart may be arbitrarily large.

Transport infrastructure or building sites require the movement of large quantities of excavated soils and building materials. The soil extracted from these construction sites can present different pollution levels, which require specialized centers treatments. Once the treatment has been completed, the inert soil obtained can be reused as backfill for earthworks, while the extracted materials such as gravel can be used as raw material for other construction sites. The different trips needed to move these materials and the operational constraints of construction sites and truck carriers lead to a difficult vehicle routing problem. The goal is to create routes that minimize the distance traveled with empty trucks, increasing operational efficiency and minimizing the carbon impact implied by these moves.

This talk will present how such a problem was solved in a business application developed for Hesus, a French company providing services to the construction industry. In a large urban region like the Paris area, several dozens of construction sites are delegating the transportation of soils and materials to this company each day, which becomes responsible for building routes that efficiently link sites and centers using trucks from external carriers. It represents 100 trucks performing 500 loads and traveling 25 000 kilometers daily.

The resolution of this problem is based on a route generation approach. First, interesting route candidates are generated using an enumeration scheme. Secondly, a combination model is solved using LocalSolver, a generic global optimization solver, to identify the best selection of routes among the candidates. Such an approach presents several advantages, which will be discussed during the presentation.