Back to 1997

Heuristics were the safe bet

Heuristics are the main tool used to solve optimisation 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 minimises 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 optimisation 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 optimisation 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 organise a boat company that operates a combination of “taxi” and “bus” services for bulk material transportation. This is similar to organising 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 optimisation 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 2020

In 2020 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.