5 Translating Mixed Expressions

From a practical point of view, mixing logical (Boolean) and mathematical operations in a single formula is much more interesting and its translation into mathematics is more demanding than translating just Boolean formula into mathematics. One way to link Boolean propositions and mathematical (linear) constraints is the big-M method that is presented here.

A disadvantage of the big-M method is that it requires lower and upper bounds on the linear constraints as well as a small number ϵ. In the following, U(y) is used as “upper bound value for y” and L(y) as “lower bound value for y”. In the formulas the following shortcuts are used:

        (            )             (            )
          ∑                          ∑
M  =  U      aixi - b    ,  m  = L       aixi - b
           i                           i

Case 1: Indicator variable implies an inequality




Rule Constraint Translation



50      ∑           )
 δ →     aixi ≤ b||
       i         }
 ∑              -|
    aixi > b →  δ|)
  i iaixi - b M (1 - δ)



50’            }
 δ → x ≤  0
 x > 0 →  δ- x U(x) (1 - δ)



50a  --  ∑           )
 δ →     aixi ≤ b||
       i         }
 ∑               |
    aixi > b →  δ|)
  i iaixi - b M δ



50a’  --        }
 δ → x ≤  0
 x > 0 →  δ x U(x) δ



Rule 50a is the same as Rule 50, except that δ has been replaced by δ. Rule 50’ and 50a’ are simplified versions of Rule 50 and 50a, the linear inequality has been replaced by just a single variable inequality.

Case 2: Indicator variable is implied by an inequality




Rule Constraint Translation



51     ∑               )
        aixi ≤ b → δ||
      i             |||
    --   ∑          |}
    δ →      aixi > b
 --  ∑    i         |||
 δ →     aixi ≥ b + ϵ|||)
       i iaixi - b - ϵ (m - ϵ) δ



51’               )
    x ≤  1 → δ|
    --        }
 -- δ →  x > 1|
 δ → x ≥  1 + ϵ) x - 1 - ϵ (L(x - 1) - ϵ) δ



51a  ∑                 --)
    aixi - b ≤ 0 → δ |||
  i      ∑           |||
     δ →     a x >  b}
              i i    |
     ∑     i         |||
 δ →     aixi ≥ b + ϵ||)
       i iaixi - b - ϵ (m - ϵ) (1 - δ)



51a’              -)
    x ≤  1 → δ|}

    δ →  x > 1|
 δ → x ≥  1 + ϵ) x - 1 - ϵ (L(x - 1) - ϵ) (1 - δ)



Case 2 cannot be properly modeled. An small number ϵ > 0 must be introduced to deal with iaixi -b > 0. One may verify the transformation first with the simpler case 51’: Suppose the lower bound of x is 0 and ϵ = 0.1, then (L(x - 1) is -1. Suppose that x 1, then the linear inequality reduces to -1.1 + x ≥-1.1δ, and we must derive that δ = 1, suppose now x 1 + ϵ then the linear inequality reduces again to s ≥-1.1δ with s 0, and δ maybe 0 or 1, verifying the implication.

Case 3: Indicator variable implies an inequality




Rule Constraint Translation



52      ∑           )
 δ →     aixi ≥ b||
       i         }
 ∑              -|
    aixi < b →  δ|)
  i iaixi - b m (1 - δ)



52’            }
 δ → x ≥  0
 x > 0 →  δ- x L(x) (1 - δ)



52a  --  ∑           )
 δ →     aixi ≥ b||
       i         }
 ∑               |
    aixi < b →  δ|)
  i iaixi - b m δ



52a’  --        }
 δ → x ≥  0
 x < 0 →  δ x L(x) δ



Rule 52a is the same as Rule 52, except that δ has been replaced by δ. Rule 52’ and 52a’ are simplified versions of Rule 52 and 52a, the linear inequality has been replaced by just a single variable inequality.

Case 4: Indicator variable is implied by an inequality




Rule Constraint Translation



53     ∑               )
        aixi ≥ b → δ||
      i             |||
    --   ∑          |}
    δ →      aixi < b
 --  ∑    i         |||
 δ →     aixi ≤ b - ϵ|||)
       i iaixi - b + ϵ (M + ϵ) δ



53’               )
    x ≥  1 → δ|
    --        }
 -- δ →  x < 1|
 δ → x ≤  1 - ϵ) x - 1 + ϵ (U(x - 1) + ϵ) δ



53a     ∑              -)
        aixi ≥ b → δ|||
      i  ∑          |||
    δ →      ax  < b}
              i i   |
     ∑    i         |||
 δ →     aixi ≤ b - ϵ||)
       i iaixi - b + ϵ (M + ϵ) (1 - δ)



53a’              -)
    x ≥  1 → δ|}

    δ →  x < 1|
 δ → x ≤  1 - ϵ) x - 1 + ϵ (U(x - 1) + ϵ) (1 - δ)



Basically, the four cases (Case 1 to Case 4) can be reduced to two cases in fact. Case 4 is the same as case 1 if we replace A < B by A B -ϵ, or in other words, in the linear inequalities of Case 4 the right hand side b is replaced by b - ϵ (hence M also changes). Equally, Case 2 can be reduced to Case 3 by replacing A > B by A B + ϵ, or in other words, in the linear inequalities of Case 2 the right hand side b is replaced by b + ϵ (hence M also changes).

Note also that a case with equalities δ iaixi = b can be modeled by applying two rules separately since:

                      (                )    (                )
∑                       ∑                    ∑
    aixi - b = 0  ⇐⇒         aixi - b ≤ 0  ∧       aixi - b ≥ 0
 i                       i                     i

  5.1 Some Examples