14 Simple expressions (logic0)

Run LPL Code  ,  PDF Document

Problem

Study how the five following modeling situation can be handled and translated into a mathematical 0-1-ILP formulation (these examples are all from [7] and [6]).

  1. We would like to decide whether a particular depot should be built or not. The depot should be built, if a product is delivered to at least one costumer from that depot.

  2. If a product is manufactured at all then there is an additional setup (or fixed) cost.

  3. If product A is included in the blend then also at least a quantity 4 of product B must be included.

  4. If and only if we open a mine then a certain linear condition must hold.

  5. Formulate the condition matheamtically: if and only if 3x + 4y 5  2x + 3y 4 holds then also x + 2y 3   2x + 4y 5 must hold.

Modeling Steps

[Run the model and generate the EQU-file to see how LPL translates the logical statements into Math.]


Listing 7: The Complete Model implemented in LPL [13]
model Logic0 "Simple expressions"; 
  parameter c:=5  "choose example"; 
  -- Example 1 
  variable z [0..10]; binary d; 
  constraint C1 if c=1:  z>0 -> d=1; 
  constraint C1a if c=1: z>0 <-> d=1; 
  --Example 2 
  variable cost; 
  constraint C2 if c=2: cost = 5*z + 8*(z>0); 
  -- Example 3 
  variable zA [0..20]; zB [0..30]; 
  constraint C3 if c=3: zA>0 -> zB>=4; 
  constraint C3a if c=3: zA=4 -> zB=5; 
  -- Example 4 
  variable v [0..1]; w [0..1]; 
  constraint C4 if c=4: 2*v+3*w <= 1 <-> d; 
  set i:=1..5; 
  variable aa{i}; 
  constraint C4a if c=4: d or and{i} (aa>5); 
  -- Example 5 
  variable x[0..4]; y [0..5]; 
  constraint C5 if c=5: 3*x+4*y<=5 or 2*x+3*y>=4 <-> x+2*y>=3 or 2*x+4*y<=5; 
  -- Example 6 
  binary variable x1; x2; x3; 
  constraint D1 if c=6: x3 = (x1 or x2); 
  constraint D2 if c=6: x3 = (x1 and x2); 
  constraint D3 if c=6: x1 = ~x2; 
  solve 'nosolve'; 
  Write('EQU'); 
end

Example 1: The decision to build or not can be modeled by a binary variable δ: δ = 1 mean “to build an depot” and δ = 0 mean‘s “not to build the depot”. Now this depends on whether there is a positive quantity z > 0 delivered from this depot. Hence we may have: “if there is a certain (not-zero) quantity delivered from the depot then the depot should be built”, that is (let M be an upper bound for z):

z > 0 →  δ = 1

This can be modeled by the following linear inequality:

z ≤  M δ

Note that M is positive number, so can only be strictly positive if δ = 1, therefore, if x > 0 then δ must be 1). Inversely, if the depot is not built then nothing can be delivered from that depot (δ = 0 z 0). On the other side, if x = 0 then δ may be 1 or 0, that is, if nothing is delivered from the depot then the depot may be built or not.

If the condition must be imposed that the depot should only be built if some product are delivered from that depot, then equivalence is needed:

z > 0 ↔  δ = 1

This can be modeled by the following two linear inequalities (supposing the lower bound for z is 0 and the minimal strictly positive quantity is ϵ):

z ≤ M δ  ,   z ≥ ϵδ

LPL generates the linear constraint:

   C1:  + z - 10 d <= 0;

For equivalence the LPL code is (ϵ = 0.0001);

   C1a:  + z - 10 d <= 0; 
   X14X: + z - 0.0001 d >= 0;

Example 2: Suppose that z represents the quantity of a product manufactured at a marginal cost per unit of 5. If the product is manufactured at all there is a additional unique setup cost of 8. Hence, we need to distinguish two cases:

(1) Either nothing is manufactured then z = 0, and cost = 0.

(2) Or a quantity z is manufactured then z > 0, and cost = 5z + 8

To model this situation, we introduce a Boolean (indicator) variable δ which is true if “something is manufactured” (z > 0), if nothing is manufactured the δ is false. Now we can link the indicator variable with the quantity z by the implication (meaning “if the quantity z is strictly larger than 0 then something is manufactured”):

                     --
z > 0 →  δ    or     δ → z ≤  0

This is modeled by the linear constraint (M being an upper bound for z): z and the cost function is formulated as: cost = 5z + 8δ

To verify the resulting model, we check for the values of δ:

(1) if δ = 1 (true) then we have: z U(z) , cost = 5z + 8

(2) If δ = 0 (false) then we have: z 0 , cost = 0

In LPL one may formulated the cost function directly – without needing to introduce explicitly a binary variable (although this is possible too) – as follows:

   constraint C2: cost = 5*z + 8*(z>0);

It generates automatically the two linear constraints (where X13X is the additional binary variable):

   C2:  - 8 X13X - 5 z + cost = 0; 
   X14X:  + z - 10 X13X <= 0;

Example 3: If zA and zB are the quantities in a blend of the two products A and B, then the logical formulation is: zA > 0 zB b.

To model this situation, let’s introduce an indicator variable δ with the meaning “A is included in the blend” that is: zA > 0 δ. And the requirement “if product A is included in the blend, then also at least b of product B must be included” can be modeled as: δ zB b. The two constraints can be translated to mathematical inequalities as follows, where U(zA) is an upper bound for zA and L(zB) is a lower bound for zB:

zA ≤   U(zA ) ⋅ δ
zB ≥   L(zB + b) ⋅ δ

To verify the resulting model, we check for the values of δ:

(1) If δ = 1 (true) then zA U(zA) , zB b  (supposingL(zB) = 0

(2) If δ = 0 (false) then zA 0 , zB 0

Example 4: A constraint A must hold if and only if the indicator variable is true. For example: 2v + 3w 1 δ. This is equivalent to:

2v + 3w ≤  1 → δ   ,  δ →  2v + 3w ≤ 1

Supposing L(v) = L(w) = 0 , U(v) = U(w) = 1 , ϵ = 0.001 the resulting linear constraints are:

2v + 3w + 4δ ≤ 5   ,  2v + 3w +  1.001 δ ≥ 1.001

Example 5: A general version of this exercise is explained in [6] Chap 3.5. We first present the solution given by Williams in [6]. Let’s start with the constraint and repeat it:

∑                 ∑                   ∑                 ∑
    a1,jxj ≤ b1 ∨      a2,jxj ≥ b2  ↔       a3,jxj ≥  b3 ∨     a4,jxj ≤  b4
 j                 j                    j                 j

Let the four top inequalities be Pi with i ∈{1,, 4}, as well as their lower and upper bound mi, Mi with i ∈{1,, 4}. Then we have:

P1  ∨ P2   ↔   P3  ∨  P4                                                whichgives
                ---------         ---------
((P1 ∨  P2 ) ∨ (P3  ∨--P4))  ∧  ((P1  ∨-P2 ) ∨  (P3 ∨  P4))             whichgives
(P1  ∨ P2  ∨  (P3 ∧  P4))  ∧   ((P1  ∧  P2) ∨  P3  ∨ P4 )

Let’s the indicator variables be δi with i ∈{1,, 4}, δ5, and δ6 as follows:

δi = 1  →   Pi-  forall i ∈ {1,...,4}
δ5 = 1  →   P1-
δ5 = 1  →   P2
            ---
δ6 = 1  →   P3-
δ6 = 1  →   P4

Hence, the top constraint reduces to:

(δ1 ∨  δ2 ∨  δ6) ∧   (δ3 ∨  δ4 ∨  δ5)

The 8 indicator variable definitions together with the Boolean constraint generated the following 10 linear inequalities:

∑
    a1,jxj + (M1  - b1)δ1           ≤   M1
∑ j
    a2,jxj + (m2 -  b2)δ2            ≤   m2
  j
∑
    a3,jxj + (m3 -  b3)δ3            ≤   m3
∑ j
    a4,jxj + (M4  - b4)δ4           ≤   M4
  j
∑
    a1,jxj - (m1 -  b1 + ϵ)(1 - δ5) ≥   b1 + ϵ
∑ j
    a2,jxj - (M2  - b2 + ϵ)(1 - δ5)  ≥   b2 - ϵ
  j
∑   a  x  - (M   - b +  ϵ)(1 - δ )  ≥   b - ϵ
     3,j j     3    3          6       3
∑ j
    a4,jxj - (m4 -  b4 + ϵ)(1 - δ6) ≥   b4 + ϵ
  j
δ1 + δ2 + δ6                       ≥   1
δ  + δ +  δ                        ≥   1
 3    4    5

This is the translation given in [6]. In LPL, a somewhat different translation approach is chosen: before distributing and eliminating the equivalence (), the inequalities are defined by indicator variables:

δi = 1 →   Pi  , forall i ∈ {1,...,4}

Then the top constraint becomes:

δ1 ∨  δ2  ↔   δ3  ∨ δ4                                                  whichgives
((δ  ∨  δ ) ∨  (δ---∨-δ-))  ∧   ((δ--∨--δ-) ∨  (δ  ∨  δ ))                whichgives
   1     2    --3   --4        --1  -- 2       3     4
(δ1 ∨  δ2 ∨- (δ3 ∧  δ4))  ∧-- ((δ1 ∧-δ2) ∨  δ3 ∨  δ4)-                   whichgives
(δ1 ∨ δ2 ∨ δ3) ∧ (δ1 ∨ δ2 ∨ δ4) ∧ (δ1 ∨ δ3 ∨ δ4) ∧ (δ2 ∨ δ3 ∨ δ4)

The last line is an expression of four clauses, for which one can directly derive the four linear inequalities. Finaly, this translation generates only 4 additional binaries and totally 8 linear constraints, in contrast with the translation given in [6] which generates 6 binaries and 10 linear constraints.

The code of LPL is as follows:

  variable x[0..4]; y [0..5]; 
  constraint C5: 3*x+4*y<=5 or 2*x+3*y>=4 <-> x+2*y>=3 or 2*x+4*y<=5;

LPL generates the following 8 inequalities (together with the 4 binary variables X50X, X52X, X54X, X56X :

  C5:  + X56X + X54X - X50X >= 0; 
  X51X:  + 4 y + 3 x + 27 X50X <= 32; 
  X53X:  + 3 y + 2 x - 4 X52X >= 0; 
  X55X:  + 2 y + x - 3 X54X >= 0; 
  X57X:  + 4 y + 2 x + 23 X56X <= 28; 
  X58X:  + X52X + X50X - X54X >= 0; 
  X59X:  + X56X + X54X - X52X >= 0; 
  X60X:  + X52X + X50X - X56X >= 0;

Questions

  1. Check the output of LPL for example 5.

Answers

  1. Taken the first definition: δ1 = 1 P1, this gives

    3x +  4y + (M   - b )δ  ≤ M
              1   1  1     1

    Since b1 = 5 and M1 = 32, this gives :

    3x +  4y + 27δ ≤  32
              1

    corresponding to constraint X51X.