[Top][All Lists]

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

Re: [Help-glpk] "The conflict graph is either empty or too big"

From: Michael Hennebry
Subject: Re: [Help-glpk] "The conflict graph is either empty or too big"
Date: Wed, 23 May 2012 01:40:30 -0500 (CDT)
User-agent: Alpine 1.00 (DEB 882 2007-12-20)

On Tue, 22 May 2012, spiritfire wrote:

What about increasing the error? I don't really care about having the optimal
solution, I do not need such a precision.
How can I change it ? Because if I stop it before it finds the optimal
solution, than I get no results.... I whish to be able to view a solution
even if it is not the optimal one.

Does anybody knows if such an option is possible ?

If by "error" you mean difference from optimal, it wouldn't help.
GLPK hasn't found any solution.
There is an option to use depth-first.
That might help you,
but I think that that is the default until a solution is found.

You probably need problem-specific help.

I've made a suggestion regarding solution and constraint generation.

Another possibility is problem reformulation.

Big-M methods are notorious for producing poorly scaled problems.

Another source of problems is symmetry.
If you have twenty equivalent booleans,
a branch and bound solver is likely to spend a lot
of time grinding over equivalent almost-solutions.
It might be useful to add symmetry-breaking constraints such as
x[j+1]>=x[j] for j in 1..19 .
Symmetry-breaking constraints sometimes work,
but if one can, it might be more useful to replace the booleans
with a single variable indicating the number of ones.
If that cannot be done, one can always replace them
with five booleans indicating the number of ones.

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]