00001
00002
00003
00004
00005
00006
00007
00008 #include <cassert>
00009 #include <cstdlib>
00010 #include <cmath>
00011 #include <cfloat>
00012 #include <climits>
00013
00014
00015 #include "CoinTypes.hpp"
00016 #include "OsiSolverInterface.hpp"
00017 #include "OsiSolverBranch.hpp"
00018 #include "BonNWayObject.hpp"
00019 #include "CoinSort.hpp"
00020 #include "CoinError.hpp"
00021
00022
00023 namespace Bonmin {
00024
00025
00026
00027 BonNWayObject::BonNWayObject ()
00028 : OsiObject(),
00029 members_(),
00030 consequence_(NULL),
00031 quicky_(false),
00032 only_frac_branch_(0)
00033 {
00034 }
00035
00036
00037 BonNWayObject::BonNWayObject (int numberMembers,
00038 const int * which, int identifier):
00039 OsiObject(),
00040 members_(numberMembers),
00041 quicky_(false),
00042 only_frac_branch_(0)
00043 {
00044 if (numberMembers) {
00045 memcpy(members_.data(), which, numberMembers*sizeof(int));
00046 } else {
00047 }
00048 consequence_ = NULL;
00049 }
00050
00051
00052 BonNWayObject::BonNWayObject ( const BonNWayObject & rhs)
00053 : OsiObject(rhs), members_(rhs.members_), quicky_(rhs.quicky_), only_frac_branch_(rhs.only_frac_branch_)
00054 {
00055 consequence_ = NULL;
00056 if (members_.size()) {
00057 if (rhs.consequence_) {
00058 consequence_ = new n_way_consequences* [members_.size()];
00059 for (size_t i = 0; i < members_.size(); i++) {
00060 if (rhs.consequence_[i])
00061 consequence_[i] = rhs.consequence_[i]->clone();
00062 else
00063 consequence_[i] = NULL;
00064 }
00065 }
00066 } else {
00067 }
00068 }
00069
00070
00071 OsiObject *
00072 BonNWayObject::clone() const
00073 {
00074 return new BonNWayObject(*this);
00075 }
00076
00077
00078 BonNWayObject &
00079 BonNWayObject::operator=( const BonNWayObject & rhs)
00080 {
00081 if (this != &rhs) {
00082 OsiObject::operator=(rhs);
00083 members_ = rhs.members_;
00084 quicky_ = rhs.quicky_;
00085 only_frac_branch_ = rhs.only_frac_branch_;
00086 if (consequence_) {
00087 for (size_t i = 0; i < members_.size(); i++)
00088 delete consequence_[i];
00089 delete [] consequence_;
00090 consequence_ = NULL;
00091 }
00092 if (rhs.consequence_) {
00093 consequence_ = new n_way_consequences* [members_.size()];
00094 for (size_t i = 0; i < members_.size(); i++) {
00095 if (rhs.consequence_[i])
00096 consequence_[i] = rhs.consequence_[i]->clone();
00097 else
00098 consequence_[i] = NULL;
00099 }
00100 }
00101 }
00102 return *this;
00103 }
00104
00105
00106 BonNWayObject::~BonNWayObject ()
00107 {
00108 if (consequence_) {
00109 for (size_t i = 0; i < members_.size(); i++)
00110 delete consequence_[i];
00111 delete [] consequence_;
00112 }
00113 }
00114
00115 void
00116 BonNWayObject::setConsequence(int iMember, const n_way_consequences& consequence)
00117 {
00118 if (!consequence_) {
00119 consequence_ = new n_way_consequences* [members_.size()];
00120 for (size_t i = 0; i < members_.size(); i++)
00121 consequence_[i] = NULL;
00122 }
00123 consequence_[iMember] = consequence.clone();
00124 }
00125
00126
00127 void
00128 BonNWayObject::applyConsequence(OsiSolverInterface * solver, int iSequence, int state) const
00129 {
00130 assert (state == -9999 || state == 9999);
00131 if (consequence_) {
00132 n_way_consequences* consequence = consequence_[iSequence];
00133 if (consequence)
00134 consequence->applyToSolver(solver, state);
00135 }
00136 }
00137 double
00138 BonNWayObject::infeasibility(const OsiBranchingInformation * info,
00139 int &preferredWay) const
00140 {
00141 int numberUnsatis = 0;
00142 size_t j;
00143 const double * solution = info->solution_;
00144 const double * lower = info->lower_;
00145 const double * upper = info->upper_;
00146 double largestValue = 0.0;
00147
00148 double integerTolerance = info->integerTolerance_;
00149
00150 for (j = 0; j < members_.size(); j++) {
00151 int iColumn = members_[j];
00152 double value = solution[iColumn];
00153 value = CoinMax(value, lower[iColumn]);
00154 value = CoinMin(value, upper[iColumn]);
00155 double distance = CoinMin(value - lower[iColumn], upper[iColumn] - value);
00156 if (distance > integerTolerance) {
00157 numberUnsatis++;
00158 largestValue = CoinMax(distance, largestValue);
00159 }
00160 }
00161 preferredWay = 1;
00162 if (numberUnsatis) {
00163 return largestValue;
00164 } else {
00165 return 0.0;
00166 }
00167 }
00168
00169
00170 double
00171 BonNWayObject::feasibleRegion(OsiSolverInterface * solver,
00172 const OsiBranchingInformation * info) const
00173 {
00174 size_t j;
00175 const double * solution = info->solution_;
00176 const double * lower = info->lower_;
00177 const double * upper = info->upper_;
00178 double integerTolerance = info->integerTolerance_;
00179 double r_val = 0;
00180 for (j = 0; j < members_.size(); j++) {
00181 int iColumn = members_[j];
00182 double value = solution[iColumn];
00183 value = CoinMax(value, lower[iColumn]);
00184 value = CoinMin(value, upper[iColumn]);
00185 if (value >= upper[iColumn] - integerTolerance) {
00186 r_val += value - upper[iColumn];
00187 solver->setColLower(iColumn, upper[iColumn]);
00188 } else {
00189 assert (value <= lower[iColumn] + integerTolerance);
00190 r_val += value - lower[iColumn];
00191 solver->setColUpper(iColumn, lower[iColumn]);
00192 }
00193 }
00194 return r_val;
00195 }
00196
00197 OsiBranchingObject *
00198 BonNWayObject::createBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) const
00199 {
00200
00201 const double * solution = info->solution_;
00202 const double * lower = info->lower_;
00203 const double * upper = info->upper_;
00204 double integerTolerance = info->integerTolerance_;
00205 double cutoff = info->cutoff_;
00206 std::vector<int> list;
00207 list.reserve(members_.size());
00208 std::vector<double> sort;
00209 sort.reserve(members_.size());
00210
00211 int n_skipped = 0;
00212 std::list<int> skipped;
00213
00214 for (size_t j = 0; j < members_.size(); j++) {
00215 const int& iColumn = members_[j];
00216 double value = solution[iColumn];
00217 value = CoinMax(value, lower[iColumn]);
00218 value = CoinMin(value, upper[iColumn]);
00219 if (upper[iColumn] > lower[iColumn]) {
00220 if(bounds_.size() && bounds_[j] > cutoff) {
00221
00222 continue;
00223 }
00224 if( (quicky_ || info->depth_ > only_frac_branch_ ) && fabs(solution[iColumn] - lower[iColumn]) < integerTolerance){
00225 if(info->depth_ > only_frac_branch_) {
00226 n_skipped++;
00227
00228 skipped.push_back(static_cast<int>(j));
00229 continue;
00230 }
00231 }
00232 double distance = upper[iColumn] - value;
00233 list.push_back(static_cast<int>(j));
00234 sort.push_back(distance);
00235 }
00236 }
00237
00238 if(n_skipped == 1) {
00239 const int& iColumn = members_[skipped.front()];
00240 double value = solution[iColumn];
00241 value = CoinMax(value, lower[iColumn]);
00242 value = CoinMin(value, upper[iColumn]);
00243 double distance = upper[iColumn] - value;
00244 list.push_back(skipped.front());
00245 sort.push_back(distance);
00246 skipped.pop_front();
00247 n_skipped --;
00248 }
00249
00250
00251 CoinSort_2(sort.data(), sort.data() + sort.size(), list.data());
00252
00253 OsiBranchingObject * branch;
00254
00255
00256 branch = new BonNWayBranchingObject(solver, this, list, skipped);
00257 return branch;
00258 }
00259
00260
00261
00262 BonNWayBranchingObject::BonNWayBranchingObject()
00263 : OsiBranchingObject(), object_(NULL),
00264 order_(), skipped_()
00265 {
00266 }
00267
00268
00269 BonNWayBranchingObject::BonNWayBranchingObject (OsiSolverInterface * solver,
00270 const BonNWayObject * nway,
00271 const std::vector<int>& order, const std::list<int> &skipped)
00272 : OsiBranchingObject(solver, 0.5), order_(order), skipped_(skipped)
00273 {
00274 numberBranches_ = static_cast<int>(order_.size()) + (!skipped.empty());
00275 object_ = nway;
00276 }
00277
00278
00279 BonNWayBranchingObject::BonNWayBranchingObject ( const BonNWayBranchingObject & rhs) :
00280 OsiBranchingObject(rhs), object_(rhs.object_),
00281 order_(rhs.order_), skipped_(rhs.skipped_)
00282 {
00283 object_ = rhs.object_;
00284 }
00285
00286
00287 BonNWayBranchingObject &
00288 BonNWayBranchingObject::operator=( const BonNWayBranchingObject & rhs)
00289 {
00290 if (this != &rhs) {
00291 OsiBranchingObject::operator=(rhs);
00292 object_ = rhs.object_;
00293 order_ = rhs.order_;
00294 skipped_ = rhs.skipped_;
00295 }
00296 return *this;
00297 }
00298 OsiBranchingObject *
00299 BonNWayBranchingObject::clone() const
00300 {
00301 return (new BonNWayBranchingObject(*this));
00302 }
00303
00304
00305
00306 BonNWayBranchingObject::~BonNWayBranchingObject ()
00307 {
00308 }
00309
00310 double
00311 BonNWayBranchingObject::branch(OsiSolverInterface * solver)
00312 {
00313 int which = branchIndex_;
00314 branchIndex_++;
00315 if(!skipped_.empty() && branchIndex_ == static_cast<int>(order_.size())){
00316 which = -1;
00317 }
00318 return branch(solver, which);
00319 }
00320
00321 double
00322 BonNWayBranchingObject::branch(OsiSolverInterface * solver, int which)
00323 {
00324 const double * lower = solver->getColLower();
00325 const double * upper = solver->getColUpper();
00326 const int * members = object_->members();
00327 for (size_t j = 0; j < order_.size(); j++) {
00328 const int& iSequence = order_[j];
00329 const int& iColumn = members[iSequence];
00330 if (j != which) {
00331 solver->setColUpper(iColumn, lower[iColumn]);
00332 assert (lower[iColumn] > -1.0e20);
00333 } else {
00334 solver->setColLower(iColumn, upper[iColumn]);
00335 #ifdef FULL_PRINT
00336 printf("Up Fix %d to %g\n", iColumn, upper[iColumn]);
00337 #endif
00338 assert (upper[iColumn] < 1.0e20);
00339
00340 object_->applyConsequence(solver, iSequence, 9999);
00341 }
00342 }
00343 if(which != -1){
00344 for(std::list<int>::iterator k = skipped_.begin() ; k != skipped_.end() ; k++){
00345 assert(upper[members[*k]] > lower[members[*k]] + 0.5);
00346 solver->setColUpper(members[*k], lower[members[*k]]);
00347 }
00348 }
00349 return 0.0;
00350 }
00351
00352 }
00353