help-glpk
[Top][All Lists]

## Re: [Help-glpk] Absolute Value

 From: Michael Hennebry Subject: Re: [Help-glpk] Absolute Value Date: Tue, 29 May 2012 13:45:37 -0500 (CDT) User-agent: Alpine 1.00 (DEB 882 2007-12-20)

```On Tue, 29 May 2012, Andrew Makhorin wrote:

```
```
```
```How to express |A-B|>=C for glpsol ?

A,B and C are a boolean variables

```
```
One way is to evaluate the truth table and then use CNF description.

See http://lists.gnu.org/archive/html/help-glpk/2012-05/msg00013.html
for more details.
```
```
The referenced message does not mention the CNF description.
Also, not all CNF descriptions are created equal.
One should only use minimal clauses.
A minimal clause might correspond to a facet of the polytope.
A non-minimal clause will not correspond to a facet of the polytope.
Not all facets correspond to minimal clauses.
The number of facets can be super-exponential in the number of variables,
but the number of clauses is merely exponential.

In this case, all valid clauses are minimal.
Consider z = x OR y
(x + y + ~z)(x + ~y + z)(~x + y + z)(~x + ~y + z)
Above are four clauses, only one of which corresponds to a facet.
(x + y + ~z)(~x + z)(~y + z)
Above are three clauses, all of which correspond to facets.
There are four facets total.
The remaining facet is z<=1.
No other variable bound is a facet.

In three dimensions with four allowed boolean points,
there will always be four facets.

--