Bonmin::BonChooseVariable Class Reference

This class chooses a variable to branch on. More...

#include <BonChooseVariable.hpp>

Inheritance diagram for Bonmin::BonChooseVariable:

Inheritance graph
[legend]
Collaboration diagram for Bonmin::BonChooseVariable:

Collaboration graph
[legend]
List of all members.

Message handling.

enum  Messages_Types {
  PS_COST_HISTORY = 0, PS_COST_MULT, PS_COST_ESTIMATES, CANDIDATE_LIST,
  CANDIDATE_LIST2, CANDIDATE_LIST3, SB_HEADER, SB_RES,
  BRANCH_VAR, CHOSEN_VAR, UPDATE_PS_COST, BON_CHOOSE_MESSAGES_DUMMY_END
}
void passInMessageHandler (CoinMessageHandler *handler)
CoinMessageHandler & message (Messages_Types type) const

Public Types

 PS_COST_HISTORY = 0
 PS_COST_MULT
 PS_COST_ESTIMATES
 CANDIDATE_LIST
 CANDIDATE_LIST2
 CANDIDATE_LIST3
 SB_HEADER
 SB_RES
 BRANCH_VAR
 CHOSEN_VAR
 UPDATE_PS_COST
 BON_CHOOSE_MESSAGES_DUMMY_END
 provenInfeasible = -1
 doneNoFixing
 All done no variable can be fixed.
 doneCanFix
 Several variable can be fixed.
 interuptedCanFix
 Interupted and found a variable to fix.
 maxTime
 Interupted because of time limit.
 infeasibleNode = -1
 hasCandidate
 Normal termination, found a variable to branch on.
 feasibleNode
 All variable are feasible, the node is feasible.
 canFixAndStrongBranch
 Found variable to fix and also has remaining candidate for strong branching.
 canFixAndBranch
 Found variable to fix and also has a (non-strong) branching candidate.
 canFixNoCandidate
 Can fix variables but does not have strong branching candidates.
enum  DoStrongReturnStatuses {
  provenInfeasible = -1, doneNoFixing, doneCanFix, interuptedCanFix,
  maxTime
}
enum  chooseVariableReturnStatuses {
  infeasibleNode = -1, hasCandidate, feasibleNode, canFixAndStrongBranch,
  canFixAndBranch, canFixNoCandidate
}
 Return statuses for chooseVariable. More...

Public Member Functions

 BonChooseVariable (BabSetupBase &b, const OsiSolverInterface *solver)
 Constructor from solver (so we can set up arrays etc).
 BonChooseVariable (const BonChooseVariable &)
 Copy constructor.
BonChooseVariableoperator= (const BonChooseVariable &rhs)
 Assignment operator.
virtual OsiChooseVariable * clone () const
 Clone.
virtual ~BonChooseVariable ()
 Destructor.
double maxminCrit (const OsiBranchingInformation *info) const
 Helper functions for setupList and chooseVariable.
void computeMultipliers (double &upMult, double &downMult) const
double computeUsefulness (const double MAXMIN_CRITERION, const double upMult, const double dowMult, const double value, const OsiObject *object, int i, double &value2) const
virtual int setupList (OsiBranchingInformation *info, bool initialize)
 Sets up strong list and clears all if initialize is true.
virtual int chooseVariable (OsiSolverInterface *solver, OsiBranchingInformation *info, bool fixVariables)
 Choose a variable Returns - -1 Node is infeasible 0 Normal termination - we have a candidate 1 All looks satisfied - no candidate 2 We can change the bound on a variable - but we also have a strong branching candidate 3 We can change the bound on a variable - but we have a non-strong branching candidate 4 We can change the bound on a variable - no other candidates We can pick up branch from bestObjectIndex() and bestWhichWay() We can pick up a forced branch (can change bound) from firstForcedObjectIndex() and firstForcedWhichWay() If we have a solution then we can pick up from goodObjectiveValue() and goodSolution() If fixVariables is true then 2,3,4 are all really same as problem changed.
virtual void updateInformation (const OsiBranchingInformation *info, int branch, OsiHotInfo *hotInfo)
 Given a candidate fill in useful information e.g. estimates.
virtual void updateInformation (int whichObject, int branch, double changeInObjective, double changeInValue, int status)
 Given a branch fill in useful information e.g. estimates.
void setCbcModel (CbcModel *cbc_model)
 Method for setting CbcModel, which is used to get statusOfSearch.
void setOnlyPseudoWhenTrusted (bool only_pseudo_when_trusted)
const OsiPseudoCosts & pseudoCosts () const
 Access to pseudo costs storage.
OsiPseudoCosts & pseudoCosts ()
 Access to pseudo costs storage.

Static Public Member Functions

static void registerOptions (Ipopt::SmartPtr< Bonmin::RegisteredOptions > roptions)

Protected Types

 NotDone = -1
 Feasible
 Child is proven feasible.
 Infeasible
 Child is proven infeasible.
 NotFinished
 Child is not finished.
enum  StrongStatus { NotDone = -1, Feasible, Infeasible, NotFinished }
 Statuses for strong branching candidates. More...

Protected Member Functions

virtual int doStrongBranching (OsiSolverInterface *solver, OsiBranchingInformation *info, int numberToDo, int returnCriterion)
 This is a utility function which does strong branching on a list of objects and stores the results in OsiHotInfo.objects.
int determineStatus (OsiSolverInterface *solver) const
 Determine status of strong branching solution.
bool isRootNode (const OsiBranchingInformation *info) const
 detecting if this is root node

Protected Attributes

SmartPtr< Journalist > jnlst_
 Holding on the a pointer to the journalist.
int bb_log_level_
 verbosity level
vector< HotInforesults_
 Stores strong branching results.
CbcModel * cbc_model_
 CbcModel, used to get status of search.
bool only_pseudo_when_trusted_
 Flag indicating whether we don't want to mix strong branching and pseudo costs during the decision which variable to branch on.
int number_not_trusted_
 Number of variables put into the list because there were not trusted.
CoinMessageHandler * handler_
 Message handler.
Messages messages_
 Messages.
Algoirithmic options
double maxmin_crit_no_sol_
 maxmin weight in branching decision when no solution has been found yet
double maxmin_crit_have_sol_
 maxmin weight in branching decision when no solution has been found yet
double setup_pseudo_frac_
 fraction of branching candidates that are not trusted yet
int numberBeforeTrustedList_
 number of times a branch has to happen so that it is trusted in setupList
int numberStrongRoot_
 number of strong branching points at root node
int numberStrongBackup_
 backup of numberStrong_ before Root node solve
int numberLookAhead_
 number of look-ahead strong-branching steps
int minNumberStrongBranch_
 Always strong branch that many first candidate in the list regardless of numberTrusted.
OsiPseudoCosts pseudoCosts_
 Stores the pseudo costs.
int trustStrongForPseudoCosts_
 Wether or not to trust strong branching results for updating pseudo costs.

Static Protected Attributes

static const std::string CNAME = "BonChooseVariable"
 Stores the class name for throwing errors.

Private Member Functions

 BonChooseVariable ()
 Default Constructor, forbiden for some reason.

Private Attributes

double time_limit_
 Global time limit for algorithm.
double start_time_
 Starting time of algorithm.

Classes

class  Messages

Detailed Description

This class chooses a variable to branch on.

This is the base class for the branching rules in Bonmin (inherits from OsiChooseVariable). This class implements a simple strong branching algorithm where the changes in the objective value induced by branching on a specific object are estimated with the pure virtual function fill_changes.

Definition at line 79 of file BonChooseVariable.hpp.


Member Enumeration Documentation

enum Bonmin::BonChooseVariable::StrongStatus [protected]

Statuses for strong branching candidates.

Enumerator:
NotDone 
Feasible  Child is proven feasible.
Infeasible  Child is proven infeasible.
NotFinished  Child is not finished.

Definition at line 107 of file BonChooseVariable.hpp.

enum Bonmin::BonChooseVariable::Messages_Types

Enumerator:
PS_COST_HISTORY 
PS_COST_MULT 
PS_COST_ESTIMATES 
CANDIDATE_LIST 
CANDIDATE_LIST2 
CANDIDATE_LIST3 
SB_HEADER 
SB_RES 
BRANCH_VAR 
CHOSEN_VAR 
UPDATE_PS_COST 
BON_CHOOSE_MESSAGES_DUMMY_END 

Definition at line 115 of file BonChooseVariable.hpp.

enum Bonmin::BonChooseVariable::DoStrongReturnStatuses

Enumerator:
provenInfeasible 
doneNoFixing  All done no variable can be fixed.
doneCanFix  Several variable can be fixed.
interuptedCanFix  Interupted and found a variable to fix.
maxTime  Interupted because of time limit.

Definition at line 150 of file BonChooseVariable.hpp.

enum Bonmin::BonChooseVariable::chooseVariableReturnStatuses

Return statuses for chooseVariable.

Enumerator:
infeasibleNode 
hasCandidate  Normal termination, found a variable to branch on.
feasibleNode  All variable are feasible, the node is feasible.
canFixAndStrongBranch  Found variable to fix and also has remaining candidate for strong branching.
canFixAndBranch  Found variable to fix and also has a (non-strong) branching candidate.
canFixNoCandidate  Can fix variables but does not have strong branching candidates.

Definition at line 158 of file BonChooseVariable.hpp.


Constructor & Destructor Documentation

Bonmin::BonChooseVariable::BonChooseVariable ( BabSetupBase b,
const OsiSolverInterface *  solver 
)

Constructor from solver (so we can set up arrays etc).

Set values of standard branching options.

Get values of options specific to BonChooseVariable.

Definition at line 43 of file BonChooseVariable.cpp.

References bb_log_level_, Bonmin::BabSetupBase::getIntParameter(), handler_, jnlst_, Bonmin::BabSetupBase::journalist(), maxmin_crit_have_sol_, maxmin_crit_no_sol_, minNumberStrongBranch_, Bonmin::BabSetupBase::MinReliability, numberBeforeTrustedList_, numberLookAhead_, Bonmin::BabSetupBase::NumberStrong, numberStrongRoot_, Bonmin::BabSetupBase::options(), pseudoCosts_, setup_pseudo_frac_, start_time_, time_limit_, and trustStrongForPseudoCosts_.

Bonmin::BonChooseVariable::BonChooseVariable ( const BonChooseVariable  ) 

Copy constructor.

Definition at line 88 of file BonChooseVariable.cpp.

References bb_log_level_, handler_, and jnlst_.

Bonmin::BonChooseVariable::~BonChooseVariable (  )  [virtual]

Destructor.

Definition at line 148 of file BonChooseVariable.cpp.

References handler_.

Bonmin::BonChooseVariable::BonChooseVariable (  )  [private]

Default Constructor, forbiden for some reason.

Referenced by clone().


Member Function Documentation

int Bonmin::BonChooseVariable::doStrongBranching ( OsiSolverInterface *  solver,
OsiBranchingInformation *  info,
int  numberToDo,
int  returnCriterion 
) [protected, virtual]

This is a utility function which does strong branching on a list of objects and stores the results in OsiHotInfo.objects.

On entry the object sequence is stored in the OsiHotInfo object and maybe more. It returns - -1 - one branch was infeasible both ways 0 - all inspected - nothing can be fixed 1 - all inspected - some can be fixed (returnCriterion==0) 2 - may be returning early - one can be fixed (last one done) (returnCriterion==1) 3 - returning because max time

Definition at line 775 of file BonChooseVariable.cpp.

References isRootNode(), maxminCrit(), numberLookAhead_, results_, start_time_, and time_limit_.

Referenced by chooseVariable().

void Bonmin::BonChooseVariable::passInMessageHandler ( CoinMessageHandler *  handler  )  [inline]

Definition at line 136 of file BonChooseVariable.hpp.

References handler_.

Referenced by Bonmin::BonminSetup::initializeBBB().

CoinMessageHandler& Bonmin::BonChooseVariable::message ( Messages_Types  type  )  const [inline]

Definition at line 143 of file BonChooseVariable.hpp.

References handler_, and messages_.

Referenced by chooseVariable(), computeMultipliers(), computeUsefulness(), setupList(), and updateInformation().

BonChooseVariable & Bonmin::BonChooseVariable::operator= ( const BonChooseVariable rhs  ) 

Assignment operator.

Definition at line 115 of file BonChooseVariable.cpp.

References bb_log_level_, cbc_model_, handler_, jnlst_, maxmin_crit_have_sol_, maxmin_crit_no_sol_, minNumberStrongBranch_, numberBeforeTrustedList_, numberLookAhead_, numberStrongRoot_, only_pseudo_when_trusted_, pseudoCosts_, results_, setup_pseudo_frac_, and trustStrongForPseudoCosts_.

OsiChooseVariable * Bonmin::BonChooseVariable::clone (  )  const [virtual]

Clone.

Reimplemented in CouenneChooseStrong.

Definition at line 143 of file BonChooseVariable.cpp.

References BonChooseVariable().

void Bonmin::BonChooseVariable::registerOptions ( Ipopt::SmartPtr< Bonmin::RegisteredOptions roptions  )  [static]

Definition at line 154 of file BonChooseVariable.cpp.

References Bonmin::RegisteredOptions::BonminCategory.

Referenced by Bonmin::BabSetupBase::registerAllOptions().

double Bonmin::BonChooseVariable::maxminCrit ( const OsiBranchingInformation *  info  )  const

Helper functions for setupList and chooseVariable.

Definition at line 945 of file BonChooseVariable.cpp.

References cbc_model_, maxmin_crit_have_sol_, and maxmin_crit_no_sol_.

Referenced by chooseVariable(), doStrongBranching(), setupList(), and BM_lp::sort_objects().

void Bonmin::BonChooseVariable::computeMultipliers ( double &  upMult,
double &  downMult 
) const

Definition at line 204 of file BonChooseVariable.cpp.

References message(), PS_COST_HISTORY, PS_COST_MULT, and pseudoCosts_.

Referenced by setupList(), and BM_lp::sort_objects().

double Bonmin::BonChooseVariable::computeUsefulness ( const double  MAXMIN_CRITERION,
const double  upMult,
const double  dowMult,
const double  value,
const OsiObject *  object,
int  i,
double &  value2 
) const

Definition at line 231 of file BonChooseVariable.cpp.

References message(), numberBeforeTrustedList_, PS_COST_ESTIMATES, and pseudoCosts_.

Referenced by setupList(), and BM_lp::sort_objects().

int Bonmin::BonChooseVariable::setupList ( OsiBranchingInformation *  info,
bool  initialize 
) [virtual]

Sets up strong list and clears all if initialize is true.

Returns number of infeasibilities.

Reimplemented in CouenneChooseStrong.

Definition at line 307 of file BonChooseVariable.cpp.

References bb_log_level_, CANDIDATE_LIST, CANDIDATE_LIST2, CANDIDATE_LIST3, CNAME, computeMultipliers(), computeUsefulness(), maxminCrit(), message(), number_not_trusted_, numberBeforeTrustedList_, numberStrongRoot_, OLD_USEFULLNESS, pseudoCosts_, and setup_pseudo_frac_.

int Bonmin::BonChooseVariable::chooseVariable ( OsiSolverInterface *  solver,
OsiBranchingInformation *  info,
bool  fixVariables 
) [virtual]

Choose a variable Returns - -1 Node is infeasible 0 Normal termination - we have a candidate 1 All looks satisfied - no candidate 2 We can change the bound on a variable - but we also have a strong branching candidate 3 We can change the bound on a variable - but we have a non-strong branching candidate 4 We can change the bound on a variable - no other candidates We can pick up branch from bestObjectIndex() and bestWhichWay() We can pick up a forced branch (can change bound) from firstForcedObjectIndex() and firstForcedWhichWay() If we have a solution then we can pick up from goodObjectiveValue() and goodSolution() If fixVariables is true then 2,3,4 are all really same as problem changed.

Reimplemented in CouenneChooseStrong.

Definition at line 599 of file BonChooseVariable.cpp.

References bb_log_level_, BRANCH_VAR, CHOSEN_VAR, doStrongBranching(), isRootNode(), maxminCrit(), message(), minNumberStrongBranch_, number_not_trusted_, numberStrongRoot_, only_pseudo_when_trusted_, pseudoCosts_, results_, SB_HEADER, and SB_RES.

void Bonmin::BonChooseVariable::updateInformation ( const OsiBranchingInformation *  info,
int  branch,
OsiHotInfo *  hotInfo 
) [virtual]

Given a candidate fill in useful information e.g. estimates.

On entry the object sequence is stored in the OsiHotInfo object and maybe more. It returns - -1 - one branch was infeasible both ways 0 - all inspected - nothing can be fixed 1 - all inspected - some can be fixed (returnCriterion==0) 2 - may be returning early - one can be fixed (last one done) (returnCriterion==1) 3 - returning because max time

Definition at line 961 of file BonChooseVariable.cpp.

References pseudoCosts_, and trustStrongForPseudoCosts_.

Referenced by CouenneChooseStrong::doStrongBranching().

void Bonmin::BonChooseVariable::updateInformation ( int  whichObject,
int  branch,
double  changeInObjective,
double  changeInValue,
int  status 
) [virtual]

Given a branch fill in useful information e.g. estimates.

Definition at line 1011 of file BonChooseVariable.cpp.

References cbc_model_, message(), pseudoCosts_, and UPDATE_PS_COST.

void Bonmin::BonChooseVariable::setCbcModel ( CbcModel *  cbc_model  )  [inline]

Method for setting CbcModel, which is used to get statusOfSearch.

Definition at line 234 of file BonChooseVariable.hpp.

References cbc_model_.

Referenced by Bonmin::Bab::branchAndBound().

void Bonmin::BonChooseVariable::setOnlyPseudoWhenTrusted ( bool  only_pseudo_when_trusted  )  [inline]

Definition at line 239 of file BonChooseVariable.hpp.

References only_pseudo_when_trusted_.

Referenced by Bonmin::BonminSetup::initializeBBB(), and Bonmin::CouenneSetup::InitializeCouenne().

const OsiPseudoCosts& Bonmin::BonChooseVariable::pseudoCosts (  )  const [inline]

Access to pseudo costs storage.

Definition at line 246 of file BonChooseVariable.hpp.

References pseudoCosts_.

Referenced by Bonmin::GuessHeuristic::solution(), and BM_lp::unpack_pseudo_costs().

OsiPseudoCosts& Bonmin::BonChooseVariable::pseudoCosts (  )  [inline]

Access to pseudo costs storage.

Definition at line 250 of file BonChooseVariable.hpp.

References pseudoCosts_.

int Bonmin::BonChooseVariable::determineStatus ( OsiSolverInterface *  solver  )  const [inline, protected]

Determine status of strong branching solution.

Definition at line 264 of file BonChooseVariable.hpp.

bool Bonmin::BonChooseVariable::isRootNode ( const OsiBranchingInformation *  info  )  const [protected]

detecting if this is root node

Definition at line 939 of file BonChooseVariable.cpp.

Referenced by chooseVariable(), and doStrongBranching().


Member Data Documentation

SmartPtr<Journalist> Bonmin::BonChooseVariable::jnlst_ [protected]

Holding on the a pointer to the journalist.

Reimplemented in CouenneChooseStrong.

Definition at line 255 of file BonChooseVariable.hpp.

Referenced by BonChooseVariable(), and operator=().

int Bonmin::BonChooseVariable::bb_log_level_ [protected]

verbosity level

Definition at line 258 of file BonChooseVariable.hpp.

Referenced by BonChooseVariable(), chooseVariable(), operator=(), and setupList().

vector<HotInfo> Bonmin::BonChooseVariable::results_ [protected]

Stores strong branching results.

Definition at line 261 of file BonChooseVariable.hpp.

Referenced by chooseVariable(), CouenneChooseStrong::doStrongBranching(), doStrongBranching(), and operator=().

double Bonmin::BonChooseVariable::time_limit_ [private]

Global time limit for algorithm.

Definition at line 279 of file BonChooseVariable.hpp.

Referenced by BonChooseVariable(), and doStrongBranching().

double Bonmin::BonChooseVariable::start_time_ [private]

Starting time of algorithm.

Definition at line 282 of file BonChooseVariable.hpp.

Referenced by BonChooseVariable(), and doStrongBranching().

CbcModel* Bonmin::BonChooseVariable::cbc_model_ [protected]

CbcModel, used to get status of search.

Definition at line 285 of file BonChooseVariable.hpp.

Referenced by maxminCrit(), operator=(), setCbcModel(), and updateInformation().

bool Bonmin::BonChooseVariable::only_pseudo_when_trusted_ [protected]

Flag indicating whether we don't want to mix strong branching and pseudo costs during the decision which variable to branch on.

Definition at line 290 of file BonChooseVariable.hpp.

Referenced by chooseVariable(), operator=(), and setOnlyPseudoWhenTrusted().

int Bonmin::BonChooseVariable::number_not_trusted_ [protected]

Number of variables put into the list because there were not trusted.

Definition at line 294 of file BonChooseVariable.hpp.

Referenced by chooseVariable(), and setupList().

CoinMessageHandler* Bonmin::BonChooseVariable::handler_ [protected]

Message handler.

Definition at line 297 of file BonChooseVariable.hpp.

Referenced by BonChooseVariable(), message(), operator=(), passInMessageHandler(), and ~BonChooseVariable().

Messages Bonmin::BonChooseVariable::messages_ [protected]

Messages.

Definition at line 300 of file BonChooseVariable.hpp.

Referenced by message().

double Bonmin::BonChooseVariable::maxmin_crit_no_sol_ [protected]

maxmin weight in branching decision when no solution has been found yet

Definition at line 306 of file BonChooseVariable.hpp.

Referenced by BonChooseVariable(), maxminCrit(), and operator=().

double Bonmin::BonChooseVariable::maxmin_crit_have_sol_ [protected]

maxmin weight in branching decision when no solution has been found yet

Definition at line 309 of file BonChooseVariable.hpp.

Referenced by BonChooseVariable(), maxminCrit(), and operator=().

double Bonmin::BonChooseVariable::setup_pseudo_frac_ [protected]

fraction of branching candidates that are not trusted yet

Definition at line 311 of file BonChooseVariable.hpp.

Referenced by BonChooseVariable(), operator=(), and setupList().

int Bonmin::BonChooseVariable::numberBeforeTrustedList_ [protected]

number of times a branch has to happen so that it is trusted in setupList

Definition at line 314 of file BonChooseVariable.hpp.

Referenced by BonChooseVariable(), computeUsefulness(), operator=(), and setupList().

int Bonmin::BonChooseVariable::numberStrongRoot_ [protected]

number of strong branching points at root node

Definition at line 316 of file BonChooseVariable.hpp.

Referenced by BonChooseVariable(), chooseVariable(), operator=(), and setupList().

int Bonmin::BonChooseVariable::numberStrongBackup_ [protected]

backup of numberStrong_ before Root node solve

Definition at line 318 of file BonChooseVariable.hpp.

int Bonmin::BonChooseVariable::numberLookAhead_ [protected]

number of look-ahead strong-branching steps

Definition at line 320 of file BonChooseVariable.hpp.

Referenced by BonChooseVariable(), doStrongBranching(), and operator=().

int Bonmin::BonChooseVariable::minNumberStrongBranch_ [protected]

Always strong branch that many first candidate in the list regardless of numberTrusted.

Definition at line 326 of file BonChooseVariable.hpp.

Referenced by BonChooseVariable(), chooseVariable(), and operator=().

OsiPseudoCosts Bonmin::BonChooseVariable::pseudoCosts_ [protected]

Stores the pseudo costs.

Definition at line 328 of file BonChooseVariable.hpp.

Referenced by BonChooseVariable(), chooseVariable(), computeMultipliers(), computeUsefulness(), operator=(), pseudoCosts(), setupList(), and updateInformation().

int Bonmin::BonChooseVariable::trustStrongForPseudoCosts_ [protected]

Wether or not to trust strong branching results for updating pseudo costs.

Definition at line 330 of file BonChooseVariable.hpp.

Referenced by BonChooseVariable(), operator=(), and updateInformation().

const std::string Bonmin::BonChooseVariable::CNAME = "BonChooseVariable" [static, protected]

Stores the class name for throwing errors.

Definition at line 338 of file BonChooseVariable.hpp.

Referenced by setupList().


The documentation for this class was generated from the following files:
Generated on Thu Oct 8 03:08:49 2009 by  doxygen 1.4.7