LP Tour

 Linear/Integer Programming Solver The LP/IP Solver add-in provides an algorithm that solves Linear and Integer Programming problems. It can be used instead of the Excel solver for the linear models created by the Mathematical Programming add-in. There are no built-in limits for model size. Arrays are dimensioned automatically. For large problems, excessive memory requirements may cause the program to crash or computation time may be large.

When this add-in is installed, a new item appears on the OR_MM menu, LP/IP Solver. This item does not solve models. Rather, models are solved when the user clicks on the Solve button on the linear, integer, or mixed integer model sheets. The LP/IP Solver menu item presents a dialog that sets several parameters related to the solution process and displays. The dialog will appear only when a mathematical programming model constructed with the Math Programming add-in is present on the active worksheet. Otherwise the message below indicates that it is not available.

"This is not a valid worksheet for the LP/IP Solver"

When a valid worksheet is active, choosing the LP/IP Solver menu item presents the dialog below. These options only affect the Jensen LP/IP Solver, and do not affect the Excel Solver.

Solution Display Options

These options create a separate worksheet for algorithm details that shows iteration information from the solution algorithms. The reports are useful for the student who is learning about the solution methods used. They may also be useful for practitioners trying to discover why certain IP models are so hard to solve.

Simplex Iterations

This option creates a new worksheet with the suffix Details. Information about the iterations of the primal simplex is printed on this worksheet. The number field to the left on the dialog holds the number of iterations to be displayed. Since some problems may require thousands of iterations, this number should be set to a reasonable value or the memory requirement for Excel will be excessive.

The figure below shows the detail worksheet for the Production problem described earlier. The display shows the slack variables added for the four constraints. No artificial variables are required. Five simplex iterations are necessary to find the optimum solution. The display shows details about the iterations.

Enumeration Tree

When the production variables are required to be integer, the LP/IP add-in can be used to show the details of the enumeration process. Using the LP/IP Solver dialog we click the Show Enumeration Tree checkbox. The number field to the left on the dialog is the number of enumeration tree vertices to be displayed. We have also checked the Show Incumbents checkbox.

While the problem is solved a record is kept of the enumeration process and displayed on the Details worksheet. The production problem with integer variables requires an enumeration tree with 42 nodes.

Clicking both display checkboxes will show both the enumeration tree and the corresponding steps of the simplex method used by the bounding procedure.

The solution of the problem is below. Cell F4 shows the profit associated with the best solution found (the final Incumbent). Cell F5 shows the upper bound on the profit. In this case, the solution is optimum and the upper bound has the same value as the incumbent.

Below the model we show the incumbents discovered during the procedure. The first feasible solution was found at node 7 of the enumeration tree. The second, and final, feasible solution was found at node 35. It is often useful to view the incumbents in this manner. Integer and mixed-integer problems sometimes have many similar solutions and viewing the incumbents may show this.

Algorithm Control Options

Initial Variable Values

Two different starting strategies are available. The first option starts with all variable values equal to 0. The second strategy gathers the initial variable values from the values shown on the worksheet. The algorithm starts with these values. This advanced start option reduces the number of iterations required when only slight modifications are made to the model. When the model is an IP or MIP and the initial solution is feasible, the solution add-in uses this solution as the initial incumbent. A good initial solution often reduces the size of the enumeration tree and the time required to solve the problem. When the example uses the optimal solution for the initial solution, the enumeration tree has only 16 nodes. The tree is shown below.

MIP Tolerance

When solving integer or mixed integer programming problems, vertices of the enumeration tree are fathomed when the relaxed solution objective is less than (for a maximization problem) than the incumbent solution. A nonzero tolerance makes the fathoming test a little easier by fathoming the vertex if its relaxed objective is within x% of the incumbent solution, where x is the number entered in this field. The solution may be found with fewer iterations and less time when this value is greater than 0. When the tolerance is other than 0, however, there is no guarantee that the optimum solution is obtained. It is guaranteed that the solution is with x% of the optimum. The Excel Solver has a similar tolerance specified in the Options dialog of the Solver.

In the dialog below we specify a 1% tolerance level.

Clicking the Solve button provides the following solution. The solution returned is not optimum. Rather the solution has the profit of 2976. The optimum has the profit of 2984. The upper bound returned in cell F5 is 2988. One of the primary features of the solution procedure is that it returns both lower and upper bounds on the solution value. Although the selection of 1% in for the example does not result in a guaranteed optimum, we are guaranteed that the solution is 1% of the optimum. The objective for the incumbent and the Upper Bound value provides a range in which the optimum value must reside.

The advantage of choosing a nonzero tolerance is that the size of the tree is significantly reduced. For the example the tree is reduced from 42 to 14 nodes. For larger problems, the reduction will often be a much greater proportion.

Time Limit

When solving all integer or mixed integer programming problems, the process may take a long time. The program will stop when this time limit is reached. The user may give up at this point or continue the optimization. The Excel Solver has a similar time limit specified in the Options dialog of the Solver.

Show Incumbents

When solving all integer or mixed integer programming problems, the algorithm may find feasible solutions during the enumeration process. During the process, the feasible solution with the best value is called the incumbent solution. When the process is complete, the final incumbent is placed on the worksheet as the solution. When this checkbox is selected, all incumbents discovered are shown below the model. This is illustrated in a figure above.

Operations Research Models and Methods
Internet
by Paul A. Jensen