The history of optimization engines from heuristics, followed by the constraint programming, MIP optimization engine, CP Optimizer, until LocalSolver and how they make the industry efficient.
Back to 1997
Heuristics were the safe bet
Heuristics are the main tool used to solve optimization problems in the industry. Initially, heuristic localsearch algorithms were often used.
Airline crew scheduling: Models, algorithms, and data sets
[…] Gershkoff (1989) presents an SPP that minimizes the cost for the daily pairing problem. Gershkoff introduces a heuristic algorithm in which possible pairings are constructed at each iteration for a subset of the scheduled air legs. The heuristic continues until no further improvement is possible or a stopping criterion such as a time restriction is satisfied. Results are presented for American Airlines.Anbil et al. (1991) use this approach in software for American Airlines called the Trip Reevaluation and Improvement Program (TRIP). They explain the advances that allow the software to solve large problems more quickly. This software was sold to ten other airlines.
Atoosa Kasirzadeha Mohammed Saddouneb François Soumis Les cahiers du GERAD, 2014.
MILP engines didn’t scale
Despite continuous progress since 1950, MILP engines are not able to solve industrial size problems yet. Existing MILP engines are research tools rather than industrial tools.
- 1983 XPress
- 1987 CPLEX
- 1992 IBM OSL
But…
Ed Rothberg (CPLEX) explains there was no robust MILP commercial tool.
In 1998 CPLEX 6.5 is the first CPLEX version able to solve real problems.
"[…] the late 90s were preceded by a period of some thirty years of important theoretical and computational developments, many clearly relevant to MIP computation, but virtually none of which had been implemented in commercial codes. The conclusion was clear. It was time to change that. With CPLEX version 6.5 a systematic program was undertaken to include as many of these ideas as possible. You see the result in the chart. The net effect was that in 1998 there was a fundamental change in our ability to solve real-world MIPs."
Robert E Bixby: A Brief history of linear and mixed integer linear programming, 2012
Research focused on decomposition
In 1997 the Parrot project started
- ILOG
- Carmen Systems
- Lufthansa
- Olympic Airways
The objective of the PARROT project is to provide efficient means to address the highly complex and costly problem of airline crew scheduling […] developing on promising results in the combination of Operations Research (OR) techniques and Constraint Programming (CP).
Decomposition for crew rostering was already a common technique in the literature.
"The three most common solution methodologies are Lagrangian relaxation (Geoffrion (1974), Fisher (1981), Fisher (1985), and Martin (1999)), Benders decomposition (Benders (1962) and Minoux and Vajda (1986)) and branch and price (Desaulniers et al. (1998), Desrosiers et al. (1995), and Barnhart et al. (1996)). Since the 1990s, the most popular approach has been the [set covering problem] with CG embedded in branch and bound (see Desrosiers and Lübbecke (2005), Desrosiers et al. (1995), and Barnhart et al. (1996)). "
Airline crew scheduling: Models, algorithms, and data sets, 2014.
But decompositions require complex algorithms to assist the IP engine:
- Heuristics to generate columns in column generation
- Heuristics to generate cuts in Benders decomposition and branch-cut-and-price
The purpose of the Parrot project was to replace the heuristic with an engine suited to solving non-linear problems, in this case a constraint programming engine.
That approach has been used by ad-opt / GERAD (2003)
CP was a backtracking heuristic
Constraint programming is the “successor” of custom branch-and-bound algorithms from the 80s, with emphasis in generality and constraints that are not linear in a “non-numeric” way.
- Non-linear, numeric: y = x2 + 3
- Non-linear, non-numeric: y = A[x] where A=[1,7,8,9], x in [0 … 3]
I like to describe early Constraint Programming toolkits as “systems that help you write backtracking heuristics”
- Prolog (Colmerauer, 1972) was a programming language that included an backtracking mechanism in its core
- Alice (Laurière) 1976 was a “modern” constraint programming engine where you described your problem with equations and it would find the optimal solution for you
- CHIP (Dincbas 1988) was an early commercial system based on Prolog
- ILOG Solver (Puget 1994) was the first successful commercial system in C++ but was harder to use than a MIP engine
Solving industrial problems in 1997
The available options in 1997 to solve industrial optimization problems were
- Heuristics
- Custom-made branch & bound
- Constraint programming (= backtracking heuristics)
- Decomposition with a MILP engine and some kind of heuristic
In 1997, only very few people had the skillset required to solve complex industrial problems. Only large companies could afford having large research and development teams to develop in-house solutions for their problems.
Back to 2007
MIP engines are much faster
A typical industrial project: The problem consisted in die cutting metallic foils
The problem requires to
- Design the die
- Decide the number of times a die will be pressed
This problem should remind you of the cutting-stock problem. The approach chosen by the original team was
- Column and constraint generation (BCP) for the master MIP
- 20 heuristics to generate columns and MIP model to check column layout
- Exchange heuristic to “polish” the final result
Replaced the solution with
- Column generation using a master MIP
- MIP model to generate columns
What matters in an industrial project
Industrial projects have specific requirements
- Maintenance: MIP speed doubles every 1 1⁄2 year (constant machine). But will a solution that contains custom code benefit much from MIP improvements?
- Knowledge: When a solution needs to be updated in 5 years by a different person, will he master all the techniques used?
- Evolution: When the customer asks for new constraints to be added, will that be possible in an easy way?
Modeling languages are mature
GAMS, AMPL, OPL, Mosel… pick the one you like the most
- They allow people that can’t code to write models
- They prevent people that can code from writing anything else than models and simple decompositions
- Models can be expressed in a short and compact way, most of the time so short you end knowing each line by heart
- They isolate the optimization logic from the rest of the tool and prevent other programmers from altering it
A new engine: CP Optimizer
MIP engines despite their improvements cannot solve all type of problems.
Problems that typically resist them are scheduling problems with “continuous time” that is a very long time horizon, as they require one binary variable per time point.
Constraint programming engines use bound variables instead
Activity : { start : [6…6], end : [12…12] }
Constraint programming engines are not new …
Constraint programming engines are not new … but CPO is a completely different as it introduces new mathematical concepts to model problems:
- Interval variables: model activities
- Function variables: model resources
- State variables: model locations
The engine works like a MIP engine:
- Preprocessing and simplification of the model
- Temporal relaxation solved with an LP
- Deductions done with scheduling algorithms (edge-finding, etc)
- Branching strategies
- Heuristics
CP Optimizer allowed solving robustly a whole family of scheduling problems that aren’t accessible to MIP engines.
CPO in action
The problem was to organize a boat company that operates a combination of “taxi” and “bus” services for bulk material transportation. This is similar to organizing a hub-and-spoke network.
The approach chosen by the original team was:
- Generate a distance matrix using CPLEX (all pair shortest paths)
- Assign tasks to boats with CPLEX
- Assign for each boat the pickup and delivery times of the activities it has been assigned with a greedy algorithm (sort and adjust travel times)
Replaced it with a straight CPO model:
- Generate a distance matrix using CPLEX
- Solve the scheduling and routing problem with CPO
Solving industrial problems in 2007
In 2007 we were able to solve a significantly larger number of industrial problems than before
- Modeling languages make optimization easily accessible people that are not comfortable programming in low-level languages like C++
- The progress in MIP performance makes real problems solvable with simpler methods like straight models and simple decompositions
- New engine CPO complements MIP engine weaknesses and makes complex scheduling problems
Today in 2017
A new engine: LocalSolver
In 2010 LocalSolver started embedding local search into an optimization engine that can be used just like any MIP engine or CPO. All the benefits of local search and heuristics:
- Very large scale problems
- Results obtained very quickly
- Constraints can be violated if necessary
Some of the benefits of MIP engines:
- Lower bounds and optimality proofs
- Without the problems caused by having to write your own heuristic code
LocalSolver model for the traveling salesman problem
function model() {
// A list variable: cities[i] is the index of the ith city in the tour
cities <- list(nbCities);
// All cities must be visited
constraint count(cities) == nbCities;
// Minimise the total distance
obj <- sum(1..nbCities-1, i => distanceWeight[cities[i-1]][cities[i]])
+ distanceWeight[cities[nbCities-1]][cities[0]];
minimize obj;
}
The authors explain their business motivations
“After many years of OR practice, we have learnt important lessons about the needs of users in business and industry […] The “no solution found” answer is not an acceptable answer for end users. Indeed, they already have solutions in operations, even if these solutions may be bad (objectives poorly optimized, important constraints violated). […] Even when a solution violating [some] constraints is unacceptable, seeing it is very useful for the user to detect the cause of the problem, which is almost always an inconsistency in input data.”
Mathematical Programming Solver Based on Local Search, 2014
Local solver had predecessors Localizer in 1999 Comet in 2005
And some applicative packages already used “automatic local search” to solve specific industry problems like ILOG TPO for vehicle routing problems.
But LocalSolver is the first tool to be of practical use in an industrial setting and to be adopted by many users (Airbus, Amadeus, etc).
In 2017 we are in a paradoxical situation: we have a large range of tools we didn’t have before but we don’t seem to be using them to their full extent.