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