1 /* $Id$ */ 2 // Copyright (C) 2005, International Business Machines 3 // Corporation and others. All Rights Reserved. 4 // This code is licensed under the terms of the Eclipse Public License (EPL). 5 6 #ifndef CbcBranchDynamic_H 7 #define CbcBranchDynamic_H 8 9 #include "CoinPackedMatrix.hpp" 10 #include "CbcSimpleIntegerDynamicPseudoCost.hpp" 11 #include "CbcBranchActual.hpp" 12 13 /** Branching decision dynamic class 14 15 This class implements a simple algorithm 16 (betterBranch()) for choosing a branching variable when dynamic pseudo costs. 17 */ 18 19 class CbcBranchDynamicDecision : public CbcBranchDecision { 20 public: 21 // Default Constructor 22 CbcBranchDynamicDecision(); 23 24 // Copy constructor 25 CbcBranchDynamicDecision(const CbcBranchDynamicDecision &); 26 27 virtual ~CbcBranchDynamicDecision(); 28 29 /// Clone 30 virtual CbcBranchDecision *clone() const; 31 32 /// Initialize, <i>e.g.</i> before the start of branch selection at a node 33 virtual void initialize(CbcModel *model); 34 35 /** \brief Compare two branching objects. Return nonzero if \p thisOne is 36 better than \p bestSoFar. 37 38 The routine compares branches using the values supplied in \p numInfUp and 39 \p numInfDn until a solution is found by search, after which it uses the 40 values supplied in \p changeUp and \p changeDn. The best branching object 41 seen so far and the associated parameter values are remembered in the 42 \c CbcBranchDynamicDecision object. The nonzero return value is +1 if the 43 up branch is preferred, -1 if the down branch is preferred. 44 45 As the names imply, the assumption is that the values supplied for 46 \p numInfUp and \p numInfDn will be the number of infeasibilities reported 47 by the branching object, and \p changeUp and \p changeDn will be the 48 estimated change in objective. Other measures can be used if desired. 49 50 Because an \c CbcBranchDynamicDecision object remembers the current best 51 branching candidate (#bestObject_) as well as the values used in the 52 comparison, the parameter \p bestSoFar is redundant, hence unused. 53 */ 54 virtual int betterBranch(CbcBranchingObject *thisOne, 55 CbcBranchingObject *bestSoFar, 56 double changeUp, int numInfUp, 57 double changeDn, int numInfDn); 58 /** Sets or gets best criterion so far */ 59 virtual void setBestCriterion(double value); 60 virtual double getBestCriterion() const; 61 /** Says whether this method can handle both methods - 62 1 better, 2 best, 3 both */ whichMethod()63 virtual int whichMethod() 64 { 65 return 3; 66 } 67 68 /** Saves a clone of current branching object. Can be used to update 69 information on object causing branch - after branch */ 70 virtual void saveBranchingObject(OsiBranchingObject *object); 71 /** Pass in information on branch just done. 72 assumes object can get information from solver */ 73 virtual void updateInformation(OsiSolverInterface *solver, 74 const CbcNode *node); 75 76 private: 77 /// Illegal Assignment operator 78 CbcBranchDynamicDecision &operator=(const CbcBranchDynamicDecision &rhs); 79 80 /// data 81 82 /// "best" so far 83 double bestCriterion_; 84 85 /// Change up for best 86 double bestChangeUp_; 87 88 /// Number of infeasibilities for up 89 int bestNumberUp_; 90 91 /// Change down for best 92 double bestChangeDown_; 93 94 /// Number of infeasibilities for down 95 int bestNumberDown_; 96 97 /// Pointer to best branching object 98 CbcBranchingObject *bestObject_; 99 }; 100 /** Simple branching object for an integer variable with pseudo costs 101 102 This object can specify a two-way branch on an integer variable. For each 103 arm of the branch, the upper and lower bounds on the variable can be 104 independently specified. 105 106 Variable_ holds the index of the integer variable in the integerVariable_ 107 array of the model. 108 */ 109 110 class CbcDynamicPseudoCostBranchingObject : public CbcIntegerBranchingObject { 111 112 public: 113 /// Default constructor 114 CbcDynamicPseudoCostBranchingObject(); 115 116 /** Create a standard floor/ceiling branch object 117 118 Specifies a simple two-way branch. Let \p value = x*. One arm of the 119 branch will be is lb <= x <= floor(x*), the other ceil(x*) <= x <= ub. 120 Specify way = -1 to set the object state to perform the down arm first, 121 way = 1 for the up arm. 122 */ 123 CbcDynamicPseudoCostBranchingObject(CbcModel *model, int variable, 124 int way, double value, 125 CbcSimpleIntegerDynamicPseudoCost *object); 126 127 /** Create a degenerate branch object 128 129 Specifies a `one-way branch'. Calling branch() for this object will 130 always result in lowerValue <= x <= upperValue. Used to fix a variable 131 when lowerValue = upperValue. 132 */ 133 134 CbcDynamicPseudoCostBranchingObject(CbcModel *model, int variable, int way, 135 double lowerValue, double upperValue); 136 137 /// Copy constructor 138 CbcDynamicPseudoCostBranchingObject(const CbcDynamicPseudoCostBranchingObject &); 139 140 /// Assignment operator 141 CbcDynamicPseudoCostBranchingObject &operator=(const CbcDynamicPseudoCostBranchingObject &rhs); 142 143 /// Clone 144 virtual CbcBranchingObject *clone() const; 145 146 /// Destructor 147 virtual ~CbcDynamicPseudoCostBranchingObject(); 148 149 /// Does part of constructor 150 void fillPart(int variable, 151 int way, double value, 152 CbcSimpleIntegerDynamicPseudoCost *object); 153 154 using CbcBranchingObject::branch; 155 /** \brief Sets the bounds for the variable according to the current arm 156 of the branch and advances the object state to the next arm. 157 This version also changes guessed objective value 158 */ 159 virtual double branch(); 160 161 /** Some branchingObjects may claim to be able to skip 162 strong branching. If so they have to fill in CbcStrongInfo. 163 The object mention in incoming CbcStrongInfo must match. 164 Returns nonzero if skip is wanted */ 165 virtual int fillStrongInfo(CbcStrongInfo &info); 166 167 /// Change in guessed changeInGuessed() const168 inline double changeInGuessed() const 169 { 170 return changeInGuessed_; 171 } 172 /// Set change in guessed setChangeInGuessed(double value)173 inline void setChangeInGuessed(double value) 174 { 175 changeInGuessed_ = value; 176 } 177 /// Return object object() const178 inline CbcSimpleIntegerDynamicPseudoCost *object() const 179 { 180 return object_; 181 } 182 /// Set object setObject(CbcSimpleIntegerDynamicPseudoCost * object)183 inline void setObject(CbcSimpleIntegerDynamicPseudoCost *object) 184 { 185 object_ = object; 186 } 187 188 /** Return the type (an integer identifier) of \c this */ type() const189 virtual CbcBranchObjType type() const 190 { 191 return DynamicPseudoCostBranchObj; 192 } 193 194 // LL: compareOriginalObject and compareBranchingObject are inherited from 195 // CbcIntegerBranchingObject thus need not be declared/defined here. After 196 // all, this kind of branching object is simply using pseudocosts to make 197 // decisions, but once the decisions are made they are the same kind as in 198 // the underlying class. 199 200 protected: 201 /// Change in guessed objective value for next branch 202 double changeInGuessed_; 203 /// Pointer back to object 204 CbcSimpleIntegerDynamicPseudoCost *object_; 205 }; 206 207 #endif 208 209 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2 210 */ 211