|
|
Teach
Linear Programming Excel Add-in
|
|
-
The Interior Point Method
|
|
|
An interior point demonstration is included
in the add-in collection as part of the Teach LP add-in. Access
to the demonstration is via the menu item at the left. The
dialog defining the model is the same as that used for the
tableau and revised simplex options, except we allow only
Demonstration and Run solution options. The Demonstration
option shows each step of the process while the Run option
completes all steps without interruption and presents a summary
of the solutions.
The examples for this section are in the Teach
LP demo (teachlpdem.xls). To solve or change the model you
must have the Teach LP add-in loaded. Use the Relink buttons
command to establish links to the worksheet buttons.
|
|
The Model
After pressing the OK button the model arrays
are constructed on the worksheet. After data is entered, press
the start button to build the arrays for the initial solution.
The figure below shows the example problem. It is the same
as the example for the simplex methods. In the case of the
interior point method, no artificial variables are added.
Data cells are provided for the Step factor
and the Stopping Gap. The Step Factor determines how close
a step will come to the boundary of the feasible region. A
step of 1 goes exactly to the boundary. A number less than
1 should be entered. The Stopping Gap holds the minimum value
of the primal dual gap. The program stops when the gap reaches
this level. The student controls these values by entering
numbers in the cells. They may be changed during a demonstration
run.
The following discussion describes the several
arrays that are placed on the Excel worksheet. Yellow areas
contain formulas that implement the interior point method.
|
|
|
|
Initial Interior Solution
A simple algorithm attempts to find interior solutions for
the primal and dual problems. The algorithm will not work
unless the last m columns of the primal constraints
form a nonsingular matrix. If the algorithm is successful
the initial values of x, z and pi are
set to the interior values; otherwise they are all set to
1. The interior point algorithm is usually successful with
a non-interior start, but it may fail. In the case of the
example, the program did not find an interior primal solution
and the primal variables are set to 1. With a non-interior
initial solution the gap measure is changed as described below.
|
|
|
|
The Current Solution
In the first iteration the initial solution
is placed in the arrays holding the current solution. Note
that these arrays are not colored indicating that the student
may change them. Also shown on the figure is the iteration
number, the gap measure and the value of Mu. When the initial
solution is interior we use the difference between the dual
and primal objective values as a gap measure. This gap is
always positive for interior solutions and decreases as the
iterations progress.
If the solutions are not interior, the gap as
defined above may become negative and is no longer a good
measure of optimality. In this case, the program changes the
gap to the product of the x and z vectors. Because
the optimal solution will satisfy primal-dual complementary
slackness, this measure should approach zero as the solution
approaches the optimum. Note that it is important that both
x and z be strictly positive.
|
|
|
|
Feasibility and Complementary Slackness
The primal and dual feasibility vectors tell whether the
corresponding solution is feasible. The vectors are 0 for
feasible solutions. For the first iteration, the vectors show
that the primal solution is not feasible, while the dual solution
is feasible. The vector labeled Comp. Slack. is a measure
of complementary slackness. It should approach 0 as the iterations
progress.
|
|
The Direction and Ratio Vectors
The direction vectors show directions in which pi,
z and x should change to move toward feasibility
and optimality. The ratio vectors tell how far each component
can change to remain interior to the region. The smallest
ratio indicates the maximum change that will move to a boundary.
We multiply that step by the step factor, less than 1, to
determine how far to move.
|
|
Next Solution
The next solution is reached from the current solution by
taking the indicated step.
|
|
Taking the next step
The iterative process continues by moving the next solution
to the arrays for the current solution. The formulas on the
sheet calculate the new next solution and the process continues.
The procedure terminates when the gap reaches the specified
smallest value.
|
|
The History
The program keeps a history of the primal (x) and
dual (pi) solutions as the algorithm progresses. The
history for the example is shown below.
|
|