Re: [Help-glpk] [GLPK] not-equal constraints

[Michael Hennebry]

On Fri, 6 Feb 2009, Andrew Makhorin wrote:

> Assuming that x and y are integer (in your case x = A and y = B+3),
> the condition x != y is equivalent to |x - y| >= 1. To describe the
> latter constraint, which is non-linear, it is sufficient to describe
> the absolute value. Let |s| <= u, where s = x - y and u is a known
> constant. Then
>
>   |s| = s1 + s2,
>
> where:
>
>   s = s1 - s2,
>
>   0 <= s1 <= u * z,
>
>   0 <= s2 <= u * (1 - z),
>
>   z is binary.

The above works, but is non-optimal:
Given u1, u2 and
s = s1 - s2
-u2 <= s <= u1
0 <= s1 <= u1 * z
0 <= s2 <= u2 * (1-z)
z binary
|s| = s-1 + s2,

Allowing u1 and u2 to be different might
allow one of them to be smaller than u.
That would allow a tighter relaxation.

--
Michael   address@hidden
"Pessimist: The glass is half empty.
Optimist:   The glass is half full.
Engineer:   The glass is twice as big as it needs to be."