How the Solver Handles Constraints

[Dividing Line Image]

Constraints are fundamental to a Solver model. A constraint specifies an upper or lower limit, or an exact value that a calculated function of the decision variables must satisfy at any solution found by the Solver. This page provides more insight into the details of how the Solver handles constraints, which can help you select the most efficient forms of constraints, and determine when the Solver's limits on the number of constraints may be exceeded.

Form and Meaning of Constraints

As noted in Elements of Solver Models, constraints are relations such as A1 >= 0. A constraint is satisfied if the condition it specifies is true within a small tolerance, specified by the Precision setting in the Solver Options dialog. This is a little different from a logical formula such as =A1>=0 evaluating to TRUE or FALSE which you might enter in a cell. In this example, if A1 were -0.0000001, the logical formula would evaluate to FALSE, but with the default Precision setting, the constraint would be satisfied. Because of the numerical methods used to find solutions to Solver models and the finite precision of computer arithmetic, it would be unrealistic to require that constraints like A1 >= 0 be satisfied exactly -- such solutions would rarely be found.

Another type of constraint is of the form A1 = integer, where A1 is one of the decision variables. This specifies that the solution value for A1 must be an integer or whole number such as -1, 0 or 1 to within a small tolerance (also the Precision setting). The presence of even one such integer constraint in a Solver model makes the problem an integer programming problem, which may be much more difficult to solve than the equivalent problem without the integer constraint (See Algorithmic methods used by the Solver).

Constraint Left and Right Hand Sides

In our spreadsheet Solvers, constraints are specified by giving a cell reference such as A1 or A1:A10 (the "left hand side"), a relation (<=, = or >=), and an expression for the "right hand side." Although Excel and 1-2-3 allow you to enter any numeric expression on the right hand side, we strongly encourage you to use only constants, or references to cells which contain constant values on the right hand side. (A constant value to the Solver is any value which does not depend on any of the decision variables.) Using constant right hand sides in constraints will simplify your model, and is essential to obtain the benefits of fast problem setup in the enhanced solvers.

The constraint left hand side, entered in the Cell Reference edit box of the Add Constraint or Change Constraint dialog, may be any individual selection, such as a column, row, or rectangular area of cells. Multiple selections are not permitted here.

The constraint right hand side may be any of the following:

A numeric constant such as 1.
A cell reference such as C1.
An (individual) selection such as C1:C5.
An arbitrary formula such as C1+1 or C2/D2.

Defined names may be used in lieu of cell references or cell ranges, and this practice is recommended to make your model more readable and maintainable. See Hints for Building Readable, Manageable Models for more suggestions.

If you use option 3, a selection of more than one cell, the number of cells selected must match the number of cells you selected for the constraint left hand side. The two selections need not have the same "shape:" For example, the left hand side could be a column and the right hand side a row. You may also use rectangular areas of cells. In any case, when you use this form you are specifying several constraints at once, and the constraint left hand sides correspond element-by-element to the right hand sides. In the previous chapter, for example, you could have entered the right hand side values 400, 200, 800, 400 and 600 into cells C1 to C5, and entered a single constraint such as B1:B5 <= C1:C5. You can see examples of this form in nearly all of our sample worksheets. It is by far the most useful form.

If the constraint right hand side is a cell reference, cell selection or formula, the Solver needs to know whether the contents of those cells, or the value of the formula is constant in the problem, or variable (i.e. dependent on the values of the decision variables). If the right hand side depends on any of the decision variables, the Solver transforms a constraint such as "LHS >= RHS" into "LHS - RHS >= 0" internally. Both the linear and nonlinear Solvers work internally with constant bounds on the constraint functions.

Efficiency of Constraint Forms

The Solver recognizes the case where the constraint left hand side is a decision variable, or a set of decision variables. As long as the corresponding right hand sides are constant (i.e. not dependent on any of the variables), these constraints are specially treated as bounds on the variables. In the solution process, such bounds require considerably less time to satisfy than the more general constraint forms. The most common instance of a bound on a variable is a non-negativity constraint such as A1 >= 0, but any sort of constant bounds are efficiently handled by both the linear and nonlinear Solvers.

There is no difference in terms of efficiency between a constraint entered (for example) as A1 <= 100 or as A1 <= B1 where B1 contains 100; the Solver recognizes that B1 is equivalent to a constant. The form A1 <= B1 is usually better from the standpoint of maintainability of your optimization model. Similarly, there is no difference in efficiency if you use defined names instead of cell references, so this practice is recommended.

On the other hand, a constraint right hand side which is a formula -- even a simple one like 2+2 -- will incrementally increase the solution time for the model. Because the Solver doesn't have the facilities to recognize the right hand side "on the fly," it treats any formula as a RHS potentially dependent on the variables, and internally creates a constraint "LHS - RHS >= 0" -- even if the formula really was a constant bound on a variable. It is better to place whatever formula you need into a cell, and reference that cell as the constraint right hand side: Because the formula has already been analyzed by the spreadsheet program when it was entered in the cell, the Solver can determine whether it is dependent on the variables.

Constraints and Fast Problem Setup

You can use any spreadsheet formula, operator or function to compute the values in the left hand sides of constraints -- whether your problem is linear or nonlinear. However, if your problem is linear and involves a significant number of decision variables and/or constraints, it pays to use certain common functions to express the left hand sides -- both for the sake of keeping your model readable and manageable, and to obtain the benefit of fast problem setup offered by Frontline's enhanced solvers. As discussed in Linear and Nonlinear Functions, any linear function can be written in the form of a single call to the SUMPRODUCT function -- or, if the cells you are referencing are scattered around the worksheet, Frontline's add-in DOTPRODUCT function. In many simple cases you can use the SUM function, which is equivalent to SUMPRODUCT where one of the two arguments consists of all 1's. If you organize and lay out your model's parameters in columns and rows and you consistently use these simple functions, you will gain many benefits down the road.

Limits on the Number of Constraints

The standard spreadsheet Solvers have a limit of 200 decision variables or changing cells. They also impose a limit on the number of constraints in certain situations. Here are the details: If the problem is linear -- and you have checked the Assume Linear Model box in the Solver Options dialog -- then there is no limit on the number of constraints. If the problem is nonlinear, there is a limit of 100 constraints other than constant bounds on the variables and integer constraints. So, for example, if A1 is a decision variable, you could specify A1 >= 0, A1 <= 1 and A1 = integer without using up any of the 100 constraints. On the other hand, a constraint such as A1 = 2+2 would count against the limit of 100 constraints, because the Solver treats the right hand side as a formula (even though it is actually a constant value) as noted earlier.

Note that while there is no limit on the number of constraints in a linear problem, in practice it is unusual to have more constraints than decision variables (though you may have both upper and lower bounds on some constraint cells). This is because a problem with more constraints than variables is an overdetermined linear system, and some of the constraints must be redundant (i.e. always satisfied when the other constraints are satisfied).

If your problem exceeds the limits on the number of decision variables and constraints allowed by the standard spreadsheet Solvers, it is likely that one of Frontline's enhanced solvers will be able to handle the problem. Even if your problem doesn't exceed these limits, you may find that the standard Solver takes a long time to find the solution; in this case you may find the enhanced solvers worthwhile, since they can be many times faster than the standard Solver.