[Coin-discuss] some information about Cbc

[Benoît MERLET]

John,

Your questions make me think : I profiled my code, and I found that my 
"cutGenerationProcess" is the method where time is spent. So, I tried to 
avoid running it when the solution isn't integral.

In the method generateCuts() of my generator :

         if( hasFractionnalComponent(si.getColSolution(), nVars) )
         {
                 cerr << "  fractionnal component, exiting" << endl;
                 return;
         }

Cuts are added only when the solution is integral, but, as I said in my 
previous mail, this solution can be infeasible for the MIP problem, 
because cuts we added are inequalities (here, metric inequalities) 
discribing the feasible solutions of the MIP problem (a network design 
problem).

But, sadly, it doesn't work well. Indeed, Cbc consider integral 
solutions as good ones, but after the branch-and-bound, if I try to 
generate cuts :

	model.branchAndBound();
         cout << "Verifying if solution is feasible ... ";
         MyGenerator generator;
         OsiCuts cutset;
         generator.generateCuts(*model.solver(), cutset);
         cout << ((cutset.sizeCuts() == 0)?"ok.":"nok") << endl;

"nok" is printed.

I wonder if cuts are added *before* considering the current solution as 
the best solution.

Could you confirm ? Have you another explanation ?

Benoît.


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