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)

What is the objective?

Starting from an origin node, find the minimum distance required to visit
each node once and only once and return to the origin.

Why is it important?

TSP is at core of all vehicle routing problems

Local routing and last mile deliveries are both common and important

What are the challenges?

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

Possible solutions increase exponentially with number of nodes

What are the primary approaches?

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

What is the objective?

Given a network of nodes and arcs, find the minimum cost flow of
product from supply nodes that satisfy demand at destination nodes

Why is it important?

Transportation problems are everywhere (see Banner Chemical)

Transshipment problems are at the heart of larger supply chain network
design models

What are the challenges?

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?

What are the primary approaches?

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)
caplice@mit.edu

ctl.mit.edu