Question

Use implicit enumeration to solve the following zero-one IP

Objective function: max z = 0.2A + 0.3B + 0.5C + 0.1D

s.t. 0.5A + 1B + 1.5C + 0.1D ≤ 3.1

     0.3A + 0.8B + 1.5C + 0.4D ≤ 2.5

     0.2A + 0.2B + 0.3C + 0.1D ≤ 0.4

              A, B, C, D = 0, 1

Answer 1

Solution	A	B	C	D	Feasibility	Z value
1	0	0	0	0	Feasible	0
2	1	0	0	0	Feasible	0.2
3	0	1	0	0	Feasible	0.3
4	0	0	1	0	Feasible	0.5
5	0	0	0	1	Feasible	0.1
6	1	1	0	0	Feasible	0.5
7	1	0	1	0	Infeasible	0.7
8	1	0	0	1	Feasible	0.3
9	0	1	1	0	Infeasible	0.8
10	0	1	0	1	Feasible	0.4
11	0	0	1	1	Feasible	0.6
12	1	1	1	0	Infeasible	1
13	1	0	1	1	Infeasible	0.8
14	1	1	0	1	Infeasible	0.6
15	0	1	1	1	Infeasible	0.9
16	1	1	1	1	Infeasible	1.1

The complete enumeration (i.e., the list of all possible solution sets) for this model is as follows.

The solution 7, 9, 13 & 14 can be eliminated because they violate the third constraint. The solution 12, 15 & 16 can also be eliminated because they violate 2^nd and 3rd constraints. Among the remaing solution sets 1 can be eliminated as it chooses none of the recreational values. After evaluating the objective function value of these remaining solutions, we find the best solution to be 11, with A=0, B=0, C=1, D=1, as it has the maximum Z value=0.6.