diff options
Diffstat (limited to 'build/Bonmin/include/coin/BonChooseVariable.hpp')
| -rw-r--r-- | build/Bonmin/include/coin/BonChooseVariable.hpp | 345 |
1 files changed, 345 insertions, 0 deletions
diff --git a/build/Bonmin/include/coin/BonChooseVariable.hpp b/build/Bonmin/include/coin/BonChooseVariable.hpp new file mode 100644 index 0000000..82e7575 --- /dev/null +++ b/build/Bonmin/include/coin/BonChooseVariable.hpp @@ -0,0 +1,345 @@ +// Copyright (C) 2006, 2008 International Business Machines +// Corporation and others. All Rights Reserved. +#ifndef BonChooseVariable_H +#define BonChooseVariable_H + +#include "OsiChooseVariable.hpp" +#ifdef BONMIN_CURVATURE_BRANCHING +#include "BonCurvatureEstimator.hpp" +#endif +#include "BonOsiTMINLPInterface.hpp" +#include "CoinMessageHandler.hpp" +#include "BonBabSetupBase.hpp" +// Forward declaration +class CbcModel; + +#define OLD_USEFULLNESS + +namespace Bonmin +{ + + class HotInfo : public OsiHotInfo { + public: + /// Default constructor + HotInfo(); + + /// Constructor from usefull information + HotInfo( OsiSolverInterface * solver, + const OsiBranchingInformation *info, + const OsiObject * const * objects, int whichObject); + + /// Copy constructor + HotInfo(const HotInfo & other); + + /// Assignment operator + HotInfo & operator=(const HotInfo & rhs); + + /// Clone + virtual OsiHotInfo * clone() const; + + /// Destructor + virtual ~HotInfo(); + + /// Fill in some usefull information after a strong branching is done: + int updateInformation( const OsiSolverInterface * solver, const OsiBranchingInformation * info, + OsiChooseVariable * choose); + + /// up infeasibility + double upInfeasibility() const{ + return infeasibilities_[1]; + } + + /// down infeasibility + double downInfeasibility() const{ + return infeasibilities_[0]; + } + + + /// Set the down infeasibility + void setUpInfeasibility(double x){ + assert(branchingObject_->numberBranches()==2); + infeasibilities_[1] = x; + } + + /// Set the down infeasibility + void setDownInfeasibility(double x){ + assert(branchingObject_->numberBranches()==2); + infeasibilities_[0] = x; + } + private: + /// infeasibilities of children + vector<double> infeasibilities_; + }; + + /** 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. + */ + + class BonChooseVariable : public OsiChooseVariable + { + protected: + /** 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 + + */ + virtual int doStrongBranching( OsiSolverInterface * solver, + OsiBranchingInformation *info, + int numberToDo, int returnCriterion); +#ifndef OLD_USEFULLNESS + /** Criterion applied to sort candidates.*/ + enum CandidateSortCriterion { + DecrPs = 0, + IncrPs, + DecrInfeas, + IncrInfeas}; +#endif + + /** Statuses for strong branching candidates.*/ + enum StrongStatus{ + NotDone=-1, + Feasible/** Child is proven feasible.*/, + Infeasible /** Child is proven infeasible.*/, + NotFinished /** Child is not finished.*/}; + public: + /** \name Message handling.*/ + /** @{ */ + enum Messages_Types { + PS_COST_HISTORY = 0, + PS_COST_MULT, + PS_COST_ESTIMATES, + CANDIDATE_LIST, + CANDIDATE_LIST2, + CANDIDATE_LIST3, + SB_START, + SB_HEADER, + SB_RES, + BRANCH_VAR, + CHOSEN_VAR, + UPDATE_PS_COST, + BON_CHOOSE_MESSAGES_DUMMY_END + }; + + class Messages : public CoinMessages + { + public: + Messages(); + }; + + void passInMessageHandler(CoinMessageHandler * handler) { + int logLevel = handler_->logLevel(); + delete handler_; + handler_ = handler->clone(); + handler_->setLogLevel(logLevel); + } + + CoinMessageHandler& message(Messages_Types type) const { + return handler_->message(type, messages_); + } + /** @} */ + + + + enum DoStrongReturnStatuses{ + provenInfeasible = -1 /** One branch has two infeasible children.*/, + 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.*/}; + + /** Return statuses for chooseVariable.*/ + enum chooseVariableReturnStatuses{ + infeasibleNode = -1/** Node has been proven infeasible.*/, + 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.*/ + }; + /// Constructor from solver (so we can set up arrays etc) + BonChooseVariable (BabSetupBase& b, const OsiSolverInterface* solver); + + /// Copy constructor + BonChooseVariable (const BonChooseVariable &); + + /// Assignment operator + BonChooseVariable & operator= (const BonChooseVariable& rhs); + + /// Clone + virtual OsiChooseVariable * clone() const; + + /// Destructor + virtual ~BonChooseVariable (); + + static void registerOptions(Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions); + + /** Helper functions for setupList and chooseVariable */ + double maxminCrit(const OsiBranchingInformation* info) const; + 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; + + /** Sets up strong list and clears all if initialize is true. + Returns number of infeasibilities. */ + virtual int setupList ( OsiBranchingInformation *info, bool initialize); + + /** 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 int chooseVariable( OsiSolverInterface * solver, OsiBranchingInformation *info, bool fixVariables); + /** 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 + + */ + + /// Given a candidate fill in useful information e.g. estimates + virtual void updateInformation(const OsiBranchingInformation *info, + int branch, OsiHotInfo * hotInfo); +#if 1 + /// Given a branch fill in useful information e.g. estimates + virtual void updateInformation( int whichObject, int branch, + double changeInObjective, double changeInValue, + int status); +#endif + + /** Method for setting CbcModel, which is used to get statusOfSearch */ + void setCbcModel(CbcModel* cbc_model) + { + cbc_model_ = cbc_model; + } + + void setOnlyPseudoWhenTrusted(bool only_pseudo_when_trusted) + { + only_pseudo_when_trusted_ = only_pseudo_when_trusted; + } + + + /** Access to pseudo costs storage.*/ + const OsiPseudoCosts & pseudoCosts() const{ + return pseudoCosts_;} + + /** Access to pseudo costs storage.*/ + OsiPseudoCosts & pseudoCosts() { + return pseudoCosts_;} + protected: + + /// Holding on the a pointer to the journalist + Ipopt::SmartPtr<Ipopt::Journalist> jnlst_; + + /// verbosity level + int bb_log_level_; + + /** Stores strong branching results.*/ + vector<HotInfo> results_; + + /** Determine status of strong branching solution.*/ + int determineStatus(OsiSolverInterface * solver) const { + if (solver->isProvenOptimal()) + return 0; // optimal + else if (solver->isIterationLimitReached() + &&!solver->isDualObjectiveLimitReached()) + return 2; // unknown + else + return 1; // infeasible + } + + private: + /** Default Constructor, forbiden for some reason.*/ + BonChooseVariable (); + + /** Global time limit for algorithm. */ + double time_limit_; + + /** Starting time of algorithm.*/ + double start_time_; + protected: + /// CbcModel, used to get status of search + CbcModel* cbc_model_; + + /** Flag indicating whether we don't want to mix strong branching + * and pseudo costs during the decision which variable to branch + * on */ + bool only_pseudo_when_trusted_; + + /** Number of variables put into the list because there were not + * trusted */ + int number_not_trusted_; + + /** Message handler.*/ + CoinMessageHandler * handler_; + + /** Messages.*/ + Messages messages_; + // ToDo: Make this options + /** @name Algoirithmic options */ + //@{ + /** maxmin weight in branching decision when no solution has been + * found yet */ + double maxmin_crit_no_sol_; + /** maxmin weight in branching decision when no solution has been + * found yet */ + double maxmin_crit_have_sol_; + /** fraction of branching candidates that are not trusted yet */ + double setup_pseudo_frac_; + /** number of times a branch has to happen so that it is trusted in + * setupList */ + int numberBeforeTrustedList_; + /** number of strong branching points at root node */ + int numberStrongRoot_; + /** backup of numberStrong_ before Root node solve */ + int numberStrongBackup_; + /** number of look-ahead strong-branching steps */ + int numberLookAhead_; +#ifndef OLD_USEFULLNESS + /** Criterion to use in setup list.*/ + CandidateSortCriterion sortCrit_; +#endif + /** Always strong branch that many first candidate in the list regardless of numberTrusted.*/ + int minNumberStrongBranch_; + /** Stores the pseudo costs. */ + OsiPseudoCosts pseudoCosts_; + /** Wether or not to trust strong branching results for updating pseudo costs.*/ + int trustStrongForPseudoCosts_; + + //@} + + /** detecting if this is root node */ + bool isRootNode(const OsiBranchingInformation *info) const; + + /** Stores the class name for throwing errors.*/ + static const std::string CNAME; + }; + +} +#endif |