<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META content="text/html; charset=iso-8859-1" http-equiv=Content-Type>
<META name=GENERATOR content="MSHTML 8.00.6001.18975">
<STYLE></STYLE>
</HEAD>
<BODY bgColor=#ffffff>
<DIV>
<BR><BR>Hi Thomas and Stephen,<BR><BR>I apologize to Thomas.<BR><BR>The updating
of bestPossibleObjective_ from the objective function value
<BR>of the root is an expensive operation that looks at all the nodes
<BR>currently in the tree.<BR>How often this is done depends on the
printFrequency_ member variable of <BR>CbcModel , which is set to 0 in the
constructor, but readjusted
later.<BR>--------------------------------------------------<BR>Bits from
CbcModel.cpp<BR>bestPossibleObjective_=originalContinuousObjective_;<BR><BR><BR><BR>
if (printFrequency_ <= 0) {<BR> printFrequency_ = 1000
;<BR> if (getNumCols() >
2000)<BR> printFrequency_ = 100 ;<BR>
}<BR>/////////////[NOT A BINARY
OPERATION<BR>
if ((numberNodes_%printFrequency_) == 0)
{<BR>
int j
;<BR>
int nNodes = tree_->size()
;<BR>
bestPossibleObjective_ = 1.0e100
;<BR>
for (j = 0;j < nNodes;j++)
{<BR>
CbcNode * node = tree_->nodePointer(j)
;<BR>
if (node&&node->objectiveValue() <
<BR>bestPossibleObjective_)<BR>
bestPossibleObjective_ = <BR>node->objectiveValue()
;<BR>
}<BR><BR><BR><BR><BR><BR> if
(!status_)
{<BR>
// Set best possible unless stopped on
gap<BR>
if(secondaryStatus_ !=
2)<BR>
bestPossibleObjective_=bestObjective_;<BR><BR><BR><BR><BR>bestPossibleObjective_(COIN_DBL_MAX),<BR><BR><BR><BR><BR>printFrequency_(0),<BR><BR><BR><BR><BR><BR><BR>double<BR>CbcModel::getBestPossibleObjValue()
const<BR>{<BR> return
CoinMin(bestPossibleObjective_,bestObjective_) * <BR>solver_->getObjSense()
;<BR>}<BR><BR>Gabrielle<BR><BR>----- Original Message ----- <BR>From: Stefan
Vigerske<BR>To: Thomas Schoenemann<BR>Cc: <A
href="">cbc@list.coin-or.org</A><BR>Sent: Tuesday, November 09, 2010 9:12
AM<BR>Subject: Re: [Cbc] How to get the lower
bound?<BR><BR><BR>Hi,<BR><BR>CbcModel::getBestPossibleObjValue() should give you
the dual bound (=<BR>lower bound for minimization) that you are interested
in.<BR>If the dual bound does not change during B&B, then because of reasons
2<BR>or 3 in your mail.<BR>Cbc may have a different strategies on how to
generate which cuts and<BR>how to select nodes from the tree, which may be less
lucky in computing<BR>tighter bounds on your instance than other
solvers.<BR><BR>You could test CbcModel::getBestPossibleObjValue() on a simpler
instance<BR>and see how it improves over time.<BR><BR>Stefan<BR><BR><BR>Thomas
Schoenemann wrote:<BR>> Dear Gabrielle,<BR>><BR>> I think you
misunderstand me: I am interested in lower bounds derived from<BR>>
fractional solutions, not the upper bound defined by the best known <BR>>
integral<BR>> solution (just for clarity: I am considering _minimization_
problems).<BR>><BR>> Concerning upper bounds, CBC is working just fine and
hardly comparable to <BR>> any<BR>> other solver since it leaves the
decision of what heuristics to run <BR>> entirely<BR>> to the
user.<BR>><BR>> Concerning lower bounds, I think I was quite specific in
my previous <BR>> posting<BR>> about how I want them to be computed. As I
said, I have never seen the <BR>> value<BR>> change in the printout, and I
see three possible explanations: 1. the <BR>> value is<BR>> not computed
in the way I want it 2. the relaxation of at least one child <BR>> of<BR>>
the root node is never solved. 3. the relaxation value one of the childs
<BR>> is<BR>> indentical to that of the root node.<BR>><BR>> I
cannot exclude 2 and 3, but they do sound strange to me. As I said, many<BR>>
other solvers, both commercial (Gurobi, Cplex, Xpress) and open source <BR>>
(SCIP)<BR>> provide tigther bounds.<BR>><BR>> Apart from that, I would
like to clarify that CBC is in my view absolutely<BR>> competitive (there is
no universally best solver, which is not to be <BR>> expected<BR>> given
the generality of the solved problems). It is indeed my default <BR>>
solver<BR>> due to the clever customized stragegy of integrating your own
cuts and<BR>> heuristics. There is just this one minor issue that confuses
me.<BR>><BR>> Best regards,<BR>>
Thomas<BR>><BR>><BR>> Am Dienstag, 9. November 2010 02:02:16 schrieb
Gabrielle A. Grun:<BR>>> HI Thomas,<BR>>><BR>>> bestObjective_
is a member variable of CbcModel not associated to any<BR>>> specific
node. It is updated in CbcModel setBestSolution (CBC_Message <BR>>>
how,<BR>>> double & objectiveValue, const double
*solutionIn,
bool<BR>>> fixVariables) when the
objective value of an integer solution <BR>>> "beats"<BR>>> the
incumbent bestObjective_ value(a cutoff is used)<BR>>><BR>>> if
bestObjective_ is unchanged from the point of root node, then
no<BR>>> integer solution was found in the branch and cut
process.<BR>>><BR>>> If the best objective printed by Cbc
IS less than that of commercial<BR>>> products for the same
node count limit ( that there are different ways of<BR>>> counting nodes),
either cbc has found an integer solution with a "better"<BR>>> objective
function value or most likely, there is something wrong with <BR>>>
Cbc,<BR>>> the other products or your use of them.<BR>>><BR>>>
Take care.<BR>>><BR>>> Gabrielle<BR>>> ----- Original Message
-----<BR>>> From: Thomas Schoenemann<BR>>> To: <A
href="">cbc@list.coin-or.org</A><BR>>> Sent: Monday, November 08, 2010
1:02 AM<BR>>> Subject: Re: [Cbc] How to get the lower
bound?<BR>>><BR>>><BR>>> Dear Gabrielle and
John,<BR>>><BR>>> I am interested in the best proven lower bound. I
did not know about the<BR>>> getMinimizationObjValue() function, so that
already helps somewhat. As <BR>>> for<BR>>> the<BR>>>
printouts, I did notice them and found that the values were
consistently<BR>>> lower<BR>>> than those printed out by commercial
products. I also had the impression<BR>>> that<BR>>> the value never
changed after the root node. If you split the root node<BR>>> into two and
solve both lp-relaxations, I would like to know the lower of<BR>>> the two
objectives. This should be the best proven lower bound, and every<BR>>>
time you solve the two children of a node you can propagate this value
to<BR>>> all of its ancestors. Is this done in the current implementation
of Cbc?<BR>>><BR>>> The main reason I asked this question now is an
upcoming deadline on<BR>>> Thursday.<BR>>> The respective
observations I made throughout the last half a year and <BR>>>
they<BR>>> all date at least a month back. I am very sorry, but due to the
deadline <BR>>> I<BR>>> cannot give you specific information right
now. I'll investigate next <BR>>> week!<BR>>><BR>>> Best
regards,<BR>>> Thomas<BR>>><BR>>> Am
Sonntag, 7. November 2010 19:34:54 schrieb Gabrielle A. Grun:<BR>>>> Hi
Thomas,<BR>>>><BR>>>> is this what you are
after?<BR>>>> /// Get best objective function value as
minimization<BR>>>> inline double getMinimizationObjValue()
const<BR>>>> { return bestObjective_;};<BR>>>>
[CbcModel.hpp]<BR>>>><BR>>>> You should be seeing
bestObjective_ in any case as John says.<BR>>>><BR>>>>
{CBC_END,5,1,"Partial search - best objective %g (best possible %g),
<BR>>>> took<BR>>>> %d iterations and %d nodes (%.2f
seconds)"},<BR>>>> CbcMessage.cpp]<BR>>>><BR>>>>
status_=1;<BR>>>> if (!status_) {<BR>>>> // Set best possible
unless stopped on gap<BR>>>> if(secondaryStatus_ != 2)<BR>>>>
bestPossibleObjective_=bestObjective_;<BR>>>>
handler_->message(CBC_END_GOOD,messages_)<BR>>>> <<
bestObjective_ << numberIterations_ <<<BR>>>>
numberNodes_<<getCurrentSeconds()<BR>>>> << CoinMessageEol
;<BR>>>> } else {<BR>>>>
handler_->message(CBC_END,messages_)<BR>>>> << bestObjective_
<<bestPossibleObjective_<BR>>>> << numberIterations_
<< numberNodes_<<getCurrentSeconds()<BR>>>> <<
CoinMessageEol ;<BR>>>> }<BR>>>>
CbcModel::branchAndBound---------CbcModel.cpp]<BR>>>><BR>>>>
Take care.<BR>>>><BR>>>><BR>>>>
Gabrielle<BR>>>> ----- Original Message -----<BR>>>> From:
Thomas Schoenemann<BR>>>> To: <A
href="">cbc@list.coin-or.org</A><BR>>>> Sent: Sunday, November 07, 2010
7:22 AM<BR>>>> Subject: [Cbc] How to get the lower
bound?<BR>>>><BR>>>><BR>>>> Dear
all,<BR>>>><BR>>>> several of my problems cannot be solved
exactly by Cbc (or any other<BR>>>> solver),<BR>>>> so I set a
limit on the number of nodes. In this case, most commercial<BR>>>>
products provide the tightest lowest bound from the part of the<BR>>>>
branch-and-<BR>>>> bound that was actually executed. Is there a way to
get this information<BR>>>> in<BR>>>> Cbc? So far I only found
the value of the root-relaxation and the value<BR>>>> of
the<BR>>>> last round of cuts at the root node, but the latter only by
reading it<BR>>>> off from the output on the
screen.<BR>>>><BR>>>> Best
regards,<BR>>>> Thomas<BR>>>><BR>>>>
_______________________________________________<BR>>>> Cbc mailing
list<BR>>>> <A href="">Cbc@list.coin-or.org</A><BR>>>> <A
href="">http://list.coin-or.org/mailman/listinfo/cbc</A><BR>>>><BR>>>>
_______________________________________________<BR>>>> Cbc mailing
list<BR>>>> <A href="">Cbc@list.coin-or.org</A><BR>>>> <A
href="">http://list.coin-or.org/mailman/listinfo/cbc</A><BR>>>
_______________________________________________<BR>>> Cbc mailing
list<BR>>> <A href="">Cbc@list.coin-or.org</A><BR>>> <A
href="">http://list.coin-or.org/mailman/listinfo/cbc</A><BR>>><BR>>>
_______________________________________________<BR>>> Cbc mailing
list<BR>>> <A href="">Cbc@list.coin-or.org</A><BR>>> <A
href="">http://list.coin-or.org/mailman/listinfo/cbc</A><BR>><BR>>
_______________________________________________<BR>> Cbc mailing list<BR>>
<A href="">Cbc@list.coin-or.org</A><BR>> <A
href="">http://list.coin-or.org/mailman/listinfo/cbc</A><BR>><BR><BR><BR>--
<BR>Stefan Vigerske<BR>Humboldt University Berlin, Numerical Mathematics<BR><A
href="">http://www.math.hu-berlin.de/~stefan</A><BR><BR>_______________________________________________<BR>Cbc
mailing list<BR><A href="">Cbc@list.coin-or.org</A><BR><A
href="">http://list.coin-or.org/mailman/listinfo/cbc</A> <BR>3</DIV>
<DIV> </DIV>
<DIV>Gabrielle</DIV></BODY></HTML>