/home/coin/SVN-release/OS-2.0.0/Couenne/src/branch/CouenneComplBranchingObject.cpp

Go to the documentation of this file.
00001 /* $Id: CouenneComplBranchingObject.cpp 141 2009-06-03 04:19:19Z pbelotti $ */
00002 /*
00003  * Name:    CouenneComplBranchingObject.cpp
00004  * Authors: Pietro Belotti, Carnegie Mellon University
00005  * Purpose: Branching object for auxiliary variables
00006  *
00007  * (C) Carnegie-Mellon University, 2006-08.
00008  * This file is licensed under the Common Public License (CPL)
00009  */
00010 
00011 #include "CoinHelperFunctions.hpp"
00012 
00013 #include "OsiRowCut.hpp"
00014 
00015 #include "CouenneSolverInterface.hpp"
00016 #include "CouenneProblem.hpp"
00017 #include "CouenneObject.hpp"
00018 #include "CouenneComplBranchingObject.hpp"
00019 
00020 // translate changed bound sparse array into a dense one
00021 void sparse2dense (int ncols, t_chg_bounds *chg_bds, int *&changed, int &nchanged);
00022 
00023 
00030 CouenneComplBranchingObject::CouenneComplBranchingObject (OsiSolverInterface *solver,
00031                                                           const OsiObject * originalObject,
00032                                                           JnlstPtr jnlst, 
00033                                                           expression *var, 
00034                                                           expression *var2, 
00035                                                           int way, 
00036                                                           CouNumber brpoint, 
00037                                                           bool doFBBT, bool doConvCuts):
00038 
00039   CouenneBranchingObject (solver, originalObject, jnlst, var, way, brpoint, doFBBT, doConvCuts),
00040   variable2_    (var2) {
00041 
00042   jnlst_ -> Printf (J_ITERSUMMARY, J_BRANCHING, 
00043                     "Complem. Branch: x%-3d = 0 or x%-3d = 0\n", 
00044                     way ? variable_ -> Index () : variable2_ -> Index ());
00045 }
00046 
00047 
00055 double CouenneComplBranchingObject::branch (OsiSolverInterface * solver) {
00056 
00057   // way = 0 if "x1=0" node, 
00058   //       1 if "x2=0" node
00059 
00060   int 
00061     way   = (!branchIndex_) ? firstBranch_ : !firstBranch_,
00062     index = way ? variable2_ -> Index () : variable_ -> Index ();
00063 
00064   jnlst_ -> Printf (J_ITERSUMMARY, J_BRANCHING, "Branching: x%-3d = 0\n", 
00065                     //printf ("complementarity Branching: x%-3d = 0\n", 
00066                     way ? variable2_ -> Index () : variable_ -> Index ());
00067 
00068   /*
00069   double time = CoinCpuTime ();
00070   jnlst_ -> Printf (J_VECTOR, J_BRANCHING,"[vbctool] %02d:%02d:%02d.%02d_I x%d%c=%g_[%g,%g]\n",
00071                     (int) (floor(time) / 3600), 
00072                     (int) (floor(time) / 60) % 60, 
00073                     (int) floor(time) % 60, 
00074                     (int) ((time - floor (time)) * 100),
00075                     index, way ? '>' : '<', integer ? ((way ? ceil (brpt): floor (brpt))) : brpt,
00076                     solver -> getColLower () [index],
00077                     solver -> getColUpper () [index]);
00078   */
00079 
00081 
00082   solver -> setColLower (index, 0.);
00083   solver -> setColUpper (index, 0.);
00084 
00086 
00087   CouenneSolverInterface *couenneSolver = dynamic_cast <CouenneSolverInterface *> (solver);
00088   CouenneProblem *p = couenneSolver -> CutGen () -> Problem ();
00089 
00090   int 
00091     nvars  = p -> nVars (),
00092     objind = p -> Obj (0) -> Body () -> Index ();
00093 
00094   p -> domain () -> push (nvars,
00095                           solver -> getColSolution (), 
00096                           solver -> getColLower    (), 
00097                           solver -> getColUpper    ()); // have to alloc+copy
00098 
00099   //CouNumber &estimate = way ? upEstimate_ : downEstimate_;
00100   CouNumber estimate = 0.;//way ? upEstimate_ : downEstimate_;
00101 
00102   t_chg_bounds *chg_bds = new t_chg_bounds [nvars];
00103 
00104   chg_bds [index].setUpper (t_chg_bounds::CHANGED);
00105   chg_bds [index].setLower (t_chg_bounds::CHANGED);
00106 
00107   bool infeasible = false;
00108 
00109   if (     doFBBT_ &&           // this branching object should do FBBT, and
00110       p -> doFBBT ()) {         // problem allowed to do FBBT
00111 
00112     p -> installCutOff ();
00113 
00114     if (!p -> btCore (chg_bds)) // done FBBT and this branch is infeasible
00115       infeasible = true;        // ==> report it
00116     else {
00117 
00118       const double
00119         *lb = solver -> getColLower (),
00120         *ub = solver -> getColUpper ();
00121 
00122       //CouNumber newEst = p -> Lb (objind) - lb [objind];
00123       estimate = CoinMax (0., p -> Lb (objind) - lb [objind]);
00124 
00125       //if (newEst > estimate) 
00126       //estimate = newEst;
00127 
00128       for (int i=0; i<nvars; i++) {
00129         if (p -> Lb (i) > lb [i]) solver -> setColLower (i, p -> Lb (i));
00130         if (p -> Ub (i) < ub [i]) solver -> setColUpper (i, p -> Ub (i));
00131       }
00132     }
00133   }
00134 
00135   if (!infeasible && doConvCuts_ && simulate_) { 
00136     // generate convexification cuts before solving new node's LP
00137 
00138     int nchanged, *changed = NULL;
00139     OsiCuts cs;
00140 
00141     // sparsify structure with info on changed bounds and get convexification cuts
00142     sparse2dense (nvars, chg_bds, changed, nchanged);
00143     couenneSolver -> CutGen () -> genRowCuts (*solver, cs, nchanged, changed, chg_bds);
00144     free (changed);
00145 
00146     solver -> applyCuts (cs);
00147   }
00148 
00149   delete [] chg_bds;
00150 
00151   p -> domain () -> pop ();
00152 
00153   // next time do other branching
00154   branchIndex_++;
00155 
00156   return (infeasible ? COIN_DBL_MAX : estimate); // estimated change in objective function
00157 }

Generated on Mon Aug 3 03:02:19 2009 by  doxygen 1.4.7