Chapter 7
Integer Programming: Logical Constraints
In the previous chapter, we covered how to solve integer programming problems using Solver. We also introduced the use of binary variables, which represent yes/no decisions, and we saw how binary variables arise naturally in set covering, set packing, and set partitioning. In this chapter, we expand the use of binary variables in connection with relationships we call logical constraints that restrict consideration to certain combinations of variables. Normally, we might not immediately think of these restrictions as linear constraints, but we can capture them in linear form with the use of binary variables.
We begin with the illustration of a counting constraint. This term refers to a quantitative constraint for counting our decisions, and the use of binary variables makes counting easy. As an example, we revisit the capital budgeting problem which, in its basic form, is a pure integer program containing binary variables and one constraint. We encountered this structure in Example 6.2, in the Newton Corporation.
EXAMPLE 7.1 The Newton Corporation
The Newton Corporation has tentatively allocated $40 million for capital investments after considering the financial characteristics of the following projects.
P1 Renovate the production facility for greater efficiency.
P2 License a new technology for use in production.
P3 Expand advertising by naming a stadium.
P4 Purchase land and construct a new headquarters building.
P5 Introduce ...
