00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011 #include "CoinHelperFunctions.hpp"
00012
00013 #include "OsiRowCut.hpp"
00014
00015
00016 #include "CouenneSOSObject.hpp"
00017 #include "CouenneProblem.hpp"
00018
00019
00020 void sparse2dense (int ncols, t_chg_bounds *chg_bds, int *&changed, int &nchanged);
00021
00022
00030 double CouenneSOSBranchingObject::branch (OsiSolverInterface * solver) {
00031
00032
00033 double retval = OsiSOSBranchingObject::branch (solver);
00034
00035
00036
00037
00038 int
00039 nvars = problem_ -> nVars (),
00040 objind = problem_ -> Obj (0) -> Body () -> Index ();
00041
00042 bool infeasible = false;
00043
00044 problem_ -> domain () -> push (nvars,
00045 solver -> getColSolution (),
00046 solver -> getColLower (),
00047 solver -> getColUpper ());
00048
00049 int nMembers = dynamic_cast <const OsiSOS *> (originalObject ()) -> numberMembers ();
00050 const int *Members = dynamic_cast <const OsiSOS *> (originalObject ()) -> members ();
00051
00052
00053 CouNumber estimate = 0.;
00054
00055 t_chg_bounds *chg_bds = new t_chg_bounds [nvars];
00056
00057 while (nMembers--) {
00058 chg_bds [*Members] .setUpper (t_chg_bounds::CHANGED);
00059 chg_bds [*Members++].setLower (t_chg_bounds::CHANGED);
00060 }
00061
00062 if ( doFBBT_ &&
00063 problem_ -> doFBBT ()) {
00064
00065 problem_ -> installCutOff ();
00066
00067 if (!problem_ -> btCore (chg_bds))
00068 infeasible = true;
00069 else {
00070
00071 const double
00072 *lb = solver -> getColLower (),
00073 *ub = solver -> getColUpper ();
00074
00075
00076 estimate = CoinMax (0., problem_ -> Lb (objind) - lb [objind]);
00077
00078
00079
00080
00081 for (int i=0; i<nvars; i++) {
00082 if (problem_ -> Lb (i) > lb [i]) solver -> setColLower (i, problem_ -> Lb (i));
00083 if (problem_ -> Ub (i) < ub [i]) solver -> setColUpper (i, problem_ -> Ub (i));
00084 }
00085 }
00086 }
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098
00099
00100
00101
00102 delete [] chg_bds;
00103
00104 problem_ -> domain () -> pop ();
00105
00106
00107 branchIndex_++;
00108
00109
00110 return (infeasible ? COIN_DBL_MAX : CoinMax (retval, estimate));
00111 }
00112
00113
00116 OsiBranchingObject *CouenneSOSObject::createBranch (OsiSolverInterface* si,
00117 const OsiBranchingInformation* info, int way) const
00118 {
00119
00120
00121 int j;
00122 const double * solution = info->solution_;
00123 double tolerance = info->primalTolerance_;
00124 const double * upper = info->upper_;
00125 int firstNonFixed=-1;
00126 int lastNonFixed=-1;
00127 int firstNonZero=-1;
00128 int lastNonZero = -1;
00129 double weight = 0.0;
00130 double sum =0.0;
00131 for (j=0;j<numberMembers_;j++) {
00132 int iColumn = members_[j];
00133 if (upper[iColumn]) {
00134 double value = CoinMax(0.0,solution[iColumn]);
00135 sum += value;
00136 if (firstNonFixed<0)
00137 firstNonFixed=j;
00138 lastNonFixed=j;
00139 if (value>tolerance) {
00140 weight += weights_[j]*value;
00141 if (firstNonZero<0)
00142 firstNonZero=j;
00143 lastNonZero=j;
00144 }
00145 }
00146 }
00147 assert (lastNonZero-firstNonZero>=sosType_) ;
00148
00149 assert (sum>0.0);
00150 weight /= sum;
00151 int iWhere;
00152 double separator=0.0;
00153 for (iWhere=firstNonZero;iWhere<lastNonZero;iWhere++)
00154 if (weight<weights_[iWhere+1])
00155 break;
00156 if (sosType_==1) {
00157
00158 separator = 0.5 *(weights_[iWhere]+weights_[iWhere+1]);
00159 } else {
00160
00161 if (iWhere==lastNonFixed-1)
00162 iWhere = lastNonFixed-2;
00163 separator = weights_[iWhere+1];
00164 }
00165
00166
00167 return new CouenneSOSBranchingObject (problem_, reference_,
00168 si, this, way, separator, jnlst_, doFBBT_, doConvCuts_);
00169 }