Chapter 11 – Integer Linear Programming
Tulsa 350,000 9 4 3 10,000
St. Louis 200,000 12 6 2 10,000
Portland 480,000 4 10 11 10,000
Demand 3,000 8,000 9,000
Develop a model whose solution would reveal which plants to build and the optimal shipping schedule.
50. Simplon Manufacturing must decide on the processes to use to produce 1650 units. If machine 1 is used, its production
will be between 300 and 1500 units. Machine 2 and/or machine 3 can be used only if machine 1’s production is at least
1000 units. Machine 4 can be used with no restrictions.
Machine Fixed
cost Variable
cost Minimum
Production Maximum
Production
1 500 2.00 300 1500
2 800 0.50 500 1200
3 200 3.00 100 800
4 50 5.00 any any
(HINT: Use an additional 0 – 1 variable to indicate when machines 2 and 3 can be used.)
Chapter 11 – Integer Linear Programming
51. Your express package courier company is drawing up new zones for the location of drop boxes for customers. The
city has been divided into the seven zones shown below. You have targeted six possible locations for drop boxes. The list
of which drop boxes could be reached easily from each zone is listed below.
Zone Can Be Served By Locations:
Downtown Financial 1, 2, 5, 6
Downtown Legal 2, 4, 5
Retail South 1, 2, 4, 6
Retail East 3, 4, 5
Manufacturing North 1, 2, 5
Manufacturing East 3, 4
Corporate West 1, 2, 6
Let xi = 1 if drop box location i is used, 0 otherwise. Develop a model to provide the smallest number of locations yet
make sure that each zone is covered by at least two boxes.
52. Consider the problem faced by a summer camp recreation director who is trying to choose activities for a rainy day.
Information about possible choices is given in the table below.
Category
Activity Time
(minutes) Popularity
Chapter 11 – Integer Linear Programming
with Campers Popularity with
Counselors
Art 1 – Painting 30 4 2
2 – Drawing 20 5 2
3 – Nature craft 30 3 1
Music 4 – Rhythm band 20 5 5
Sports 5 – Relay races 45 2 1
6 – Basketball 60 1 3
Computer 7 – Internet 45 1 1
8 – Creative writing 30 4 3
9 – Games 40 1 2
a. Give a general definition of the variables necessary in this problem so that each activity can be considered for
inclusion in the day’s schedule.
b. The popularity ratings are defined so that 1 is the most popular. If the objective is to keep the campers happy, what
should the objective function be?
Write constraints for these restrictions:
c. At most one art activity can be done.
d. No more than two computer activities can be done.
e. If basketball is chosen, then the music must be chosen.
f. At least 120 minutes of activities must be selected.
g. No more than 165 minutes of activities may be selected.
h. To keep the staff happy, the counselor rating should be no higher than 10.
53. Tower Engineering Corporation is considering undertaking several proposed projects for the next fiscal year. The
projects, the number of engineers and the number of support personnel required for each project, and the expected profits
for each project are summarized in the following table:
Project
1 2 3 4 5 6
Engineers Required 20 55 47 38 90 63
Support Personnel Required 15 45 50 40 70 70
Profit ($1,000,000s) 1.0 1.8 2.0 1.5 3.6 2.2
Formulate an integer program that maximizes Tower’s profit subject to the following management constraints:
1) Use no more than 175 engineers
2) Use no more than 150 support personnel
3) If either project 6 or project 4 is done, both must be done
4) Project 2 can be done only if project 1 is done
Chapter 11 – Integer Linear Programming
5) If project 5 is done, project 3 must not be done and vice versa
6) No more than three projects are to be done.
54. Given the following all-integer linear program:
Max 3x1 + 2x2
s.t. 3x1 + x2 ≤ 9
x1 + 3x2 ≤ 7
−x1 + x2 ≤ 1
x1, x2 ≥ 0 and integer
a.
Solve the problem as a linear program ignoring the integer constraints. Show that the optimal solution to the linear
program gives fractional values for both x1 and x2.
b.
What is the solution obtained by rounding fractions greater than of equal to 1/2 to the next larger number? Show that
this solution is not a feasible solution.
c. What is the solution obtained by rounding down all fractions? Is it feasible?
d.
Enumerate all points in the linear programming feasible region in which both x1 and x2 are integers, and show that
the feasible solution obtained in (c) is not optimal and that in fact the optimal integer is not obtained by any form of
rounding.
Chapter 11 – Integer Linear Programming
55. Tom’s Tailoring has five idle tailors and four custom garments to make. The estimated time (in hours) it would take
each tailor to make each garment is listed below. (An ‘X’ in the table indicates an unacceptable tailor-garment
assignment.)
Tailor
Garment 1 2 3 4 5
Wedding gown 19 23 20 21 18
Clown costume 11 14 X 12 10
Admiral’s uniform 12 8 11 X 9
Bullfighter’s outfit X 20 20 18 21
Formulate and solve an integer program for determining the tailor-garment assignments that minimize the total estimated
time spent making the four garments. No tailor is to be assigned more than one garment and each garment is to be worked
on by only one tailor.
Chapter 11 – Integer Linear Programming
56. Market Pulse Research has conducted a study for Lucas Furniture on some designs for a new commercial office desk.
Three attributes were found to be most influential in determining which desk is most desirable: number of file drawers,
the presence or absence of pullout writing boards, and simulated wood or solid color finish. Listed below are the part-
worths for each level of each attribute provided by a sample of 7 potential Lucas customers.
File Drawers Pullout Writing Boards Finish
Consumer 0 1 2 Present Absent Simul. Wood Solid Color
1 5 26 20 18 11 17 10
2 18 11 5 12 16 15 26
3 4 16 22 7 13 11 19
4 12 8 4 18 9 22 14
5 19 9 3 4 14 30 19
6 6 15 21 8 17 20 11
7 9 6 3 13 5 16 28
Suppose the overall utility (sum of part-worths) of the current favorite commercial office desk is 50 for each customer.
What is the product design that will maximize the share of choices for the seven sample participants? Formulate and
solve, using Lindo or Excel, this 0 – 1 integer programming problem.
Chapter 11 – Integer Linear Programming
57. Kloos Industries has projected the availability of capital over each of the next three years to be $850,000, $1,000,000,
and $1,200,000, respectively. It is considering four options for the disposition of the capital:
(1) Research and development of a promising new product
(2) Plant expansion
(3) Modernization of its current facilities
(4) Investment in a valuable piece of nearby real estate
Monies not invested in these projects in a given year will NOT be available for following year’s investment in the projects.
The expected benefits three years hence from each of the four projects and the yearly capital outlays of the four options
are summarized in the table below in $1,000,000’s.
In addition, Kloos has decided to undertake exactly two of the projects, and if plant expansion is selected, it will also
modernize its current facilities.
Capital Outlay
Options Year 1 Year 2 Year 3 Projected Benefits
New Product R&D .35 .55 .75 5.2
Plant Expansion .50 .50 0 3.6
Modernization .35 .40 .45 3.2
Real Estate .50 0 0 2.8
Formulate and solve this problem as a binary programming problem.
Chapter 11 – Integer Linear Programming
58. Given the following all-integer linear program:
Max 15x1 + 2x2
s. t. 7x1 + x2 < 23
3x1 – x2 < 5
x1, x2 > 0 and integer
a. Solve the problem as an LP, ignoring the integer constraints.
b. What solution is obtained by rounding up fractions greater than or equal to 1/2? Is this the optimal integer solution?
c. What solution is obtained by rounding down all fractions? Is this the optimal integer solution? Explain.
d. Show that the optimal objective function value for the ILP is lower than that for the optimal LP.
e. Why is the optimal objective function value for the ILP problem always less than or equal to the corresponding LP’s
optimal objective function value? When would they be equal? Comment on the MILP’s optimal objective function
compared to the corresponding LP & ILP.
59. A business manager for a grain distributor is asked to decide how many containers of each of two grains to purchase to
fill its 1,600 pound capacity warehouse. The table below summarizes the container size, availability, and expected profit
per container upon distribution.
Grain Container
Size Containers
Available Container
Profit
A 500 lbs. 3 $1,200
B 600 lbs. 2 $1,500
a. Formulate as a linear program with the decision variables representing the number of containers purchased of each
grain. Solve for the optimal solution.
b. What would be the optimal solution if you were not allowed to purchase fractional containers?
c. There are three possible results from rounding an LP solution to obtain an integer solution:
(1) the rounded optimal LP solution will be the optimal IP solution;
(2) the rounded optimal LP solution gives a feasible, but not optimal IP solution;
Chapter 11 – Integer Linear Programming
(3) the rounded optimal LP solution is an infeasible IP solution.
For this problem (i) round down all fractions; (ii) round up all fractions; (iii) round off (to the nearest integer) all fractions
(NOTE: Two of these are equivalent.) Which result above (1, 2, or 3) occurred under each rounding method?
60. Given the following all-integer linear programming problem:
Max 3x1 + 10x2
s. t. 2x1 + x2 < 5
x1 + 6x2 < 9
x1 – x2 > 2
x1, x2 > 0 and integer
a. Solve the problem graphically as a linear program.
b. Show that there is only one integer point and it is optimal.
c. Suppose the third constraint was changed to x1 – x2 > 2.1. What is the new optimal solution to the LP? ILP?
Essay
61. The use of integer variables creates additional restrictions but provides additional flexibility. Explain.
62. Why are 0 – 1 variables sometimes called logical variables?
63. Give a verbal interpretation of each of these constraints in the context of a capital budgeting problem.
a. x1 − x2 ≥ 0
b. x1 − x2 = 0
c. x1 + x2 + x3 ≤ 2
Chapter 11 – Integer Linear Programming
64. Explain how integer and 0-1 variables can be used in an objective function to minimize the sum of fixed and variable
costs for production on two machines.
65. Explain how integer and 0-1 variables can be used in a constraint to enable production.
66. List and explain four types of constraints involving 0-1 integer variables only.