Chapter 11: Applications of Linear Programming October 25, 2020
Applications of Linear Programming
In this chapter we will look at several applications of linear programming. The last application will be sort of a failure, but will lead into the next chapter successfully.
Exercise 27 [2 points] (target due date: Monday, November 9)
In this exercise you will explore using LP to solve a problem that comes up in game
programming. Also, you’ll get to practice performing the simplex method on a number of
LP instances where you can verify the correctness of the results.
Suppose you have two polygonal objects in a 2D game, as follows. The first object has its
center at the point c = ccxy , and has vectors a1, a2, and a3 from c to its three vertices
(the technique works for any number of vertices). Then it turns out that every point in
the first object can be expressed as
c + µ1a1 + µ2a2 + µ3a3;
where µ1 + µ2 + µ3 = 1 and all the µj values are nonnegative (this is a standard convex
combination idea). In addition, let’s say that this object is moving along a straight line
with velocity vector v = vvxy , so that at any time λ (with λ ≥ 0, of course) the center is
at c + λv.
The second object is modeled similarly, with center d, vectors b1, b2, and b3 from its center
to its vertices, numbers νk in place of µj, and velocity w in place of v.
Then we can model the continuous collision detection problem (CCD) by saying that we
want to find the earliest time λ at which a point in the moving first body touches a
point in the moving second body. This problem is important to maintain physical realism
in a game, since it lets us keep objects from overlapping (assuming they aren’t already
overlapping and are moving toward each other).
A cheap alternative to continuous collision detection is to simply let everything move, check for overlaps, and somehow deal with them. This is
common, but doesn’t actually work in the sense that if objects are moving
too fast for the thickness of other objects, they can move past each other in
one time step so they aren’t overlapping. This is called tunneling.”
In mathematical language, we want to find the minimum λ such that
c + λv + X µjaj = d + λw + X νkbk
with P µj = 1, P νk = 1, and all the µj’s and νk’s nonnegative.
It’s important, of course, to realize that the µj and νk quantities are single
numbers, as is λ, while c, d, v, w, and the aj and bk guys are 2D points with
x and y components.
CS 4050 Fall 2020 Page 11.1
Chapter 11: Applications of Linear Programming October 25, 2020
With some thought we realize that this is a linear programming problem, where the decision
variables are λ, the µj’s, and the νk’s, all of which are restricted to be nonnegative, with
four equality constraints. So, one way to do CCD would be to formulate and solve an LP
instance.
Your job on this project is to write a small, somewhat trivial program that will ask the
user to enter c, v, d, and w (as 8 double values|you might want to use cx, cy, etc. to
hold these values), and will then produce an output file that contains data ready to be
input into ManualSimplex to solve the Phase 1 LP corresponding to the CCD problem
(once a feasible choice of basic variables is found in Phase 1, it’s easy to put in the Phase 2
objective function, because it is just minimize λ”), where for simplicity the vertex vectors
aj and bk are fixed.
In your program hard-code the vertex vectors as a1 = -11 , a2 = 2 1 , a3 = -31 ,
b1 = – -1 1 , b2 = 2 0 , b3 = -11 , and b4 = -03 .
We could have these as inputs, but we won’t because it doesn’t add much
conceptually, and hard-coding them keeps things a little simpler.
We want c and d to be input by the user, but for the first 4 problems we will use c = 3 4
and d = 10 9 , giving this picture of what is going on:
•
c+a1
• c+a2
•
c+a3
•
c
….. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . .. . . .. . . .
•
d+b1
• d+b2
•
d+b3
d+b4 • •
d
…. …. …. …. . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . .. . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .. . .. . .. . .. . .. . .. . .. . .. . . . … . .. . . . .. . … . . . … . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . … … … … … … ….
Note that the aj’s and bk’s are shown here as points, but they are actually vectors from c
or d leading to the indicated points.
Be sure that your program generates a tableau with the right-hand side values all nonnegative.
CS 4050 Fall 2020 Page 11.2
Chapter 11: Applications of Linear Programming October 25, 2020
After you have written the little program, test it on the cases given below. For each test
case, use your program to generate a tableau, use ManualSimplex to solve the LP instance,
and interpret the results (the diagrams showing the velocity vectors should be helpful as
you try to picture how the objects are moving). Note that the optimal value of λ tells the
time at which the two objects first touch, and the values of the µj’s and νk’s tell precisely
what points on the two objects are touching at that time.
When you do ManualSimplex on some of these problems a rounding error issue will arise.
It is common when doing row operations to have values that should be exactly 0 be some
tiny number, and those tiny numbers should be treated as 0, and even changed to 0 when
possible (the software won’t let you change the upper right corner value). It is crucial that
you don’t treat a tiny negative value in the objective function row as an indication that
the non-basic variable for that column should become basic.
a. c = 3 4 , v = 2 1 , d = 10 9 , w = – -3 1 :
•a1
•
a2
a3•
•
c
….. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . .. . . .. . . .
• b1
• b2
b3•
b4 • •
d
…. …. …. …. . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . .. . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . … . . . … . . . .. . .. . .. . … . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . … … … … … … ….
……………………… v ……………………………………… . .. . .. . .. . .. . .. . .. . .. . … … … … … .. … … .. . .. . . . .. . . . . . . . . .
… .. .. .. … .. . … . … .. … .. …… .. … … . . … . .. . . . ………………… w ………………………………………………………………………………………
CS 4050 Fall 2020 Page 11.3
Chapter 11: Applications of Linear Programming October 25, 2020
b. c = 3 4 , v = 1 0 , d = 10 9 , w = -01 :
•a1
a2 •
a3•
•
c
….. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . .. . . .. . . .
b1•
• b2
b3•
b4 • •
d
…. …. …. …. . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . .. . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . .. . .. . .. . … . .. . . . … . . . … . .. . .. . . . .. . .. . … . . . … . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . … … … … … … ….
………………………………………… .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ….
v
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
………………………..
w
c. c = 3 4 , v = 3 1 , d = 10 9 , w = 0 0 :
•a1
a2 •
a3•
•
c
….. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . .. . . .. . . .
b1•
• b2
b3•
b4 • •
d
…. …. …. …. . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . .. . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . … . .. . . . .. . … . . . … . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . … … … … … … ….
…………………………………..
| v | …………………. . . . .. . .. . . . … … .. …… .. … .. … . … . .. … .. .. .. …. |
| ……………….. |
………………………………..CS 4050 Fall 2020 Page 11.4
Chapter 11: Applications of Linear Programming October 25, 2020
d. c = 3 4 , v = 0 1 , d = 10 9 , w = -11 :
•a1
a2 •
a3•
•
c
….. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . .. . . .. . . .
b1•
• b2
b3•
b4 • •
d
…. …. …. …. . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . .. . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . .. . .. . .. . .. . … . . . … . . . … . .. . .. . . . … . . . … . . . .. . … . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . … … … … … … ….
………………. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ………………. v
w ……………………………………………………………….
e. c = 7 8 , v = 2 1 , d = 10 9 , w = – -3 1
(note that the first object has been moved from where it was in the first four problems|
you’ll need to sketch it in yourself):
b1•
• b2
b3•
b4 • •
d
…. …. …. …. . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . … . .. . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . … . .. . .. . . . … . . . … . . . … . . . .. . .. . … . . . … . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . … … … … … … ….
Turn in hand-written summaries of these 5 test cases showing your final results. Be sure
to check geometrically that your results are correct.
You do not need to submit your program.
CS 4050 Fall 2020 Page 11.5
Chapter 11: Applications of Linear Programming October 25, 2020
The Transportation Problem
Before using LP to tackle ETSP, let’s look at a problem, known as the transportation
problem, that can be solved by modeling it as an LP. This work is interesting in its own
right, and will provide a sort of warm-up for attacking ETSP.
Suppose we have some factories, each of which produces some number of units of some
product, and some stores, each of which wants to receive some number of units of the
product, where the number of units produced is equal to the number of units desired
(technically we are doing the balanced transportation problem, where the supply equals
the demand).
Factory 3
Factory 2
Factory 1
Store 5
Store 4
Store 3
| Store 2 . . . . . . . . .. .. . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. |
||
| .. . . .. . .. .. . .. … . . … . . . . .. . .. . .. . .. . .. .. .. .. . . .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . | . . . . .. . . | . . . . . . |
| .. …. …. …. . . . . . … …. … . … . . . . . . . | . . . .. . . . | . . . . . . . . . . . . . . . . . . . |
| . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . … .. …. . . .. . . . . . . … . | ||
| . . . . . . . . | . . . . . . . . . . . . . . . . . | |
| . .. . . . .. | . . . . . . . . . . . . . . . . . | |
| . . . . . . . . | . . . . . . . . . . . . . . . . . . . . . . | |
| . . . . . . . |
Store 1
.. … . . . . . . . . . . . . . . . . . . . . .. . . . . . . .. . . . . .. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . .. . . .. . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . .. . . . . . . . .. . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . . . . .. . . .. .. . . . . . .. . .. . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . … .. . . . . . .. . .. . . . . … . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . .. . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. . . . . … . .. . . . . . . .
| .. . … . . . . . . . . . . . . . | . .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . |
| . . . . . … | . . . . . . . . . . . . . . . . . . . . . . . .. .. . .. |
. . . . . . . . … . . . . . . . . . .. . . . . . . . …. . . . . .. . . . . . . .. . .. . . . . . . . … . …. . . . . . . . . . . . . .. . . . . . . . … . .. . . . . … . . . . . . . . . . .. . … . . . …. . . . . . .. . . .. .. . . . . . .. . …. . … . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. . . . . . . . . . .. . . . . . . .. . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . . .. . . . . . . . . .. . . . . .. . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .. . ……………………………………………………………………………………………………………………………………………………………. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . .. . .. . .. . . . . . . . . .. . .. . .. . .. . .. . . . . . .. . .. . .. . .. . .. . .. . . . . … … … … … … .. .. … … … … … … … . .. . .. .. .. ..
Units to ship
10
15
12
Units to receive
8 6
10
7 6
Further, suppose there is a per-unit cost to ship a unit from any factory to any store. The
transportation problem” is to decide how many units to ship from each factory to each
store in order to minimize the total shipping cost.
Because it is too cumbersome to write the unit shipping costs along each edge from a
factory to a store, we typically display all those costs in a 2D chart, where the rows are
the factories and the columns are the stores, along with the number of units to be shipped
by each factory and the number of units to be received at each store:
1 2 3
1 2 3 4 5
10
15
12
8 6 10 7 6
| 3 | 7 | 11 | 4 | 2 |
| 5 | 9 | 4 | 2 | 8 |
| 6 | 1 | 9 | 4 | 7 |
(where the number in row j, column k is the cost of shipping one unit from factory j to
store k)
CS 4050 Fall 2020 Page 11.6
Chapter 11: Applications of Linear Programming October 25, 2020
To model this problem as an LP, we take as the decision variables
xjk = the number of units to be sent from factory j to store k.
Then we can simply write down all the facts of the problem using these variables, and
realize that this problem is actually an LP.
Here is the mathematical form of this LP:
min 3×11 + 7×12 + 11×13 + 4×14 + 2×15+
5×21 + 9×22 + 4×23 + 2×24 + 8×25+
6×31 + 1×32 + 9×33 + 4×34 + 7×35 subject to
x11 + x12 + x13 + x14 + x15 = 10
x21 + x22 + x23 + x24 + x25 = 15
x31 + x32 + x33 + x34 + x35 = 12
x11 + x21 + x31 = 8
x12 + x22 + x32 = 6
x13 + x23 + x33 = 10
x14 + x24 + x34 = 7
x15 + x25 + x35 = 6
x ≥ 0
The first three constraints say that the total units sent from each factory has to add up
to the number of units available at the factory, while the last five constraints say that the
total number of units arriving at each store has to be as desired.
) Let’s finish setting up, solving, and interpreting this sample transportation problem. We
will use the chart below as a compact way to represent an instance of the transportation
problem and check our work.
1 2 3
1 2 3 4 5
10
15
12
8 6 10 7 6
| 3 | 7 | 11 | 4 | 2 |
| 5 | 9 | 4 | 2 | 8 |
| 6 | 1 | 9 | 4 | 7 |
An important point for the modeling is to realize that the eight constraints are redundant,
because the total units produced at the factories equals the total units wanted at the stores,
so if the first seven constraints are satisfied, the eighth one has to be. So, before creating
the data file, we throw out the last constraint.
If we don’t do this, at the end of Phase 1 the last row says a8 = 0, and has no non-zeros
in the non-artificial columns, so it basically says nothing and just clutters up the tableau.
CS 4050 Fall 2020 Page 11.7
Chapter 11: Applications of Linear Programming October 25, 2020
Exercise 28 [10 points] (target due date: Monday, November 9)
Formulate and solve the LP produced by the transportation problem with this data:
1 2 3 4
1 2 3 4 5 6
| 12 | 17 | 13 | 19 | 20 | 15 |
| 10 | 8 | 12 | 14 | 13 | 6 |
| 19 | 15 | 21 | 11 | 14 | 20 |
| 17 | 14 | 17 | 10 | 16 | 18 |
13 12 10 14 15 16
24
18
22
16
Put your optimal point in this chart and check that the objective function value matches
the direct calculation and that the rows and columns add up to the targets.
1 2 3 4
1 2 3 4 5 6
| 12 | 17 | 13 | 19 | 20 | 15 |
| 10 | 8 | 12 | 14 | 13 | 6 |
| 19 | 15 | 21 | 11 | 14 | 20 |
| 17 | 14 | 17 | 10 | 16 | 18 |
13 12 10 14 15 16
24
18
22
16
CS 4050 Fall 2020 Page 11.8
Chapter 11: Applications of Linear Programming October 25, 2020
Solving Network Flow Problems by LP
Network flow problems are important in lots of areas, and many algorithms have been
studied for solving them. We will tackle network flow problems by modeling them as LP
instances. This leads, no doubt|since there are many famous algorithms for network
flow|to an inferior algorithm, but it will provide another example of using LP.
A network flow problem is a directed graph with a source node and a sink node, and a
bunch of other vertices and edges, where each edge has a maximum flow capacity. The
problem is to determine the maximum flow through the graph.
Here is an example, where 1 is the source node|viewed as a source of an arbitrarily large
amount of stuff|and 11 is the sink node|viewed as able to absorb an arbitrarily large
amount of stuff (the stuff might be water, or oil, or electricity, or : : :):
………………………….1………………………….
……………….. . . . . . . . . . . . . . . . . . . . . . .. .. .. ..
………………………….2………………………….
……………………………………………….. ……………………………………………………………………..3………………………………………….. ……………………………………………………………………..4…………………………………………..
…………………………..5………………………….
……………………………………………….
| ……………………. ….. .. .. . .. …… …. |
……………………. ….. .. .. . .. …… |
||
| …………………………………………4 …… | …………………….1 …………………… | ……………………………………………………………………………….. | |
| ….. | ……. | …. ……… |
|
| …. | ……. | ….. | |
| ….. ……. |
…. | ………3………. | |
| …………. ………………. |
………….. | ||
| ….. ……. |
…. | …. | |
| …. ……. |
….. | ….. | |
| ….. ……. |
…. | …. | |
| ………….. . . . .. .. .. .. . . . . . | ……. | ………. . . . | ….. |
| . . . . . . . . . | |||
| ……. | ……… | ||
| ………….. | ……… …. |
||
| ……. | ….. …….. |
||
| ……………………………………………………………. | |||
| ….. . . . .. .. .. . .. . . . . . . . . . |
| ……………………………6…….. …………………………………………………………………………………………………………………………………………………. . . . . . . . . . . . . . . . … |
……………………………9…….. |
| ………………………………….. …. |
………………………………….. . . . . .. . .. . … . .. . . . … … … … … … .. … .. . .. . . . .. . . . . . . . . . |
| …………… | |
| …. |
| ………………………….. . …… . . |
||
| ……. ………………………. |
……………………….. | |
| ……. | ……… | ………….. |
| ……. | …….. . | ………….. |
| ……. | ….. …. | ………….. |
| ……………. 8 ………….. |
||
| ……. | …….. ………….. |
|
| ……. | ……… ………… |
|
| ……. | ……… ………….. |
|
| ……. | ……… ………….. |
|
| ……. | ……… | ………….. |
| ……. | …….. | ………….. |
| …….. …. . …. | ……….. … |
…….
| …………………………… | ……………………… …….. …………… |
|
| …………………….7 10 ………………. …………… …………………………………………………………………………………………………………………………………………………. . . . . . . . . . . . . . . . … |
||
| …….. | …….. | . ….. . . . . . . . |
| …………………………… | …………… . . . . . . . . . . …. | |
| ………. … | ……………… . .. .. . |
|
| …………………. | ……………….. | 3 |
…………………………………8………………………….
………………………………………………. …………………………………. . . . . . . …………………
| …………………. ….. .. .. ….. |
3 |
| . . .. |
11 ……………….
……………….. . . . . . . . . . . . . . . . . . . . . . .. .. .. ..
7 …………… …………………………………………… .. ….. ….. …. … ….. … …. ….. … ….. ….. …… ….. … ….. … … … ….. .. .. … .. .. ……. …… …… … …… . . . . . . . . . . . . . .
……………………………………………………………………………………………………………………………………………………………………………….
2
…………………………………………………1 ……………………………………………………. . . . . . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. ……
…………………………………………………………………………………………………………………………………………………. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. …
2
……..5
………………..
| ……… | ……………………………. |
| ……… |
4…………………..
| ……. | ……… |
| ……. | …. ….. |
……………………………………………………………………………………………………………………..6………………………………………. ………….. ………..
………….
| ………….. | …. |
| ………….. | ….. |
| ………………………. | ….3….. |
| ………….. | ….. |
| ………………………. …….. |
|
| ………….. …. |
|
| ………………………. | ….. |
| …………………………………………….. .. . | …. |
| ….. | |
| …. |
…………………………………………………………………………………………………………………………………………………. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. …
7
8…….. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . …………………………………………………………………………………………..1 ……………………………………………………. . . . . . .. . .. . .. . .. . . . . . . . . . …………………………………………………………………………………………………………………………………………………. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. …
4 …………… .. …. …. …. .. ……. ………………………………………………………………….. . …….. .. . .. .. .. . . …. …. …. …… . . … . . .. . . . … . .. . .. .. . . .. . . .. …. . .. .. .. .. . . . . . . . . . . . . . . . . .
To model this problem as an LP, the crucial idea is to let xjk be the amount of flow from
vertex j to vertex k.
Then the constraints are pretty obvious.
For each edge, say from vertex 1 to vertex 2, we have a constraint
x12 ≤ 7
saying that the flow along that edge can’t exceed the capacity. We can follow our usual
strategy and introduce a nicely named slack variable s12 and have the equality constraint
x12 + s12 = 7:
For each vertex we know that the amount of stuff flowing in must equal the amount of
stuff flowing out. So, for example for vertex 6, we have the constraint
x26 + x36 = x67 + x68 + x6;10;
CS 4050 Fall 2020 Page 11.9
Chapter 11: Applications of Linear Programming October 25, 2020
or, in the required form for a tableau,
x26 + x36 – x67 – x68 – x6;10 = 0:
Since we want to find the maximum flow through the network from the source to the sink,
we can use as the objective function
z = x8;11 + x9;11 + x10;11:
(we could equally well use x12 + x13 + x14)
) Let’s finish this example.
Exercise 29 [2 points] (target due date: Monday, November 9)
Implement the small instance of the maximum network flow problem shown below as an
LP instance and solve it using ManualSimplex. Turn in a graph showing the optimal
amount of flow along each edge.
Assume, obviously, that vertex 1 is the source and vertex 6 is the sink, and that the
numbers written along the edges are the capacities of the edges.
. …………………………………………………………1……………………………………………………………………………………………………………………………………………………………………………………
| ….. | . . ……… |
| ….. |
…………..3……..2………………………………. .. …. … … ….. ….. …… …. ………. … … … … … … … … … .. …. .. … … … … … … … … … … … … … … … … … … … … …2 … … … … … … … … … … … … … … … … … … … … … … … … … …. … … … … … … … … … … … … .. . .. . ……………………………………………………………………………………………………………………………………3……..5…………………………… …. .. .. …. . …. …. …… …… …… . ….. ………. .. . . … …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. ….3 ..5.. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. …. … ………………………………………………………………………………………………………….. ………………………….4……..2…………………………… … .. .. …. . …. …. …… …… …… . ….. ………………………………………………………………..6………………………………………………………………….. .. . .
……………. 4 …………… … .. . … . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . .. ……………………… . … . .. . .. . .. . .. . … …… . . . . . . 1
Try to Model ETSP as an LP and Thus Solve It
Now let’s see if we can model ETSP as an LP and thus solve this allegedly difficult problem.
We have already seen the traveling salesperson problem and noted that the brute force
approach to this problem|simply generating all the permutations of the n vertices and
computing the total weight of each corresponding tour|has time efficiency in Θ((n – 1)!),
and that the dynamic programming-based algorithm for this problem has time efficiency in
Θ(n22n). Since neither of those efficiencies are practical when n is large, we now want to see
if we can solve it by modeling it as an LP. And, since LP can be solved in polynomial time,
as a function of the input size, this would be good, and would beat the other approaches..
There is an algorithm, discovered by Khachiyan and collaborators in 1979,
and a more practical algorithm popularized by Karmarkar in 1984 (actually previously discovered in the 1960’s by other researchers)) that have
CS 4050 Fall 2020 Page 11.10
Chapter 11: Applications of Linear Programming October 25, 2020
polynomial-time worst-case efficiency. In our following discussion, we will
use the simplex method to solve instances of LP, even though it was shown
long ago that in the worst-case the simplex method has exponential running
time|on average it runs in polynomial time.
So, let’s try to write down a linear programming problem that corresponds to a given
ETSP instance. We begin by making the fairly obvious choice that our decision variables
should be xjk, representing the intensity of the connection between vertices j and k, where
xjk = 0 means that there is no edge at all between vertex j and vertex k, and xjk = 1
means that there is an edge between those two vertices. We would like xjk to only have
one or the other of those values, but we will see that this, unfortunately, does not always
happen.
Note that since the edges in our graph are undirected (because the distance from A to B
is the same as the distance from B to A), we only need to use decision variables xjk where
j < k.
Using these xjk decision variables, if we let cjk be the Euclidean distance between vertices
j and k, then the objective function, which we want to minimize, can be taken as
z = X
j<k
cjkxjk:
We like the standard restriction feature of the simplex method, namely that the obvious
restrictions xkj ≥ 0 are automatic. Now we need to design constraints that will somehow
say that the choice of values for these decision variables corresponds to a tour.
We want all xjk to be either 0 or 1, but the closest we can come to saying that in an
LP instance is to say that xjk ≥ 0, which is automatic, and that xjk ≤ 1, which is an
inequality constraint that has to be converted to an equality constraint by adding a slack
variable sjk and changing the constraint to xjk + sjk = 1.
These last constraints are unfortunate, because they double the number of
variables we have. But, they are essential, because otherwise the optimal
solution to the LP can easily have edges with weight 2. This occurs naturally
when all the points are paired up and far away from each other.
The trickier constraints try to say that the choice of intensities form a tour. We note that
in any tour, exactly two of the edges connected to each vertex have intensity 1 and the
others have intensity 0. We can’t say exactly that in an LP, but we can say that all the
intensities of edges connected to each vertex add up to 2.
For example, if we have 6 vertices, then for example for vertex 3, we have the constraint
x13 + x23 + x34 + x35 + x36 = 2:
Let’s try out these ideas in a small LP instance.
CS 4050 Fall 2020 Page 11.11
Chapter 11: Applications of Linear Programming October 25, 2020
Example of an LP Instance that Models ETSP
) Let’s tackle the ETSP instance given by these 6 points:
v1 = (10; 10), v2 = (60; 20), v3 = (10; 20), v4 = (50; 70), v5 = (20; 10), v6 = (40; 40)
Here is a graph of these points (where the grid lines are at multiples of 10):
•
1
•
2
•
3
4•
•
5
6•
……………….. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . …………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………. . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ….
Here are the weights (distances) for this problem, namely the values of ckj (rounded to 2
decimal places):
1 2 3 4 5
2 3 4 5 6
| 50:99 | 10 | 72:11 | 10 | 42:43 |
| 50 | 50:99 | 41:23 | 28:28 | |
| 64:03 | 14:14 | 36:06 | ||
| 67:08 | 31:62 | |||
| 36:06 |
For example,
c25 = p(60 – 20)2 + (20 – 10)2 = p402 + 102 = p1700 = 41:23105625617661 ≈ 41:23:
CS 4050 Fall 2020 Page 11.12
Chapter 11: Applications of Linear Programming October 25, 2020
Now we can write down the LP instance corresponding to this ETSP instance using the
constraints we have figured out:
min c12x12 + c13x13 + c14x14 + c15x15 + c16x16+
c23x23 + c24x24 + c25x25 + c26x26+
c34x34 + c35x35 + c36x36+
c45x45 + c46x46+
c56x56
subject to the constraints
x12 + x13 + x14 + x15 + x16 = 2
x12 + x23 + x24 + x25 + x26 = 2
x13 + x23 + x34 + x35 + x36 = 2
x14 + x24 + x34 + x45 + x46 = 2
x15 + x25 + x35 + x45 + x56 = 2
x16 + x26 + x36 + x46 + x56 = 2
x12 + s12 = 1
x13 + s13 = 1
x14 + s14 = 1
x15 + s15 = 1
x16 + s16 = 1
x23 + s23 = 1
x24 + s24 = 1
x25 + s25 = 1
x26 + s26 = 1
x34 + s34 = 1
x35 + s35 = 1
x36 + s36 = 1
x45 + s45 = 1
x46 + s46 = 1
x56 + s56 = 1
x12; x13; x14; x15; x16; x23; x24; x25; x26; x34; x35; x36; x45; x46; x56;
s12; s13; s14; s15; s16; s23; s24; s25; s26; s34; s35; s36; s45; s46; s56 ≥ 0
CS 4050 Fall 2020 Page 11.13
Chapter 11: Applications of Linear Programming October 25, 2020
Then we create, in the file Code/ManualSimplex/etsp1, the Phase 1 tableau for this
LP instance, recognizing that we need an artificial variable for each of the first kind of
constraints.
The slack variables can serve as initial basic variables for all the xjk +sjk = 2
constraints.
Here is this starting tableau:
z
a1
a2
a3
a4
a5
a6
s12
s13
s14
s15
s16
s23
s24
s25
s26
s34
s35
s36
s45
s46
s56
z x12 x13 x14 x15 x16 x23 x24 x25 x26 x34 x35 x36 x45 x46 x56 s12 s13 s14 s15 s16 s23 s24 s25 s26 s34 s35 s36 s45 s46 s56 a1 a2 a3 a4 a5 a6 rhs
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0
0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 2
0 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 2
0 0 1 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 2
0 0 0 1 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 2
0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 2
0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1
After doing Phase 1 and Phase 2, we obtain the optimal point with z = 145:03, and basic
original decision variables x24 = 1, x46 = 1, x26 = 1, x35 = 1, x13 = 1, x15 = 1, and
x23 = 0 (basic but at 0). We can draw the edges of intensity 1 to see this optimal solution:
•
1
•
2
•
3
4 •
•
5
6•
………………. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . …………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………. …………………………………….. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ………………………… ………………………………………………………….. …………. ………………………………………………………….. ……………………………………………. ………………….. ………………….. ……………………………………………………………………….. ………………….. ………………….. ………………….. ……………………………………………………. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ….
Note that this is the optimal solution to the LP that is trying to model ETSP, but it is
clearly not the optimal solution to ETSP|it is not even valid. Basically it is cheating,
from the perspective of ETSP, getting a lower score than any possible tour, but not being
a tour.
This example motivates us to introduce another kind of constraint.
CS 4050 Fall 2020 Page 11.14
Chapter 11: Applications of Linear Programming October 25, 2020
Cuts
It turns out we can sort of solve the disconnected sub-tours problem by a clever idea,
known as a cut.”
The idea is a generalization of the earlier idea that the sum of all the intensities coming
into a vertex must be 2.
If we consider any non-empty subset S of the set A consisting of all the vertices, then we
know that for any tour the number of edges crossing the boundary between S and A – S
must be at least 2. This is a little hard to describe carefully, but is actually pretty obvious.
So, we can add the corresponding constraint, and change our LP to include this constraint
that forces any feasible point of the LP to satisfy this property.
To apply this idea to our instance, let’s take S = f1; 3; 5g:
•
1
•
2
•
3
4•
•
5
6•
……………….
| . . . . . . . . . . . | …………… |
| . | . . . . . . . . . . . . . . . . …. |
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ………………. the corresponding cut constraint is
x12 + x14 + x16 + x23 + x34 + x36 + x25 + x45 + x56 ≥ 2:
So, our current idea is to start with an LP instance that uses the original constraints
(which are really cut constraints with S = fvjg), along with the xjk ≤ 1 constraints, and
do the simplex method to obtain the optimal tableau. Then, if we observe that we don’t
have a single connected tour, we add an appropriate cut constraint and solve the new LP
instance that has one more constraint.
Note that if we added all such constraints|one for every subset of A|we
would have an LP instance for which the only feasible points were tours. The
problem with this approach, of course, is that there are 2n such subsets, so
we’d be adding 2n constraints, which would make the LP far larger and more
costly to compute than the good old dynamic programming chart. So, in a
heuristic spirit, we are adding just a few constraints from cuts as needed, we
hope, to somehow get an optimal point for the LP which happens to be a
tour.
CS 4050 Fall 2020 Page 11.15
Chapter 11: Applications of Linear Programming October 25, 2020
Continuing the Example
Now we could add the additional cut constraint described above. Adding this constraint
would unfortunately require adding a surplus variable, say just named s1, and another
artificial variable, a7, to be the basic variable for the new row at the start of Phase 1.
But, somewhere around here this whole process becomes too cumbersome to be worth it!
Instead, I took some time and created a Java application HeuristicTSP that takes the
data for the points, constructs the corresponding tableau that tries to model ETSP for
those points, and then automatically does the simplex method to find the optimal point,
graphically displaying the results.
If we make the file Code/ETSP/points1 and run HeuristicTSP on it, we see the solution
we saw before, with two sub-tours.
But, HeuristicTSP also has the ability to add any number of additional cut” constraints.
We simply put in the data file at the bottom the desired cut, namely
cut 1 3 5
The application adds the cut constraints to the tableaux and solves it. If we do this for
points1, we get this optimal point:
•
1
| • 2 |
• 3 . ……………………….. |
•
4
•
5
•
6
……………………………………………………
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . …………………………………………………………………………………………………………………………………………………………………………………………………………………………….. ……………………………………………………………………………………………………………………………………………………………………. ……………………………………………………. . …………………………………………………………………………………………………………………………………………………………………………………………………………………. ……………………………………………………………………………………………………………..
This is in fact the optimal tour|the solution to the ETSP instance. The objective function
value is 179.9, which worse|bigger|than the earlier optimal point for the LP. This makes
sense because without the cut constraint, the LP solution could cheat and have two subtours.
We can prove that this is the optimal point for ETSP, because every tour is a feasible
point for the LP. The problem is that there are lots of feasible points for the LP that
CS 4050 Fall 2020 Page 11.16
Chapter 11: Applications of Linear Programming October 25, 2020
aren’t tours. So, if we stumble across a tour that is the best feasible point for the LP, then
it is of course the best tour.
If we were feeling skeptical we could run DynProgTSP on this instance to see
if it thinks this is the optimal tour.
So, now we are feeling pretty good about the whole business, maybe, but the next little
example will disabuse us of that optimism.
Another ETSP Example to Try
Consider these points (discovered by Randy Sorensen, a student in CS 4050 in 2015):
30 30
70 30
48 50
52 50
30 70
70 70
Here is a picture of these points:
………………. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . …………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………… • •1 5 •3•4 • •2 6 . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ….
These points are in the file Code/ETSP/sorensen. If we run HeuristicTSP on this data,
we get this optimal point for the LP:
•
1
•
2
•
3
•
4
| • 5 . . . . |
• . . . . . |
| . . |
. . |
6
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
………………………………….
……………………
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
………………………………………………………………………………………………………………………………………………………………………………………………………………….
…………………………………
………………………………………………………………………………………………………………………………………………………………………………………………………………….
CS 4050 Fall 2020 Page 11.17
Chapter 11: Applications of Linear Programming October 25, 2020
where the dotted edges all have intensities of 12. The solid edges, as usual, have intensity
1.
This example shows the final and most devastating way in which the LP can cheat|can
find an optimal set of intensities|that is not a tour, despite our best efforts to put in
constraints that force a tour. And, sadly, we have no way to effectively deal with this by
simply adding more constraints.
If we imagine drawing a border around any subset of the vertices, we see that
the total intensity crossing that border is at least 2. If we think of cutting
vertices 5 and 6, for example, we see that they are connected to the other
4 vertices by four edges with intensity 1 2, for a total of 2. If we cut vertices
1, 3, and 5, we see that they are connected to vertices 2, 4, and 6 by three
edges of intensity 1, for a total of 3. The cut with vertices 2 and 5 gives
connection intensities totaling 4.
So, in the next chapter, we will have to learn about the branch and bound algorithm design
technique, which will allow us to make further progress on solving ETSP by using LP as
a tool
CS 4050 Fall 2020 Page 11.18
