[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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.

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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]