Re: [Help-glpk] Modeling Choice

[Andrew Makhorin]

>In my problem I have a number of constraints over integer variables 
>where I require at least one of several inequalities to be true, often like:
>
>    c - b <= -1
>       or
>    c - b >= 1
>       or
>    c - a <= -1
>       or
>    c - a >= 1
>
>(essentially c != b || c != a)
>
>Previously I was managing all of these myself, feeding one at a time 
>into the solver, backtracking over all the possibilities to find a 
>feasible/optimal solution.
>
>I noticed that I could model the above choice with some binary variables 
>w, x, y, and z, like:
>
>   c - b - 1000 * w <= -1
>      and
>   c - b + 1000 * x >= 1
>      and
>   c - a - 1000 * y <= -1
>      and
>   c - a + 1000 * z >= 1
>      and
>   w + x + y + z = 3
>
>When w, x, y, or z is 1, the inequality containing it is trivially 
>satisfied.  And the final equation requires that one of these variables 
>be 0.
>
>So I wouldn't have to rerun the solver from scratch everytime I tried 
>another choice.  My assumption was that this would be much faster, but 
>instead it ran at about half the speed of my previous solution.
>
>Is there some better way, using integer linear programming, to assert 
>that one of a list of inequalities must hold?

Your integer description is not quite good, although correct. There is
a standard, better way.

Assuming that a, b, and c are integer, the condition

   c != b or c != a

can be expressed as

   |c - b| + |c - a| >= 1.

So, you need to describe the absolute value, which is a nonlinearity.

Let |x| <= u, i.e. -u <= x <= +u, where u is a known constant. It is
well known that

   |x| = x1 + x2,

where

   x = x1 - x2,

   0 <= x1 <= u * k,

   0 <= x2 <= u * (1 - k),

   k^2 = k (i.e. k is binary)

Let in your case |c - b| <= u and |c - a| <= v, where u and v are known
constants. Then, assuming that |c - b| = x1 + x2 and |c - a| = y1 + y2,
the description of your condition is the following:

   (x1 + x2) + (y1 + y2) >= 1,

   c - b = x1 - x2,

   0 <= x1 <= u * k,

   0 <= x2 <= u * (1 - k),

   c - a = y1 - y2,

   0 <= y1 <= v * t,

   0 <= y2 <= v * (1 - t),

   k, t are binary.

So you need to introduce four continuous non-negative variables x1, x2,
y1, y2, two binary variables k, t, and seven linear constraints.

(Please, check formulae before using them; I didn't check them.)