Set-Based Modeling in LocalSolver 6.0
www.localsolver.com

Who we areBouygues, one of the French largest
corporation, €33 bn in revenues
http://www.bouygues.com

Operations Research subsidiary of Bouygues
20 years of practice and research
http://www.innovation24.fr

Mathematical optimization solvercommercialized by Innovation 24
http://www.localsolver.com

2 22

LocalSolver
Hybrid math optimization solver

LocalSolver=

LS + CP/SAT + LP/MIP + NLP

For combinatorial, numerical,
or mixed-variable optimization
Suited for large-scale
non-convex optimization
Quality solutions in seconds
without tuning
free trial with support – free for academics - renting licenses
from 590 €/month - perpetual licenses from 9,900 €www.localsolver.com

3 22

Motivations
Modeling approaches for

the Traveling Salesman Problem

4 22

Mixed-Integer Programming
With an exponential number of constraints(1) with O(n²) variables and constraints
VariantMinimise ∑cij xiji, ji≠jConventional Formulation (C) (Dantzig, Fulkerson and Johnson (1954))∑ x =1∀ i∈N

SINGLE COMMODITY FLOW (F1) (Gavish and Graves (1978))(2)

Both constraints are retained but we also introduce (continuous) variables:

ij

jj≠i

∑ x =1∀ j∈N

yij = ‘Flow’ in an arc (i,j) i≠j(3)ij

and constraints:ii≠ j∑ x ≤ |M| – 1ij∀ M⊂N such that {1}∉M,|M| ≥ 2

yij ≤ (n - 1)x(4)ij∀ i,j ∈N , i≠ji, j∈Mi≠ j(the symbol ‘ ⊂ ‘ represents proper inclusion) Iterative procedure to add subtour
elimination
constraintsn∑ y = n−1
1jj
j≠1This formulation has 2 + 2n - 2 constraints and n(n - 1) 0-1 variables.

∑ y −∑ y =1ijjkiki≠ ji≠ k∀ j∈N - {1}In Orman & Williams : A survey of different integer programming formulations of the TSP

5 22

LocalSolver 5.0
A compact model based on positions

 A polynomial-size model (not an iterative procedure) No artificial variables and constraints
 But still based on binary decisions

6 22

Natural Modeling
As a permutation

In Kenneth R. Rosen: Permutations and Combinations.

7 22

Reference modelingGarey & Johnson

8 22Set-based modelingInnovative modeling concepts
for routing & scheduling problems

9 22

List Variables
Structured decisional operator list(n)• Order a subset of values in domain {0, …, n-1}
• Each value is unique in the list

Classical operators to interact with “list”
••
•
••
•

count(u): number of values selected in the list
at(u,i) or u[i]: value at index i in the list
indexOf(u,v): index of value v in the list
contains(u,v): equivalent to “indexOf(u,v) != -1”
disjoint(u1, u2, …, uk): true if u1, u2, …, uk are pairwise disjoint
partition(u1, u2, …, uk): true if u1, u2, …, uk induce a partition of {0, …, n-1}

10 22

Traveling salesman
function model() {x <- list(N) ; // order n cities {0, ..., n-1} to visit
constraint count(x) == N; // exactly n cities to visit
minimize sum[i in 1..N-1]( Dist[ x[i-1] ][ x[i] ] )+ Dist[ x[N-1] ][ x[0] ] ; // minimize sum of traveled distances}

Could you imagine simpler model?
• Natural declarative model: straightforward to understand• Common set-oriented concepts: easy to learn• Still easier for people with (basic) programming skills• Compact: linear in the size of input  highly scalable (1 million nodes)

11 22

Why not a single line model ?

12 22

Real–world models do not fit in tight frameworks
Time 𝐴, 𝐵, 𝑇 =2 𝛼𝑥 2 +𝛼𝑦 2−2 𝛼𝑥 𝛽𝑥 +𝛼𝑦 𝛽𝑦 + 4 𝛼𝑥 𝛽𝑥 +𝛼𝑦 𝛽𝑦2−4 𝛼𝑥 2 +𝛼𝑦 2 𝛽𝑥 2 +𝛽𝑦 2 −𝑉²With 𝛼𝑥 , 𝛽𝑥 , 𝛼𝑦 , 𝛽𝑦 function of A,B and T+𝑇?

Kinetic TSP

13 22

Performance ?
TSP: real-life 200-client instance
LocalSolver 5.0 vs 5.5 (with operator list)
1800000

1600000

1400000

1200000

1000000

LS 5.0800000

600000LS 5.5400000

200000Best known solution0
1 2 3 4 5 6 7 8 9 10111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758

14 22

Vehicle routing
function model() {x[1..K] <- list(N) ; // for each truck, order the clients to visit

constraint partition( x[1..K] ); // each client is visited once
distances[k in 1..K] <- sum[i in 1..N-1]( dist( x[k][i-1], x[k][i]) )+ dist( x[k][N-1], x[k][0] ); // traveled distance for each truck
minimize sum[k in 1..K]( distances[k] ); // minimize total traveled distance}

TSPVRP

NormalCount(x)=Npartition(x[1..K])Prize-collecting

maximize sum(…) disjoint(x[1..K])

15 22

CVRP benchmarks
CVRP - instances A•••••

32 to 80 clients, 10 trucks max.
27 instances
5 minutes of running time
LS binary: almost infeasible
LS list: 1 % avg. opt. gap

CVRP - instances X100-500•••••

100 to 500 clients, 138 trucks max.
67 instances
5 minutes of running time
LS binary: almost infeasible
LS list: 9 % avg. opt. gap

16 22

CVRPTW benchmarks
CVRPTW - instances Solomon R100
•
•
•
•
•

101 to 112 clients, 19 trucks max.
13 instances
5 minutes of running time
LS binary: N/A
LS list: 3 % avg. opt. gap

CVRPTW - instances Solomon R200
•
•
•
•
•

201 to 208 clients, 4 trucks max.
8 instances
5 minutes of running time
LS binary: N/A
LS list: 8 % avg. opt. gap

17 22

Beyond routing problems
Scheduling, planning, sequencing

18 22

Flow-shop scheduling
Machine 1
Machine 2
Machine 3

BACBDABECA

DEC

DESince we are looking for a permutation of jobs the model isstraightforward with a single list variable

20 22

Planning
Flights to plane assignments
AECDCB

CA

DB

transferECAB

A solution is a partition of flights into K lists (one per plane)
The goal is to minimize the total transfer times
21 22

Conclusion
List Variables are a first step towards set-based modeling inLocalSolverThis higher level of modeling yields simple and compact models
producing high quality solutions forRouting

Planning

Scheduling
B

AC

DBAC

B

RCPSP

A

E
DCE
DE

Any othersequencing
problem

22 22