Phase I and Phase II

From Glossary

Jump to: navigation, search

Phase I of a mathematical program is finding a feasible solution, and Phase II is entered with a feasible solution to find an optimal solution. The standard Phase I is:

\max \sum_i \{u_i\} + \sum_i \{v_i + w_i\}: u, v, w \ge 0,

g(x) - u \le 0, h(x) - v + w = 0.

Then, for any LaTeX: x, one could set LaTeX: \textstyle u = g(x)^+, v = h(x)^+ and w = -h(x)^- to have a feasible solution to the Phase I mathematical program. The optimal objective value is 0 if, and only if, LaTeX: u=0 and LaTeX: v=w=0, in which case LaTeX: x is feasible in the original mathematical program (to commence Phase II). The Phase I problem is sometimes called an elastic program (thinking of the artificial variables LaTeX: (u,v,w) as providing "elastic" behavior in the levels of constraint violation).

In linear programming, the standard Phase I & II are:

I. Min ev: LaTeX: \textstyle x, v \ge 0, Ax + v = b, and
II. Max cx: LaTeX: \textstyle x \ge 0, Ax = b, \mbox{ where } b \ge 0 \mbox{ (multiply by } -1 \mbox{ for } i: b_i < 0.

Personal tools