1 /* $Id$ 2 * 3 * Name: CouenneObject.hpp 4 * Authors: Pierre Bonami, IBM Corp. 5 * Pietro Belotti, Carnegie Mellon University 6 * Purpose: Object for auxiliary variables 7 * 8 * (C) Carnegie-Mellon University, 2006-11. 9 * This file is licensed under the Eclipse Public License (EPL) 10 */ 11 12 #ifndef COUENNEOBJECT_HPP 13 #define COUENNEOBJECT_HPP 14 15 #include "BonBabSetupBase.hpp" 16 17 #include "CouenneExprVar.hpp" 18 #include "CouenneJournalist.hpp" 19 #include "OsiBranchingObject.hpp" 20 21 namespace Couenne { 22 23 const CouNumber default_alpha = 0.25; 24 const CouNumber default_clamp = 0.2; 25 const CouNumber max_pseudocost = 1000.; 26 27 /// if |branching point| > this, change it 28 const double large_bound = 1e9; 29 30 #define AGGR_MUL 2 31 #define THRES_ZERO_SYMM 0.8 32 33 const CouNumber closeToBounds = .05; 34 35 /// Define what kind of branching (two- or three-way) and where to 36 /// start from: left, (center,) or right. The last is to help 37 /// diversify branching through randomization, which may help when the 38 /// same variable is branched upon in several points of the BB tree. 39 40 enum {TWO_LEFT, TWO_RIGHT, TWO_RAND, 41 THREE_LEFT, THREE_CENTER, THREE_RIGHT, THREE_RAND, BRANCH_NONE}; 42 43 class funtriplet; 44 class CouenneProblem; 45 class CouenneCutGenerator; 46 47 CouNumber minMaxDelta (funtriplet *ft, CouNumber lb, CouNumber ub); 48 CouNumber maxHeight (funtriplet *ft, CouNumber lb, CouNumber ub); 49 50 51 /// OsiObject for auxiliary variables $w=f(x)$. 52 /// 53 /// Associated with a multi-variate function $f(x)$ and a related 54 /// infeasibility $|w-f(x)|$, creates branches to help restoring 55 /// feasibility 56 57 class CouenneObject: public OsiObject { 58 59 public: 60 61 /// type of up/down estimate to return for pseudocosts 62 enum pseudocostMult {INFEASIBILITY, 63 INTERVAL_LP, INTERVAL_LP_REV, 64 INTERVAL_BR, INTERVAL_BR_REV, 65 PROJECTDIST}; 66 67 /// type of object (for branching variable selection) 68 enum branch_obj {EXPR_OBJ, VAR_OBJ, VT_OBJ}; 69 70 /// strategy names 71 enum brSelStrat {NO_STRATEGY, NO_BRANCH, MID_INTERVAL, MIN_AREA, BALANCED, LP_CENTRAL, LP_CLAMPED}; 72 73 /// empty constructor (for unused objects) 74 CouenneObject (); 75 76 /// Constructor with information for branching point selection strategy 77 CouenneObject (CouenneCutGenerator *cutgen, 78 CouenneProblem *p, 79 exprVar *ref, Bonmin::BabSetupBase *base, JnlstPtr jnlst); 80 81 /// Constructor with lesser information, used for infeasibility only 82 CouenneObject (exprVar *ref, Bonmin::BabSetupBase *base, JnlstPtr jnlst); 83 84 /// Destructor ~CouenneObject()85 ~CouenneObject () {} 86 87 /// Copy constructor 88 CouenneObject (const CouenneObject &src); 89 90 /// Cloning method clone() const91 virtual CouenneObject * clone () const 92 {return new CouenneObject (*this);} 93 94 /// set object parameters by reading from command line 95 void setParameters (Bonmin::BabSetupBase *base); 96 97 /// compute infeasibility of this variable, |w - f(x)| (where w is 98 /// the auxiliary variable defined as w = f(x) 99 virtual double infeasibility (const OsiBranchingInformation *info, int &way) const; 100 101 /// compute infeasibility of this variable, |w - f(x)|, where w is 102 /// the auxiliary variable defined as w = f(x) 103 virtual double checkInfeasibility (const OsiBranchingInformation * info) const; 104 105 /// fix (one of the) arguments of reference auxiliary variable 106 virtual double feasibleRegion (OsiSolverInterface*, const OsiBranchingInformation*) const; 107 108 /// create CouenneBranchingObject or CouenneThreeWayBranchObj based 109 /// on this object 110 virtual OsiBranchingObject *createBranch (OsiSolverInterface*, 111 const OsiBranchingInformation*, int) const; 112 113 /// return reference auxiliary variable Reference() const114 exprVar *Reference () const 115 {return reference_;} 116 117 /// return branching point selection strategy Strategy() const118 enum brSelStrat Strategy () const 119 {return strategy_;} 120 121 /// pick branching point based on current strategy 122 CouNumber getBrPoint (funtriplet *ft, CouNumber x0, CouNumber l, CouNumber u, const OsiBranchingInformation *info = NULL) const; 123 124 /// returns a point "inside enough" a given interval, or x if it 125 /// already is. Modify alpha_ using gap provided by info 126 CouNumber midInterval (CouNumber x, CouNumber l, CouNumber u, const OsiBranchingInformation *info = NULL) const; 127 128 /// Return "down" estimate (for non-convex, distance old <--> new LP point) downEstimate() const129 virtual double downEstimate () const 130 {//if (jnlst_ -> ProduceOutput (J_MATRIX, J_BRANCHING)) { 131 //printf ("DOWN EST = %g for ", downEstimate_); 132 //reference_ -> print (); 133 //printf ("\n"); 134 //} 135 return downEstimate_;} 136 137 /// Return "up" estimate (for non-convex, distance old <--> new LP point) upEstimate() const138 virtual double upEstimate () const 139 {//if (jnlst_ -> ProduceOutput (J_MATRIX, J_BRANCHING)) { 140 //printf ("UP EST = %g for ", upEstimate_); 141 //reference_ -> print (); 142 //printf ("\n"); 143 //} 144 return upEstimate_;} 145 146 /// set up/down estimate (0 for down, 1 for up). This happens in 147 /// CouenneChooseStrong, where a new LP point is available and we 148 /// can measure distance from old LP point. This is the denominator 149 /// we use in pseudocost setEstimate(double est,int direction)150 void setEstimate (double est, int direction) 151 {(direction ? upEstimate_ : downEstimate_) = est;} 152 153 /// set up/down estimates based on branching information 154 void setEstimates (const OsiBranchingInformation *info, 155 CouNumber *infeasibility, 156 CouNumber *brpt) const; 157 158 /// are we on the bad or good side of the expression? isCuttable() const159 virtual bool isCuttable () const { 160 return (reference_ -> Image ()) ? 161 ((!(reference_ -> isInteger ())) && 162 reference_ -> Image () -> isCuttable (problem_, reference_ -> Index ())) : 163 (!(reference_ -> isInteger ())); 164 } 165 166 /// integer infeasibility: min {value - floor(value), ceil(value) - value} 167 virtual double intInfeasibility (double value, double lb, double ub) const; 168 169 /// Defines safe interval percentage for using LP point as a branching point lp_clamp() const170 CouNumber lp_clamp () const 171 {return lp_clamp_;} 172 173 /// Returns the column index columnNumber() const174 virtual int columnNumber () const 175 {return (reference_ ? reference_ -> Index () : -1);} 176 177 protected: 178 179 /// pointer to cut generator (not necessary, can be NULL) 180 CouenneCutGenerator *cutGen_; 181 182 /// pointer to Couenne problem 183 CouenneProblem *problem_; 184 185 /// The (auxiliary) variable this branching object refers to. If the 186 /// expression is w=f(x,y), this is w, as opposed to 187 /// CouenneBranchingObject, where it would be either x or y. 188 exprVar *reference_; 189 190 /// Branching point selection strategy 191 enum brSelStrat strategy_; 192 193 /// SmartPointer to the Journalist 194 JnlstPtr jnlst_; 195 196 /// Combination parameter for the mid-point branching point 197 /// selection strategy 198 CouNumber alpha_; 199 200 /// Defines safe interval percentage for using LP point as a branching point 201 CouNumber lp_clamp_; 202 203 /// feasibility tolerance (equal to that of CouenneProblem) 204 CouNumber feas_tolerance_; 205 206 /// shall we do Feasibility based Bound Tightening (FBBT) at branching? 207 bool doFBBT_; 208 209 /// shall we add convexification cuts at branching? 210 bool doConvCuts_; 211 212 /// down estimate (to be used in pseudocost) 213 mutable double downEstimate_; 214 215 /// up estimate (to be used in pseudocost) 216 mutable double upEstimate_; 217 218 /// multiplier type for pseudocost 219 enum pseudocostMult pseudoMultType_; 220 }; 221 222 } 223 224 #endif 225