Chapter 7 – Integer Linear Programming
True / False
1. The LP Relaxation contains the objective function and constraints of the IP problem, but drops all integer restrictions.
a.
True
b.
False
True
2. In general, rounding large values of decision variables to the nearest integer value causes fewer problems than rounding
small values.
a.
True
b.
False
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.
a.
True
b.
False
False
Graphical solution
4. If the optimal solution to the LP relaxation problem is integer, it is the optimal solution to the integer linear program.
a.
True
b.
False
True
5. Slack and surplus variables are not useful in integer linear programs.
a.
True
b.
False
6. A multiple choice constraint involves selecting k out of n alternatives, where k ≥ 2.
a.
True
b.
False
False
Multiple choice constraint
Chapter 7 – Integer Linear Programming
7. In a model involving fixed costs, the 0 – 1 variable guarantees that the capacity is not available unless the cost has been
incurred.
a.
True
b.
False
True
8. If x1 + x2 ≤ 500y1 and y1 is 0 – 1, then if y1 is 0, x1 and x2 will be 0.
a.
True
b.
False
True
9. The constraint x1 + x2 + x3 + x4 ≤ 2 means that two out of the first four projects must be selected.
a.
True
b.
False
False
10. The constraint x1 − x2 = 0 implies that if project 1 is selected, project 2 cannot be.
a.
True
b.
False
False
11. The product design and market share optimization problem presented in the textbook is formulated as a 0-1 integer
linear programming model.
a.
True
b.
False
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.
a.
True
b.
False
True
Chapter 7 – Integer Linear Programming
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.
a.
True
b.
False
True
14. Dual prices cannot be used for integer programming sensitivity analysis because they are designed for linear
programs.
a.
True
b.
False
True
15. Some linear programming problems have a special structure that guarantees the variables will have integer values.
a.
True
b.
False
True
16. Generally, the optimal solution to an integer linear program is less sensitive to the constraint coefficients than is a
linear program.
a.
True
b.
False
False
17. The classic assignment problem can be modeled as a 0-1 integer program.
a.
True
b.
False
True
18. If Project 5 must be completed before Project 6, the constraint would be x5 − x6 ≤ 0.
a.
True
b.
False
False
19. If the LP relaxation of an integer program has a feasible solution, then the integer program has a feasible solution.
Chapter 7 – Integer Linear Programming
a.
True
b.
False
False
Rounding to obtain an integer solution
20. Multiple choice constraints involve binary variables.
a.
True
b.
False
True
Multiple choice and mutually exclusive constraints
21. Most practical applications of integer linear programming involve only 0 -1 integer variables.
a.
True
b.
False
True
0 – 1 integer variables
22. Integer linear programs are harder to solve than linear programs.
a.
True
b.
False
True
Introduction
Multiple Choice
23. 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
Introduction
24. 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
c
Chapter 7 – Integer Linear Programming
25. Rounded solutions to linear programs must be evaluated for
a.
feasibility and optimality.
b.
sensitivity and duality.
c.
relaxation and boundedness.
d.
each of these choices are true.
26. 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.
Graphical solution
27. 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
Graphical solution
28. 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.
Graphical solution
29. 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.
Chapter 7 – Integer Linear Programming
Fixed costs
30. 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.
Sensitivity analysis
31. 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
Conditional and corequisite constraints
32. 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
k out of n alternatives constraint
33. 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.
Modeling flexibility provided by 0-1 integer variables
Chapter 7 – Integer Linear Programming
34. 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.
Types of integer linear programming models
35. 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.
d.
use LP relaxation.
A cautionary note about sensitivity analysis
36. 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.
Applications involving 0-1 variables
37. 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.
Applications involving 0-1 variables
38. Assuming W1, W2 and W3 are 0 -1 integer variables, the constraint W1 + W2 + W3 < 1 is often called a
a.
multiple-choice constraint.
b.
mutually exclusive constraint.
c.
k out of n alternatives constraint.
d.
corequisite constraint.
Mutually exclusive constraints
Chapter 7 – Integer Linear Programming
39. Which of the following applications modeled in the textbook does not involve only 0 – 1 integer variables?
a.
supply chain design
b.
bank location
c.
capital budgeting
d.
product design and market share optimization
a
0 – 1 integer variables
Subjective Short Answer
40. Solve the following problem graphically.
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.
a.
The feasible region is those integer values in the space labeled feasible region.
b.
Optimal LP relaxed occurs at X = 5.818, Y = 4.636, with Z = 56.909. Rounded down
c.
Optimal solution is at X = 4, Y = 6, and Z = 56.
Graphical solution
41. Solve the following problem graphically.
Max
X + 2Y
s.t.
6X + 8Y ≤ 48
Chapter 7 – Integer Linear Programming
7X + 5Y ≥ 35
X, Y ≥ 0
Y is 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.
labeled F. R.
b.
The optimal relaxed solution is at X = 1.538, Y = 4.846 where Z = 11.231. The rounded
c.
The optimal solution is at X = 2.667, Y = 4, Z = 10.667.
Graphical solution
42. Solve the following problem graphically.
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.
a.
The feasible region is the set of integer points in the area labeled feasible region.
Chapter 7 – Integer Linear Programming
43. Consider a capital budgeting example with five projects from which to select. Let xi = 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.
e.
No more than two of projects 1, 2, and 3 can be chosen.
Capital budgeting
44. Grush Consulting has five projects to consider. Each will require time in the next two quarters according to the table
below.
Project
Time in first quarter
Time in second quarter
Revenue
A
5
8
12000
B
3
12
10000
C
7
5
15000
D
2
3
5000
E
15
1
20000
Revenue from each project is also shown. Develop a model whose solution would maximize revenue, meet the time
b.
The optimal relaxed solution is at X = 4.5, Y = 1.75, and Z = 46.25.
The rounded solution is X = 5, Y = 2.
c.
The optimal solution is at X = 6, Y = 1, and Z = 47.
Graphical solution
Chapter 7 – Integer Linear Programming
budget of 25 in the first quarter and 20 in the second quarter, and not do both projects C and D.
12000A + 10000B + 15000C + 5000D + 20000E
5A + 3B + 7C + 2D + 15E ≤ 25
8A + 12B + 5C + 3D + 1E ≤ 20
C + D ≤ 1
Capital budgeting
45. 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.
Machine
Fixed Cost to Set
Up Production Run
Variable Cost
Per Hose
Capacity
1
750
1.25
6000
2
500
1.50
7500
3
1000
1.00
4000
4
300
2.00
5000
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.
Fixed costs
46. 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.
Shipping Cost to Destination
Sources
Construction
Cost
Seattle
Denver
Kansas City
Capacity
San Diego
—-
5
7
8
2,500
Houston
—-
10
8
6
2,500
Tulsa
350,000
9
4
3
10,000
St. Louis
200,000
12
6
2
10,000