Re: [Help-glpk] Modeling Choice

[Andrew Makhorin]

> I read your replies to the Modeling Choice in gnu mail list and I was
> wondering a similar question:
> If both a,b,c,d are 0 or 1(binary number),
> Given constraint:
> |a - b| + |c - d| >= 1
>
> Can we model it as below:?
> a + b + c + d >= 1,
> 0 <= a <= k,
> 0 <= b <= 1 - k,
> 0 <= c <= j,
> 0 <= d <= 1 - j,
> k and j are binaries.


Let f(a,b,c,d): |a - b| + |c - d| >= 1. Then its truth table is:

a  b  c  d  |a - b|  |c - d|  f(a,b,c,d)
0  0  0  0     0        0         0   
0  0  0  1     0        1         1
0  0  1  0     0        1         1
0  0  1  1     0        0         0
0  1  0  0     1        0         1
0  1  0  1     1        1         1
0  1  1  0     1        1         1
0  1  1  1     1        0         1
1  0  0  0     1        0         1
1  0  0  1     1        1         1
1  0  1  0     1        1         1
1  0  1  1     1        0         1
1  1  0  0     0        0         0
1  1  0  1     0        1         1
1  1  1  0     0        1         1
1  1  1  1     0        0         0

Therefore the conjunctive normal form is:

f(a,b,c,d) = (a or b or c or d) and (a or b or ~c or ~d) and
             (~a or ~b or c or d) and (~a or ~b or ~c or ~d)

And the final description can be written as follows (one constraint
per one combination where f takes on false):

a + b + c + d >= 1
a + b + (1-c) + (1-d) >= 1
(1-a) + (1-b) + c + d >= 1
(1-a) + (1-b) + (1-c) + (1-d) >= 1

I believe my description is more efficient than yours, because it uses
no additional binary variables.