Re: [Help-glpk] help to formulate problem in terms of LP

[Andrew Makhorin]

> I tried to simulate following scenario :
> http://www.nabble.com/file/p16823521/mip_question.gif 

> (X<=1 or X>=4) and (X>=2 and X<=3)
> (Y<=1 or Y>=4) and (Y>=2 and Y<=3)
> (Z<=1 or Z>=4) and (Z>=2 and Z<=3)

> expressed in terms of MIP

> \* Problem: bubble *\

> Maximize
>  obj: + X + Y + Z

> Subject To
>  r_1: - 10000000000 b1 + 3 X <= 3
>  r_2: + 10000000000 b1 - 3 X <= 9999999988
>  r_3: - 10000000000 b2 + 3 Y <= 3
>  r_4: + 10000000000 b2 - 3 Y <= 9999999988
>  r_5: - 10000000000 b3 + 3 Z <= 3
>  r_6: + 10000000000 b3 - 3 Z <= 9999999988
>  r_7: + X >= 2
>  r_8: - X >= -3
>  r_9: + Y >= 2
>  r_10: - Y >= -3
>  r_11: + Z >= 2
>  r_12: - Z >= -3

> Bounds
>  0 <= b1 <= 1
>  0 <= b2 <= 1
>  0 <= b3 <= 1

> Generals
>  b1
>  b2
>  b3

> End

Using "big M" technique is not a good idea, since it may cause
numerical difficulties (which it does in your case).

A more appropriate modeling technique might be the folloiwng.

As I understand you need to model the condition that a point (x,y)
belongs to the dashed area having two disconnected components.

Let there be following five binary variables:

   z1 = 1 means that x <= 1

   z2 = 1 means that 1 <= x <= 4 and y <= 1

   z3 = 1 means that 2 <= x <= 3 and 2 <= y <= 3

   z4 = 1 means that 1 <= x <= 4 and y >= 4

   z5 = 1 means that x >= 4

The first constraint is the following:

   z1 + z2 + z3 + z4 + z5 = 1

that means than exactly one condition must be true.

Assuming that 0 <= x <= x_max and 0 <= y <= y_max two other
constraints can be written as follows:

   0 * z1 + 1 * z2 + 2 * z3 + 1 * z4 + 4 * z5 <= x <=
   1 * z1 + 4 * z2 + 3 * z3 + 4 * z4 + x_max * z5

   0 * z1 + 0 * z2 + 2 * z3 + 4 * z4 + 0 * z5 <= y <=
   y_max * z1 + 1 * z2 + 3 * z3 + y_max * z4 + y_max * z5