Integer Linear Programming: Multiple Choice
Integer Linear Programming: Multiple Choice
Integer Linear Programming: Multiple Choice
MULTIPLE CHOICE
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
ANSWER: c
TOPIC: Introduction
1
2 Chapter 7 Integer Linear Programming
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.
ANSWER: b
TOPIC: Graphical solution
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 + x 2 = 1
b. x1 + x 2 = 2
c. x1 - x 2 < 0
d. x1 - x 2 > 0
ANSWER: d
TOPIC: Conditional and corequisite constraints
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 + x 2 + x 3 > 2
b. x1 + x 2 + x 3 < 2
c. x1 + x 2 + x 3 = 2
d. x1 - x 2 = 0
ANSWER: a
TOPIC: k out of n alternatives constraints
Chapter 7 Integer Linear Programming 3
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.
ANSWER: d
TOPIC: Modeling flexibility provided by 0-1 integer variables
TRUE/FALSE
1. The LP Relaxation contains the objective function and constraints of the IP problem, but drops all integer
restrictions.
ANSWER: True
TOPIC: LP relaxation
2. In general, rounding large values of decision variables to the nearest integer value causes fewer problems
than rounding small values.
ANSWER: True
TOPIC: LP relaxation
4 Chapter 7 Integer Linear Programming
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.
ANSWER: False
TOPIC: Graphical solution
4. If the optimal solution to the LP relaxation problem is integer, it is the optimal solution to the integer
linear program.
ANSWER: True
TOPIC: LP relaxation
5. Slack and surplus variables are not useful in integer linear programs.
ANSWER: False
TOPIC: Capital budgeting
7. In a model involving fixed costs, the 0 - 1 variable guarantees that the capacity is not available unless the
cost has been incurred.
ANSWER: True
TOPIC: Fixed costs
10. The constraint x1 - x2 = 0 implies that if project 1 is selected, project 2 cannot be.
ANSWER: False
TOPIC: Conditional and corequisite constraints
11. The product design and market share optimization problem presented in the textbook is formulated as a
0-1 integer linear programming model.
ANSWER: True
TOPIC: Product design and market share optimization problem
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.
ANSWER: True
TOPIC: Product design and market share optimization problem
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.
ANSWER: True
TOPIC: Rounding to obtain an integer solution
14. Dual prices cannot be used for integer programming sensitivity analysis because they are designed for
linear programs.
ANSWER: True
TOPIC: A cautionary note about sensitivity analysis
Chapter 7 Integer Linear Programming 5
15. Some linear programming problems have a special structure which guarantees that the variables will have
integer values.
ANSWER: True
TOPIC: Introduction to integer linear programming
SHORT ANSWER
1. The use of integer variables creates additional restrictions but provides additional flexibility. Explain.
TOPIC: Introduction
3. Give a verbal interpretation of each of these constraints in the context of a capital budgeting problem.
a. x1 - x 2 > 0
b. x1 - x 2 = 0
c. x1 + x 2 + x 3 < 2
TOPIC: Capital budgeting
4. 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.
TOPIC: Distribution system design
5. Explain how integer and 0-1 variables can be used in a constraint to enable production.
TOPIC: Distribution system design
PROBLEMS
Max 5X + 6Y
s.t. 17X + 8Y < 136
3X + 4Y < 36
X, Y > 0 and integer
a. Graph the constraints for this problem. Indicate all feasible solutions.
b. Find the optimal solution to the LP Relaxation. Round down to find a feasible integer solution.
Is this solution optimal?
c. Find the optimal solution.
Max X + 2Y
s.t. 6X + 8Y < 48
7X + 5Y > 35
X, Y > 0
Y integer
a. Graph the constraints for this problem. Indicate all feasible solutions.
6 Chapter 7 Integer Linear Programming
b. Find the optimal solution to the LP Relaxation. Round down to find a feasible integer solution.
Is this solution optimal?
c. Find the optimal solution.
Min 6X + 11Y
s.t. 9X + 3Y > 27
7X + 6Y > 42
4X + 8Y > 32
X, Y > 0 and integer
a. Graph the constraints for this problem. Indicate all feasible solutions.
b. Find the optimal solution to the LP Relaxation. Round up to find a feasible integer solution. Is
this solution optimal?
c. Find the optimal solution.
4. Consider a capital budgeting example with five projects from which to select. Let x i = 1 if project i is
selected, 0 if not, for i = 1,...,5. Write the appropriate constraint(s) for each condition. Conditions are
independent.
a. Choose no fewer than three projects.
b. If project 3 is chosen, project 4 must be chosen.
c. If project 1 is chosen, project 5 must not be chosen.
d. Projects cost 100, 200, 150, 75, and 300 respectively. The budget is 450.
d. No more than two of projects 1, 2, and 3 can be chosen.
TOPIC: Capital budgeting
5. Grush Consulting has five projects to consider. Each will require time in the next two quarters according
to the table below.
Revenue from each project is also shown. Develop a model whose solution would maximize revenue,
meet the time budget of 25 in the first quarter and 20 in the second quarter, and not do both projects C
and D.
6. The Westfall Company has a contract to produce 10,000 garden hoses for a large discount chain.
Westfall has four different machines that can produce this kind of hose. Because these machines are
from different manufacturers and use differing technologies, their specifications are not the same.
a. This problem requires two different kinds of decision variables. Clearly define each kind.
b. The company wants to minimize total cost. Give the objective function.
c. Give the constraints for the problem.
d. Write a constraint to ensure that if machine 4 is used, machine 1 cannot be.
7. Hansen Controls has been awarded a contract for a large number of control panels. To meet this demand,
it will use its existing plants in San Diego and Houston, and consider new plants in Tulsa, St. Louis, and
Portland. Finished control panels are to be shipped to Seattle, Denver, and Kansas City. Pertinent
information is given in the table.
Develop a model whose solution would reveal which plants to build and the optimal shipping schedule.
8. 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.
(HINT: Use an additional 0 - 1 variable to indicate when machines 2 and 3 can be used.)
9. 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
8 Chapter 7 Integer Linear Programming
locations for drop boxes. The list of which drop boxes could be reached easily from each zone is listed
below.
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.
10. 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.
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?
11. 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
Chapter 7 Integer Linear Programming 9
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:
SOLUTIONS TO PROBLEMS
1. a. The feasible region is those integer values in the space labeled feasible region.
20
15
10
Feasible
5 Region
0
0 5 10 15
b. Optimal LP relaxed occurs at X = 5.818, Y = 4.636, with Z = 56.909. Rounded down solution
occurs at X = 5, Y = 4, Z= 49.
c. Optimal solution is at X = 4, Y = 6, and Z = 56.
2. a. The feasible region consists of the portions of the horizontal lines that lie within the area labeled
F. R.
10 Chapter 7 Integer Linear Programming
10
F. R.
0
0 5 10
b. The optimal relaxed solution is at X = 1.538, Y = 4.846 where Z = 11.231. The rounded solution
is X = 1.538, Y = 4.
c. The optimal solution is at X = 2.667, Y = 4, Z = 10.667.
3. a. The feasible region is the set of integer points in the area labeled feasible region.
10
Feasible
Region
0
0 5 10
4. a. x1 + x 2 + x 3 + x 4 + x 5 > 3
b. x3 - x 4 < 0
c. x1 + x 5 < 1
d. 100x1 + 200x2 + 150x3 + 75x4 + 300x5 < 450
e. x1 + x 2 + x 3 < 2
Chapter 7 Integer Linear Programming 11
Min 350000B3 + 200000B4 + 480000B5 + 5P11 + 7P12 + 8P13 + 10P21 + 8P22 + 6P23
+ 9P31 + 4P32 + 3P33 + 12P41 + 6P42 + 2P43 + 4P51 + 10P52 + 11P53
9. Min xi
s.t. x1 + x 2 + x 5 + x 6 > 2
x2 + x 4 + x 5 > 2
x1 + x 2 + x 4 + x 6 > 2
x3 + x 4 + x 5 > 2
x1 + x 2 + x 5 > 2
12 Chapter 7 Integer Linear Programming
x3 + x 4 > 2
x1 + x 2 + x 6 > 2