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 ...

Get Optimization Modeling with Spreadsheets, Second Edition now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.