21 Math-Logic Expression II (logic7)

Run LPL Code  ,  PDF Document

Problem

Formulate the following constraint: “If at most 2 kg of the ingredient A or at most 3 kg of the ingredient B is in a mixture then at most 8 kg of the ingredient E or at least 7 kg of the ingredient F is in the mixture and vice versa.” This example is from [9].

/MOmodeling Suppose the quantity of kilograms of each ingredient is a, b, e, and f, then this statement can be formulated as follows:

a ≤ 2 ∨ b ≤ 3  ↔   e ≤ 8 ∨ f ≥  7

One can apply exactly the same procedure as in model logic0, Example 5.


Listing 14: The Complete Model implemented in LPL [13]
model Logic7 "Math-Logic Expression II"; 
  variable a [1..20]; b [0..100]; e[2..20]; f[3..20]; 
  constraint S: a<=2 or b<=3 <-> e<=8 or f>=7; 
  minimize obj: a+b+e+f; 
  Writep(obj); 
end

Further Comments

McKinnon ([9]) give a solution with 6 additional indicator variables and 10 linear constraints, while LPL generates a model with 4 additional binaries and 8 linear constraints as follows:

  S:  + X48X + X46X - X42X >= 0; 
  X43X:  + a + 18 X42X <= 20; 
  X45X:  + b + 97 X44X <= 100; 
  X47X:  + e + 12 X46X <= 20; 
  X49X:  + f - 4 X48X >= 3; 
  X50X:  + X44X + X42X - X46X >= 0; 
  X51X:  + X48X + X46X - X44X >= 0; 
  X52X:  + X44X + X42X - X48X >= 0;

Questions

  1. Change e<=8 to e>=8 and compare the two objective values, What do you notice?

Answers

  1. The solution to the first model is 6 while to the second it is 10. Minimizing the sum of the four variables will set them to their lower bound, that is: a = 1, b = 0, e = 2, and f = 3, since the left side and the right side of the equivalence are both true, the constraint is fulfiled.

    In the second case, the right side is true only if f 7, hence the solution is a+b+c+d = 10. If, on the other hand, the left would be false then a 3 and b 4 must hold and f and g would be at there lower bound, hence a + b + c + d 12 which is larger than 10.