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.