Model the disjunctive grey space defined in the Figure 1
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).
We introduce two variables x ≥ 0 (horizontal extension) and y ≥ 0 (vertical extension).
The rectangle space R can be modeled as a convex space (intersection of two linear constraints):
The triangle space T can be modeled as a convex space:
The union of R and T is therefore:
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
Depending on the objective function, various optimal points are found and they are easy to verify :
With the function max x + y, the optimum is (5, 2).
With the function max y, the optimum is (3, 3).
With the function max x, the optimum is (6, 0).
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;
[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.