00001
00002
00003
00004
00005
00006
00007
00008
00009
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
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
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
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
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
00094
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
00126 index, way ? '>' : '<', integer ? (way ? ceil (brpt) : floor (brpt)) : brpt);
00127
00128
00129
00130
00131
00132
00133
00134
00135
00136
00137
00138
00139
00140 if (!way) solver -> setColUpper (index, integer ? floor (brpt) : brpt);
00141 else solver -> setColLower (index, integer ? ceil (brpt) : brpt);
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 ());
00154
00155
00156 CouNumber estimate = 0.;
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_ &&
00164 p -> doFBBT ()) {
00165
00166 p -> installCutOff ();
00167
00168 if (!p -> btCore (chg_bds))
00169 infeasible = true;
00170 else {
00171
00172 const double
00173 *lb = solver -> getColLower (),
00174 *ub = solver -> getColUpper ();
00175
00176
00177 estimate = CoinMax (0., p -> Lb (objind) - lb [objind]);
00178
00179
00180
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
00191
00192 int nchanged, *changed = NULL;
00193 OsiCuts cs;
00194
00195
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
00208 branchIndex_++;
00209
00210 return (infeasible ? COIN_DBL_MAX : estimate);
00211 }