Chapter 4
\R PROGRAMMING
Algorithm 2DBOUNDEDLP(H,c,ml,m2)
. (H U {m m} c) where H is a set of n half-planes,
Input. A hnear program 1, 2, ,
c E JR2 and ml m2 bound the solution. .
Output. If (H U {~l ,m2}, c) is infeasible, then thi~ fact is repor:ed. OtherWIse,
the lexicographically smallest point p that maX1ITuzesfc(p) IS reported.
-
1. Let Vo be the comer of Co·
2. Let hI, ... ,hn be the half-planes of H.
3. for i<- 1 to n
4. do if Vi-l E hi
5. then Vi <- Vi-l
6. else Vi <-the point p on Ri that maximizes fc(p), subject to the
constraints in Hi-I.
7. if p does not exist·
8. then Report that the linear program is infeasible and quit.
9. return Vn
Algorithm 2DRANDOMIZEDB OUNDEDLP(H, C, ml, m2)
Input. A linear program (HU {ml,m2},c), where H is a set of n half-planes,
cE JR2, and ml, m2 bound the solution.
Output. If (H U {m 1 ,m2}, c) is infeasible, then this fact is reported. Otherwise,
the lexicographically smallest point p that maximizes fc(p) is reported.
1. Let Vo be the comer of Co.
2. Compute a random permutation hI, ... ,hn of the half-planes by calling
RANDOMPERMUTATION(H[1· .. nj).
3. for i <- 1 to n
4. doifvi-lEhi
5. then Vi<- Vi-I
6. else Vi <-the point p on Ri that maximizes fc(p), subject to the
constraints in Hi-I.
7. if p does not exist
8. then Report that the linear program is infeasible and quit.
9. return Vn