QUANTITATIVE METHODS

CHAPTER 7
Integer Linear Programming

One or more variables must be integer. If all variables must be integer, we have an all-integer
linear program. If some, but not all, variables must be integer, we have a mixed-integer linear
program. In many applications of integer linear programming, one or more integer variables
are required to equal either 0 or 1. Such variables are called 0-1 or binary variables. If all
variables are 0-1 variables, we have a 0-1 integer linear program.

The linear program that results from dropping the integer requirements is called the LP
Relaxation of the integer linear program.

Rounding to an integer solution is a trial-and-error approach. Each rounded solution must be

For integer linear programs involving maximization, the value of the optimal solution to the LP
Relaxation provides an upper bound on the value of the optimal integer solution. For integer
linear programs involving minimization, the value of the optimal solution to the LP Relaxation
provides a lower bound on the value of the optimal integer solution.

1. Applications involving 0-1 Variables

Capital Budgeting

In a capital budgeting problem, the company’s objective function is to maximize the net
present value of the capital budgeting projects.

1
Fixed Cost

(read previous problem without fixed cost from the book)

2
Distribution Systems Design

The Martin-Beck Company operates a plant in St. Louis with an annual capacity of 30,000 units.
Product is shipped to regional distribution centers located in Boston, Atlanta, and Houston.
Because of an anticipated increase in demand, Martin-Beck plans to increase capacity by
constructing a new plant in one or more of the following cities: Detroit, Toledo, Denver, or
Kansas City. The estimated annual fixed cost and the annual capacity for the four proposed
plants are as follows:

3
4
Using the special properties of 0-1 variables, the model can also be expanded to accommodate
a variety of configuration constraints on the plant locations. For example, suppose in another
problem, site 1 were in Dallas and site 2 were in Fort Worth. A company might not want to
locate plants in both Dallas and Fort Worth because the cities are so close together. To prevent
this result from happening, the following constraint can be added to the model:

Constraint allows either y1 or y2 to equal 1, but not both. If we had written the constraints as
an equality, it would require that a plant be located in either Dallas or Fort Worth.

Bank Location (IMPORTANTE) – Location Problem

The long-range planning department for the Ohio Trust Company is considering expanding its
operation into a 20-county region in northeastern Ohio. Currently, Ohio Trust does not have a
principal place of business in any of the 20 counties. According to the banking laws in Ohio, if a
bank establishes a principal place of business (PPB) in any county, branch banks can be
established in that county and in any adjacent county. However, to establish a new principal
place of business, Ohio Trust must either obtain approval for a new bank from the state’s
superintendent of banks or purchase an existing bank.

5
6
Ohio Trust would like to determine the minimum number of PPBs necessary to do business
throughout the 20-county region. A 0-1 integer programming model can be used to solve this
location problem for Ohio Trust.

See computer output

Product Design and Market Share Optimization

Salem Foods is planning to enter the frozen pizza market. Currently, two existing brands,
Antonio’s and King’s, have the major share of the market. In trying to develop a sausage pizza
that will capture a significant share of the market, Salem determined that the four most
important attributes when consumers purchase a frozen sausage pizza are crust, cheese,
sauce, and sausage flavor. The crust attribute has two levels (thin and thick); the cheese
attribute has two levels (mozzarella and blend); the sauce attribute has two levels (smooth and
chunky); and the sausage flavor attribute has three levels (mild, medium, and hot). In a typical
conjoint analysis, a sample of consumers is asked to express their preference for specially
prepared pizzas with chosen levels for the attributes. Then regression analysis is used to
determine the part-worth for each of the attribute levels. In essence, the part-worth is the
utility value that a consumer attaches to each level of each attribute. A discussion of how to
use regression analysis to compute the part-worth is beyond the scope of this text, but we will
show how the part-worth can be used to determine the overall value a consumer attaches to a
particular pizza.

7
The part-worths (preferences) can be used to determine the overall value (utility) each
consumer attaches to a particular type of pizza. Salem must design a pizza (choose the type of
crust, cheese, sauce, and sausage flavor) that will have the highest utility for enough people to
ensure sufficient sales to justify making the product.

8
 MULTIPLE CHOICE

1. Which of the following is the most useful contribution of integer programming?

a. finding whole number solutions where fractional solutions would not be appropriate

b. using 0-1 variables for modeling flexibility

c. increased ease of solution

d. provision for solution procedures for transportation and assignment problems

2. In a model, x1 ≥ 0 and integer, x2 ≥ 0, and x3 = 0, 1. Which solution would not be feasible?

a. x1 = 5, x2 = 3, x3 = 0

b. x1 = 4, x2 = .389, x3 = 1

c. x1 = 2, x2 = 3, x3 = .578

d. x1 = 0, x2 = 8, x3 = 0

3. Rounded solutions to linear programs must be evaluated for

a. feasibility and optimality.

b. sensitivity and duality.

c. relaxation and boundedness.

d. each of the above is true.

9
4. Rounding the solution of an LP Relaxation to the nearest integer values provides

a. a feasible but not necessarily optimal integer solution.

b. an integer solution that is optimal.

c. an integer solution that might be neither feasible nor optimal.

d. an infeasible solution.

5. The solution to the LP Relaxation of a maximization integer linear program provides

a. an upper bound for the value of the objective function.

b. a lower bound for the value of the objective function.

c. an upper bound for the value of the decision variables.

d. a lower bound for the value of the decision variables.

6. The graph of a problem that requires x1 and x2 to be integer has a feasible region

a. the same as its LP relaxation.

b. of dots.

c. of horizontal stripes.

d. of vertical stripes.

7. The 0-1 variables in the fixed cost models correspond to

a. a process for which a fixed cost occurs.

b. the number of products produced.

c. the number of units produced.

d. the actual value of the fixed cost.

8. Sensitivity analysis for integer linear programming

a. can be provided only by computer.

b. has precisely the same interpretation as that from linear programming.

c. does not have the same interpretation and should be disregarded.

d. is most useful for 0-1 models.

10
9. Let x1 and x2 be 0-1 variables whose values indicate whether projects 1 and 2 are not done
or are done. Which answer below indicates that project 2 can be done only if project 1 is
done?

a. x1 + x2 = 1

b. x1 + x2 = 2

c. x1 − x2 ≤ 0

d. x1 − x2 ≥ 0

10. Let x1 , x2 , and x3 be 0-1 variables whose values indicate whether the projects are not
done (0) or are done (1). Which answer below indicates that at least two of the projects must
be done?

a. x1 + x2 + x3 ≥ 2

b. x1 + x2 + x3 ≤ 2

c. x1 + x2 + x3 = 2

d. x1 − x2 = 0

11. If the acceptance of project A is conditional on the acceptance of project B, and vice versa,
the appropriate constraint to use is a

a. multiple-choice constraint.

b. k out of n alternatives constraint.

c. mutually exclusive constraint.

d. corequisite constraint.

12. In an all-integer linear program,

a. all objective function coefficients must be integer.

b. all right-hand side values must be integer.

c. all variables must be integer.

d. all objective function coefficients and right-hand side values must be integer.

13. To perform sensitivity analysis involving an integer linear program, it is recommended to

a. use the dual prices very cautiously.

b. make multiple computer runs.

c. use the same approach as you would for a linear program.

11
d. use LP relaxation.

14. Modeling a fixed cost problem as an integer linear program requires

a. adding the fixed costs to the corresponding variable costs in the objective function.

b. using 0-1 variables.

c. using multiple-choice constraints.

d. using LP relaxation.

15. Most practical applications of integer linear programming involve

a. only 0-1 integer variables and not ordinary integer variables.

b. mostly ordinary integer variables and a small number of 0-1 integer variables.

c. only ordinary integer variables.

d. a near equal number of ordinary integer variables and 0-1 integer variables.

1. The LP Relaxation contains the objective function and constraints of the IP problem, but
drops all integer restrictions. TRUE

2. In general, rounding large values of decision variables to the nearest integer value causes
fewer problems than rounding small values. TRUE

3. The solution to the LP Relaxation of a minimization problem will always be less than or equal
to the value of the integer program minimization problem. FALSE

4. If the optimal solution to the LP relaxation problem is integer, it is the optimal solution to
the integer linear program. TRUE

5. Slack and surplus variables are not useful in integer linear programs. FALSE

6. A multiple choice constraint involves selecting k out of n alternatives, where k ≥ 2. FALSE

7. In a model involving fixed costs, the 0-1 variable guarantees that the capacity is not
available unless the cost has been incurred. TRUE

8. If x1 + x2 ≤ 500y1 and y1 is 0-1, then if y1 is 0, x1 and x2 will be 0. TRUE

9. The constraint x1 + x2 + x3 + x4 ≤ 2 means that two out of the first four projects must be
selected. FALSE

10. The constraint x1 − x2 = 0 implies that if project 1 is selected, project 2 cannot be. FALSE

11. The product design and market share optimization problem presented in the textbook is
formulated as a 0-1 integer linear programming model. TRUE

12. The objective of the product design and market share optimization problem presented in
the textbook is to choose the levels of each product attribute that will maximize the number of
sampled customers preferring the brand in question. TRUE

12
13. If a problem has only less-than-or-equal-to constraints with positive coefficients for the
variables, rounding down will always provide a feasible integer solution. TRUE

14. Dual prices cannot be used for integer programming sensitivity analysis because they are
designed for linear programs. TRUE

15. Some linear programming problems have a special structure which guarantees that the
variables will have integer values. TRUE

13