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.

Fast Problem Setup

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