Methods for Integer Problems
Problems with integer constraints can be extremely
difficult and time-consuming to solve. There are problems with only
a few hundred integer constraints which have never been solved, even
with custom programs running on the fastest parallel supercomputers
-- let alone in Microsoft Excel! Unfortunately it is difficult to
know in advance whether a given problem will be solved easily, or
will take a great deal of time. A different formulation of the same
underlying problem may require 100 to 1000 times more or less
solution time in some cases.
Bear in mind that the Branch and Bound method
solves a large number of subproblems, each one an instance of the
problem on your worksheet without the integer constraints. Thus,
efforts to reduce solution time on the subproblems, through the
measures described above, will pay off many times over in an integer
problem. If the problem involves many variables and constraints, the
subproblems must for practical purposes be linear if you are to have
a realistic chance of finding an optimal or near-optimal solution.
Adding or tightening constraints can be quite effective in reducing
solution time on integer problems. And of course, it pays to
eliminate non-essential calculations from the worksheet containing
the Solver model.
The Tolerance option in the Solver Options dialog
allows you to specify a tolerance within which an integer solution
(one where the variables with integer constraints do have integer
values) will be considered "good enough," allowing the
Solver to stop and report its best solution so far. The default
value for this Tolerance is 0.05, which will allow the Solver to
stop when the objective function value is within 5% of the true
integer optimal objective. Since the Branch and Bound process can
take a great deal of time try to "close the gap"
represented by the Tolerance setting, it is often a good idea to
increase this value for a difficult integer problem.
If you have a linear or quadratic problem
(possibly with integer constraints) where you can see that much of
the total solution time is spent with "Setting Up
Problem..." on the Excel message bar, there is a good chance
that Frontline's Premium Solver products can be used to greatly reduce your
solution time. To gain this benefit, you'll need to write your
objective and constraint formulas using certain functions such as
SUM, SUMPRODUCT, and Frontline's add-in DOTPRODUCT and QUADPRODUCT
functions. For problems with hundreds of decision variables or more,
fast problem setup can be 10 times or even 100 times faster. For
more information on fast problem setup, consult the Premium
Solver Platform User Guide, or request access to the fast
Problem Setup example in our "protected" support area for
Excel Solver products.
Back to Methods for Nonlinear Problems
Back to Improving Slow Solution Times
Back to Standard Excel Solver
Support Information
