Problem
Given 9 products I = {1,…, 9}, the following logical condition should be modeled: “If 3 or more out of the products {1, 2, 3, 4, 5} are made, or less than 4 of products {3, 4, 5, 6, 8, 9} are made then at least 2 of products {7, 8, 9} must be made unless none of products {5, 6, 7} are made.” This example has been published in [9].
Modeling Steps
To formulate this constraint, a Boolean variable P_{i} with i ∈ I is introduced with the meaning “product i is made if P_{i} = 1 (that is, if P_{i} is true) otherwise P_{i} = 0 (or P_{i} is false)”. The logical statement can then be reformulated as follows:
“At least 3 of P_{i} with i ∈ I_{1} = {1, 2, 3, 4, 5} are true or at most 3 of P_{i} with i ∈ I_{2} = {3, 4, 5, 6, 8, 9} are true and not none of P_{i} with i ∈ I_{3} = {5, 6, 7} is true implies that at least 2 of P_{i} with i ∈ I_{4} = {7, 8, 9} are true”. Or formally:
Reducing implication and pushing not, gives:
Applying some other rules for the indexed operators gives:
or:
Let us introduce three binary variables:
Hence, the whole constraint can be reduced to 5 linear inequalities as follows:
model Logic3 "Indexed Boolean Expression";
set i := [1..9] "A set of products";
i1{i} := [1 2 3 4 5] "Sublist: products 1 to 5";
i2{i} := [3 4 5 6 8 9];
i3{i} := [5 6 7];
i4{i} := [7 8 9];
binary variable P{i} "Product i is produced?";
constraint Cond:
(atleast(3){i1} P[i1] or atmost(3){i2} P[i2])
and ~(nor{i3} P[i3]) -> atleast(2){i4} P[i4];
maximize obj: sum{i} P;
Writep(P);
end
Further Comments
LPL generates the following constraints, which corresponds exactly the solution above. It is also identical with the solution given in [9]:
Cond: X50X + X48X + X45X >= 1; X46X: P[1] + P[2] + P[3] + P[4] + P[5] + 3 X45X <= 5; X47X: P[3] + P[4] + P[5] + P[6] + P[8] + P[9] - 4 X45X >= 0; X49X[5]: - X48X - P[5] >= -1; X49X[6]: - X48X - P[6] >= -1; X49X[7]: - X48X - P[7] >= -1; X51X: P[7] + P[8] + P[9] - 2 X50X >= 0;
Questions
For some reasons, the company wants only produce two products. Which product is certainly not in that list.
Answers
If only two product are produced then certainly product 5 and 6 cannot be part of them. Why? Because this makes the premise of the implication true and the consequence false, since then less than two of set I_{4} are part and not none of set I_{3} are in the part. One can check this by adding the two constraints (the model becomes infeasible – saying that there is no way to make this true):
constraint D: sum{i} P <= 2;
constraint E: P[5] or P[6];