Cut Generation Methods
In Version 8.0, the Premium Solver uses cut
generation methods to create new constraints, or cuts, that
reduce the size of the LP feasible region without eliminating any
potential integer solutions. Gomory cuts are generated
for all integer variables, based on the LP ending basis of the
parent problem. Knapsack cuts, also known as lifted
cover inequalities, are generated for sets of 0-1 integer
variables. Options on the Integer Options tab for the Simplex
LP Solver allow you to control the frequency of
application of these cut generation methods.
Dual Simplex Method with Bound Swapping
The Premium Solver uses the Dual Simplex
method (by default) to solve the LP subproblems created in the
Branch & Bound search, starting from the ending basis of a
parent problem. Since these subproblems are always dual
feasible, it is often possible to reach a dual optimal (and primal
feasible) solution in just a few Dual Simplex iterations. In
Version 8.0, the Premium Solver uses an advanced Dual Simplex method with
"bound-swapping" for variables that have both upper and
lower bounds (such as 0-1 integer variables), which becomes faster
as the Branch & Bound search progresses and the bounds become
tighter.
Controlling Solution Time on Integer Problems
The Premium
Solver provides new ways to control the solution time of
problems with integer constraints. You can limit the number of
subproblems explored and/or the number of integer solutions
found, as well as the maximum time in seconds. The limits you
specify can be as large as you like, whereas they have an upper
bound of 32767 in the standard Excel Solver.
If you have a known integer solution value for a
problem from a previous Solver run, you can enter it as an integer
cutoff value, which the Solver can use to speed up the solution
process on new runs, by eliminating branches whose objective must be
worse than the "cutoff" value. And you can easily solve
the relaxation of the problem (temporarily ignoring the
integer constraints) by selecting an option in the new Integer
Options dialog (pictured above), or -- even more convenient -- on a
"one-time-only" basis in the Solver Results dialog.
Back to Premium Solver Product
Overview
