[Cbc] CBC hints?

[Esben Mose Hansen]

On Friday October 26 2007 05:41:34 anthony at resolution.com wrote:

> It continues going on, and on, after 11,100 nodes, it still has 4440.25 as
> the best solution.
>
> We can get it to stop by using allow or secs, or by reducing the number of
> nodes it searches.
>
> What can we do (if anything) to get it to solve faster?

This problem is a classic IP trouble. Very likely, the found solution is the 
best possible, but there is no way the algorithm can know that without 
searching out the entire problem space between the LP relaxation (the "best 
possible") and the best current solution.

If that is the problem, the only real solution is to improve the LP 
relaxation. In practice this means either improving (tightening) the model or 
making a custom cut generator. The former is nearly always better and easier 
than the latter, especially since Coin already includes many good cut 
generators.

Without knowing your model --- and even then I am no expert! --- it is hard to 
say much about where to look. But as an example, if you have any constraints 
of the form

sum - Mx <= b

where M is a suitable big number that is always bigger than the sum, then 
getting M to be the exact maximum can improve the model considerable. I 
memtion this because it is tempting to just choose M big enough (too big), 
often possible to calculate the exact maximum and a common problem.

-- 
regards, Esben