Disjunctive Constraint (logic4)

Run LPL Code  ,  PDF Document

Problem

Model the disjunctive grey space defined in the Figure 1


PIC

Figure 1: A Disjunctive Space

Modeling Steps

Informally, a set is concave, if some points on a straight segment with its endpoints in the set are outside the set. For a definition see Wikipedia. The grey set (space) in Figure 1 is concave (or disjunctive) and we know that this space cannot be modeled using a single LP – that is using linear inequalities, since the feasible space of an LP is always convex. A set of constraints can be interpreted as the intersection of all constraints in the set. In the Figure 1 the grey surface can be interpreted as the union of two convex figures: (1) a rectangle with the four corners (0, 0), (0, 2), (5, 2), and (5, 0). (2) a triangle with the corners (0, 0), (3, 3), and (6, 0).

  1. We introduce two variables x 0 (horizontal extension) and y 0 (vertical extension).

  2. The rectangle space R can be modeled as a convex space (intersection of two linear constraints):

    R : x ≤ 6  ∧ y ≤  2
  3. The triangle space T can be modeled as a convex space:

    T : y ≤ x  ∧ y ≤  6 - x
  4. The union of R and T is therefore:

    (x ≤ 6 ∧  y ≤ 2 ) ∨   (y ≤ x  ∧ y ≤  6 - x )

Listing 1: The Complete Model implemented in LPL [2]
model Logic4 "Disjunctive Constraint"; 
  variable x[0..10]; y[0..20]; 
  constraint Grey: (x<=5 and y<=2) or (y<=x and y<=6-x); 
  maximize obj: x+y; 
  Write('Optimum is: (%d,%d)' n' ,x,y); 
end

Solution

Depending on the objective function, various optimal points are found and they are easy to verify :

  1. With the function max  x + y, the optimum is (5, 2).

  2. With the function max  y, the optimum is (3, 3).

  3. With the function max  x, the optimum is (6, 0).

  4. With the function max  y - x, the optimum is (0, 2).

LPL transforms the disjunctive constraint into the following 5 linear constraints, adding two binary variables X40 and X43:

  max:  + y + x; 
  Grey:  + X43X + X40X >= 1; 
  X41X:  + x + 5 X40X <= 10; 
  X42X:  + y + 18 X40X <= 20; 
  X44X:  - x + y + 20 X43X <= 20; 
  X45X:  + x + y + 24 X43X <= 30;

References

[1]   MatMod. Homepage for Learning Mathematical Modeling :  https://matmod.ch.

[2]   Hürlimann T. Reference Manual for the LPL Modeling Language, most recent version. https://matmod.ch/lpl/doc/manual.pdf.