[Coin-discuss] some information about Cbc

[Benoît MERLET]

Hello,

> Your approach adds all possible cuts before going on to allow Cbc to
> branch.  Are you sure you need to do that?  The main thing is to add cuts
> while you have what looks like an integral solution but which is invalid
> because of possible cuts.  You also want to add cuts to improve bound but
> it is the first that is important.  You can force Cbc to keep going round
> adding cuts until you tell it to stop and there are various other switches
> you can set to avoid fake solutions e.g. in strong branching.  You can find
> an example in examples/qmip2.cpp.  It is still a bit experimental.

I think I need to explain the history of the method I implemented.

In fact, another exact method exists to solve the same problem : a 
Benders-like constraint generation. The MIP is solved, and with its 
solution, a violated constraint is generated and added to the MIP. This 
sequence is iterated until no more violated constraints can be found. It 
is important to note that the generated constraints are feasability 
constraints, so when one can't generate one, the current solution is the 
solution.

But with this method, at each iteration, a MIP is solved, which takes 
time. We decided then to integrate directly the constraint generation 
process during the search progress of the branch-and-bound : here comes 
our branch-and-cut. And you can see we have to add all possible cuts 
before branching because at each node we want to evaluate a feasible 
solution for our problem (even if this solution is not integral).

> It might also be useful to use -pg to profile your code to see where time
> is being spent.

Yes, the executable is compiled and linked with this option. I will take 
time to see what's happenning.

Thanks a lot for your answers,
Benoît.