Transcript Slide 1

Lecture 9: Constraint Relaxation
Simplex Method
Munkres Assignment
Branch-and-Bound Search
Constraint Relaxation
Problem solving methods that use constraint relaxation take advantage of a low-order
polynomial algorithm to test a whether a solution exists which is at least as "good" as some
set value (the constraint). If no solution is found or if it is determined that no solution exists
whose values meets or beats the constraint value, then that value is relaxed by some amount
the the test is repeated.
If the constraint value type is discrete the relaxation can be by a minimum (e.g. unit) amount.
An optional approach that can be adapted to continuous type constraint values is the use of
the bisection method.
Linear Programming (LP) Problem
A linear programming (LP) problem is a problem in which we are asked to find the maximum
(or minimum) value of a linear objective function
p = ax + by + cz + ...
Example: p = 3x - 2y + z
Subject to one or more linear constraints of the form
Ax + By + Cz + . . . <= (or >= ) N
Example: x + y - 3z <= 12
The desired largest (or smallest) value of the objective function is called the optimal value, and a
collection of values of x, y, z, . . . that gives the optimal value constitutes an optimal solution. The
variables x, y, z, . . . are called the decision variables.
http://people.hofstra.edu/Stefan_waner/RealWorld/
Standard Maximization Problem
A linear programming (LP) problem is called a standard maximization problem if:
We are to find the maximum (not minimum) value of the objective function.
All the variables x, y, z, ... are constrained to be non-negative.
All further constraints have the form Ax + By + Cz + . . . <= N (and not >= ).
Example: The following is a standard maximization problem:
Maximize p = 2x - 3y + 4z subject to the constraints
4x - 3y + z <= 3
x + y + z <= 10
2x + y - z <= 10,
where x, y, and z are non-negative.
Simplex Method
step-by-step
Step1: Convert the LP problem to a system of linear equations.
The constraints
4x - 3y + z <= 3
x + y + z <= 10
2x + y - z <= 10
in the above LP problem are written as equations by adding a new slack variable to the left-hand side
of each to take up the slack. In addition, the objective function
p = 2x - 3y + 4z
is rewritten with all the unknowns on the left-hand side. This gives the following system of equations.
4x
x
2x
-2x
- 3y + z +
+ y + z +
+ y - z +
+ 3y -4z +
s
t
u
p
= 3
= 10
= 10
= 0
Step 2: Set up the initial tableau.
By the initial "tableau," we mean the augmented matrix of the system of equations we just
obtained.
Example
For the system
4x
x
2x
-2x
- 3y + z +
+ y + z +
+ y - z +
+ 3y -4z +
s
t
u
p
= 3
= 10
= 10
= 0
the initial tableau is as follows
x
z
s
t
u
p
Ans
4 -3 1
1 1 1
2 1 -1
1
0
0
0
1
0
0
0
1
0
0
0
3
10
10
0
0
0
1
0
-2
y
3 -4
Step 3: Select the pivot column.
The rule for the selecting a pivot column is this:
Look at all the numbers in the bottom row, excluding the Answer column. From these, choose the
negative number with the largest magnitude. Its column is the pivot column. (If there are two
candidates, choose either one.) If all the numbers in the bottom row are zero or positive, then you
are done, and the basic solution is the optimal solution.
Example
In the initial tableau you just analyzed, the most negative number in the bottom row is the -3, and
hence the pivot column is the z-column. This means that the pivot will be somewhere in the zcolumn.
x
z
s
t
u
p
Ans
4 -3 1
1 1 1
2 1 -1
1
0
0
0
1
0
0
0
1
0
0
0
3
10
10
0
0
0
1
0
-2
y
3 -4
Step 4: Select the pivot in the pivot column.
Selecting the Pivot
1) The pivot must always be a positive number. (This rules out zeros and negative numbers,
such as the -3 in the bottom row.)
2) For each positive entry b in the pivot column, compute the ratio a/b, where a is the number in
the rightmost column in that row. We call this a test ratio.
3) Of these ratios, choose the smallest one. The corresponding number b is the pivot.
Example
In the following tableau, the pivot column is the "t"-column. Since neither zeros nor negative
numbers can serve as a pivot, we must choose between the 3 and the 1 in the "t"-column. The test
ratios are shown on the side.
x
y
z
s
t
u
p
Ans
0 -3 1
4 1 0
0 10 -1
1
0
0
3
1
0
0
0
2
0
0
0
3
10
10
0
0 -4
0
5
15
3
0
test ratio = 3/3 = 1
test ratio = 10/1 =10
Since 3/3 = 1 is the smaller of the two test ratios, the pivot is the 3.
Step 5: Use the pivot to clear the pivot column in the normal manner.
This gives the next tableau.
Example
In the following tableau, the pivot is shown in color, and we clear its column using the given row
operations.
x
y
s
t
u
p
Ans
0 -3
4 1
0 1
1 1
0 0
0-10
3
1
0
0
0
2
0
0
0
3
10 3R2 - R1
10
0
0
0 -4
0
5
15 3R4 + 4R1
z
s
t
u
p
Ans
0 -3 1 1
12 6 -1 -1
0 1 0-10
3
0
0
0
0
2
0
0
0
3
27
10
0
0 15
57
3
z
This gives the next tableau:
x
y
0 -3
4
4
Step 6: Repeat Steps 3-5 until there are no more negative numbers in the bottom row (with
the possible exception of the Answer column).
x
y
z
7
59
-28
0
0
3
4
0
s
u
p
Ans
1 1
0 8
0 -4
0 0
3 -2
0 1
0
0
0
6
48
6
0
0
3
66
1
t
2
The x-column is not cleared, so x = 0.
Since the y-column is cleared with pivot 3, the value of y is 6/3 = 2.
Since the z-column is cleared with pivot 1, the value of y is 6/1 = 6.
Since the t-column is cleared with pivot 3, the value of t is 48/3 = 16.
Since the s and u-columns are not cleared, their value is 0.
Since the p-column is cleared with pivot 3, the value of y is 66/3 = 22.
Maximal Matching Problem
Assume we have a graph made up of two groups of nodes.
Every node in Group I is connected to at least one node in Group II and vice
versa. However no two nodes in the same group are connected.
We are interested in finding the maximum number of pairings of nodes in Group I with
nodes in Group II. Any node can be a member of, at most one pairing.
Graphs of the type described here are called bipartite graphs.
Group I
Group II
The Algorithm
Given a bipartite graph Gn,m we are to find a maximal matching (max number of pairs)
between the n nodes of group I and the m nodes of group II. There is a greedy
algorithm for the maximal matching problem:
Augmenting Path: An Example
Start with a bipartite graph.
Choose arbitrary pairings until no additional matches are possible.
In this example nodes C, R and S are not matched.
Matching edges are shown in bold
We will now build an augmenting path starting from node S.
S-A=P-C.
We exchange the matched and unmatched edges in this augmenting
path increasing the total number of matches by one.
A is matched to S
B is matched to Q
C is matched to P
This is a maximal matching because there are no more unmatched
nodes in one of the two groups.
Munkres Assignment
Assignment Problem - Let C be an nxn matrix representing the costs of each of n workers to
perform any of n jobs. The assignment problem is to assign jobs to workers so as to minimize
the total cost. Since each worker can perform only one job and each job can be assigned to only
one worker the assignments constitute an independent set of the matrix C.
An arbitrary assignment is shown above in which worker a is assigned job q, worker b is
assigned job s and so on. The total cost of this assignment is 23. Can you find a lower cost
assignment? Can you find the minimal cost assignment? Remember that each assignment
must be unique in its row and column.
A brute-force algorithm for solving the assignment problem involves generating all independent
sets of the matrix C, computing the total costs of each assignment and a search of all assignment
to find a minimal-sum independent set.
The complexity of this method is driven by the number of independent assignments possible in
an nxn matrix. There are n choices for the first assignment, n-1 choices for the second assignment
and so on, giving n! possible assignment sets. Therefore, this approach has, at least, an
exponential runtime complexity.
As each assignment is chosen that row and column are eliminated from consideration. The
question is raised as to whether there is a better algorithm. In fact there exists a polynomial
runtime complexity algorithm for solving the assignment problem developed by James Munkre's
in the late 1950's.
The following 6-step algorithm is a modified form of the original Munkres' Assignment
Algorithm (sometimes referred to as the Hungarian Algorithm). This algorithm describes to the
manual manipulation of a two-dimensional matrix by starring and priming zeros and by covering
and uncovering rows and columns.
Step 0: Create an nxm matrix called the cost matrix in which each element represents the
cost of assigning one of n workers to one of m jobs. Rotate the matrix so that there are at least
as many columns as rows and let k=min(n,m).
Step 1: For each row of the matrix, find the smallest element and subtract it from every
element in its row. Go to Step 2.
Step 2: Find a zero (Z) in the resulting matrix. If there is no starred zero in its row or column,
star Z. Repeat for each element in the matrix. Go to Step 3.
Step 3: Cover each column containing a starred zero. If K columns are covered, the starred
zeros describe a complete set of unique assignments. In this case, Go to DONE, otherwise, Go
to Step 4.
Step 4: Find a noncovered zero and prime it. If there is no starred zero in the row containing
this primed zero, Go to Step 5. Otherwise, cover this row and uncover the column containing
the starred zero. Continue in this manner until there are no uncovered zeros left. Save the
smallest uncovered value and Go to Step 6.
Step 5: Construct a series of alternating primed and starred zeros as follows. Let Z0 represent
the uncovered primed zero found in Step 4. Let Z1 denote the starred zero in the column of Z0 (if
any). Let Z2 denote the primed zero in the row of Z1 (there will always be one). Continue until
the series terminates at a primed zero that has no starred zero in its column. Unstar each starred
zero of the series, star each primed zero of the series, erase all primes and uncover every line in
the matrix. Return to Step 3.
Step 6: Add the value found in Step 4 to every element of each covered row, and subtract it from
every element of each uncovered column. Return to Step 4 without altering any stars, primes, or
covered lines.
DONE: Assignment pairs are indicated by the positions of the starred zeros in the cost matrix. If
C(i,j) is a starred zero, then the element associated with row i is assigned to the element
associated with column j.
Some of these descriptions require careful interpretation. In Step 4, for example, the possible
situations are, that there is a noncovered zero which get primed and if there is no starred zero in its
row the program goes onto Step 5. The other possible way out of Step 4 is that there are no
noncovered zeros at all, in which case the program goes to Step 6.
At first it may seem that the erratic nature of this algorithm would make its implementation
difficult. However, we can apply a few general rules of programming style to simplify this
problem. The same rules can be applied to any step-algorithm.
procedure munkres is
n : constant integer := 20;
C : is array(1..n,1..n) of float;
M : is array(1..n,1..n) of integer;
Row,Col : is array(1..n) of integer;
stepnum : integer;
done : boolean;
-- num rows/columns
-- cost matrix
-- a mask matrix to indicate
-- primed (=2) starred (=1) zeros in C
-- which row/columns are covered.
-- covered = 1, non-covered = 0
function step1(stepnum: in out integer) is
:
function step2(stepnum: in out integer) is
:
function step3(stepnum: in out integer) is
:
begin
done:=false;
stepnum:=1;
while not(done) loop
case stepnum is
when 1 => step1(stepnum);
when 2 => step2(stepnum);
when 3 => step3(stepnum);
when 4 => step4(stepnum);
when 5 => step5(stepnum);
when 6 => step6(stepnum);
when others => done:=true;
end case;
end loop;
end munkres;
In each pass of the loop the procedure called sets the value
of stepnum for the next pass. When the algorithm is
finished the value of stepnum is set to some value outside
the range 1..6 so that done will be set to true and the
program will end. In the completed program the tagged
(starred) zeros flag the row/column pairs that have been
assigned to each other.
We will assume that the cost matrix C(i,j) has already been
loaded with the first index referring to the row number and
the second index referring to the column number.
Step 1: For each row of the matrix, find the smallest element and subtract it from every element in
its row. Go to Step 2.
We can define a local variable called minval that is used to hold the smallest value in a row. Notice
that there are two loops over the index j appearing inside an outer loop over the index i. The first
inner loop over the index j searches a row for the minval. Once minval has been found this value is
subtracted from each element of that row in the second inner loop over j. The value of step is set to 2
just before stepone ends.
procedure stepone(step : in out integer) is
minval : integer;
begin
for i in 1..n loop
minval:=C(i,1);
for j in 2..n loop
if minval>C(i,j) then
minval:=C(i,j);
end if;
end loop;
for j in 1..n loop
C(i,j):=C(i,j)-minval;
end loop;
end loop;
step:=2;
end stepone;
Step 2: Find a zero (Z) in the resulting matrix. If there is no starred zero in its row or column, star
Z. Repeat for each element in the matrix. Go to Step 3.
In this step, we introduce the mask matrix M, which in the same dimensions as the cost matrix and
is used to star and prime zeros of the cost matrix. If M(i,j)=1 then C(i,j) is a starred zero, If
M(i,j)=2 then C(i,j) is a primed zero. We also define two vectors R_cov and C_cov that are used to
"cover" the rows and columns of the cost matrix C.
procedure steptwo(step: in out integer) is
begin
for i in 1..n loop
for j in 1..n loop
if C(i,j)=0 and C_cov(j)=0 and R_cov(i)=0 then
M(i,j):=1;
C_cov(j):=1;
R_cov(i):=1;
end if;
end loop;
end loop;
for i in 1..n loop
C_cov(i):=0;
R_cov(i):=0;
end loop;
step:=3;
end steptwo;
In the nested loop (over indices i and j) we check to see if C(i,j) is a zero value and if its column or
row is not already covered. If not then we star this zero (i.e. set M(i,j)=1) and cover its row and
column (i.e. set R_cov(i)=1 and C_cov(j)=1). Before we go on to Step 3, we uncover all rows and
columns so that we can use the cover vectors to help us count the number of starred zeros.
Step 3: Cover each column containing a starred zero. If K columns are covered, the starred zeros
describe a complete set of unique assignments. In this case, Go to DONE, otherwise, Go to Step 4.
Once we have searched the entire cost matrix, we count the number of independent zeros found. If
we have found (and starred) K independent zeros then we are done. If not we proceed to Step 4.
procedure stepthree(step : in out integer) is
count : integer;
begin
for i in 1..n loop
for j in 1..n loop
if M(i,j)=1 then
C_cov(j):=1;
end if;
end loop;
end loop;
count:=0;
for j in 1..n loop
count:=count + C_cov(j);
end loop;
if count>=n then
step:=7;
else
step:=4;
end if;
end stepthree;
Step 4: Find a noncovered zero and prime it. If there is no starred zero in the row containing this
primed zero, Go to Step 5. Otherwise, cover this row and uncover the column containing the starred
zero. Continue in this manner until there are no uncovered zeros left. Save the smallest uncovered
value and Go to Step 6.
procedure stepfour(step : in out integer) is
row,col : integer;
done
: boolean;
begin
done:=false;
while not(done) loop
find_a_zero(row,col);
if row=0 then
done:=true;
step:=6;
else
M(row,col):=2;
if star_in_row(row) then
find_star_in_row(row,col);
R_cov(row):=1;
C_cov(col):=0;
else
done:=true;
step:=5;
Z0_r:=row;
Z0_c:=col;
end if;
end if;
end loop;
end stepfour;
procedure find_a_zero(row,col : out integer) is
i,j : integer;
done: boolean;
begin
row:=0;
col:=0;
i:=1;
done:=false;
loop
j:=1;
loop
if C(i,j)=0 and R_cov(i)=0 and C_cov(j)=0 then
row:=i;
col:=j;
done:=true;
end if;
j:=j+1;
exit when j>n;
end loop;
i:=i+1;
if i>n then done:=true; end if;
exit when done;
end loop;
end find_a_zero;
function star_in_row(row : integer) return boolean is
tbool : boolean;
begin
tbool:=false;
for j in 1..n loop
if M(row,j)=1 then
tbool:=true;
end if;
end loop;
return tbool;
end star_in_row;
procedure find_star_in_row(row, col : in out integer) is
begin
col:=0;
for j in 1..n loop
if M(row,j)=1 then
col:=j;
end if;
end loop;
end find_star_in_row;
Step 5: Construct a series of alternating primed and starred zeros as follows. Let Z0 be the uncovered
primed zero from Step 4. Let Z1 be the starred zero in the column of Z0 (if any). Let Z2 be the primed zero
in the row of Z1. Continue until the series end at a primed zero with no starred zero in its column. Unstar
each starred zero of the series, star each primed zero of the series, erase all primes and uncover every line
in the matrix. Return to Step 3.
procedure
count
done
r,c
stepfive(step : in out integer) is
: integer;
: boolean;
: integer;
begin
count:=1;
path(count,1):=z0_r;
path(count,2):=z0_c;
done:=false;
while not(done) loop
find_star_in_col(path(count,2),r);
if r>0 then
count:=count+1;
path(count,1):=r;
path(count,2):=path(count-1,2);
else
done:=true;
end if;
if not(done) then
find_prime_in_row(path(count,1),c);
count:=count+1;
path(count,1):=path(count-1,1);
path(count,2):=c;
end if;
end loop;
convert_path;
clear_covers;
erase_primes;
step:=3;
end stepfive;
You may notice that Step 5 seems vaguely familiar. It is a verbal description of the augmenting path
algorithm (for solving the maximal matching problem) which we discussed in Lecture 3. We
decompose the operations of this step into a main procedure and five relatively simple subprograms.
procedure find_star_in_col(c : in integer; r : in out integer) is
begin
r:=0;
for i in 1..n loop
if M(i,c)=1 then
r:=i;
end if;
end loop;
end find_star_in_col;
procedure find_prime_in_row(r : in integer; c : in out integer) is
begin
for j in 1..n loop
if M(r,j)=2 then
c:=j;
end if;
end loop;
end find_prime_in_row;
procedure convert_path is
begin
for i in 1..count loop
if M(path(i,1),path(i,2))=1 then
M(path(i,1),path(i,2)):=0;
else
M(path(i,1),path(i,2)):=1;
end if;
end loop;
end convert_path;
procedure clear_covers is
begin
for i in 1..n loop
R_cov(i):=0;
C_cov(i):=0;
end loop;
end clear_covers;
procedure erase_primes is
begin
for i in 1..n loop
for j in 1..n loop
if M(i,j)=2 then
M(i,j):=0;
end if;
end loop;
end loop;
end erase_primes;
Step 6: Add the value found in Step 4 to every element of each covered row, and subtract it from
every element of each uncovered column. Return to Step 4 without altering any stars, primes, or
covered lines.
procedure stepsix(step : in out integer) is
minval : integer;
begin
find_smallest(minval);
for i in 1..n loop
for j in 1..n loop
if R_cov(i)=1 then
C(i,j):=C(i,j)+minval;
end if;
if C_cov(j)=0 then
C(i,j):=C(i,j)-minval;
end if;
end loop;
end loop;
step:=4;
end stepsix;
Notice that this step uses the smallest uncovered value in the cost matrix to modify the matrix. Even
though this step refers to the value being found in Step 4 it is more convenient to wait until you reach
Step 6 before searching for this value.
It may seem that since the values in the cost matrix are being altered, we would lose sight of the
original problem. However, we are only changing certain values that have already been tested and
found not to be elements of the minimal assignment. Also we are only changing the values by an
amount equal to the smallest value in the cost matrix, so we will not jump over the optimal (i.e.
minimal assignment) with this change.
procedure find_smallest(minval : out integer) is
begin
minval:=integer'last;
for i in 1..n loop
for j in 1..n loop
if R_cov(i)=0 and C_cov(j)=0 then
if minval>C(i,j) then
minval:=C(i,j);
end if;
end if;
end loop;
end loop;
end find_smallest;
Munkres Assignment
Sample Execution
Euclidean TSP
Euclidean TSP is a sub-class of the TSP problem in which the cities are points in R2
and the distances between cities are the Euclidean (straight-line) distances between
the points corresponding to cites.
It has been shown that this sub-class of the the general TSP problem is solvable in
determiministic polynomial time. We will use this sub-class as an example of a problem
class for which standard B&B fails.
A
B
4
C
D
F
E
G
H
J
M
K
N
I
O
P
L
In integer approximation of the distances between the cities of the Euclidean TSP
A
B
C
D
A
-
8
5
5 13 11 11 13 18 18 16 20 22 21 21 22
B
8
- 13
C
5 13
-
8 16
D
5
8
-
8 13
5 11 13 17 13 14 20 18 16 17
5 16
8
- 21
5 18 13 23 17 12 26 23 20 17
E 13
5
F 11 18
G 11
5
F
5 18
5 13 21
8 13
H 13 17
5
E
- 16
J 18 23 13 17 23
5 18
J
K
L
M
N
O
P
K 16 18 13 13 17 11 11
8 11 22 12 13 17 20
8 18 11
- 13
8 12
8 18
L 20 17 20 14 12 22
I
8 17 13 13 20 17 16 18 20
- 13
5 13
I 18 16 17 13 13 18
H
8 17 16 23 18 17 26 23 21 20
5 13
5 16
8 11 18
G
5
- 17
9 20 17 13 12
5 17
9
9
8 11 14
5 18 14
9
8
5 17
-
8 20
4
5 13 17
5
8
- 12
9
5
5
9
- 21 17
9
5
9 17
9
5 20 12
M 22 26 17 20 26 12 20
9 18
4
8 21
-
4 12 16
N 21 23 16 18 23 13 17
8 14
5
5 17
4
-
8 12
O 21 21 18 16 20 17 13 11
9 13
5
9 12
8
-
4
P 22 20 20 17 17 20 12 14
8 17
9
5 16 12
4
-
A greedy solution to this TSP will result in a tour of length..
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
5
5
5 13 11 11 13 18 18 16 20 22 21 21 22__
5
5 5 18 8 17 16 23 18 17 26 23 21 20 __
5
A
-
8
5
B
8
- 13
5
C
5 13
-
8 16
5
D
5
8
-
8 13
13
E 13
5 16
8
- 21
5
F 11 18
5
G 11
5
H 13 17
8
I 18 16 17
4
J 18 23 13
5
K 16 18 13 13 17 11 11
5
L 20 17 20 14 12 22
4
M 22 26 17 20 26 12 20
9 18
4
8 21
-
5
N 21 23 16 18 23 13 17
8 14
5
5 17
4
4
O 21 21 18 16 20 17 13 11
9 13
5
9 12
8
-
5
P 22 20 20 17 17 20 12 14
8 17
9
5 16 12
4
5
87 greedy TSP
8
5
8 17 13 13 20 17 16 18 20 __
5
5 11 13 17 13 14 20 18 16 17 __
5
5 18 13 23 17 12 26 23 20 17 __
5 13
5
8 11 22 12 13 17 20 __
5
5 5 16 - 13 8 18 11 9 20 17 13 12 __
5
11 18 5 13 - 13 5 5 17 9 8 11 14 __
5
13 13 18 8 12 - 17 9 5 18 14 9 8 __
4
17 23 8 18 5 17 - 8 20 4 5 13 17 __
5 13 21
8 13
P
- 16
5 18
5
9 17
9
8
- 12
5 20 12
9
5
5
- 21 17
9
5
9 __
5
5 __
4
4 12 16 __
4
- 8 12 __
4
4 __
4
- __
lower bound heuristic 75
Standard B&B for Euclidean TSP
A
3
B
0
C
0
D
8
E
6
6
8 13 13
F
G
H
I
11 15 17 16 16
J
K
L
M
N
17
O
P
87 - 75 = 12 greater
8
3 11
0
B
D
F
E
8
G
3 12
H
8
I
8
J
15 12 11 13
K
L
M
N
15
O
P
A partial expansion of the permutation tree to the third level for the standard B&B TSP.
Branch & Bound with Constraint Relaxation
Rather than set global upper and lower bounds based on the greedy TSP solution and the
min cost heuristic, we can analyze our example problem and note that no city is farther than
a distance of 5 from its nearest neighbors (points in R2).
Using the Constraint Relaxation problem solving method we search the permutation tree with
the maximum allowed node-to-node distance set to some value, say 8. If no solution is
found we relax the constraint up to 9 and repeat until a solution is found. At a smallest
constraint level for which we find at least one solution, the shortest TSP solution will be an
overall minimal solution.
A
B
4
C
D
F
E
G
H
J
M
K
N
I
O
P
L
B&B TSP with Constraint Relaxation
(maxval = 8)
A
B
D
C E G
D G
C
E
D E
G
I
D
B E G
F
H J
D
H
F J K
B
E G
C
F H
E
B G
G
B E
The first three levels of the permutation tree with maximum node-to-node distances of 8.
I
Solution for max node-to-node = 8
A
C
B
D
F
E
G
H
J
M
K
N
I
O
P
L
Summary
Simplex Method
Munkres Assignment
Branch-and-Bound Search
Standard B&B Traveling Salesperson Problem
B&B TSP with Constraint Relaxation