17 Indexed Boolean Expression (logic3)

Run LPL Code  ,  PDF Document

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 Pi with i I is introduced with the meaning “product i is made if Pi = 1 (that is, if Pi is true) otherwise Pi = 0 (or Pi is false)”. The logical statement can then be reformulated as follows:

“At least 3 of Pi with i I1 = {1, 2, 3, 4, 5} are true or at most 3 of Pi with i I2 = {3, 4, 5, 6, 8, 9} are true and not none of Pi with i I3 = {5, 6, 7} is true implies that at least 2 of Pi with i I4 = {7, 8, 9} are true”. Or formally:

((atleast(3)    Pi ∨ atmost (3)   Pi) ∧  ¬(nor  Pi))  →   atleast(2)    Pi
           i∈I1               i∈I2           i∈I3                     i∈I4

Reducing implication and pushing not, gives:

¬ (atleast(3)    Pi ∧ ¬atmost (3)    Pi) ∨  nor  Pi ∨   atleast(2)    Pi
            i∈I1                i∈I2        i∈I3                 i∈I4

Applying some other rules for the indexed operators gives:

(atmost (2 )   P  ∧ atleast(4 )   P )  ∨ atleast(0)    ¬P   ∨  atleast(2 )   P
          i∈I1  i           i∈I2  i              i∈I3    i             i∈I4  i

or:

 ∑              ∑               ∧           ∑
(    Pi ≤  2 ∧      Pi ≥ 4)  ∨      ¬Pi ∨       Pi ≥  2
 i∈I1            i∈I2            i∈I3         i∈I4

Let us introduce three binary variables:

            ∑
δ1 = 1  →       Pi ≤  2
            i∑∈I1
δ1 = 1  →       Pi ≥  4
            i∈I
            ∧ 2
δ2 = 1  →       ¬Pi
            i∈∑I3
δ3 = 1  →       Pi ≥  2
            i∈I4

Hence, the whole constraint can be reduced to 5 linear inequalities as follows:

∑
     Pi + 3δ1 ≤ 5
i∑∈I1
     Pi - 4δ1 ≥ 0
i∈I2
Pi + δ2 ≤ 1         forall f i ∈ I3
∑
     Pi - 2δ3 ≥ 0
i∈I4
δ1 + δ2 + δ3 ≥ 1

Listing 10: The Complete Model implemented in LPL [13]
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

  1. For some reasons, the company wants only produce two products. Which product is certainly not in that list.

Answers

  1. 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 I4 are part and not none of set I3 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];