[Cbc] How to get the lower bound?
Gabrielle A. Grun
grun at cs.sfu.ca
Wed Nov 10 01:33:38 EST 2010
Hi Thomas and Stephen,
I apoligize to Thomas.
The updating of bestPossibleObjective_ from the objective function value
of the root is an expendsive operatjion that looks atb all the nodes
currently in the tree.
How often this is done depends on the printFrequency_ member variable of
CbcModel , which is set to 0 in the constructor, but readjusted later.
--------------------------------------------------
Bits from CbcModel.cpp
bestPossibleObjective_=originalContinuousObjective_;
if (printFrequency_ <= 0) {
printFrequency_ = 1000 ;
if (getNumCols() > 2000)
printFrequency_ = 100 ;
}
/////////////[NOT A BINARY OPERATION
if ((numberNodes_%printFrequency_) == 0) {
int j ;
int nNodes = tree_->size() ;
bestPossibleObjective_ = 1.0e100 ;
for (j = 0;j < nNodes;j++) {
CbcNode * node = tree_->nodePointer(j) ;
if (node&&node->objectiveValue() <
bestPossibleObjective_)
bestPossibleObjective_ =
node->objectiveValue() ;
}
if (!status_) {
// Set best possible unless stopped on gap
if(secondaryStatus_ != 2)
bestPossibleObjective_=bestObjective_;
bestPossibleObjective_(COIN_DBL_MAX),
printFrequency_(0),
double
CbcModel::getBestPossibleObjValue() const
{
return CoinMin(bestPossibleObjective_,bestObjective_) *
solver_->getObjSense() ;
}
Gabrielle
----- Original Message -----
From: Stefan Vigerske
To: Thomas Schoenemann
Cc: cbc at list.coin-or.org
Sent: Tuesday, November 09, 2010 9:12 AM
Subject: Re: [Cbc] How to get the lower bound?
Hi,
CbcModel::getBestPossibleObjValue() should give you the dual bound (=
lower bound for minimization) that you are interested in.
If the dual bound does not change during B&B, then because of reasons 2
or 3 in your mail.
Cbc may have a different strategies on how to generate which cuts and
how to select nodes from the tree, which may be less lucky in computing
tighter bounds on your instance than other solvers.
You could test CbcModel::getBestPossibleObjValue() on a simpler instance
and see how it improves over time.
Stefan
Thomas Schoenemann wrote:
> 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
>
> _______________________________________________
> Cbc mailing list
> Cbc at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/cbc
>
--
Stefan Vigerske
Humboldt University Berlin, Numerical Mathematics
http://www.math.hu-berlin.de/~stefan
_______________________________________________
Cbc mailing list
Cbc at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/cbc
More information about the Cbc
mailing list