Sc0x w3l2 Clean

Advanced Optimization
ctl.mit.edu
Agenda for Lesson

Network Models
Non-Linear Optimization
Tips on Optimization in Practice
Networks
Network Representation
Network Terminology
Node or vertices a point (facility, DC, plant, region)

Arc or edge link between two nodes (roads, flows, etc.), may be directional
Network or graph a collection of nodes and arcs
1
6
14
3
8
2
4
11
15
12
Arcs
16
10
13
xij = flow on arc from node i to node j

cij = per unit cost for arc i to j
Nodes:
yj = 1 if node j is used, =0 otherwise

fj = cost of opening node j
hj = unit cost for any flow through node j
4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Chicago
St. Louis
Indianapolis
Louisville
Nashville
Cleveland
Columbus
Cincinnati
Lexington
Knoxville
Morgantown
Charleston
Greensboro
Harrisburg
Washington
15 DC
16 Richmond
Richmond
Washington DC
Harrisburg
Greensboro
Charleston
Morgantown
Knoxville
Lexington
Cincinnati
Columbus
Cleveland
Nashville
Louisville
Indianapolis
St. Louis
Chicago
Distance/Connectivity Matrix
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
300 201
362
300
245 263 312
201 245
114
176 112
263 114
175
86
312
175
180
362
142
201 251
332
176
142
105
112
105
95
204
86
95
170
177
180
170
299
201
157
213 209
251
204 177
157
244
318
299
244
205
332
213
120
209
120
318 205
111
111
5
Three Network Problems

Shortest Path Problem
Given: One origin, one destination

Find: Shortest path from single origin to single destination
Traveling Salesman Problem
Given: One origin, many destinations, sequential stops, one vehicle

Find: Shortest tour connecting each stop once and only once and
returning to the origin
Transportation & Transshipment Problems
Given: Multiple supply and demand nodes with fixed and/or variable
costs and capacities on nodes and/or arcs
Find: Minimum cost flow of product from origins to destinations
6
Shortest Path Problem
Shortest Path Problem (SPP)

What is the objective?
Find the shortest path in a network between two nodes
Why is it important?
Result is used as base for other analysis

Connects physical to operational network
What are the challenges?
What route in practice is used? Shortest? Fastest? Un-restricted?

How frequently should we update the network?
Should we use time or distance?
What is the impact of real-time changes due to congestion or weather?
Speed of calculating versus looking up in a table
What are the primary approaches?
Standard Linear Programming (LP) Formulation

Specialized Algorithms (e.g., Network Simplex, Dijkstras)
8
LP Formulation for Shortest Path

Find shortest path from 1 to 5
Min z = 3x12 +4x13 +5x14 +7x25 +2x34 +4x35 + x45
s.t.
5
4
Minimize: cij xij

i
Subject to:
x =1
x - x
x =1
i
ji
ji
ij
xij 0
ij
" j=s
= 0 " j s, j t
x12 + x13 +x14

=1
x12
x25
=0
x13
x34 x35
=0
x14
+x34
x45 = 0
x25
+x35 +x45 = 1
x12, x13, x14, x25, x34, x35, x45 0
Note:
Note that integrality is guaranteed
Other specialized algorithms leverage the
network structure to solve much faster.
" j=t
where:
xij = Number of units flowing from node i to node j
cij = Cost per unit for flow from node i to node j
s = Source node where flow starts
t = terminal node where flow ends
5
4
9
Traveling Salesman Problem
10
Traveling Salesman Problem (TSP)

Starting from an origin node, find the minimum distance required to visit
each node once and only once and return to the origin.
TSP is at core of all vehicle routing problems

Local routing and last mile deliveries are both common and important
It is exceptionally hard to solve exactly, due to its size

Possible solutions increase exponentially with number of nodes
Special algorithms for exact solutions (smaller problems)

Heuristics many available
Nearest Neighbor
Cheapest Insertion
11
Finding TSP using Nearest Neighbor Heuristic

1.
2.
3.
1
Select any node to be the active node

Connect the active node to the closest unconnected
node, make that the new active node
If there are more unconnected nodes go to step 2,
otherwise connect to the origin and end.
6
14
7
11
8
2
4
15
12
9
16
5
10
13
12
Finding TSP using Cheapest Insertion Heuristic

1.
2.
1
Form a sub tour from the convex hull

Add the to the tour the unconnected node
that increases the cost the least, continue until
all nodes are connected.
6
14
7
11
8
2
4
15
12
9
16
5
10
13
13
Transportation & Transshipment

Problems
14
Transportation & Transshipment Problems

Given a network of nodes and arcs, find the minimum cost flow of
product from supply nodes that satisfy demand at destination nodes
Transportation problems are everywhere (see Banner Chemical)

Transshipment problems are at the heart of larger supply chain network
design models
Data requirements can be extensive

Where to draw the line on realism versus practicality
Cost structure: variable and/or fixed on arcs and/or nodes? Concave costs?
Single or multiple commodities? Are products fungible?
Is there any variability of demand, supply or flows considered?
Are there any capacity (min or mx) on arcs or transshipment nodes?
Mixed Integer Linear Programs

Some simulation usually after optimization
15
R1
Network Flow Models
P1
R2
R1
P1
P2
R2
Transshipment Problem
R3
Min
P2
s.t.
Transportation Problem
Min
cij xij
ij
Si
"i S
"j D
xij 0
ij
Dj
cij xij
s.t.
x
x
i
z=
x S "i S
x D "j D
x - x = 0 "j D, S
z=
R3
xij 0
"ij
ij
ij
ij
ji
"ij
Conservation of Flow Constraints

xij
The inbound flow must equal the

outbound flow at transshipment points,
cross-docks, mixing centers, etc.
i xij
xji
i xji
16
Non-Linear Programs (NLP)
17
Non Linear Optimization

Optimal Cut-Out, x* = 0.196 m
Max Volume (x*) = 0.132 m3
0.14
0.12
0.08
0.196
0.06
0.608 m
Box Volume (cubic meters)
0.10
0.04
0.02
1.108 m
0.05
0.10
0.15
0.20
0.25
0.30
0.35
0.40
0.45
0.50
Size of corner cut-out (meters)

18
Example of NLP: Ace Ice Carvers

Ace Ice Carvers creates ice sculptures for parties and
special occasions. The number of sculptures
produced is the product of the two inputs, ice and
labor. Ice can be purchased at $80 per unit and
labor is $20 per hour. A total of $160 is available.
How much labor and how much ice should be

procured in order to maximize the output?
Image CC0 Public Domain from pixabay.com. Problem adapted from Winston (1994)
19
Formulating Ace Ice Carvers
Step 1. Determine Decision Variables

x = Number of units of ice to acquire, 0
y = Number of hours of labor to acquire 0
Step 2. Formulate Objective Function

Maximize = z = xy
Step 3. Formulate Constraints

80x + 20y 160
Max z = xy
80x + 20y 160
x0
y0
Max
z = xi
i
s.t.
cx
i
xi 0
B
"i
where:
xi = Number of units of input i to acquire
ci = Cost per unit of input i
B = Budget for input
20
Feasible
Region
Y units of ice
Ace Ice Carvers
X labor hours
21
Feasible
Region
Y units of ice
Ace Ice Carvers
z= xy = 1
X labor hours
22
Feasible
Region
Y units of ice
Ace Ice Carvers
z= xy = 2
z= xy = 1
X labor hours
23
Feasible
Region
Y units of ice
Ace Ice Carvers
z= xy = 3
z= xy = 2
z= xy = 1
X labor hours
24
Feasible
Region
Y units of ice
Ace Ice Carvers
Things to Note:
Optimal solution is no
longer in a corner!
NLPs require different
solution techniques and
tools
Shape of objective function
and constraints determine
whether solution is local or
global
Convex Min - Global
Concave Max - Global
Optimal NLP Solution

x = 1 labor hour
y = 4 units of ice
Max Production = 4 sculptures
z= xy = 4
z= xy = 3
z= xy = 2
z= xy = 1
X labor hours
25
Practical Tips for Optimization
26
Optimization Models in Practice (1/2)

What are we here for?
Determining what to solve is rarely readily apparent or agreed upon

by all stakeholders.
Establish and document the over-riding objective of a project early on.
Level of Detail & Scope of the Model
Models cannot fully represent reality (caricature vs. portrait)

Models will NEVER consider all factors
Determine problem boundaries and data aggregation levels
Input Data
Collecting data is hardest, least appreciated, and most time

consuming task in an optimization project.
Data are never complete, clean, or totally correct.
Every extra hour spent on data collection, cleaning, and verification
saves days later on in the project.
27
Optimization Models in Practice (2/2)

Sensitivity and Robustness Analysis
These are all deterministic models data assumed perfect & unchanging!
Optimization models will do anything for a dollar, yuan, peso, euro, etc.
Run multiple what-if scenarios changing uncertain input values and
testing different conditions.
Models versus People (Models dont make decisions, People do!)
Optimization models are good at . . .

Making trade-offs between complicated options and
Uncovering unexpected insights and solutions.
People are good at . . .

Considering intangible and non-quantifiable factors,
Identifying underlying patterns, and
Mining previous experience and insights.
Models should be used for Decision Support not for the Decision itself
28
Key Points from Lesson
29
Key Points from Lesson

Network Optimization
Shortest Path Easy & fast to solve (LP or special algorithms)

Traveling Salesman Problem Hard to solve (heuristics)
Flow Problems (Transportation & Transshipment) Widely used (MILPs)
Non-Linear Programs
Harder to solve than LPs lose corner solutions

Shape of objective function and constraints dictate approach and
difficulty
Practical Tips for Optimization in Practice
Know your problem

Know your team
Know your tool
30
Questions, Comments, Suggestions?

Use the Discussion Forum!
Daisy ready to get optimal

(photos courtesy of Lana Scott)
[email protected]
ctl.mit.edu

Sc0x w3l2 Clean

Uploaded by

Copyright:

Available Formats

Sc0x w3l2 Clean

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Sc0x w3l2 Clean

Uploaded by

Copyright:

Available Formats

Advanced Optimization

Agenda for Lesson

Node or vertices a point (facility, DC, plant, region)

xij = flow on arc from node i to node j

yj = 1 if node j is used, =0 otherwise

Three Network Problems

Given: One origin, one destination

Traveling Salesman Problem

Given: One origin, many destinations, sequential stops, one vehicle

Transportation & Transshipment Problems

Shortest Path Problem

Shortest Path Problem (SPP)

Find the shortest path in a network between two nodes

Result is used as base for other analysis

What are the challenges?

What route in practice is used? Shortest? Fastest? Un-restricted?

What are the primary approaches?

Standard Linear Programming (LP) Formulation

LP Formulation for Shortest Path

Min z = 3x12 +4x13 +5x14 +7x25 +2x34 +4x35 + x45

Minimize: cij xij

x12 + x13 +x14

Traveling Salesman Problem

Traveling Salesman Problem (TSP)

TSP is at core of all vehicle routing problems

What are the challenges?

It is exceptionally hard to solve exactly, due to its size

What are the primary approaches?

Special algorithms for exact solutions (smaller problems)

Finding TSP using Nearest Neighbor Heuristic

Select any node to be the active node

Finding TSP using Cheapest Insertion Heuristic

Form a sub tour from the convex hull

Transportation & Transshipment

Transportation & Transshipment Problems

Transportation problems are everywhere (see Banner Chemical)

What are the challenges?

Data requirements can be extensive

What are the primary approaches?

Mixed Integer Linear Programs

Network Flow Models

Conservation of Flow Constraints

The inbound flow must equal the

Non-Linear Programs (NLP)

Non Linear Optimization

Box Volume (cubic meters)

Size of corner cut-out (meters)

Example of NLP: Ace Ice Carvers

How much labor and how much ice should be

Formulating Ace Ice Carvers

Step 1. Determine Decision Variables

Step 2. Formulate Objective Function

Step 3. Formulate Constraints

Ace Ice Carvers

Ace Ice Carvers

Ace Ice Carvers

Ace Ice Carvers

Ace Ice Carvers

Optimal NLP Solution