Transcript LP-IP Survey - University of Washington

Combinatorial Optimization
in Action
Martin Grötschel
MathAcrossCampus Colloquium
University of Washington
Seattle, January 22, 2009
Martin Grötschel
 Institut für Mathematik, Technische Universität Berlin (TUB)
 DFG-Forschungszentrum “Mathematik für Schlüsseltechnologien” (MATHEON)
 Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)
[email protected]
http://www.zib.de/groetschel
2
Contents
1. Where do I come from?
2. CO in Action: Solving problems from industry
3. What optimization problems can we solve well today?
4. Where are modelling challenges?
5. Where are mathematical challenges?
6. Public Transport
7. Logistics
8. Telecommunication
9. Summary
Martin
Grötschel
3
Contents
1. Where do I come from?
2. CO in Action: Solving problems from industry
3. What optimization problems can we solve well today?
4. Where are modelling challenges?
5. Where are mathematical challenges?
6. Public Transport
7. Logistics
8. Telecommunication
9. Summary
Martin
Grötschel
4
TU Berlin: last week
Martin
Grötschel
5
Konrad-Zuse-Zentrum
Martin
Grötschel
6
Some MATHEON statistics
Financial Funding (in million Euros, 1€ ~ 1.3$)
 DFG
5.7
TU, HU, FU, ZIB, WIAS
3.1
State of Berlin
0.1
Technology Foundation Berlin
0.1
Total budget:
9.0
(plus industry support ,which varies from year to year)
Grant period: 4+4+4 years, subject to successful peer review
Funded Persons
(2+2+2) ~ 40 professors &
7 junior research groups
(3+2+2) ~160 researchers
70
researchers
20
research students
 6 full professors
DFG
Research
Center
Matheon
Persons involved
7
Festival of Mathematics 2006
Martin
Grötschel
 Approximately 1000 participants, Audimax, TU Berlin,
on November 16, 2006
8
The MATHEON Buddy Bear (June 11, 2005)
Workshop
BAG
SPNV
9
existing DFG Research Centers
 rcom
Ocean margins, Bremen (2001)
 CFN
Functional nanostructures, Karlsruhe (2001)
 Rudolf-Virchow-Center
Experimental biomedicine, Würzburg (2001)
 MATHEON
Mathematics for key technologies, Berlin (2002)
 CMPB
Molecular physiology of the brain, Göttingen (2002)
 CRTD
Regenerative therapies, Dresden (2006)
Martin
Grötschel
10
MATHEON research
I
Optimization and discrete mathematics
W. Römisch (HU)
M. Skutella (TU)
G. M. Ziegler (TU)
II Numerical analysis and scientific
computing
R. Kornhuber (FU)
R. Schneider (TU)
H. Yserentant (TU))
III Applied and stochastic analysis
C. Lasser (FU),
A. Mielke (HU, WIAS)
including: scientists in charge
Martin
Grötschel
Mathematical fields
11
MATHEON research
A
Application areas
Life sciences
A. Bockmayr (FU), P. Deuflhard (FU, ZIB), Ch. Schütte (FU)
Martin
Grötschel
B
Logistics, traffic and telecommunication networks
M. Grötschel (TU, ZIB), R. Möhring (TU), M. Skutella (TU)
C
Production
C. Carstensen (HU), D. Hömberg (TU, WIAS), F. Tröltzsch (TU)
D
Circuit Simulation and Opto-Electronic Devices
V. Mehrmann (TU), A. Mielke (HU,WIAS), F. Schmidt (ZIB)
E
Finance
D. Becherer (HU), P. Imkeller (HU)
F
Visualization
K. Polthier (ZIB), J. Sullivan (TU), G. M. Ziegler (TU)
G
Education, Outreach, Administration
J. Kramer (HU)
including: scientists in charge
12
The MATHEON Vision:
Application Area B
 The role of networks
 Networks are omnipresent
 Rapidly growing in size and
importance
 Their design and operation
poses new challenges
 What constitutes a good network?
 Study common mathematical
properties of network
applications
 Develop theory, algorithms,
and software for an advanced
level of network analysis
 Address network planning
problems as a whole
Martin
Grötschel
13
Contents
1. Where do I come from?
2. CO in Action: Solving problems from industry
3. What optimization problems can we solve well today?
4. Where are modelling challenges?
5. Where are mathematical challenges?
6. Public Transport
7. Logistics
8. Telecommunication
9. Summary
Martin
Grötschel
The Problem Solving Cycle in Modern Applied Mathematics
The Real Problem
Hard- Software ware
Data
GUI
Implementation in Practice
Numerical
Solution
Simulation
Modelling
Quick Check:
Heuristics
Simulation
The Application Driven
Approach
Practitioner
Specialist
Education
Mathematical
Model
Optimization
Algorithmic
Implementation
Computer Science
Design
of Good Solution
Algorithms
Mathematical
Theory
Pure Mathematics
15
Beginning with the End, a School Activity:
Combinatorial Optimization in Education
Education Film
Martin
Grötschel
16
No good application
without adequate theory!
Discrete Mathematics
1.
Graph Theory
2.
Matroids and Indepentent
Sets
3.
Min-Max Results
4.
Combinatorial Theory
5.
Polyhedral Combinatorics
Optimization
1.
Linear Programming
2.
Duality
3.
Nonlinear Programming
4.
Nonlinear Nondifferential
Programming
5.
0/1-Programming
6.
Integer Programming
7.
Mixed-Integer Programming
8.
Stochastic Programming
E.ON-Project on gas transport
and gas pipeline capacity planning 9.
Stochastic Nonlinear MixedInteger Programming
since January 2009
1 million Euros/year
8.
Online Optimization
9.
Complexity Theory
10. Understanding Heuristics
Martin
Grötschel
17
Contents
1. Where do I come from?
2. CO in Action: Solving problems from industry
3. What optimization problems can we solve well today?
4. Where are modelling challenges?
5. Where are mathematical challenges?
6. Public Transport
7. Logistics
8. Telecommunication
9. Summary
Martin
Grötschel
18
typical optimization problems
max f ( x ) or min f ( x )
g i ( x )  0, i  1, 2,..., k
h j ( x)  0, j  1, 2,..., m
x  R n (and x  S )
min cT x
min cT x
Ax  a
Ax  a
Bx  b
x0
x j  Z, j  J
Bx  b
x0
( x  R n n)
( x  k n n)
„general“
(nonlinear)
program
NLP
linear
program
LP
program = optimization problem
Martin
Grötschel
( x j  0,1)
(linear)
mixedinteger
program
IP, MIP
20
The Simplex Method for
linear programming
 Dantzig, 1947: primal Simplex Method
 Lemke, 1954; Beale, 1954: dual Simplex Method
 Dantzig, 1953: revised Simplex Method
 ….
 Underlying Idea: Find a vertex of the set of feasible LP
solutions (polyhedron) and move to a better neighbouring
vertex, if possible.
Martin
Grötschel
21
The Simplex Method:
an example
min/max + x1 + 3x2
(1)
(2)
(3)
(4)
(5)
- x2
- x1 - x2
- x1 + x2
+ x1
+ x1 + 2x2
<= 0
<=-1
<= 3
<= 3
<= 9
(4)
(1)
Martin
Grötschel
22
The Simplex Method:
an example
min/max + x1 + 3x2
(1)
(2)
(3)
(4)
(5)
- x2
- x1 - x2
- x1 + x2
+ x1
+ x1 + 2x2
<= 0
<=-1
<= 3
<= 3
<= 9
(4)
(1)
Martin
Grötschel
23
computationally important idea of the
Simplex Method
Let a (m,n)-Matrix A with full row rank m, an m-vector b and
an n-vector c with m<n be given. For every vertex y of the
polyhedron of feasible solutions of the LP,
max cT x
Ax  b
N
A= B
x0
there is a non-singular (m,m)-submatrix B (called basis)
of A representing the vertex y (basic solution) as follows
yB  B1b, yN  0
Martin
Grötschel
Many computational consequences:
Update-formulas, reduced cost calculations,
number of non-zeros of a vertex,…
24
Hirsch Conjecture
If P is a polytope of dimension n with m facets then every
vertex of P can be reached from any other vertex of P on a
path of length at most m-n.
In the example before: m=5, n=2 and m-n=3, conjecture is true.
At present, not even a polynomial bound on the path length is known.
Best upper bound: Kalai, Kleitman (1992): The diameter of the graph of
an n-dimensional polyhedron with m facets is at most m(log n+1).
Lower bound: Holt, Klee (1997): at least m-n (m, n large enough).
Martin
Grötschel
25
The Ellipsoid Method
 Shor, 1970 - 1979
 Yudin & Nemirovskii, 1976
 Khachiyan, 1979
 M. Grötschel, L. Lovász,
A. Schrijver,
Geometric Algorithms and
Combinatorial Optimization
Algorithms and Combinatorics 2,
Springer, 1988
Martin
Grötschel
26
The Ellipsoid Method: an example
Martin
Grötschel
Initialization
Stopping criterion
Feasibility check
Cutting plane
choice
Update
The
Ellipsoid Method
29
Interior-Point Methods: an example
Karmarkar (1984) and
many others afterwards
Often also called
Barrier Methods
central path
(4)
(1)
min
Martin
Grötschel
interior Point
George Dantzig and Bob Bixby, 2000
Linear
Programming
ILOG slides obtained from Bob Bixby
on November 11, 2007
© Copyright 2006 - ILOG, Inc. - All Rights Reserved
30
LP Progress: An Example
A Production Planning Model
401,640 cons. 1,584,000 vars. 9,498,000 nonzeros
Solution time line (2.0 GHz P4):
 1988 (CPLEX 1.0):
 1997 (CPLEX 5.0):
 2003 (CPLEX 9.0):
29.8 days
1.5 hours
59.1 seconds
Speedup
1x
480x
43500x
Solving IN 1988: 82 years (machines 1000x slower)
© Copyright 2006 - ILOG, Inc. - All Rights Reserved
31
LP Progress: 1988-2004
(Operations Research, Jan 2002, pp. 3—15, updated in 2004)
 Algorithms (machine independent):
Primal versus best of Primal/Dual/Barrier
 Machines (workstations PCs):
 NET: Algorithm × Machine
3300x
1600x
5 300 000x
(2 months/5300000 ~= 1 second)
 Bad news: Little change in LP since 2004
© Copyright 2006 - ILOG, Inc. - All Rights Reserved
32
33
Why do I talk about LP?
 Algorithms to solve linear programs are the most
important ingredient of the techniques for solving
combinatorial and integer programming problems.
Martin
Grötschel
34
The Branch&Bound Technique:
An Example
min cT x
min cT x
Ax  a
Ax  a
Bx  b
Bx  b
x0
x0
x  0,1
n
0/1program
Martin
Grötschel
x  0,1
n
x 1
LPrelaxation
 Solve the LP-relaxation and get
optimal solution y. (lower bound)
 If y integral, DONE!
 Otherwise pick fractional
component y(i).
 Create two new subproblems by
adding y(i)=1 and y(i)=0, resp.
LP solution
 ….
y(i)=0
y(k)=1
integral solution
= upper bound
y(i)=1 = lower bound
y(j)=1
35
Branching (in general)
 Current solution is infeasible
Martin
Grötschel
36
Branching (in general)
 Rounding a fractional component up and down
 Decomposition into subproblems removes infeasible
solution
Martin
Grötschel
37
cutting plane technique for integer and
mixed-integer programming
Feasible
integer
solutions
Objective
function
Convex
hull
LP-based
relaxation
Cutting
planes
Martin
Grötschel
Mixed Integer Speedups 1991-2008
George Dantzig and Ralph Gomory
the fathers of
Linear Programming
and
Integer Programming
40
Primal and Dual Heuristics

Primal Heuristic: Finds a (hopefully) good feasible solution.

Dual Heuristic: Finds a bound on the optimum solution value
(e.g., by finding a feasible solution of the LP-dual of an LP-relaxation of a
combinatorial optimization problem).
Minimization:
dual heuristic value ≤ optimum value ≤ primal heuristic value
(In maximization the inequalities are the other way around.)
quality guarantee
Martin
Grötschel
in practice and theory
41
Primal and Dual Heuristics
Primal and Dual Heuristics give rise to worst-case guarantee:
Minimization:
optimum value
≤
≤
dual heuristic value ≤
≤
primal heuristic value
(1+e) optimum value
primal heuristic value
(1+e) dual heuristic value
(In maximization the inequalities are the other way around.)
quality guarantee
Martin
Grötschel
in practice and theory
42
Martin
Grötschel
Linear & Mixed-Integer Programming:
ZIB Software-Suite

SCIP: Constrained Mixed Integer Programming (Verwendung z.B. in
Bereichen Verkehr, Telekommunikation, TU Berlin, TU Darmstadt, TU
Chemnitz, Universität Bayreuth, ..., auch bei CO@Work)

SoPlex- und SCIP-Weiterentwicklung, SCIP-SoPlex-Integration
(Kooperation mit TU Darmstadt; Finanzierung durch Siemens)

ILOG/ZIB-Kooperation zu Forschung in mathematischer Programmierung

Modellierungssprache ZIMPL (mit Anbindung an SCIP)

perPlex: LP-Prüfer mit exakter Arithmetik

Schnittebenenverfahren, MIP-Primalheuristiken

Branch-and-Bound (z. B. Reliability-Branching, Conflict Analysis)

Testbibliotheken MIPLIB, MADLIB, SteinLib, …
43
Martin
Grötschel
A ZIB/MATHEON contribution to
CPLEX
44
General computational results
 linear programming:
excellent
 nonlinear programming:
problem specific
 integer programming:
problem specific
 mixed-integer programming:
very problem specific
 nonlinear mixed-integer programming:
very very problem specific
 Stochastic nonlinear mixed-integer programming:
very very very problem specific
Martin
Grötschel
45
Contents
1. Where do I come from?
2. CO in Action: Solving problems from industry
3. What optimization problems can we solve well today?
4. Where are modelling challenges?
5. Where are mathematical challenges?
6. Public Transport
7. Logistics
8. Telecommunication
9. Summary
Martin
Grötschel
46
The “classical” Transportation Problem
in Mathematical Programming

min
( i , j )S T
cij xij
subject to
x
 ai i  S
S = sources, origins,
supply
x
 b j j  T
T = sinks, destinations,
demand
jT
iS
ij
ij
0  xij ( capij )
Martin
Grötschel
 This problem rarely occurs in real life
in its pure form.
 It does appear as a subproblem of
some much more complex real
problems.
 It can be solved very quickly.
47
Just one example:
Planning Public Transportation
Phase:
Planning
Scheduling
Dispatching
Horizon:
Long Term
Medium term
(very) Short term
Timetable Period
Day of Operation
online planning
Objective:
Service Level
Cost Reduction
Get it done
Steps:
Network Design
Line Planning
Timetabling
Vehicle Scheduling
Duty Scheduling
Duty Rostering
Crew Assignment
Delay Management
Failure Management
politically
difficult
done well
Martin
Grötschel
industry not ready
48
Contents
1. Where do I come from?
2. CO in Action: Solving problems from industry
3. What optimization problems can we solve well today?
4. Where are modelling challenges?
5. Where are mathematical challenges?
6. Public Transport
7. Logistics
8. Telecommunication
9. Summary
Martin
Grötschel
49
New challenges
with each new application
 very, very large-scale linear programs – see integrated
scheduling
 The curse of symmetry – see GSM channel assignment
 Breaking NP-completeness in practice
 Understand new structures – nonlinear constraints in MIP
 Employ new insights from other areas – semi-algebraic
a side step follows
geometry.
 Multi-scales – railroad rolling stock circulation
 Multi-objective optimization – almost everywhere
 Online and real time optimization – ADAC, harbour
Martin
Grötschel
50
Semi-algebraic Geometry
Real-algebraic Geometry
fi ( x), g j ( x), hk ( x) are polynomials in d real variables
dd
S : {x  R : f1 ( x)  0,..., fl ( x)  0}
basic closed
dd
S : {x  R : g1 ( x)  0,..., g m ( x)  0} basic open
dd
S : {x  R : h1 ( x)  0,..., hn ( x)  0}
S : S
Martin
Grötschel
S
S
is a semi-algebraic set
51
Theorem of Bröcker(1991) & Scheiderer(1989)
basic closed case
Every basic closed semi-algebraic set of the form
dd
S  {x  R : f1 ( x)  0,..., fl ( x)  0},
where fi  R[ x1 ,..., xd ],1  i  l , are polynomials,
can be represented by at most
d (d  1) / 2
polynomials, i.e., there exist polynomials
p1 ,..., pd (d 1)/ 2 R[ x1,..., xd ] such that
S  {x  Rd : p1 ( x)  0,..., pd (d 1)/ 2 ( x)  0}.
Martin
Grötschel
52
Our main theorem
Theorem Let
P  Rn be a n-dimensional
polytope given by an inequality representation. Then
2n polynomials
pi R[ x1 ,..., xn ]
can be constructed such that
P  P (p1 ,..., p2n ).
Can this insight be
used algorithmically?
Hartwig Bosse, Martin Grötschel, Martin Henk:
Polynomial inequalities representing polyhedra
Mathematical Programming 103 (2005)35-44
Further results by Averkov&Henk and Bröcker
Martin
Grötschel
53
Contents
1. Where do I come from?
2. CO in Action: Solving problems from industry
3. What optimization problems can we solve well today?
4. Where are modelling challenges?
5. Where are mathematical challenges?
6. Public Transport
7. Logistics
8. Telecommunication
9. Summary
Martin
Grötschel
54
How do graphs look?
Martin
Grötschel
Petersen graph
55
How do graphs look?
Martin
Grötschel
Petersen graph
56
Vehicle Scheduling in Public Transit
large cases:
100 million edges
= # of variables
Martin
Grötschel
57
Duty Scheduling in Public Transit
large cases:
1,000 million edges
= # of variables
Martin
Grötschel
58
Airline Crew Scheduling
large cases:
10 million edges
= # of variables
plus additional
constraints
Martin
Grötschel
59
Planning in Public Transport
Cost Recovery
Fares
Construction Costs
Network Topology
Velocities
Lines
Service Level
Frequencies
Connections
Timetable
Sensitivity
Rotations
Relief Points
Duties
Duty Mix
Rostering
Fairness
Crew Assignment
Disruptions
Operations Control
IS-OPT
Martin
Grötschel
APD
VS-OPT2
DS-OPT VS-OPT BS-OPT
AN-OPT
B15
B1
B3
B1
multidepartmental
Departments
multidepotwise
Depots
multiple line groups
Line Groups
multiple lines
Lines
multiple rotations
Rotations
60
Solution “Technology”
 linear programming
 integer and mixed-integer programming
 nondifferentiable optimization
 lots of heuristics
Martin
Grötschel
61
BVG (Berlin): bus circulation
Martin
Grötschel
62
Vehicle Scheduling:
The "Camel Curve"
68
Martin
Grötschel
Savings in Berlin public transport
64
Integer Programming Model
700 000 deadheads
VSP
1 000 000 duties
DSP
coupling constraints
Martin
Grötschel
28 000 cons
6 000 cons
150 000 cons
65
Solving Very Large LPs
(IVU41 838,500 x 3,570, 10.5 NNEs per column)
450
400
350
300
250
0
20
40
60
80
100
[s]
Martin
Grötschel
Coordinate Ascent
Subgradient
Volume
Bundle+AS
Dual Simplex
Barrier
66
Bundle Method
(Kiwiel [1990], Helmberg [2000])
max f ( )  max


min
c
x vehicleschedule
T
)
x  1Dx 
min
d
T
y duty schedule
y  2Cy
)
 piecewise linear functions
 quadratic subproblem
(dualization reduces dim.)
fˆ
f1
 primal & dual convergence
 approximation
f
2
3
1
 decomposable functions

f ( )  c T x   T (b  Ax  )
Martin
Grötschel
fˆk ( ) : min f ( )
Jk
uk
ˆ
k 1  argmax fk ( ) 
  ˆk
2

2
67
Integrated Scheduling 1983-2007
Article
trips
v
d
Problem
sequential planning
Ball et al. [1983]
1
1 000
--
133
Scott [1985]
1
456
54
--
VSP + duty cost estimate
17
300
--
--
VSP + additional constraints
Falkner & Ryan [1992]
1
182
--
41
DSP + additional constraints
Patrikalakis et al. [1992]
--
111
20
45
DSP + min cost flow
28
257
44
65
ISP without driver releases
Freling [1997]
1
296
38
90
ISP
Friberg & Haase [1997]
1
30
--
--
Freling et al. [2000]
1
476
9
23
ISP
Huisman [2004]
--
653
67
117
ISP
Weider [2007]
7
3 698
209
260
ISP + caps + resource cons
Tosini & Vercellis [1988]
Gaffi & Nonato [1997]
Martin
Grötschel
depots
DSP + SPP to optimality
68
Modelling challenge: two examples
Mathematical layout design of transportation infrastructure
 public transportation systems of cities/regions
 making best use of railway tracks
Martin
Grötschel
69
Origin-Destination Matrix of Potsdam
Martin
Grötschel
70
Determining ticket prices
in public transport
 Ansatz
 „Controlling“ demand via prices and travel times
 Price system = Individual price + ???
 Maximize profit?
 Maximize user utility?
 Electronic Ticketing
 Status
 Data?
 Mathematical models ?
 Giant amount of economic literature on topics of questionable
value for practice (versions of local elasticities)
Martin
Grötschel
71
Planning prices
optimal price
income/profit
demand
price
Martin
Grötschel
Maximize
income
price
73
Fare – Demand – Revenue
Demand/pax
Fare/€
 Demand
Martin
Grötschel
d = d(x)
Revenue/€
Fare/€
 Revenue r(x) = d(x) · p(x)
74
Demand Functions
 Logit vs. constant elasticity
 e(x) := x·d'(x)/d(x)  (d/d)/(x/x)
 Curtin [1968] : e  – 0.3
 Cobb-Douglas-functions d(x) = c·xe with constant elasticity
Martin
Grötschel
75
Example:
Single and Monthly Ticket
(FPP) max
p
iC' stD
s.t.
Martin
Grötschel
i
st
( x)  dsti ( x)
xP

xs = 1.57 € / 1.79 €

xm = 43.72 € / 48.21 €

r(x) = 2,129,971 €
(+3%)

d(x) = 58,601.4
(-12%)

Modal split = 28%
(-4%)
76
Comparing Fare Systems
Status quo
fare system
revenue
demand
cost
single/monthly
2 072 106
66 503.0
3 597 604
single/monthly
1 659 052
30 200.6
1 500 000
standard/reduced
1 428 374
43 942.6
1 500 000
single/monthly
2 053 676
66 723.6
3 553 676
standard/reduced
1 675 575
73 474.5
3 175 575
Max-P*
Max-D*
* = Subsidy 1 500 000 €
Martin
Grötschel
77
Service Planning in Public Transport
Fares
Martin
Grötschel
Demand
Lines
Transfers
Timetable
78
Railway network as a market place
 The railway network manager is obliged by EU and
German law to offer
 as much network capacity as possible
 to all train operation companies (TOCs)
non-discriminatingly
→ The network is a market place, but not a simple one
 Help needed to impove the market design
Martin
Grötschel
79
Our sample network
Martin
Grötschel
80
Results
 Test Network
 45
Tracks
 32
Stations
6
Traintypes
 10
Trainsets
 122 Nodes
 659 Arcs
 3-12 Hours
 96
Station Capacities
 612 Headway Times
Martin
Grötschel
81
The project
Trassenbörse: Railway Slot Auctioning
 The project aims at developing new ideas to make better
(or even best) use of railway tracks.
 A basic assumption, always favoured by economists, is
that "markets" lead to an optimal allocation of goods.
 But what are the goods to be allocated in the "railway
market"?
 And if we can define such goods precisely, how can one
introduce trade mechanisms that lead to fair competition?
 In other words, is there a way to deregulate the current
railway system that results in a "better" utilization of the
railway infrastructure?
Martin
Grötschel
82
Difficulties to be considered
 What is a slot precisely?
 How many details can/should be taken into account?
 What about track profiles?
 What about engine characteristics?
 Routing through stations?
 Weichengenaue Planung (switch scheduling)?
 Buffers and slacks?
 Signals?
 Auctioning process
Martin
Grötschel
83
The project
Trassenbörse: Railway Slot Auctioning
 The collection of question raised calls for a
multidisciplinary approach.
 The project is carried out by a group of economists,
mathematicians, and railway engineers from Berlin and
Hannover, each group bringing its particular expertise.
Martin
Grötschel
84
Rail Track Auction
TOCs decide on bids for slots
BEGIN
Bid is
unchanged
Bid is increased by a
minimum increment
yes
All bids
Unchanged?
no
OPTRA
model is solved with
maximum earnings
no
yes
Wish to increase
bid?
yes
no
END
Martin
Grötschel
Bid assigned?
85
Modelling challenges
 Mathematical models that help making best use of
transportation infrastructure
 Designing auctions for technically difficult infrastructure
use
Martin
Grötschel
86
Contents
1. Where do I come from?
2. CO in Action: Solving problems from industry
3. What optimization problems can we solve well today?
4. Where are modelling challenges?
5. Where are mathematical challenges?
6. Public Transport
7. Logistics
8. Telecommunication
9. Summary
Martin
Grötschel
87
Optimization of Botany Bay
a Container Terminal in Sydney, Australia
Martin
Grötschel
88
Martin
Grötschel
Port Botany –
existing Terminal layout
89
MATHEON Project B14:
Combinatorial Aspects of Logistics

Task:

Practice:
nothing like the logistics problem
(specific aspects in each application)

Wanted:
identify and tackle core models/approaches,
e.g. reoptimization for online problems
Applications:
Martin
Grötschel
online/offline control of logistics systems
vehicle dispatching, elevator control,
automated transportation systems, ...
90
B14: Recent Applications
 Scheduling of laser welding robots in car
body manufacturing (Volkswagen):
 During welding each robot is fed by a laser
source
 Goal: minimize number of required laser
sources
 Control of destination-call elevator
systems (Kollmorgen Steuerungstechnik):
 Passenger specifies destination already
when calling an elevator
 Goal: small average/maximal waiting and
journey times
Martin
Grötschel
91
Contents
1. Where do I come from?
2. CO in Action: Solving problems from industry
3. What optimization problems can we solve well today?
4. Where are modelling challenges?
5. Where are mathematical challenges?
6. Public Transport
7. Logistics
8. Telecommunication
9. Summary
Martin
Grötschel
92
The beginning: Clyde Monma
(Bell Labs/Bell Communications Research)
 Cornell University, 1987
 Survivable telecommunications networks
 What was the problem?
Martin
Grötschel
93
Martin
Grötschel
The
BellCore
study
94
Real data
Martin
Grötschel
95
Problemreductions
Martin
Grötschel
96
Computational results with real data
Martin
Grötschel
97
LATA DL: optimal solutions
Martin
Grötschel
98
Problem
 Nobody at Bell was interested (except for the scientists).
 We were too much ahead of time!
 But then!
Martin
Grötschel
99
But then: USA 1987-1988
(collected by Clyde Monma)
Martin
Grötschel
100
Survivability-Models:
today still a hot topic
mathematical models and software for:
Diversification
„route node-disjoint“
H
B
120
D
H
60
D
F
30
F
30
M
Reservation
„reroute all demands“
M
H
(or p% of all affected demands)
B
H
60
D
(or p% of all demands)
Path restoration
„reroute affected demands“
B
D
60
F
120
F
M
H
M
B
H
60
D
F
60
D
B
60
F
M
plus: simultaneous capacity planning and routing
Martin
Grötschel
B
60
M
101
Mathematical Model
Te
min   k et x et
e E t 1
x et  {0,1} e  E , t  1,
xet 1  xet e  E, t  1,
Te
ye   cet xet
,Te
, Te
 topology decisison
 capacity decisions
 normal operation routing
 component failure routing
e E
t 0
ye 

0
uvD Puv
:eP
duv 
Martin
Grötschel


0
Puv
0
fuv
(P) e  E
0
fuv
(P)
s
fuv
(P)  0
uv  D
s
s  S, uv  Ds ,P  uv
102
Finding feasible solutions?
Heuristics
Manipulation of
 Local search
– Routings
– Topology
– Capacities
 Simulated Annealing
 Genetic algorithms
 ...
Problem Sizes
Martin
Grötschel
Nodes
Edges
Demands
Routing-Paths
15
46
78
> 150 x 10e6
36
107
79
> 500 x 10e9
36
123
123
>
2 x 10e12
103
What can one save?
Real scenario
•
•
•
PhD Thesis:
163 nodes
http://www.zib.de/wessaely
227 edges
[email protected]
561 demands
34% potential savings!
==
> hundred million dollars
Martin
Grötschel
104
Getting more general:
What is the Telecom Problem?
Design excellent technical devices
and a robust network that survives
all kinds of failures and organize
the traffic such that high quality
telecommunication between
very many individual units at
many locations is feasible
at low cost!
Martin
Grötschel
Speech
Data
Video
Etc.
105
What is the Telecom Problem?
Design excellent technical devices
and a robust network that survives
all kinds of failures and organize
the traffic such that high quality
telecommunication between
very many individual units at
many locations is feasible
at low cost!
Martin
Grötschel
This problem is
too general
to be solved in
one step.
Approach in Practice:
 Decompose whenever possible.
 Look at a hierarchy of problems.
 Address the individual problems one by one.
 Recompose to find a good global solution.
106
Connecting Mobiles: What´s up?
BSC
MSC
MSC
BSC
BSC
MSC
MSC
BSC
BSC
MSC
BSC
BTS
Martin
Grötschel
BSC
107
Frequency or Channel Assignment
 The story to be told now is based on
GSM technology
(GSM = Global System for Mobile Communications)
 There are other mobile communication technologies such as UMTS
(UMTS = Universal Mobile Telecommunications System),
a system that is based on CDMA technology
(CDMA = Code Division Multiple Access) where the „story“ is different.
Martin
Grötschel
108
Antennas & Interference
co- & adjacent
channel
interference
cell
antenna
x
x
x
x
site
x
x
x
x
cell
backbone
network
Martin
Grötschel
109
Interference
Level of interference depends on
 distance between transmitters
 geographical position
 power of the signals
 direction in which signals are transmitted
 weather conditions
 assigned frequencies
 co-channel interference
 adjacent-channel interference
Martin
Grötschel
110
Separation
Frequencies assigned to the same
location (site) have to be separated
Site
Blocked channels
Parts of the spectrum forbidden
at some locations:
 government regulations,
 agreements with operators in
neighboring regions,
 requirements military forces, etc.
Martin
Grötschel
111
FAP:
Frequency Assignment Problem
Find an assignment of frequencies to transmitters that
satisfies
 all separation constraints
 all blocked channels requirements
and either
 avoids interference at all
or
 minimizes the (total/maximum) interference level
Martin
Grötschel
112
Minimum Interference
Frequency Assignment Problem (FAP)
FAP is an Integer Linear Program:
min

vwE
s.t.
vf

ad ad
cvw
zvw
vwE ad
co
x
f Fv
Martin
Grötschel
co co
cvw
zvw 
1
v  V
xvf  xwg  1
vw  E d , f  g  d (vw)
co
xvf  xwf  1  zvw
ad
xvf  xwg  1  zvw
co
ad
xvf , zvw
, zvw
 0,1
vw  E co , f  Fv  Fw
vw  E ad , f  g  1
that is very difficult to solve.
113
[%
mi
ni m ]
av um
era de
ge gre
de e
ma
gr
ee
xim
um
de
dia
gr
me
ee
cli ter
qu
en
um
be
r
de
ns
|V
|
Ins
tan
ity
ce
A Glance at some Instances
k
267 56,8 2 151,0
B-0-E-20 1876 13,7 40 257,7
f
2786 4,5 3 135,0
h
4240 5,9 11 249,0
238
779
453
561
E-Plus Project
Martin
Grötschel
3 69
5 81
12 69
10 130
114
Region Berlin - Dresden
2877
carriers
50 channels
Interference
reduction:
83.6%
Martin
Grötschel
115
UMTS Movie
(UMTS auction: the source of MATHEON funds)
Movie
Martin
Grötschel
116
G-WiN Data
G-WiN = Gigabit-Wissenschafts-Netz of the DFN-Verein
Internet access of all German universities
and research institutions
 Locations to be connected:
750
 Data volume in summer 2000:
220 Terabytes/month
 Expected data volume in 2004: 10.000 Terabytes/month
Clustering (to design a hierarchical network):
 10 nodes in Level 1a
261 nodes eligible for
 20 nodes in Level 1b
Level 1
 All other nodes in Level 2
Martin
Grötschel
117
G-WiN Location/Clustering Problem
min   wip xip 
pZ iV
x
ip
1

pZ k K p
wkp z kp
Each location i must be connected to a Level 1 node
p
 di xip 
i
k
z
 p 1
k
k
c
z
 p p
Capacity at p must be large enough
k
Only one configuration at each Location 1 node
k
k
z
 p  const
p
All variables are 0/1.
Martin
Grötschel
# of Level 1a nodes
118
Solution: Hierarchy & Backbone
Martin
Grötschel
119
G-WiN Location Problem:
Solution Statistics
The DFN problem leads to ~100.000 0/1-variables.
Typical computational experience:
Optimal solution via CPLEX in a few seconds!
A very related problem at Telekom Austria has
~300.000 0/1-variables plus some continuous variables
and capacity constraints.
Computational experience (before problem specific fine tuning):
10% gap after 6 h of CPLEX computation,
60% gap after „simplification“
(dropping certain capacities).
Martin
Grötschel
120
X-WIN
 G-WIN served the ~750 scientific institutions from
2000 to 2006.
 G-WIN was reconfigured about every two months to meet
changes in demand. Three modifications were allowed at
each update at most.
 With new transport, hub, and switching technologies new
design possibilities arise. We have designed the new
German science network, called X-WIN which started
operating at the end of 2006 (terabit backbone,
10 gigabit/second connections,…)
Martin
Grötschel
121
Data and a glimpse at the model
initial model:
 1 billion variables
after reduction
 ~100.000 variables
 ~100.000 constraints
solved by ZIMPL/CPLEX
in a few minutes.
 81 scenarios have been
considered and solved –
after lots of trials – for each
choice of reasonable number
of core nodes.
Martin
Grötschel
122
Number of Nodes in the Core Network
Martin
Grötschel
123
Contents
1. Where do I come from?
2. CO in Action: Solving problems from industry
3. What optimization problems can we solve well today?
4. Where are modelling challenges?
5. Where are mathematical challenges?
6. Public Transport
7. Logistics
8. Telecommunication
9. Summary
Martin
Grötschel
124
Mathematical challenges
(examples coming from public transport)
 solving integrated models
 multicommodity flow (vehicle circulation, 100 million variables)
 set partitioning (driver scheduling, 1 billion variables)
combined solution at present hopeles for large instances
 multi-objective integer programs
 minimize number of vehicles
 minimize operation costs
 minimize environmental impact (CO2, energy consumption)
 minimize number of drivers
 minimize driver costs
all at the same time
 nonlinear integer programming
Martin
Grötschel
 pricing
125
Mathematical challenges
 stochastic integer programs
 finding „realistic“ distributions (stochastic models)
 solving stochastic integer programs
 real time/online optimization
 solving rescheduling problems of real instances in real time
 multi-scale integer programming
 example: integrating various time scales and
scales of technical detail
 train scheduling (day-week)
 track assignment in stations (minutes)
 rolling stock maintainance (weeks-months)
Martin
Grötschel
126
Mathematical challenges
 mathematics of regulation/deregulation
 railway track auctioning
 slot management in airports
 energy
A major issue in the new
E.ON gas transport project
 Nobel Prize in Economics
2007
 auctioning
 mechanism design
Martin
Grötschel
127
Summary
 Large improvement potentials in telecommunication with
respect to
 cost
 survivability
 capacity
 congestion
 interference
 ….
 New technologies bring new questions, e.g.,
NGN-networks
Martin
Grötschel
128
Summary
 Large improvement potentials in logistics, (public)
transport with respect to
 cost
 pollution, environmental impact
 service quality
 management support/quality
 quality control
 ….
 Can public transport break even?
 Where are the bottlenecks?
Martin
Grötschel
Book Presentation on
November 11, 2008
Thanks for
Combinatorial Optimization
your
attention
in Action
Martin Grötschel
MathAcrossCampus Colloquium
University of Washington
Seattle, January 22, 2009
Martin Grötschel
 Institut für Mathematik, Technische Universität Berlin (TUB)
 DFG-Forschungszentrum “Mathematik für Schlüsseltechnologien” (MATHEON)
 Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)
[email protected]
http://www.zib.de/groetschel