Applications in Research andIndustry
Michael RitterMatthias Silbernagl

Technische Universität München
Workshop on Optimization Applications withFICO Xpress 2010

Applications in Research and Industry

Xpress in Mathematics Education
courses complementing mathematicalprogramming classes
hands-on modelling experience
implementation using Mosel
trial and error learning experience
involvement in industry/research projects

Michael Ritter, Matthias Silbernagl

2

Applications in Research and Industry

flight scheduling at airports
increasing air traffic
limited airport capacity
operational constraints
legal restrictions

objective: optimal airport schedule

Michael Ritter, Matthias Silbernagl

3Applications in Research and Industry

flight scheduling at airports
Issue:
limited airport capacity increasing demand
allocation of arrival/departure slots

Michael Ritter, Matthias Silbernagl

4Applications in Research and Industry

flight scheduling at airports
Issue:
limited airport capacity increasing demand
allocation of arrival/departure slots
Constraints:
coupled series
airlines’ demands
hub/feeder flights
arrival / departure
correspondance
legal restrictions
limited ground times
time windows
Michael Ritter, Matthias Silbernagl

4Applications in Research and Industry

time window constraints

bounds on arrivals,
departures, total flights
time windows overlapping
local bounds“globalized” effect

3A
3D

4A
3D

4A
3D
AD

Michael Ritter, Matthias Silbernagl

5Applications in Research and Industry

model characteristics
integer linear program
one season (6 months)≈ 190 000 time windows≈ 200 000 requests
many linked requests≈ 150 000 binary variables≈ 300 000 constraints

Michael Ritter, Matthias Silbernagl

6

Applications in Research and Industry

implementation
Java software embedding Xpress Mosel
data preprocessing
decrease number of variables
SOS-type constraints
guide branching process
fast heuristics
feasible solutions
bound generationspeed up branch & boundMichael Ritter, Matthias Silbernagl

7

Applications in Research and Industry

problems in flight scheduling practicelimited influence on scheduling process
non-optimal scheduling procedures
still implemented
combinatorics of time windows“blocking” in real flight schedules(full, but not maximum)

Michael Ritter, Matthias Silbernagl

8Applications in Research and Industry

problems in flight scheduling practicelimited influence on scheduling process
new question
non-optimal scheduling procedures
Designtime windows such that . . .
still implemented
capacity limits
combinatorics
of aretimerespectedwindows
no “bad” schedule is possible“blocking”
real flight
optimalnumber ofin flights
doesschedules
not change(full, but not maximum)

Michael Ritter, Matthias Silbernagl

8Applications in Research and Industry

optimal time window structure

structural analysis“optimal” blocking strategies IP model
devise strategies to avoid blocking
extensive tests using Java/Mosel software

Michael Ritter, Matthias Silbernagl

9Applications in Research and Industry

results summary
flight scheduling:increase by ≈ 4 000 movements
generally better schedule
time window design:
several strategies devised
extensive tests using Java/Mosel
small trade-off:flights robustness

Michael Ritter, Matthias Silbernagl

10Applications in Research and Industry

traffic infrastructure repair works
bridge repair works
traffic impact
staff/budget/time restrictions
third-party works(e. g. railway tracks)

objective: minimize traffic impact

Michael Ritter, Matthias Silbernagl

11

Applications in Research and Industry

traffic infrastructure repairs works
traffic infrastructure
size, condition repair costcurrent condition repair deadline
third-party infrastructure (railway tracks)
traffic impact: “network effect”
complex interdependencies

Michael Ritter, Matthias Silbernagl

12Applications in Research and Industry

traffic infrastructure repairs works
traffic infrastructure
size, condition repair costcurrent condition repair deadline
third-party infrastructure (railway tracks)
traffic impact: “network effect”
complex interdependencies
objective
minimize traffic impactbalance repair costs
utilize third-party repairs whenever possible
Michael Ritter, Matthias Silbernagl

12Applications in Research and Industry

power loss in semiconductor circuits
energy consumption,
heat dissipation
increased risk of failure
sophisticated cooling devices
mobile devices, medicine,aeronautics

objective: decrease power loss
Michael Ritter, Matthias Silbernagl

13

Applications in Research and Industry

semiconductor circuit

Michael Ritter, Matthias Silbernagl

14

Applications in Research and Industry

semiconductor circuit

Michael Ritter, Matthias Silbernagl

14

Applications in Research and Industry

schematic model
total area

minimum distanceMichael Ritter, Matthias Silbernagl

15

Applications in Research and Industry

schematic model
total area

minimum distanceMichael Ritter, Matthias Silbernagl

15

Applications in Research and Industry

schematic model
total area

minimum distancequestions
optimal distances?

Michael Ritter, Matthias Silbernagl

15

Applications in Research and Industry

schematic model
total area

minimum distancequestions
optimal distances?

Michael Ritter, Matthias Silbernagl

15

Applications in Research and Industry

schematic model
total area

minimum distancequestions
optimal distances?
optimal order?
Michael Ritter, Matthias Silbernagl

15

Applications in Research and Industry

model characteristics
initial approach
nonlinear objective function
continuous and integer variables
hundreds of wires

Michael Ritter, Matthias Silbernagl

16

Applications in Research and Industry

model characteristics
initial approach
nonlinear objective function
continuous and integer variables
hundreds of wires
structural analysis
spacing and ordering two subproblems
spacing analytically solvable

Michael Ritter, Matthias Silbernagl

16

Applications in Research and Industry

model characteristics
initial approach
nonlinear objective function
continuous and integer variables
hundreds of wires
structural analysis
spacing and ordering two subproblems
spacing analytically solvable
ordering turns into special TSP
even TSP efficiently solvable(!)
Michael Ritter, Matthias Silbernagl

16

Applications in Research and Industry

enhanced models
correlation in wire switches(simultaneous switches)more complicated objective(timing, crosstalk, etc.)
deplacement costs
interaction with more than two
neighboring wires

Michael Ritter, Matthias Silbernagl

17

Applications in Research and Industry

enhanced models
correlation in wire switches(simultaneous switches)more complicated objective(timing, crosstalk, etc.)
deplacement costs
interaction with more than two
neighboring wires
significant structural changes
much harder to solve
Michael Ritter, Matthias Silbernagl

17

Applications in Research and Industry

modelling the power market

renewable energy production
grows rapidly
especially production from windunits

Michael Ritter, Matthias Silbernagl

18

Applications in Research and Industry

modelling the power market

renewable energy production
grows rapidly
especially production from windunits
but: production fluctuates heavily

Michael Ritter, Matthias Silbernagl

18

Applications in Research and Industry

power production

cheap units are used for base load
fast but expensive units are used for peak load
Michael Ritter, Matthias Silbernagl

19

Applications in Research and Industry

power production

production of wind units fluctuates heavily
more wind units in the future intensify situation
Michael Ritter, Matthias Silbernagl

20

Applications in Research and Industryproblem
expectation: more fast gas units
neededhow many, at which price?

Michael Ritter, Matthias Silbernagl

21

Applications in Research and Industry

problem
expectation: more fast gas units
neededhow many, at which price?
goal: quantify competitive
advantage of gas units
model the power market

Michael Ritter, Matthias Silbernagl

21

Applications in Research and Industry

model

Grid

Unit Commitment formulation
Michael Ritter, Matthias Silbernagl

22

Applications in Research and Industry

model

Grid

Demand(historical/expected)

Unit Commitment formulation
Michael Ritter, Matthias Silbernagl

22

Applications in Research and Industry

modelWind units(historical/expected)

GridDemand(historical/expected)

Unit Commitment formulation
Michael Ritter, Matthias Silbernagl

22

Applications in Research and Industry

modelWind units(historical/expected)

Units(modelled)

Grid

Demand(historical/expected)

Unit Commitment formulation
Michael Ritter, Matthias Silbernagl

22

Applications in Research and Industry

modelWind units(historical/expected)

Units(modelled)

Grid

Demand(historical/expected)

Neighbor markets(historical/expected)
Unit Commitment formulation
Michael Ritter, Matthias Silbernagl

22

Applications in Research and Industry

implementation
completely in Xpress Mosel

Michael Ritter, Matthias Silbernagl

23

Applications in Research and Industry

implementation
completely in Xpress Mosel
flexible data sources and targets
Oracle database
Excel worksheet → frontend for
non-programmers

Michael Ritter, Matthias Silbernagl

23

Applications in Research and Industry

implementation
completely in Xpress Mosel
flexible data sources and targets
Oracle database
Excel worksheet → frontend for
non-programmers
data preprocessing
real-world parameters → model parameters
substantial reduction of constraints
no customization of Xpress Optimizer needed
Michael Ritter, Matthias Silbernagl

23