[Top][All Lists]

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

Re: [Help-glpk] Clique cuts

From: Andrew Makhorin
Subject: Re: [Help-glpk] Clique cuts
Date: Mon, 26 Jan 2009 07:04:23 +0300

> I'm trying to solve a Binary Program (BP) where the generation of
> clique inequalities is very important.
> GLPK, however, emits the following message at the beginning of the search:

> "The conflict graph is either empty or too big"

> In fact, I've noticed that this message is quite frequent in many BPs.
> When I use other solver (e.g. COIN) in this instance lots of clique
> inequalities are generated.

> Why GLPK has this limitation ?

Currently the clique cut generator is rudimentary and does not allow
processing more than 4000 binary variables; though this limit can be
changed, if necessary.

>  Does it uses a dense matrix for
> conflicts ? (it would not be a good option...)

Yes, currently the conflict graph is stored in dense format. More
efficient representation (a sparse graph plus a union of cliques) is
not implemented yet.

>  Another point is that
> the clique separation needs to consider *only* variables which are
> active in the current fractional solution (a much smaller set).

reply via email to

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