Re: [Help-glpk] Absolute Value

[Michael Hennebry]

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.

--
Michael   address@hidden
"On Monday, I'm gonna have to tell my kindergarten class,
whom I teach not to run with scissors,
that my fiance ran me through with a broadsword."  --  Lily