Operations Research Models and Methods / Computation / Mathematical Programming

LP/IP Solver

The LP/IP Solver add-in provides an algorithm that solves Linear Programming problems. It can be used instead of the Excel solver for the linear programming models created by the Mathematical Programming add-in. It works also works when some or all of the variables are required to be integer. When it is installed, a new item appears on the OR_MM menu, LP/IP Solver. Subroutines provided by the algorithm are called when the user clicks on the Solve button on the linear, integer, or mixed integer model sheets.

Choosing the LP/IP Solver menu item presents the dialog shown below. These options only affect the Jensen LP/IP Solver, and do not affect the Excel Solver.

Solution Display Options

These options print information on the problem worksheet, on a separate worksheet, or displayed through a message box. They are useful for debugging algorithms, learning the principles of the algorithms, and sensitivity analysis.

  • Simplex Iterations: This option creates a new worksheet with the suffix _Details. Detailed information showing the iterations of the primal simplex are printed on this worksheet. The number field to the right is the number of iterations shown. 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.
  • Enumeration Tree: This option displays on the Details worksheet information about the branch and bound tree for integer problems. The number field to the right is the number of branch and bound nodes shown.

Algorithm Control Options

Initial Variable Values

Two different starting strategies are available. The first option starts with all varaibles equal to zero. The second strategy gathers the initial flows from the values shown on the worksheet.. The algorithm starts with these values. The advanced start option is useful when only slight modifications are made to the network model.

MIP Tolerance

When solving all integer or mixed integer programming problems nodes of the branch and bound tree are fathomed when the relaxed solution objective is less than (for a maximization problem) than the incumbent solution. This tolerance makes the fathoming test a little easier by fathoming the nodes is within x% of the encumbent 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, but it is a 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.

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.

 

 



Updated 1/16/01
Operations Research Models and Methods

by Paul A. Jensen and Jon Bard, University of Texas, Copyright by the Authors