Chapter 7 – Integer Linear Programming
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.
47. 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 7 – Integer Linear Programming
48. 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.
Min
s.t.
Applications of integer linear programming
49. 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
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
Distribution system design
Chapter 7 – Integer Linear Programming
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.
Applications of integer programming
50. 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
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.
Chapter 7 – Integer Linear Programming
51. 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.
part (c) solution
Applications of integer programming
Chapter 7 – Integer Linear Programming
52. 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 7 – Integer Linear Programming
53. 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 7 – Integer Linear Programming
54. 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.
Capital budgeting
Product design and market share optimization
Chapter 7 – Integer Linear Programming
55. 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.
56. 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;
(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?
Chapter 7 – Integer Linear Programming
57.
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?
58. The use of integer variables creates additional restrictions but provides additional flexibility. Explain.
59. Why are 0 – 1 variables sometimes called logical variables?
60. 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
61. 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.
Chapter 7 – Integer Linear Programming
62. Explain how integer and 0-1 variables can be used in a constraint to enable production.
63. List and explain four types of constraints involving 0-1 integer variables only.