CD7s-1
CD Supplement to Chapter 7 Advanced Formulation Techniques for
Binary Integer Programming
Review Questions
7s-1 A binary decision variable is a binary variable that represents a yes-or-no decision. An
auxiliary binary variable is an additional binary variable that is introduced into the model,
not to represent a yes-or-no decision, but simply to help formulate the model as a BIP
problem.
7s-2 Mutually exclusive products exist when at most one product can be chosen for production
due to competition for the same customers.
7s-4 An either-or constraint arises because the products are to be produced at either Plant 3 or
Plant 4, not both.
7s-5 An auxiliary binary variable can be defined as 1 if the first constraint must hold and 0 if the
second constraint must hold.
7s-7 The constraint y1 + y2 + y3 ≤ 2 forces choosing at most two of the possible new products.
7s-8 It is not possible to write a legitimate objective function because profit is not proportional
to the number of TV spots allocated to that product.
Problems
7s.1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
A B C D E F G H I
Product 1 Product 2 Product 3 Product 4
Start-up Cost $50,000 $40,000 $70,000 $60,000
Marginal Revenue $70 $60 $90 $80
Modified
Resource Resource Resource
Used Available Available
Constraint 1 5 3 6 4 6,000 <= 6,000 6,000
Constraint 2 4 6 3 5 12,000 <= 15,999 6,000
Product 1 Product 2 Product 3 Product 4
Units Produced 0 2,000 0 0
<= <= <= <=
Only if Setup 0 9,999 0 0 Total Max Products
Setup? 0 1 0 0 1 <= 2
<= <=
only if (1 or 2) 1 1 Revenue $120,000
Setup Cost $40,000
Which Constraint (0 = Constraint 1, 1 = Constraint 2): 0 Total Profit $80,000
Resource Used per Unit Produced
7s.2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
A B C D E F G
Toy 1 Toy 2
Start-up Cost $50,000 $80,000
Unit Profit $10 $15
Modified
Resource Hours Hours
Used Available Available
Factory 1 0.02 0.025 560 <= 10,499 500
Factory 2 0.025 0.04 700 <= 700 700
Toy 1 Toy 2
Units Produced 28,000 0
<= <= Gross Profit $280,000
Only if Setup 99,999 0 Setup Cost $50,000
Setup? 1 0 Net Profit $230,000
Which Factory (0 = Factory 1, 1 = Factory 2)? 1
Hours Used per
Unit Produced
7s.3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
A B C D E F G H I J K
Profit ($million)
1 Plane 2 Planes 3 Planes 4 Planes 5 Planes
Customer 1 -1 2 4 Š Š
Customer 2 1 5 Š Š Š
Customer 3 1 3 5 6 7
Capacity Used
1 Plane 2 Planes 3 Planes 4 Planes 5 Planes Total
Customer 1 20% 40% 60% Š Š Capacity Capacity
Customer 2 40% 80% Š Š Š Used Available
Customer 3 20% 40% 60% 80% 100% 100% <= 100%
Produce?
1 Plane 2 Planes 3 Planes 4 Planes 5 Planes Total
Customer 1 0 0 0 0 0 0 <= 1 Total Profit
Customer 2 0 0 0 0 0 0 <= 1 7
Customer 3 0 0 0 0 1 1 <= 1 ($million)
An alternative optimal solution is to produce 3 planes for customer 1 and 2 planes for
customer 2.
CD7s-3
7s.4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
A B C D E F G
Product 1 Product 2 Product 3
Unit Profit $50 $20 $25
Hours Hours
Machine Hours Used per Unit Produced Used Available
Milling machine 9 3 5 500 <= 500
Lathe 5 4 0 350 <= 350
Grinder 3 0 2 135.714 <= 150
Product 1 Product 2 Product 3 Total Profit
Production Rate 45.238 30.952 0 $2,881
<= <= <=
Only if Produce 999 999 0 Total
Produce? 1 1 0 2 <= 2
Produce 3 Production Rate 0 <= 20 Sales Potential
7s.5 a) Let yij = 1 if xi = j; 0 otherwise (for i = 1, 2; and j = 1, 2, 3)
Maximize Profit = 3y11 + 8y12 + 9y13 + 9y21 + 24y22 + 9y23
b)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
A B C D E F G H I
Profit Value
1 2 3
X13 8 9
X2924 9
Constraint
1 2 3
X11 2 3 Total
X21 2 3 3 <= 3
Assignment
1 2 3 Total
X11 0 0 1 <= 1 Total Profit
X20 1 0 1 <= 127
c) Optimal Solution (x1,x2) = (1, 2). Profit = 27.