The Problem

A builder is planning to construct new buildings at four local sites designated 1, 2, 3 and 4. At each site there are three possible building designs labeled A, B and C. There is also the option of not using a site. The problem is to select the building locations and accompanying designs. Preliminary studies have determined the required investment and net annual income for each of the 12 options. These are shown in the table below, with A1, for example, denoting design A at site 1. The company has an investment budget of $100M. The goal is to maximize total annual income without exceeding the investment budget. As the OR analyst, you are given the job of finding the optimum plan.

This example introduces one of the major differences between linear and integer programming; the indivisibility of decisions. It is an obvious requirement here that only whole buildings may be built and only whole designs may be selected.

Linear/Integer Programming Model

To begin creating a model, variables must be defined to represent each decision. In many cases models can be more succinctly stated using algebraic expressions with subscripted variables. In this section, we use variable names like A1, A2, … C3, and C4 to represent the decisions. This makes it easier to present the model in a browser readable format. The notation is also similar to that used for the computer model. We will write several models in this section, but the simplest is:

Objective: Max. z = 6*A1 + 7*A2 + 9*A3 ... + 19*C3 + 20*C4

subject to:

Budget: 13*A1 + 20*A2 + 24*A3 ... + 48*C3 + 55*C4 100

Simple Bounds and Integrality

0 A1 1, 0 A2 1, ... , 0 C4 1 and integer

We use * to indicate multiplication and ... to indicate a continuation in a similar fashion.

Note that since the variables are restricted between 0 and 1 and required to be integer, there are actually only two feasible values, 0 and 1 for each variable. A design/location combination either adds its contributions to the net income and budget (=1) or does not (=0). The simple phrase "and integer" specifies that all the variables must be integer Thus the model describes the problem of selecting the set of design/location combinations that maximize net income, while not exceeding the budget constraint.

The model has the linear form required for linear programming, but it is not a linear programming model because the variables are not allowed to assume all values within a continuum. Often the phrase Integer Programming is used for the linear model with some or all the variables required to be integer, leaving out the term linear. Although one can express models that are integer and nonlinear, these are generally much more difficult to solve. For a nonlinear-integer model we use the phrase nonlinear-integer program. We only consider (linear) integer programming models in this section.