SbbModel Class Reference

#include <SbbModel.hpp>

List of all members.

Public Types
enum	SbbIntParam { SbbMaxNumNode = 0, SbbMaxNumSol, SbbFathomDiscipline, SbbLastIntParam }
enum	SbbDblParam {   SbbIntegerTolerance = 0, SbbInfeasibilityWeight, SbbCutoffIncrement, SbbAllowableGap,   SbbMaximumSeconds, SbbLastDblParam }
Public Member Functions
Solve methods
void	initialSolve ()
	Solve the initial LP relaxation.
void	branchAndBound ()
	Invoke the branch & cut algorithm.
bool	solveWithCuts (OsiCuts &cuts, int numberTries, SbbNode *node, int &numberOldActiveCuts, int &numberNewCuts, int &maximumWhich, int *&whichGenerator)
	Evaluate a subproblem using cutting planes and heuristics.
bool	resolve ()
	Reoptimise an LP relaxation.
Presolve methods
SbbModel *	findCliques (bool makeEquality, int atLeastThisMany, int lessThanThis, int defaultValue=1000)
SbbModel *	integerPresolve (bool weak=false)
bool	integerPresolveThisModel (OsiSolverInterface *originalSolver, bool weak=false)
void	originalModel (SbbModel *presolvedModel, bool weak)
	Put back information into the original model after integer presolve.
bool	tightenVubs (int type, bool allowMultipleBinary=false, double useCutoff=1.0e50)
	For variables involved in VUB constraints, see if we can tighten bounds by solving lp's.
bool	tightenVubs (int numberVubs, const int *which, double useCutoff=1.0e50)
	For variables involved in VUB constraints, see if we can tighten bounds by solving lp's.
Object manipulation routines
See SbbObject for an explanation of `object' in the context of SbbModel.
int	numberObjects () const
	Get the number of objects.
SbbObject **	objects () const
	Get the array of objects.
const SbbObject *	object (int which) const
	Get the specified object.
void	deleteObjects ()
	Delete all object information.
void	addObjects (int numberObjects, SbbObject **objects)
void	synchronizeModel ()
	Ensure attached objects point to this model.
void	findIntegers (bool startAgain)
	Identify integer variables and create corresponding objects.
Parameter set/get methods
The set methods return true if the parameter was set to the given value, false if the value of the parameter is out of range. The get methods return the value of the parameter.
bool	setIntParam (SbbIntParam key, int value)
	Set an integer parameter.
bool	setDblParam (SbbDblParam key, double value)
	Set a double parameter.
int	getIntParam (SbbIntParam key) const
	Get an integer parameter.
double	getDblParam (SbbDblParam key) const
	Get a double parameter.
void	setCutoff (double value)
	Set cutoff bound on the objective function.
double	getCutoff () const
	Get the cutoff bound on the objective function - always as minimize.
bool	setMaximumNodes (int value)
	Set the maximum node limit .
int	getMaximumNodes () const
	Get the maximum node limit .
bool	setMaximumSolutions (int value)
int	getMaximumSolutions () const
bool	setIntegerTolerance (double value)
double	getIntegerTolerance () const
bool	setInfeasibilityWeight (double value)
double	getInfeasibilityWeight () const
bool	setAllowableGap (double value)
double	getAllowableGap () const
void	setForcePriority (int value)
	Set the force priority level.
int	getForcePriority () const
	Get the force priority level.
void	setMinimumDrop (double value)
	Set the minimum drop to continue cuts.
double	getMinimumDrop () const
	Get the minimum drop to continue cuts.
void	setMaximumCutPassesAtRoot (int value)
int	getMaximumCutPassesAtRoot () const
void	setMaximumCutPasses (int value)
int	getMaximumCutPasses () const
void	setNumberStrong (int number)
int	numberStrong () const
void	setPrintFrequency (int number)
int	printFrequency () const
	Get the print frequency.
Methods returning info on how the solution process terminated
bool	isAbandoned () const
	Are there a numerical difficulties?
bool	isProvenOptimal () const
	Is optimality proven?
bool	isProvenInfeasible () const
	Is infeasiblity proven (or none better than cutoff)?
bool	isNodeLimitReached () const
	Node limit reached?
bool	isSolutionLimitReached () const
	Solution limit reached?
int	getIterationCount () const
	Get how many iterations it took to solve the problem.
int	getNodeCount () const
	Get how many Nodes it took to solve the problem.
int	status () const
Problem information methods
These methods call the solver's query routines to return information about the problem referred to by the current object. Querying a problem that has no data associated with it result in zeros for the number of rows and columns, and NULL pointers from the methods that return vectors. Const pointers returned from any data-query method are valid as long as the data is unchanged and the solver is not called.
int	numberRowsAtContinuous () const
	Number of rows in continuous (root) problem.
int	getNumCols () const
	Get number of columns.
int	getNumRows () const
	Get number of rows.
int	getNumElements () const
	Get number of nonzero elements.
int	numberIntegers () const
	Number of integers in problem.
const int *	integerVariable () const
const double *	getColLower () const
	Get pointer to array[getNumCols()] of column lower bounds.
const double *	getColUpper () const
	Get pointer to array[getNumCols()] of column upper bounds.
const char *	getRowSense () const
const double *	getRightHandSide () const
const double *	getRowRange () const
const double *	getRowLower () const
	Get pointer to array[getNumRows()] of row lower bounds.
const double *	getRowUpper () const
	Get pointer to array[getNumRows()] of row upper bounds.
const double *	getObjCoefficients () const
	Get pointer to array[getNumCols()] of objective function coefficients.
double	getObjSense () const
	Get objective function sense (1 for min (default), -1 for max).
bool	isContinuous (int colIndex) const
	Return true if variable is continuous.
bool	isBinary (int colIndex) const
	Return true if variable is binary.
bool	isInteger (int colIndex) const
bool	isIntegerNonBinary (int colIndex) const
	Return true if variable is general integer.
bool	isFreeBinary (int colIndex) const
	Return true if variable is binary and not fixed at either bound.
const CoinPackedMatrix *	getMatrixByRow () const
	Get pointer to row-wise copy of matrix.
const CoinPackedMatrix *	getMatrixByCol () const
	Get pointer to column-wise copy of matrix.
double	getInfinity () const
	Get solver's value for infinity.
Methods related to querying the solution
void	setBestSolution (SBB_Message how, double &objectiveValue, const double *solution, bool fixVariables=false)
	Record a new incumbent solution and update objectiveValue.
double	checkSolution (double cutoff, const double *solution, bool fixVariables)
bool	feasibleSolution (int &numberIntegerInfeasibilities, int &numberObjectInfeasibilities) const
double *	currentSolution () const
const double *	getColSolution () const
	Get pointer to array[getNumCols()] of primal solution vector.
const double *	getRowPrice () const
	Get pointer to array[getNumRows()] of dual prices.
const double *	getReducedCost () const
	Get a pointer to array[getNumCols()] of reduced costs.
const double *	getRowActivity () const
	Get pointer to array[getNumRows()] of row activity levels.
double	getCurrentObjValue () const
	Get current objective function value.
double	getObjValue () const
	Get best objective function value.
const double *	bestSolution () const
int	getSolutionCount () const
	Get number of solutions.
void	setSolutionCount (int value)
	Set number of solutions (so heuristics will be different).
int	getNumberHeuristicSolutions () const
	Get number of heuristic solutions.
void	setObjSense (double s)
	Set objective function sense (1 for min (default), -1 for max,).
double	getContinuousObjective () const
	Value of objective at continuous.
void	setContinuousObjective (double value)
int	getContinuousInfeasibilities () const
	Number of infeasibilities at continuous.
void	setContinuousInfeasibilities (int value)
Node selection
SbbCompareBase *	nodeComparison () const
void	setNodeComparison (SbbCompareBase *compare)
void	setNodeComparison (SbbCompareBase &compare)
Branching Decisions
See the SbbBranchDecision class for additional information.
SbbBranchDecision *	branchingMethod () const
	Get the current branching decision method.
void	setBranchingMethod (SbbBranchDecision *method)
	Set the branching decision method.
void	setBranchingMethod (SbbBranchDecision &method)
Row (constraint) and Column (variable) cut generation
void	reducedCostFix ()
CoinWarmStartBasis *	getEmptyBasis (int ns=0, int na=0) const
	Get an empty basis object.
void	takeOffCuts (OsiCuts &cuts, int *whichGenerator, int &numberOldActiveCuts, int &numberNewCuts, bool allowResolve)
int	addCuts (SbbNode *node, CoinWarmStartBasis *&lastws)
void	addCuts1 (SbbNode *node, CoinWarmStartBasis *&lastws)
SbbCountRowCut **	addedCuts () const
	Return the list of cuts initially collected for this subproblem.
int	currentNumberCuts () const
	Number of entries in the list returned by addedCuts().
int	numberCutGenerators () const
	Get the number of cut generators.
SbbCutGenerator **	cutGenerators () const
	Get the list of cut generators.
SbbCutGenerator *	cutGenerator (int i) const
	Get the specified cut generator.
void	addCutGenerator (CglCutGenerator *generator, int howOften=1, const char *name=NULL, bool normal=true, bool atSolution=false, bool infeasible=false)
Heuristics and priorities
void	addHeuristic (SbbHeuristic *generator)
	Add one heuristic.
void	passInPriorities (const int *priorities, bool ifClique, int defaultValue=1000)
const int *	priority () const
	Priorities.
int	priority (int sequence) const
	Returns priority level for an object (or 1000 if no priorities exist).
Message handling
void	passInMessageHandler (CoinMessageHandler *handler)
	Pass in Message handler (not deleted at end).
void	newLanguage (CoinMessages::Language language)
	Set language.
void	setLanguage (CoinMessages::Language language)
CoinMessageHandler *	messageHandler () const
	Return handler.
CoinMessages	messages ()
	Return messages.
CoinMessages *	messagesPointer ()
	Return pointer to messages.
Constructors and destructors etc
	SbbModel ()
	Default Constructor.
	SbbModel (const OsiSolverInterface &)
	Constructor from solver.
void	assignSolver (OsiSolverInterface *&solver)
	SbbModel (const SbbModel &)
	Copy constructor.
SbbModel &	operator= (const SbbModel &rhs)
	Assignment operator.
	~SbbModel ()
	Destructor.
OsiSolverInterface *	solver () const
	Returns solver - has current state.
OsiSolverInterface *	continuousSolver () const
	Returns solver with continuous state.
void	gutsOfDestructor ()
	Clears out as much as possible (except solver).
Private Attributes
Private member data
OsiSolverInterface *	solver_
	The solver associated with this model.
bool	ourSolver_
OsiSolverInterface *	continuousSolver_
	A copy of the solver, taken at the continuous (root) node.
CoinMessageHandler *	handler_
	Message handler.
bool	defaultHandler_
CoinMessages	messages_
	Sbb messages.
int	intParam_ [SbbLastIntParam]
	Array for integer parameters.
double	dblParam_ [SbbLastDblParam]
	Array for double parameters.
CoinWarmStart *	emptyWarmStart_
CoinWarmStartBasis *	basis_
double	bestObjective_
	Best objective.
double *	bestSolution_
	Array holding the incumbent (best) solution.
double *	currentSolution_
OsiCuts	globalCuts_
	Global cuts.
double	minimumDrop_
	Minimum degradation in objective value to continue cut generation.
int	numberSolutions_
	Number of solutions.
int	forcePriority_
	Force priority level.
int	numberHeuristicSolutions_
	Number of heuristic solutions.
int	numberNodes_
	Cumulative number of nodes.
int	numberIterations_
	Cumulative number of iterations.
int	status_
	Status of problem - 0 finished, 1 stopped, 2 difficulties.
int	numberIntegers_
	Number of integers in problem.
int	numberRowsAtContinuous_
	Number of rows at continuous.
int	maximumNumberCuts_
	Maximum number of cuts.
int	currentNumberCuts_
	Number of entries in addedCuts_.
int	maximumDepth_
SbbNodeInfo **	walkback_
SbbCountRowCut **	addedCuts_
int *	integerVariable_
	Indices of integer variables.
int	strategy_
	0 bit gomory, 1 probing, 2 knapsack, 3 oddhole
SbbCompareBase *	nodeCompare_
	User node comparison function.
SbbBranchDecision *	branchingMethod_
	Variable selection function.
int	numberStrong_
int	printFrequency_
	Print frequency.
int	numberCutGenerators_
	Number of cut generators.
SbbCutGenerator **	generator_
int	numberHeuristics_
	Number of heuristics.
SbbHeuristic **	heuristic_
int	numberObjects_
	Total number of objects.
SbbObject **	object_
	Integer and Clique and ... information.
int *	originalColumns_
	Original columns as created by integerPresolve.
int *	priority_
	Priorities.
int	howOftenGlobalScan_
	How often to scan global cuts.
double	continuousObjective_
int	continuousInfeasibilities_
	Number of infeasibilities at continuous.
int	maximumCutPassesAtRoot_
	Maximum number of cut passes at root.
int	maximumCutPasses_
	Maximum number of cut passes.

---

Detailed Description

Simple Branch and bound class

The initialSolve() method solves the initial LP relaxation of the MIP problem. The branchAndBound() method can then be called to finish using a branch and cut algorithm.

Search Tree Traversal

Subproblems (aka nodes) requiring additional evaluation are stored using the SbbNode and SbbNodeInfo objects. Ancestry linkage is maintained in the SbbNodeInfo object. Evaluation of a subproblem within branchAndBound() proceeds as follows:

• The node representing the most promising parent subproblem is popped from the heap which holds the set of subproblems requiring further evaluation.
• Using branching instructions stored in the node, and information in its ancestors, the model and solver are adjusted to create the active subproblem.
• If the parent subproblem will require further evaluation (i.e., there are branches remaining) its node is pushed back on the heap. Otherwise, the node is deleted. This may trigger recursive deletion of ancestors.
• The newly created subproblem is evaluated.
• If the subproblem requires further evaluation, a node is created. All information needed to recreate the subproblem (branching information, row and column cuts) is placed in the node and the node is added to the set of subproblems awaiting further evaluation.

Note that there is never a node representing the active subproblem; the model and solver represent the active subproblem.

Row (Constraint) Cut Handling

For a typical subproblem, the sequence of events is as follows:

• The subproblem is rebuilt for further evaluation: One result of a call to addCuts() is a traversal of ancestors, leaving a list of all cuts used in the ancestors in addedCuts_. This list is then scanned to construct a basis that includes only tight cuts. Entries for loose cuts are set to NULL.
• The subproblem is evaluated: One result of a call to solveWithCuts() is the return of a set of newly generated cuts for the subproblem. addedCuts_ is also kept up-to-date as old cuts become loose.
• The subproblem is stored for further processing: A call to SbbNodeInfo::addCuts() adds the newly generated cuts to the SbbNodeInfo object associated with this node.

See SbbCountRowCut for details of the bookkeeping associated with cut management.

Definition at line 80 of file SbbModel.hpp.

---

Member Enumeration Documentation

enum SbbModel::SbbDblParam

Enumeration values: SbbIntegerTolerance  The maximum amount the value of an integer variable can vary from integer and still be considered feasible. SbbInfeasibilityWeight  The objective is assumed to worsen by this amount for each integer infeasibility. SbbCutoffIncrement  The amount by which to tighten the objective function cutoff when a new solution is discovered. SbbAllowableGap  Stop when the gap between the objective value of the best known solution and the best bound on the objective of any solution is less than this. This is an absolute value. Conversion from a percentage is left to the client. SbbMaximumSeconds  The maximum number of seconds before terminating. A double should be adequate! SbbLastDblParam  Just a marker, so that a static sized array can store parameters. Definition at line 103 of file SbbModel.hpp. { SbbIntegerTolerance=0, SbbInfeasibilityWeight, SbbCutoffIncrement, SbbAllowableGap, SbbMaximumSeconds, SbbLastDblParam };

enum SbbModel::SbbIntParam

Enumeration values: SbbMaxNumNode  The maximum number of nodes before terminating SbbMaxNumSol  The maximum number of solutions before terminating SbbFathomDiscipline  Fathoming discipline Controls objective function comparisons for purposes of fathoming by bound or determining monotonic variables. If 1, action is taken only when the current objective is strictly worse than the target. Implementation is handled by adding a small tolerance to the target. SbbLastIntParam  Just a marker, so that a static sized array can store parameters. Definition at line 84 of file SbbModel.hpp. { SbbMaxNumNode=0, SbbMaxNumSol, SbbFathomDiscipline, SbbLastIntParam };

---

Constructor & Destructor Documentation

SbbModel::SbbModel (   )

Default Constructor. Default Constructor Creates an empty model without an associated solver. Definition at line 1264 of file SbbModel.cpp. References branchingMethod_, dblParam_, handler_, intParam_, messages_, nodeCompare_, SbbAllowableGap, SbbCutoffIncrement, SbbFathomDiscipline, SbbInfeasibilityWeight, SbbIntegerTolerance, SbbMaximumSeconds, SbbMaxNumNode, SbbMaxNumSol, and CoinMessageHandler::setLogLevel(). Referenced by findCliques(), and integerPresolve(). : solver_(NULL), ourSolver_(true), continuousSolver_(NULL), defaultHandler_(true), emptyWarmStart_(NULL), basis_(NULL), bestObjective_(DBL_MAX), bestSolution_(NULL), currentSolution_(NULL), minimumDrop_(1.0e-4), numberSolutions_(0), forcePriority_(-1), numberHeuristicSolutions_(0), numberNodes_(0), numberIterations_(0), status_(0), numberIntegers_(0), numberRowsAtContinuous_(0), maximumNumberCuts_(0), currentNumberCuts_(0), maximumDepth_(0), walkback_(NULL), addedCuts_(NULL), integerVariable_(NULL), strategy_(0), numberStrong_(5), printFrequency_(0), numberCutGenerators_(0), generator_(NULL), numberHeuristics_(0), heuristic_(NULL), numberObjects_(0), object_(NULL), originalColumns_(NULL), priority_(NULL), howOftenGlobalScan_(1), continuousObjective_(DBL_MAX), continuousInfeasibilities_(INT_MAX), maximumCutPassesAtRoot_(20), maximumCutPasses_(10) { intParam_[SbbMaxNumNode] = 9999999; intParam_[SbbMaxNumSol] = 9999999; intParam_[SbbFathomDiscipline] = 0; dblParam_[SbbIntegerTolerance] = 1e-6; dblParam_[SbbInfeasibilityWeight] = 0.0; dblParam_[SbbCutoffIncrement] = 1e-5; dblParam_[SbbAllowableGap] = 1.0e-10; dblParam_[SbbMaximumSeconds] = 1.0e100; nodeCompare_=NULL; branchingMethod_=NULL; handler_ = new CoinMessageHandler(); handler_->setLogLevel(2); messages_ = SbbMessage(); }

SbbModel::SbbModel (  const OsiSolverInterface &  rhs  )

Constructor from solver. Constructor from solver. Creates a model complete with a clone of the solver passed as a parameter. Definition at line 1329 of file SbbModel.cpp. References bestSolution_, branchingMethod_, OsiSolverInterface::clone(), currentSolution_, dblParam_, OsiSolverInterface::getNumCols(), handler_, integerVariable_, intParam_, OsiSolverInterface::isInteger(), messages_, nodeCompare_, numberIntegers_, ourSolver_, SbbAllowableGap, SbbCutoffIncrement, SbbFathomDiscipline, SbbInfeasibilityWeight, SbbIntegerTolerance, SbbMaximumSeconds, SbbMaxNumNode, SbbMaxNumSol, CoinMessageHandler::setLogLevel(), and solver_. : continuousSolver_(NULL), defaultHandler_(true), emptyWarmStart_(NULL), basis_(NULL) , bestObjective_(DBL_MAX), minimumDrop_(1.0e-4), numberSolutions_(0), forcePriority_(-1), numberHeuristicSolutions_(0), numberNodes_(0), numberIterations_(0), status_(0), numberRowsAtContinuous_(0), maximumNumberCuts_(0), currentNumberCuts_(0), maximumDepth_(0), walkback_(NULL), addedCuts_(NULL), strategy_(0), numberStrong_(5), printFrequency_(0), numberCutGenerators_(0), generator_(NULL), numberHeuristics_(0), heuristic_(NULL), numberObjects_(0), object_(NULL), originalColumns_(NULL), priority_(NULL), howOftenGlobalScan_(-1), continuousObjective_(DBL_MAX), continuousInfeasibilities_(INT_MAX), maximumCutPassesAtRoot_(20), maximumCutPasses_(10) { intParam_[SbbMaxNumNode] = 9999999; intParam_[SbbMaxNumSol] = 9999999; intParam_[SbbFathomDiscipline] = 0; dblParam_[SbbIntegerTolerance] = 1e-6; dblParam_[SbbInfeasibilityWeight] = 0.0; dblParam_[SbbCutoffIncrement] = 1e-5; dblParam_[SbbAllowableGap] = 1.0e-10; dblParam_[SbbMaximumSeconds] = 1.0e100; nodeCompare_=NULL; branchingMethod_=NULL; handler_ = new CoinMessageHandler(); handler_->setLogLevel(2); messages_ = SbbMessage(); solver_ = rhs.clone(); ourSolver_ = true ; // Initialize solution and integer variable vectors bestSolution_ = NULL; // to say no solution found numberIntegers_=0; int numberColumns = solver_->getNumCols(); int iColumn; if (numberColumns) { // Space for current solution currentSolution_ = new double[numberColumns]; for (iColumn=0;iColumn<numberColumns;iColumn++) { if( solver_->isInteger(iColumn)) numberIntegers_++; } } else { // empty model currentSolution_=NULL; } if (numberIntegers_) { integerVariable_ = new int [numberIntegers_]; numberIntegers_=0; for (iColumn=0;iColumn<numberColumns;iColumn++) { if( solver_->isInteger(iColumn)) integerVariable_[numberIntegers_++]=iColumn; } } else { integerVariable_ = NULL; } }

---

Member Function Documentation

void SbbModel::addCutGenerator (  CglCutGenerator *  generator, int  howOften = 1, const char *  name = NULL, bool  normal = true, bool  atSolution = false, bool  infeasible = false )

Add one generator - up to user to delete generators. howoften affects how generator is used. 0 or 1 means always, >1 means every that number of nodes. Negative values have same meaning as positive but they may be switched off (-> -100) by code if not many cuts generated at continuous. -99 is just done at root. Name is just for printout Definition at line 1865 of file SbbModel.cpp. References numberCutGenerators_. { SbbCutGenerator ** temp = generator_; generator_ = new SbbCutGenerator * [numberCutGenerators_+1]; memcpy(generator_,temp,numberCutGenerators_*sizeof(SbbCutGenerator *)); delete[] temp ; generator_[numberCutGenerators_++]= new SbbCutGenerator(this,generator, howOften, name, normal,atSolution,whenInfeasible); }

int SbbModel::addCuts (  SbbNode *  node, CoinWarmStartBasis *&  lastws )

Determine and install the active cuts that need to be added for the current subproblem The whole truth is a bit more complicated. The first action is a call to addCuts1(). addCuts() then sorts through the list, installs the tight cuts in the model, and does bookkeeping (adjusts reference counts). The basis returned from addCuts1() is adjusted accordingly. If it turns out that the node should really be fathomed by bound, addCuts() simply treats all the cuts as loose as it does the bookkeeping. Definition at line 1997 of file SbbModel.cpp. References addCuts(), addCuts1(), addedCuts_, OsiSolverInterface::applyRowCuts(), basis_, CoinWarmStartBasis::clone(), currentNumberCuts(), currentNumberCuts_, SbbCountRowCut::decrement(), SbbNode::depth(), CoinWarmStartBasis::getArtifStatus(), getCutoff(), getNumCols(), SbbNode::nodeInfo(), SbbNodeInfo::numberBranchesLeft(), numberNodes_, numberRowsAtContinuous_, SbbNode::numberUnsatisfied(), SbbNode::objectiveValue(), CoinWarmStartBasis::print(), printFrequency_, CoinWarmStartBasis::resize(), CoinWarmStartBasis::setArtifStatus(), OsiSolverInterface::setWarmStart(), solver_, and status(). Referenced by addCuts(), branchAndBound(), and solveWithCuts(). { /* addCuts1 performs step 1 of restoring the subproblem at this node; see the comments there. */ addCuts1(node,lastws); int i; int numberColumns = getNumCols(); SbbNodeInfo * nodeInfo = node->nodeInfo(); double cutoff = getCutoff() ; int currentNumberCuts=currentNumberCuts_; /* If the node can't be fathomed by bound, reinstall tight cuts in the constraint system. */ if (node->objectiveValue() < cutoff) { int numberToAdd = 0; OsiRowCut * addCuts; if (currentNumberCuts == 0) addCuts = NULL; else addCuts = new OsiRowCut[currentNumberCuts]; # ifdef CHECK_CUT_COUNTS printf("addCuts: expanded basis; rows %d+%d\n", numberRowsAtContinuous_,currentNumberCuts); lastws->print(); # endif /* Adjust the basis and constraint system so that we retain only active cuts. There are three steps: 1) Scan the basis. If the logical associated with the cut is basic, it's loose and we drop it. The status of the logical for tight cuts is written back into the status array, compressing as we go. 2) Resize the basis to fit the number of active cuts, stash a clone, and install with a call to setWarmStart(). 3) Install the tight cuts into the constraint system (applyRowCuts). TODO: After working through the code in createInfo, I'm more comfortable if inactive cuts are retained in lastws. So, instead of cloning lastws into basis_ after the compression loop, do it ahead of time and then recover lastws from basis_ after the setWarmStart(). (Minimal code change :-). See SbbNode::createInfo for more. */ if (basis_) delete basis_ ; basis_= dynamic_cast<CoinWarmStartBasis *>(lastws->clone()) ; for (i=0;i<currentNumberCuts;i++) { CoinWarmStartBasis::Status status = lastws->getArtifStatus(i+numberRowsAtContinuous_); if (status != CoinWarmStartBasis::basic&&addedCuts_[i]) { # ifdef CHECK_CUT_COUNTS printf("Using cut %d %x as row %d\n",i,addedCuts_[i], numberRowsAtContinuous_+numberToAdd); # endif lastws->setArtifStatus(numberToAdd+numberRowsAtContinuous_,status); addCuts[numberToAdd++] = OsiRowCut(*addedCuts_[i]); } else { # ifdef CHECK_CUT_COUNTS printf("Dropping cut %d %x\n",i,addedCuts_[i]); # endif addedCuts_[i]=NULL; } } int numberRowsNow=numberRowsAtContinuous_+numberToAdd; lastws->resize(numberRowsNow,numberColumns); #ifdef FULL_DEBUG printf("addCuts: stripped basis; rows %d + %d\n", numberRowsAtContinuous_,numberToAdd); lastws->print(); #endif /* Apply the cuts and set the basis in the solver. */ solver_->applyRowCuts(numberToAdd,addCuts); solver_->setWarmStart(lastws); /* TODO: Undo the debugging change. Delete lastws and assign basis_. */ delete lastws ; lastws = basis_ ; basis_ = 0 ; #if 0 if ((numberNodes_%printFrequency_)==0) { printf("Objective %g, depth %d, unsatisfied %d\n", node->objectiveValue(), node->depth(),node->numberUnsatisfied()); } #endif /* Clean up and we're out of here. */ delete [] addCuts; numberNodes_++; return 0; } /* This node has been fathomed by bound as we try to revive it out of the live set. Adjust the cut reference counts to reflect that we no longer need to explore the remaining branch arms, hence they will no longer reference any cuts. Cuts whose reference count falls to zero are deleted. */ else { int i; int numberLeft = nodeInfo->numberBranchesLeft(); for (i = 0 ; i < currentNumberCuts ; i++) { if (addedCuts_[i]) { if (!addedCuts_[i]->decrement(numberLeft)) { delete addedCuts_[i]; addedCuts_[i] = NULL; } } } return 1 ; } }

void SbbModel::addCuts1 (  SbbNode *  node, CoinWarmStartBasis *&  lastws )

Traverse the tree from node to root and prep the model addCuts1() begins the job of prepping the model to match the current subproblem. The model is stripped of all cuts, and the search tree is traversed from node to root to determine the changes required. Appropriate bounds changes are installed, a list of cuts is collected but not installed, and an appropriate basis (minus the cuts, but big enough to accommodate them) is constructed. Todo: addCuts1() is called in contexts where it's known in advance that all that's desired is to determine a list of cuts and do the bookkeeping (adjust the reference counts). The work of installing bounds and building a basis goes to waste. Definition at line 1909 of file SbbModel.cpp. References addedCuts_, SbbNodeInfo::applyToModel(), currentNumberCuts(), currentNumberCuts_, OsiSolverInterface::deleteRows(), getNumCols(), OsiSolverInterface::getNumRows(), maximumDepth_, maximumNumberCuts_, SbbNode::nodeInfo(), SbbNodeInfo::numberCuts(), numberRowsAtContinuous_, CoinWarmStartBasis::setSize(), solver_, and walkback_. Referenced by addCuts(), and tree::cleanTree(). { int i; int nNode=0; int numberColumns = getNumCols(); SbbNodeInfo * nodeInfo = node->nodeInfo(); /* Remove all cuts from the constraint system. (original comment includes ``see note below for later efficiency'', but the reference isn't clear to me). */ int currentNumberCuts = solver_->getNumRows()-numberRowsAtContinuous_; int *which = new int[currentNumberCuts]; for (i = 0 ; i < currentNumberCuts ; i++) which[i] = i+numberRowsAtContinuous_; solver_->deleteRows(currentNumberCuts,which); delete [] which; /* Accumulate the path from node to the root in walkback_, and accumulate a cut count in currentNumberCuts. original comment: when working then just unwind until where new node joins old node (for cuts?) */ currentNumberCuts = 0; while (nodeInfo) { //printf("nNode = %d, nodeInfo = %x\n",nNode,nodeInfo); walkback_[nNode++]=nodeInfo; currentNumberCuts += nodeInfo->numberCuts() ; nodeInfo = nodeInfo->parent() ; if (nNode==maximumDepth_) { maximumDepth_ *= 2; SbbNodeInfo ** temp = new SbbNodeInfo * [maximumDepth_]; for (i=0;i<nNode;i++) temp[i] = walkback_[i]; delete [] walkback_; walkback_ = temp; } } /* Create an empty basis with sufficient capacity for the constraint system we'll construct: original system plus cuts. Make sure we have capacity to record those cuts in addedCuts_. The method of adjusting the basis at a FullNodeInfo object (the root, for example) is to use a copy constructor to duplicate the basis held in the nodeInfo, then resize it and return the new basis object. Guaranteed, lastws will point to a different basis when it returns. We pass in a basis because we need the parameter to return the allocated basis, and it's an easy way to pass in the size. But we take a hit for memory allocation. */ currentNumberCuts_=currentNumberCuts; if (currentNumberCuts >= maximumNumberCuts_) { maximumNumberCuts_ = currentNumberCuts; delete [] addedCuts_; addedCuts_ = new SbbCountRowCut * [maximumNumberCuts_]; } lastws->setSize(numberColumns,numberRowsAtContinuous_+currentNumberCuts); /* This last bit of code traverses the path collected in walkback_ from the root back to node. At the end of the loop, * lastws will be an appropriate basis for node; * variable bounds in the constraint system will be set to be correct for node; and * addedCuts_ will be set to a list of cuts that need to be added to the constraint system at node. applyToModel does all the heavy lifting. */ currentNumberCuts=0; while (nNode) { --nNode; walkback_[nNode]->applyToModel(this,lastws,addedCuts_,currentNumberCuts); } }

void SbbModel::addObjects (  int  numberObjects, SbbObject **  objects )

Add in object information. Objects are cloned; the owner can delete the originals. Definition at line 3355 of file SbbModel.cpp. References SbbObject::clone(), numberObjects_, object_, and SbbObject::setModel(). Referenced by findCliques(). { int newNumberObjects= numberObjects+numberObjects_; SbbObject ** temp = new SbbObject * [newNumberObjects]; int i; for (i=0;i<numberObjects_;i++) temp[i]=object_[i]; for (;i<newNumberObjects;i++) { temp[i]=objects[i-numberObjects_]->clone(); temp[i]->setModel(this); } delete [] object_; object_ = temp; numberObjects_ = newNumberObjects; }

void SbbModel::assignSolver (  OsiSolverInterface *&  solver  )

Assign a solver to the model (model assumes ownership) On return, solver will be NULL. Note: Parameter settings in the outgoing solver are not inherited by the incoming solver. Definition at line 1431 of file SbbModel.cpp. References basis_, emptyWarmStart_, OsiSolverInterface::getNumCols(), integerVariable_, OsiSolverInterface::isInteger(), CoinMessageHandler::logLevel(), OsiSolverInterface::messageHandler(), numberIntegers_, ourSolver_, CoinMessageHandler::setLogLevel(), and solver_. { // Keep the current message level for solver (if solver exists) if (solver_) solver->messageHandler()->setLogLevel(solver_->messageHandler()->logLevel()) ; if (ourSolver_) delete solver_ ; solver_ = solver; solver = NULL ; ourSolver_ = true ; /* Basis information is solver-specific. */ if (basis_) { delete basis_ ; basis_ = 0 ; } if (emptyWarmStart_) { delete emptyWarmStart_ ; emptyWarmStart_ = 0 ; } /* Initialize integer variable vector. */ numberIntegers_=0; int numberColumns = solver_->getNumCols(); int iColumn; for (iColumn=0;iColumn<numberColumns;iColumn++) { if( solver_->isInteger(iColumn)) numberIntegers_++; } if (numberIntegers_) { integerVariable_ = new int [numberIntegers_]; numberIntegers_=0; for (iColumn=0;iColumn<numberColumns;iColumn++) { if( solver_->isInteger(iColumn)) integerVariable_[numberIntegers_++]=iColumn; } } else { integerVariable_ = NULL; } return ; }

const double* SbbModel::bestSolution (   )  const [inline]

The best solution to the integer programming problem. The best solution to the integer programming problem found during the search. If no solution is found, the method returns null. Definition at line 657 of file SbbModel.hpp. References bestSolution_. Referenced by SbbLocalSearch::solution(). { return bestSolution_;};

void SbbModel::branchAndBound (   )

Invoke the branch & cut algorithm. The method assumes that initialSolve() has been called to solve the LP relaxation. It processes the root node, then proceeds to explore the branch & cut search tree. The search ends when the tree is exhausted or one of several execution limits is reached. Definition at line 507 of file SbbModel.cpp. References OsiSolverInterface::activateRowCutDebugger(), addCuts(), SbbNodeInfo::addCuts(), addedCuts_, basis_, bestObjective_, bestSolution_, SbbNode::branch(), SbbNode::chooseBranch(), tree::cleanTree(), CoinWarmStartBasis::clone(), OsiSolverInterface::clone(), continuousInfeasibilities_, continuousObjective_, continuousSolver_, SbbNode::createInfo(), currentNumberCuts(), currentNumberCuts_, currentSolution_, dblParam_, SbbNodeInfo::decrement(), SbbCountRowCut::decrement(), OsiSolverInterface::deleteRows(), SbbNode::depth(), findIntegers(), getColLower(), OsiSolverInterface::getColSolution(), getColUpper(), getCutoff(), getIntegerTolerance(), getNumCols(), OsiSolverInterface::getNumRows(), getNumRows(), OsiSolverInterface::getObjSense(), OsiSolverInterface::getObjValue(), OsiSolverInterface::getRowCutDebugger(), OsiSolverInterface::getStrParam(), OsiSolverInterface::getWarmStart(), globalCuts_, handler_, SbbCountRowCut::increment(), SbbNodeInfo::increment(), SbbObject::infeasibility(), SbbNode::initializeInfo(), OsiSolverInterface::initialSolve(), integerVariable_, intParam_, isNodeLimitReached(), OsiSolverInterface::isProvenOptimal(), maximumCutPasses_, maximumCutPassesAtRoot_, maximumDepth_, maximumNumberCuts_, CoinMessageHandler::message(), OsiSolverInterface::messageHandler(), messageHandler(), messages(), messages_, nodeCompare_, SbbNode::nodeInfo(), SbbNode::numberBranches(), SbbNodeInfo::numberBranchesLeft(), numberHeuristics_, numberHeuristicSolutions_, numberIterations_, numberNodes_, numberObjects_, SbbNodeInfo::numberPointingToThis(), numberRowsAtContinuous_, numberSolutions_, SbbNode::numberUnsatisfied(), object_, SbbNode::objectiveValue(), OsiRowCutDebugger::onOptimalPath(), tree::pop(), CoinWarmStartBasis::print(), printFrequency_, tree::push(), SbbObject::resetBounds(), OsiSolverInterface::resolve(), resolve(), SbbAllowableGap, SbbInfeasibilityWeight, SbbMaximumSeconds, SbbMaxNumNode, SbbMaxNumSol, setBestSolution(), tree::setComparison(), setCutoff(), SbbNode::setGuessedObjectiveValue(), OsiSolverInterface::setHintParam(), CoinMessageHandler::setLogLevel(), SbbNode::setObjectiveValue(), SbbHeuristic::solution(), solver_, solveWithCuts(), status_, synchronizeModel(), takeOffCuts(), tree::top(), SbbNode::variable(), and walkback_. Referenced by originalModel(). { # ifdef SBB_DEBUG std::string problemName ; solver_->getStrParam(OsiProbName,problemName) ; printf("Problem name - %s\n",problemName.c_str()) ; solver_->setHintParam(OsiDoReducePrint,false,OsiHintDo,0) ; # endif /* Assume we're done, and see if we're proven wrong. */ status_ = 0 ; /* Scan the variables, noting the integer variables. Create an SbbSimpleInteger object for each integer variable. */ findIntegers(false) ; /* Ensure that objects on the lists of SbbObjects, heuristics, and cut generators attached to this model all refer to this model. */ synchronizeModel() ; /* Capture a time stamp before we start. */ double time1 = CoinCpuTime() ; /* Solve the relaxation. Apparently there are circumstances where this will be non-trivial --- i.e., we've done something since initialSolve that's trashed the solution to the continuous relaxation. */ bool feasible = resolve() ; /* If the linear relaxation of the root is infeasible, bail out now. Otherwise, continue with processing the root node. */ if (!feasible) { handler_->message(SBB_INFEAS,messages_)<< CoinMessageEol ; status_ = 1 ; return ; } # ifdef SBB_DEBUG /* OsiRowCutDebugger knows an optimal answer for a subset of MIP problems. Assuming it recognises the problem, when called upon it will check a cut to see if it cuts off the optimal answer. */ solver_->activateRowCutDebugger(problemName.c_str()) ; # endif /* Begin setup to process a feasible root node. */ bestObjective_ = 1.0e50 ; numberSolutions_ = 0 ; numberHeuristicSolutions_ = 0 ; // Everything is minimization double cutoff=getCutoff() ; double direction = solver_->getObjSense() ; if (cutoff < 1.0e20&&direction<0.0) messageHandler()->message(SBB_CUTOFF_WARNING1, messages()) << cutoff << -cutoff << CoinMessageEol ; if (cutoff > bestObjective_) cutoff = bestObjective_ ; setCutoff(cutoff) ; /* We probably already have a current solution, but just in case ... */ int numberColumns = getNumCols() ; if (!currentSolution_) currentSolution_ = new double[numberColumns] ; /* Create a copy of the solver, thus capturing the original (root node) constraint system (aka the continuous system). */ continuousSolver_ = solver_->clone() ; numberRowsAtContinuous_ = getNumRows() ; /* Check the objective to see if we can deduce a nontrivial increment. If it's better than the current value for SbbCutoffIncrement, it'll be installed. */ analyseObjective(*this) ; /* Set up for cut generation. addedCuts_ holds the cuts which are relevant for the active subproblem. whichGenerator will be used to record the generator that produced a given cut. */ int maximumWhich = 1000 ; int * whichGenerator = new int[maximumWhich] ; int currentNumberCuts = 0 ; maximumNumberCuts_ = 0 ; currentNumberCuts_ = 0 ; delete [] addedCuts_ ; addedCuts_ = NULL ; /* Set up an empty heap and associated data structures to hold the live set (problems which require further exploration). */ tree branchingTree ; SbbCompareObjective compareObjective ; SbbCompareDepth compareDepth ; SbbCompareDefault compareDefault(dblParam_[SbbInfeasibilityWeight]) ; if (!nodeCompare_) branchingTree.setComparison(compareDepth) ; else branchingTree.setComparison(*nodeCompare_) ; /* Used to record the path from a node to the root of the search tree, so that we can then traverse from the root to the node when restoring a subproblem. */ maximumDepth_ = 10 ; delete [] walkback_ ; walkback_ = new SbbNodeInfo * [maximumDepth_] ; /* Used to generate bound edits for SbbPartialNodeInfo. */ double * lowerBefore = new double [numberColumns] ; double * upperBefore = new double [numberColumns] ; /* Generate cuts at the root node and reoptimise. solveWithCuts does the heavy lifting. It will iterate a generate/reoptimise loop (including reduced cost fixing) until no cuts are generated, the change in objective falls off, or the limit on the number of rounds of cut generation is exceeded. At the end of all this, any cuts will be recorded in cuts and also installed in the solver's constraint system. We'll have reoptimised, and removed any slack cuts (numberOldActiveCuts and numberNewCuts have been adjusted accordingly). TODO: Why don't we make a copy of the solution after solveWithCuts? TODO: If numberUnsatisfied == 0, don't we have a solution? */ OsiCuts cuts ; int anyAction = -1 ; int numberOldActiveCuts = 0 ; int numberNewCuts = 0 ; { int iObject ; int preferredWay ; double otherWay ; int numberUnsatisfied = 0 ; double integerTolerance = getIntegerTolerance() ; memcpy(currentSolution_,solver_->getColSolution(), numberColumns*sizeof(double)) ; for (iObject = 0 ; iObject < numberObjects_ ; iObject++) { double infeasibility = object_[iObject]->infeasibility(preferredWay,otherWay) ; if (infeasibility > integerTolerance) numberUnsatisfied++ ; } if (numberUnsatisfied) { feasible = solveWithCuts(cuts,maximumCutPassesAtRoot_, NULL,numberOldActiveCuts,numberNewCuts, maximumWhich, whichGenerator) ; } } currentNumberCuts_ = numberNewCuts ; /* We've taken the continuous relaxation as far as we can. Time to branch. The first order of business is to actually create a node. chooseBranch currently uses strong branching to evaluate branch object candidates, unless forced back to simple branching. If chooseBranch concludes that a branching candidate is monotone (anyAction == -1) or infeasible (anyAction == -2) when forced to integer values, it returns here immediately. Monotone variables trigger a call to resolve(). If the problem remains feasible, try again to choose a branching variable. At the end of the loop, resolved == true indicates that some variables were fixed. Loss of feasibility will result in the deletion of newNode. */ bool resolved = false ; SbbNode *newNode = NULL ; if (feasible) { newNode = new SbbNode ; newNode->setObjectiveValue(direction*solver_->getObjValue()) ; anyAction = -1 ; while (anyAction == -1) { anyAction = newNode->chooseBranch(this,NULL) ; if (anyAction == -1) { feasible = resolve() ; resolved = true ; # ifdef SBB_DEBUG printf("Resolve (root) as something fixed, Obj value %g %d rows\n", solver_->getObjValue(), solver_->getNumRows()) ; # endif if (!feasible) anyAction = -2 ; } if (anyAction == -2) { delete newNode ; newNode = NULL ; feasible = false ; } } } /* At this point, the root subproblem is infeasible or fathomed by bound (newNode == NULL), or we're live with an objective value that satisfies the current objective cutoff. */ assert (!newNode || newNode->objectiveValue() < getCutoff()) ; /* The common case is that the lp relaxation is feasible but doesn't satisfy integrality (i.e., newNode->variable() >= 0, indicating we've been able to select a branching variable). Remove any cuts that have gone slack due to forcing monotone variables. Then tack on an SbbFullNodeInfo object and full basis (via createInfo()) and stash the new cuts in the nodeInfo (via addCuts()). If, by some miracle, we have an integral solution at the root (newNode->variable() < 0), takeOffCuts() will ensure that the solver holds a valid solution for use by setBestSolution(). */ CoinWarmStartBasis *lastws = 0 ; if (feasible && newNode->variable() >= 0) { if (resolved) { bool needValidSolution = (newNode->variable() < 0) ; takeOffCuts(cuts,whichGenerator,numberOldActiveCuts,numberNewCuts, needValidSolution) ; # ifdef CHECK_CUT_COUNTS { printf("Number of rows after chooseBranch fix (root)" "(active only) %d\n", numberRowsAtContinuous_+numberNewCuts+numberOldActiveCuts) ; const CoinWarmStartBasis* debugws = dynamic_cast <const CoinWarmStartBasis*>(solver_->getWarmStart()) ; debugws->print() ; delete debugws ; } # endif } newNode->createInfo(this,NULL,NULL,NULL,NULL,0,0) ; newNode->nodeInfo()->addCuts(cuts, newNode->numberBranches(),whichGenerator) ; /* Courtesy of createInfo, there's now a full basis stashed in newNode->nodeInfo_->basis_. We're about to make two more copies, lastws and model.basis_. (jf) With some thought I should be able to get rid of lastws and use basis_. (lh) I agree, but haven't pursued it to the end. */ if (basis_) delete basis_ ; basis_ = dynamic_cast<CoinWarmStartBasis*>(solver_->getWarmStart()) ; if (lastws) delete lastws ; lastws = dynamic_cast<CoinWarmStartBasis*>(basis_->clone()) ; } /* Continuous data to be used later */ continuousObjective_ = 0.0 ; continuousInfeasibilities_ = 0 ; if (newNode) { continuousObjective_ = newNode->objectiveValue() ; continuousInfeasibilities_ = newNode->numberUnsatisfied() ; } /* Bound may have changed so reset in objects */ { int i ; for (i = 0;i < numberObjects_;i++) object_[i]->resetBounds() ; } /* For printing totals */ numberIterations_ = 0 ; numberNodes_ = 0 ; bool stoppedOnGap = false ; /* Feasible? Then we should have either a live node prepped for future expansion (indicated by variable() >= 0), or (miracle of miracles) an integral solution at the root node. initializeInfo sets the reference counts in the nodeInfo object. Since this node is still live, push it onto the heap that holds the live set. */ if (newNode) { if (newNode->variable() >= 0) { newNode->initializeInfo() ; branchingTree.push(newNode) ; # ifdef CHECK_NODE printf("Node %x on tree\n",newNode) ; # endif } else { // continuous is integer double objectiveValue = newNode->objectiveValue(); setBestSolution(SBB_SOLUTION,objectiveValue, solver_->getColSolution()) ; delete newNode ; newNode = NULL ; } } if (printFrequency_ <= 0) { printFrequency_ = 1000 ; if (getNumCols() > 2000) printFrequency_ = 100 ; } /* At last, the actual branch-and-cut search loop, which will iterate until the live set is empty or we hit some limit (integrality gap, time, node count, etc.). The overall flow is to rebuild a subproblem, reoptimise using solveWithCuts(), choose a branching pattern with chooseBranch(), and finally add the node to the live set. The first action is to winnow the live set to remove nodes which are worse than the current objective cutoff. */ double bestValue = 0.0 ; while (!branchingTree.empty()) { if (cutoff > getCutoff()) { // Do from deepest branchingTree.cleanTree(this, getCutoff()) ; if (!nodeCompare_) { if (!compareDefault.getWeight()) { // set to get close to this double costPerInteger = (bestObjective_-continuousObjective_)/ ((double) continuousInfeasibilities_) ; compareDefault.setWeight(0.98*costPerInteger) ; /*printf("Setting weight per infeasibility to %g\n", 0.98*costPerInteger);*/ } branchingTree.setComparison(compareDefault) ; //branchingTree.setComparison(compareObjective) ; } else { nodeCompare_->newSolution(this) ; nodeCompare_->newSolution(this,continuousObjective_, continuousInfeasibilities_) ; branchingTree.setComparison(*nodeCompare_) ; } if (branchingTree.empty()) break; // finished } cutoff = getCutoff() ; /* Periodic activities: Opportunities to + tweak the nodeCompare criteria, + check if we've closed the integrality gap enough to quit, + print a summary line to let the user know we're working */ if ((numberNodes_%1000) == 0&&nodeCompare_) nodeCompare_->every1000Nodes(this, numberNodes_) ; if ((numberNodes_%printFrequency_) == 0) { int j ; int nNodes = branchingTree.size() ; bestValue = 1.0e100 ; for (j = 0;j < nNodes;j++) { SbbNode * node = branchingTree[j] ; if (node->objectiveValue() < bestValue) bestValue = node->objectiveValue() ; } messageHandler()->message(SBB_STATUS,messages()) << numberNodes_<< nNodes<< bestObjective_<< bestValue << CoinMessageEol ; // See if can stop on gap if (bestObjective_-bestValue < dblParam_[SbbAllowableGap]) { stoppedOnGap = true ; } } # ifdef CHECK_NODE_FULL verifyTreeNodes(branchingTree,*this) ; # endif # ifdef CHECK_CUT_COUNTS verifyCutCounts(branchingTree,*this) ; # endif /* Now we come to the meat of the loop. To create the active subproblem, we'll pop the most promising node in the live set, rebuild the subproblem it represents, and then execute the current arm of the branch to create the active subproblem. */ SbbNode *node = branchingTree.top() ; branchingTree.pop() ; # ifdef CHECK_NODE /* WARNING: The use of integerVariable_[*] here will break as soon as the branching object is something other than an integer variable. This needs some thought. */ printf("Node %x popped from tree - %d left, %d count\n",node, node->nodeInfo()->numberBranchesLeft(), node->nodeInfo()->numberPointingToThis()) ; printf("\tdepth = %d, z = %g, unsat = %d, var = %d.\n", node->depth(),node->objectiveValue(), node->numberUnsatisfied(), integerVariable_[node->variable()]) ; # endif /* Rebuild the subproblem for this node: Call addCuts() to adjust the model to recreate the subproblem for this node (set proper variable bounds, add cuts, create a basis). This may result in the problem being fathomed by bound or infeasibility. Returns 1 if node is fathomed. Execute the current arm of the branch: If the problem survives, save the resulting variable bounds and call branch() to modify variable bounds according to the current arm of the branching object. If we're processing the final arm of the branching object, flag the node for removal from the live set. */ SbbNodeInfo * nodeInfo = node->nodeInfo() ; newNode = NULL ; if (!addCuts(node,lastws)) { int i ; const double * lower = getColLower() ; const double * upper = getColUpper() ; for (i = 0 ; i < numberColumns ; i++) { lowerBefore[i]= lower[i] ; upperBefore[i]= upper[i] ; } bool deleteNode ; if (node->branch()) { branchingTree.push(node) ; deleteNode = false ; # ifdef CHECK_NODE printf("Node %x pushed back on tree - %d left, %d count\n",node, nodeInfo->numberBranchesLeft(), nodeInfo->numberPointingToThis()) ; # endif } else { deleteNode = true ; } # ifdef SBB_DEBUG /* This doesn't work as intended --- getRowCutDebugger will return null unless the current feasible solution region includes the optimal solution that RowCutDebugger knows. There's no way to tell inactive from off the optimal path. */ const OsiRowCutDebugger *debugger = solver_->getRowCutDebugger() ; if (debugger) { if(debugger->onOptimalPath(*solver_)) printf("On optimal path\n") ; else printf("Not on optimal path\n") ; } # endif /* Reoptimize, possibly generating cuts and/or using heuristics to find solutions. Cut reference counts are unaffected unless we lose feasibility, in which case solveWithCuts() will make the adjustment. */ cuts = OsiCuts() ; currentNumberCuts = solver_->getNumRows()-numberRowsAtContinuous_ ; feasible = solveWithCuts(cuts,maximumCutPasses_,node, numberOldActiveCuts,numberNewCuts, maximumWhich,whichGenerator) ; /* Check for abort on limits: node count, solution count, time, integrality gap. */ double totalTime = CoinCpuTime()-time1 ; if (numberNodes_ < intParam_[SbbMaxNumNode] && numberSolutions_ < intParam_[SbbMaxNumSol] && totalTime < dblParam_[SbbMaximumSeconds] && !stoppedOnGap) { /* Are we still feasible? If so, create a node and do the work to attach a branching object, reoptimising as needed if chooseBranch() identifies monotone objects. Finally, attach a partial nodeInfo object and store away any cuts that we created back in solveWithCuts. addCuts() will also deal with the cut reference counts. TODO: (lh) I'm confused. We create a nodeInfo without checking whether we have a solution or not. Then we use numberUnsatisfied() to decide whether to stash the cuts and bump reference counts. Other places we use variable() (i.e., presence of a branching variable). Equivalent? */ if (feasible) { newNode = new SbbNode ; newNode->setObjectiveValue(direction*solver_->getObjValue()) ; anyAction =-1 ; resolved = false ; while (anyAction == -1) { anyAction = newNode->chooseBranch(this,node) ; if (anyAction == -1) { feasible = resolve() ; resolved = true ; if (feasible) { newNode->setObjectiveValue(direction* solver_->getObjValue()) ; } else { anyAction = -2 ; } } } if (anyAction >= 0) { if (resolved) { bool needValidSolution = (newNode->variable() < 0) ; takeOffCuts(cuts,whichGenerator,numberOldActiveCuts, numberNewCuts,needValidSolution) ; # ifdef CHECK_CUT_COUNTS { printf("Number of rows after chooseBranch fix (node)" "(active only) %d\n", numberRowsAtContinuous_+numberNewCuts+ numberOldActiveCuts) ; const CoinWarmStartBasis* debugws = dynamic_cast<const CoinWarmStartBasis*> (solver_->getWarmStart()) ; debugws->print() ; delete debugws ; } # endif } newNode->createInfo(this,node,lastws,lowerBefore,upperBefore, numberOldActiveCuts,numberNewCuts) ; if (newNode->numberUnsatisfied()) newNode->nodeInfo()->addCuts(cuts,newNode->numberBranches(), whichGenerator) ; } } else { anyAction = -2 ; } // May have slipped through i.e. anyAction == 0 and objective above cutoff if ( anyAction >=0 ) { assert (newNode); if (newNode->objectiveValue() > getCutoff()) anyAction = -2; // say bad after all } /* If we end up infeasible, we can delete the new node immediately. Since this node won't be needing the cuts we collected, decrement the reference counts. If we are feasible, then we'll be placing this node into the live set, so increment the reference count in the current (parent) nodeInfo. */ if (anyAction == -2) { delete newNode ; newNode = NULL ; for (i = 0 ; i < currentNumberCuts_ ; i++) { if (addedCuts_[i]) { if (!addedCuts_[i]->decrement(1)) delete addedCuts_[i] ; } } } else { nodeInfo->increment() ; } /* At this point, there are three possibilities: * We have a live node (variable() >= 0) which will require further branching to resolve. Before we push it onto the search tree, try for a heuristic solution. * We have a solution, in which case newNode is non-null but we have no branching variable. Decrement the cut counts and save the solution. * The node was found to be infeasible, in which case it's already been deleted, and newNode is null. TODO: (lh) Now I'm more confused. I thought that the call to addCuts() above took care of incrementing the reference counts for cuts at newNode. Clearly I need to look more carefully. */ assert (!newNode || newNode->objectiveValue() <= getCutoff()) ; if (newNode) { if (newNode->variable() >= 0) { handler_->message(SBB_BRANCH,messages_) << numberNodes_<< newNode->objectiveValue() << newNode->numberUnsatisfied()<< newNode->depth() << integerVariable_[newNode->variable()] << newNode->variable() << CoinMessageEol ; // Increment cut counts (taking off current) int numberLeft = newNode->numberBranches() ; for (i = 0;i < currentNumberCuts_;i++) { if (addedCuts_[i]) { # ifdef CHECK_CUT_COUNTS printf("Count on cut %x increased by %d\n",addedCuts_[i], numberLeft-1) ; # endif addedCuts_[i]->increment(numberLeft-1) ; } } double estValue = 1.0e100 ; int found = -1 ; solver_->resolve() ; // double check current optimal double * newSolution = new double [numberColumns] ; double heurValue = getCutoff() ; int iHeur ; for (iHeur = 0 ; iHeur < numberHeuristics_ ; iHeur++) { double saveValue = heurValue ; int ifSol = heuristic_[iHeur]->solution(heurValue,newSolution) ; if (ifSol > 0) // new solution found { found = iHeur ; } else if (ifSol < 0) // just returning an estimate { estValue = min(heurValue,estValue) ; heurValue = saveValue ; } } if (found >= 0) { setBestSolution(SBB_ROUNDING,heurValue,newSolution) ; } delete [] newSolution ; newNode->setGuessedObjectiveValue(estValue) ; branchingTree.push(newNode) ; # ifdef CHECK_NODE printf("Node %x pushed on tree c\n",newNode) ; # endif } else { for (i = 0 ; i < currentNumberCuts_ ; i++) { if (addedCuts_[i]) { if (!addedCuts_[i]->decrement(1)) delete addedCuts_[i] ; } } double objectiveValue = newNode->objectiveValue(); setBestSolution(SBB_SOLUTION,objectiveValue, solver_->getColSolution()) ; assert(nodeInfo->numberPointingToThis() <= 2) ; // avoid accidental pruning, if newNode was final branch arm nodeInfo->increment(); delete newNode ; nodeInfo->decrement() ; } } /* This node has been completely expanded and can be removed from the live set. */ if (deleteNode) delete node ; } /* End of the non-abort actions. The next block of code is executed if we've aborted because we hit one of the limits. Clean up by deleting the live set and break out of the node processing loop. */ else { branchingTree.cleanTree(this,-DBL_MAX) ; if (stoppedOnGap) { messageHandler()->message(SBB_GAP,messages()) << bestObjective_-bestValue << dblParam_[SbbAllowableGap] << CoinMessageEol ; status_ = 0 ; } else if (isNodeLimitReached()) { handler_->message(SBB_MAXNODES,messages_) << CoinMessageEol ; status_ = 1 ; } else if (totalTime >= dblParam_[SbbMaximumSeconds]) { handler_->message(SBB_MAXTIME,messages_) << CoinMessageEol ; } else { handler_->message(SBB_MAXSOLS,messages_) << CoinMessageEol ; status_ = 1 ; } break ; } /* Delete cuts to get back to the original system. I'm thinking this is redundant --- the call to addCuts that conditions entry to this code block also performs this action. */ int numberToDelete = getNumRows()-numberRowsAtContinuous_ ; if (numberToDelete) { int * delRows = new int[numberToDelete] ; int i ; for (i = 0 ; i < numberToDelete ; i++) { delRows[i] = i+numberRowsAtContinuous_ ; } solver_->deleteRows(numberToDelete,delRows) ; delete [] delRows ; } } /* This node fathomed when addCuts atttempted to revive it. Toss it. */ else { delete node ; } } /* That's it, we've exhausted the search tree, or broken out of the loop because we hit some limit on evaluation. */ if (!status_) handler_->message(SBB_END_GOOD,messages_) << bestObjective_ << numberIterations_ << numberNodes_ << CoinMessageEol ; else handler_->message(SBB_END,messages_) << numberIterations_ << numberNodes_ << CoinMessageEol ; /* If we think we have a solution, restore and confirm it with a call to setBestSolution(). We need to reset the cutoff value so as not to fathom the solution on bounds. Note that calling setBestSolution( ..., true) leaves the continuousSolver_ bounds vectors fixed at the solution value. Running resolve() here is a failsafe --- setBestSolution has already reoptimised using the continuousSolver_. If for some reason we fail to prove optimality, run the problem again after instructing the solver to tell us more. If all looks good, replace solver_ with continuousSolver_, so that the outside world will be able to obtain information about the solution using public methods. */ if (bestSolution_) { setCutoff(1.0e50) ; // As best solution should be worse than cutoff setBestSolution(SBB_SOLUTION,bestObjective_,bestSolution_,true) ; continuousSolver_->resolve() ; if (!continuousSolver_->isProvenOptimal()) { continuousSolver_->messageHandler()->setLogLevel(2) ; continuousSolver_->initialSolve() ; } delete solver_ ; solver_ = continuousSolver_ ; continuousSolver_ = NULL ; } /* Clean up dangling objects. continuousSolver_ may already be toast. */ delete lastws ; delete [] whichGenerator ; delete [] lowerBefore ; delete [] upperBefore ; delete [] walkback_ ; walkback_ = NULL ; delete [] addedCuts_ ; addedCuts_ = NULL ; if (continuousSolver_) { delete continuousSolver_ ; continuousSolver_ = NULL ; } /* Destroy global cuts by replacing with an empty OsiCuts object. */ globalCuts_= OsiCuts() ; return ; }

double SbbModel::checkSolution (  double  cutoff, const double *  solution, bool  fixVariables )

Call this to really test if a valid solution can be feasible Solution is number columns in size. If fixVariables true then bounds of continuous solver updated. Returns objective value (worse than cutoff if not feasible) Definition at line 3418 of file SbbModel.cpp. References continuousSolver_, currentSolution_, SbbObject::feasibleRegion(), getColLower(), OsiSolverInterface::getColSolution(), getColUpper(), OsiSolverInterface::getDblParam(), OsiSolverInterface::getHintParam(), getIntegerTolerance(), OsiSolverInterface::getMatrixByCol(), OsiSolverInterface::getNumCols(), OsiSolverInterface::getNumRows(), OsiSolverInterface::getObjSense(), OsiSolverInterface::getObjValue(), OsiSolverInterface::getRowLower(), OsiSolverInterface::getRowUpper(), handler_, OsiSolverInterface::initialSolve(), OsiSolverInterface::isInteger(), OsiSolverInterface::isProvenOptimal(), CoinMessageHandler::message(), messages_, numberObjects_, object_, OsiSolverInterface::setColLower(), OsiSolverInterface::setColSolution(), OsiSolverInterface::setColUpper(), OsiSolverInterface::setHintParam(), OsiSolverInterface::setWarmStart(), and solver_. Referenced by setBestSolution(). { int numberColumns = solver_->getNumCols(); /* Grab the continuous solver (the pristine copy of the problem, made before starting to work on the root node). Save the bounds on the variables. Install the solution passed as a parameter, and copy it to the model's currentSolution_. TODO: This is a belt-and-suspenders approach. Once the code has settled a bit, we can cast a critical eye here. */ OsiSolverInterface * saveSolver = solver_; solver_ = continuousSolver_; // move solution to continuous copy solver_->setColSolution(solution); // Put current solution in safe place memcpy(currentSolution_,solver_->getColSolution(), numberColumns*sizeof(double)); //solver_->messageHandler()->setLogLevel(4); // save original bounds double * saveUpper = new double[numberColumns]; double * saveLower = new double[numberColumns]; memcpy(saveUpper,getColUpper(),numberColumns*sizeof(double)); memcpy(saveLower,getColLower(),numberColumns*sizeof(double)); /* Run through the objects and use feasibleRegion() to set variable bounds so as to fix the variables specified in the objects at their value in this solution. */ int i; for (i=0;i<numberObjects_;i++) object_[i]->feasibleRegion(); /* (lh) Original comment was ``solve with all slack basis so fixed will be clean''. A typical initialSolve will probably do this, but I'm asking ``Why the call to setWarmStart?'' (jf) The answer is that most "initialSolves" use current basis. (lh) Hmmm ... says to me that we should be more explicit in the OSI specifications. initialSolve should force the solver to do whatever it would do when handed a fresh problem? setWarmStart should manufacture an all-slack basis when handed an empty basis (or called without parameter)? (JF) But it is better to get the right answer. initialSolve should not force anything as solver should be saying - how can I solve this problem when I am a long way from optimal. I am putting back all slack basis as some problems are failing. */ CoinWarmStartBasis slack; solver_->setWarmStart(&slack); // Give a hint not to do scaling //bool saveTakeHint; //OsiHintStrength saveStrength; //bool gotHint = (solver_->getHintParam(OsiDoScale,saveTakeHint,saveStrength)); //assert (gotHint); //solver_->setHintParam(OsiDoScale,false,OsiHintTry); solver_->initialSolve(); //solver_->setHintParam(OsiDoScale,saveTakeHint,saveStrength); if (!solver_->isProvenOptimal()) { std::cout << "checkSolution infeas! Retrying wihout scaling." << std::endl ; bool saveTakeHint; OsiHintStrength saveStrength; bool savePrintHint; bool gotHint = (solver_->getHintParam(OsiDoReducePrint,savePrintHint,saveStrength)); gotHint = (solver_->getHintParam(OsiDoScale,saveTakeHint,saveStrength)); solver_->setHintParam(OsiDoScale,false,OsiHintTry); solver_->setHintParam(OsiDoReducePrint,false,OsiHintTry) ; solver_->initialSolve(); solver_->setHintParam(OsiDoScale,saveTakeHint,saveStrength); solver_->setHintParam(OsiDoReducePrint,savePrintHint,OsiHintTry) ; } assert(solver_->isProvenOptimal()); double objectiveValue = solver_->getObjValue()*solver_->getObjSense(); /* Check that the solution still beats the objective cutoff. If it passes, make a copy of the primal variable values and do some cleanup and checks: + Values of all variables are are within original bounds and values of all integer variables are within tolerance of integral. + There are no constraint violations. There really should be no need for the check against original bounds. Perhaps an opportunity for a sanity check? */ if (solver_->isProvenOptimal() && objectiveValue <= cutoff) { solution = solver_->getColSolution() ; memcpy(currentSolution_,solution,numberColumns*sizeof(double)) ; const double * rowLower = solver_->getRowLower() ; const double * rowUpper = solver_->getRowUpper() ; int numberRows = solver_->getNumRows() ; double *rowActivity = new double[numberRows] ; memset(rowActivity,0,numberRows*sizeof(double)) ; double integerTolerance = getIntegerTolerance() ; int iColumn; for (iColumn = 0 ; iColumn < numberColumns ; iColumn++) { double value = currentSolution_[iColumn] ; value = max(value, saveLower[iColumn]) ; value = min(value, saveUpper[iColumn]) ; if (solver_->isInteger(iColumn)) assert(fabs(value-currentSolution_[iColumn]) <= integerTolerance) ; currentSolution_[iColumn] = value ; } solver_->getMatrixByCol()->times(currentSolution_,rowActivity) ; double primalTolerance ; solver_->getDblParam(OsiPrimalTolerance,primalTolerance) ; double largestInfeasibility =0.0; for (i=0 ; i < numberRows ; i++) { largestInfeasibility = max(largestInfeasibility, rowLower[i]-rowActivity[i]); largestInfeasibility = max(largestInfeasibility, rowActivity[i]-rowUpper[i]); } if (largestInfeasibility>100.0*primalTolerance) handler_->message(SBB_NOTFEAS3, messages_) << largestInfeasibility << CoinMessageEol ; delete [] rowActivity ; } else { objectiveValue=1.0e50 ; } /* Regardless of what we think of the solution, we may need to restore the original bounds of the continuous solver. Unfortunately, const'ness prevents us from simply reversing the memcpy used to make these snapshots. */ if (!fixVariables) { for (int iColumn = 0 ; iColumn < numberColumns ; iColumn++) { solver_->setColLower(iColumn,saveLower[iColumn]) ; solver_->setColUpper(iColumn,saveUpper[iColumn]) ; } } delete [] saveLower; delete [] saveUpper; /* Restore the usual solver. */ solver_=saveSolver; return objectiveValue; }

double* SbbModel::currentSolution (   )  const [inline]

Solution to the most recent lp relaxation. The solver's solution to the most recent lp relaxation. Definition at line 624 of file SbbModel.hpp. References currentSolution_. Referenced by SbbSimpleInteger::createBranch(), SbbClique::createBranch(), SbbSimpleInteger::feasibleRegion(), SbbClique::feasibleRegion(), SbbSimpleInteger::infeasibility(), SbbClique::infeasibility(), SbbSimpleInteger::notPreferredNewFeasible(), and SbbSimpleInteger::preferredNewFeasible(). { return currentSolution_;};

bool SbbModel::feasibleSolution (  int &  numberIntegerInfeasibilities, int &  numberObjectInfeasibilities )  const

Test the current solution for feasiblility. Scan all objects for indications of infeasibility. This is broken down into simple integer infeasibility (numberIntegerInfeasibilities) and all other reports of infeasibility (numberObjectInfeasibilities). Definition at line 3671 of file SbbModel.cpp. References currentSolution_, OsiSolverInterface::getColSolution(), getIntegerTolerance(), OsiSolverInterface::getNumCols(), SbbObject::infeasibility(), numberIntegers_, numberObjects_, object(), object_, and solver_. Referenced by SbbNode::chooseBranch(), and originalModel(). { int numberUnsatisfied=0; double sumUnsatisfied=0.0; int preferredWay; double otherWay; double integerTolerance = getIntegerTolerance(); int j; // Put current solution in safe place memcpy(currentSolution_,solver_->getColSolution(), solver_->getNumCols()*sizeof(double)); for (j=0;j<numberIntegers_;j++) { const SbbObject * object = object_[j]; double infeasibility = object->infeasibility(preferredWay,otherWay); if (infeasibility>integerTolerance) { numberUnsatisfied++; sumUnsatisfied += infeasibility; } } numberIntegerInfeasibilities = numberUnsatisfied; for (;j<numberObjects_;j++) { const SbbObject * object = object_[j]; double infeasibility = object->infeasibility(preferredWay,otherWay); if (infeasibility>integerTolerance) { numberUnsatisfied++; sumUnsatisfied += infeasibility; } } numberObjectInfeasibilities = numberUnsatisfied-numberIntegerInfeasibilities; return (!numberUnsatisfied); }

SbbModel * SbbModel::findCliques (  bool  makeEquality, int  atLeastThisMany, int  lessThanThis, int  defaultValue = 1000 )

Identify cliques and construct corresponding objects. Find cliques with size in the range [atLeastThisMany, lessThanThis] and construct corresponding SbbClique objects. If makeEquality is true then a new model may be returned if modifications had to be made, otherwise this is returned. If the problem is infeasible numberObjects_ is set to -1. A client must use deleteObjects() before a second call to findCliques(). If priorities exist, clique priority is set to the default. Definition at line 2937 of file SbbModel.cpp. References OsiSolverInterface::addCol(), addObjects(), findIntegers(), getColLower(), getColUpper(), OsiSolverInterface::getMatrixByCol(), OsiSolverInterface::getMatrixByRow(), OsiSolverInterface::getNumCols(), OsiSolverInterface::getNumRows(), getRowLower(), getRowUpper(), integerVariable_, numberIntegers_, numberObjects_, object(), object_, originalColumns_, priority_, SbbModel(), OsiSolverInterface::setColLower(), OsiSolverInterface::setColUpper(), OsiSolverInterface::setInteger(), OsiSolverInterface::setRowLower(), OsiSolverInterface::setRowUpper(), solver(), solver_, and synchronizeModel(). { // No objects are allowed to exist assert(numberObjects_==numberIntegers_); CoinPackedMatrix matrixByRow(*solver_->getMatrixByRow()); int numberRows = solver_->getNumRows(); int numberColumns = solver_->getNumCols(); // We may want to add columns int numberSlacks=0; int * rows = new int[numberRows]; double * element =new double[numberRows]; int iRow; findIntegers(true); numberObjects_=numberIntegers_; int numberCliques=0; SbbObject ** object = new SbbObject * [numberRows]; int * which = new int[numberIntegers_]; char * type = new char[numberIntegers_]; int * lookup = new int[numberColumns]; int i; for (i=0;i<numberColumns;i++) lookup[i]=-1; for (i=0;i<numberIntegers_;i++) lookup[integerVariable_[i]]=i; // Statistics int totalP1=0,totalM1=0; int numberBig=0,totalBig=0; int numberFixed=0; // Row copy const double * elementByRow = matrixByRow.getElements(); const int * column = matrixByRow.getIndices(); const int * rowStart = matrixByRow.getVectorStarts(); const int * rowLength = matrixByRow.getVectorLengths(); // Column lengths for slacks const int * columnLength = solver_->getMatrixByCol()->getVectorLengths(); const double * lower = getColLower(); const double * upper = getColUpper(); const double * rowLower = getRowLower(); const double * rowUpper = getRowUpper(); for (iRow=0;iRow<numberRows;iRow++) { int numberP1=0, numberM1=0; int j; double upperValue=rowUpper[iRow]; double lowerValue=rowLower[iRow]; bool good=true; int slack = -1; for (j=rowStart[iRow];j<rowStart[iRow]+rowLength[iRow];j++) { int iColumn = column[j]; int iInteger=lookup[iColumn]; if (upper[iColumn]-lower[iColumn]<1.0e-8) { // fixed upperValue -= lower[iColumn]*elementByRow[j]; lowerValue -= lower[iColumn]*elementByRow[j]; continue; } else if (upper[iColumn]!=1.0||lower[iColumn]!=0.0) { good = false; break; } else if (iInteger<0) { good = false; break; } else { if (columnLength[iColumn]==1) slack = iInteger; } if (fabs(elementByRow[j])!=1.0) { good=false; break; } else if (elementByRow[j]>0.0) { which[numberP1++]=iInteger; } else { numberM1++; which[numberIntegers_-numberM1]=iInteger; } } int iUpper = (int) floor(upperValue+1.0e-5); int iLower = (int) ceil(lowerValue-1.0e-5); int state=0; if (upperValue<1.0e6) { if (iUpper==1-numberM1) state=1; else if (iUpper==-numberM1) state=2; else if (iUpper<-numberM1) state=3; } if (!state&&lowerValue>-1.0e6) { if (-iLower==1-numberP1) state=-1; else if (-iLower==-numberP1) state=-2; else if (-iLower<-numberP1) state=-3; } if (good&&state) { if (abs(state)==3) { // infeasible numberObjects_=-1; break; } else if (abs(state)==2) { // we can fix all numberFixed += numberP1+numberM1; if (state>0) { // fix all +1 at 0, -1 at 1 for (i=0;i<numberP1;i++) solver_->setColUpper(integerVariable_[which[i]],0.0); for (i=0;i<numberM1;i++) solver_->setColLower(integerVariable_[which[numberIntegers_-i-1]], 1.0); } else { // fix all +1 at 1, -1 at 0 for (i=0;i<numberP1;i++) solver_->setColLower(integerVariable_[which[i]],1.0); for (i=0;i<numberM1;i++) solver_->setColUpper(integerVariable_[which[numberIntegers_-i-1]], 0.0); } } else { int length = numberP1+numberM1; if (length >= atLeastThisMany&&length<lessThanThis) { // create object bool addOne=false; int objectType; if (iLower==iUpper) { objectType=1; } else { if (makeEquality) { objectType=1; element[numberSlacks]=state; rows[numberSlacks++]=iRow; addOne=true; } else { objectType=0; } } if (state>0) { totalP1 += numberP1; totalM1 += numberM1; for (i=0;i<numberP1;i++) type[i]=1; for (i=0;i<numberM1;i++) { which[numberP1]=which[numberIntegers_-i-1]; type[numberP1++]=0; } } else { totalP1 += numberM1; totalM1 += numberP1; for (i=0;i<numberP1;i++) type[i]=0; for (i=0;i<numberM1;i++) { which[numberP1]=which[numberIntegers_-i-1]; type[numberP1++]=1; } } if (addOne) { // add in slack which[numberP1]=numberIntegers_+numberSlacks-1; slack = numberP1; type[numberP1++]=1; } else if (slack >= 0) { for (i=0;i<numberP1;i++) { if (which[i]==slack) { slack=i; } } } object[numberCliques++] = new SbbClique(this,objectType,numberP1, which,type, 1000000+numberCliques,slack); } else if (numberP1+numberM1 >= lessThanThis) { // too big numberBig++; totalBig += numberP1+numberM1; } } } } delete [] which; delete [] type; delete [] lookup; if (numberCliques<0) { printf("*** Problem infeasible\n"); } else { if (numberCliques) printf("%d cliques of average size %g found, %d P1, %d M1\n", numberCliques, ((double)(totalP1+totalM1))/((double) numberCliques), totalP1,totalM1); else printf("No cliques found\n"); if (numberBig) printf("%d large cliques ( >= %d) found, total %d\n", numberBig,lessThanThis,totalBig); if (numberFixed) printf("%d variables fixed\n",numberFixed); } if (numberCliques>0&&numberSlacks&&makeEquality) { printf("adding %d integer slacks\n",numberSlacks); // add variables to make equality rows int * temp = new int[numberIntegers_+numberSlacks]; memcpy(temp,integerVariable_,numberIntegers_*sizeof(int)); // Get new model SbbModel * newModel = new SbbModel(*this); OsiSolverInterface * newSolver = newModel->solver(); for (i=0;i<numberSlacks;i++) { temp[i+numberIntegers_]=i+numberColumns; int iRow = rows[i]; double value = element[i]; double lowerValue = 0.0; double upperValue = 1.0; double objValue = 0.0; CoinPackedVector column(1,&iRow,&value); newSolver->addCol(column,lowerValue,upperValue,objValue); // set integer newSolver->setInteger(numberColumns+i); if (value >0) newSolver->setRowLower(iRow,rowUpper[iRow]); else newSolver->setRowUpper(iRow,rowLower[iRow]); } // replace list of integers for (i=0;i<newModel->numberObjects_;i++) delete newModel->object_[i]; newModel->numberObjects_ = 0; delete [] newModel->object_; newModel->object_=NULL; newModel->findIntegers(true); //Set up all integer objects if (priority_) { // old model had priorities delete [] newModel->priority_; newModel->priority_ = new int[newModel->numberIntegers_+numberCliques]; memcpy(newModel->priority_,priority_,numberIntegers_*sizeof(int)); for (i=numberIntegers_;i<newModel->numberIntegers_+numberCliques;i++) newModel->priority_[i]=defaultValue; } if (originalColumns_) { // old model had originalColumns delete [] newModel->originalColumns_; newModel->originalColumns_ = new int[numberColumns+numberSlacks]; memcpy(newModel->originalColumns_,originalColumns_,numberColumns*sizeof(int)); // mark as not in previous model for (i=numberColumns;i<numberColumns+numberSlacks;i++) newModel->originalColumns_[i]=-1; } delete [] rows; delete [] element; newModel->addObjects(numberCliques,object); for (;i<numberCliques;i++) delete object[i]; delete [] object; newModel->synchronizeModel(); return newModel; } else { if (numberCliques>0) { addObjects(numberCliques,object); for (;i<numberCliques;i++) delete object[i]; synchronizeModel(); } delete [] object; if (priority_) { // model had priorities int * temp = new int[numberIntegers_+numberCliques]; memcpy(temp,priority_,numberIntegers_*sizeof(int)); delete [] priority_; priority_=temp; for (i=numberIntegers_;i<numberIntegers_+numberCliques;i++) priority_[i]=defaultValue; } delete [] rows; delete [] element; return this; } }

void SbbModel::findIntegers (  bool  startAgain  )

Identify integer variables and create corresponding objects. Record integer variables and create an SbbSimpleInteger object for each one. If startAgain is true, a new scan is forced, overwriting any existing integer variable information. Definition at line 3300 of file SbbModel.cpp. References getNumCols(), handler_, integerVariable_, isInteger(), CoinMessageHandler::message(), messages_, numberIntegers_, numberObjects_, object_, and solver_. Referenced by branchAndBound(), deleteObjects(), findCliques(), integerPresolveThisModel(), originalModel(), and passInPriorities(). { assert(solver_); /* No need to do this if we have previous information, unless forced to start over. */ if (numberIntegers_&&!startAgain&&object_) return; /* Clear out the old integer variable list, then count the number of integer variables. */ delete [] integerVariable_; numberIntegers_=0; int numberColumns = getNumCols(); int iColumn; for (iColumn=0;iColumn<numberColumns;iColumn++) { if (isInteger(iColumn)) numberIntegers_++; } /* Found any? Allocate an array to hold the indices of the integer variables. If we don't already have an array of object pointers, make one. */ if (numberIntegers_) { if (!object_) { object_ = new SbbObject * [numberIntegers_]; memset(object_,0,numberIntegers_*sizeof(SbbObject *)); numberObjects_=numberIntegers_; } integerVariable_ = new int [numberIntegers_]; /* Walk the variables again, filling in the indices and creating objects for the integer variables. Initially, the objects hold the index and upper & lower bounds. */ numberIntegers_=0; for (iColumn=0;iColumn<numberColumns;iColumn++) { if(isInteger(iColumn)) { delete object_[numberIntegers_]; object_[numberIntegers_] = new SbbSimpleInteger(this,numberIntegers_,iColumn); integerVariable_[numberIntegers_++]=iColumn; } } } else { handler_->message(SBB_NOINT,messages_) << CoinMessageEol ; return; } }

double SbbModel::getAllowableGap (   )  const [inline]

Get the allowable gap between the best known solution and the best possible solution. Definition at line 377 of file SbbModel.hpp. References getDblParam(), and SbbAllowableGap. { return getDblParam(SbbAllowableGap); }

CoinWarmStartBasis * SbbModel::getEmptyBasis (  int  ns = 0, int  na = 0 )  const

Get an empty basis object. Return an empty basis object of the specified size A useful utility when constructing a basis for a subproblem from scratch. The object returned will be of the requested capacity and appropriate for the solver attached to the model. Definition at line 1232 of file SbbModel.cpp. References CoinWarmStart::clone(), emptyWarmStart_, OsiSolverInterface::getEmptyWarmStart(), CoinWarmStartBasis::setSize(), and solver_. Referenced by tree::cleanTree(). { CoinWarmStartBasis *emptyBasis ; /* Acquire an empty basis object, if we don't yet have one. */ if (emptyWarmStart_ == 0) { if (solver_ == 0) { throw CoinError("Cannot construct basis without solver!", "getEmptyBasis","SbbModel") ; } emptyBasis = dynamic_cast<CoinWarmStartBasis *>(solver_->getEmptyWarmStart()) ; if (emptyBasis == 0) { throw CoinError( "Solver does not appear to use a basis-oriented warm start.", "getEmptyBasis","SbbModel") ; } emptyBasis->setSize(0,0) ; emptyWarmStart_ = dynamic_cast<CoinWarmStart *>(emptyBasis) ; } /* Clone the empty basis object, resize it as requested, and return. */ emptyBasis = dynamic_cast<CoinWarmStartBasis *>(emptyWarmStart_->clone()) ; assert(emptyBasis) ; if (ns != 0 || na != 0) emptyBasis->setSize(ns,na) ; return (emptyBasis) ; }

double SbbModel::getInfeasibilityWeight (   )  const [inline]

Get the weight per integer infeasibility Definition at line 364 of file SbbModel.hpp. References getDblParam(), and SbbInfeasibilityWeight. { return getDblParam(SbbInfeasibilityWeight); }

double SbbModel::getIntegerTolerance (   )  const [inline]

Get the integrality tolerance Definition at line 349 of file SbbModel.hpp. References getDblParam(), and SbbIntegerTolerance. Referenced by branchAndBound(), checkSolution(), and feasibleSolution(). { return getDblParam(SbbIntegerTolerance); }

int SbbModel::getMaximumCutPasses (   )  const [inline]

Get the maximum number of cut passes at other nodes (default 10) Definition at line 408 of file SbbModel.hpp. References maximumCutPasses_. { return maximumCutPasses_;};

int SbbModel::getMaximumCutPassesAtRoot (   )  const [inline]

Get the maximum number of cut passes at root node Definition at line 400 of file SbbModel.hpp. References maximumCutPassesAtRoot_. { return maximumCutPassesAtRoot_;};

int SbbModel::getMaximumSolutions (   )  const [inline]

Get the maximum number of solutions desired. Definition at line 336 of file SbbModel.hpp. References getIntParam(), and SbbMaxNumSol. { return getIntParam(SbbMaxNumSol); }

const double* SbbModel::getRightHandSide (   )  const [inline]

Get pointer to array[getNumRows()] of rows right-hand sides if rowsense()[i] == 'L' then rhs()[i] == rowupper()[i] if rowsense()[i] == 'G' then rhs()[i] == rowlower()[i] if rowsense()[i] == 'R' then rhs()[i] == rowupper()[i] if rowsense()[i] == 'N' then rhs()[i] == 0.0 Definition at line 529 of file SbbModel.hpp. References OsiSolverInterface::getRightHandSide(), and solver_. { return solver_->getRightHandSide();};

const double* SbbModel::getRowRange (   )  const [inline]

Get pointer to array[getNumRows()] of row ranges. if rowsense()[i] == 'R' then rowrange()[i] == rowupper()[i] - rowlower()[i] if rowsense()[i] != 'R' then rowrange()[i] is 0.0 Definition at line 540 of file SbbModel.hpp. References OsiSolverInterface::getRowRange(), and solver_. { return solver_->getRowRange();};

const char* SbbModel::getRowSense (   )  const [inline]

Get pointer to array[getNumRows()] of row constraint senses. 'L': <= constraint 'E': = constraint 'G': >= constraint 'R': ranged constraint 'N': free constraint Definition at line 518 of file SbbModel.hpp. References OsiSolverInterface::getRowSense(), and solver_. { return solver_->getRowSense();};

void SbbModel::initialSolve (   )

Solve the initial LP relaxation. Invoke the solver's initialSolve() method. Definition at line 1217 of file SbbModel.cpp. References OsiSolverInterface::initialSolve(), and solver_. { assert (solver_); solver_->initialSolve(); }

SbbModel * SbbModel::integerPresolve (  bool  weak = false  )

Do integer presolve, creating a new (presolved) model. Returns the new model, or NULL if feasibility is lost. If weak is true then just does a normal presolve Todo: It remains to work out the cleanest way of getting a solution to the original problem at the end. So this is very preliminary. Definition at line 4078 of file SbbModel.cpp. References handler_, integerPresolveThisModel(), CoinMessageHandler::message(), messageHandler(), messages_, resolve(), SbbModel(), CoinMessageHandler::setLogLevel(), solver_, status_, and synchronizeModel(). { status_ = 0; // solve LP bool feasible = resolve(); SbbModel * newModel = NULL; if (feasible) { // get a new model newModel = new SbbModel(*this); newModel->messageHandler()->setLogLevel(messageHandler()->logLevel()); feasible = newModel->integerPresolveThisModel(solver_,weak); } if (!feasible) { handler_->message(SBB_INFEAS,messages_) <<CoinMessageEol; status_ = 1; delete newModel; return NULL; } else { newModel->synchronizeModel(); // make sure everything that needs solver has it return newModel; } }

bool SbbModel::integerPresolveThisModel (  OsiSolverInterface *  originalSolver, bool  weak = false )

Do integer presolve, modifying the current model. Returns true if the model remains feasible after presolve. Definition at line 4108 of file SbbModel.cpp. References OsiSolverInterface::activateRowCutDebugger(), addedCuts_, bestObjective_, OsiSolverInterface::clone(), continuousSolver_, OsiSolverInterface::copyParameters(), currentNumberCuts_, currentSolution_, dblParam_, deleteObjects(), findIntegers(), OsiSolverInterface::getColLower(), getColLower(), OsiSolverInterface::getColUpper(), getColUpper(), getCutoff(), OsiClpSolverInterface::getModelPtr(), OsiClpSolverInterface::getNumCols(), getNumCols(), getNumRows(), OsiSolverInterface::getObjCoefficients(), OsiSolverInterface::getObjSense(), OsiSolverInterface::getRowCutDebugger(), OsiSolverInterface::getStrParam(), integerVariable_, isInteger(), OsiSolverInterface::isInteger(), maximumCutPassesAtRoot_, maximumDepth_, maximumNumberCuts_, CoinMessageHandler::message(), messageHandler(), messages(), numberHeuristics_, numberHeuristicSolutions_, numberIntegers_, numberRowsAtContinuous_, numberSolutions_, OsiRowCutDebugger::onOptimalPath(), originalColumns_, priority_, resolve(), SbbCutoffIncrement, setBestSolution(), OsiSolverInterface::setColLower(), OsiSolverInterface::setColUpper(), setCutoff(), SbbHeuristic::solution(), solver_, solveWithCuts(), status_, synchronizeModel(), and walkback_. Referenced by integerPresolve(). { status_ = 0; // solve LP bool feasible = resolve(); bestObjective_=1.0e50; numberSolutions_=0; numberHeuristicSolutions_=0; double cutoff = getCutoff() ; double direction = solver_->getObjSense(); if (cutoff < 1.0e20&&direction<0.0) messageHandler()->message(SBB_CUTOFF_WARNING1, messages()) << cutoff << -cutoff << CoinMessageEol ; if (cutoff > bestObjective_) cutoff = bestObjective_ ; setCutoff(cutoff) ; int iColumn; int numberColumns = getNumCols(); int originalNumberColumns = numberColumns; int numberPasses=0; synchronizeModel(); // make sure everything that needs solver has it // just point to solver_ delete continuousSolver_; continuousSolver_ = solver_; // get a copy of original so we can fix bounds OsiSolverInterface * cleanModel = originalSolver->clone(); #ifdef SBB_DEBUG std::string problemName; cleanModel->getStrParam(OsiProbName,problemName); printf("Problem name - %s\n",problemName.c_str()); cleanModel->activateRowCutDebugger(problemName.c_str()); const OsiRowCutDebugger * debugger = cleanModel->getRowCutDebugger(); #endif // array which points from original columns to presolved int * original = new int[numberColumns]; // arrays giving bounds - only ones found by probing // rest will be found by presolve double * originalLower = new double[numberColumns]; double * originalUpper = new double[numberColumns]; { const double * lower = getColLower(); const double * upper = getColUpper(); for (iColumn=0;iColumn<numberColumns;iColumn++) { original[iColumn]=iColumn; originalLower[iColumn] = lower[iColumn]; originalUpper[iColumn] = upper[iColumn]; } } findIntegers(true); // save original integers int * originalPriority = NULL; int * originalIntegers = new int[numberIntegers_]; int originalNumberIntegers = numberIntegers_; memcpy(originalIntegers,integerVariable_,numberIntegers_*sizeof(int)); if (priority_) { originalPriority = new int[numberIntegers_]; memcpy(originalPriority,priority_,numberIntegers_*sizeof(int)); delete [] priority_; priority_=NULL; } int todo=20; if (weak) todo=1; while (numberPasses<todo) { numberPasses++; numberSolutions_=0; // this will be set false to break out of loop with presolved problem bool doIntegerPresolve=(numberPasses!=20); // Current number of free integer variables // Get increment in solutions { const double * objective = cleanModel->getObjCoefficients(); const double * lower = cleanModel->getColLower(); const double * upper = cleanModel->getColUpper(); double maximumCost=0.0; bool possibleMultiple=true; int numberChanged=0; for (iColumn=0;iColumn<originalNumberColumns;iColumn++) { if (originalUpper[iColumn]>originalLower[iColumn]) { if( cleanModel->isInteger(iColumn)) { maximumCost = max(maximumCost,fabs(objective[iColumn])); } else if (objective[iColumn]) { possibleMultiple=false; } } if (originalUpper[iColumn]<upper[iColumn]) { #ifdef SBB_DEBUG printf("Changing upper bound on %d from %g to %g\n", iColumn,upper[iColumn],originalUpper[iColumn]); #endif cleanModel->setColUpper(iColumn,originalUpper[iColumn]); numberChanged++; } if (originalLower[iColumn]>lower[iColumn]) { #ifdef SBB_DEBUG printf("Changing lower bound on %d from %g to %g\n", iColumn,lower[iColumn],originalLower[iColumn]); #endif cleanModel->setColLower(iColumn,originalLower[iColumn]); numberChanged++; } } // if first pass - always try if (numberPasses==1) numberChanged += 1; if (possibleMultiple) { int increment=0; double multiplier = 2520.0; while (10.0*multiplier*maximumCost<1.0e8) multiplier *= 10.0; for (iColumn=0;iColumn<originalNumberColumns;iColumn++) { if (originalUpper[iColumn]>originalLower[iColumn]) { if( isInteger(iColumn)&&objective[iColumn]) { double value = fabs(objective[iColumn])*multiplier; int nearest = (int) floor(value+0.5); if (fabs(value-floor(value+0.5))>1.0e-8) { increment=0; break; // no good } else if (!increment) { // first increment=nearest; } else { increment = gcd(increment,nearest); } } } } if (increment) { double value = increment; value /= multiplier; if (value*0.999>dblParam_[SbbCutoffIncrement]) { messageHandler()->message(SBB_INTEGERINCREMENT,messages()) <<value <<CoinMessageEol; dblParam_[SbbCutoffIncrement]=value*0.999; } } } if (!numberChanged) { doIntegerPresolve=false; // not doing any better } } #ifdef SBB_DEBUG if (debugger) assert(debugger->onOptimalPath(*cleanModel)); #endif #ifdef COIN_USE_CLP // do presolve - for now just clp but easy to get osi interface OsiClpSolverInterface * clpSolver = dynamic_cast<OsiClpSolverInterface *> (cleanModel); assert (clpSolver); ClpSimplex * clp = clpSolver->getModelPtr(); ClpPresolve pinfo; ClpSimplex * model2 = pinfo.presolvedModel(*clp,1.0e-8); if (!model2) { // presolve found to be infeasible feasible=false; } else { // update original array const int * originalColumns = pinfo.originalColumns(); // just slot in new solver OsiClpSolverInterface * temp = new OsiClpSolverInterface(model2); numberColumns = temp->getNumCols(); for (iColumn=0;iColumn<originalNumberColumns;iColumn++) original[iColumn]=-1; for (iColumn=0;iColumn<numberColumns;iColumn++) original[originalColumns[iColumn]]=iColumn; // copy parameters temp->copyParameters(*solver_); delete solver_; solver_ = temp; setCutoff(cutoff); deleteObjects(); synchronizeModel(); // make sure everything that needs solver has it // just point to solver_ continuousSolver_ = solver_; feasible=resolve(); if (!feasible||!doIntegerPresolve||weak) break; // see if we can get solution by heuristics int found=-1; int iHeuristic; double * newSolution = new double [numberColumns]; double heuristicValue=getCutoff(); for (iHeuristic=0;iHeuristic<numberHeuristics_;iHeuristic++) { double saveValue=heuristicValue; int ifSol = heuristic_[iHeuristic]->solution(heuristicValue, newSolution); if (ifSol>0) { // better solution found found=iHeuristic; } else if (ifSol<0) { heuristicValue = saveValue; } } if (found >= 0) { // We probably already have a current solution, but just in case ... int numberColumns = getNumCols() ; if (!currentSolution_) currentSolution_ = new double[numberColumns] ; // better solution save setBestSolution(SBB_ROUNDING,heuristicValue, newSolution); // update cutoff cutoff = getCutoff(); } delete [] newSolution; // Space for type of cuts int maximumWhich=1000; int * whichGenerator = new int[maximumWhich]; // save number of rows numberRowsAtContinuous_ = getNumRows(); maximumNumberCuts_=0; currentNumberCuts_=0; delete [] addedCuts_; addedCuts_ = NULL; // maximum depth for tree walkback maximumDepth_=10; delete [] walkback_; walkback_ = new SbbNodeInfo * [maximumDepth_]; OsiCuts cuts; int numberOldActiveCuts=0; int numberNewCuts = 0; feasible = solveWithCuts(cuts,maximumCutPassesAtRoot_, NULL,numberOldActiveCuts,numberNewCuts, maximumWhich, whichGenerator); currentNumberCuts_=numberNewCuts; delete [] whichGenerator; delete [] walkback_; walkback_ = NULL; delete [] addedCuts_; addedCuts_=NULL; if (feasible) { // fix anything in original which integer presolve fixed // for now just integers const double * lower = solver_->getColLower(); const double * upper = solver_->getColUpper(); int i; for (i=0;i<originalNumberIntegers;i++) { iColumn = originalIntegers[i]; int jColumn = original[iColumn]; if (jColumn >= 0) { if (upper[jColumn]<originalUpper[iColumn]) originalUpper[iColumn] = upper[jColumn]; if (lower[jColumn]>originalLower[iColumn]) originalLower[iColumn] = lower[jColumn]; } } } } #endif if (!feasible||!doIntegerPresolve) { break; } } //solver_->writeMps("xx"); delete cleanModel; // create new priorities and save list of original columns if (originalPriority) { priority_ = new int[numberIntegers_]; int i; int number=0; // integer variables are in same order if they exist at all for (i=0;i<originalNumberIntegers;i++) { iColumn = originalIntegers[i]; int newColumn=original[iColumn]; if (newColumn >= 0) priority_[number++]=originalPriority[i]; } assert (number==numberIntegers_); delete [] originalPriority; } delete [] originalIntegers; numberColumns = getNumCols(); delete [] originalColumns_; originalColumns_ = new int[numberColumns]; numberColumns=0; for (iColumn=0;iColumn<originalNumberColumns;iColumn++) { int jColumn = original[iColumn]; if (jColumn >= 0) originalColumns_[numberColumns++]=iColumn; } delete [] original; delete [] originalLower; delete [] originalUpper; deleteObjects(); synchronizeModel(); // make sure everything that needs solver has it continuousSolver_=NULL; currentNumberCuts_=0; return feasible; }

bool SbbModel::isInteger (  int  colIndex  )  const [inline]

Return true if column is integer. Note: This function returns true if the the column is binary or a general integer. Definition at line 571 of file SbbModel.hpp. References OsiSolverInterface::isInteger(), and solver_. Referenced by findIntegers(), and integerPresolveThisModel(). { return solver_->isInteger(colIndex);};

int SbbModel::numberStrong (   )  const [inline]

Get the maximum number of candidates to be evaluated for strong branching. Definition at line 420 of file SbbModel.hpp. References numberStrong_. Referenced by SbbNode::chooseBranch(), SbbParam::intParameter(), and SbbParam::setIntParameter(). { return numberStrong_;};

void SbbModel::passInPriorities (  const int *  priorities, bool  ifClique, int  defaultValue = 1000 )

Pass in branching priorities. If ifClique then priorities are on cliques otherwise priorities are on integer variables. Other type (if exists set to default) 1 is highest priority. (well actually -INT_MAX is but that's ugly) If a priority < forcePriority() then branches are created to force the variable to the value given by best solution. This enables a sort of hot start. The node choice should be greatest depth and forcePriority should normally be switched off after a solution. Definition at line 3231 of file SbbModel.cpp. References findIntegers(), numberIntegers_, numberObjects_, and priority_. { findIntegers(false); int i; if (!priority_) { priority_ = new int[numberObjects_]; for (i=0;i<numberObjects_;i++) priority_[i]=defaultValue; } if (priorities) { if (ifObject) memcpy(priority_+numberIntegers_,priorities, (numberObjects_-numberIntegers_)*sizeof(int)); else memcpy(priority_,priorities,numberIntegers_*sizeof(int)); } }

void SbbModel::reducedCostFix (   )

Perform reduced cost fixing Fixes integer variables at their current value based on reduced cost penalties. Definition at line 2118 of file SbbModel.cpp. References OsiSolverInterface::getColLower(), OsiSolverInterface::getColSolution(), OsiSolverInterface::getColUpper(), getCutoff(), getDblParam(), OsiSolverInterface::getObjSense(), OsiSolverInterface::getObjValue(), OsiSolverInterface::getReducedCost(), integerVariable_, numberIntegers_, SbbIntegerTolerance, OsiSolverInterface::setColLower(), OsiSolverInterface::setColUpper(), and solver_. Referenced by solveWithCuts(). { double cutoff = getCutoff() ; double direction = solver_->getObjSense() ; double gap = cutoff - solver_->getObjValue()*direction ; double integerTolerance = getDblParam(SbbIntegerTolerance) ; const double *lower = solver_->getColLower() ; const double *upper = solver_->getColUpper() ; const double *solution = solver_->getColSolution() ; const double *reducedCost = solver_->getReducedCost() ; int numberFixed = 0 ; for (int i = 0 ; i < numberIntegers_ ; i++) { int iColumn = integerVariable_[i] ; double djValue = direction*reducedCost[iColumn] ; if (upper[iColumn]-lower[iColumn] > integerTolerance) { if (solution[iColumn] < lower[iColumn]+integerTolerance && djValue > gap) { solver_->setColUpper(iColumn,lower[iColumn]) ; numberFixed++ ; } else if (solution[iColumn] > upper[iColumn]-integerTolerance && -djValue > gap) { solver_->setColLower(iColumn,upper[iColumn]) ; numberFixed++ ; } } } return ; }

bool SbbModel::resolve (   )

Reoptimise an LP relaxation. Invoke the solver's resolve() method. Definition at line 2905 of file SbbModel.cpp. References getIterationCount(), OsiSolverInterface::getNumRows(), OsiSolverInterface::getRowLower(), OsiSolverInterface::getRowUpper(), OsiSolverInterface::isDualObjectiveLimitReached(), OsiSolverInterface::isProvenOptimal(), numberIterations_, numberRowsAtContinuous_, OsiSolverInterface::resolve(), and solver_. Referenced by branchAndBound(), integerPresolve(), integerPresolveThisModel(), originalModel(), and solveWithCuts(). { // We may have deliberately added in violated cuts - check to avoid message int iRow; int numberRows = solver_->getNumRows(); const double * rowLower = solver_->getRowLower(); const double * rowUpper = solver_->getRowUpper(); bool feasible=true; for (iRow= numberRowsAtContinuous_;iRow<numberRows;iRow++) { if (rowLower[iRow]>rowUpper[iRow]+1.0e-8) feasible=false; } /* Reoptimize. Consider the possibility that we should fathom on bounds. But be careful --- where the objective takes on integral values, we may want to keep a solution where the objective is right on the cutoff. */ if (feasible) { solver_->resolve() ; numberIterations_ += getIterationCount() ; feasible = (solver_->isProvenOptimal() && !solver_->isDualObjectiveLimitReached()) ; } return feasible ; }

bool SbbModel::setAllowableGap (  double  value  )  [inline]

Set the allowable gap between the best known solution and the best possible solution. Definition at line 371 of file SbbModel.hpp. References SbbAllowableGap, and setDblParam(). { return setDblParam(SbbAllowableGap,value); }

void SbbModel::setBranchingMethod (  SbbBranchDecision &  method  )  [inline]

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts. Set the branching method Definition at line 713 of file SbbModel.hpp. References branchingMethod_. { branchingMethod_ = &method;};

void SbbModel::setCutoff (  double  value  )

Set cutoff bound on the objective function. When using strict comparison, the bound is adjusted by a tolerance to avoid accidentally cutting off the optimal solution. Definition at line 3388 of file SbbModel.cpp. References OsiSolverInterface::getDblParam(), getIntParam(), OsiSolverInterface::getObjSense(), SbbFathomDiscipline, OsiSolverInterface::setDblParam(), and solver_. Referenced by branchAndBound(), integerPresolveThisModel(), setBestSolution(), and tightenVubs(). { double tol = 0 ; int fathomStrict = getIntParam(SbbFathomDiscipline) ; double direction = solver_->getObjSense(); if (fathomStrict == 1) { solver_->getDblParam(OsiDualTolerance,tol) ; tol = tol*(1+fabs(value)) ; value += tol ; } // Solvers know about direction solver_->setDblParam(OsiDualObjectiveLimit,value*direction); }

bool SbbModel::setInfeasibilityWeight (  double  value  )  [inline]

Set the weight per integer infeasibility Definition at line 357 of file SbbModel.hpp. References SbbInfeasibilityWeight, and setDblParam(). { return setDblParam(SbbInfeasibilityWeight,value); }

bool SbbModel::setIntegerTolerance (  double  value  )  [inline]

Set the integrality tolerance Definition at line 343 of file SbbModel.hpp. References SbbIntegerTolerance, and setDblParam(). { return setDblParam(SbbIntegerTolerance,value); }

void SbbModel::setMaximumCutPasses (  int  value  )  [inline]

Set the maximum number of cut passes at other nodes (default 10) Minimum drop can also be used for fine tuning Definition at line 405 of file SbbModel.hpp. References maximumCutPasses_. {maximumCutPasses_=value;};

void SbbModel::setMaximumCutPassesAtRoot (  int  value  )  [inline]

Set the maximum number of cut passes at root node (default 20) Minimum drop can also be used for fine tuning Definition at line 397 of file SbbModel.hpp. References maximumCutPassesAtRoot_. {maximumCutPassesAtRoot_=value;};

bool SbbModel::setMaximumSolutions (  int  value  )  [inline]

Set the maximum number of solutions desired. Definition at line 329 of file SbbModel.hpp. References SbbMaxNumSol, and setIntParam(). { return setIntParam(SbbMaxNumSol,value); }

void SbbModel::setNumberStrong (  int  number  )

Set the maximum number of candidates to be evaluated for strong branching. A value of 0 disables strong branching. Definition at line 1856 of file SbbModel.cpp. References numberStrong_. Referenced by SbbParam::setIntParameter(). { if (number<0) numberStrong_=0; else numberStrong_=number; }

void SbbModel::setPrintFrequency (  int  number  )  [inline]

Set the print frequency. Controls the number of nodes evaluated between status prints. If number <=0 the print frequency is set to 100 nodes for large problems, 1000 for small problems. Print frequency has very slight overhead if small. Definition at line 430 of file SbbModel.hpp. References printFrequency_. { printFrequency_=number;};

bool SbbModel::solveWithCuts (  OsiCuts &  cuts, int  numberTries, SbbNode *  node, int &  numberOldActiveCuts, int &  numberNewCuts, int &  maximumWhich, int *&  whichGenerator )

Evaluate a subproblem using cutting planes and heuristics. The method invokes a main loop which generates cuts, applies heuristics, and reoptimises using the solver's native resolve() method. It returns true if the subproblem remains feasible at the end of the evaluation. Definition at line 2163 of file SbbModel.cpp. References addCuts(), addedCuts_, OsiSolverInterface::applyRowCuts(), basis_, OsiCuts::colCutPtr(), currentNumberCuts_, SbbCountRowCut::decrement(), SbbCutGenerator::generateCuts(), OsiSolverInterface::getColLower(), OsiSolverInterface::getColSolution(), OsiSolverInterface::getColUpper(), getCutoff(), getDblParam(), CoinPackedVector::getElements(), CoinPackedVector::getIndices(), OsiSolverInterface::getIterationCount(), OsiSolverInterface::getNumCols(), CoinPackedVector::getNumElements(), OsiSolverInterface::getNumRows(), OsiSolverInterface::getObjSense(), OsiSolverInterface::getObjValue(), OsiSolverInterface::getRowCutDebugger(), OsiSolverInterface::getWarmStart(), globalCuts_, OsiCut::globallyValid(), handler_, SbbCutGenerator::howOften(), howOftenGlobalScan_, OsiCuts::insert(), OsiRowCutDebugger::invalidCut(), OsiSolverInterface::isDualObjectiveLimitReached(), OsiSolverInterface::isProvenOptimal(), OsiColCut::lbs(), CoinMessageHandler::logLevel(), CoinMessageHandler::message(), messages_, minimumDrop_, numberCutGenerators_, numberHeuristics_, numberNodes_, numberRowsAtContinuous_, OsiRowCutDebugger::onOptimalPath(), CoinWarmStartBasis::print(), OsiCuts::printCuts(), reducedCostFix(), CoinWarmStartBasis::resize(), resolve(), OsiCuts::rowCut(), OsiCuts::rowCutPtr(), SbbIntegerTolerance, CoinWarmStartBasis::setArtifStatus(), setBestSolution(), OsiSolverInterface::setColLower(), OsiSolverInterface::setColUpper(), OsiSolverInterface::setWarmStart(), OsiCuts::sizeColCuts(), OsiCuts::sizeRowCuts(), solver_, takeOffCuts(), OsiColCut::ubs(), OsiRowCut::violated(), and OsiColCut::violated(). Referenced by branchAndBound(), and integerPresolveThisModel(). : numberTries: (i) the maximum number of iterations for this round of cut generation; no a priori limit if 0 cuts: (o) all cuts generated in this round of cut generation whichGenerator: (i/o) whichGenerator[i] is loaded with the index of the generator that produced cuts[i]; reallocated as required numberOldActiveCuts: (o) the number of active cuts at this node from previous rounds of cut generation numberNewCuts: (o) the number of cuts produced in this round of cut generation maximumWhich: (i/o) capacity of whichGenerator; may be updated if whichGenerator grows. node: (currently unused) */ { bool feasible = true ; int lastNumberCuts = 0 ; double lastObjective = -1.0e100 ; int violated = 0 ; int numberRowsAtStart = solver_->getNumRows() ; int numberColumns = solver_->getNumCols() ; numberOldActiveCuts = numberRowsAtStart-numberRowsAtContinuous_ ; numberNewCuts = 0 ; # ifdef SBB_DEBUG /* See OsiRowCutDebugger for details. In a nutshell, make sure that current variable values do not conflict with a known optimal solution. (Obviously this can be fooled when there are multiple solutions.) */ bool onOptimalPath = false ; const OsiRowCutDebugger *debugger = solver_->getRowCutDebugger() ; if (debugger) onOptimalPath = (debugger->onOptimalPath(*solver_)) ; # endif /* Resolve the problem. If we've lost feasibility, might as well bail out right after the debug stuff. */ feasible = resolve() ; #ifdef SBB_DEBUG if (feasible) { printf("Obj value %g (%s) %d rows\n",solver_->getObjValue(), (solver_->isProvenOptimal())?"proven":"unproven", solver_->getNumRows()) ; } else { printf("Infeasible %d rows\n",solver_->getNumRows()) ; } /* If the RowCutDebugger said we were compatible with the optimal solution, and now we're suddenly infeasible, we might be confused. Then again, we may have fathomed by bound, heading for a rediscovery of an optimal solution. */ if (onOptimalPath && !solver_->isDualObjectiveLimitReached()) assert(feasible) ; # endif if (!feasible) return (false) ; /* Do reduced cost fixing, and then grab the primal solution and bounds vectors. */ reducedCostFix() ; const double *lower = solver_->getColLower() ; const double *upper = solver_->getColUpper() ; const double *solution = solver_->getColSolution() ; /* Set up for at most numberTries rounds of cut generation. If numberTries is negative, we'll ignore the minimumDrop_ cutoff and keep generating cuts for the specified number of rounds. */ double minimumDrop = minimumDrop_ ; if (numberTries<0) { numberTries = -numberTries ; minimumDrop = -1.0 ; } /* Is it time to scan the cuts in order to remove redundant cuts? If so, set up to do it. */ # define SCANCUTS 100 int *countColumnCuts = NULL ; int *countRowCuts = NULL ; bool fullScan = false ; if ((numberNodes_%SCANCUTS) == 0) { fullScan = true ; countColumnCuts = new int[numberCutGenerators_+numberHeuristics_] ; countRowCuts = new int[numberCutGenerators_+numberHeuristics_] ; memset(countColumnCuts,0, (numberCutGenerators_+numberHeuristics_)*sizeof(int)) ; memset(countRowCuts,0, (numberCutGenerators_+numberHeuristics_)*sizeof(int)) ; } double direction = solver_->getObjSense() ; double startObjective = solver_->getObjValue()*direction ; int numberPasses = 0 ; double primalTolerance = 1.0e-7 ; /* Begin cut generation loop. Cuts generated during each iteration are collected in theseCuts. The loop can be divided into four phases: 1) Prep: Fix variables using reduced cost. In the first iteration only, consider scanning globalCuts_ and activating any applicable cuts. 2) Cut Generation: Call each generator and heuristic registered in the generator_ and heuristic_ arrays. Newly generated global cuts are copied to globalCuts_ at this time. 3) Cut Installation and Reoptimisation: Install column and row cuts in the solver. Copy row cuts to cuts (parameter). Reoptimise. 4) Cut Purging: takeOffCuts() removes inactive cuts from the solver, and does the necessary bookkeeping in the model. */ do { numberPasses++ ; numberTries-- ; OsiCuts theseCuts ; /* Scan previously generated global column and row cuts to see if any are useful. Unclear this code is exercised at present --- howOftenGlobalScan is initialized to -1 and never changed. In any event, I can't see why this code needs its own copy of the primal solution. Removed the dec'l. */ if (numberPasses == 1 && howOftenGlobalScan_ > 0 && (numberNodes_%howOftenGlobalScan_) == 0) { int numberCuts = globalCuts_.sizeColCuts() ; int i; for ( i = 0 ; i < numberCuts ; i++) { const OsiColCut *thisCut = globalCuts_.colCutPtr(i) ; if (thisCut->violated(solution)>primalTolerance) { printf("Global cut added - violation %g\n", thisCut->violated(solution)) ; theseCuts.insert(*thisCut) ; } } numberCuts = globalCuts_.sizeRowCuts() ; for ( i = 0;i<numberCuts;i++) { const OsiRowCut * thisCut = globalCuts_.rowCutPtr(i) ; if (thisCut->violated(solution)>primalTolerance) { printf("Global cut added - violation %g\n", thisCut->violated(solution)) ; theseCuts.insert(*thisCut) ; } } } /* Generate new cuts (global and/or local) and/or apply heuristics. If CglProbing is used, then it should be first as it can fix continuous variables. At present, CglProbing is the only case where generateCuts will return true. generateCuts actually modifies variable bounds in the solver when CglProbing indicates that it can fix a variable. Reoptimisation is required to take full advantage. */ double * newSolution = new double [numberColumns] ; double heuristicValue = getCutoff() ; int found = -1; // no solution found for (int i = 0;i<numberCutGenerators_+numberHeuristics_;i++) { int numberRowCutsBefore = theseCuts.sizeRowCuts() ; int numberColumnCutsBefore = theseCuts.sizeColCuts() ; if (i<numberCutGenerators_) { bool mustResolve = generator_[i]->generateCuts(theseCuts,fullScan) ; if (mustResolve) { feasible = resolve() ; # ifdef SBB_DEBUG debugger = solver_->getRowCutDebugger() ; if (debugger) onOptimalPath = (debugger->onOptimalPath(*solver_)) ; if (onOptimalPath && !solver_->isDualObjectiveLimitReached()) assert(feasible) ; # endif if (!feasible) break ; } } else { // see if heuristic will do anything double saveValue = heuristicValue ; int ifSol = heuristic_[i-numberCutGenerators_]->solution(heuristicValue, newSolution, theseCuts) ; if (ifSol>0) { // better solution found found = i ; } else if (ifSol<0) { heuristicValue = saveValue ; } } int numberRowCutsAfter = theseCuts.sizeRowCuts() ; int numberColumnCutsAfter = theseCuts.sizeColCuts() ; #ifdef SBB_DEBUG if (onOptimalPath) { int k ; for (k = numberRowCutsBefore;k<numberRowCutsAfter;k++) { OsiRowCut thisCut = theseCuts.rowCut(k) ; assert(!debugger->invalidCut(thisCut)) ; } } #endif /* The cut generator/heuristic has done its thing, and maybe it generated some cuts and/or a new solution. Do a bit of bookkeeping: load whichGenerator[i] with the index of the generator responsible for a cut, and place cuts flagged as global in the global cut pool for the model. lastNumberCuts is the sum of cuts added in previous iterations; it's the offset to the proper starting position in whichGenerator. TODO: Why is whichGenerator increased to 2*maximumWhich when it grows? */ int numberBefore = numberRowCutsBefore+numberColumnCutsBefore+lastNumberCuts ; int numberAfter = numberRowCutsAfter+numberColumnCutsAfter+lastNumberCuts ; if (numberAfter > maximumWhich) { maximumWhich = max(maximumWhich*2+100,numberAfter) ; int * temp = new int[2*maximumWhich] ; memcpy(temp,whichGenerator,numberBefore*sizeof(int)) ; delete [] whichGenerator ; whichGenerator = temp ; } int j ; if (fullScan) { // counts countRowCuts[i] += numberRowCutsAfter-numberRowCutsBefore ; countColumnCuts[i] += numberColumnCutsAfter-numberColumnCutsBefore ; } for (j = numberRowCutsBefore;j<numberRowCutsAfter;j++) { whichGenerator[numberBefore++] = i ; const OsiRowCut * thisCut = theseCuts.rowCutPtr(j) ; if (thisCut->globallyValid()) { // add to global list globalCuts_.insert(*thisCut) ; } } for (j = numberColumnCutsBefore;j<numberColumnCutsAfter;j++) { whichGenerator[numberBefore++] = i ; const OsiColCut * thisCut = theseCuts.colCutPtr(j) ; if (thisCut->globallyValid()) { // add to global list globalCuts_.insert(*thisCut) ; } } } /* End of the loop to exercise each generator/heuristic. Did any of the heuristics turn up a new solution? Record it before we free the vector. */ if (found >= 0) { setBestSolution(SBB_ROUNDING,heuristicValue,newSolution) ; } delete [] newSolution ; #if 0 // switch on to get all cuts printed theseCuts.printCuts() ; #endif int numberColumnCuts = theseCuts.sizeColCuts() ; int numberRowCuts = theseCuts.sizeRowCuts() ; violated = numberRowCuts + numberColumnCuts ; /* Apply column cuts (aka bound tightening). This may be partially redundant for column cuts returned by CglProbing, as generateCuts installs bounds from CglProbing when it determines it can fix a variable. TODO: Looks like the use of violated has evolved. The value set above is completely ignored. All that's left is violated == -1 indicates some cut is violated, violated == -2 indicates infeasibility. Only infeasibility warrants exceptional action. TODO: Strikes me that this code will fail to detect infeasibility, because the breaks escape the inner loops but the outer loop keeps going. Infeasibility in an early cut will be overwritten if a later cut is merely violated. */ if (numberColumnCuts) { #ifdef SBB_DEBUG double * oldLower = new double [numberColumns] ; double * oldUpper = new double [numberColumns] ; memcpy(oldLower,lower,numberColumns*sizeof(double)) ; memcpy(oldUpper,upper,numberColumns*sizeof(double)) ; #endif double integerTolerance = getDblParam(SbbIntegerTolerance) ; for (int i = 0;i<numberColumnCuts;i++) { const OsiColCut * thisCut = theseCuts.colCutPtr(i) ; const CoinPackedVector & lbs = thisCut->lbs() ; const CoinPackedVector & ubs = thisCut->ubs() ; int j ; int n ; const int * which ; const double * values ; n = lbs.getNumElements() ; which = lbs.getIndices() ; values = lbs.getElements() ; for (j = 0;j<n;j++) { int iColumn = which[j] ; double value = solution[iColumn] ; #ifdef SBB_DEBUG printf("%d %g %g %g %g\n",iColumn,oldLower[iColumn], solution[iColumn],oldUpper[iColumn],values[j]) ; #endif solver_->setColLower(iColumn,values[j]) ; if (value<values[j]-integerTolerance) violated = -1 ; if (values[j]>upper[iColumn]+integerTolerance) { // infeasible violated = -2 ; break ; } } n = ubs.getNumElements() ; which = ubs.getIndices() ; values = ubs.getElements() ; for (j = 0;j<n;j++) { int iColumn = which[j] ; double value = solution[iColumn] ; #ifdef SBB_DEBUG printf("%d %g %g %g %g\n",iColumn,oldLower[iColumn], solution[iColumn],oldUpper[iColumn],values[j]) ; #endif solver_->setColUpper(iColumn,values[j]) ; if (value>values[j]+integerTolerance) violated = -1 ; if (values[j]<lower[iColumn]-integerTolerance) { // infeasible violated = -2 ; break ; } } } #ifdef SBB_DEBUG delete [] oldLower ; delete [] oldUpper ; #endif } /* End installation of column cuts. The break here escapes the numberTries loop. */ if (violated == -2) { // infeasible feasible = false ; break ; } /* Now apply the row (constraint) cuts. This is a bit more work because we need to obtain and augment the current basis. TODO: Why do this work, if there are no row cuts? The current basis will do just fine. */ int numberRowsNow = solver_->getNumRows() ; assert(numberRowsNow == numberRowsAtStart+lastNumberCuts) ; int numberToAdd = theseCuts.sizeRowCuts() ; numberNewCuts = lastNumberCuts+numberToAdd ; /* Get a basis by asking the solver for warm start information. Resize it (retaining the basis) so it can accommodate the cuts. */ delete basis_ ; basis_ = dynamic_cast<CoinWarmStartBasis*>(solver_->getWarmStart()) ; assert(basis_ != NULL); // make sure not volume basis_->resize(numberRowsAtStart+numberNewCuts,numberColumns) ; /* Now actually add the row cuts and reoptimise. Install the cuts in the solver using applyRowCuts and augment the basis with the corresponding slack. We also add each row cut to the set of row cuts (cuts.insert()) supplied as a parameter. The new basis must be set with setWarmStart(). TODO: It's not clear to me why we can't separate this into two sections. The first would add the row cuts, and be executed only if row cuts need to be installed. The second would call resolve() and would be executed if either row or column cuts have been installed. TODO: Seems to me the original code could allocate addCuts with size 0, if numberRowCuts was 0 and numberColumnCuts was nonzero. That might explain the memory fault noted in the comment by AJK. Unfortunately, just commenting out the delete[] results in massive memory leaks. Try a revision to separate the row cut case. Why do we need addCuts at all? A typing issue, apparently: OsiCut vs. OsiRowCut. TODO: It looks to me as if numberToAdd and numberRowCuts are identical at this point. Confirm & get rid of one of them. TODO: Any reason why the three loops can't be consolidated? */ if (numberRowCuts > 0 || numberColumnCuts > 0) { if (numberToAdd > 0) { int i ; OsiRowCut * addCuts = new OsiRowCut [numberToAdd] ; for (i = 0 ; i < numberToAdd ; i++) { addCuts[i] = theseCuts.rowCut(i) ; } solver_->applyRowCuts(numberToAdd,addCuts) ; // AJK this caused a memory fault on Win32 delete [] addCuts ; for (i = 0 ; i < numberToAdd ; i++) { cuts.insert(theseCuts.rowCut(i)) ; } for (i = 0 ; i < numberToAdd ; i++) { basis_->setArtifStatus(numberRowsNow+i, CoinWarmStartBasis::basic) ; } if (solver_->setWarmStart(basis_) == false) { throw CoinError("Fail setWarmStart() after cut installation.", "solveWithCuts","SbbModel") ; } } feasible = resolve() ; # ifdef SBB_DEBUG printf("Obj value after cuts %g %d rows\n",solver_->getObjValue(), solver_->getNumRows()) ; if (onOptimalPath && !solver_->isDualObjectiveLimitReached()) assert(feasible) ; # endif } /* No cuts. Cut short the cut generation (numberTries) loop. */ else { numberTries = 0 ; } /* If the problem is still feasible, first, call takeOffCuts() to remove cuts that are now slack. takeOffCuts() will call the solver to reoptimise if that's needed to restore a valid solution. Next, see if we should quit due to diminishing returns: * we've tried three rounds of cut generation and we're getting insufficient improvement in the objective; or * we generated no cuts; or * the solver declared optimality with 0 iterations after we added the cuts generated in this round. If we decide to keep going, prep for the next iteration. It just seems more safe to tell takeOffCuts() to call resolve(), even if we're not continuing cut generation. Otherwise code executed between here and final disposition of the node will need to be careful not to access the lp solution. It can happen that we loose feasibility in takeOffCuts --- numerical jitters when the cutoff bound is epsilon less than the current best, and we're evaluating an alternative optimum. TODO: After successive rounds of code motion, there seems no need to distinguish between the two checks for aborting the cut generation loop. Confirm and clean up. */ if (feasible) { int cutIterations = solver_->getIterationCount() ; takeOffCuts(cuts,whichGenerator,numberOldActiveCuts,numberNewCuts,true) ; if (solver_->isDualObjectiveLimitReached()) { feasible = false ; # ifdef SBB_DEBUG double z = solver_->getObjValue() ; double cut = getCutoff() ; printf("Lost feasibility by %g in takeOffCuts; z = %g, cutoff = %g\n", z-cut,z,cut) ; # endif } if (feasible) { numberRowsAtStart = numberOldActiveCuts+numberRowsAtContinuous_ ; lastNumberCuts = numberNewCuts ; if (direction*solver_->getObjValue() < lastObjective+minimumDrop && numberPasses >= 3) { numberTries = 0 ; } if (numberRowCuts+numberColumnCuts == 0 || cutIterations == 0) { break ; } if (numberTries > 0) { reducedCostFix() ; lastObjective = direction*solver_->getObjValue() ; lower = solver_->getColLower() ; upper = solver_->getColUpper() ; solution = solver_->getColSolution() ; } } } /* We've lost feasibility --- this node won't be referencing the cuts we've been collecting, so decrement the reference counts. TODO: Presumably this is in preparation for backtracking. Seems like it should be the `else' off the previous `if'. */ if (!feasible) { int i ; for (i = 0;i<currentNumberCuts_;i++) { // take off node if (addedCuts_[i]) { if (!addedCuts_[i]->decrement()) delete addedCuts_[i] ; addedCuts_[i] = NULL ; } } numberTries = 0 ; } } while (numberTries) ; /* End of cut generation loop. Now, consider if we want to disable or adjust the frequency of use for any of the cut generators. If the client specified a positive number for howOften, it will never change. If the original value was negative, it'll be converted to 1000000+|howOften|, and this value will be adjusted each time fullScan is true. Actual cut generation is performed every howOften%1000000 nodes; the 1000000 offset is just a convenient way to specify that the frequency is adjustable. During cut generation, we recorded the number of cuts produced by each generator for this node. For all cuts, whichGenerator records the generator that produced a cut. TODO: All this should probably be hidden in a method of the SbbCutGenerator class. */ if (feasible&&fullScan&&numberCutGenerators_) { // Root node or every so often - see what to turn off int i ; double thisObjective = solver_->getObjValue()*direction ; double totalCuts = 0.0 ; for (i = 0;i<numberCutGenerators_;i++) totalCuts += countRowCuts[i] + 5.0*countColumnCuts[i] ; if (!numberNodes_) handler_->message(SBB_ROOT,messages_) <<numberNewCuts <<startObjective<<thisObjective <<numberPasses <<CoinMessageEol ; int * count = new int[numberCutGenerators_] ; memset(count,0,numberCutGenerators_*sizeof(int)) ; for (i = 0;i<numberNewCuts;i++) count[whichGenerator[i]]++ ; double small = (0.5* totalCuts) / ((double) numberCutGenerators_) ; for (i = 0;i<numberCutGenerators_;i++) { int howOften = generator_[i]->howOften() ; if (howOften<-99) continue ; if (howOften<0||howOften >= 1000000) { // If small number switch mostly off double thisCuts = countRowCuts[i] + 5.0*countColumnCuts[i] ; if (!thisCuts||howOften == -99) { if (howOften == -99) howOften = -100 ; else howOften = 1000000+SCANCUTS; // wait until next time } else if (thisCuts<small) { int k = (int) sqrt(small/thisCuts) ; howOften = k+1000000 ; } else { howOften = 1+1000000 ; } } generator_[i]->setHowOften(howOften) ; int newFrequency = generator_[i]->howOften()%1000000 ; if (handler_->logLevel()>1||!numberNodes_) handler_->message(SBB_GENERATOR,messages_) <<i <<generator_[i]->cutGeneratorName() <<countRowCuts[i]<<count[i] <<countColumnCuts[i] <<newFrequency <<CoinMessageEol ; } delete [] count ; } delete [] countRowCuts ; delete [] countColumnCuts ; #ifdef CHECK_CUT_COUNTS if (feasible) { delete basis_ ; basis_ = dynamic_cast<CoinWarmStartBasis*>(solver_->getWarmStart()) ; printf("solveWithCuts: Number of rows at end (only active cuts) %d\n", numberRowsAtContinuous_+numberNewCuts+numberOldActiveCuts) ; basis_->print() ; } #endif #ifdef SBB_DEBUG if (onOptimalPath && !solver_->isDualObjectiveLimitReached()) assert(feasible) ; #endif return feasible ; }

int SbbModel::status (   )  const [inline]

Final status of problem 0 finished, 1 stopped, 2 difficulties Definition at line 460 of file SbbModel.hpp. References status_. Referenced by addCuts(), and takeOffCuts(). { return status_;};

void SbbModel::synchronizeModel (   )

Ensure attached objects point to this model. Ensure all attached objects (SbbObjects, heuristics, and cut generators) point to this model. Definition at line 3269 of file SbbModel.cpp. References numberCutGenerators_, numberHeuristics_, numberObjects_, object_, SbbCutGenerator::refreshModel(), SbbObject::setModel(), and SbbHeuristic::setModel(). Referenced by branchAndBound(), findCliques(), integerPresolve(), integerPresolveThisModel(), operator=(), originalModel(), and SbbModel(). { int i; for (i=0;i<numberHeuristics_;i++) heuristic_[i]->setModel(this); for (i=0;i<numberObjects_;i++) object_[i]->setModel(this); for (i=0;i<numberCutGenerators_;i++) generator_[i]->refreshModel(this); }

void SbbModel::takeOffCuts (  OsiCuts &  cuts, int *  whichGenerator, int &  numberOldActiveCuts, int &  numberNewCuts, bool  allowResolve )

Remove inactive cuts from the model An OsiSolverInterface is expected to maintain a valid basis, but not a valid solution, when loose cuts are deleted. Restoring a valid solution requires calling the solver to reoptimise. If it's certain the solution will not be required, set allowResolve to false to suppress reoptimisation. Definition at line 2802 of file SbbModel.cpp. References addedCuts_, currentNumberCuts_, SbbCountRowCut::decrement(), OsiSolverInterface::deleteRows(), OsiCuts::eraseRowCut(), CoinWarmStartBasis::getArtifStatus(), OsiSolverInterface::getIterationCount(), OsiSolverInterface::getWarmStart(), numberRowsAtContinuous_, OsiSolverInterface::resolve(), solver_, and status(). Referenced by branchAndBound(), and solveWithCuts(). { // int resolveIterations = 0 ; int firstOldCut = numberRowsAtContinuous_ ; int totalNumberCuts = numberNewCuts+numberOldActiveCuts ; int *solverCutIndices = new int[totalNumberCuts] ; int *newCutIndices = new int[numberNewCuts] ; const CoinWarmStartBasis* ws ; CoinWarmStartBasis::Status status ; bool needPurge = true ; /* The outer loop allows repetition of purge in the event that reoptimisation changes the basis. To start an iteration, clear the deletion counts and grab the current basis. */ while (needPurge) { int numberNewToDelete = 0 ; int numberOldToDelete = 0 ; int i ; ws = dynamic_cast<const CoinWarmStartBasis*>(solver_->getWarmStart()) ; /* Scan the basis entries of the old cuts generated prior to this round of cut generation. Loose cuts are `removed' by decrementing their reference count and setting the addedCuts_ entry to NULL. (If the reference count falls to 0, they're really deleted. See SbbModel and SbbCountRowCut doc'n for principles of cut handling.) */ int oldCutIndex = 0 ; for (i = 0 ; i < numberOldActiveCuts ; i++) { status = ws->getArtifStatus(i+firstOldCut) ; while (!addedCuts_[oldCutIndex]) oldCutIndex++ ; assert(oldCutIndex < currentNumberCuts_) ; if (status == CoinWarmStartBasis::basic) { solverCutIndices[numberOldToDelete++] = i+firstOldCut ; if (addedCuts_[oldCutIndex]->decrement() == 0) delete addedCuts_[oldCutIndex] ; addedCuts_[oldCutIndex] = NULL ; oldCutIndex++ ; } else { oldCutIndex++ ; } } /* Scan the basis entries of the new cuts generated with this round of cut generation. At this point, newCuts is the only record of the new cuts, so when we delete loose cuts from newCuts, they're really gone. newCuts is a vector, so it's most efficient to compress it (eraseRowCut) from back to front. */ int firstNewCut = firstOldCut+numberOldActiveCuts ; int k = 0 ; for (i = 0 ; i < numberNewCuts ; i++) { status = ws->getArtifStatus(i+firstNewCut) ; if (status == CoinWarmStartBasis::basic) { solverCutIndices[numberNewToDelete+numberOldToDelete] = i+firstNewCut ; newCutIndices[numberNewToDelete++] = i ; } else { // save which generator did it whichGenerator[k++] = whichGenerator[i] ; } } for (i = numberNewToDelete-1 ; i >= 0 ; i--) { int iCut = newCutIndices[i] ; newCuts.eraseRowCut(iCut) ; } /* Did we delete anything? If so, delete the cuts from the constraint system held in the solver and reoptimise unless we're forbidden to do so. If the call to resolve() results in pivots, there's the possibility we again have basic slacks. Repeat the purging loop. */ if (numberNewToDelete+numberOldToDelete > 0) { solver_->deleteRows(numberNewToDelete+numberOldToDelete, solverCutIndices) ; numberNewCuts -= numberNewToDelete ; numberOldActiveCuts -= numberOldToDelete ; # ifdef SBB_DEBUG std::cout << "takeOffCuts: purged " << numberOldToDelete << "+" << numberNewToDelete << " cuts." << std::endl ; # endif if (allowResolve) { solver_->resolve() ; if (solver_->getIterationCount() == 0) { needPurge = false ; } # ifdef SBB_DEBUG else { std::cout << "Repeating purging loop. " << solver_->getIterationCount() << " iters." << std::endl ; } # endif } else { needPurge = false ; } } else { needPurge = false ; } } /* Clean up and return. */ delete ws ; delete [] solverCutIndices ; delete [] newCutIndices ; }

bool SbbModel::tightenVubs (  int  numberVubs, const int *  which, double  useCutoff = 1.0e50 )

For variables involved in VUB constraints, see if we can tighten bounds by solving lp's. This version is just handed a list of variables to be processed. Definition at line 3794 of file SbbModel.cpp. References OsiSolverInterface::addRow(), OsiSolverInterface::clone(), CglProbing::generateCutsAndModify(), SbbCutGenerator::generator(), OsiSolverInterface::getColLower(), OsiSolverInterface::getColSolution(), OsiSolverInterface::getColUpper(), getCutoff(), CglProbing::getMaxLook(), CglProbing::getMaxPass(), CglProbing::getMaxProbe(), OsiSolverInterface::getNumCols(), OsiSolverInterface::getObjCoefficients(), OsiSolverInterface::getObjSense(), OsiSolverInterface::getWarmStart(), handler_, SbbCutGenerator::howOften(), OsiSolverInterface::initialSolve(), CoinPackedVector::insert(), OsiSolverInterface::isInteger(), OsiSolverInterface::isProvenOptimal(), CoinMessageHandler::message(), messages_, numberCutGenerators_, printFrequency(), OsiSolverInterface::resolve(), CglProbing::rowCuts(), OsiSolverInterface::setColLower(), OsiSolverInterface::setColSolution(), OsiSolverInterface::setColUpper(), setCutoff(), SbbCutGenerator::setHowOften(), CglProbing::setMaxLook(), CglProbing::setMaxPass(), CglProbing::setMaxProbe(), OsiSolverInterface::setObjCoeff(), CglProbing::setRowCuts(), OsiSolverInterface::setWarmStart(), solver(), solver_, CglProbing::tightLower(), and CglProbing::tightUpper(). { int numberColumns = solver_->getNumCols(); int iColumn; OsiSolverInterface * solver = solver_; double saveCutoff = getCutoff() ; double * objective = new double[numberColumns]; memcpy(objective,solver_->getObjCoefficients(),numberColumns*sizeof(double)); double direction = solver_->getObjSense(); // add in objective if there is a cutoff if (useCutoff<1.0e30) { // get new version of model solver = solver_->clone(); CoinPackedVector newRow; for (iColumn=0;iColumn<numberColumns;iColumn++) { solver->setObjCoeff(iColumn,0.0); // zero out in new model if (objective[iColumn]) newRow.insert(iColumn,direction * objective[iColumn]); } solver->addRow(newRow,-DBL_MAX,useCutoff); // signal no objective delete [] objective; objective=NULL; } setCutoff(DBL_MAX); bool * vub = new bool [numberColumns]; int iVub; // mark vub columns for (iColumn=0;iColumn<numberColumns;iColumn++) vub[iColumn]=false; for (iVub=0;iVub<numberSolves;iVub++) vub[which[iVub]]=true; OsiCuts cuts; // First tighten bounds anyway if CglProbing there CglProbing* generator = NULL; int iGen; for (iGen=0;iGen<numberCutGenerators_;iGen++) { generator = dynamic_cast<CglProbing*>(generator_[iGen]->generator()); if (generator) break; } int numberFixed=0; int numberTightened=0; int numberFixedByProbing=0; int numberTightenedByProbing=0; int printFrequency = (numberSolves+19)/20; // up to 20 messages int save[4]; if (generator) { // set to cheaper and then restore at end save[0]=generator->getMaxPass(); save[1]=generator->getMaxProbe(); save[2]=generator->getMaxLook(); save[3]=generator->rowCuts(); generator->setMaxPass(1); generator->setMaxProbe(10); generator->setMaxLook(50); generator->setRowCuts(0); // Probing - return tight column bounds generator->generateCutsAndModify(*solver,cuts); const double * tightLower = generator->tightLower(); const double * lower = solver->getColLower(); const double * tightUpper = generator->tightUpper(); const double * upper = solver->getColUpper(); for (iColumn=0;iColumn<numberColumns;iColumn++) { double newUpper = tightUpper[iColumn]; double newLower = tightLower[iColumn]; if (newUpper<upper[iColumn]-1.0e-8*(fabs(upper[iColumn])+1)|| newLower>lower[iColumn]+1.0e-8*(fabs(lower[iColumn])+1)) { if (newUpper<newLower) { fprintf(stderr,"Problem is infeasible\n"); return false; } if (newUpper==newLower) { numberFixed++; numberFixedByProbing++; solver->setColLower(iColumn,newLower); solver->setColUpper(iColumn,newUpper); } else if (vub[iColumn]) { numberTightened++; numberTightenedByProbing++; if (!solver->isInteger(iColumn)) { // relax newLower=max(lower[iColumn], newLower -1.0e-5*(fabs(lower[iColumn])+1)); newUpper=min(upper[iColumn], newUpper +1.0e-5*(fabs(upper[iColumn])+1)); } solver->setColLower(iColumn,newLower); solver->setColUpper(iColumn,newUpper); } } } } CoinWarmStart * ws = solver->getWarmStart(); double * solution = new double [numberColumns]; memcpy(solution,solver->getColSolution(),numberColumns*sizeof(double)); for (iColumn=0;iColumn<numberColumns;iColumn++) solver->setObjCoeff(iColumn,0.0); //solver->messageHandler()->setLogLevel(2); for (iVub=0;iVub<numberSolves;iVub++) { iColumn = which[iVub]; int iTry; for (iTry=0;iTry<2;iTry++) { double saveUpper = solver->getColUpper()[iColumn]; double saveLower = solver->getColLower()[iColumn]; double value; if (iTry==1) { // try all way up solver->setObjCoeff(iColumn,-1.0); } else { // try all way down solver->setObjCoeff(iColumn,1.0); } solver->initialSolve(); value = solver->getColSolution()[iColumn]; bool change=false; if (iTry==1) { if (value<saveUpper-1.0e-4) { if (solver->isInteger(iColumn)) { value = floor(value+0.00001); } else { // relax a bit value=min(saveUpper,value+1.0e-5*(fabs(saveUpper)+1)); } if (value-saveLower<1.0e-7) value = saveLower; // make sure exactly same solver->setColUpper(iColumn,value); saveUpper=value; change=true; } } else { if (value>saveLower+1.0e-4) { if (solver->isInteger(iColumn)) { value = ceil(value-0.00001); } else { // relax a bit value=max(saveLower,value-1.0e-5*(fabs(saveLower)+1)); } if (saveUpper-value<1.0e-7) value = saveUpper; // make sure exactly same solver->setColLower(iColumn,value); saveLower=value; change=true; } } solver->setObjCoeff(iColumn,0.0); if (change) { if (saveUpper==saveLower) numberFixed++; else numberTightened++; int saveFixed=numberFixed; int jColumn; if (generator) { // Probing - return tight column bounds cuts = OsiCuts(); generator->generateCutsAndModify(*solver,cuts); const double * tightLower = generator->tightLower(); const double * lower = solver->getColLower(); const double * tightUpper = generator->tightUpper(); const double * upper = solver->getColUpper(); for (jColumn=0;jColumn<numberColumns;jColumn++) { double newUpper = tightUpper[jColumn]; double newLower = tightLower[jColumn]; if (newUpper<upper[jColumn]-1.0e-8*(fabs(upper[jColumn])+1)|| newLower>lower[jColumn]+1.0e-8*(fabs(lower[jColumn])+1)) { if (newUpper<newLower) { fprintf(stderr,"Problem is infeasible\n"); return false; } if (newUpper==newLower) { numberFixed++; numberFixedByProbing++; solver->setColLower(jColumn,newLower); solver->setColUpper(jColumn,newUpper); } else if (vub[jColumn]) { numberTightened++; numberTightenedByProbing++; if (!solver->isInteger(jColumn)) { // relax newLower=max(lower[jColumn], newLower -1.0e-5*(fabs(lower[jColumn])+1)); newUpper=min(upper[jColumn], newUpper +1.0e-5*(fabs(upper[jColumn])+1)); } solver->setColLower(jColumn,newLower); solver->setColUpper(jColumn,newUpper); } } } } if (numberFixed>saveFixed) { // original solution may not be feasible // go back to true costs to solve if exists if (objective) { for (jColumn=0;jColumn<numberColumns;jColumn++) solver->setObjCoeff(jColumn,objective[jColumn]); } solver->setColSolution(solution); solver->setWarmStart(ws); solver->resolve(); if (!solver->isProvenOptimal()) { fprintf(stderr,"Problem is infeasible\n"); return false; } delete ws; ws = solver->getWarmStart(); memcpy(solution,solver->getColSolution(), numberColumns*sizeof(double)); for (jColumn=0;jColumn<numberColumns;jColumn++) solver->setObjCoeff(jColumn,0.0); } } solver->setColSolution(solution); solver->setWarmStart(ws); } if (iVub%printFrequency==0) handler_->message(SBB_VUB_PASS,messages_) <<iVub+1<<numberFixed<<numberTightened <<CoinMessageEol; } handler_->message(SBB_VUB_END,messages_) <<numberFixed<<numberTightened <<CoinMessageEol; delete ws; delete [] solution; // go back to true costs to solve if exists if (objective) { for (iColumn=0;iColumn<numberColumns;iColumn++) solver_->setObjCoeff(iColumn,objective[iColumn]); delete [] objective; } delete [] vub; if (generator) { /*printf("Probing fixed %d and tightened %d\n", numberFixedByProbing, numberTightenedByProbing);*/ if (generator_[iGen]->howOften()==-1&& (numberFixedByProbing+numberTightenedByProbing)*5> (numberFixed+numberTightened)) generator_[iGen]->setHowOften(1000000+1); generator->setMaxPass(save[0]); generator->setMaxProbe(save[1]); generator->setMaxLook(save[2]); generator->setRowCuts(save[3]); } if (solver!=solver_) { // move bounds across const double * lower = solver->getColLower(); const double * upper = solver->getColUpper(); const double * lowerOrig = solver_->getColLower(); const double * upperOrig = solver_->getColUpper(); for (iColumn=0;iColumn<numberColumns;iColumn++) { solver_->setColLower(iColumn,max(lower[iColumn],lowerOrig[iColumn])); solver_->setColUpper(iColumn,min(upper[iColumn],upperOrig[iColumn])); } delete solver; } setCutoff(saveCutoff); return true; }

bool SbbModel::tightenVubs (  int  type, bool  allowMultipleBinary = false, double  useCutoff = 1.0e50 )

For variables involved in VUB constraints, see if we can tighten bounds by solving lp's. Returns false if feasibility is lost. If CglProbing is available, it will be tried as well to see if it can tighten bounds. This routine is just a front end for tightenVubs(int,const int*,double). If type = -1 all variables are processed (could be very slow). If type = 0 only variables involved in VUBs are processed. If type = n > 0, only the n most expensive VUB variables are processed, where it is assumed that x is at its maximum so delta would have to go to 1 (if x not at bound). If allowMultipleBinary is true, then a VUB constraint is a row with one continuous variable and any number of binary variables. If useCutoff < 1.0e30, the original objective is installed as a constraint with useCutoff as a bound. Definition at line 3711 of file SbbModel.cpp. References OsiSolverInterface::getColLower(), OsiSolverInterface::getColSolution(), OsiSolverInterface::getColUpper(), OsiSolverInterface::getMatrixByRow(), OsiSolverInterface::getNumCols(), OsiSolverInterface::getNumRows(), OsiSolverInterface::getObjCoefficients(), OsiSolverInterface::isFreeBinary(), and solver_. { CoinPackedMatrix matrixByRow(*solver_->getMatrixByRow()); int numberRows = solver_->getNumRows(); int numberColumns = solver_->getNumCols(); int iRow,iColumn; // Row copy //const double * elementByRow = matrixByRow.getElements(); const int * column = matrixByRow.getIndices(); const int * rowStart = matrixByRow.getVectorStarts(); const int * rowLength = matrixByRow.getVectorLengths(); const double * colUpper = solver_->getColUpper(); const double * colLower = solver_->getColLower(); //const double * rowUpper = solver_->getRowUpper(); //const double * rowLower = solver_->getRowLower(); const double * objective = solver_->getObjCoefficients(); //double direction = solver_->getObjSense(); const double * colsol = solver_->getColSolution(); int numberVub=0; int * continuous = new int[numberColumns]; if (type >= 0) { double * sort = new double[numberColumns]; for (iRow=0;iRow<numberRows;iRow++) { int j; int numberBinary=0; int numberUnsatisfiedBinary=0; int numberContinuous=0; int iCont=-1; double weight=1.0e30; for (j=rowStart[iRow];j<rowStart[iRow]+rowLength[iRow];j++) { int iColumn = column[j]; if (colUpper[iColumn]-colLower[iColumn]>1.0e-8) { if (solver_->isFreeBinary(iColumn)) { numberBinary++; /* For sort I make naive assumption: x - a * delta <=0 or -x + a * delta >= 0 */ if (colsol[iColumn]>colLower[iColumn]+1.0e-6&& colsol[iColumn]<colUpper[iColumn]-1.0e-6) { numberUnsatisfiedBinary++; weight = min(weight,fabs(objective[iColumn])); } } else { numberContinuous++; iCont=iColumn; } } } if (numberContinuous==1&&numberBinary) { if (numberBinary==1||allowMultipleBinary) { // treat as vub if (!numberUnsatisfiedBinary) weight=-1.0; // at end sort[numberVub]=-weight; continuous[numberVub++] = iCont; } } } if (type>0) { // take so many CoinSort_2(sort,sort+numberVub,continuous); numberVub = min(numberVub,type); } delete [] sort; } else { for (iColumn=0;iColumn<numberColumns;iColumn++) continuous[iColumn]=iColumn; numberVub=numberColumns; } bool feasible = tightenVubs(numberVub,continuous,useCutoff); delete [] continuous; return feasible; }

---

Member Data Documentation

SbbCountRowCut** SbbModel::addedCuts_ [private]

The list of cuts initially collected for this subproblem When the subproblem at this node is rebuilt, a set of cuts is collected for inclusion in the constraint system. If any of these cuts are subsequently removed because they have become loose, the corresponding entry is set to NULL. Definition at line 1010 of file SbbModel.hpp. Referenced by addCuts(), addCuts1(), addedCuts(), branchAndBound(), gutsOfDestructor(), integerPresolveThisModel(), operator=(), SbbModel(), solveWithCuts(), and takeOffCuts().

CoinWarmStartBasis* SbbModel::basis_ [private]

Pointer to a warm start basis. Definition at line 950 of file SbbModel.hpp. Referenced by addCuts(), assignSolver(), branchAndBound(), gutsOfDestructor(), operator=(), SbbModel(), and solveWithCuts().

double SbbModel::continuousObjective_ [private]

Value of objective at continuous Should be an array with depths? Definition at line 1063 of file SbbModel.hpp. Referenced by branchAndBound(), getContinuousObjective(), and operator=().

double* SbbModel::currentSolution_ [private]

Array holding the current solution. This array is used more as a temporary. Definition at line 962 of file SbbModel.hpp. Referenced by branchAndBound(), checkSolution(), currentSolution(), feasibleSolution(), gutsOfDestructor(), integerPresolveThisModel(), operator=(), originalModel(), SbbModel(), and setBestSolution().

bool SbbModel::defaultHandler_ [private]

Flag to say if handler_ is the default handler. The default handler is deleted when the model is deleted. Other handlers (supplied by the client) will not be deleted. Definition at line 928 of file SbbModel.hpp. Referenced by operator=(), passInMessageHandler(), SbbModel(), and ~SbbModel().

CoinWarmStart* SbbModel::emptyWarmStart_ [mutable, private]

Pointer to an empty warm start object It turns out to be useful to have this available as a base from which to build custom warm start objects. This is typed as CoinWarmStart rather than CoinWarmStartBasis to allow for the possibility that a client might want to apply a solver that doesn't use a basis-based warm start. See getEmptyBasis for an example of how this field can be used. Definition at line 947 of file SbbModel.hpp. Referenced by assignSolver(), getEmptyBasis(), gutsOfDestructor(), operator=(), and SbbModel().

int SbbModel::maximumDepth_ [private]

Current limit on search tree depth The allocated size of walkback_. Increased as needed. Definition at line 995 of file SbbModel.hpp. Referenced by addCuts1(), branchAndBound(), integerPresolveThisModel(), operator=(), and SbbModel().

int SbbModel::numberStrong_ [private]

Maximum number of candidates to consider for strong branching. To disable strong branching, set this to 0. Definition at line 1025 of file SbbModel.hpp. Referenced by numberStrong(), operator=(), and setNumberStrong().

SbbObject** SbbModel::object_ [private]

Integer and Clique and ... information. Note: The code assumes that the first objects on the list will be SimpleInteger objects for each integer variable, followed by Clique objects. Portions of the code that understand Clique objects will fail if they do not immediately follow the SimpleIntegers. Large chunks of the code will fail if the first objects are not SimpleInteger. As of 2003.08, SimpleIntegers and Cliques are the only objects. Definition at line 1051 of file SbbModel.hpp. Referenced by addObjects(), branchAndBound(), checkSolution(), deleteObjects(), feasibleSolution(), findCliques(), findIntegers(), gutsOfDestructor(), object(), objects(), operator=(), SbbModel(), and synchronizeModel().

bool SbbModel::ourSolver_ [private]

Ownership of the solver object The convention is that SbbModel owns the null solver. Currently there is no public method to give SbbModel a solver without giving ownership, but the hook is here. Definition at line 915 of file SbbModel.hpp. Referenced by assignSolver(), operator=(), SbbModel(), and ~SbbModel().

SbbNodeInfo** SbbModel::walkback_ [private]

Array used to assemble the path between a node and the search tree root The array is resized when necessary. maximumDepth_ is the current allocated size. Definition at line 1001 of file SbbModel.hpp. Referenced by addCuts1(), branchAndBound(), gutsOfDestructor(), integerPresolveThisModel(), operator=(), and SbbModel().

---

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

• SbbModel.hpp
• SbbModel.cpp

---