CD7s-1
CD Supplement to Chapter 7 Some Perspectives on Solving Binary
Integer Programming Problems
Review Questions
7s-1 Push the objective function line in the direction of improving values of the objective
function. Stop at the last instant when the objective function line passes through a feasible
integer point (a binary solution).
7s-2 The exhaustive enumeration method can be used for larger problems while the graphical
method is limited to problems with just two variables.
7s-5 The LP relaxation of a BIP problem replaces the constraint on each binary variable that the
variable is binary by the constraint that it is between 0 and 1.
7s-7 A BIP problem containing mutually exclusive alternative is an example of a problem with
special structure.
7s-8 The two primary determinants of computational difficulty for a BIP problem are the
number of binary variables and any special structure in the problem.
Problems
7s.1 a)
Solution
Feasible?
P = 2x1 + 5x2
Optimal?
(0, 0)
Yes
0
(1, 0)
No
(0, 1)
Yes
5
***
(1, 1)
No
CD7s-2
c) Solving the LP relaxation graphically, the optimal solution is (x1, x2) = (1, 0.667). This
rounds to (1, 1) which is not a feasible solution.
d) Rounding down results in a solution of (1, 0) which is also not a feasible solution.
7s.2 a)
Feasible?
P = –5x1 +25x2
Optimal?
Yes
0
Yes
–5
No
Yes
20
***
b) Optimal solution: (x1, x2) = (1,1).
rounds to (0, 1) which is not a feasible solution.
d) Rounding down results in a solution of (0, 0) which is a feasible solution but yields Z=0
which in not an optimal solution.
CD7s-3
7s.3
Solution
Feasible?
P = 9x1 +5x2 +6x3 +4x4
Optimal?
(0, 0, 0, 0)
Yes
0
(1, 0, 0, 0)
Yes
9
(0, 1, 0, 0)
Yes
5
(0, 0, 1, 0)
No
(0, 0, 0, 1)
No
(1, 1, 0, 0)
Yes
14
***
(0, 1, 1, 0)
No
(0, 0, 1, 1)
No
(1, 0, 0, 1)
No
(1, 0, 1, 0)
No
(0, 1, 0, 1)
Yes
9
(1, 1, 1, 0)
No
(0, 1, 1, 1)
No
(1, 0, 1, 1)
No
(1, 1, 0, 1)
No
(1, 1, 1, 1)
No
7s.4 a) True. The current algorithms for solving BIP problems still are not nearly as efficient
as those for solving linear programming problems.