[Cbc] How to get the lower bound?

[Thomas Schoenemann]

Dear Gabrielle,

I think you misunderstand me: I am interested in lower bounds derived from 
fractional solutions, not the upper bound defined by the best known integral 
solution (just for clarity: I am considering _minimization_ problems).

Concerning upper bounds, CBC is working just fine and hardly comparable to any 
other solver since it leaves the decision of what heuristics to run entirely 
to the user.

Concerning lower bounds, I think I was quite specific in my previous posting 
about how I want them to be computed. As I said, I have never seen the value 
change in the printout, and I see three possible explanations: 1. the value is 
not computed in the way I want it 2. the relaxation of at least one child of 
the root node is never solved. 3. the relaxation value one of the childs is 
indentical to that of the root node. 

I cannot exclude 2 and 3, but they do sound strange to me. As I said, many 
other solvers, both commercial (Gurobi, Cplex, Xpress) and open source (SCIP) 
provide tigther bounds. 

Apart from that, I would like to clarify that CBC is in my view absolutely 
competitive (there is no universally best solver, which is not to be expected 
given the generality of the solved problems). It is indeed my default solver 
due to the clever customized stragegy of integrating your own cuts and 
heuristics. There is just this one minor issue that confuses me.

Best regards,
  Thomas


Am Dienstag, 9. November 2010 02:02:16 schrieb Gabrielle A. Grun:
> HI Thomas,
>
> bestObjective_ is a member variable of CbcModel not associated to any
> specific node. It is updated in CbcModel setBestSolution (CBC_Message how,
> double & objectiveValue, const double *solutionIn,                  bool
> fixVariables)       when the objective value of an integer solution "beats"
> the incumbent bestObjective_ value(a cutoff is used)
>
> if bestObjective_ is unchanged from the point of  root node, then no
> integer solution was found in the branch and cut process.
>
> If the best objective printed by Cbc IS   less than that of commercial
> products for the same node count limit ( that there are different ways of
> counting nodes), either cbc has found an integer solution with a "better"
> objective function value or most likely, there is something wrong with Cbc,
> the other products or your use of them.
>
> Take care.
>
> Gabrielle
> ----- Original Message -----
> From: Thomas Schoenemann
> To: cbc at list.coin-or.org
> Sent: Monday, November 08, 2010 1:02 AM
> Subject: Re: [Cbc] How to get the lower bound?
>
>
> Dear Gabrielle and John,
>
> I am interested in the best proven lower bound. I did not know about the
> getMinimizationObjValue() function, so that already helps somewhat. As for
> the
> printouts, I did notice them and found that the values were consistently
> lower
> than those printed out by commercial products. I also had the impression
> that
> the value never changed after the root node. If you split the root node
> into two and solve both lp-relaxations, I would like to know the lower of
> the two objectives. This should be the best proven lower bound, and every
> time you solve the two children of a node you can propagate this value to
> all of its ancestors. Is this done in the current implementation of Cbc?
>
> The main reason I asked this question now is an upcoming deadline on
> Thursday.
> The respective observations I made throughout the last half a year and they
> all date at least a month back. I am very sorry, but due to the deadline I
> cannot give you specific information right now. I'll investigate next week!
>
> Best regards,
>    Thomas
>
> Am Sonntag, 7. November 2010 19:34:54 schrieb Gabrielle A. Grun:
> > Hi Thomas,
> >
> > is this what you are after?
> > /// Get best objective function value as minimization
> > inline double getMinimizationObjValue() const
> > { return bestObjective_;};
> > [CbcModel.hpp]
> >
> > You should be seeing bestObjective_ in any case as John says.
> >
> > {CBC_END,5,1,"Partial search - best objective %g (best possible %g), took
> > %d iterations and %d nodes (%.2f seconds)"},
> > CbcMessage.cpp]
> >
> > status_=1;
> > if (!status_) {
> > // Set best possible unless stopped on gap
> > if(secondaryStatus_ != 2)
> > bestPossibleObjective_=bestObjective_;
> > handler_->message(CBC_END_GOOD,messages_)
> > << bestObjective_ << numberIterations_ <<
> > numberNodes_<<getCurrentSeconds()
> > << CoinMessageEol ;
> > } else {
> > handler_->message(CBC_END,messages_)
> > << bestObjective_ <<bestPossibleObjective_
> > << numberIterations_ << numberNodes_<<getCurrentSeconds()
> > << CoinMessageEol ;
> > }
> > CbcModel::branchAndBound---------CbcModel.cpp]
> >
> > Take care.
> >
> >
> > Gabrielle
> > ----- Original Message -----
> > From: Thomas Schoenemann
> > To: cbc at list.coin-or.org
> > Sent: Sunday, November 07, 2010 7:22 AM
> > Subject: [Cbc] How to get the lower bound?
> >
> >
> > Dear all,
> >
> > several of my problems cannot be solved exactly by Cbc (or any other
> > solver),
> > so I set a limit on the number of nodes. In this case, most commercial
> > products provide the tightest lowest bound from the part of the
> > branch-and-
> > bound that was actually executed. Is there a way to get this information
> > in
> > Cbc? So far I only found the value of the root-relaxation and the value
> > of the
> > last round of cuts at the root node, but the latter only by reading it
> > off from the output on the screen.
> >
> > Best regards,
> >   Thomas
> >
> > _______________________________________________
> > Cbc mailing list
> > Cbc at list.coin-or.org
> > http://list.coin-or.org/mailman/listinfo/cbc
> >
> > _______________________________________________
> > Cbc mailing list
> > Cbc at list.coin-or.org
> > http://list.coin-or.org/mailman/listinfo/cbc
>
> _______________________________________________
> Cbc mailing list
> Cbc at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/cbc
>
> _______________________________________________
> Cbc mailing list
> Cbc at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/cbc