/home/coin/SVN-release/OS-2.0.1/Couenne/src/branch/CouenneBranchingObject.cpp

Go to the documentation of this file.
00001 /* $Id$
00002  *
00003  * Name:    CouenneBranchingObject.cpp
00004  * Authors: Pierre Bonami, IBM Corp.
00005  *          Pietro Belotti, Carnegie Mellon University
00006  * Purpose: Branching object for auxiliary variables
00007  *
00008  * (C) Carnegie-Mellon University, 2006-08.
00009  * This file is licensed under the Common Public License (CPL)
00010  */
00011 
00012 #include "CoinHelperFunctions.hpp"
00013 
00014 #include "OsiRowCut.hpp"
00015 
00016 #include "CouenneSolverInterface.hpp"
00017 #include "CouenneProblem.hpp"
00018 #include "CouenneObject.hpp"
00019 #include "CouenneBranchingObject.hpp"
00020 
00021 // translate changed bound sparse array into a dense one
00022 void sparse2dense (int ncols, t_chg_bounds *chg_bds, int *&changed, int &nchanged);
00023 
00024 
00031 CouenneBranchingObject::CouenneBranchingObject (OsiSolverInterface *solver,
00032                                                 const OsiObject * originalObject,
00033                                                 JnlstPtr jnlst, 
00034                                                 expression *var, 
00035                                                 int way, 
00036                                                 CouNumber brpoint, 
00037                                                 bool doFBBT, bool doConvCuts):
00038 
00039   OsiTwoWayBranchingObject (solver, originalObject, way, brpoint),
00040   variable_     (var),
00041   jnlst_        (jnlst),
00042   doFBBT_       (doFBBT),
00043   doConvCuts_   (doConvCuts),
00044   downEstimate_ (0.),
00045   upEstimate_   (0.),
00046   simulate_     (false) {
00047 
00048   // This two-way branching rule is only applied when both lower and
00049   // upper bound are finite. Otherwise, a CouenneThreeWayBranchObj is
00050   // used (see CouenneThreeWayBranchObj.hpp).
00051   //
00052   // The rule is as follows:
00053   //
00054   // - if x is well inside the interval (both bounds are infinite or
00055   // there is a difference of at least COU_NEAR_BOUND), set
00056   // value_ to x;
00057   //
00058   // - otherwise, try to get far from bounds by setting value_ to a
00059   // convex combination of current and midpoint
00060   //
00061   // TODO: consider branching value that maximizes distance from
00062   // current point (how?)
00063 
00064   value_ = (*variable_) ();
00065 
00066   if (fabs (brpoint) < COUENNE_INFINITY) 
00067     value_ = brpoint;
00068 
00069   CouNumber lb, ub;
00070   var -> getBounds (lb, ub);
00071 
00072   // do not branch too close to bounds
00073   if ((lb > -COUENNE_INFINITY) && (ub < COUENNE_INFINITY)) {
00074     if      ((value_ - lb) / (ub-lb) < closeToBounds) value_ = lb + (ub-lb) * closeToBounds;
00075     else if ((ub - value_) / (ub-lb) < closeToBounds) value_ = ub + (lb-ub) * closeToBounds;
00076   }
00077 
00078   jnlst_ -> Printf (J_ITERSUMMARY, J_BRANCHING, 
00079                     "Branch: x%-3d will branch on %g (cur. %g) [%g,%g]; firstBranch_ = %d\n", 
00080                     variable_ -> Index (), value_, (*variable_) (), lb, ub, firstBranch_);
00081 }
00082 
00083 
00091 double CouenneBranchingObject::branch (OsiSolverInterface * solver) {
00092 
00093   // way = 0 if "<=" node, 
00094   //       1 if ">=" node
00095 
00096   int 
00097     way   = (!branchIndex_) ? firstBranch_ : !firstBranch_,
00098     index = variable_ -> Index ();
00099 
00100   bool 
00101     integer    = variable_ -> isInteger (),
00102     infeasible = false;
00103 
00104   CouNumber
00105     l      = solver -> getColLower () [index],
00106     u      = solver -> getColUpper () [index],
00107     brpt   = value_;
00108 
00109   if (way) {
00110     if      (value_ < l)             
00111       jnlst_->Printf(J_STRONGWARNING, J_BRANCHING, "Nonsense up-br: [ %.8f ,(%.8f)] -> %.8f\n",l,u,value_);
00112     else if (value_ < l+COUENNE_EPS) 
00113       jnlst_->Printf(J_STRONGWARNING, J_BRANCHING, "## WEAK  up-br: [ %.8f ,(%.8f)] -> %.8f\n",l,u,value_);
00114   } else {
00115     if      (value_ > u)             
00116       jnlst_->Printf(J_STRONGWARNING, J_BRANCHING, "Nonsense dn-br: [(%.8f), %.8f ] -> %.8f\n",l,u,value_);
00117     else if (value_ > u+COUENNE_EPS) 
00118       jnlst_->Printf(J_STRONGWARNING, J_BRANCHING, "## WEAK  dn-br: [(%.8f), %.8f ] -> %.8f\n",l,u,value_);
00119   }
00120 
00121   if ((brpt < l) || (brpt > u))
00122     brpt = 0.5 * (l+u);
00123 
00124   jnlst_ -> Printf (J_ITERSUMMARY, J_BRANCHING, "Branching: x%-3d %c= %g\n", 
00125                     //printf ("Branching: x%-3d %c= %g\n", 
00126                     index, way ? '>' : '<', integer ? (way ? ceil (brpt) : floor (brpt)) : brpt);
00127 
00128   /*
00129   double time = CoinCpuTime ();
00130   jnlst_ -> Printf (J_VECTOR, J_BRANCHING,"[vbctool] %02d:%02d:%02d.%02d_I x%d%c=%g_[%g,%g]\n",
00131                     (int) (floor(time) / 3600), 
00132                     (int) (floor(time) / 60) % 60, 
00133                     (int) floor(time) % 60, 
00134                     (int) ((time - floor (time)) * 100),
00135                     index, way ? '>' : '<', integer ? ((way ? ceil (brpt): floor (brpt))) : brpt,
00136                     solver -> getColLower () [index],
00137                     solver -> getColUpper () [index]);
00138   */
00139 
00140   if (!way) solver -> setColUpper (index, integer ? floor (brpt) : brpt); // down branch
00141   else      solver -> setColLower (index, integer ? ceil  (brpt) : brpt); // up   branch
00142 
00143   CouenneSolverInterface *couenneSolver = dynamic_cast <CouenneSolverInterface *> (solver);
00144   CouenneProblem *p = couenneSolver -> CutGen () -> Problem ();
00145 
00146   int 
00147     nvars  = p -> nVars (),
00148     objind = p -> Obj (0) -> Body () -> Index ();
00149 
00150   p -> domain () -> push (nvars,
00151                           solver -> getColSolution (), 
00152                           solver -> getColLower    (), 
00153                           solver -> getColUpper    ()); // have to alloc+copy
00154 
00155   //CouNumber &estimate = way ? upEstimate_ : downEstimate_;
00156   CouNumber estimate = 0.;//way ? upEstimate_ : downEstimate_;
00157 
00158   t_chg_bounds *chg_bds = new t_chg_bounds [nvars];
00159 
00160   if (!way) chg_bds [index].setUpper (t_chg_bounds::CHANGED);
00161   else      chg_bds [index].setLower (t_chg_bounds::CHANGED);
00162 
00163   if (     doFBBT_ &&           // this branching object should do FBBT, and
00164       p -> doFBBT ()) {         // problem allowed to do FBBT
00165 
00166     p -> installCutOff ();
00167 
00168     if (!p -> btCore (chg_bds)) // done FBBT and this branch is infeasible
00169       infeasible = true;        // ==> report it
00170     else {
00171 
00172       const double
00173         *lb = solver -> getColLower (),
00174         *ub = solver -> getColUpper ();
00175 
00176       //CouNumber newEst = p -> Lb (objind) - lb [objind];
00177       estimate = CoinMax (0., p -> Lb (objind) - lb [objind]);
00178 
00179       //if (newEst > estimate) 
00180       //estimate = newEst;
00181 
00182       for (int i=0; i<nvars; i++) {
00183         if (p -> Lb (i) > lb [i]) solver -> setColLower (i, p -> Lb (i));
00184         if (p -> Ub (i) < ub [i]) solver -> setColUpper (i, p -> Ub (i));
00185       }
00186     }
00187   }
00188 
00189   if (!infeasible && doConvCuts_ && simulate_) { 
00190     // generate convexification cuts before solving new node's LP
00191 
00192     int nchanged, *changed = NULL;
00193     OsiCuts cs;
00194 
00195     // sparsify structure with info on changed bounds and get convexification cuts
00196     sparse2dense (nvars, chg_bds, changed, nchanged);
00197     couenneSolver -> CutGen () -> genRowCuts (*solver, cs, nchanged, changed, chg_bds);
00198     free (changed);
00199 
00200     solver -> applyCuts (cs);
00201   }
00202 
00203   delete [] chg_bds;
00204 
00205   p -> domain () -> pop ();
00206 
00207   // next time do other branching
00208   branchIndex_++;
00209 
00210   return (infeasible ? COIN_DBL_MAX : estimate); // estimated change in objective function
00211 }

Generated on Thu Oct 8 03:02:55 2009 by  doxygen 1.4.7