|
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, 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."
[Prev in Thread] | Current Thread | [Next in Thread] |