[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## Re: [Help-glpk] Modeling Choice

**From**: |
Andrew Makhorin |

**Subject**: |
Re: [Help-glpk] Modeling Choice |

**Date**: |
Fri, 08 Aug 2003 16:30:23 +0400 |

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

[Prev in Thread] |
**Current Thread** |
[Next in Thread] |

**Re: [Help-glpk] Modeling Choice**,
*Andrew Makhorin* **<=**