FOR IMMEDIATE RELEASE

Backgrounder on Integer Constraints in Solver Models

Since Microsoft Excel 4.0 was released in 1992, the Excel Solver has allowed users to define "integer constraints" on decision variables. Integer constraints specify that the solution values of the chosen variables must be whole numbers such as 1 or 2, rather than fractional values such as 12.34.

This apparently simple feature actually opens up an enormous range of new Solver applications. But it also creates enormous new demands for computing power and speed. In fact, it is possible to define a problem with the standard Excel Solver that would require more solution time and computing speed than is available on the fastest supercomputer today.

Solver problems which include integer constraints are called "integer programming" problems. The Solver handles both integer linear and integer nonlinear problems (see the Backgrounder on Feasibility and Linearity in Solver Models), but most practical applications involve integer linear models.

The Premium Solver Plus can solve linear programming problems 3 to 5 times faster than the standard Excel Solver, which is beneficial in many applications. But much greater gains are possible on integer programming problems. Frontline Systems has a number of user-contributed models with integer constraints, where the Premium Solver Plus is more than 100 times faster than the standard Excel Solver.

Integer Constraints Express Choices and Yes-No Decisions

Integer constraints may be used when the physical resource represented by a decision variable cannot be subdivided into fractional amounts, for example when scheduling (full-time) employees, or when allocating fixed-length commercials to available time slots on radio or TV. But the most powerful and most common use of integer constraints is to express Yes-No decisions. For example, a manufacturing product mix model might include products to build and parts in inventory, but also a decision about whether to buy and use a new milling machine, which would incur extra costs but save production time.

A Yes-No decision can be represented by a decision variable such as A1, where A1 >= 0, A1 <= 1 and A1 must be a whole number. This implies that A1 must be either 1 (Yes) or 0 (No) at the solution. A1 would be called a "binary integer" or "0-1" variable. In the Excel 97 Solver and in the Premium Solver products, all three limits on a variable can be imposed in one step with a "binary integer constraint."

Resource allocation problems where binary integer constraints are often used include many types of scheduling problems; equipment purchasing, truck loading, and vehicle routing problems; and capital budgeting decisions (where a project is either fully funded, or not funded at all). The major airlines make extensive use of integer programming for route planning, flight scheduling and crew scheduling.

Integer Constraints Make a Problem Very Difficult to Solve

Integer constraints make a problem very challenging, because the Solver must explore many specific combinations of whole number values for the decision variables. The Solver begins by solving the problem without considering the integer constraints. If this yields a solution value of, say, 12.34 for a decision variable A1 which is required to be integer, the Solver then creates two new subproblems, one with an extra constraint A1 <= 12 and the other with a constraint A1 >= 13. Solving this subproblem may cause other integer variables to have fractional solution values – which means that further subproblems must be created and solved. The number of subproblems may grow exponentially.

The search methods used for integer programming problems have much in common with the methods used in artificial intelligence applications such as computer chess. An enormous number of subproblems must be considered – far too many for even the fastest computer. To find an optimal solution in a reasonable amount of time, the Solver must "prune" the ever-growing "tree" of subproblems, eliminating cases where a better solution cannot occur. For example, once a solution satisfying the integer constraints (called an "incumbent") has been found, the Solver can eliminate subproblems which would simply impose tighter constraints on a problem whose best solution is already worse than the incumbent.

Premium Solver Plus Implements Sophisticated Strategies

The Premium Solver can solve integer programming problems 5 to 10 times faster than the standard Excel Solver, thanks to improved strategies for searching the "tree" of subproblems. New in Version 3.0 are user options to provide an "incumbent" or known integer value from a previous run, and limits on the total number of subproblems and the number of unexplored subproblems that may exist at one time.

The Premium Solver Plus, which focuses on faster solution methods, excels at solving integer programming problems. Frontline has implemented several different strategies from the research literature, which are effective for problems with both general integer and binary integer constraints. As a result, the Premium Solver Plus is often 5 to 10 times faster than the Premium Solver, and 25 to 100 times (or more) faster than the standard Excel Solver.

The Premium Solver Plus provides all of the user-controlled options found in the Premium Solver V3.0, plus a number of new options which allow the user to select specific strategies such as Probing, Bounds Improvement, Optimality Fixing and Variable Reordering. User may find that specific combinations of these strategy options are more effective on their problems.

The ability to solve larger and more challenging integer programming problems helps extend the domain of use of the Premium Solver products. Increasingly, applications which once required expensive scientific and technical workstations and specialized software can now be solved on a conventional PC with Microsoft Excel. Frontline expects that this trend will continue and strengthen in the future.

For More Information Contact:

CompanyLongName
CompanyAddress
Tel: CompanyPhone
FAX: CompanyFAX
Internet: CompanyEmail

Copyright © 1997 CompanyLongName
Last modified: July 11, 2000