Re: [Help-glpk] Clique cuts

[Andrew Makhorin]

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