LocalSolver Intro: My Notes on the All-in-one Mathematical Programming Solver for Large-scale Mixed-variable Optimisation

Since modelling is the master and computation the servant, no computational method should presume to have its own solver. This means there should be no CP solvers, no MIP solvers, and no SAT solvers.

All of these techniques should be available in a single system to solve the model at hand. They should seamlessly combine to exploit problem structure. Exact methods should evolve gracefully into inexact and heuristic methods as the problem scales up.

John N. Hooker (2007) “Good and Bad Futures for Constraint Programming (and Operations Research)” Constraint Programming Letters 1, pp. 21-32

Mixed Integer Linear Programming (MILP)

Mixed Integer Linear Programming (MILP) is undoubtedly one of the most powerful tools of Operations Research (OR).

Its ease of use appeals to OR professionals:

• the user models the problem as an integer linear program in simple & generic formalism
• the MIP engine solves it by branch & bound & cut.

This "model & run" approach, when effective, reduces considerably development and maintenance of optimisation software, and other tree search-based technologies like Constraint Programming (CP) are following the way.

Faced with situations such as large-scale nonlinear optimisation problems, OR practitioners often find MIP or CP solvers ineffective.

Mixed-integer programming techniques (B&B, B&C, BCP) are:

• Designed for proving optimality & unsatisfiability
• Not designed to find feasible solutions

MIP solvers still fail to find feasible solutions for real-life instances with no more than 10,000 binaries.

Tree search is limited. They address this problem by implementing local search heuristics.

Pure tree-search (TS) techniques will remain powerless for solving very large-scale combinatorial problems (millions of binaries).

1) Relaxation is often useless but costs a lot in efficiency. So why losing running time to enumerate partial solutions?

2) Why an incomplete TS should be better than LS? Moreover, TS is not really suited for exploring randomly a search space.

Facts: State-of-the-art IP solvers integrate more and more LS ingredients (Local Branching, Relaxation Induced Neighbourhood Search).

Local Search (LS)

In contrast with tree search techniques, Local Search (LS) involves applying iterative changes (called moves) to improve the objective function. This technique allows operations researchers to obtain good-quality solutions in a reasonable time (in the order of minutes).

• LS needs only linear memory in problem size
• LS deals well with large and over-constrained problems
• LS is good for online algorithms (dynamically changing constraints)
• LS produces good-quality solutions within short running times
• LS provides practical solution for practical problems
• LS is incomplete & non deterministic search, randomised moves & incremental computation, run faster.
• But LS is not metaheuristics as generally assumed.

However, designing and implementing local search algorithms is not straightforward, even with frameworks that have been designed to help the programmer, inducing extra costs (development & maintenance).

The algorithmic layer dedicated to the evaluation of moves is particularly difficult to engineer, because it requires an expertise both in algorithms and computer programming. More algorithmic, less mathematical (analytical).

What are the needs in business and industry?

1) Clients have optimisation problems, and rarely satisfaction problems.

“No solution found” is rarely an acceptable answer for users. Thus, once the model is well stated, finding a feasible solution should be easy.

2) Optimal solution is not what clients really want.

• Proof of optimality is much less what they want
• They want first a nice software providing good solutions quickly

Fundamental Principle of Autonomous Local Search

The LS solver must work in the same way that an LS practitioner works. This implies that LS solver performs structured moves to maintain the feasibility of solutions at each iteration, whose evaluation is accelerated by exploiting invariants induced by the structure of the model.

The most simple generic move is the change of the value of a decision, if we want to move from one feasible solution to another, as in most hand-made local search algorithms, more structured moves are required. The solver builds such moves by analysing the structure of the model.

More generally, following ejection chains or ejections cycles in the constraint hyper-graph yields very powerful moves. In addition to these small neighbourhoods, larger neighbourhoods can be explored by combining smaller neighbourhoods within a destroy & repair mechanism. Finally, the identification of special combinatorial structures can trigger the activation of specific neighbourhoods. Note that the neighbourhoods can be explored almost randomly or by targeting moves with higher probability of success.

The exploration of the search space is distributed on several threads with periodic synchronisation. The global diversification of the search is ensured through simulated annealing with reheating and restart mechanisms. Statistics on the performance of the moves are dynamically exploited to improve the overall performance along the search.

Components that make the algorithm efficient are:

• An incremental machinery that quickly evaluates the impact of a transformation of the solution;
• Multiple autonomous moves exploiting the combinatorial structure of the model to explore feasible neighbourhoods of a solution;
• A global adaptive search strategy guiding the search towards high-quality solutions.

The incremental machinery is based on a representation of the model as a directed acyclic graph (DAG), the roots of which are the decisions and the leaves, the constraints and objectives.

Applying moves to the current solution consists of modifying the current values of the decisions (roots) and evaluating constraints and objectives (leaves) by propagating these modifications along the DAG.

Designing a highly optimised propagation algorithm allows evaluating millions of moves per minute on real-life models.

This observation motivated the development of LocalSolver, a mathematical programming solver based on local search.

The Development of LocalSolver

The LocalSolver project began in 2007. Its long-term objectives:

1. Defining a simple, generic declarative formalism suited for LS (model)
2. Developing an effective LS-based solver with fundamental principle: ? doing what an expert would do ? (run)

Started in 2007, the project aims to combine the simplicity of use of a model-and- run solver and the power of local search techniques for combinatorial optimisation. It thus enables OR practitioners to focus on the modelling of the problem using a simple formalism, and leave its actual resolution to a solver based on efficient and reliable local search techniques.

In 2009, the first software LocalSolver 1.0 was available and freely distributed:

• Allows to tackle large-scale generalised 0-1 programs
• Mathematical operators for declaring constraints and objectives (arithmetic, logical, conditional, relational)
• Lexicographic multiple objectives

The main capabilities of LocalSolver is to scale in comparison to classical tree-search solvers (as explained on the complexity graph). Optimisation models with millions 0-1 decisions can be tackled in minutes. Note that only decision variables have to be 0-1; of course, all intermediate variables can be integer (64-bit, even on x86 platforms).

In 2011, LocalSolver 1.1 was released with multithreading, enriched moves and annealing.

The main principles behind LocalSolver:

1. multithreaded adaptive simulated annealing;
2. autonomous moves maintaining feasibility at each iteration (here is the main innovation);
3. highly-optimised incremental evaluation in order to explore millions of solutions per minute of running time.

In 2012, LocalSolver 2.0 was mature enough to move from a research project to a commercial product.

In 2015, the introduction of high level decision variables, inspired from "set variables" introduced in Constraint Programming. This new kind of variables allows building very simple and very effective models for a number of optimisation problems, involve sequencing or ordering concepts, including scheduling, routing, network design problems. The value of such a variable is not a number but a collection of numbers. More precisely, a list variable list(n) represents a sub-permutation of the set {0,1,2, ..., n-1}. Instead of based on numerical decision variables only (binary, integer or continuous).

LocalSolver

LocalSolver is an autonomous local search solver for large-scale optimisation problems. Having modelled our optimisation problem using common mathematical operators, LocalSolver provides us with high-quality solutions in short running times. Combining different optimisation techniques, LocalSolver scales up to millions of variables, running on basic computers.

LocalSolver includes an innovative math modelling and scripting language for fast prototyping called LSP (Local Search Programming) language. LocalSolver’s modelling language is close to that of classical mathematical programming but its use of a larger set of common mathematical operators makes it more intuitive and easy to learn for OR practitioners.

It is a rich yet simple modelling framework. Indeed, most usual mathematical operators are available, including arithmetical expressions (sum, product, trigonometric functions) or logical expressions (comparisons, conditional terms, array indexing).

As a consequence, there is no need to linearise the considered problem: the user can model it directly and naturally. The lightweight object-oriented APIs are also available for full integration (C++, Java, .NET).

Learn more about LocalSolver.

Conclusion

In the end, any problem can be solved using any language/technology, solvers, algorithms, or any kind of combinations. The main point is about the total cost of ownership of the optimisation solutions we develop.

So, we should be lowering our cost by with a solver that:

1. makes the modelling of our problem easier
2. delivers quality feasible solutions really fast
3. scales smoothly to solve the huge problems encountered in industry