cbcintlinprog added

1 files changed, 345 insertions, 0 deletions

diff --git a/thirdparty/linux/include/coin/BonChooseVariable.hpp b/thirdparty/linux/include/coin/BonChooseVariable.hpp
new file mode 100644
index 0000000..82e7575
--- /dev/null
+++ b/thirdparty/linux/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