Chapter 10: Transform and Conquer October 13, 2020
The Transform and Conquer Algorithm Design Technique
In this part of the course we will look at some simple examples of another general technique
for designing algorithms, namely “transform and conquer.”
Then we will study in depth one very important (for practical uses) such algorithm, the
simplex method.
The idea of transform and conquer is simple: when faced with a problem, figure out how
to transform it into a different form or different problem, such that a solution to the
transformed problem gives a solution to the original problem.
An Example: the Element Uniqueness Problem
Consider this problem: given n integers a1, a2, . . ., an, determine whether any two of them
are the same.
The obvious algorithm for this problem is to go through all the numbers, in order, and for
each ak, see if it is the same as any of ak+1, . . ., an.
This algorithm has efficiency in Θ(n2).
We can get a more efficient algorithm by applying the transform and conquer idea: first
sort the numbers into, say, increasing order. Then easily go through the sorted list and
determine whether any two are the same. The answer to the question for the sorted list is
the same as the answer for the original list.
This algorithm has efficiency in Θ(n log n), since the pre-sorting takes a number of comparisons in Θ(n log n), and the scan to look for adjacent items that are the same is obviously
in Θ(n), which is negligible compared to the work to pre-sort.
Another Example: the Smallest Difference Problem
Consider this problem: given n real numbers a1, a2, . . ., an, find the pair aj and ak for
which |aj – ak| is the smallest.
⇒ Let’s invent an algorithm for this problem based on the idea of comparing all possible pairs
(aj, ak) and determine the pair that has the smallest difference between its two members.
⇒ Now let’s think of pre-sorting the numbers and using the obvious algorithm. Let’s also
analyze the efficiency category for both algorithms.
CS 4050 Fall 2020 Page 10.1
Chapter 10: Transform and Conquer October 13, 2020
Amazing Example: Instant Insanity
Consider the so-called Instant Insanity puzzle, which consists of these 4 cubes:
……………………………. …………………………….

…………..	…………….	G
….

……………. ………………G
B B R
(W on bottom)
……………………………. …………………………….

…………..	…………….	R
….

……………. ………………B
W W R
(G on bottom)
……………………………. …………………………….

…………..	…………….	R
….

……………. ………………G
R B R
(W on bottom)
……………………………. …………………………….

…………..	…………….	G
….

……………. ………………R
G W W
(B on bottom)
To play along at home, there is a file insanity.pdf in the Documents folder
at the course web site that, if you have a printer, you could print, cut out, and
tape together to get your own set of four cubes. Note that I have designed
the printing so that you can cut along the dotted lines, fold along the borders
between squares, to provide a more robust cube.
If you don’t have a printer, you can just draw the flat arrangements of squares
in the document on paper. Or, if you can find four similar cubes of any sort
in your home, you could somehow mark the colors of the sides to match the
puzzle.
The goal of the puzzle is to arrange the cubes in a row so that each row of four adjacent
squares has each of the four colors appearing in it.
Our purpose for this example is to show how we can transform the puzzle to a different
representation and solve a related problem, leading to solution of the original problem.
If we cleverly decide to represent the information using a graph (like with edges and
vertices, not like a graph of a function), then we have to figure out what the vertices are
and determine the edges. After some deep thought, and lots of playing with the cubes, we
decide that we want a vertex for each color, and that whenever cube j has colors X and
Y on opposite sides we’ll draw an edge, labeled with j, between vertices X and Y .
CS 4050 Fall 2020 Page 10.2
Chapter 10: Transform and Conquer October 13, 2020
When we create the graph like this, we obtain:
R G
B W
1
1
1
3
3
4 3 4
2 4
2
2
Now we solve the following transformed problem: find a tour of the graph that uses an
edge for each of the cubes. One such tour is
R -→ 1 B -→ 3 W -→ 2 G -→ 4 R.
Now, if we arrange the cubes with cube 1 first, with red in front and blue in back, cube
3 with blue in front and white in back, cube 2 with white in front and green in back,
and cube 4 with green in front and red in back, we see that we have solved part of the
puzzle—the front and back rows have all four colors occurring.
Now we note that we can spin each of the cubes however we want, keeping the front and
back fixed, getting whatever other pair of faces we want on the top and bottom rows. To
see exactly how to do this, we go back to the graph and look for another tour, this time
not using any of the edges that we have already used.
We see that the tour
R -→ 2 B -→ 1 W -→ 4 G -→ 3 R
meets these requirements.
If we spin the cubes to make the corresponding faces on the top and bottom—namely put
cube 2 with red on top and blue on the bottom, cube 1 with blue on the top and white
on the bottom, cube 4 with white on the top and green on the bottom, and cube 3 with
green on the top and red on the bottom, then we have fully solved the puzzle.
This example is intended merely to suggest that changing the representation of a problem
can lead to a situation where the solution is more apparent. No one is suggesting that this
is not a very clever approach.
CS 4050 Fall 2020 Page 10.3
Chapter 10: Transform and Conquer October 13, 2020
Another Example: Evaluating a Polynomial
Here is an apparently simple problem that you have been solving for years:
given a polynomial
P(x) = a0 + a1x + a2x2 + · · · + anxn,
compute its value at any desired value of x.
If a typical calculus student were asked to compute, say P(9) for P(x) = 3+7x-4×2+5×3,
they would probably compute 7 times 9, getting 63 and add that to 3, giving 66. Then
they might square 9 to get 81, multiply by 4, and subtract that value from 66, and so on.
To analyze the efficiency of this algorithm, we note that the constant term requires 0
multiplications, the x1 term requires 1, the x2 requires 2, and so on, up to the xn term
requiring n, for a total of 0 + 1 + 2 + · · · + n = n(n + 1)/2 ∈ Θ(n2) multiplications. This
algorithm is also irritating because you need to somehow store the products long enough
to add them up.
If we apply the transform and conquer technique (this is all a little contrived—it’s unlikely
that Horner set out to design his algorithm by thinking “hmmm, can I transform a given
polynomial into an equivalent form that is more efficient to evaluate?”), we might think
to write the previous polynomial as
P(x) = (((5x – 4)x + 7)x + 3.
Then computing, say, P(9) can be done with Θ(n) multiplications and no extra storage,
by just pressing the keys
5 * 9 = – 4 = * 9 = + 7 = * 9 = + 3 =
A Super Famous Example: Solving a System of Linear Equations
Consider the familiar problem of solving a system of linear equations such as
2x + 3y – z = 5
4x + 7y – 5z = 3
-6x + 11y – 4z = 4
You have actually taken an entire math course mostly about solving this problem (MTH
2140 or maybe MTH 3140). The idea, as we hope you recall, at least vaguely, is to first
transform the problem by writing it as a matrix:

2 3 -1 5
4 7 -5 3
-6 11 -4 4

CS 4050 Fall 2020 Page 10.4
Chapter 10: Transform and Conquer October 13, 2020
(with the understanding that the first three columns correspond to the variables x, y, z,
and the last column holds the right-hand side).
Then we perform row operations on the matrix, namely multiplying a row by a non-zero
number, adding a multiple of one row to another, and swapping two rows, until the matrix
is transformed to a form where the solution can easily be obtained.
⇒ To remind ourselves of how to do row operations, let’s solve this system by hand. Or at
least start.
This is the last time we’ll do row operations by hand. For our upcoming
study of the simplex method to solve linear programming problems (LP), we
will use a little program named ManualSimplex—available in the Code folder
at the course web site—to perform the arithmetic of row operations, leaving
us to understand the overall algorithm without going insane.
You may say “but I have other applications that do matrix algebra for me,”
and that may be true, but this program is customized to let you do exactly
what you need to be able to do quite comfortably.
When you run ManualSimplex, you have to provide on the command line
the name of a data file containing the information specifying the augmented
matrix you want to work with.
The required format is:
<number of rows> <number of columns>
<row labels>
<column labels>
<data for the matrix>
⇒ Let’s use ManualSimplex to solve the previous system of linear equations.
We’ll use a trick that is sometimes useful: we’ll leave off the <data for the
matrix> part of the file—the program notices if things are wrong at this
point in the file and reverts to using 0’s, and then we can easily input the
desired numbers (hit ? to see a very brief user’s guide for ManualSimplex).
CS 4050 Fall 2020 Page 10.5
Chapter 10: Transform and Conquer October 13, 2020
The Linear Programming Problem and the Simplex Method
Now we want to study a problem, known as “linear programming,” and one algorithm that
solves this problem, known as the “simplex method.”
A lot of real world problems, from computer science, mathematics, various sciences, engineering, business, and economics, can be formulated as linear programming problems. In
addition to its practical uses, our work in this section will give us an important case study
in computational complexity in the last part of the course, when we study computational
complexity and “P vs. NP.”
Software packages that implement the simplex method have been well-developed for half a
century, and are still in common use. When I taught MTH 3250 in the early 1980’s, the text
we used said that half the computer time being used on the planet was being devoted to
performing the simplex method. Lists of the most important algorithms typically include
the simplex method.
We have mostly been avoiding numerical algorithms, since they are covered in depth in
MTH 4480–4490. Technically the simplex method is a numerical algorithm, subject to
rounding error issues, but if it were executed with perfectly accurate arithmetic computations, it would behave like a non-numerical algorithm. And, it uses simple mathematical
ideas in a profoundly powerful way.
Finally, we will later see how to solve ETSP by using the simplex method as a tool for a
branch and bound algorithm (the last algorithm design technique we will cover).
The Linear Programming Problem (LP)
The linear programming problem, known henceforth as LP, is to find the optimal value of
a function, subject to certain constraints on the arguments, where the function and the
constraints are linear, namely of the form of a sum of terms consisting of a scalar times a
variable, such as 3×1 + 2×2.
An instance of LP has the standard form
max cT x subject to
Ax = b
x ≥ 0
where standard matrix notation is used, n is the number of decision variables, m is the
number of equality constraints, x and c are n by 1 matrices, A is m by n, b is m by 1, and
for any matrix M, M ≥ 0 means that all the components of M are non-negative. We also
assume that b ≥ 0. The only inequality constraints, which are very special and are known
as restrictions, are the x ≥ 0 ones (which means all the components of x are nonnegative).
Later we will see how all sorts of problems that don’t have the standard form can be
transformed to an equivalent problem that fits this form. So, all our theory, and the
algorithm we present for solving an LP, will be based on this form.
CS 4050 Fall 2020 Page 10.6
Chapter 10: Transform and Conquer October 13, 2020
First Example of an LP Suppose a farmer has 1200 acres of farm land to be planted
in either corn or wheat. Suppose further that the farmer has 12000 units of water to be
devoted to these crops, and 18000 monetary units with which to buy seed for the crops.
Each acre of corn requires 8 units of water for the season, and each acre of wheat requires
15. Seed for an acre of corn costs 6 monetary units, while an acre of wheat costs on 30
units per acre. If the expected produce from an acre of corn will sell for 20 monetary units
and an acre of wheat will produce 30 monetary units, how many acres of corn and wheat
should the farmer decide to plant?
To solve this word problem, we begin, like with many such problems, by identifying the
variables whose values we need to determine. In the world of LP, these are known as
decision variables. So, let x be the number of acres of corn to plant, and y be the number
of acres of wheat to plant. With these variables, we easily translate the facts of the problem
into precise mathematical quantities.
max 20x + 30y subject to
x + y ≤ 1200
8x + 15y ≤ 12000
6x + 30y ≤ 18000
x, y ≥ 0
We can graph the boundary lines for the constraints, and some level sets for the objective
function (sets on which all points have the same function value) for this problem:

……. …. ….. ….. …. ….. …. ….. ….. …. ….. …. ….. ….. …. ….. … .. .. .. …… ……. . ……… . ………. …….. .. …….. . . . …. .. .. . . …… .. . …. …… .	……..	…….	.
………. . ..	. …. . .. .. . ….. . …….. …….	…….	…….. ……..
……. . ………. . …….. . . ……. ………… ………. …..	. .. ……. … ……. . .. … … .. .. . …	.
.. … …….	………	..	…….
… . …. .. .. . .. …….	. ……..
.	.	.	.	..	……..	.	……..
……..
……	…….
..	.
……..	……..	………	……
…….	……
.	..
..

……. …	…….	………
… … . . .. .. . …. ….. . . . . ….	.
……..	……..
……..
…….
………	……..	.	………	……..

.. .. . ………. …… . . . . .. . . … ……. . ……..	.. ……. …….	……..	…….	…….
..

…. .. .. . …. …. . . …… .. ……. . ….. …. ….. …. ….. …. ….. ….. ….. ………. … .. .. .. ………. ….. .. …. ….

… .. …. .. …. .. .. ………. … …………… … …… ……….. . .. … …. .. …… …… …. ….. … ……. .. …. ……. .. ……. .. .. …… …….. …. ….. …. ….. ….. …. ….. …. ….. ….. …. ….. …. ….. ….. . … ……..	.. …….. ……..
… ……… .. . .. ….. ……. .. . ….. . .. … .	… ….. …. ….. ….. ……. ……
…….	.	………	……..	…….
…….
.	……..	……	. ……..
.

………….. . … . . .. .. . . … .. .. . . …. .. .. … … …… …. … .. .. ……. ….. ….. .. . .. ….. .

.. .. .. ….. ……….. …. ……. . .. ……..	.	..	..
…. … ……… … …. .. .. .. . . .. … . . …. …….. .. ……………….. ……. .. …..	……………………..
………. . ……… …. …….. ……..	……………………………………………………………………………………………… ……. ……. …… …….
. ……..	.. ……… ……. ……..

…… . ……… . …….. .. . …….. ……… ….. …. ….. …. .

… …. ……… …. ….. ..	………	…….	……..
……………………………………………..	…….	. ……..	…….
.	.	…….
……
..

. …….. ..	….
……………………………………………………………………………………………………………………… ………	……..	……..	. .	……..
…….

………………………

…….

………

……..

.
.
……..
……..
……..
……..
………
……..
……..

……..
………	……..

……..
.
……………………
.
……………..
………

……..

……..

………

……..
……..
……..

………

……..

……..
……..
……..

……..

……..

………

……..
……..
.
………
………
……..
0 .
5
10
15
20
0 5 10 15 20 25 30
(in units of 100)
CS 4050 Fall 2020 Page 10.7
Chapter 10: Transform and Conquer October 13, 2020
⇒ We can solve this instance of LP by finding the feasible region—the region consisting of
points (x, y) that satisfy all the constraints—and then finding the level set which crosses
the feasible set and has the largest objective function value. We can do this graphically,
or by solving pairs of linear equations to find candidates for the winning point.
Actually this problem is not an instance of LP, because it has inequality constraints. Later
we will learn how to convert inequality constraints into equality constraints.
Some Theory of LP and the Brute Force Approach
Consider an instance of LP, where the coefficient matrix A is m rows by n columns. To
avoid bogging down in a lot of math, no matter how much fun that might be, we will
simply state the crucial theoretical facts that we need to know in order to understand our
two approaches to solving LP (brute force and the simplex method).
Big Fact: an optimal point can be obtained by selecting m of the n variables to be allowed
to be positive, while holding the other n – m variables at 0.
The m variables that are allowed to be positive are known as basic variables,
and the other n – m are known, in a stroke of creative nomenclature, as
non-basic variables.
It is possible that there are no points that satisfy both the constraints (Ax =
b) and the restrictions (x ≥ 0). Such an instance of LP is said to be infeasible.
The set of points that satisfies both Ax = b and x ≥ 0 is known as the feasible
set.
The rest of what we need to know is based on a standard principle of matrix algebra: if
we partition a matrix computation in any way that makes sense, then any fact that would
be true if the blocks of matrices were numbers is still true.
Using this principle, let’s partition x into m basic variables and n-m non-basic variables,
and purely for notational convenience pretend that the variables have been rearranged so
that the basic variables come first, followed by the non-basics. Then we can partition
x = xxNB . We will similarly rearrange the columns of A, denoting the first m columns
of A by B, and the remaining n – m columns by N, so we have partitioned A = [B N].
And, we rearrange the components of c so that c = ccNB .
We also want to express the objective function in the same form as the constraints. To do
this, we introduce a new variable z, and define z = cT x. To put this in the same form as
the constraints, we need a constant on the right-hand side, so we subtract cT x from both
sides, obtaining z – cT x = 0.
With all this notation, our LP becomes:
CS 4050 Fall 2020 Page 10.8
Chapter 10: Transform and Conquer October 13, 2020
xB
z 1
B N b
-cT
B -cT N 0
xT
B xT N
0 0… 0
z
Note that the top row in this tableau consists of variable names, for convenience, showing
us which column corresponds to which variables. Similarly, the leftmost column consists
of the names, it will turn out, of the current basic variables.
The column for the z variable never changes (and in fact z doesn’t appear in any equation
except the objective function one), and is only there to remind us of what the objection
function row means, namely
1z – cT Bxb – cT NxN = 0.
Now we are ready to do some block row operations. We first multiply the “second row” of
the partitioned matrix by B-1 (which of course only works if this matrix is non-singular),
obtaining the equivalent set of equations
xB
z 1
I B-1N B-1b
-cT
B -cT N 0
xT
B xT N
0 0 … 0
z
(noting that B-1 times the first block, which is a column of all 0’s, gives a column of all
0’s)
CS 4050 Fall 2020 Page 10.9
Chapter 10: Transform and Conquer October 13, 2020
Then we add the correct multiple, namely cT B, of “row 2” to “row 1” to zero out “row 2”
in “column 1,” obtaining the tableau
xB
z 1
I B-1N B-1b
0T cT BB-1N – cT N cT B B-1b
xT
B xT N
0 0 … 0
z
Now, the “second row” says that
IxB + B-1N xn = B-1b,
so if we set xN = 0, these equations say that xB = B-1b.
The “first row” says that
z + 0T xB + (cT BB-1N – cT N)xN = cT BB-1b,
or, using xN = 0, that
z = cT
BB-1b.
Thus, the first row of the rightmost column of the tableau gives the value of the objective
function corresponding to the current choice of basic variables, and the elements below
that in the rightmost column give the values of the basic variables.
Note that all the steps being described algebraically will actually be performed in ManualSimplex by moving the cursor around and hitting p to
produce the identity matrix in the first m columns. Of course, in reality
those “identity columns” will be sprinkled through the matrix, not all neatly
sitting in the first m columns.
CS 4050 Fall 2020 Page 10.10
Chapter 10: Transform and Conquer October 13, 2020
One Great Example of Lots of Things
We will take a very pragmatic approach to learning the simplex method and just explain
everything through the following example of pretty much everything, with embedded general discussion.
This material should be enough to enable you to succesffully complete the upcoming Exercises and Test questions, and later to understand how we use LP as a tool to solve the
Euclidean traveling salesperson problem.
Consider this original problem:
max 3×1 + 5×2 subject to
3×1 + 4×2 ≤ 60
2×1 + 5×2 ≤ 50
-x1 + 3×2 ≤ 15
x1 + 4×2 ≥ 12
x ≥ 0
Because there are only two decision variables, we can picture this problem, where the
arrows on the lines show which half-plane satisfies the corresponding inequality:

……………. ………………………… ……………………	. . … . . . … .. . …… .. .. .. .. .. .. . .. … ….. .. . . . …….. .. ………………….. … . . . . . . . . … . ………………..	…….. . .. . .. …. . .	…….	………………………………..
………………. .. . .. . .. . . .. .. . . .3 . ……. …. .. . . . . . . . . . . . . . . . . . . . . …. …. . . . .. . .. . … . ……………………….. . …. . . . . . . . . …. . ………… ….	.. .. . ……….. … . … . . . . . … . … ……….. . . . . . . ……….. … . . .. . . . . . … . . .. .. ……… .. .. ……. .. .. . . . … .. .. .. . .. . … .. . ……. …. . …. .. ….
………………. .. . .. . . . .. . . .. . . .. . .. . .. 2 … ……… …. .. .. . … .. .. . . . .. .. … … . … . . .	… . . . … ……. …. . . . . .. . .. . . . . .. .. .. .. .. . . . . . . . .. . .. … . . . ….. . ….. . . … . . . . . . . . . . . . . . . . . . …. . . . . . . ..	…………………………………………………………………………………………………………………………………………………..
…. . . …. ……. ….. . . . .. . .. . . . . .. ..	…….	……..	…….
. . .. . … ……….. . . .. . . ……….. … . . .. . . . . . . .. . ………….. . . .. .. .. .. ………………… .. .. .. .. .. .. .. . . . . .. . .. . . . … .. ……. …………… …… .. .. .. …… ………………. .. .. .. .. . . .. .. . . . . . .. . .. .. . .. .. . ……….. .. … … … ….. .. . .. … .. ….. …. .. .. .. . …. .. …. . .. .. .. ….. .. . . . .. .. .. .. .. .. .. .. … .. . .. ….. . .. .. .. …. . …… .. … .. .. …. …. . .. .. …. .. … .. ……. . . .. .. ….. … . . .. .. .. .. .. . .. …… . ……………. . . . . . . . … . . . … .. .. … . . . .. … . . .. . …….	……. …….	……. …….	…….
. . .. .. . . . .	…….. ……..	…….. …….. ……..	…….	…….
.. . .. . . . …. . . ………. . . . … . . . . . .. . .	…….
. . … … . .	………………
. . . . .. . . . .	……………….
. . . . ……….. … . . .. . . .. . … . …… . .. .. …… ….. .. …. ……. …. .. ……. .. .. .. ……. .. . ….. . .. .. …. .. .. . ….. …. . . …. ..
……… .. …. ……. …. …………. .	……. …….	……. …….	……..
…………………………………………………………….	…….
………………………………………………………………………
…………………………………………………..
…….	…….	…….	…….
.. .. . .. . .. . .. . .. . .. . .. . .. …..	…….	…….
.
…….	……..	…….
…….	…….	.	…….
…….
…….	…….
…….	…..
…….	…….
…….	…….	…….
……. …….	……. …. …… … . … ….. .. .. .. … . ………….
……. … .. … .. … ……………..	…….	…….
……. ….. ……. ….. .. .. …. .. …….	…….	…….
.
……..
…….
…….
…….
…….	……	…………
…….
…….
…….
……..
…….
……. ……… …………. .

…….. …… . …… . . .. . … . .. .. …. . …1. . . ….. . …. … … .. .. .. .	…….
……. . .. … ..	. ……..	…….. …….
……………………. .. .. .. .. .. .. .. .. .. …..	.
…….. ……..	……..	……. …….	……..	……..	…….	…….
…….

. . . .. . . ..

. ………..4…………….. …. .. . .	……. ………………………… …………………………. ……………………… . ….. … … . . . .	. .. … .. . . .. …. .. . .	……. …. … . . . . . . .. . … . …..	…….
…. ……………………….. …………………………. …….
…………………… ……………… …………..	…………….
… . . …. .	…………….
…… ….. . . . … .. . . …. .. .. .. …. .. .. … . . . … . . . ……………… .. . .. . .. . …. ……………………… … .. . . . . . … …. ……	…………	…….	…….	……

.. .. ……….. . . . .. .. …..x…….1……….. . .
……..
…………..
x2
………
……………
….. ………………….. …. .. . . . .
0 5 10 15 20 25 30
5
10
15
20
………………………..

…….	……..	…….	…….	……..	…….
…….. ……..	…….
…….

……..
…….
…….
……..
.
…….
…….
.
…….
…….
.
…….
. .. .. ….. ………. ……………………. .. ………… .. ……………. ………… .. ………….. .. ……………………… .. ………… .. ………….. .. ……………. ………… .. ………….. .. ………… .. ………………………………………. zz = 100 = 90
………………………………………………………………………………………………….. z = 110
CS 4050 Fall 2020 Page 10.11
Chapter 10: Transform and Conquer October 13, 2020
This problem is not an instance of LP, because it has inequality constraints (other than the
restrictions). But, the fact that LP maintains nonnegativeness of all the variables allows
us to convert this problem to an instance of LP by introducing a new variable, say s1 (“s”
for “slack”) that is the amount by which 3×1 + 4×2 is less than 60. So, we convert the first
equation to 3×1 + 4×2 + s1 = 60, which is in the desired form for LP.
Formally, we note that
3×1 + 4×2 + s1 = 60 and s1 ≥ 0
if and only if
3×1 + 4×2 ≤ 60.
We can convert the next two inequalities to equalities in the same way. For the last
inequality we similarly add a new variable s4 (“s” for “surplus,” somewhat unfortunately)
and note that
x1 + 4×2 ≥ 12
if and only if
x1 + 4×2 – s4 = 12 and s4 ≥ 0.
Another little technique is to introduce a new variable z that is intended to be the value
of the objective function. To do this, we add the equation
z = 3×1 + 5×2,
but in order to make this look like the other constraints, we write it in the obviously
equivalent form
z – 3×1 – 5×2 = 0.
In the figure we have drawn three sample lines showing the set of all points
(x1, x2) such that z = 90, 100, and 110. There is such a line for each possible
value of z. We can visually solve the LP by imagining which of these parallel
lines hits a point in the feasible set with z as large as possible.
These techniques give us this instance of LP:
max z subject to
z – 3×1 – 5×2 = 0
3×1 + 4×2 + s1 = 60
2×1 + 5×2 + s2 = 50
-x1 + 3×2 + s3 = 15
x1 + 4×2 – s4 = 12
x ≥ 0
s ≥ 0
CS 4050 Fall 2020 Page 10.12
Chapter 10: Transform and Conquer October 13, 2020
Note that really, to fit our definition of LP, we should have named s1 as x3, s2 as x4,
and so on. We don’t, because it is helpful to understand that the xj variables are original
“decision variables,” while the sk variables are slack or surplus variables added to the
original problem to convert it to an LP.
This example, though allegedly great, is somewhat misleading, because after
this example we will never try to visualize what is going on again! The
picture is merely intended to help us believe the theoretical claims we are
making.
Repeat of the Important Theoretical Fact
As mentioned earlier, it turns out that if we have an LP with A having m rows and n
columns, then the optimal value can always be obtained by selecting the correct set of m
variables to be basic, setting the other n – m variables (known, perhaps not surprisingly,
as “non-basic variables) to 0, and solving the system of equations by pivoting on the basic
variable columns and noting that the values of the basic variables show up in the right-hand
side.
Interpreting What the Tableau Says
“Tableau” is the fancy name for the matrix we’re doing row operations on, together with
its row and column labels.
Consider this tableau for the “great” example, which can occur by doing suitable pivot
steps:
z
x2
s2
s1
s4
z x1 x2 s1 s2 s3 s4 rhs
1 -4.67 0 0 0 1.67 0 25
0 -0.33 1 0 0 0.33 0 5
0 3.67 0 0 1 -1.67 0 25
0 4.33 0 1 0 -1.33 0 40
0 -2.33 0 0 0 1.33 1 8
Here z is special and appears where it always does, as the basic variable for the first row,
which is known as the “objective function row.”
The basic variables are x2, s2, s1, and s4, so the non-basic variables are x1 and s3. Thus,
to understand what each row is saying, we need to remember that x1 = 0 and s3 = 0.
Then the first row—the so-called objective function row—says
z – 4.67×1 + 1.67s3 = 25,
but since x1 and s3 are 0, this row really just says z = 25. Thus, the current value of the
objective function—z—is always written in the upper-right corner of the tableau.
CS 4050 Fall 2020 Page 10.13
Chapter 10: Transform and Conquer October 13, 2020
The second row, which has x2 as its basic variable, similarly says that
-0.33×1 + x2 + 0.33s3 = 5,
or x2 = 5, since x1 and s3 are non-basic.
We can similarly interpret the other rows as saying that s2 = 25, s1 = 40, and s4 = 8.
Thus, the right-hand side gives the current values of all the basic variables.
The Brute Force Method
Now let’s solve this LP by using ManualSimplex and the previous observations.
Here (again, but this time more carefully) is the format for the data file to be fed to
ManualSimplex, where M is the number of rows (including the objective function row
and the m constraints) and N is the number of columns (including one for z, one for the
right-hand side, and one for each of the n variables):
M N
<column of M basic variables, one for each row)>
<column of N column labels (starting with z, ending with rhs)>
<M by N rectangular arrangement of all the coefficients>
The main tool provided by ManualSimplex is to be able to hit p to pivot on any row and
column—this simply does row operations to produce a 1 in the cursor row and column,
and zeros everywhere else in the cursor column.
You can hit arrow keys to move the cursor around. You can see all the
operations you can perform by hitting ?, and then hitting esc to go back to
normal operation.
By pivoting in various places, we can go through all possible choices of basic variables
(there are 6 variables—ignoring z which is special—giving us the 6 4 = 15 possibilities
listed in the chart below). For each choice of basic variables, we can also note the two
non-basic variables, and realizing that the point must lie on the line corresponding to a
variable, we can verify from the earlier graph of the feasible set in x1, x2 space where the
intersection lies, and whether it is feasible.
For example, with s3 and s4 non-basic, we see that the intersection of lines 3 and 4 will
happen with negative x1. Note that there are 6 lines, leading to 6 2 = 15 intersection
points of two of these lines, corresponding to the 15 extreme points.
Note that there are 6 points that are the intersection of 2 lines ending up with x1 and x2
nonnegative.
Note that this is the last time we will bother to try to match the picture in decision variable
space to the algebra.
CS 4050 Fall 2020 Page 10.14
Chapter 10: Transform and Conquer October 13, 2020
Basic Variables Feasible? z (if feasible)
x1, x2, s1, s2 no
x1, x2, s1, s3 no
x1, x2, s1, s4 yes 56.818
x1, x2, s2, s3 no
x1, x2, s2, s4 no
x1, x2, s3, s4 yes 64.286
x1, s1, s2, s3 yes 36
x1, s1, s2, s4 no
x1, s1, s3, s4 no
x1, s2, s3, s4 yes 60
x2, s1, s2, s3 yes 15
x2, s1, s2, s4 yes 25
x2, s2, s3, s4 no
s1, s2, s3, s4 no
Now we can finish the brute force approach to LP: obviously the optimal point is with s1
and s2 non-basic, leading to x1 = 14.286, x2 = 4.286, s3 = 16.4286, and s4 = 19.4286.
We should also observe that this same approach finds the minimum value of the objective
function over the feasible set, namely 15.
⇒ Let’s do everything necessary to put the instance into a data file and use ManualSimplex
to perform the brute force method for solving LP.
CS 4050 Fall 2020 Page 10.15
Chapter 10: Transform and Conquer October 13, 2020
Exercise 25 [10 points] (target due date: Monday, October 26)
Demonstrate the brute force method, using the ManualSimplex application, on this LP
(you will need to use a text editor to make a suitable input file for this problem, which is
already in the required format for LP):
max x1 + 2×2 + 3×3 + 3×4 + 2×5 + x6 subject to
4×1 + 8×2 + 3×3 + 6×4 + 10×5 – x6 = 120
8×1 – 4×2 – 6×3 – 8×4 + x5 + 3×6 = 24
12×1 + 5×2 – 9×3 + 6×4 – 9×5 + 8×6 = 360
x ≥ 0
List all different ways (order doesn’t matter) to choose m basic variables, and for each,
use the program to do the row operations, and mark as infeasible or feasible, and if it is
feasible, write the objective function value. When all have been done, note the optimal
choice, and state clearly the values of all the variables and the objection function value for
this optimal choice.
Deriving the Simplex Method (through examples)
We are now ready, in our example, to explain the simplex method. It is simply an improvement of the brute force method obtained by thinking about what the objective function
row means.
Consider again our earlier sample tableau for the “great” example:
z
x2
s2
s1
s4
z x1 x2 s1 s2 s3 s4 rhs
1 -4.67 0 0 0 1.67 0 25
0 -0.33 1 0 0 0.33 0 5
0 3.67 0 0 1 -1.67 0 25
0 4.33 0 1 0 -1.33 0 40
0 -2.33 0 0 0 1.33 1 8
We use a very simple idea: since we are sitting at a feasible point (no basic variables
are negative) in 7 dimensional space, with x1 and s3 non-basic, and hence 0, what would
happen if we allowed one of them to increase from 0? For example, suppose we let x1
increase to some positive number α. Then the first row would say
z – 4.67α + 1.67s3 = 25,
or
z – 4.67α = 25,
since we are still holding s3 at 0. Doing some very simple algebra, we see that
z = 25 + 4.67α.
CS 4050 Fall 2020 Page 10.16
Chapter 10: Transform and Conquer October 13, 2020
Thus, we would make z bigger by 4.67 units for every unit that we increase x1.
This looks like we could increase x1 to infinity, obtaining an infinitely big objective function
value. But, as we increase x1, how would the basic variables change (the other non-basics,
in this case s3, just stay at 0)?
Row 2 says (leaving out the s3 term since it is being held at 0)
-0.33α + x2 = 5,
or
x2 = 5 + 0.33α.
This is great, because as we increase α, making z bigger, x2 also gets bigger, continuing to
satisfy the restriction that x2 ≥ 0. Note that x2, being basic, doesn’t appear in any other
rows, so changes to x2 don’t affect the other equations.
Row 3, on the other hand, says that
3.67α + s2 = 25,
or
s2 = 25 – 3.67α.
Thus, as x1 increases, s2 decreases. In fact, at α = 325 .67, s2 hits 0. And, if x1 were to go
above 25
3.67, s2 would go negative, violating the restriction s2 ≥ 0.
Similarly, row 3 says that x1 can’t increase beyond 440 .33, or s1 would go negative.
Finally, as x1 increases, s4 also increases (just like x2 did).
The Simplex Method
We have derived most of the simplex method:
First, look in the objective function row for a non-basic variable that has a
negative coefficient.
Then in the column for that non-basic variable we compute the minimum
ratio of a right-hand side value in a row divided by the coefficient in the
non-basic column—but we only do this for positive coefficients (negative or
zero coefficients represent basic variables that get more positive).
Having thus identified a column and then a row in the tableau, we pivot
in that position, letting the formerly non-basic variable become the basic
variable for the row, and forcing the previously basic variable for the row to
hit 0 and become non-basic.
This step is repeated until there are no more non-basic variables with a
negative coefficient in the objective function row.
Note that when doing this process, we can reach a place where a non-basic variable has no
positive numbers in its column. This situation allows us to increase that non-basic variable
to infinity, while keeping the constraints and restrictions satisfied. In this situation we say
that the problem is unbounded.
CS 4050 Fall 2020 Page 10.17
Chapter 10: Transform and Conquer October 13, 2020
A First Example of the Simplex Method
⇒ Using ManualSimplex, let’s perform the simplex method on the example tableau, starting
with x1, s1, s2, and s3 as the basic variables.
Getting an Initial Feasible Basis
This is all great, but the simplex method needs to start with a choice of basic variables
that is feasible, so it can iteratively improve, but it turns out to be just as hard (in a
philosophical sense) to find an initial feasible basis as it is to solve the problem in general.
One good strategy (which we will use exclusively) for getting an initial feasible basis is to
add an artificial variable to each row that does not have a slack variable already providing a
nice choice for a basic variable, and to temporarily use as the objective function “minimize
the sum of the artificial variables.” This is known as “Phase 1.”
If the original constraints have a feasible point, all the artificial variables can be reduced
to 0, giving an initial feasible basis without any artificial variables. Then we delete the artificial variable columns, change the objective function to be the actual objective function,
pivot on the basic columns to zero out the new objective function row in those columns,
and solve the original problem. This is known as “Phase 2.”
At the start of both Phases we must pivot on all the basic variable spots to ensure that
the objective function coefficients are correct. This is known as “pricing out.”
Note that Phase 1 requires minimizing z instead of maximizing. To do this we simply
multiply the objective function by -1 and maximize it, recognizing that the resulting
objective function value will be the opposite of the optimal value of the original objective
function.
This technique is useful any time we want to minimize rather than maximizing.
⇒ Let’s use the Phase1-Phase 2 technique to solve our “great” example, starting with just
slack variables and artificial variables as the basic variables at the beginning.
The first step is to notice that the slack variables s1, s2, and s3 can be chosen as basic at
the start—since they only appear once in the problem, and the right-hand side values of
the equations they occur in are nonnegative, we can pivot on them without introducing a
negative value on the right-hand side.
So, it’s only the row using the surplus variable s4 that doesn’t have an obvious variable to
pivot on. So, we simply add an artificial variable a1, obtaining:
x1 + 4×2 – s4 + a1 = 12
Note that if we pivot on a1, the right-hand side will remain at 12.
CS 4050 Fall 2020 Page 10.18
Chapter 10: Transform and Conquer October 13, 2020
But, of course we can’t just add in a meaningless new variable for free. The price we pay is
that we have to use “minimize the sum of the artificial variables” as our Phase 1 objective.
Since a1 is the only artificial variable we had to add, the objective becomes “minimize a1.”
But, the simplex method always maximizes z. So, we turn the objective function upside
down and change our objective to “maximize -a1.”
As usual, to make the objective function look like a constraint we introduce z by saying
z = -a1
and then doing a little algebra to put this constraint in the usual form:
z + a1 = 0.
So, here is our Phase 1 problem:

max

z

subject to z + a1 = 0

3×1 + 4×2 + s1 = 60
2×1 + 5×2 + s2 = 50
-x1 + 3×2 + s3 = 15
x1 + 4×2 – s4 + a1 = 12
x ≥ 0
s ≥ 0
a ≥ 0
We put the data into a file named greatPhase1 and do
java ManualSimplex greatPhase1
at the command line, obtaining this initial tableau:
z
s1
s2
s3
a1
z x1 x2 s1 s2 s3 s4 a1 rhs
1 0 0 0 0 0 0 1 0
0 3 4 1 0 0 0 0 60
0 2 5 0 1 0 0 0 50
0 -1 3 0 0 1 0 0 15
0 1 4 0 0 0 -1 1 12
This tableau is not actually a legal initial tableau, because the upper-right corner value is
supposed to be the value of the objective function for the current choice of basic variables,
but it says 0. It should say -12, because z = -a1 is the function we want to maximize,
and from the last row we can read off that a1 = 12.
The problem is that we are listing a1 as basic for the last row, simply by typing it in the
data file, but we haven’t pivoted on it, so there’s a 1 in the a1 column that should be
zeroed out.
CS 4050 Fall 2020 Page 10.19
Chapter 10: Transform and Conquer October 13, 2020
So, we put the cursor on the bottom row, in the column for a1, and hit p, obtaining the
correct initial tableau. The other good thing that happens at this point is that some
negative values appear in the objective function row—without those, we would think that
we could not improve the objective function.
z
s1
s2
s3
a1
z x1 x2 s1 s2 s3 s4 a1 rhs
1 -1 -4 0 0 0 1 0 -12
0 3 4 1 0 0 0 0 60
0 2 5 0 1 0 0 0 50
0 -1 3 0 0 1 0 0 15
0 1 4 0 0 0 -1 1 12
Now we could let either x1 or x2 move from non-basic to basic and improve the objective
function, because they both have negative values in the z row. Let’s pick x2, because it
has a more negative value (this is a very arbitrary choice, but not bad).
So, as reasoned before, we know that letting x2 increase to some positive value will typically change all the basic variables. We’ll discuss the details of this once more, and then
summarize our findings.
For s1, we have (we’ll say once more, x1 is being held at 0 so it isn’t mentioned in the
equation)
4×2 + s1 = 60,
or
s1 = 60 – 4×2,
so x2 can increase up to 60 4 = 15, which would force s1 to 0. Note that this value—15—is
simply the ratio of the right-hand side number 60 for the row divided by the coefficient of
x2 in the row for s1.
For s2, we have
5×2 + s2 = 50,
or
s2 = 50 – 5×2,
so x2 can increase up to 50 5 = 10, at which point s2 would be forced to 0. Again, and for
the last time (but note that you will need to understand the minimum ratio computation
for the test), we observe that 10 is just the ratio of the right-hand side by the coefficient
in the entering column—the column for x2.
For s3, the ratio is 15 3 , which is 5, and for a1 the ratio is 12 4 , which is 4.
So, as x2 increases, the first currently basic variable that is pushed to 0 will be a1, when
x2 reaches 4. We say that 4 is the minimum ratio. In the software, you can simply press m
to move the cursor to the row with the minimum ratio, which is where it should be when
you press p.
CS 4050 Fall 2020 Page 10.20
Chapter 10: Transform and Conquer October 13, 2020
Finally, pressing p with the cursor in the a1 row, x2 column, produces this tableau (and
registers x2 as basic, having replaced a1):
z
s1
s2
s3
x2
z x1 x2 s1 s2 s3 s4 a1 rhs
1 0 0 0 0 0 0 1 0
0 2 0 1 0 0 1 -1 48
0 0.75 0 0 1 0 1.25 -1.25 35
0 -1.75 0 0 0 1 0.75 -0.75 6
0 0.25 1 0 0 0 -0.25 0.25 3
At this point when we scan the z row for a negative value, we don’t find any, so no non-basic
variable can be raised from 0 to make the objective function bigger. Also, in the upperright corner we see 0 as the current z value. This makes sense, because a1 has become
non-basic, so its value is 0, so the objective function value is 0. So, we have reached the
optimal choice of basic variables for the Phase 1 LP. All this has been done in order to get
a choice of basic variables that has all nonnegative values, and is hence a feasible point.
We are now ready to move on to Phase 2, and solve the actual problem.
Our first step is to delete all the artificial columns—they don’t appear in the original
problem, and they were forced to 0 by Phase 1. This gives us, obviously, this tableau:
z
s1
s2
s3
x2
z x1 x2 s1 s2 s3 s4 rhs
1 0 0 0 0 0 0 0
0 2 0 1 0 0 1 48
0 0.75 0 0 1 0 1.25 35
0 -1.75 0 0 0 1 0.75 6
0 0.25 1 0 0 0 -0.25 3
Next we need to manually edit the z row (hit e to edit the table arbitrarily, and then
esc) to put in the Phase 2 objective, which is to maximize z = 3×1 + 5×2, giving us the
constraint z – 3×1 – 5×2 = 0, for this tableau:
z
s1
s2
s3
x2
z x1 x2 s1 s2 s3 s4 rhs
1 -3 -5 0 0 0 0 0
0 2 0 1 0 0 1 48
0 0.75 0 0 1 0 1.25 35
0 -1.75 0 0 0 1 0.75 6
0 0.25 1 0 0 0 -0.25 3
As at the start of Phase 1, this is not a valid tableau, because we have just arbitrarily
typed numbers in the z row, so we might have messed up a basic column. Indeed, note
that x2 is listed as basic, so its column should have all zeros except for the 1 in the x2 row.
And, consequently, the upper-right corner number of 0 is silly.
CS 4050 Fall 2020 Page 10.21
Chapter 10: Transform and Conquer October 13, 2020
So, we simply pivot on all the basic variables that have had their identity columns messed
up by the editing in of new numbers in those columns. In this case, this only happens for
x2, so after pivoting on the 1 in the x2 row in the x2 column, we obtain:
z
s1
s2
s3
x2
z x1 x2 s1 s2 s3 s4 rhs
1 -1.75 0 0 0 0 -1.25 15
0 2 0 1 0 0 1 48
0 0.75 0 0 1 0 1.25 35
0 -1.75 0 0 0 1 0.75 6
0 0.25 1 0 0 0 -0.25 3
As a check, note that the upper-right corner value is 15. Is this correct? Well, the objective
function is z = 3×1 + 5×2, and x1 = 0 (it’s non-basic), and x2 = 3, so, yes, we should have
z = 3(0) + 5(3) = 15.
Next we proceed with standard simplex method steps. There are two negative values in
the z row, so we arbitrarily pick x1 to enter the basic variables. The ratios for the x1
column are 48
2 = 24, .35 75 = 46.666, and .25 3 = 12 (we don’t do ratios for negative or zero
values in the column because those basic variables are getting more positive or staying
the same as the chosen non-basic increases), so we pivot in the x2 row in the x1 column,
obtaining:
z
s1
s2
s3
x1
z x1 x2 s1 s2 s3 s4 rhs
1 0 7 0 0 0 -3 36
0 0 -8 1 0 0 3 24
0 0 -3 0 1 0 2 26
0 0 7 0 0 1 -1 27
0 1 4 0 0 0 -1 12
There’s still a negative in the z row, for column s4, so after determining the minimum
ratio we pivot in the s1 row, obtaining:
z
s4
s2
s3
x1
z x1

x2 -1	s1 1
-2.67 0.33 2.33 -0.67
4.33 1.33	0.33 0.33

s2 s3 s4 rhs
1 0 0 0 1 0 0 10
Doing one more step (x2 becomes basic in place of s2), we have:
CS 4050 Fall 2020 Page 10.22
Chapter 10: Transform and Conquer October 13, 2020
z
s4
x2
s3
x1
z x1 x2

s1 0.71

s2 0.43

s3 s4 rhs
.29
0 0 0 -0.43 1.14 0 1 19.43
0 0 1 -0.29 0.43 0 0 4.29
0 0 0 1.57 -1.86 1 0 16.43
0 1 0 0.71 -0.57 0 0 14.29
This is the optimal tableau, with z = 64.29 (all the values are rounded), x1 = 14.29, and
x2 = 4.29, s3 = 16.43, s4 = 19.43, and the other variables non-basic and hence 0.
We can check these values against the original problem:
3×1 + 5×2 = 3(14.29) + 5(4.29) = 64.32
3×1 + 4×2 + s1 = 3(14.29) + 4(4.29) + 0 = 60.03
2×1 + 5×2 + s2 = 2(14.29) + 5(4.29) + 0 = 50.03
-x1 + 3×2 + s3 = -14.29 + 3(4.29) + 16.43 = 15.01
x1 + 4×2 – s4 = 14.29 + 4(4.29) – 19.43 = 12.02
so everything checks (within rounding error).
CS 4050 Fall 2020 Page 10.23
Chapter 10: Transform and Conquer October 13, 2020
Exercise 26 [10 points] (target due date: Monday, October 26)(medskip
For each of the 3 problems below, produce a careful mathematical description of the LP,
ready to be put into a data file for use with ManualSimplex. Then use the application,
noting the values of the basic variables and the objective function at the optimal tableau
for both Phase 1 and Phase 2, as appropriate, and describe the final solution to each
problem as infeasible, unbounded, or having an optimal feasible point.
a. Formulate and solve this LP:
max x1 + 2×2 + 3×3
subject to the constraints
-3×1 + 15×2 – 3×3 ≥ 3
6×1 + 3×2 + 6×3 ≤ 60
-6×1 + 6×2 + 3×3 ≤ 21
9×1 + 5×2 – x3 ≥ 21
-3×1 + 5×2 + 2×3 ≥ 3
6×1 + 8×2 – 4×3 ≤ 30
8×2 – 4×3 ≤ 12
3×1 + 3×3 ≥ 12
x1, x2, x3 ≥ 0
b. Formulate and solve the above LP, but with this constraint added:
2×3 ≤ 1
c. Formulate and solve the LP for part a, but with the first four constraints removed.
CS 4050 Fall 2020 Page 10.24