Solver Tutorial - Defining Constraints

Defining Constraints

Constraints are logical conditions that a solution to an optimization problem must satisfy.  They reflect real-world limits on production capacity, market demand, available funds, and so on.  To define a constraint, you first compute the value of interest using the decision variables.  Then you place an appropriate limit (<=, = or >=) on this computed value.  The following examples illustrate a variety of types of constraints that commonly occur in optimization problems.

General Constraints

Suppose that cells A1:A5 contain the percentage of funds to be invested in each of 5 stocks. We would want the sum of these cells to equal 1 (or 100%).  To accomplish this, in cell B1 you might calculate the sum of the percentages as =SUM(A1:A5) and then use solver to define a constraint to require that cell B1 = 1.

As another example, suppose a company has an advertising budget of $50,000 for the coming month and TV and newspaper ads cost $3,000 and $500 per ad, respectively.  If cells C3 and D3 represent decision variables for, respectively, the number of TV ads purchased and the number of newspaper ads purchased we could calculate the total amount spent of advertising in, say, cell E3 as =3000*C3 + 500*D3.  We would then use solver to define a constraint requiring that E3<=50000.

Bounds on Variables

You can also place a constraint directly on a decision variable, such as A1 <= 100 or B7>=5. These types of  upper and lower bounds on the variables are handled efficiently by most optimizers and are very useful in many problems. For example, if your decision variables measure the number of products of different types that you plan to manufacture, producing a negative number of products would make no sense.  This type of non-negativity constraint is very common.  Although it may be obvious to you, non-negativity constraints such as A1 >= 0 must be communicated to the solver so that it knows that negative values are not allowed. 

Policy Constraints  

Some constraints are determined by policies that you or your organization may set.  For example, in a portfolio optimization, you might have a limit on the maximum percentage of funds to be invested in any one stock, or one industry group.

Physical Constraints  

Many constraints are determined by the physical nature of the problem.  For example, suppose you are modeling product shipments in and out of a warehouse over time.  You'll probably need a balance constraint to specify that, in each time period, the beginning inventory plus the products received minus the products shipped out equals the ending inventory. And, of course, the ending inventory in one period becomes the beginning inventory for the next period.

Integer Constraints

Optimization software also allows you to specify constraints requiring decision variables to assume only integer (whole number) values in the final solution. For example, if you are scheduling a fleet of trucks, a solution that calls for a fraction of a truck to travel a certain route would not be useful.  Integer constraints normally can be applied only to decision variables, not to quantities calculated from them.

A special type of integer constraint specifies that a variable must be binary -- either 0 or 1 -- at the final solution.  Binary variables can be used to model "yes/no" or "go/no-go" decisions and are very useful in a variety of modeling situations.  For example, you might use a 0-1 or binary integer variable to represent a decision about whether to lease a new machine.  Your model could use this binary variable to include (or exclude) the monthly fixed lease cost for the machine in the objective as well as to create a lower cost per item processed with the machine, if it is used. In this way, a solver can determine whether or not the machine should be leased. 

Some problems involve determining an optimal ordering of items.  For example, we might want to determine the optimal ordering of jobs on a machine where set-up costs on the machine vary depending on the order of the jobs.  As another example, we might want to determine the optimal order in which to deliver packages to customers throughout a city while minimizing total travel distance.  In these situations, solver offers a special type of integer constraint (known as an "alldifferent" constraint) where the values of n decision variables must be a permutation of integers from 1 to n.