SbbNode Class Reference

#include <SbbNode.hpp>

List of all members.

Public Member Functions
	SbbNode ()
	Default Constructor.
	SbbNode (SbbModel *model, SbbNode *lastNode)
	Construct and increment parent reference count.
	SbbNode (const SbbNode &)
	Copy constructor.
SbbNode &	operator= (const SbbNode &rhs)
	Assignment operator.
	~SbbNode ()
	Destructor.
void	createInfo (SbbModel *model, SbbNode *lastNode, const CoinWarmStartBasis *lastws, const double *lastLower, const double *lastUpper, int numberOldActiveCuts, int numberNewCuts)
int	chooseBranch (SbbModel *model, SbbNode *lastNode)
void	decrementCuts (int change=1)
	Decrement active cut counts.
void	decrementParentCuts (int change=1)
	Decrement all active cut counts in chain starting at parent.
void	nullNodeInfo ()
	Nulls out node info.
void	initializeInfo ()
int	branch ()
	Does next branch and updates state.
SbbNodeInfo *	nodeInfo () const
double	objectiveValue () const
void	setObjectiveValue (double value)
int	numberBranches () const
	Number of arms defined for the attached SbbBranchingObject.
int	variable () const
int	way () const
int	depth () const
	Depth in branch-and-cut search tree.
int	numberUnsatisfied () const
	Get the number of objects unsatisfied at this node.
double	guessedObjectiveValue () const
void	setGuessedObjectiveValue (double value)
Private Attributes
SbbNodeInfo *	nodeInfo_
	Information to make basis and bounds.
double	objectiveValue_
double	guessedObjectiveValue_
SbbBranchingObject *	branch_
	Branching object for this node.
int	depth_
	Depth of the node in the search tree.
int	numberUnsatisfied_
	The number of objects unsatisfied at this node.

---

Detailed Description

Information required while the node is live

When a subproblem is initially created, it is represented by an SbbNode object and an attached SbbNodeInfo object.

The SbbNode contains information (depth, branching instructions), that's needed while the subproblem remains `live', i.e., while the subproblem is not fathomed and there are branch arms still be be evaluated. The SbbNode is deleted when the last branch arm has been evaluated.

The SbbNodeInfo object contains the information needed to maintain the search tree and recreate the subproblem for the node. It remains in existence until there are no nodes remaining in the subtree rooted at this node.

Definition at line 368 of file SbbNode.hpp.

---

Constructor & Destructor Documentation

SbbNode::~SbbNode (   )

Destructor. parent->decrement(1); Definition at line 1398 of file SbbNode.cpp. References branch_, SbbNodeInfo::decrement(), nodeInfo_, SbbNodeInfo::nullOwner(), SbbNodeInfo::numberBranchesLeft(), and SbbNodeInfo::numberPointingToThis(). { #ifdef CHECK_NODE if (nodeInfo_) printf("SbbNode %x Destructor nodeInfo %x (%d)\n", this,nodeInfo_,nodeInfo_->numberPointingToThis()); else printf("SbbNode %x Destructor nodeInfo %x (?)\n", this,nodeInfo_); #endif if (nodeInfo_) { nodeInfo_->nullOwner(); int numberToDelete=nodeInfo_->numberBranchesLeft(); // SbbNodeInfo * parent = nodeInfo_->parent(); if (nodeInfo_->decrement(numberToDelete)==0) { delete nodeInfo_; } else { //printf("node %x nodeinfo %x parent %x\n",this,nodeInfo_,parent); // anyway decrement parent //if (parent) } } delete branch_; }

---

Member Function Documentation

int SbbNode::chooseBranch (  SbbModel *  model, SbbNode *  lastNode )

Create a branching object for the node The routine scans the object list of the model and selects a set of unsatisfied objects as candidates for branching. The candidates are evaluated, and an appropriate branch object is installed. If evaluation determines that an object is monotone or infeasible, the routine returns immediately. In the case of a monotone object, the branch object has already been called to modify the model. Return value: 0: A branching object has been installed -1: A monotone object was discovered -2: An infeasible object was discovered Definition at line 803 of file SbbNode.cpp. References SbbBranchDecision::bestBranch(), SbbBranchDecision::betterBranch(), branch_, SbbModel::branchingMethod(), SbbObject::createBranch(), depth_, SbbModel::feasibleSolution(), OsiSolverInterface::getColLower(), OsiSolverInterface::getColSolution(), OsiSolverInterface::getColUpper(), SbbModel::getCutoff(), SbbModel::getDblParam(), SbbModel::getForcePriority(), OsiSolverInterface::getIntParam(), OsiSolverInterface::getIterationCount(), OsiClpSolverInterface::getModelPtr(), SbbModel::getNodeCount(), SbbModel::getNumCols(), OsiSolverInterface::getObjSense(), OsiSolverInterface::getObjValue(), SbbModel::getSolutionCount(), OsiSolverInterface::getWarmStart(), SbbObject::infeasibility(), SbbModel::integerVariable(), OsiSolverInterface::isDualObjectiveLimitReached(), OsiSolverInterface::isIterationLimitReached(), OsiSolverInterface::isProvenOptimal(), ClpModel::logLevel(), OsiSolverInterface::markHotStart(), ClpModel::maximumIterations(), CoinMessageHandler::message(), SbbModel::messageHandler(), SbbModel::messages(), SbbSimpleInteger::modelSequence(), SbbModel::numberObjects(), SbbModel::numberStrong(), numberUnsatisfied_, SbbModel::object(), SbbModel::priority(), SbbModel::setBestSolution(), OsiSolverInterface::setColLower(), OsiSolverInterface::setColSolution(), OsiSolverInterface::setColUpper(), OsiSolverInterface::setIntParam(), ClpModel::setLogLevel(), ClpModel::setMaximumIterations(), OsiSolverInterface::setWarmStart(), OsiSolverInterface::solveFromHotStart(), SbbModel::solver(), ClpSimplex::strongBranching(), OsiSolverInterface::unmarkHotStart(), and SbbBranchingObject::way(). Referenced by SbbModel::branchAndBound(). { if (lastNode) depth_ = lastNode->depth_+1; else depth_ = 0; delete branch_; branch_=NULL; OsiSolverInterface * solver = model->solver(); double saveObjectiveValue = solver->getObjValue(); double objectiveValue = solver->getObjSense()*saveObjectiveValue; const double * lower = solver->getColLower(); const double * upper = solver->getColUpper(); int anyAction=0; double integerTolerance = model->getDblParam(SbbModel::SbbIntegerTolerance); int i; bool beforeSolution = model->getSolutionCount()==0; int numberStrong=model->numberStrong(); int numberObjects = model->numberObjects(); int maximumStrong = max(min(model->numberStrong(),numberObjects),1); int numberColumns = model->getNumCols(); double * saveUpper = new double[numberColumns]; double * saveLower = new double[numberColumns]; // Save solution in case heuristics need good solution later double * saveSolution = new double[numberColumns]; memcpy(saveSolution,solver->getColSolution(),numberColumns*sizeof(double)); /* Get a branching decision object. Use the default decision criteria unless the user has loaded a decision method into the model. */ SbbBranchDecision *decision = model->branchingMethod(); if (!decision) decision = new SbbBranchDefaultDecision(); typedef struct { SbbBranchingObject * possibleBranch; // what a branch would do double upMovement; // cost going up (and initial away from feasible) double downMovement; // cost going down int numIntInfeasUp ; // without odd ones int numObjInfeasUp ; // just odd ones bool finishedUp; // true if solver finished int numItersUp ; // number of iterations in solver int numIntInfeasDown ; // without odd ones int numObjInfeasDown ; // just odd ones bool finishedDown; // true if solver finished int numItersDown; // number of iterations in solver int objectNumber; // Which object it is } Strong; Strong * choice = new Strong[maximumStrong]; for (i=0;i<numberColumns;i++) { saveLower[i] = lower[i]; saveUpper[i] = upper[i]; } // compute current state int numberIntegerInfeasibilities; // without odd ones int numberObjectInfeasibilities; // just odd ones model->feasibleSolution( numberIntegerInfeasibilities, numberObjectInfeasibilities); /* Original comment ``Put in coding for forcePriority for hot starts.'' Looks like a `to do' to me, given the assert. -- lh, 2003.08. */ assert(model->getForcePriority()<0); double saveOtherWay=0.0; // just for non-strong branching numberUnsatisfied_ = 0; int bestPriority=INT_MAX; /* Scan for branching objects that indicate infeasibility. Choose the best maximumStrong candidates, using priority as the first criteria, then integer infeasibility. The algorithm is to fill the choice array with a set of good candidates (by infeasibility) with priority bestPriority. Finding a candidate with priority better (less) than bestPriority flushes the choice array. (This serves as initialization when the first candidate is found.) A new candidate is added to choices only if its infeasibility exceeds the current max infeasibility (mostAway). When a candidate is added, it replaces the candidate with the smallest infeasibility (tracked by iSmallest). */ int iSmallest ; double mostAway ; for (i = 0 ; i < maximumStrong ; i++) choice[i].possibleBranch = NULL ; numberStrong=0; for (i=0;i<numberObjects;i++) { const SbbObject * object = model->object(i); int preferredWay; double otherWay; double infeasibility = object->infeasibility(preferredWay,otherWay); if (infeasibility>integerTolerance) { numberUnsatisfied_++; int priorityLevel = model->priority(i); // Better priority? Flush choices. if (priorityLevel<bestPriority) { int j; iSmallest=0; for (j=0;j<maximumStrong;j++) { choice[j].upMovement=0.0; delete choice[j].possibleBranch; choice[j].possibleBranch=NULL; } bestPriority = priorityLevel; mostAway=integerTolerance; numberStrong=0; } else if (priorityLevel>bestPriority) { continue; } // Check for suitability based on infeasibility. if (infeasibility>mostAway) { //add to list choice[iSmallest].upMovement=infeasibility; choice[iSmallest].downMovement=otherWay; saveOtherWay=otherWay; delete choice[iSmallest].possibleBranch; choice[iSmallest].possibleBranch=object->createBranch(preferredWay); numberStrong = max(numberStrong,iSmallest+1); // Save which object it was choice[iSmallest].objectNumber=i; int j; iSmallest=-1; mostAway = 1.0e50; for (j=0;j<maximumStrong;j++) { if (choice[j].upMovement<mostAway) { mostAway=choice[j].upMovement; iSmallest=j; } } } } } /* Some solvers can do the strong branching calculations faster if they do them all at once. At present only Clp does for ordinary integers but I think this coding would be easy to modify */ bool allNormal=true; // to say if we can do fast strong branching for (i=0;i<numberStrong;i++) { choice[i].numIntInfeasUp = numberUnsatisfied_; choice[i].numIntInfeasDown = numberUnsatisfied_; if (!dynamic_cast <const SbbSimpleInteger *> (model->object(choice[i].objectNumber))) allNormal=false; // Something odd so lets skip clever fast branching } /* Is strong branching enabled? If so, set up and do it. Otherwise, we'll fall through to simple branching. Setup for strong branching involves saving the current basis (for restoration afterwards) and setting up for hot starts. */ if (model->numberStrong()) { bool solveAll=false; // set true to say look at all even if some fixed (experiment) // Save basis CoinWarmStart * ws = solver->getWarmStart(); // save limit int saveLimit; solver->getIntParam(OsiMaxNumIterationHotStart,saveLimit); if (beforeSolution) solver->setIntParam(OsiMaxNumIterationHotStart,10000); // go to end /* If we are doing all strong branching in one go then we create new arrays to store information. If clp NULL then doing old way. Going down - outputSolution[2*i] is final solution. outputStuff[2*i] is status (0 - finished, 1 infeas, other unknown outputStuff[2*i+numberStrong] is number iterations On entry newUpper[i] is new upper bound, on exit obj change Going up - outputSolution[2*i+1] is final solution. outputStuff[2*i+1] is status (0 - finished, 1 infeas, other unknown outputStuff[2*i+1+numberStrong] is number iterations On entry newLower[i] is new lower bound, on exit obj change */ OsiClpSolverInterface * osiclp = dynamic_cast< OsiClpSolverInterface*> (solver); ClpSimplex * clp=NULL; double * newLower = NULL; double * newUpper = NULL; double ** outputSolution=NULL; int * outputStuff=NULL; int saveLogLevel; // For moment - until full testing - go back to normal way //allNormal=false; if (osiclp&& allNormal) { clp = osiclp->getModelPtr(); saveLogLevel = clp->logLevel(); int saveMaxIts = clp->maximumIterations(); clp->setMaximumIterations(saveLimit); clp->setLogLevel(0); // Clp - do a different way newLower = new double[numberStrong]; newUpper = new double[numberStrong]; outputSolution = new double * [2*numberStrong]; outputStuff = new int [4*numberStrong]; int * which = new int[numberStrong]; for (i=0;i<numberStrong;i++) { int iObject = choice[i].objectNumber; const SbbObject * object = model->object(iObject); const SbbSimpleInteger * simple = dynamic_cast <const SbbSimpleInteger *> (object); int iSequence = simple->modelSequence(); newLower[i]= ceil(saveSolution[iSequence]); newUpper[i]= floor(saveSolution[iSequence]); which[i]=iSequence; outputSolution[2*i]= new double [numberColumns]; outputSolution[2*i+1]= new double [numberColumns]; } clp->strongBranching(numberStrong,which, newLower, newUpper,outputSolution, outputStuff,outputStuff+2*numberStrong,!solveAll,false); clp->setMaximumIterations(saveMaxIts); delete [] which; } else { // Doing normal way // Mark hot start solver->markHotStart(); } /* Open a loop to do the strong branching LPs. For each candidate variable, solve an LP with the variable forced down, then up. If a direction turns out to be infeasible or monotonic (i.e., over the dual objective cutoff), force the objective change to be big (1.0e100). If we determine the problem is infeasible, or find a monotone variable, escape the loop. TODO: The `restore bounds' part might be better encapsulated as an unbranch() method. Branching objects more exotic than simple integers or cliques might not restrict themselves to variable bounds. TODO: Virtuous solvers invalidate the current solution (or give bogus results :-) when the bounds are changed out from under them. So we need to do all the work associated with finding a new solution before restoring the bounds. */ for (i = 0 ; i < numberStrong ; i++) { double objectiveChange ; double newObjectiveValue=1.0e100; // status is 0 finished, 1 infeasible and other int iStatus; /* Try the down direction first. (Specify the initial branching alternative as down with a call to way(-1). Each subsequent call to branch() performs the specified branch and advances the branch object state to the next branch alternative.) */ if (!clp) { choice[i].possibleBranch->way(-1) ; choice[i].possibleBranch->branch() ; solver->solveFromHotStart() ; // restore bounds for (int j=0;j<numberColumns;j++) { if (saveLower[j] != lower[j]) solver->setColLower(j,saveLower[j]); if (saveUpper[j] != upper[j]) solver->setColUpper(j,saveUpper[j]); } /* We now have an estimate of objective degradation that we can use for strong branching. If we're over the cutoff, the variable is monotone up. If we actually made it to optimality, check for a solution, and if we have a good one, call setBestSolution to process it. Note that this may reduce the cutoff, so we check again to see if we can declare this variable monotone. */ if (solver->isProvenOptimal()) iStatus=0; // optimal else if (solver->isIterationLimitReached() &&!solver->isDualObjectiveLimitReached()) iStatus=2; // unknown else iStatus=1; // infeasible newObjectiveValue = solver->getObjSense()*solver->getObjValue(); choice[i].numItersDown = solver->getIterationCount(); objectiveChange = newObjectiveValue-objectiveValue ; } else { iStatus = outputStuff[2*i]; choice[i].numItersDown = outputStuff[2*numberStrong+2*i]; newObjectiveValue = objectiveValue+newUpper[i]; solver->setColSolution(outputSolution[2*i]); } objectiveChange = newObjectiveValue - objectiveValue; if (!iStatus) { choice[i].finishedDown = true ; if (newObjectiveValue>model->getCutoff()) { objectiveChange = 1.0e100; // say infeasible } else { // See if integer solution if (model->feasibleSolution(choice[i].numIntInfeasDown, choice[i].numObjInfeasDown)) { model->setBestSolution(SBB_STRONGSOL, newObjectiveValue, solver->getColSolution()) ; if (newObjectiveValue > model->getCutoff()) // *new* cutoff objectiveChange = 1.0e100 ; } } } else if (iStatus==1) { objectiveChange = 1.0e100 ; } else { // Can't say much as we did not finish choice[i].finishedDown = false ; } choice[i].downMovement = objectiveChange ; //printf("Down on %d, status is %d, obj %g its %d cost %g finished %d inf %d infobj %d\n", // choice[i].objectNumber,iStatus,newObjectiveValue,choice[i].numItersDown, // choice[i].downMovement,choice[i].finishedDown,choice[i].numIntInfeasDown, // choice[i].numObjInfeasDown); // repeat the whole exercise, forcing the variable up if (!clp) { choice[i].possibleBranch->branch(); solver->solveFromHotStart(); // restore bounds for (int j=0;j<numberColumns;j++) { if (saveLower[j] != lower[j]) solver->setColLower(j,saveLower[j]); if (saveUpper[j] != upper[j]) solver->setColUpper(j,saveUpper[j]); } if (solver->isProvenOptimal()) iStatus=0; // optimal else if (solver->isIterationLimitReached() &&!solver->isDualObjectiveLimitReached()) iStatus=2; // unknown else iStatus=1; // infeasible newObjectiveValue = solver->getObjSense()*solver->getObjValue(); choice[i].numItersUp = solver->getIterationCount(); objectiveChange = newObjectiveValue-objectiveValue ; } else { iStatus = outputStuff[2*i+1]; choice[i].numItersUp = outputStuff[2*numberStrong+2*i+1]; newObjectiveValue = objectiveValue+newLower[i]; solver->setColSolution(outputSolution[2*i+1]); } objectiveChange = newObjectiveValue - objectiveValue; if (!iStatus) { choice[i].finishedUp = true ; if (newObjectiveValue>model->getCutoff()) { objectiveChange = 1.0e100; // say infeasible } else { // See if integer solution if (model->feasibleSolution(choice[i].numIntInfeasUp, choice[i].numObjInfeasUp)) { model->setBestSolution(SBB_STRONGSOL, newObjectiveValue, solver->getColSolution()) ; if (newObjectiveValue > model->getCutoff()) // *new* cutoff objectiveChange = 1.0e100 ; } } } else if (iStatus==1) { objectiveChange = 1.0e100 ; } else { // Can't say much as we did not finish choice[i].finishedUp = false ; } choice[i].upMovement = objectiveChange ; //printf("Up on %d, status is %d, obj %g its %d cost %g finished %d inf %d infobj %d\n", // choice[i].objectNumber,iStatus,newObjectiveValue,choice[i].numItersUp, // choice[i].upMovement,choice[i].finishedUp,choice[i].numIntInfeasUp, // choice[i].numObjInfeasUp); /* End of evaluation for this candidate variable. Possibilities are: * Both sides below cutoff; this variable is a candidate for branching. * Both sides infeasible or above the objective cutoff: no further action here. Break from the evaluation loop and assume the node will be purged by the caller. * One side below cutoff: Install the branch (i.e., fix the variable). Break from the evaluation loop and assume the node will be reoptimised by the caller. */ if (choice[i].upMovement<1.0e100) { if(choice[i].downMovement<1.0e100) { // feasible - no action } else { // up feasible, down infeasible anyAction=-1; if (!solveAll) { choice[i].possibleBranch->way(1); choice[i].possibleBranch->branch(); break; } } } else { if(choice[i].downMovement<1.0e100) { // down feasible, up infeasible anyAction=-1; if (!solveAll) { choice[i].possibleBranch->way(-1); choice[i].possibleBranch->branch(); break; } } else { // neither side feasible anyAction=-2; break; } } } if (!clp) { // Delete the snapshot solver->unmarkHotStart(); } else { clp->setLogLevel(saveLogLevel); delete [] newLower; delete [] newUpper; delete [] outputStuff; int i; for (i=0;i<2*numberStrong;i++) delete [] outputSolution[i]; delete [] outputSolution; } solver->setIntParam(OsiMaxNumIterationHotStart,saveLimit); // restore basis solver->setWarmStart(ws); delete ws; /* anyAction >= 0 indicates that strong branching didn't produce any monotone variables. Sift through the candidates for the best one. QUERY: Setting numberNodes looks to be a distributed noop. numberNodes is local to this code block. Perhaps should be numberNodes_ from model? Unclear what this calculation is doing. */ if (anyAction>=0) { int numberNodes = model->getNodeCount(); // get average cost per iteration and assume stopped ones // would stop after 50% more iterations at average cost??? !!! ??? double averageCostPerIteration=0.0; double totalNumberIterations=1.0; int smallestNumberInfeasibilities=INT_MAX; for (i=0;i<numberStrong;i++) { totalNumberIterations += choice[i].numItersDown + choice[i].numItersUp ; averageCostPerIteration += choice[i].downMovement + choice[i].upMovement; smallestNumberInfeasibilities= min(min(choice[i].numIntInfeasDown , choice[i].numIntInfeasUp ), smallestNumberInfeasibilities); } if (smallestNumberInfeasibilities>=numberIntegerInfeasibilities) numberNodes=1000000; // switch off search for better solution numberNodes=1000000; // switch off anyway averageCostPerIteration /= totalNumberIterations; // all feasible - choose best bet #if 0 for (i = 0 ; i < numberStrong ; i++) { int iColumn = model->integerVariable()[choice[i].possibleBranch->variable()] ; model->messageHandler()->message(SBB_STRONG,model->messages()) << i << iColumn <<choice[i].downMovement<<choice[i].numIntInfeasDown <<choice[i].upMovement<<choice[i].numIntInfeasUp <<choice[i].possibleBranch->value() <<CoinMessageEol; int betterWay = decision->betterBranch(choice[i].possibleBranch, branch_, choice[i].upMovement, choice[i].numIntInfeasUp , choice[i].downMovement, choice[i].numIntInfeasDown ); if (betterWay) { delete branch_; // C) create branching object branch_ = choice[i].possibleBranch; choice[i].possibleBranch=NULL; branch_->way(betterWay); } } #else // New method does all at once so it can be more sophisticated // in deciding how to balance actions. // But it does need arrays double * changeUp = new double [numberStrong]; int * numberInfeasibilitiesUp = new int [numberStrong]; double * changeDown = new double [numberStrong]; int * numberInfeasibilitiesDown = new int [numberStrong]; SbbBranchingObject ** objects = new SbbBranchingObject * [ numberStrong]; for (i = 0 ; i < numberStrong ; i++) { int iColumn = model->integerVariable()[choice[i].possibleBranch->variable()] ; model->messageHandler()->message(SBB_STRONG,model->messages()) << i << iColumn <<choice[i].downMovement<<choice[i].numIntInfeasDown <<choice[i].upMovement<<choice[i].numIntInfeasUp <<choice[i].possibleBranch->value() <<CoinMessageEol; changeUp[i]=choice[i].upMovement; numberInfeasibilitiesUp[i] = choice[i].numIntInfeasUp; changeDown[i]=choice[i].downMovement; numberInfeasibilitiesDown[i] = choice[i].numIntInfeasDown; objects[i] = choice[i].possibleBranch; } int whichObject = decision->bestBranch(objects,numberStrong,numberUnsatisfied_, changeUp,numberInfeasibilitiesUp, changeDown,numberInfeasibilitiesDown, objectiveValue); // move branching object and make sure it will not be deleted if (whichObject>=0) { branch_ = objects[whichObject]; choice[whichObject].possibleBranch=NULL; } delete [] changeUp; delete [] numberInfeasibilitiesUp; delete [] changeDown; delete [] numberInfeasibilitiesDown; delete [] objects; #endif } } /* Simple branching. Why are we choosing choice[0]? Seems arbitrary. Why not the final candidate? (It will have the greatest infeasibility.) (jjf) you can choose the first or last as if we get here choice has length 1! */ else { // not strong // C) create branching object branch_ = choice[0].possibleBranch; choice[0].possibleBranch=NULL; // we could use otherWay - think a bit } /* Cleanup, then we're outta here. */ if (!model->branchingMethod()) delete decision; for (i=0;i<maximumStrong;i++) delete choice[i].possibleBranch; delete [] choice; delete [] saveLower; delete [] saveUpper; // restore solution solver->setColSolution(saveSolution); delete [] saveSolution; return anyAction; }

void SbbNode::createInfo (  SbbModel *  model, SbbNode *  lastNode, const CoinWarmStartBasis *  lastws, const double *  lastLower, const double *  lastUpper, int  numberOldActiveCuts, int  numberNewCuts )

Create a description of the subproblem at this node The SbbNodeInfo structure holds the information (basis & variable bounds) required to recreate the subproblem for this node. It also links the node to its parent (via the parent's SbbNodeInfo object). If lastNode == NULL, a SbbFullNodeInfo object will be created. All parameters except model are unused. If lastNode != NULL, a SbbPartialNodeInfo object will be created. Basis and bounds information will be stored in the form of differences between the parent subproblem and this subproblem. (More precisely, lastws, lastUpper, lastLower, numberOldActiveCuts, and numberNewCuts are used.) Definition at line 626 of file SbbNode.cpp. References SbbModel::addedCuts(), CoinWarmStartBasis::clone(), SbbModel::currentNumberCuts(), CoinWarmStartBasis::generateDiff(), CoinWarmStartBasis::getArtifStatus(), OsiSolverInterface::getColLower(), OsiSolverInterface::getColUpper(), OsiSolverInterface::getNumCols(), OsiSolverInterface::getNumRows(), OsiSolverInterface::getWarmStart(), nodeInfo_, SbbModel::numberRowsAtContinuous(), CoinWarmStartBasis::print(), CoinWarmStartBasis::resize(), CoinWarmStartBasis::setArtifStatus(), and SbbModel::solver(). Referenced by SbbModel::branchAndBound(). { OsiSolverInterface * solver = model->solver(); /* The root --- no parent. Create full basis and bounds information. */ if (!lastNode) { nodeInfo_=new SbbFullNodeInfo(model,solver->getNumRows()); } /* Not the root. Create an edit from the parent's basis & bound information. This is not quite as straightforward as it seems. We need to reintroduce cuts we may have dropped out of the basis, in the correct position, because this whole process is strictly positional. Start by grabbing the current basis. */ else { const CoinWarmStartBasis* ws = dynamic_cast<const CoinWarmStartBasis*>(solver->getWarmStart()); assert(ws!=NULL); // make sure not volume //int numberArtificials = lastws->getNumArtificial(); int numberColumns = solver->getNumCols(); const double * lower = solver->getColLower(); const double * upper = solver->getColUpper(); int i; /* Create a clone and resize it to hold all the structural constraints, plus all the cuts: old cuts, both active and inactive (currentNumberCuts), and new cuts (numberNewCuts). TODO: You'd think that the set of constraints (logicals) in the expanded basis should match the set represented in lastws. At least, that's what I thought. But it turns out that lastws is actually the stripped basis produced at the end of addCuts(), rather than the raw basis handed back by addCuts1(). The expanded basis here is equivalent to the raw basis of addCuts1(). I said ``whoa, that's not good'' and went back to John's code to see where I'd gone wrong. And discovered the same `error' in his code. After a bit of thought, my conclusion is that correctness is not affected by whether lastws is the stripped or raw basis. The diffs have no semantics --- just a set of changes that need to be made to convert lastws into expanded. I think the only effect is that we store a lot more diffs (everything in expanded that's not covered by the stripped basis). But I need to give this more thought. There may well be some subtle error cases. In the mean time, I've twiddled addCuts() to set lastws to the raw basis. Makes me less nervous to compare apples to apples. */ CoinWarmStartBasis *expanded = dynamic_cast<CoinWarmStartBasis *>(ws->clone()) ; int numberRowsAtContinuous = model->numberRowsAtContinuous(); int iFull = numberRowsAtContinuous+model->currentNumberCuts()+ numberNewCuts; //int numberArtificialsNow = iFull; //int maxBasisLength = ((iFull+15)>>4)+((numberColumns+15)>>4); //printf("l %d full %d\n",maxBasisLength,iFull); expanded->resize(iFull,numberColumns); #ifdef FULL_DEBUG printf("Before expansion: orig %d, old %d, new %d, current %d\n", numberRowsAtContinuous,numberOldActiveCuts,numberNewCuts, model->currentNumberCuts()) ; ws->print(); #endif /* Now fill in the expanded basis. Anything indices beyond nPartial must be cuts created while processing this node --- they can be copied directly into the expanded basis. From nPartial down, pull the status of active cuts from ws, interleaving with a B entry for the deactivated (loose) cuts. */ int numberDropped = model->currentNumberCuts()-numberOldActiveCuts; int iCompact=iFull-numberDropped; SbbCountRowCut ** cut = model->addedCuts(); int nPartial = model->currentNumberCuts()+numberRowsAtContinuous; iFull--; for (;iFull>=nPartial;iFull--) { CoinWarmStartBasis::Status status = ws->getArtifStatus(--iCompact); assert (status != CoinWarmStartBasis::basic); expanded->setArtifStatus(iFull,status); } for (;iFull>=numberRowsAtContinuous;iFull--) { if (cut[iFull-numberRowsAtContinuous]) { CoinWarmStartBasis::Status status = ws->getArtifStatus(--iCompact); assert (status != CoinWarmStartBasis::basic); expanded->setArtifStatus(iFull,status); } else { expanded->setArtifStatus(iFull,CoinWarmStartBasis::basic); } } #ifdef FULL_DEBUG printf("Expanded basis\n"); expanded->print() ; printf("Diffing against\n") ; lastws->print() ; #endif /* Now that we have two bases in proper positional correspondence, creating the actual diff is dead easy. */ CoinWarmStartDiff *basisDiff = expanded->generateDiff(lastws) ; /* Diff the bound vectors. It's assumed the number of structural variables is not changing. Assuming that branching objects all involve integer variables, we should see at least one bound change as a consequence of processing this subproblem. Different types of branching objects could break this assertion. */ double *boundChanges = new double [2*numberColumns] ; int *variables = new int [2*numberColumns] ; int numberChangedBounds=0; for (i=0;i<numberColumns;i++) { if (lower[i]!=lastLower[i]) { variables[numberChangedBounds]=i; boundChanges[numberChangedBounds++]=lower[i]; } if (upper[i]!=lastUpper[i]) { variables[numberChangedBounds]=i|0x80000000; boundChanges[numberChangedBounds++]=upper[i]; } #ifdef SBB_DEBUG if (lower[i]!=lastLower[i]) printf("lower on %d changed from %g to %g\n", i,lastLower[i],lower[i]); if (upper[i]!=lastUpper[i]) printf("upper on %d changed from %g to %g\n", i,lastUpper[i],upper[i]); #endif } #ifdef SBB_DEBUG printf("%d changed bounds\n",numberChangedBounds) ; #endif assert (numberChangedBounds); /* Hand the lot over to the SbbPartialNodeInfo constructor, then clean up and return. */ nodeInfo_ = new SbbPartialNodeInfo(lastNode->nodeInfo_,this,numberChangedBounds, variables,boundChanges,basisDiff) ; delete basisDiff ; delete [] boundChanges; delete [] variables; delete expanded ; delete ws; } }

void SbbNode::initializeInfo (   )

Initialize reference counts in attached SbbNodeInfo This is a convenience routine, which will initialize the reference counts in the attached SbbNodeInfo object based on the attached SbbBranchingObject. See also: SbbNodeInfo::initializeInfo(int). Definition at line 1444 of file SbbNode.cpp. References branch_, SbbNodeInfo::initializeInfo(), nodeInfo_, and SbbBranchingObject::numberBranches(). Referenced by SbbModel::branchAndBound(). { assert(nodeInfo_ && branch_) ; nodeInfo_->initializeInfo(branch_->numberBranches()); }

int SbbNode::variable (   )  const [inline]

Branching `variable' associated with the attached SbbBranchingObject. Check SbbBranchingObject::variable() for a longer explanation of `variable'. Definition at line 471 of file SbbNode.hpp. References branch_, and SbbBranchingObject::variable(). Referenced by SbbModel::branchAndBound(). {if (branch_) return branch_->variable();else return -1;};

---

The documentation for this class was generated from the following files:

• SbbNode.hpp
• SbbNode.cpp

---