[1573] | 1 | // $Id: CbcSimpleIntegerPseudoCost.cpp 1899 2013-04-09 18:12:08Z forrest $ |
---|
| 2 | // Copyright (C) 2002, International Business Machines |
---|
| 3 | // Corporation and others. All Rights Reserved. |
---|
| 4 | // This code is licensed under the terms of the Eclipse Public License (EPL). |
---|
| 5 | |
---|
[1357] | 6 | // Edwin 11/10/2009-- carved out of CbcBranchActual |
---|
[1573] | 7 | |
---|
[1357] | 8 | #if defined(_MSC_VER) |
---|
| 9 | // Turn off compiler warning about long names |
---|
| 10 | # pragma warning(disable:4786) |
---|
| 11 | #endif |
---|
| 12 | #include <cassert> |
---|
| 13 | #include <cstdlib> |
---|
| 14 | #include <cmath> |
---|
| 15 | #include <cfloat> |
---|
| 16 | //#define CBC_DEBUG |
---|
| 17 | |
---|
| 18 | #include "CoinTypes.hpp" |
---|
| 19 | #include "OsiSolverInterface.hpp" |
---|
| 20 | #include "OsiSolverBranch.hpp" |
---|
| 21 | #include "CbcModel.hpp" |
---|
| 22 | #include "CbcMessage.hpp" |
---|
| 23 | #include "CbcSimpleIntegerPseudoCost.hpp" |
---|
| 24 | #include "CbcSimpleIntegerDynamicPseudoCost.hpp" |
---|
| 25 | #include "CbcBranchActual.hpp" |
---|
| 26 | #include "CoinSort.hpp" |
---|
| 27 | #include "CoinError.hpp" |
---|
| 28 | |
---|
| 29 | //############################################################################## |
---|
| 30 | |
---|
| 31 | /** Default Constructor |
---|
| 32 | |
---|
| 33 | Equivalent to an unspecified binary variable. |
---|
| 34 | */ |
---|
| 35 | CbcSimpleIntegerPseudoCost::CbcSimpleIntegerPseudoCost () |
---|
| 36 | : CbcSimpleInteger(), |
---|
| 37 | downPseudoCost_(1.0e-5), |
---|
| 38 | upPseudoCost_(1.0e-5), |
---|
| 39 | upDownSeparator_(-1.0), |
---|
| 40 | method_(0) |
---|
| 41 | { |
---|
| 42 | } |
---|
| 43 | |
---|
| 44 | /** Useful constructor |
---|
| 45 | |
---|
| 46 | Loads actual upper & lower bounds for the specified variable. |
---|
| 47 | */ |
---|
| 48 | CbcSimpleIntegerPseudoCost::CbcSimpleIntegerPseudoCost (CbcModel * model, |
---|
| 49 | int iColumn, double breakEven) |
---|
| 50 | : CbcSimpleInteger(model, iColumn, breakEven) |
---|
| 51 | { |
---|
| 52 | const double * cost = model->getObjCoefficients(); |
---|
| 53 | double costValue = CoinMax(1.0e-5, fabs(cost[iColumn])); |
---|
| 54 | // treat as if will cost what it says up |
---|
| 55 | upPseudoCost_ = costValue; |
---|
| 56 | // and balance at breakeven |
---|
| 57 | downPseudoCost_ = ((1.0 - breakEven_) * upPseudoCost_) / breakEven_; |
---|
| 58 | upDownSeparator_ = -1.0; |
---|
| 59 | method_ = 0; |
---|
| 60 | } |
---|
| 61 | |
---|
| 62 | /** Useful constructor |
---|
| 63 | |
---|
| 64 | Loads actual upper & lower bounds for the specified variable. |
---|
| 65 | */ |
---|
| 66 | CbcSimpleIntegerPseudoCost::CbcSimpleIntegerPseudoCost (CbcModel * model, |
---|
| 67 | int iColumn, double downPseudoCost, |
---|
| 68 | double upPseudoCost) |
---|
| 69 | : CbcSimpleInteger(model, iColumn) |
---|
| 70 | { |
---|
| 71 | downPseudoCost_ = CoinMax(1.0e-10, downPseudoCost); |
---|
| 72 | upPseudoCost_ = CoinMax(1.0e-10, upPseudoCost); |
---|
| 73 | breakEven_ = upPseudoCost_ / (upPseudoCost_ + downPseudoCost_); |
---|
| 74 | upDownSeparator_ = -1.0; |
---|
| 75 | method_ = 0; |
---|
| 76 | } |
---|
| 77 | // Useful constructor - passed and model index and pseudo costs |
---|
| 78 | CbcSimpleIntegerPseudoCost::CbcSimpleIntegerPseudoCost (CbcModel * model, |
---|
| 79 | int /*dummy*/, |
---|
| 80 | int iColumn, |
---|
| 81 | double downPseudoCost, double upPseudoCost) |
---|
| 82 | { |
---|
| 83 | *this = CbcSimpleIntegerPseudoCost(model, iColumn, downPseudoCost, upPseudoCost); |
---|
| 84 | columnNumber_ = iColumn; |
---|
| 85 | } |
---|
| 86 | |
---|
| 87 | // Copy constructor |
---|
| 88 | CbcSimpleIntegerPseudoCost::CbcSimpleIntegerPseudoCost ( const CbcSimpleIntegerPseudoCost & rhs) |
---|
| 89 | : CbcSimpleInteger(rhs), |
---|
| 90 | downPseudoCost_(rhs.downPseudoCost_), |
---|
| 91 | upPseudoCost_(rhs.upPseudoCost_), |
---|
| 92 | upDownSeparator_(rhs.upDownSeparator_), |
---|
| 93 | method_(rhs.method_) |
---|
| 94 | |
---|
| 95 | { |
---|
| 96 | } |
---|
| 97 | |
---|
| 98 | // Clone |
---|
| 99 | CbcObject * |
---|
| 100 | CbcSimpleIntegerPseudoCost::clone() const |
---|
| 101 | { |
---|
| 102 | return new CbcSimpleIntegerPseudoCost(*this); |
---|
| 103 | } |
---|
| 104 | |
---|
| 105 | // Assignment operator |
---|
| 106 | CbcSimpleIntegerPseudoCost & |
---|
| 107 | CbcSimpleIntegerPseudoCost::operator=( const CbcSimpleIntegerPseudoCost & rhs) |
---|
| 108 | { |
---|
| 109 | if (this != &rhs) { |
---|
| 110 | CbcSimpleInteger::operator=(rhs); |
---|
| 111 | downPseudoCost_ = rhs.downPseudoCost_; |
---|
| 112 | upPseudoCost_ = rhs.upPseudoCost_; |
---|
| 113 | upDownSeparator_ = rhs.upDownSeparator_; |
---|
| 114 | method_ = rhs.method_; |
---|
| 115 | } |
---|
| 116 | return *this; |
---|
| 117 | } |
---|
| 118 | |
---|
| 119 | // Destructor |
---|
| 120 | CbcSimpleIntegerPseudoCost::~CbcSimpleIntegerPseudoCost () |
---|
| 121 | { |
---|
| 122 | } |
---|
| 123 | CbcBranchingObject * |
---|
| 124 | CbcSimpleIntegerPseudoCost::createCbcBranch(OsiSolverInterface * solver, const OsiBranchingInformation * /*info*/, int way) |
---|
| 125 | { |
---|
| 126 | //OsiSolverInterface * solver = model_->solver(); |
---|
| 127 | const double * solution = model_->testSolution(); |
---|
| 128 | const double * lower = solver->getColLower(); |
---|
| 129 | const double * upper = solver->getColUpper(); |
---|
| 130 | double value = solution[columnNumber_]; |
---|
| 131 | value = CoinMax(value, lower[columnNumber_]); |
---|
| 132 | value = CoinMin(value, upper[columnNumber_]); |
---|
| 133 | #ifndef NDEBUG |
---|
| 134 | double nearest = floor(value + 0.5); |
---|
| 135 | double integerTolerance = |
---|
| 136 | model_->getDblParam(CbcModel::CbcIntegerTolerance); |
---|
| 137 | assert (upper[columnNumber_] > lower[columnNumber_]); |
---|
| 138 | #endif |
---|
| 139 | if (!model_->hotstartSolution()) { |
---|
| 140 | assert (fabs(value - nearest) > integerTolerance); |
---|
| 141 | } else { |
---|
| 142 | const double * hotstartSolution = model_->hotstartSolution(); |
---|
| 143 | double targetValue = hotstartSolution[columnNumber_]; |
---|
| 144 | if (way > 0) |
---|
| 145 | value = targetValue - 0.1; |
---|
| 146 | else |
---|
| 147 | value = targetValue + 0.1; |
---|
| 148 | } |
---|
| 149 | CbcIntegerPseudoCostBranchingObject * newObject = |
---|
| 150 | new CbcIntegerPseudoCostBranchingObject(model_, columnNumber_, way, |
---|
| 151 | value); |
---|
| 152 | double up = upPseudoCost_ * (ceil(value) - value); |
---|
| 153 | double down = downPseudoCost_ * (value - floor(value)); |
---|
| 154 | double changeInGuessed = up - down; |
---|
| 155 | if (way > 0) |
---|
| 156 | changeInGuessed = - changeInGuessed; |
---|
| 157 | changeInGuessed = CoinMax(0.0, changeInGuessed); |
---|
| 158 | //if (way>0) |
---|
| 159 | //changeInGuessed += 1.0e8; // bias to stay up |
---|
| 160 | newObject->setChangeInGuessed(changeInGuessed); |
---|
| 161 | newObject->setOriginalObject(this); |
---|
| 162 | return newObject; |
---|
| 163 | } |
---|
| 164 | double |
---|
| 165 | CbcSimpleIntegerPseudoCost::infeasibility(const OsiBranchingInformation * /*info*/, |
---|
| 166 | int &preferredWay) const |
---|
| 167 | { |
---|
| 168 | OsiSolverInterface * solver = model_->solver(); |
---|
| 169 | const double * solution = model_->testSolution(); |
---|
| 170 | const double * lower = solver->getColLower(); |
---|
| 171 | const double * upper = solver->getColUpper(); |
---|
| 172 | if (upper[columnNumber_] == lower[columnNumber_]) { |
---|
| 173 | // fixed |
---|
| 174 | preferredWay = 1; |
---|
| 175 | return 0.0; |
---|
| 176 | } |
---|
| 177 | double value = solution[columnNumber_]; |
---|
| 178 | value = CoinMax(value, lower[columnNumber_]); |
---|
| 179 | value = CoinMin(value, upper[columnNumber_]); |
---|
| 180 | /*printf("%d %g %g %g %g\n",columnNumber_,value,lower[columnNumber_], |
---|
| 181 | solution[columnNumber_],upper[columnNumber_]);*/ |
---|
| 182 | double nearest = floor(value + 0.5); |
---|
| 183 | double integerTolerance = |
---|
| 184 | model_->getDblParam(CbcModel::CbcIntegerTolerance); |
---|
| 185 | double below = floor(value + integerTolerance); |
---|
| 186 | double above = below + 1.0; |
---|
| 187 | if (above > upper[columnNumber_]) { |
---|
| 188 | above = below; |
---|
| 189 | below = above - 1; |
---|
| 190 | } |
---|
| 191 | double downCost = CoinMax((value - below) * downPseudoCost_, 0.0); |
---|
| 192 | double upCost = CoinMax((above - value) * upPseudoCost_, 0.0); |
---|
| 193 | if (downCost >= upCost) |
---|
| 194 | preferredWay = 1; |
---|
| 195 | else |
---|
| 196 | preferredWay = -1; |
---|
| 197 | // See if up down choice set |
---|
| 198 | if (upDownSeparator_ > 0.0) { |
---|
| 199 | preferredWay = (value - below >= upDownSeparator_) ? 1 : -1; |
---|
| 200 | } |
---|
| 201 | if (preferredWay_) |
---|
| 202 | preferredWay = preferredWay_; |
---|
| 203 | if (fabs(value - nearest) <= integerTolerance) { |
---|
| 204 | return 0.0; |
---|
| 205 | } else { |
---|
| 206 | // can't get at model so 1,2 don't make sense |
---|
| 207 | assert(method_ < 1 || method_ > 2); |
---|
| 208 | if (!method_) |
---|
| 209 | return CoinMin(downCost, upCost); |
---|
| 210 | else |
---|
| 211 | return CoinMax(downCost, upCost); |
---|
| 212 | } |
---|
| 213 | } |
---|
| 214 | |
---|
| 215 | // Return "up" estimate |
---|
| 216 | double |
---|
| 217 | CbcSimpleIntegerPseudoCost::upEstimate() const |
---|
| 218 | { |
---|
| 219 | OsiSolverInterface * solver = model_->solver(); |
---|
| 220 | const double * solution = model_->testSolution(); |
---|
| 221 | const double * lower = solver->getColLower(); |
---|
| 222 | const double * upper = solver->getColUpper(); |
---|
| 223 | double value = solution[columnNumber_]; |
---|
| 224 | value = CoinMax(value, lower[columnNumber_]); |
---|
| 225 | value = CoinMin(value, upper[columnNumber_]); |
---|
| 226 | if (upper[columnNumber_] == lower[columnNumber_]) { |
---|
| 227 | // fixed |
---|
| 228 | return 0.0; |
---|
| 229 | } |
---|
| 230 | double integerTolerance = |
---|
| 231 | model_->getDblParam(CbcModel::CbcIntegerTolerance); |
---|
| 232 | double below = floor(value + integerTolerance); |
---|
| 233 | double above = below + 1.0; |
---|
| 234 | if (above > upper[columnNumber_]) { |
---|
| 235 | above = below; |
---|
| 236 | below = above - 1; |
---|
| 237 | } |
---|
| 238 | double upCost = CoinMax((above - value) * upPseudoCost_, 0.0); |
---|
| 239 | return upCost; |
---|
| 240 | } |
---|
| 241 | // Return "down" estimate |
---|
| 242 | double |
---|
| 243 | CbcSimpleIntegerPseudoCost::downEstimate() const |
---|
| 244 | { |
---|
| 245 | OsiSolverInterface * solver = model_->solver(); |
---|
| 246 | const double * solution = model_->testSolution(); |
---|
| 247 | const double * lower = solver->getColLower(); |
---|
| 248 | const double * upper = solver->getColUpper(); |
---|
| 249 | double value = solution[columnNumber_]; |
---|
| 250 | value = CoinMax(value, lower[columnNumber_]); |
---|
| 251 | value = CoinMin(value, upper[columnNumber_]); |
---|
| 252 | if (upper[columnNumber_] == lower[columnNumber_]) { |
---|
| 253 | // fixed |
---|
| 254 | return 0.0; |
---|
| 255 | } |
---|
| 256 | double integerTolerance = |
---|
| 257 | model_->getDblParam(CbcModel::CbcIntegerTolerance); |
---|
| 258 | double below = floor(value + integerTolerance); |
---|
| 259 | double above = below + 1.0; |
---|
| 260 | if (above > upper[columnNumber_]) { |
---|
| 261 | above = below; |
---|
| 262 | below = above - 1; |
---|
| 263 | } |
---|
| 264 | double downCost = CoinMax((value - below) * downPseudoCost_, 0.0); |
---|
| 265 | return downCost; |
---|
| 266 | } |
---|
[1432] | 267 | |
---|