[Top][All Lists]

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

Re: [Help-glpk] binary boolean

From: Michael Hennebry
Subject: Re: [Help-glpk] binary boolean
Date: Fri, 4 May 2012 12:33:33 -0500 (CDT)
User-agent: Alpine 1.00 (DEB 882 2007-12-20)

On Fri, 4 May 2012, Andrew Makhorin wrote:

Since the conversion from mathematical formulation to constraints is
 systematic , could this be added to marhprog?

No, it is not. There exist infinitely many mip descriptions of the same
integer set. Even z = x OR y can be formulated in infinitely many ways.

All the sensible ones are equivalent.
Even a function from two booleans to the reals will have a simple convex hull.
If full dimensional, the convex hull will be a tetrahedron.
If not, the function is linear.

More booleans would complicate matters.
The convex hull could still be achieved with
2**n additional continuous variables,
though making them binary would still be mathematically correct.
Without additional variables, one might have to sacrifice the convex hull,
but 2**(n+1) constraints would be sufficient
and could be systematically generated.
In this case, different systems might produce inequivalent constraints.

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]