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

Go to the documentation of this file.
00001 /* $Id: CouenneComplBranchingObject.cpp 694 2011-06-18 20:13:17Z stefan $
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-10.
00008  * This file is licensed under the Eclipse Public License (EPL)
00009  */
00010 
00011 #include "CoinHelperFunctions.hpp"
00012 
00013 #include "OsiRowCut.hpp"
00014 
00015 #include "CouenneCutGenerator.hpp"
00016 #include "CouenneProblem.hpp"
00017 #include "CouenneProblemElem.hpp"
00018 #include "CouenneObject.hpp"
00019 #include "CouenneComplBranchingObject.hpp"
00020 
00021 using namespace Ipopt;
00022 using namespace Couenne;
00023 
00024 // translate changed bound sparse array into a dense one
00025 void sparse2dense (int ncols, t_chg_bounds *chg_bds, int *&changed, int &nchanged);
00026 
00027 
00034 CouenneComplBranchingObject::CouenneComplBranchingObject (OsiSolverInterface *solver,
00035                                                           const OsiObject * originalObject,
00036                                                           JnlstPtr jnlst, 
00037                                                           CouenneCutGenerator *c,
00038                                                           CouenneProblem *p,
00039                                                           expression *var, 
00040                                                           expression *var2, 
00041                                                           int way, 
00042                                                           CouNumber brpoint, 
00043                                                           bool doFBBT, bool doConvCuts, int sign):
00044 
00045   CouenneBranchingObject (solver, originalObject, jnlst, c, p, var, way, brpoint, doFBBT, doConvCuts),
00046   variable2_    (var2),
00047   sign_         (sign) {
00048 
00049   jnlst_ -> Printf (J_ITERSUMMARY, J_BRANCHING, 
00050                     "Complem. Branch: x%-3d = 0 or x%-3d = 0\n", 
00051                     way ? variable_ -> Index () : variable2_ -> Index ());
00052 }
00053 
00054 
00062 double CouenneComplBranchingObject::branch (OsiSolverInterface * solver) {
00063 
00064   // way = 0 if "x1=0" node, 
00065   //       1 if "x2=0" node
00066 
00067   int 
00068     way   = (!branchIndex_) ? firstBranch_ : !firstBranch_,
00069     index = way ? variable2_ -> Index () : variable_ -> Index ();
00070 
00071   jnlst_ -> Printf (J_ITERSUMMARY, J_BRANCHING, "Branching: x%-3d = 0\n", 
00072                     //printf ("complementarity Branching: x%-3d = 0\n", 
00073                     way ? variable2_ -> Index () : variable_ -> Index ());
00074 
00075   /*
00076   double time = CoinCpuTime ();
00077   jnlst_ -> Printf (J_VECTOR, J_BRANCHING,"[vbctool] %02d:%02d:%02d.%02d_I x%d%c=%g_[%g,%g]\n",
00078                     (int) (floor(time) / 3600), 
00079                     (int) (floor(time) / 60) % 60, 
00080                     (int) floor(time) % 60, 
00081                     (int) ((time - floor (time)) * 100),
00082                     index, way ? '>' : '<', integer ? ((way ? ceil (brpt): floor (brpt))) : brpt,
00083                     solver -> getColLower () [index],
00084                     solver -> getColUpper () [index]);
00085   */
00086 
00088 
00089   int 
00090     ind0 = variable_  -> Index (),
00091     ind1 = variable2_ -> Index ();
00092 
00093   if (!sign_) { // constraint x1 x2 = 0
00094     solver -> setColLower (index, 0.);
00095     solver -> setColUpper (index, 0.);
00096   } else {
00097 
00098     if (sign_ < 0) // it is a x1 x2 <= 0
00099       if (!way) {  // branch on second orthant first
00100         solver -> setColUpper (ind0, 0.);
00101         solver -> setColLower (ind1, 0.);
00102       } else {     // branch on fourth orthant first
00103         solver -> setColLower (ind0, 0.);
00104         solver -> setColUpper (ind1, 0.);
00105       }
00106     else           // it is a x1 x2 >= 0
00107       if (!way) {  // branch on first orthant first
00108         solver -> setColLower (ind0, 0.);
00109         solver -> setColLower (ind1, 0.);
00110       } else {     // branch on third orthant first
00111         solver -> setColUpper (ind0, 0.);
00112         solver -> setColUpper (ind1, 0.);
00113       }
00114   }
00115 
00117 
00118   //CouenneSolverInterface *couenneSolver = dynamic_cast <CouenneSolverInterface *> (solver);
00119   //CouenneProblem *p = couenneSolver -> CutGen () -> Problem ();
00120 
00121   int 
00122     nvars  = problem_ -> nVars (),
00123     objind = problem_ -> Obj (0) -> Body () -> Index ();
00124 
00125   //CouNumber &estimate = way ? upEstimate_ : downEstimate_;
00126   CouNumber estimate = 0.;//way ? upEstimate_ : downEstimate_;
00127 
00128   bool infeasible = false;
00129 
00130   // only bother doing all of the below if the allocated and pushed
00131   // stuff will be really used
00132   if ((doFBBT_ && problem_ -> doFBBT ()) ||
00133       (doConvCuts_ && simulate_ && cutGen_)) { 
00134 
00135     problem_ -> domain () -> push (nvars,
00136                                    solver -> getColSolution (), 
00137                                    solver -> getColLower    (), 
00138                                    solver -> getColUpper    ()); // have to alloc+copy
00139 
00140     t_chg_bounds *chg_bds = new t_chg_bounds [nvars];
00141 
00142     if (!sign_) {
00143       chg_bds [index].setLower (t_chg_bounds::CHANGED);
00144       chg_bds [index].setUpper (t_chg_bounds::CHANGED);
00145     } else {
00146       chg_bds [ind0].setLower (t_chg_bounds::CHANGED);
00147       chg_bds [ind0].setUpper (t_chg_bounds::CHANGED);
00148 
00149       chg_bds [ind1].setLower (t_chg_bounds::CHANGED);
00150       chg_bds [ind1].setUpper (t_chg_bounds::CHANGED);
00151     }
00152 
00153     if (            doFBBT_ &&           // this branching object should do FBBT, and
00154         problem_ -> doFBBT ()) {         // problem allowed to do FBBT
00155 
00156       problem_ -> installCutOff ();
00157 
00158       if (!problem_ -> btCore (chg_bds)) // done FBBT and this branch is infeasible
00159         infeasible = true;        // ==> report it
00160       else {
00161 
00162         const double
00163           *lb = solver -> getColLower (),
00164           *ub = solver -> getColUpper ();
00165 
00166         //CouNumber newEst = problem_ -> Lb (objind) - lb [objind];
00167         estimate = CoinMax (0., problem_ -> Lb (objind) - lb [objind]);
00168 
00169         //if (newEst > estimate) 
00170         //estimate = newEst;
00171 
00172         for (int i=0; i<nvars; i++) {
00173           if (problem_ -> Lb (i) > lb [i]) solver -> setColLower (i, problem_ -> Lb (i));
00174           if (problem_ -> Ub (i) < ub [i]) solver -> setColUpper (i, problem_ -> Ub (i));
00175         }
00176       }
00177     }
00178 
00179     if (!infeasible && doConvCuts_ && simulate_ && cutGen_) { 
00180       // generate convexification cuts before solving new node's LP
00181 
00182       int nchanged, *changed = NULL;
00183       OsiCuts cs;
00184 
00185       // sparsify structure with info on changed bounds and get convexification cuts
00186       sparse2dense (nvars, chg_bds, changed, nchanged);
00187       cutGen_ -> genRowCuts (*solver, cs, nchanged, changed, chg_bds);
00188       free (changed);
00189 
00190       solver -> applyCuts (cs);
00191     }
00192 
00193     delete [] chg_bds;
00194 
00195     problem_ -> domain () -> pop ();
00196   }
00197 
00198   // next time do other branching
00199   branchIndex_++;
00200 
00201   return (infeasible ? COIN_DBL_MAX : estimate); // estimated change in objective function
00202 }

Generated on Thu Sep 22 03:05:56 2011 by  doxygen 1.4.7