[Coin-discuss] some information about Cbc

[John J Forrest]

Benoît,

You may need some of the settings I mentioned in qmip2.cpp - see points a)
b) c) d) especially d) as the final recompute of solution may be bad.  If
you send me the output I can look at it to see if anything is obvious.

John Forrest


                                                                           
             Benoît MERLET                                                 
             <benoit.merlet at or                                             
             ange-ft.com>                                               To 
             Sent by:                  Discussions about open source       
             coin-discuss-boun         software for Operations Research    
             ces at list.coin-or.         <coin-discuss at list.coin-or.org>     
             org                                                        cc 
                                                                           
                                                                   Subject 
             08/08/06 12:06 PM         Re: [Coin-discuss] some information 
                                       about Cbc                           
                                                                           
             Please respond to                                             
             Discussions about                                             
                open source                                                
               software for                                                
                Operations                                                 
                 Research                                                  
             <coin-discuss at lis                                             
              t.coin-or.org>                                               
                                                                           
                                                                           




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.


_______________________________________________
Coin-discuss mailing list
Coin-discuss at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/coin-discuss