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