[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Michael Hennebry
Subject: Re: [Help-glpk] [GLPK] not-equal constraints
Date: Fri, 6 Feb 2009 14:53:27 -0600 (CST)
User-agent: Alpine 1.00 (DEB 882 2007-12-20)

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,


  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."

reply via email to

[Prev in Thread] Current Thread [Next in Thread]