[1271] | 1 | /* $Id: CbcHeuristic.cpp 1730 2011-09-25 08:21:46Z forrest $ */ |
---|
[2] | 2 | // Copyright (C) 2002, International Business Machines |
---|
| 3 | // Corporation and others. All Rights Reserved. |
---|
[1573] | 4 | // This code is licensed under the terms of the Eclipse Public License (EPL). |
---|
| 5 | |
---|
[2] | 6 | #if defined(_MSC_VER) |
---|
| 7 | // Turn off compiler warning about long names |
---|
| 8 | # pragma warning(disable:4786) |
---|
| 9 | #endif |
---|
[311] | 10 | |
---|
[325] | 11 | #include "CbcConfig.h" |
---|
[311] | 12 | |
---|
[2] | 13 | #include <cassert> |
---|
[904] | 14 | #include <cstdlib> |
---|
[2] | 15 | #include <cmath> |
---|
| 16 | #include <cfloat> |
---|
| 17 | |
---|
[912] | 18 | //#define PRINT_DEBUG |
---|
[311] | 19 | #ifdef COIN_HAS_CLP |
---|
[197] | 20 | #include "OsiClpSolverInterface.hpp" |
---|
[246] | 21 | #endif |
---|
[2] | 22 | #include "CbcModel.hpp" |
---|
| 23 | #include "CbcMessage.hpp" |
---|
| 24 | #include "CbcHeuristic.hpp" |
---|
[833] | 25 | #include "CbcHeuristicFPump.hpp" |
---|
[197] | 26 | #include "CbcStrategy.hpp" |
---|
| 27 | #include "CglPreProcess.hpp" |
---|
[1499] | 28 | #include "CglGomory.hpp" |
---|
[1059] | 29 | #include "CglProbing.hpp" |
---|
[264] | 30 | #include "OsiAuxInfo.hpp" |
---|
[833] | 31 | #include "OsiPresolve.hpp" |
---|
[912] | 32 | #include "CbcBranchActual.hpp" |
---|
[940] | 33 | #include "CbcCutGenerator.hpp" |
---|
[912] | 34 | //============================================================================== |
---|
[2] | 35 | |
---|
[912] | 36 | CbcHeuristicNode::CbcHeuristicNode(const CbcHeuristicNode& rhs) |
---|
| 37 | { |
---|
[1286] | 38 | numObjects_ = rhs.numObjects_; |
---|
| 39 | brObj_ = new CbcBranchingObject*[numObjects_]; |
---|
| 40 | for (int i = 0; i < numObjects_; ++i) { |
---|
| 41 | brObj_[i] = rhs.brObj_[i]->clone(); |
---|
| 42 | } |
---|
[912] | 43 | } |
---|
| 44 | |
---|
| 45 | void |
---|
| 46 | CbcHeuristicNodeList::gutsOfDelete() |
---|
| 47 | { |
---|
[1507] | 48 | for (int i = (static_cast<int>(nodes_.size())) - 1; i >= 0; --i) { |
---|
[1286] | 49 | delete nodes_[i]; |
---|
| 50 | } |
---|
[912] | 51 | } |
---|
| 52 | |
---|
| 53 | void |
---|
| 54 | CbcHeuristicNodeList::gutsOfCopy(const CbcHeuristicNodeList& rhs) |
---|
| 55 | { |
---|
[1286] | 56 | append(rhs); |
---|
[912] | 57 | } |
---|
| 58 | |
---|
| 59 | CbcHeuristicNodeList::CbcHeuristicNodeList(const CbcHeuristicNodeList& rhs) |
---|
| 60 | { |
---|
[1286] | 61 | gutsOfCopy(rhs); |
---|
[912] | 62 | } |
---|
| 63 | |
---|
| 64 | CbcHeuristicNodeList& CbcHeuristicNodeList::operator= |
---|
[1286] | 65 | (const CbcHeuristicNodeList & rhs) |
---|
[912] | 66 | { |
---|
[1286] | 67 | if (this != &rhs) { |
---|
| 68 | gutsOfDelete(); |
---|
| 69 | gutsOfCopy(rhs); |
---|
| 70 | } |
---|
| 71 | return *this; |
---|
[912] | 72 | } |
---|
| 73 | |
---|
| 74 | CbcHeuristicNodeList::~CbcHeuristicNodeList() |
---|
| 75 | { |
---|
[1286] | 76 | gutsOfDelete(); |
---|
[912] | 77 | } |
---|
| 78 | |
---|
| 79 | void |
---|
| 80 | CbcHeuristicNodeList::append(CbcHeuristicNode*& node) |
---|
| 81 | { |
---|
[1286] | 82 | nodes_.push_back(node); |
---|
| 83 | node = NULL; |
---|
[912] | 84 | } |
---|
| 85 | |
---|
| 86 | void |
---|
| 87 | CbcHeuristicNodeList::append(const CbcHeuristicNodeList& nodes) |
---|
| 88 | { |
---|
[1286] | 89 | nodes_.reserve(nodes_.size() + nodes.size()); |
---|
| 90 | for (int i = 0; i < nodes.size(); ++i) { |
---|
| 91 | CbcHeuristicNode* node = new CbcHeuristicNode(*nodes.node(i)); |
---|
| 92 | append(node); |
---|
| 93 | } |
---|
[912] | 94 | } |
---|
| 95 | |
---|
| 96 | //============================================================================== |
---|
[1271] | 97 | #define DEFAULT_WHERE ((255-2-16)*(1+256)) |
---|
[2] | 98 | // Default Constructor |
---|
[912] | 99 | CbcHeuristic::CbcHeuristic() : |
---|
[1286] | 100 | model_(NULL), |
---|
| 101 | when_(2), |
---|
| 102 | numberNodes_(200), |
---|
| 103 | feasibilityPumpOptions_(-1), |
---|
| 104 | fractionSmall_(1.0), |
---|
| 105 | heuristicName_("Unknown"), |
---|
| 106 | howOften_(1), |
---|
| 107 | decayFactor_(0.0), |
---|
| 108 | switches_(0), |
---|
| 109 | whereFrom_(DEFAULT_WHERE), |
---|
| 110 | shallowDepth_(1), |
---|
| 111 | howOftenShallow_(1), |
---|
| 112 | numInvocationsInShallow_(0), |
---|
| 113 | numInvocationsInDeep_(0), |
---|
| 114 | lastRunDeep_(0), |
---|
| 115 | numRuns_(0), |
---|
| 116 | minDistanceToRun_(1), |
---|
| 117 | runNodes_(), |
---|
| 118 | numCouldRun_(0), |
---|
| 119 | numberSolutionsFound_(0), |
---|
| 120 | inputSolution_(NULL) |
---|
[2] | 121 | { |
---|
[1286] | 122 | // As CbcHeuristic virtual need to modify .cpp if above change |
---|
[2] | 123 | } |
---|
| 124 | |
---|
| 125 | // Constructor from model |
---|
[912] | 126 | CbcHeuristic::CbcHeuristic(CbcModel & model) : |
---|
[1286] | 127 | model_(&model), |
---|
| 128 | when_(2), |
---|
| 129 | numberNodes_(200), |
---|
| 130 | feasibilityPumpOptions_(-1), |
---|
| 131 | fractionSmall_(1.0), |
---|
| 132 | heuristicName_("Unknown"), |
---|
| 133 | howOften_(1), |
---|
| 134 | decayFactor_(0.0), |
---|
| 135 | switches_(0), |
---|
| 136 | whereFrom_(DEFAULT_WHERE), |
---|
| 137 | shallowDepth_(1), |
---|
| 138 | howOftenShallow_(1), |
---|
| 139 | numInvocationsInShallow_(0), |
---|
| 140 | numInvocationsInDeep_(0), |
---|
| 141 | lastRunDeep_(0), |
---|
| 142 | numRuns_(0), |
---|
| 143 | minDistanceToRun_(1), |
---|
| 144 | runNodes_(), |
---|
| 145 | numCouldRun_(0), |
---|
| 146 | numberSolutionsFound_(0), |
---|
| 147 | inputSolution_(NULL) |
---|
[912] | 148 | {} |
---|
| 149 | |
---|
| 150 | void |
---|
| 151 | CbcHeuristic::gutsOfCopy(const CbcHeuristic & rhs) |
---|
[2] | 152 | { |
---|
[1286] | 153 | model_ = rhs.model_; |
---|
| 154 | when_ = rhs.when_; |
---|
| 155 | numberNodes_ = rhs.numberNodes_; |
---|
| 156 | feasibilityPumpOptions_ = rhs.feasibilityPumpOptions_; |
---|
| 157 | fractionSmall_ = rhs.fractionSmall_; |
---|
| 158 | randomNumberGenerator_ = rhs.randomNumberGenerator_; |
---|
| 159 | heuristicName_ = rhs.heuristicName_; |
---|
| 160 | howOften_ = rhs.howOften_; |
---|
| 161 | decayFactor_ = rhs.decayFactor_; |
---|
| 162 | switches_ = rhs.switches_; |
---|
| 163 | whereFrom_ = rhs.whereFrom_; |
---|
| 164 | shallowDepth_ = rhs.shallowDepth_; |
---|
| 165 | howOftenShallow_ = rhs.howOftenShallow_; |
---|
| 166 | numInvocationsInShallow_ = rhs.numInvocationsInShallow_; |
---|
| 167 | numInvocationsInDeep_ = rhs.numInvocationsInDeep_; |
---|
| 168 | lastRunDeep_ = rhs.lastRunDeep_; |
---|
| 169 | numRuns_ = rhs.numRuns_; |
---|
| 170 | numCouldRun_ = rhs.numCouldRun_; |
---|
| 171 | minDistanceToRun_ = rhs.minDistanceToRun_; |
---|
| 172 | runNodes_ = rhs.runNodes_; |
---|
| 173 | numberSolutionsFound_ = rhs.numberSolutionsFound_; |
---|
| 174 | if (rhs.inputSolution_) { |
---|
| 175 | int numberColumns = model_->getNumCols(); |
---|
| 176 | setInputSolution(rhs.inputSolution_, rhs.inputSolution_[numberColumns]); |
---|
| 177 | } |
---|
[2] | 178 | } |
---|
[1286] | 179 | // Copy constructor |
---|
[640] | 180 | CbcHeuristic::CbcHeuristic(const CbcHeuristic & rhs) |
---|
| 181 | { |
---|
[1286] | 182 | inputSolution_ = NULL; |
---|
| 183 | gutsOfCopy(rhs); |
---|
[640] | 184 | } |
---|
[912] | 185 | |
---|
[1286] | 186 | // Assignment operator |
---|
| 187 | CbcHeuristic & |
---|
| 188 | CbcHeuristic::operator=( const CbcHeuristic & rhs) |
---|
[640] | 189 | { |
---|
[1286] | 190 | if (this != &rhs) { |
---|
| 191 | gutsOfDelete(); |
---|
| 192 | gutsOfCopy(rhs); |
---|
| 193 | } |
---|
| 194 | return *this; |
---|
[640] | 195 | } |
---|
| 196 | |
---|
[912] | 197 | void CbcHeurDebugNodes(CbcModel* model_) |
---|
| 198 | { |
---|
[1286] | 199 | CbcNode* node = model_->currentNode(); |
---|
| 200 | CbcNodeInfo* nodeInfo = node->nodeInfo(); |
---|
| 201 | std::cout << "===============================================================\n"; |
---|
| 202 | while (nodeInfo) { |
---|
| 203 | const CbcNode* node = nodeInfo->owner(); |
---|
| 204 | printf("nodeinfo: node %i\n", nodeInfo->nodeNumber()); |
---|
| 205 | { |
---|
| 206 | const CbcIntegerBranchingObject* brPrint = |
---|
| 207 | dynamic_cast<const CbcIntegerBranchingObject*>(nodeInfo->parentBranch()); |
---|
| 208 | if (!brPrint) { |
---|
| 209 | printf(" parentBranch: NULL\n"); |
---|
| 210 | } else { |
---|
| 211 | const double* downBounds = brPrint->downBounds(); |
---|
| 212 | const double* upBounds = brPrint->upBounds(); |
---|
| 213 | int variable = brPrint->variable(); |
---|
| 214 | int way = brPrint->way(); |
---|
| 215 | printf(" parentBranch: var %i downBd [%i,%i] upBd [%i,%i] way %i\n", |
---|
| 216 | variable, static_cast<int>(downBounds[0]), static_cast<int>(downBounds[1]), |
---|
| 217 | static_cast<int>(upBounds[0]), static_cast<int>(upBounds[1]), way); |
---|
| 218 | } |
---|
| 219 | } |
---|
| 220 | if (! node) { |
---|
| 221 | printf(" owner: NULL\n"); |
---|
| 222 | } else { |
---|
| 223 | printf(" owner: node %i depth %i onTree %i active %i", |
---|
| 224 | node->nodeNumber(), node->depth(), node->onTree(), node->active()); |
---|
| 225 | const OsiBranchingObject* osibr = |
---|
| 226 | nodeInfo->owner()->branchingObject(); |
---|
| 227 | const CbcBranchingObject* cbcbr = |
---|
| 228 | dynamic_cast<const CbcBranchingObject*>(osibr); |
---|
| 229 | const CbcIntegerBranchingObject* brPrint = |
---|
| 230 | dynamic_cast<const CbcIntegerBranchingObject*>(cbcbr); |
---|
| 231 | if (!brPrint) { |
---|
| 232 | printf(" ownerBranch: NULL\n"); |
---|
| 233 | } else { |
---|
| 234 | const double* downBounds = brPrint->downBounds(); |
---|
| 235 | const double* upBounds = brPrint->upBounds(); |
---|
| 236 | int variable = brPrint->variable(); |
---|
| 237 | int way = brPrint->way(); |
---|
| 238 | printf(" ownerbranch: var %i downBd [%i,%i] upBd [%i,%i] way %i\n", |
---|
| 239 | variable, static_cast<int>(downBounds[0]), static_cast<int>(downBounds[1]), |
---|
| 240 | static_cast<int>(upBounds[0]), static_cast<int>(upBounds[1]), way); |
---|
| 241 | } |
---|
| 242 | } |
---|
| 243 | nodeInfo = nodeInfo->parent(); |
---|
[912] | 244 | } |
---|
| 245 | } |
---|
| 246 | |
---|
| 247 | void |
---|
| 248 | CbcHeuristic::debugNodes() |
---|
| 249 | { |
---|
[1286] | 250 | CbcHeurDebugNodes(model_); |
---|
[912] | 251 | } |
---|
| 252 | |
---|
| 253 | void |
---|
| 254 | CbcHeuristic::printDistanceToNodes() |
---|
| 255 | { |
---|
[1286] | 256 | const CbcNode* currentNode = model_->currentNode(); |
---|
| 257 | if (currentNode != NULL) { |
---|
| 258 | CbcHeuristicNode* nodeDesc = new CbcHeuristicNode(*model_); |
---|
| 259 | for (int i = runNodes_.size() - 1; i >= 0; --i) { |
---|
| 260 | nodeDesc->distance(runNodes_.node(i)); |
---|
| 261 | } |
---|
| 262 | runNodes_.append(nodeDesc); |
---|
[912] | 263 | } |
---|
| 264 | } |
---|
| 265 | |
---|
| 266 | bool |
---|
[1271] | 267 | CbcHeuristic::shouldHeurRun(int whereFrom) |
---|
[912] | 268 | { |
---|
[1286] | 269 | assert (whereFrom >= 0 && whereFrom < 16); |
---|
| 270 | // take off 8 (code - likes new solution) |
---|
| 271 | whereFrom &= 7; |
---|
| 272 | if ((whereFrom_&(1 << whereFrom)) == 0) |
---|
| 273 | return false; |
---|
| 274 | // No longer used for original purpose - so use for ever run at all JJF |
---|
[1393] | 275 | #ifndef JJF_ONE |
---|
[1286] | 276 | // Don't run if hot start |
---|
| 277 | if (model_ && model_->hotstartSolution()) |
---|
| 278 | return false; |
---|
| 279 | else |
---|
| 280 | return true; |
---|
[1013] | 281 | #else |
---|
[1393] | 282 | #ifdef JJF_ZERO |
---|
[1286] | 283 | const CbcNode* currentNode = model_->currentNode(); |
---|
| 284 | if (currentNode == NULL) { |
---|
| 285 | return false; |
---|
| 286 | } |
---|
[912] | 287 | |
---|
[1286] | 288 | debugNodes(); |
---|
[912] | 289 | // return false; |
---|
| 290 | |
---|
[1286] | 291 | const int depth = currentNode->depth(); |
---|
[912] | 292 | #else |
---|
[1286] | 293 | int depth = model_->currentDepth(); |
---|
[912] | 294 | #endif |
---|
| 295 | |
---|
[1286] | 296 | const int nodeCount = model_->getNodeCount(); // FIXME: check that this is |
---|
| 297 | // correct in parallel |
---|
[912] | 298 | |
---|
[1286] | 299 | if (nodeCount == 0 || depth <= shallowDepth_) { |
---|
| 300 | // what to do when we are in the shallow part of the tree |
---|
| 301 | if (model_->getCurrentPassNumber() == 1) { |
---|
| 302 | // first time in the node... |
---|
| 303 | numInvocationsInShallow_ = 0; |
---|
| 304 | } |
---|
| 305 | ++numInvocationsInShallow_; |
---|
| 306 | // Very large howOftenShallow_ will give the original test: |
---|
| 307 | // (model_->getCurrentPassNumber() != 1) |
---|
| 308 | // if ((numInvocationsInShallow_ % howOftenShallow_) != 1) { |
---|
| 309 | if ((numInvocationsInShallow_ % howOftenShallow_) != 0) { |
---|
| 310 | return false; |
---|
| 311 | } |
---|
| 312 | // LL: should we save these nodes in the list of nodes where the heur was |
---|
| 313 | // LL: run? |
---|
[1393] | 314 | #ifndef JJF_ONE |
---|
[1286] | 315 | if (currentNode != NULL) { |
---|
| 316 | // Get where we are and create the appropriate CbcHeuristicNode object |
---|
| 317 | CbcHeuristicNode* nodeDesc = new CbcHeuristicNode(*model_); |
---|
| 318 | runNodes_.append(nodeDesc); |
---|
| 319 | } |
---|
[912] | 320 | #endif |
---|
[1286] | 321 | } else { |
---|
| 322 | // deeper in the tree |
---|
| 323 | if (model_->getCurrentPassNumber() == 1) { |
---|
| 324 | // first time in the node... |
---|
| 325 | ++numInvocationsInDeep_; |
---|
| 326 | } |
---|
| 327 | if (numInvocationsInDeep_ - lastRunDeep_ < howOften_) { |
---|
| 328 | return false; |
---|
| 329 | } |
---|
| 330 | if (model_->getCurrentPassNumber() != 1) { |
---|
| 331 | // Run the heuristic only when first entering the node. |
---|
| 332 | // LL: I don't think this is right. It should run just before strong |
---|
| 333 | // LL: branching, I believe. |
---|
| 334 | return false; |
---|
| 335 | } |
---|
| 336 | // Get where we are and create the appropriate CbcHeuristicNode object |
---|
| 337 | CbcHeuristicNode* nodeDesc = new CbcHeuristicNode(*model_); |
---|
| 338 | //#ifdef PRINT_DEBUG |
---|
[1393] | 339 | #ifndef JJF_ONE |
---|
[1286] | 340 | const double minDistanceToRun = 1.5 * log((double)depth) / log((double)2); |
---|
[915] | 341 | #else |
---|
| 342 | const double minDistanceToRun = minDistanceToRun_; |
---|
| 343 | #endif |
---|
| 344 | #ifdef PRINT_DEBUG |
---|
[1286] | 345 | double minDistance = nodeDesc->minDistance(runNodes_); |
---|
| 346 | std::cout << "minDistance = " << minDistance |
---|
| 347 | << ", minDistanceToRun = " << minDistanceToRun << std::endl; |
---|
[912] | 348 | #endif |
---|
[1286] | 349 | if (nodeDesc->minDistanceIsSmall(runNodes_, minDistanceToRun)) { |
---|
| 350 | delete nodeDesc; |
---|
| 351 | return false; |
---|
| 352 | } |
---|
| 353 | runNodes_.append(nodeDesc); |
---|
| 354 | lastRunDeep_ = numInvocationsInDeep_; |
---|
| 355 | // ++lastRunDeep_; |
---|
[912] | 356 | } |
---|
[1286] | 357 | ++numRuns_; |
---|
| 358 | return true; |
---|
[1013] | 359 | #endif |
---|
[912] | 360 | } |
---|
| 361 | |
---|
| 362 | bool |
---|
| 363 | CbcHeuristic::shouldHeurRun_randomChoice() |
---|
| 364 | { |
---|
[1286] | 365 | if (!when_) |
---|
| 366 | return false; |
---|
| 367 | int depth = model_->currentDepth(); |
---|
| 368 | // when_ -999 is special marker to force to run |
---|
| 369 | if (depth != 0 && when_ != -999) { |
---|
| 370 | const double numerator = depth * depth; |
---|
| 371 | const double denominator = exp(depth * log(2.0)); |
---|
| 372 | double probability = numerator / denominator; |
---|
| 373 | double randomNumber = randomNumberGenerator_.randomDouble(); |
---|
| 374 | int when = when_ % 100; |
---|
| 375 | if (when > 2 && when < 8) { |
---|
| 376 | /* JJF adjustments |
---|
| 377 | 3 only at root and if no solution |
---|
| 378 | 4 only at root and if this heuristic has not got solution |
---|
[1315] | 379 | 5 as 3 but decay more |
---|
[1286] | 380 | 6 decay |
---|
| 381 | 7 run up to 2 times if solution found 4 otherwise |
---|
| 382 | */ |
---|
| 383 | switch (when) { |
---|
| 384 | case 3: |
---|
| 385 | default: |
---|
| 386 | if (model_->bestSolution()) |
---|
| 387 | probability = -1.0; |
---|
| 388 | break; |
---|
| 389 | case 4: |
---|
| 390 | if (numberSolutionsFound_) |
---|
| 391 | probability = -1.0; |
---|
| 392 | break; |
---|
| 393 | case 5: |
---|
[1315] | 394 | assert (decayFactor_); |
---|
| 395 | if (model_->bestSolution()) { |
---|
[1286] | 396 | probability = -1.0; |
---|
[1315] | 397 | } else if (numCouldRun_ > 1000) { |
---|
| 398 | decayFactor_ *= 0.99; |
---|
| 399 | probability *= decayFactor_; |
---|
| 400 | } |
---|
[1286] | 401 | break; |
---|
| 402 | case 6: |
---|
| 403 | if (depth >= 3) { |
---|
| 404 | if ((numCouldRun_ % howOften_) == 0 && |
---|
| 405 | numberSolutionsFound_*howOften_ < numCouldRun_) { |
---|
[1013] | 406 | #ifdef COIN_DEVELOP |
---|
[1286] | 407 | int old = howOften_; |
---|
[1013] | 408 | #endif |
---|
[1315] | 409 | howOften_ = CoinMin(CoinMax(static_cast<int> (howOften_ * 1.1), howOften_ + 1), 1000000); |
---|
[961] | 410 | #ifdef COIN_DEVELOP |
---|
[1286] | 411 | printf("Howoften changed from %d to %d for %s\n", |
---|
| 412 | old, howOften_, heuristicName_.c_str()); |
---|
[961] | 413 | #endif |
---|
[1286] | 414 | } |
---|
| 415 | probability = 1.0 / howOften_; |
---|
| 416 | if (model_->bestSolution()) |
---|
| 417 | probability *= 0.5; |
---|
| 418 | } |
---|
| 419 | break; |
---|
| 420 | case 7: |
---|
| 421 | if ((model_->bestSolution() && numRuns_ >= 2) || numRuns_ >= 4) |
---|
| 422 | probability = -1.0; |
---|
| 423 | break; |
---|
| 424 | } |
---|
| 425 | } |
---|
| 426 | if (randomNumber > probability) |
---|
| 427 | return false; |
---|
| 428 | |
---|
| 429 | if (model_->getCurrentPassNumber() > 1) |
---|
| 430 | return false; |
---|
[961] | 431 | #ifdef COIN_DEVELOP |
---|
[1286] | 432 | printf("Running %s, random %g probability %g\n", |
---|
| 433 | heuristicName_.c_str(), randomNumber, probability); |
---|
[961] | 434 | #endif |
---|
[1286] | 435 | } else { |
---|
[961] | 436 | #ifdef COIN_DEVELOP |
---|
[1286] | 437 | printf("Running %s, depth %d when %d\n", |
---|
| 438 | heuristicName_.c_str(), depth, when_); |
---|
[961] | 439 | #endif |
---|
[1286] | 440 | } |
---|
| 441 | ++numRuns_; |
---|
| 442 | return true; |
---|
[912] | 443 | } |
---|
| 444 | |
---|
[6] | 445 | // Resets stuff if model changes |
---|
[1286] | 446 | void |
---|
[6] | 447 | CbcHeuristic::resetModel(CbcModel * model) |
---|
| 448 | { |
---|
[1286] | 449 | model_ = model; |
---|
| 450 | } |
---|
[838] | 451 | // Set seed |
---|
| 452 | void |
---|
| 453 | CbcHeuristic::setSeed(int value) |
---|
| 454 | { |
---|
[1286] | 455 | randomNumberGenerator_.setSeed(value); |
---|
[838] | 456 | } |
---|
[2] | 457 | |
---|
[640] | 458 | // Create C++ lines to get to current state |
---|
[1286] | 459 | void |
---|
| 460 | CbcHeuristic::generateCpp( FILE * fp, const char * heuristic) |
---|
[640] | 461 | { |
---|
[1286] | 462 | // hard coded as CbcHeuristic virtual |
---|
| 463 | if (when_ != 2) |
---|
| 464 | fprintf(fp, "3 %s.setWhen(%d);\n", heuristic, when_); |
---|
| 465 | else |
---|
| 466 | fprintf(fp, "4 %s.setWhen(%d);\n", heuristic, when_); |
---|
| 467 | if (numberNodes_ != 200) |
---|
| 468 | fprintf(fp, "3 %s.setNumberNodes(%d);\n", heuristic, numberNodes_); |
---|
| 469 | else |
---|
| 470 | fprintf(fp, "4 %s.setNumberNodes(%d);\n", heuristic, numberNodes_); |
---|
| 471 | if (feasibilityPumpOptions_ != -1) |
---|
| 472 | fprintf(fp, "3 %s.setFeasibilityPumpOptions(%d);\n", heuristic, feasibilityPumpOptions_); |
---|
| 473 | else |
---|
| 474 | fprintf(fp, "4 %s.setFeasibilityPumpOptions(%d);\n", heuristic, feasibilityPumpOptions_); |
---|
| 475 | if (fractionSmall_ != 1.0) |
---|
| 476 | fprintf(fp, "3 %s.setFractionSmall(%g);\n", heuristic, fractionSmall_); |
---|
| 477 | else |
---|
| 478 | fprintf(fp, "4 %s.setFractionSmall(%g);\n", heuristic, fractionSmall_); |
---|
| 479 | if (heuristicName_ != "Unknown") |
---|
| 480 | fprintf(fp, "3 %s.setHeuristicName(\"%s\");\n", |
---|
| 481 | heuristic, heuristicName_.c_str()) ; |
---|
| 482 | else |
---|
| 483 | fprintf(fp, "4 %s.setHeuristicName(\"%s\");\n", |
---|
| 484 | heuristic, heuristicName_.c_str()) ; |
---|
| 485 | if (decayFactor_ != 0.0) |
---|
| 486 | fprintf(fp, "3 %s.setDecayFactor(%g);\n", heuristic, decayFactor_); |
---|
| 487 | else |
---|
| 488 | fprintf(fp, "4 %s.setDecayFactor(%g);\n", heuristic, decayFactor_); |
---|
| 489 | if (switches_ != 0) |
---|
| 490 | fprintf(fp, "3 %s.setSwitches(%d);\n", heuristic, switches_); |
---|
| 491 | else |
---|
| 492 | fprintf(fp, "4 %s.setSwitches(%d);\n", heuristic, switches_); |
---|
| 493 | if (whereFrom_ != DEFAULT_WHERE) |
---|
| 494 | fprintf(fp, "3 %s.setWhereFrom(%d);\n", heuristic, whereFrom_); |
---|
| 495 | else |
---|
| 496 | fprintf(fp, "4 %s.setWhereFrom(%d);\n", heuristic, whereFrom_); |
---|
| 497 | if (shallowDepth_ != 1) |
---|
| 498 | fprintf(fp, "3 %s.setShallowDepth(%d);\n", heuristic, shallowDepth_); |
---|
| 499 | else |
---|
| 500 | fprintf(fp, "4 %s.setShallowDepth(%d);\n", heuristic, shallowDepth_); |
---|
| 501 | if (howOftenShallow_ != 1) |
---|
| 502 | fprintf(fp, "3 %s.setHowOftenShallow(%d);\n", heuristic, howOftenShallow_); |
---|
| 503 | else |
---|
| 504 | fprintf(fp, "4 %s.setHowOftenShallow(%d);\n", heuristic, howOftenShallow_); |
---|
| 505 | if (minDistanceToRun_ != 1) |
---|
| 506 | fprintf(fp, "3 %s.setMinDistanceToRun(%d);\n", heuristic, minDistanceToRun_); |
---|
| 507 | else |
---|
| 508 | fprintf(fp, "4 %s.setMinDistanceToRun(%d);\n", heuristic, minDistanceToRun_); |
---|
[640] | 509 | } |
---|
[1286] | 510 | // Destructor |
---|
[2] | 511 | CbcHeuristic::~CbcHeuristic () |
---|
| 512 | { |
---|
[1286] | 513 | delete [] inputSolution_; |
---|
[2] | 514 | } |
---|
| 515 | |
---|
| 516 | // update model |
---|
| 517 | void CbcHeuristic::setModel(CbcModel * model) |
---|
| 518 | { |
---|
[1286] | 519 | model_ = model; |
---|
[2] | 520 | } |
---|
[1271] | 521 | /* Clone but .. |
---|
| 522 | type 0 clone solver, 1 clone continuous solver |
---|
| 523 | Add 2 to say without integer variables which are at low priority |
---|
| 524 | Add 4 to say quite likely infeasible so give up easily.*/ |
---|
[1286] | 525 | OsiSolverInterface * |
---|
[1271] | 526 | CbcHeuristic::cloneBut(int type) |
---|
| 527 | { |
---|
[1286] | 528 | OsiSolverInterface * solver; |
---|
| 529 | if ((type&1) == 0 || !model_->continuousSolver()) |
---|
| 530 | solver = model_->solver()->clone(); |
---|
| 531 | else |
---|
| 532 | solver = model_->continuousSolver()->clone(); |
---|
[1271] | 533 | #ifdef COIN_HAS_CLP |
---|
[1286] | 534 | OsiClpSolverInterface * clpSolver |
---|
[1271] | 535 | = dynamic_cast<OsiClpSolverInterface *> (solver); |
---|
| 536 | #endif |
---|
[1286] | 537 | if ((type&2) != 0) { |
---|
| 538 | int n = model_->numberObjects(); |
---|
| 539 | int priority = model_->continuousPriority(); |
---|
| 540 | if (priority < COIN_INT_MAX) { |
---|
| 541 | for (int i = 0; i < n; i++) { |
---|
| 542 | const OsiObject * obj = model_->object(i); |
---|
| 543 | const CbcSimpleInteger * thisOne = |
---|
| 544 | dynamic_cast <const CbcSimpleInteger *> (obj); |
---|
| 545 | if (thisOne) { |
---|
| 546 | int iColumn = thisOne->columnNumber(); |
---|
| 547 | if (thisOne->priority() >= priority) |
---|
| 548 | solver->setContinuous(iColumn); |
---|
| 549 | } |
---|
| 550 | } |
---|
| 551 | } |
---|
| 552 | #ifdef COIN_HAS_CLP |
---|
| 553 | if (clpSolver) { |
---|
| 554 | for (int i = 0; i < n; i++) { |
---|
| 555 | const OsiObject * obj = model_->object(i); |
---|
| 556 | const CbcSimpleInteger * thisOne = |
---|
| 557 | dynamic_cast <const CbcSimpleInteger *> (obj); |
---|
| 558 | if (thisOne) { |
---|
| 559 | int iColumn = thisOne->columnNumber(); |
---|
| 560 | if (clpSolver->isOptionalInteger(iColumn)) |
---|
| 561 | clpSolver->setContinuous(iColumn); |
---|
| 562 | } |
---|
| 563 | } |
---|
| 564 | } |
---|
| 565 | #endif |
---|
[1271] | 566 | } |
---|
| 567 | #ifdef COIN_HAS_CLP |
---|
[1286] | 568 | if ((type&4) != 0 && clpSolver) { |
---|
| 569 | int options = clpSolver->getModelPtr()->moreSpecialOptions(); |
---|
| 570 | clpSolver->getModelPtr()->setMoreSpecialOptions(options | 64); |
---|
[1271] | 571 | } |
---|
| 572 | #endif |
---|
[1286] | 573 | return solver; |
---|
[1271] | 574 | } |
---|
[1121] | 575 | // Whether to exit at once on gap |
---|
[1286] | 576 | bool |
---|
[1121] | 577 | CbcHeuristic::exitNow(double bestObjective) const |
---|
| 578 | { |
---|
[1286] | 579 | if ((switches_&2048) != 0) { |
---|
| 580 | // exit may be forced - but unset for next time |
---|
| 581 | switches_ &= ~2048; |
---|
| 582 | if ((switches_&1024) != 0) |
---|
| 583 | return true; |
---|
| 584 | } else if ((switches_&1) == 0) { |
---|
| 585 | return false; |
---|
| 586 | } |
---|
| 587 | // See if can stop on gap |
---|
| 588 | OsiSolverInterface * solver = model_->solver(); |
---|
| 589 | double bestPossibleObjective = solver->getObjValue() * solver->getObjSense(); |
---|
| 590 | double absGap = CoinMax(model_->getAllowableGap(), |
---|
| 591 | model_->getHeuristicGap()); |
---|
| 592 | double fracGap = CoinMax(model_->getAllowableFractionGap(), |
---|
| 593 | model_->getHeuristicFractionGap()); |
---|
| 594 | double testGap = CoinMax(absGap, fracGap * |
---|
| 595 | CoinMax(fabs(bestObjective), |
---|
| 596 | fabs(bestPossibleObjective))); |
---|
[1271] | 597 | |
---|
[1286] | 598 | if (bestObjective - bestPossibleObjective < testGap |
---|
| 599 | && model_->getCutoffIncrement() >= 0.0) { |
---|
| 600 | return true; |
---|
| 601 | } else { |
---|
| 602 | return false; |
---|
| 603 | } |
---|
[1121] | 604 | } |
---|
[1013] | 605 | #ifdef HISTORY_STATISTICS |
---|
[833] | 606 | extern bool getHistoryStatistics_; |
---|
| 607 | #endif |
---|
[1286] | 608 | static double sizeRatio(int numberRowsNow, int numberColumnsNow, |
---|
| 609 | int numberRowsStart, int numberColumnsStart) |
---|
[1132] | 610 | { |
---|
[1286] | 611 | double valueNow; |
---|
| 612 | if (numberRowsNow*10 > numberColumnsNow || numberColumnsNow < 200) { |
---|
| 613 | valueNow = 2 * numberRowsNow + numberColumnsNow; |
---|
| 614 | } else { |
---|
| 615 | // long and thin - rows are more important |
---|
| 616 | if (numberRowsNow*40 > numberColumnsNow) |
---|
| 617 | valueNow = 10 * numberRowsNow + numberColumnsNow; |
---|
| 618 | else |
---|
| 619 | valueNow = 200 * numberRowsNow + numberColumnsNow; |
---|
| 620 | } |
---|
| 621 | double valueStart; |
---|
| 622 | if (numberRowsStart*10 > numberColumnsStart || numberColumnsStart < 200) { |
---|
| 623 | valueStart = 2 * numberRowsStart + numberColumnsStart; |
---|
| 624 | } else { |
---|
| 625 | // long and thin - rows are more important |
---|
| 626 | if (numberRowsStart*40 > numberColumnsStart) |
---|
| 627 | valueStart = 10 * numberRowsStart + numberColumnsStart; |
---|
| 628 | else |
---|
| 629 | valueStart = 200 * numberRowsStart + numberColumnsStart; |
---|
| 630 | } |
---|
| 631 | //printf("sizeProblem Now %g, %d rows, %d columns\nsizeProblem Start %g, %d rows, %d columns\n", |
---|
| 632 | // valueNow,numberRowsNow,numberColumnsNow, |
---|
| 633 | // valueStart,numberRowsStart,numberColumnsStart); |
---|
| 634 | if (10*numberRowsNow < 8*numberRowsStart) |
---|
| 635 | return valueNow / valueStart; |
---|
| 636 | else if (10*numberRowsNow < 9*numberRowsStart) |
---|
| 637 | return 1.1*(valueNow / valueStart); |
---|
| 638 | else if (numberRowsNow < numberRowsStart) |
---|
| 639 | return 1.5*(valueNow / valueStart); |
---|
[1132] | 640 | else |
---|
[1286] | 641 | return 2.0*(valueNow / valueStart); |
---|
[1132] | 642 | } |
---|
| 643 | |
---|
[1286] | 644 | |
---|
[197] | 645 | // Do mini branch and bound (return 1 if solution) |
---|
[1286] | 646 | int |
---|
| 647 | CbcHeuristic::smallBranchAndBound(OsiSolverInterface * solver, int numberNodes, |
---|
[197] | 648 | double * newSolution, double & newSolutionValue, |
---|
| 649 | double cutoff, std::string name) const |
---|
| 650 | { |
---|
[1286] | 651 | // size before |
---|
| 652 | int shiftRows = 0; |
---|
| 653 | if (numberNodes < 0) |
---|
| 654 | shiftRows = solver->getNumRows() - numberNodes_; |
---|
| 655 | int numberRowsStart = solver->getNumRows() - shiftRows; |
---|
| 656 | int numberColumnsStart = solver->getNumCols(); |
---|
[1020] | 657 | #ifdef CLP_INVESTIGATE |
---|
[1286] | 658 | printf("%s has %d rows, %d columns\n", |
---|
| 659 | name.c_str(), solver->getNumRows(), solver->getNumCols()); |
---|
[1020] | 660 | #endif |
---|
[1286] | 661 | // Use this fraction |
---|
| 662 | double fractionSmall = fractionSmall_; |
---|
| 663 | double before = 2 * numberRowsStart + numberColumnsStart; |
---|
| 664 | if (before > 40000.0) { |
---|
| 665 | // fairly large - be more conservative |
---|
| 666 | double multiplier = 1.0 - 0.3 * CoinMin(100000.0, before - 40000.0) / 100000.0; |
---|
| 667 | if (multiplier < 1.0) { |
---|
| 668 | fractionSmall *= multiplier; |
---|
[1020] | 669 | #ifdef CLP_INVESTIGATE |
---|
[1286] | 670 | printf("changing fractionSmall from %g to %g for %s\n", |
---|
| 671 | fractionSmall_, fractionSmall, name.c_str()); |
---|
[931] | 672 | #endif |
---|
[1286] | 673 | } |
---|
[1020] | 674 | } |
---|
[311] | 675 | #ifdef COIN_HAS_CLP |
---|
[1286] | 676 | OsiClpSolverInterface * osiclp = dynamic_cast< OsiClpSolverInterface*> (solver); |
---|
| 677 | if (osiclp && (osiclp->specialOptions()&65536) == 0) { |
---|
| 678 | // go faster stripes |
---|
| 679 | if (osiclp->getNumRows() < 300 && osiclp->getNumCols() < 500) { |
---|
| 680 | osiclp->setupForRepeatedUse(2, 0); |
---|
| 681 | } else { |
---|
| 682 | osiclp->setupForRepeatedUse(0, 0); |
---|
| 683 | } |
---|
| 684 | // Turn this off if you get problems |
---|
| 685 | // Used to be automatically set |
---|
| 686 | osiclp->setSpecialOptions(osiclp->specialOptions() | (128 + 64 - 128)); |
---|
| 687 | ClpSimplex * lpSolver = osiclp->getModelPtr(); |
---|
| 688 | lpSolver->setSpecialOptions(lpSolver->specialOptions() | 0x01000000); // say is Cbc (and in branch and bound) |
---|
| 689 | lpSolver->setSpecialOptions(lpSolver->specialOptions() | |
---|
| 690 | (/*16384+*/4096 + 512 + 128)); |
---|
[197] | 691 | } |
---|
[246] | 692 | #endif |
---|
[1013] | 693 | #ifdef HISTORY_STATISTICS |
---|
[1286] | 694 | getHistoryStatistics_ = false; |
---|
[833] | 695 | #endif |
---|
[1286] | 696 | int status = 0; |
---|
| 697 | int logLevel = model_->logLevel(); |
---|
[863] | 698 | #define LEN_PRINT 250 |
---|
[1286] | 699 | char generalPrint[LEN_PRINT]; |
---|
| 700 | // Do presolve to see if possible |
---|
| 701 | int numberColumns = solver->getNumCols(); |
---|
| 702 | char * reset = NULL; |
---|
| 703 | int returnCode = 1; |
---|
| 704 | int saveModelOptions = model_->specialOptions(); |
---|
[1582] | 705 | //assert ((saveModelOptions&2048) == 0); |
---|
[1286] | 706 | model_->setSpecialOptions(saveModelOptions | 2048); |
---|
| 707 | { |
---|
| 708 | int saveLogLevel = solver->messageHandler()->logLevel(); |
---|
| 709 | if (saveLogLevel == 1) |
---|
| 710 | solver->messageHandler()->setLogLevel(0); |
---|
| 711 | OsiPresolve * pinfo = new OsiPresolve(); |
---|
| 712 | int presolveActions = 0; |
---|
| 713 | // Allow dual stuff on integers |
---|
| 714 | presolveActions = 1; |
---|
| 715 | // Do not allow all +1 to be tampered with |
---|
| 716 | //if (allPlusOnes) |
---|
| 717 | //presolveActions |= 2; |
---|
| 718 | // allow transfer of costs |
---|
| 719 | // presolveActions |= 4; |
---|
| 720 | pinfo->setPresolveActions(presolveActions); |
---|
| 721 | OsiSolverInterface * presolvedModel = pinfo->presolvedModel(*solver, 1.0e-8, true, 2); |
---|
| 722 | delete pinfo; |
---|
| 723 | // see if too big |
---|
| 724 | |
---|
| 725 | if (presolvedModel) { |
---|
| 726 | int afterRows = presolvedModel->getNumRows(); |
---|
| 727 | int afterCols = presolvedModel->getNumCols(); |
---|
| 728 | //#define COIN_DEVELOP |
---|
[1121] | 729 | #ifdef COIN_DEVELOP_z |
---|
[1286] | 730 | if (numberNodes < 0) { |
---|
| 731 | solver->writeMpsNative("before.mps", NULL, NULL, 2, 1); |
---|
| 732 | presolvedModel->writeMpsNative("after1.mps", NULL, NULL, 2, 1); |
---|
| 733 | } |
---|
[1121] | 734 | #endif |
---|
[1286] | 735 | delete presolvedModel; |
---|
| 736 | double ratio = sizeRatio(afterRows - shiftRows, afterCols, |
---|
| 737 | numberRowsStart, numberColumnsStart); |
---|
| 738 | double after = 2 * afterRows + afterCols; |
---|
| 739 | if (ratio > fractionSmall && after > 300 && numberNodes >= 0) { |
---|
| 740 | // Need code to try again to compress further using used |
---|
| 741 | const int * used = model_->usedInSolution(); |
---|
| 742 | int maxUsed = 0; |
---|
| 743 | int iColumn; |
---|
| 744 | const double * lower = solver->getColLower(); |
---|
| 745 | const double * upper = solver->getColUpper(); |
---|
| 746 | for (iColumn = 0; iColumn < numberColumns; iColumn++) { |
---|
| 747 | if (upper[iColumn] > lower[iColumn]) { |
---|
| 748 | if (solver->isBinary(iColumn)) |
---|
| 749 | maxUsed = CoinMax(maxUsed, used[iColumn]); |
---|
| 750 | } |
---|
| 751 | } |
---|
| 752 | if (maxUsed) { |
---|
| 753 | reset = new char [numberColumns]; |
---|
| 754 | int nFix = 0; |
---|
| 755 | for (iColumn = 0; iColumn < numberColumns; iColumn++) { |
---|
| 756 | reset[iColumn] = 0; |
---|
| 757 | if (upper[iColumn] > lower[iColumn]) { |
---|
| 758 | if (solver->isBinary(iColumn) && used[iColumn] == maxUsed) { |
---|
| 759 | bool setValue = true; |
---|
| 760 | if (maxUsed == 1) { |
---|
| 761 | double randomNumber = randomNumberGenerator_.randomDouble(); |
---|
| 762 | if (randomNumber > 0.3) |
---|
| 763 | setValue = false; |
---|
| 764 | } |
---|
| 765 | if (setValue) { |
---|
| 766 | reset[iColumn] = 1; |
---|
| 767 | solver->setColLower(iColumn, 1.0); |
---|
| 768 | nFix++; |
---|
| 769 | } |
---|
| 770 | } |
---|
| 771 | } |
---|
| 772 | } |
---|
| 773 | pinfo = new OsiPresolve(); |
---|
| 774 | presolveActions = 0; |
---|
| 775 | // Allow dual stuff on integers |
---|
| 776 | presolveActions = 1; |
---|
| 777 | // Do not allow all +1 to be tampered with |
---|
| 778 | //if (allPlusOnes) |
---|
| 779 | //presolveActions |= 2; |
---|
| 780 | // allow transfer of costs |
---|
| 781 | // presolveActions |= 4; |
---|
| 782 | pinfo->setPresolveActions(presolveActions); |
---|
| 783 | presolvedModel = pinfo->presolvedModel(*solver, 1.0e-8, true, 2); |
---|
| 784 | delete pinfo; |
---|
| 785 | if (presolvedModel) { |
---|
| 786 | // see if too big |
---|
| 787 | int afterRows2 = presolvedModel->getNumRows(); |
---|
| 788 | int afterCols2 = presolvedModel->getNumCols(); |
---|
| 789 | delete presolvedModel; |
---|
| 790 | double ratio = sizeRatio(afterRows2 - shiftRows, afterCols2, |
---|
| 791 | numberRowsStart, numberColumnsStart); |
---|
| 792 | double after = 2 * afterRows2 + afterCols2; |
---|
| 793 | if (ratio > fractionSmall && (after > 300 || numberNodes < 0)) { |
---|
| 794 | sprintf(generalPrint, "Full problem %d rows %d columns, reduced to %d rows %d columns - %d fixed gives %d, %d - still too large", |
---|
| 795 | solver->getNumRows(), solver->getNumCols(), |
---|
| 796 | afterRows, afterCols, nFix, afterRows2, afterCols2); |
---|
| 797 | // If much too big - give up |
---|
| 798 | if (ratio > 0.75) |
---|
| 799 | returnCode = -1; |
---|
| 800 | } else { |
---|
| 801 | sprintf(generalPrint, "Full problem %d rows %d columns, reduced to %d rows %d columns - %d fixed gives %d, %d - ok now", |
---|
| 802 | solver->getNumRows(), solver->getNumCols(), |
---|
| 803 | afterRows, afterCols, nFix, afterRows2, afterCols2); |
---|
| 804 | } |
---|
[1730] | 805 | model_->messageHandler()->message(CBC_FPUMP1, model_->messages()) |
---|
[1286] | 806 | << generalPrint |
---|
| 807 | << CoinMessageEol; |
---|
| 808 | } else { |
---|
| 809 | returnCode = 2; // infeasible |
---|
| 810 | } |
---|
| 811 | } |
---|
| 812 | } else if (ratio > fractionSmall && after > 300) { |
---|
| 813 | returnCode = -1; |
---|
| 814 | } |
---|
| 815 | } else { |
---|
| 816 | returnCode = 2; // infeasible |
---|
| 817 | } |
---|
| 818 | solver->messageHandler()->setLogLevel(saveLogLevel); |
---|
[833] | 819 | } |
---|
[1286] | 820 | if (returnCode == 2 || returnCode == -1) { |
---|
| 821 | model_->setSpecialOptions(saveModelOptions); |
---|
| 822 | delete [] reset; |
---|
[1013] | 823 | #ifdef HISTORY_STATISTICS |
---|
[1286] | 824 | getHistoryStatistics_ = true; |
---|
[833] | 825 | #endif |
---|
[1286] | 826 | //printf("small no good\n"); |
---|
| 827 | return returnCode; |
---|
[961] | 828 | } |
---|
[1286] | 829 | // Reduce printout |
---|
| 830 | bool takeHint; |
---|
| 831 | OsiHintStrength strength; |
---|
| 832 | solver->getHintParam(OsiDoReducePrint, takeHint, strength); |
---|
| 833 | solver->setHintParam(OsiDoReducePrint, true, OsiHintTry); |
---|
| 834 | solver->setHintParam(OsiDoPresolveInInitial, false, OsiHintTry); |
---|
[1499] | 835 | double signedCutoff = cutoff*solver->getObjSense(); |
---|
| 836 | solver->setDblParam(OsiDualObjectiveLimit, signedCutoff); |
---|
[1286] | 837 | solver->initialSolve(); |
---|
| 838 | if (solver->isProvenOptimal()) { |
---|
| 839 | CglPreProcess process; |
---|
[1585] | 840 | if ((model_->moreSpecialOptions()&65536)!=0) |
---|
| 841 | process.setOptions(2+4+8); // no cuts |
---|
[1286] | 842 | /* Do not try and produce equality cliques and |
---|
| 843 | do up to 2 passes (normally) 5 if restart */ |
---|
| 844 | int numberPasses = 2; |
---|
| 845 | if (numberNodes < 0) { |
---|
| 846 | numberPasses = 5; |
---|
| 847 | // Say some rows cuts |
---|
| 848 | int numberRows = solver->getNumRows(); |
---|
| 849 | if (numberNodes_ < numberRows && true /* think */) { |
---|
| 850 | char * type = new char[numberRows]; |
---|
| 851 | memset(type, 0, numberNodes_); |
---|
| 852 | memset(type + numberNodes_, 1, numberRows - numberNodes_); |
---|
| 853 | process.passInRowTypes(type, numberRows); |
---|
| 854 | delete [] type; |
---|
| 855 | } |
---|
| 856 | } |
---|
| 857 | if (logLevel <= 1) |
---|
| 858 | process.messageHandler()->setLogLevel(0); |
---|
[1570] | 859 | if (!solver->defaultHandler()&& |
---|
| 860 | solver->messageHandler()->logLevel(0)!=-1000) |
---|
| 861 | process.passInMessageHandler(solver->messageHandler()); |
---|
[1286] | 862 | OsiSolverInterface * solver2 = process.preProcessNonDefault(*solver, false, |
---|
| 863 | numberPasses); |
---|
| 864 | if (!solver2) { |
---|
| 865 | if (logLevel > 1) |
---|
| 866 | printf("Pre-processing says infeasible\n"); |
---|
| 867 | returnCode = 2; // so will be infeasible |
---|
| 868 | } else { |
---|
[1121] | 869 | #ifdef COIN_DEVELOP_z |
---|
[1286] | 870 | if (numberNodes < 0) { |
---|
| 871 | solver2->writeMpsNative("after2.mps", NULL, NULL, 2, 1); |
---|
| 872 | } |
---|
[1121] | 873 | #endif |
---|
[1286] | 874 | // see if too big |
---|
| 875 | double ratio = sizeRatio(solver2->getNumRows() - shiftRows, solver2->getNumCols(), |
---|
| 876 | numberRowsStart, numberColumnsStart); |
---|
| 877 | double after = 2 * solver2->getNumRows() + solver2->getNumCols(); |
---|
| 878 | if (ratio > fractionSmall && (after > 300 || numberNodes < 0)) { |
---|
| 879 | sprintf(generalPrint, "Full problem %d rows %d columns, reduced to %d rows %d columns - too large", |
---|
| 880 | solver->getNumRows(), solver->getNumCols(), |
---|
| 881 | solver2->getNumRows(), solver2->getNumCols()); |
---|
| 882 | model_->messageHandler()->message(CBC_FPUMP1, model_->messages()) |
---|
| 883 | << generalPrint |
---|
| 884 | << CoinMessageEol; |
---|
| 885 | returnCode = -1; |
---|
| 886 | //printf("small no good2\n"); |
---|
| 887 | } else { |
---|
| 888 | sprintf(generalPrint, "Full problem %d rows %d columns, reduced to %d rows %d columns", |
---|
| 889 | solver->getNumRows(), solver->getNumCols(), |
---|
| 890 | solver2->getNumRows(), solver2->getNumCols()); |
---|
| 891 | model_->messageHandler()->message(CBC_FPUMP1, model_->messages()) |
---|
| 892 | << generalPrint |
---|
| 893 | << CoinMessageEol; |
---|
| 894 | } |
---|
| 895 | if (returnCode == 1) { |
---|
| 896 | solver2->resolve(); |
---|
| 897 | CbcModel model(*solver2); |
---|
| 898 | if (numberNodes >= 0) { |
---|
| 899 | // normal |
---|
| 900 | model.setSpecialOptions(saveModelOptions | 2048); |
---|
| 901 | if (logLevel <= 1) |
---|
| 902 | model.setLogLevel(0); |
---|
| 903 | else |
---|
| 904 | model.setLogLevel(logLevel); |
---|
| 905 | // No small fathoming |
---|
| 906 | model.setFastNodeDepth(-1); |
---|
[1499] | 907 | model.setCutoff(signedCutoff); |
---|
| 908 | // Don't do if original fraction > 1.0 and too large |
---|
| 909 | if (fractionSmall_>1.0) { |
---|
| 910 | /* 1.4 means -1 nodes if >.4 |
---|
| 911 | 2.4 means -1 nodes if >.5 and 0 otherwise |
---|
| 912 | 3.4 means -1 nodes if >.6 and 0 or 5 |
---|
| 913 | 4.4 means -1 nodes if >.7 and 0, 5 or 10 |
---|
| 914 | */ |
---|
| 915 | double fraction = fractionSmall_-floor(fractionSmall_); |
---|
| 916 | if (ratio>fraction) { |
---|
| 917 | int type = static_cast<int>(floor(fractionSmall_*0.1)); |
---|
| 918 | int over = static_cast<int>(ceil(ratio-fraction)); |
---|
| 919 | int maxNodes[]={-1,0,5,10}; |
---|
| 920 | if (type>over) |
---|
| 921 | numberNodes=maxNodes[type-over]; |
---|
| 922 | else |
---|
| 923 | numberNodes=-1; |
---|
| 924 | } |
---|
| 925 | } |
---|
[1286] | 926 | model.setMaximumNodes(numberNodes); |
---|
| 927 | model.solver()->setHintParam(OsiDoReducePrint, true, OsiHintTry); |
---|
[1582] | 928 | if ((saveModelOptions&2048) == 0) |
---|
| 929 | model.setMoreSpecialOptions(model_->moreSpecialOptions()); |
---|
[1286] | 930 | // Lightweight |
---|
| 931 | CbcStrategyDefaultSubTree strategy(model_, 1, 5, 1, 0); |
---|
| 932 | model.setStrategy(strategy); |
---|
| 933 | model.solver()->setIntParam(OsiMaxNumIterationHotStart, 10); |
---|
| 934 | model.setMaximumCutPassesAtRoot(CoinMin(20, CoinAbs(model_->getMaximumCutPassesAtRoot()))); |
---|
| 935 | model.setMaximumCutPasses(CoinMin(10, model_->getMaximumCutPasses())); |
---|
| 936 | } else { |
---|
| 937 | model.setSpecialOptions(saveModelOptions); |
---|
| 938 | model_->messageHandler()->message(CBC_RESTART, model_->messages()) |
---|
| 939 | << solver2->getNumRows() << solver2->getNumCols() |
---|
| 940 | << CoinMessageEol; |
---|
| 941 | // going for full search and copy across more stuff |
---|
| 942 | model.gutsOfCopy(*model_, 2); |
---|
| 943 | for (int i = 0; i < model.numberCutGenerators(); i++) { |
---|
[1499] | 944 | CbcCutGenerator * generator = model.cutGenerator(i); |
---|
| 945 | CglGomory * gomory = dynamic_cast<CglGomory *> |
---|
| 946 | (generator->generator()); |
---|
| 947 | if (gomory&&gomory->originalSolver()) |
---|
| 948 | gomory->passInOriginalSolver(model.solver()); |
---|
| 949 | generator->setTiming(true); |
---|
[1286] | 950 | // Turn on if was turned on |
---|
| 951 | int iOften = model_->cutGenerator(i)->howOften(); |
---|
[1053] | 952 | #ifdef CLP_INVESTIGATE |
---|
[1286] | 953 | printf("Gen %d often %d %d\n", |
---|
[1499] | 954 | i, generator->howOften(), |
---|
[1286] | 955 | iOften); |
---|
[1053] | 956 | #endif |
---|
[1286] | 957 | if (iOften > 0) |
---|
[1499] | 958 | generator->setHowOften(iOften % 1000000); |
---|
[1286] | 959 | if (model_->cutGenerator(i)->howOftenInSub() == -200) |
---|
[1499] | 960 | generator->setHowOften(-100); |
---|
[1286] | 961 | } |
---|
[1499] | 962 | model.setCutoff(signedCutoff); |
---|
[1286] | 963 | // make sure can't do nested search! but allow heuristics |
---|
| 964 | model.setSpecialOptions((model.specialOptions()&(~(512 + 2048))) | 1024); |
---|
| 965 | bool takeHint; |
---|
| 966 | OsiHintStrength strength; |
---|
| 967 | // Switch off printing if asked to |
---|
| 968 | model_->solver()->getHintParam(OsiDoReducePrint, takeHint, strength); |
---|
| 969 | model.solver()->setHintParam(OsiDoReducePrint, takeHint, strength); |
---|
| 970 | CbcStrategyDefault strategy(1, model_->numberStrong(), |
---|
| 971 | model_->numberBeforeTrust()); |
---|
| 972 | // Set up pre-processing - no |
---|
| 973 | strategy.setupPreProcessing(0); // was (4); |
---|
| 974 | model.setStrategy(strategy); |
---|
| 975 | //model.solver()->writeMps("crunched"); |
---|
| 976 | int numberCuts = process.cuts().sizeRowCuts(); |
---|
| 977 | if (numberCuts) { |
---|
| 978 | // add in cuts |
---|
| 979 | CglStored cuts = process.cuts(); |
---|
| 980 | model.addCutGenerator(&cuts, 1, "Stored from first"); |
---|
| 981 | } |
---|
| 982 | } |
---|
| 983 | // Do search |
---|
| 984 | if (logLevel > 1) |
---|
| 985 | model_->messageHandler()->message(CBC_START_SUB, model_->messages()) |
---|
| 986 | << name |
---|
| 987 | << model.getMaximumNodes() |
---|
| 988 | << CoinMessageEol; |
---|
| 989 | // probably faster to use a basis to get integer solutions |
---|
| 990 | model.setSpecialOptions(model.specialOptions() | 2); |
---|
[687] | 991 | #ifdef CBC_THREAD |
---|
[1286] | 992 | if (model_->getNumberThreads() > 0 && (model_->getThreadMode()&4) != 0) { |
---|
| 993 | // See if at root node |
---|
| 994 | bool atRoot = model_->getNodeCount() == 0; |
---|
| 995 | int passNumber = model_->getCurrentPassNumber(); |
---|
| 996 | if (atRoot && passNumber == 1) |
---|
| 997 | model.setNumberThreads(model_->getNumberThreads()); |
---|
| 998 | } |
---|
[687] | 999 | #endif |
---|
[1286] | 1000 | model.setParentModel(*model_); |
---|
| 1001 | model.setOriginalColumns(process.originalColumns()); |
---|
| 1002 | model.setSearchStrategy(-1); |
---|
| 1003 | // If no feasibility pump then insert a lightweight one |
---|
| 1004 | if (feasibilityPumpOptions_ >= 0) { |
---|
| 1005 | bool gotPump = false; |
---|
| 1006 | for (int i = 0; i < model.numberHeuristics(); i++) { |
---|
| 1007 | const CbcHeuristicFPump* pump = |
---|
| 1008 | dynamic_cast<const CbcHeuristicFPump*>(model.heuristic(i)); |
---|
| 1009 | if (pump) |
---|
| 1010 | gotPump = true; |
---|
| 1011 | } |
---|
| 1012 | if (!gotPump) { |
---|
| 1013 | CbcHeuristicFPump heuristic4; |
---|
[1569] | 1014 | // use any cutoff |
---|
| 1015 | heuristic4.setFakeCutoff(0.5*COIN_DBL_MAX); |
---|
[1499] | 1016 | if (fractionSmall_<=1.0) |
---|
| 1017 | heuristic4.setMaximumPasses(10); |
---|
[1286] | 1018 | int pumpTune = feasibilityPumpOptions_; |
---|
| 1019 | if (pumpTune > 0) { |
---|
| 1020 | /* |
---|
| 1021 | >=10000000 for using obj |
---|
| 1022 | >=1000000 use as accumulate switch |
---|
| 1023 | >=1000 use index+1 as number of large loops |
---|
| 1024 | >=100 use 0.05 objvalue as increment |
---|
| 1025 | %100 == 10,20 etc for experimentation |
---|
| 1026 | 1 == fix ints at bounds, 2 fix all integral ints, 3 and continuous at bounds |
---|
| 1027 | 4 and static continuous, 5 as 3 but no internal integers |
---|
| 1028 | 6 as 3 but all slack basis! |
---|
| 1029 | */ |
---|
| 1030 | double value = solver2->getObjSense() * solver2->getObjValue(); |
---|
| 1031 | int w = pumpTune / 10; |
---|
| 1032 | int ix = w % 10; |
---|
| 1033 | w /= 10; |
---|
| 1034 | int c = w % 10; |
---|
| 1035 | w /= 10; |
---|
| 1036 | int r = w; |
---|
| 1037 | int accumulate = r / 1000; |
---|
| 1038 | r -= 1000 * accumulate; |
---|
| 1039 | if (accumulate >= 10) { |
---|
| 1040 | int which = accumulate / 10; |
---|
| 1041 | accumulate -= 10 * which; |
---|
| 1042 | which--; |
---|
| 1043 | // weights and factors |
---|
| 1044 | double weight[] = {0.1, 0.1, 0.5, 0.5, 1.0, 1.0, 5.0, 5.0}; |
---|
| 1045 | double factor[] = {0.1, 0.5, 0.1, 0.5, 0.1, 0.5, 0.1, 0.5}; |
---|
| 1046 | heuristic4.setInitialWeight(weight[which]); |
---|
| 1047 | heuristic4.setWeightFactor(factor[which]); |
---|
| 1048 | } |
---|
| 1049 | // fake cutoff |
---|
| 1050 | if (c) { |
---|
| 1051 | double cutoff; |
---|
| 1052 | solver2->getDblParam(OsiDualObjectiveLimit, cutoff); |
---|
| 1053 | cutoff = CoinMin(cutoff, value + 0.1 * fabs(value) * c); |
---|
| 1054 | heuristic4.setFakeCutoff(cutoff); |
---|
| 1055 | } |
---|
| 1056 | if (r) { |
---|
| 1057 | // also set increment |
---|
| 1058 | //double increment = (0.01*i+0.005)*(fabs(value)+1.0e-12); |
---|
| 1059 | double increment = 0.0; |
---|
| 1060 | heuristic4.setAbsoluteIncrement(increment); |
---|
| 1061 | heuristic4.setAccumulate(accumulate); |
---|
| 1062 | heuristic4.setMaximumRetries(r + 1); |
---|
| 1063 | } |
---|
| 1064 | pumpTune = pumpTune % 100; |
---|
| 1065 | if (pumpTune == 6) |
---|
| 1066 | pumpTune = 13; |
---|
| 1067 | if (pumpTune != 13) |
---|
| 1068 | pumpTune = pumpTune % 10; |
---|
| 1069 | heuristic4.setWhen(pumpTune); |
---|
| 1070 | if (ix) { |
---|
| 1071 | heuristic4.setFeasibilityPumpOptions(ix*10); |
---|
| 1072 | } |
---|
| 1073 | } |
---|
| 1074 | model.addHeuristic(&heuristic4, "feasibility pump", 0); |
---|
| 1075 | } |
---|
| 1076 | } |
---|
| 1077 | //printf("sol %x\n",inputSolution_); |
---|
| 1078 | if (inputSolution_) { |
---|
| 1079 | // translate and add a serendipity heuristic |
---|
| 1080 | int numberColumns = solver2->getNumCols(); |
---|
| 1081 | const int * which = process.originalColumns(); |
---|
| 1082 | OsiSolverInterface * solver3 = solver2->clone(); |
---|
| 1083 | for (int i = 0; i < numberColumns; i++) { |
---|
| 1084 | if (solver3->isInteger(i)) { |
---|
| 1085 | int k = which[i]; |
---|
| 1086 | double value = inputSolution_[k]; |
---|
| 1087 | //if (value) |
---|
| 1088 | //printf("orig col %d now %d val %g\n", |
---|
| 1089 | // k,i,value); |
---|
| 1090 | solver3->setColLower(i, value); |
---|
| 1091 | solver3->setColUpper(i, value); |
---|
| 1092 | } |
---|
| 1093 | } |
---|
| 1094 | solver3->setDblParam(OsiDualObjectiveLimit, COIN_DBL_MAX); |
---|
| 1095 | solver3->resolve(); |
---|
| 1096 | if (!solver3->isProvenOptimal()) { |
---|
| 1097 | // Try just setting nonzeros |
---|
| 1098 | OsiSolverInterface * solver4 = solver2->clone(); |
---|
| 1099 | for (int i = 0; i < numberColumns; i++) { |
---|
| 1100 | if (solver4->isInteger(i)) { |
---|
| 1101 | int k = which[i]; |
---|
| 1102 | double value = floor(inputSolution_[k] + 0.5); |
---|
| 1103 | if (value) { |
---|
| 1104 | solver3->setColLower(i, value); |
---|
| 1105 | solver3->setColUpper(i, value); |
---|
| 1106 | } |
---|
| 1107 | } |
---|
| 1108 | } |
---|
| 1109 | solver4->setDblParam(OsiDualObjectiveLimit, COIN_DBL_MAX); |
---|
| 1110 | solver4->resolve(); |
---|
| 1111 | int nBad = -1; |
---|
| 1112 | if (solver4->isProvenOptimal()) { |
---|
| 1113 | nBad = 0; |
---|
| 1114 | const double * solution = solver4->getColSolution(); |
---|
| 1115 | for (int i = 0; i < numberColumns; i++) { |
---|
| 1116 | if (solver4->isInteger(i)) { |
---|
| 1117 | double value = floor(solution[i] + 0.5); |
---|
| 1118 | if (fabs(value - solution[i]) > 1.0e-6) |
---|
| 1119 | nBad++; |
---|
| 1120 | } |
---|
| 1121 | } |
---|
| 1122 | } |
---|
| 1123 | if (nBad) { |
---|
| 1124 | delete solver4; |
---|
| 1125 | } else { |
---|
| 1126 | delete solver3; |
---|
| 1127 | solver3 = solver4; |
---|
| 1128 | } |
---|
| 1129 | } |
---|
| 1130 | if (solver3->isProvenOptimal()) { |
---|
| 1131 | // good |
---|
| 1132 | CbcSerendipity heuristic(model); |
---|
| 1133 | double value = solver3->getObjSense() * solver3->getObjValue(); |
---|
| 1134 | heuristic.setInputSolution(solver3->getColSolution(), value); |
---|
[1499] | 1135 | value = value + 1.0e-7*(1.0 + fabs(value)); |
---|
| 1136 | value *= solver3->getObjSense(); |
---|
| 1137 | model.setCutoff(value); |
---|
[1286] | 1138 | model.addHeuristic(&heuristic, "Previous solution", 0); |
---|
| 1139 | //printf("added seren\n"); |
---|
| 1140 | } else { |
---|
| 1141 | double value = model_->getMinimizationObjValue(); |
---|
[1499] | 1142 | value = value + 1.0e-7*(1.0 + fabs(value)); |
---|
| 1143 | value *= solver3->getObjSense(); |
---|
| 1144 | model.setCutoff(value); |
---|
[1132] | 1145 | #ifdef CLP_INVESTIGATE |
---|
[1286] | 1146 | printf("NOT added seren\n"); |
---|
| 1147 | solver3->writeMps("bad_seren"); |
---|
| 1148 | solver->writeMps("orig_seren"); |
---|
[1150] | 1149 | #endif |
---|
[1286] | 1150 | } |
---|
| 1151 | delete solver3; |
---|
| 1152 | } |
---|
| 1153 | if (model_->searchStrategy() == 2) { |
---|
| 1154 | model.setNumberStrong(5); |
---|
| 1155 | model.setNumberBeforeTrust(5); |
---|
| 1156 | } |
---|
| 1157 | if (model.getNumCols()) { |
---|
| 1158 | if (numberNodes >= 0) { |
---|
| 1159 | setCutAndHeuristicOptions(model); |
---|
| 1160 | // not too many iterations |
---|
| 1161 | model.setMaximumNumberIterations(100*(numberNodes + 10)); |
---|
| 1162 | // Not fast stuff |
---|
| 1163 | model.setFastNodeDepth(-1); |
---|
| 1164 | } else if (model.fastNodeDepth() >= 1000000) { |
---|
| 1165 | // already set |
---|
| 1166 | model.setFastNodeDepth(model.fastNodeDepth() - 1000000); |
---|
| 1167 | } |
---|
| 1168 | model.setWhenCuts(999998); |
---|
[1499] | 1169 | #define ALWAYS_DUAL |
---|
| 1170 | #ifdef ALWAYS_DUAL |
---|
| 1171 | OsiSolverInterface * solver = model.solver(); |
---|
| 1172 | bool takeHint; |
---|
| 1173 | OsiHintStrength strength; |
---|
| 1174 | solver->getHintParam(OsiDoDualInResolve, takeHint, strength); |
---|
| 1175 | solver->setHintParam(OsiDoDualInResolve, true, OsiHintDo); |
---|
| 1176 | #endif |
---|
[1587] | 1177 | model.passInEventHandler(model_->getEventHandler()); |
---|
[1725] | 1178 | // say model_ is sitting there |
---|
| 1179 | int saveOptions = model_->specialOptions(); |
---|
| 1180 | model_->setSpecialOptions(saveOptions|1048576); |
---|
[1286] | 1181 | model.branchAndBound(); |
---|
[1725] | 1182 | model_->setSpecialOptions(saveOptions); |
---|
[1499] | 1183 | #ifdef ALWAYS_DUAL |
---|
[1514] | 1184 | solver = model.solver(); |
---|
[1499] | 1185 | solver->setHintParam(OsiDoDualInResolve, takeHint, strength); |
---|
| 1186 | #endif |
---|
[1013] | 1187 | #ifdef COIN_DEVELOP |
---|
[1286] | 1188 | printf("sub branch %d nodes, %d iterations - max %d\n", |
---|
| 1189 | model.getNodeCount(), model.getIterationCount(), |
---|
| 1190 | 100*(numberNodes + 10)); |
---|
[1013] | 1191 | #endif |
---|
[1286] | 1192 | if (numberNodes < 0) { |
---|
| 1193 | model_->incrementIterationCount(model.getIterationCount()); |
---|
| 1194 | model_->incrementNodeCount(model.getNodeCount()); |
---|
| 1195 | for (int iGenerator = 0; iGenerator < model.numberCutGenerators(); iGenerator++) { |
---|
| 1196 | CbcCutGenerator * generator = model.cutGenerator(iGenerator); |
---|
| 1197 | sprintf(generalPrint, |
---|
| 1198 | "%s was tried %d times and created %d cuts of which %d were active after adding rounds of cuts (%.3f seconds)", |
---|
| 1199 | generator->cutGeneratorName(), |
---|
| 1200 | generator->numberTimesEntered(), |
---|
| 1201 | generator->numberCutsInTotal() + |
---|
| 1202 | generator->numberColumnCuts(), |
---|
| 1203 | generator->numberCutsActive(), |
---|
| 1204 | generator->timeInCutGenerator()); |
---|
| 1205 | CglStored * stored = dynamic_cast<CglStored*>(generator->generator()); |
---|
| 1206 | if (stored && !generator->numberCutsInTotal()) |
---|
| 1207 | continue; |
---|
[1059] | 1208 | #ifndef CLP_INVESTIGATE |
---|
[1286] | 1209 | CglImplication * implication = dynamic_cast<CglImplication*>(generator->generator()); |
---|
| 1210 | if (implication) |
---|
| 1211 | continue; |
---|
[1059] | 1212 | #endif |
---|
[1286] | 1213 | model_->messageHandler()->message(CBC_FPUMP1, model_->messages()) |
---|
| 1214 | << generalPrint |
---|
| 1215 | << CoinMessageEol; |
---|
| 1216 | } |
---|
| 1217 | } |
---|
| 1218 | } else { |
---|
| 1219 | // empty model |
---|
| 1220 | model.setMinimizationObjValue(model.solver()->getObjSense()*model.solver()->getObjValue()); |
---|
| 1221 | } |
---|
| 1222 | if (logLevel > 1) |
---|
| 1223 | model_->messageHandler()->message(CBC_END_SUB, model_->messages()) |
---|
| 1224 | << name |
---|
| 1225 | << CoinMessageEol; |
---|
| 1226 | if (model.getMinimizationObjValue() < CoinMin(cutoff, 1.0e30)) { |
---|
| 1227 | // solution |
---|
| 1228 | if (model.getNumCols()) |
---|
| 1229 | returnCode = model.isProvenOptimal() ? 3 : 1; |
---|
| 1230 | else |
---|
| 1231 | returnCode = 3; |
---|
| 1232 | // post process |
---|
[700] | 1233 | #ifdef COIN_HAS_CLP |
---|
[1286] | 1234 | OsiClpSolverInterface * clpSolver = dynamic_cast< OsiClpSolverInterface*> (model.solver()); |
---|
| 1235 | if (clpSolver) { |
---|
| 1236 | ClpSimplex * lpSolver = clpSolver->getModelPtr(); |
---|
| 1237 | lpSolver->setSpecialOptions(lpSolver->specialOptions() | 0x01000000); // say is Cbc (and in branch and bound) |
---|
| 1238 | } |
---|
[700] | 1239 | #endif |
---|
[1286] | 1240 | process.postProcess(*model.solver()); |
---|
[1499] | 1241 | if (solver->isProvenOptimal() && solver->getObjValue()*solver->getObjSense() < cutoff) { |
---|
[1286] | 1242 | // Solution now back in solver |
---|
| 1243 | int numberColumns = solver->getNumCols(); |
---|
| 1244 | memcpy(newSolution, solver->getColSolution(), |
---|
| 1245 | numberColumns*sizeof(double)); |
---|
| 1246 | newSolutionValue = model.getMinimizationObjValue(); |
---|
| 1247 | } else { |
---|
| 1248 | // odd - but no good |
---|
| 1249 | returnCode = 0; // so will be infeasible |
---|
| 1250 | } |
---|
| 1251 | } else { |
---|
| 1252 | // no good |
---|
| 1253 | returnCode = model.isProvenInfeasible() ? 2 : 0; // so will be infeasible |
---|
| 1254 | } |
---|
| 1255 | int totalNumberIterations = model.getIterationCount() + |
---|
| 1256 | process.numberIterationsPre() + |
---|
| 1257 | process.numberIterationsPost(); |
---|
| 1258 | if (totalNumberIterations > 100*(numberNodes + 10)) { |
---|
| 1259 | // only allow smaller problems |
---|
| 1260 | fractionSmall = fractionSmall_; |
---|
| 1261 | fractionSmall_ *= 0.9; |
---|
[1013] | 1262 | #ifdef CLP_INVESTIGATE |
---|
[1286] | 1263 | printf("changing fractionSmall from %g to %g for %s as %d iterations\n", |
---|
| 1264 | fractionSmall, fractionSmall_, name.c_str(), totalNumberIterations); |
---|
[1013] | 1265 | #endif |
---|
[1286] | 1266 | } |
---|
| 1267 | if (model.status() == 5) |
---|
| 1268 | returnCode = -2; // stop |
---|
| 1269 | if (model.isProvenInfeasible()) |
---|
| 1270 | status = 1; |
---|
| 1271 | else if (model.isProvenOptimal()) |
---|
| 1272 | status = 2; |
---|
| 1273 | } |
---|
| 1274 | } |
---|
| 1275 | } else { |
---|
| 1276 | returnCode = 2; // infeasible finished |
---|
[197] | 1277 | } |
---|
[1286] | 1278 | model_->setSpecialOptions(saveModelOptions); |
---|
| 1279 | model_->setLogLevel(logLevel); |
---|
| 1280 | if (returnCode == 1 || returnCode == 2) { |
---|
| 1281 | OsiSolverInterface * solverC = model_->continuousSolver(); |
---|
| 1282 | if (false && solverC) { |
---|
| 1283 | const double * lower = solver->getColLower(); |
---|
| 1284 | const double * upper = solver->getColUpper(); |
---|
| 1285 | const double * lowerC = solverC->getColLower(); |
---|
| 1286 | const double * upperC = solverC->getColUpper(); |
---|
| 1287 | bool good = true; |
---|
| 1288 | for (int iColumn = 0; iColumn < numberColumns; iColumn++) { |
---|
| 1289 | if (solverC->isInteger(iColumn)) { |
---|
| 1290 | if (lower[iColumn] > lowerC[iColumn] && |
---|
| 1291 | upper[iColumn] < upperC[iColumn]) { |
---|
| 1292 | good = false; |
---|
| 1293 | printf("CUT - can't add\n"); |
---|
| 1294 | break; |
---|
| 1295 | } |
---|
| 1296 | } |
---|
| 1297 | } |
---|
| 1298 | if (good) { |
---|
| 1299 | double * cut = new double [numberColumns]; |
---|
| 1300 | int * which = new int [numberColumns]; |
---|
| 1301 | double rhs = -1.0; |
---|
| 1302 | int n = 0; |
---|
| 1303 | for (int iColumn = 0; iColumn < numberColumns; iColumn++) { |
---|
| 1304 | if (solverC->isInteger(iColumn)) { |
---|
| 1305 | if (lower[iColumn] == upperC[iColumn]) { |
---|
| 1306 | rhs += lower[iColumn]; |
---|
| 1307 | cut[n] = 1.0; |
---|
| 1308 | which[n++] = iColumn; |
---|
| 1309 | } else if (upper[iColumn] == lowerC[iColumn]) { |
---|
| 1310 | rhs -= upper[iColumn]; |
---|
| 1311 | cut[n] = -1.0; |
---|
| 1312 | which[n++] = iColumn; |
---|
| 1313 | } |
---|
| 1314 | } |
---|
| 1315 | } |
---|
| 1316 | printf("CUT has %d entries\n", n); |
---|
| 1317 | OsiRowCut newCut; |
---|
| 1318 | newCut.setLb(-COIN_DBL_MAX); |
---|
| 1319 | newCut.setUb(rhs); |
---|
| 1320 | newCut.setRow(n, which, cut, false); |
---|
| 1321 | model_->makeGlobalCut(newCut); |
---|
| 1322 | delete [] cut; |
---|
| 1323 | delete [] which; |
---|
| 1324 | } |
---|
| 1325 | } |
---|
[1271] | 1326 | #ifdef COIN_DEVELOP |
---|
[1286] | 1327 | if (status == 1) |
---|
| 1328 | printf("heuristic could add cut because infeasible (%s)\n", heuristicName_.c_str()); |
---|
| 1329 | else if (status == 2) |
---|
| 1330 | printf("heuristic could add cut because optimal (%s)\n", heuristicName_.c_str()); |
---|
[1271] | 1331 | #endif |
---|
[833] | 1332 | } |
---|
[1286] | 1333 | if (reset) { |
---|
| 1334 | for (int iColumn = 0; iColumn < numberColumns; iColumn++) { |
---|
| 1335 | if (reset[iColumn]) |
---|
| 1336 | solver->setColLower(iColumn, 0.0); |
---|
| 1337 | } |
---|
| 1338 | delete [] reset; |
---|
| 1339 | } |
---|
[1013] | 1340 | #ifdef HISTORY_STATISTICS |
---|
[1286] | 1341 | getHistoryStatistics_ = true; |
---|
[1013] | 1342 | #endif |
---|
[1286] | 1343 | solver->setHintParam(OsiDoReducePrint, takeHint, strength); |
---|
| 1344 | return returnCode; |
---|
[197] | 1345 | } |
---|
[940] | 1346 | // Set input solution |
---|
[1286] | 1347 | void |
---|
[940] | 1348 | CbcHeuristic::setInputSolution(const double * solution, double objValue) |
---|
| 1349 | { |
---|
[1286] | 1350 | delete [] inputSolution_; |
---|
| 1351 | inputSolution_ = NULL; |
---|
| 1352 | if (model_ && solution) { |
---|
| 1353 | int numberColumns = model_->getNumCols(); |
---|
| 1354 | inputSolution_ = new double [numberColumns+1]; |
---|
| 1355 | memcpy(inputSolution_, solution, numberColumns*sizeof(double)); |
---|
| 1356 | inputSolution_[numberColumns] = objValue; |
---|
| 1357 | } |
---|
[940] | 1358 | } |
---|
[2] | 1359 | |
---|
[912] | 1360 | //############################################################################## |
---|
| 1361 | |
---|
| 1362 | inline int compare3BranchingObjects(const CbcBranchingObject* br0, |
---|
[1286] | 1363 | const CbcBranchingObject* br1) |
---|
[912] | 1364 | { |
---|
[1286] | 1365 | const int t0 = br0->type(); |
---|
| 1366 | const int t1 = br1->type(); |
---|
| 1367 | if (t0 < t1) { |
---|
| 1368 | return -1; |
---|
| 1369 | } |
---|
| 1370 | if (t0 > t1) { |
---|
| 1371 | return 1; |
---|
| 1372 | } |
---|
| 1373 | return br0->compareOriginalObject(br1); |
---|
[912] | 1374 | } |
---|
| 1375 | |
---|
| 1376 | //============================================================================== |
---|
| 1377 | |
---|
| 1378 | inline bool compareBranchingObjects(const CbcBranchingObject* br0, |
---|
[1286] | 1379 | const CbcBranchingObject* br1) |
---|
[912] | 1380 | { |
---|
[1286] | 1381 | return compare3BranchingObjects(br0, br1) < 0; |
---|
[912] | 1382 | } |
---|
| 1383 | |
---|
| 1384 | //============================================================================== |
---|
| 1385 | |
---|
| 1386 | void |
---|
| 1387 | CbcHeuristicNode::gutsOfConstructor(CbcModel& model) |
---|
| 1388 | { |
---|
[1286] | 1389 | // CbcHeurDebugNodes(&model); |
---|
| 1390 | CbcNode* node = model.currentNode(); |
---|
| 1391 | brObj_ = new CbcBranchingObject*[node->depth()]; |
---|
| 1392 | CbcNodeInfo* nodeInfo = node->nodeInfo(); |
---|
| 1393 | int cnt = 0; |
---|
| 1394 | while (nodeInfo->parentBranch() != NULL) { |
---|
| 1395 | const OsiBranchingObject* br = nodeInfo->parentBranch(); |
---|
| 1396 | const CbcBranchingObject* cbcbr = dynamic_cast<const CbcBranchingObject*>(br); |
---|
| 1397 | if (! cbcbr) { |
---|
| 1398 | throw CoinError("CbcHeuristicNode can be used only with CbcBranchingObjects.\n", |
---|
| 1399 | "gutsOfConstructor", |
---|
| 1400 | "CbcHeuristicNode", |
---|
| 1401 | __FILE__, __LINE__); |
---|
| 1402 | } |
---|
| 1403 | brObj_[cnt] = cbcbr->clone(); |
---|
| 1404 | brObj_[cnt]->previousBranch(); |
---|
| 1405 | ++cnt; |
---|
| 1406 | nodeInfo = nodeInfo->parent(); |
---|
[915] | 1407 | } |
---|
[1286] | 1408 | std::sort(brObj_, brObj_ + cnt, compareBranchingObjects); |
---|
| 1409 | if (cnt <= 1) { |
---|
| 1410 | numObjects_ = cnt; |
---|
| 1411 | } else { |
---|
| 1412 | numObjects_ = 0; |
---|
| 1413 | CbcBranchingObject* br = NULL; // What should this be? |
---|
| 1414 | for (int i = 1; i < cnt; ++i) { |
---|
| 1415 | if (compare3BranchingObjects(brObj_[numObjects_], brObj_[i]) == 0) { |
---|
[1357] | 1416 | int comp = brObj_[numObjects_]->compareBranchingObject(brObj_[i], br != 0); |
---|
[1286] | 1417 | switch (comp) { |
---|
| 1418 | case CbcRangeSame: // the same range |
---|
| 1419 | case CbcRangeDisjoint: // disjoint decisions |
---|
| 1420 | // should not happen! we are on a chain! |
---|
| 1421 | abort(); |
---|
| 1422 | case CbcRangeSubset: // brObj_[numObjects_] is a subset of brObj_[i] |
---|
| 1423 | delete brObj_[i]; |
---|
| 1424 | break; |
---|
| 1425 | case CbcRangeSuperset: // brObj_[i] is a subset of brObj_[numObjects_] |
---|
| 1426 | delete brObj_[numObjects_]; |
---|
| 1427 | brObj_[numObjects_] = brObj_[i]; |
---|
| 1428 | break; |
---|
| 1429 | case CbcRangeOverlap: // overlap |
---|
| 1430 | delete brObj_[i]; |
---|
| 1431 | delete brObj_[numObjects_]; |
---|
| 1432 | brObj_[numObjects_] = br; |
---|
| 1433 | break; |
---|
| 1434 | } |
---|
| 1435 | continue; |
---|
| 1436 | } else { |
---|
| 1437 | brObj_[++numObjects_] = brObj_[i]; |
---|
| 1438 | } |
---|
| 1439 | } |
---|
| 1440 | ++numObjects_; |
---|
[912] | 1441 | } |
---|
| 1442 | } |
---|
| 1443 | |
---|
| 1444 | //============================================================================== |
---|
| 1445 | |
---|
| 1446 | CbcHeuristicNode::CbcHeuristicNode(CbcModel& model) |
---|
| 1447 | { |
---|
[1286] | 1448 | gutsOfConstructor(model); |
---|
[912] | 1449 | } |
---|
| 1450 | |
---|
| 1451 | //============================================================================== |
---|
| 1452 | |
---|
| 1453 | double |
---|
[1286] | 1454 | CbcHeuristicNode::distance(const CbcHeuristicNode* node) const |
---|
[912] | 1455 | { |
---|
| 1456 | |
---|
[1286] | 1457 | const double disjointWeight = 1; |
---|
| 1458 | const double overlapWeight = 0.4; |
---|
| 1459 | const double subsetWeight = 0.2; |
---|
| 1460 | int countDisjointWeight = 0; |
---|
| 1461 | int countOverlapWeight = 0; |
---|
| 1462 | int countSubsetWeight = 0; |
---|
| 1463 | int i = 0; |
---|
| 1464 | int j = 0; |
---|
| 1465 | double dist = 0.0; |
---|
[912] | 1466 | #ifdef PRINT_DEBUG |
---|
[1286] | 1467 | printf(" numObjects_ = %i, node->numObjects_ = %i\n", |
---|
| 1468 | numObjects_, node->numObjects_); |
---|
[912] | 1469 | #endif |
---|
[1286] | 1470 | while ( i < numObjects_ && j < node->numObjects_) { |
---|
| 1471 | CbcBranchingObject* br0 = brObj_[i]; |
---|
| 1472 | const CbcBranchingObject* br1 = node->brObj_[j]; |
---|
[912] | 1473 | #ifdef PRINT_DEBUG |
---|
[1286] | 1474 | const CbcIntegerBranchingObject* brPrint0 = |
---|
| 1475 | dynamic_cast<const CbcIntegerBranchingObject*>(br0); |
---|
| 1476 | const double* downBounds = brPrint0->downBounds(); |
---|
| 1477 | const double* upBounds = brPrint0->upBounds(); |
---|
| 1478 | int variable = brPrint0->variable(); |
---|
| 1479 | int way = brPrint0->way(); |
---|
| 1480 | printf(" br0: var %i downBd [%i,%i] upBd [%i,%i] way %i\n", |
---|
| 1481 | variable, static_cast<int>(downBounds[0]), static_cast<int>(downBounds[1]), |
---|
| 1482 | static_cast<int>(upBounds[0]), static_cast<int>(upBounds[1]), way); |
---|
| 1483 | const CbcIntegerBranchingObject* brPrint1 = |
---|
| 1484 | dynamic_cast<const CbcIntegerBranchingObject*>(br1); |
---|
| 1485 | downBounds = brPrint1->downBounds(); |
---|
| 1486 | upBounds = brPrint1->upBounds(); |
---|
| 1487 | variable = brPrint1->variable(); |
---|
| 1488 | way = brPrint1->way(); |
---|
| 1489 | printf(" br1: var %i downBd [%i,%i] upBd [%i,%i] way %i\n", |
---|
| 1490 | variable, static_cast<int>(downBounds[0]), static_cast<int>(downBounds[1]), |
---|
| 1491 | static_cast<int>(upBounds[0]), static_cast<int>(upBounds[1]), way); |
---|
[912] | 1492 | #endif |
---|
[1286] | 1493 | const int brComp = compare3BranchingObjects(br0, br1); |
---|
| 1494 | if (brComp < 0) { |
---|
| 1495 | dist += subsetWeight; |
---|
| 1496 | countSubsetWeight++; |
---|
| 1497 | ++i; |
---|
| 1498 | } else if (brComp > 0) { |
---|
| 1499 | dist += subsetWeight; |
---|
| 1500 | countSubsetWeight++; |
---|
| 1501 | ++j; |
---|
| 1502 | } else { |
---|
| 1503 | const int comp = br0->compareBranchingObject(br1, false); |
---|
| 1504 | switch (comp) { |
---|
| 1505 | case CbcRangeSame: |
---|
| 1506 | // do nothing |
---|
| 1507 | break; |
---|
| 1508 | case CbcRangeDisjoint: // disjoint decisions |
---|
| 1509 | dist += disjointWeight; |
---|
| 1510 | countDisjointWeight++; |
---|
| 1511 | break; |
---|
| 1512 | case CbcRangeSubset: // subset one way or another |
---|
| 1513 | case CbcRangeSuperset: |
---|
| 1514 | dist += subsetWeight; |
---|
| 1515 | countSubsetWeight++; |
---|
| 1516 | break; |
---|
| 1517 | case CbcRangeOverlap: // overlap |
---|
| 1518 | dist += overlapWeight; |
---|
| 1519 | countOverlapWeight++; |
---|
| 1520 | break; |
---|
| 1521 | } |
---|
| 1522 | ++i; |
---|
| 1523 | ++j; |
---|
| 1524 | } |
---|
[912] | 1525 | } |
---|
[1286] | 1526 | dist += subsetWeight * (numObjects_ - i + node->numObjects_ - j); |
---|
| 1527 | countSubsetWeight += (numObjects_ - i + node->numObjects_ - j); |
---|
[1641] | 1528 | COIN_DETAIL_PRINT(printf("subset = %i, overlap = %i, disjoint = %i\n", countSubsetWeight, |
---|
| 1529 | countOverlapWeight, countDisjointWeight)); |
---|
[1286] | 1530 | return dist; |
---|
[912] | 1531 | } |
---|
| 1532 | |
---|
| 1533 | //============================================================================== |
---|
| 1534 | |
---|
| 1535 | CbcHeuristicNode::~CbcHeuristicNode() |
---|
| 1536 | { |
---|
[1286] | 1537 | for (int i = 0; i < numObjects_; ++i) { |
---|
| 1538 | delete brObj_[i]; |
---|
| 1539 | } |
---|
| 1540 | delete [] brObj_; |
---|
[912] | 1541 | } |
---|
| 1542 | |
---|
| 1543 | //============================================================================== |
---|
| 1544 | |
---|
| 1545 | double |
---|
[915] | 1546 | CbcHeuristicNode::minDistance(const CbcHeuristicNodeList& nodeList) const |
---|
[912] | 1547 | { |
---|
[1286] | 1548 | double minDist = COIN_DBL_MAX; |
---|
| 1549 | for (int i = nodeList.size() - 1; i >= 0; --i) { |
---|
| 1550 | minDist = CoinMin(minDist, distance(nodeList.node(i))); |
---|
| 1551 | } |
---|
| 1552 | return minDist; |
---|
[912] | 1553 | } |
---|
| 1554 | |
---|
| 1555 | //============================================================================== |
---|
| 1556 | |
---|
[915] | 1557 | bool |
---|
| 1558 | CbcHeuristicNode::minDistanceIsSmall(const CbcHeuristicNodeList& nodeList, |
---|
[1286] | 1559 | const double threshold) const |
---|
[915] | 1560 | { |
---|
[1286] | 1561 | for (int i = nodeList.size() - 1; i >= 0; --i) { |
---|
| 1562 | if (distance(nodeList.node(i)) >= threshold) { |
---|
| 1563 | continue; |
---|
| 1564 | } else { |
---|
| 1565 | return true; |
---|
| 1566 | } |
---|
[915] | 1567 | } |
---|
[1286] | 1568 | return false; |
---|
[915] | 1569 | } |
---|
| 1570 | |
---|
| 1571 | //============================================================================== |
---|
| 1572 | |
---|
[912] | 1573 | double |
---|
[915] | 1574 | CbcHeuristicNode::avgDistance(const CbcHeuristicNodeList& nodeList) const |
---|
[912] | 1575 | { |
---|
[1286] | 1576 | if (nodeList.size() == 0) { |
---|
| 1577 | return COIN_DBL_MAX; |
---|
| 1578 | } |
---|
| 1579 | double sumDist = 0; |
---|
| 1580 | for (int i = nodeList.size() - 1; i >= 0; --i) { |
---|
| 1581 | sumDist += distance(nodeList.node(i)); |
---|
| 1582 | } |
---|
| 1583 | return sumDist / nodeList.size(); |
---|
[912] | 1584 | } |
---|
| 1585 | |
---|
| 1586 | //############################################################################## |
---|
| 1587 | |
---|
[2] | 1588 | // Default Constructor |
---|
[1286] | 1589 | CbcRounding::CbcRounding() |
---|
| 1590 | : CbcHeuristic() |
---|
[2] | 1591 | { |
---|
[1286] | 1592 | // matrix and row copy will automatically be empty |
---|
| 1593 | seed_ = 7654321; |
---|
| 1594 | down_ = NULL; |
---|
| 1595 | up_ = NULL; |
---|
| 1596 | equal_ = NULL; |
---|
[1315] | 1597 | //whereFrom_ |= 16; // allow more often |
---|
[2] | 1598 | } |
---|
| 1599 | |
---|
| 1600 | // Constructor from model |
---|
| 1601 | CbcRounding::CbcRounding(CbcModel & model) |
---|
[1286] | 1602 | : CbcHeuristic(model) |
---|
[2] | 1603 | { |
---|
[1286] | 1604 | // Get a copy of original matrix (and by row for rounding); |
---|
| 1605 | assert(model.solver()); |
---|
| 1606 | if (model.solver()->getNumRows()) { |
---|
| 1607 | matrix_ = *model.solver()->getMatrixByCol(); |
---|
| 1608 | matrixByRow_ = *model.solver()->getMatrixByRow(); |
---|
| 1609 | validate(); |
---|
| 1610 | } |
---|
| 1611 | down_ = NULL; |
---|
| 1612 | up_ = NULL; |
---|
| 1613 | equal_ = NULL; |
---|
| 1614 | seed_ = 7654321; |
---|
[1315] | 1615 | //whereFrom_ |= 16; // allow more often |
---|
[2] | 1616 | } |
---|
| 1617 | |
---|
[1286] | 1618 | // Destructor |
---|
[2] | 1619 | CbcRounding::~CbcRounding () |
---|
| 1620 | { |
---|
[1286] | 1621 | delete [] down_; |
---|
| 1622 | delete [] up_; |
---|
| 1623 | delete [] equal_; |
---|
[2] | 1624 | } |
---|
| 1625 | |
---|
| 1626 | // Clone |
---|
| 1627 | CbcHeuristic * |
---|
| 1628 | CbcRounding::clone() const |
---|
| 1629 | { |
---|
[1286] | 1630 | return new CbcRounding(*this); |
---|
[2] | 1631 | } |
---|
[356] | 1632 | // Create C++ lines to get to current state |
---|
[1286] | 1633 | void |
---|
| 1634 | CbcRounding::generateCpp( FILE * fp) |
---|
[356] | 1635 | { |
---|
[1286] | 1636 | CbcRounding other; |
---|
| 1637 | fprintf(fp, "0#include \"CbcHeuristic.hpp\"\n"); |
---|
| 1638 | fprintf(fp, "3 CbcRounding rounding(*cbcModel);\n"); |
---|
| 1639 | CbcHeuristic::generateCpp(fp, "rounding"); |
---|
| 1640 | if (seed_ != other.seed_) |
---|
| 1641 | fprintf(fp, "3 rounding.setSeed(%d);\n", seed_); |
---|
| 1642 | else |
---|
| 1643 | fprintf(fp, "4 rounding.setSeed(%d);\n", seed_); |
---|
| 1644 | fprintf(fp, "3 cbcModel->addHeuristic(&rounding);\n"); |
---|
[356] | 1645 | } |
---|
[838] | 1646 | //#define NEW_ROUNDING |
---|
[1286] | 1647 | // Copy constructor |
---|
[2] | 1648 | CbcRounding::CbcRounding(const CbcRounding & rhs) |
---|
[1286] | 1649 | : |
---|
| 1650 | CbcHeuristic(rhs), |
---|
| 1651 | matrix_(rhs.matrix_), |
---|
| 1652 | matrixByRow_(rhs.matrixByRow_), |
---|
| 1653 | seed_(rhs.seed_) |
---|
[2] | 1654 | { |
---|
[838] | 1655 | #ifdef NEW_ROUNDING |
---|
[1286] | 1656 | int numberColumns = matrix_.getNumCols(); |
---|
| 1657 | down_ = CoinCopyOfArray(rhs.down_, numberColumns); |
---|
| 1658 | up_ = CoinCopyOfArray(rhs.up_, numberColumns); |
---|
| 1659 | equal_ = CoinCopyOfArray(rhs.equal_, numberColumns); |
---|
[838] | 1660 | #else |
---|
[1286] | 1661 | down_ = NULL; |
---|
| 1662 | up_ = NULL; |
---|
| 1663 | equal_ = NULL; |
---|
| 1664 | #endif |
---|
[2] | 1665 | } |
---|
[6] | 1666 | |
---|
[1286] | 1667 | // Assignment operator |
---|
| 1668 | CbcRounding & |
---|
| 1669 | CbcRounding::operator=( const CbcRounding & rhs) |
---|
[640] | 1670 | { |
---|
[1286] | 1671 | if (this != &rhs) { |
---|
| 1672 | CbcHeuristic::operator=(rhs); |
---|
| 1673 | matrix_ = rhs.matrix_; |
---|
| 1674 | matrixByRow_ = rhs.matrixByRow_; |
---|
[838] | 1675 | #ifdef NEW_ROUNDING |
---|
[1286] | 1676 | delete [] down_; |
---|
| 1677 | delete [] up_; |
---|
| 1678 | delete [] equal_; |
---|
| 1679 | int numberColumns = matrix_.getNumCols(); |
---|
| 1680 | down_ = CoinCopyOfArray(rhs.down_, numberColumns); |
---|
| 1681 | up_ = CoinCopyOfArray(rhs.up_, numberColumns); |
---|
| 1682 | equal_ = CoinCopyOfArray(rhs.equal_, numberColumns); |
---|
[838] | 1683 | #else |
---|
[1286] | 1684 | down_ = NULL; |
---|
| 1685 | up_ = NULL; |
---|
| 1686 | equal_ = NULL; |
---|
| 1687 | #endif |
---|
| 1688 | seed_ = rhs.seed_; |
---|
| 1689 | } |
---|
| 1690 | return *this; |
---|
[640] | 1691 | } |
---|
| 1692 | |
---|
[6] | 1693 | // Resets stuff if model changes |
---|
[1286] | 1694 | void |
---|
[6] | 1695 | CbcRounding::resetModel(CbcModel * model) |
---|
| 1696 | { |
---|
[1286] | 1697 | model_ = model; |
---|
| 1698 | // Get a copy of original matrix (and by row for rounding); |
---|
| 1699 | assert(model_->solver()); |
---|
| 1700 | matrix_ = *model_->solver()->getMatrixByCol(); |
---|
| 1701 | matrixByRow_ = *model_->solver()->getMatrixByRow(); |
---|
| 1702 | validate(); |
---|
[6] | 1703 | } |
---|
[2] | 1704 | // See if rounding will give solution |
---|
| 1705 | // Sets value of solution |
---|
| 1706 | // Assumes rhs for original matrix still okay |
---|
[1286] | 1707 | // At present only works with integers |
---|
[2] | 1708 | // Fix values if asked for |
---|
| 1709 | // Returns 1 if solution, 0 if not |
---|
| 1710 | int |
---|
| 1711 | CbcRounding::solution(double & solutionValue, |
---|
[1286] | 1712 | double * betterSolution) |
---|
[2] | 1713 | { |
---|
| 1714 | |
---|
[1286] | 1715 | numCouldRun_++; |
---|
| 1716 | // See if to do |
---|
| 1717 | if (!when() || (when() % 10 == 1 && model_->phase() != 1) || |
---|
| 1718 | (when() % 10 == 2 && (model_->phase() != 2 && model_->phase() != 3))) |
---|
| 1719 | return 0; // switched off |
---|
| 1720 | numRuns_++; |
---|
| 1721 | OsiSolverInterface * solver = model_->solver(); |
---|
| 1722 | double direction = solver->getObjSense(); |
---|
| 1723 | double newSolutionValue = direction * solver->getObjValue(); |
---|
| 1724 | return solution(solutionValue, betterSolution, newSolutionValue); |
---|
[838] | 1725 | } |
---|
| 1726 | // See if rounding will give solution |
---|
| 1727 | // Sets value of solution |
---|
| 1728 | // Assumes rhs for original matrix still okay |
---|
[1286] | 1729 | // At present only works with integers |
---|
[838] | 1730 | // Fix values if asked for |
---|
| 1731 | // Returns 1 if solution, 0 if not |
---|
| 1732 | int |
---|
| 1733 | CbcRounding::solution(double & solutionValue, |
---|
[1286] | 1734 | double * betterSolution, |
---|
| 1735 | double newSolutionValue) |
---|
[838] | 1736 | { |
---|
| 1737 | |
---|
[1286] | 1738 | // See if to do |
---|
| 1739 | if (!when() || (when() % 10 == 1 && model_->phase() != 1) || |
---|
| 1740 | (when() % 10 == 2 && (model_->phase() != 2 && model_->phase() != 3))) |
---|
| 1741 | return 0; // switched off |
---|
| 1742 | OsiSolverInterface * solver = model_->solver(); |
---|
| 1743 | const double * lower = solver->getColLower(); |
---|
| 1744 | const double * upper = solver->getColUpper(); |
---|
| 1745 | const double * rowLower = solver->getRowLower(); |
---|
| 1746 | const double * rowUpper = solver->getRowUpper(); |
---|
| 1747 | const double * solution = solver->getColSolution(); |
---|
| 1748 | const double * objective = solver->getObjCoefficients(); |
---|
| 1749 | double integerTolerance = model_->getDblParam(CbcModel::CbcIntegerTolerance); |
---|
| 1750 | double primalTolerance; |
---|
| 1751 | solver->getDblParam(OsiPrimalTolerance, primalTolerance); |
---|
[2] | 1752 | |
---|
[1286] | 1753 | int numberRows = matrix_.getNumRows(); |
---|
| 1754 | assert (numberRows <= solver->getNumRows()); |
---|
| 1755 | int numberIntegers = model_->numberIntegers(); |
---|
| 1756 | const int * integerVariable = model_->integerVariable(); |
---|
| 1757 | int i; |
---|
| 1758 | double direction = solver->getObjSense(); |
---|
| 1759 | //double newSolutionValue = direction*solver->getObjValue(); |
---|
| 1760 | int returnCode = 0; |
---|
| 1761 | // Column copy |
---|
| 1762 | const double * element = matrix_.getElements(); |
---|
| 1763 | const int * row = matrix_.getIndices(); |
---|
| 1764 | const CoinBigIndex * columnStart = matrix_.getVectorStarts(); |
---|
| 1765 | const int * columnLength = matrix_.getVectorLengths(); |
---|
| 1766 | // Row copy |
---|
| 1767 | const double * elementByRow = matrixByRow_.getElements(); |
---|
| 1768 | const int * column = matrixByRow_.getIndices(); |
---|
| 1769 | const CoinBigIndex * rowStart = matrixByRow_.getVectorStarts(); |
---|
| 1770 | const int * rowLength = matrixByRow_.getVectorLengths(); |
---|
[2] | 1771 | |
---|
[1286] | 1772 | // Get solution array for heuristic solution |
---|
| 1773 | int numberColumns = solver->getNumCols(); |
---|
| 1774 | double * newSolution = new double [numberColumns]; |
---|
| 1775 | memcpy(newSolution, solution, numberColumns*sizeof(double)); |
---|
[2] | 1776 | |
---|
[1286] | 1777 | double * rowActivity = new double[numberRows]; |
---|
| 1778 | memset(rowActivity, 0, numberRows*sizeof(double)); |
---|
| 1779 | for (i = 0; i < numberColumns; i++) { |
---|
| 1780 | int j; |
---|
| 1781 | double value = newSolution[i]; |
---|
| 1782 | if (value < lower[i]) { |
---|
| 1783 | value = lower[i]; |
---|
| 1784 | newSolution[i] = value; |
---|
| 1785 | } else if (value > upper[i]) { |
---|
| 1786 | value = upper[i]; |
---|
| 1787 | newSolution[i] = value; |
---|
| 1788 | } |
---|
| 1789 | if (value) { |
---|
| 1790 | for (j = columnStart[i]; |
---|
| 1791 | j < columnStart[i] + columnLength[i]; j++) { |
---|
| 1792 | int iRow = row[j]; |
---|
| 1793 | rowActivity[iRow] += value * element[j]; |
---|
| 1794 | } |
---|
| 1795 | } |
---|
[64] | 1796 | } |
---|
[1286] | 1797 | // check was feasible - if not adjust (cleaning may move) |
---|
| 1798 | for (i = 0; i < numberRows; i++) { |
---|
| 1799 | if (rowActivity[i] < rowLower[i]) { |
---|
| 1800 | //assert (rowActivity[i]>rowLower[i]-1000.0*primalTolerance); |
---|
| 1801 | rowActivity[i] = rowLower[i]; |
---|
| 1802 | } else if (rowActivity[i] > rowUpper[i]) { |
---|
| 1803 | //assert (rowActivity[i]<rowUpper[i]+1000.0*primalTolerance); |
---|
| 1804 | rowActivity[i] = rowUpper[i]; |
---|
| 1805 | } |
---|
[2] | 1806 | } |
---|
[1286] | 1807 | for (i = 0; i < numberIntegers; i++) { |
---|
| 1808 | int iColumn = integerVariable[i]; |
---|
| 1809 | double value = newSolution[iColumn]; |
---|
| 1810 | if (fabs(floor(value + 0.5) - value) > integerTolerance) { |
---|
| 1811 | double below = floor(value); |
---|
| 1812 | double newValue = newSolution[iColumn]; |
---|
| 1813 | double cost = direction * objective[iColumn]; |
---|
| 1814 | double move; |
---|
| 1815 | if (cost > 0.0) { |
---|
| 1816 | // try up |
---|
| 1817 | move = 1.0 - (value - below); |
---|
| 1818 | } else if (cost < 0.0) { |
---|
| 1819 | // try down |
---|
| 1820 | move = below - value; |
---|
[91] | 1821 | } else { |
---|
[1286] | 1822 | // won't be able to move unless we can grab another variable |
---|
| 1823 | double randomNumber = randomNumberGenerator_.randomDouble(); |
---|
| 1824 | // which way? |
---|
| 1825 | if (randomNumber < 0.5) |
---|
| 1826 | move = below - value; |
---|
| 1827 | else |
---|
| 1828 | move = 1.0 - (value - below); |
---|
[91] | 1829 | } |
---|
[1286] | 1830 | newValue += move; |
---|
| 1831 | newSolution[iColumn] = newValue; |
---|
| 1832 | newSolutionValue += move * cost; |
---|
| 1833 | int j; |
---|
| 1834 | for (j = columnStart[iColumn]; |
---|
| 1835 | j < columnStart[iColumn] + columnLength[iColumn]; j++) { |
---|
| 1836 | int iRow = row[j]; |
---|
| 1837 | rowActivity[iRow] += move * element[j]; |
---|
[91] | 1838 | } |
---|
| 1839 | } |
---|
[1286] | 1840 | } |
---|
| 1841 | |
---|
| 1842 | double penalty = 0.0; |
---|
| 1843 | const char * integerType = model_->integerType(); |
---|
| 1844 | // see if feasible - just using singletons |
---|
| 1845 | for (i = 0; i < numberRows; i++) { |
---|
| 1846 | double value = rowActivity[i]; |
---|
| 1847 | double thisInfeasibility = 0.0; |
---|
| 1848 | if (value < rowLower[i] - primalTolerance) |
---|
| 1849 | thisInfeasibility = value - rowLower[i]; |
---|
| 1850 | else if (value > rowUpper[i] + primalTolerance) |
---|
| 1851 | thisInfeasibility = value - rowUpper[i]; |
---|
| 1852 | if (thisInfeasibility) { |
---|
| 1853 | // See if there are any slacks I can use to fix up |
---|
| 1854 | // maybe put in coding for multiple slacks? |
---|
| 1855 | double bestCost = 1.0e50; |
---|
| 1856 | int k; |
---|
| 1857 | int iBest = -1; |
---|
| 1858 | double addCost = 0.0; |
---|
| 1859 | double newValue = 0.0; |
---|
| 1860 | double changeRowActivity = 0.0; |
---|
| 1861 | double absInfeasibility = fabs(thisInfeasibility); |
---|
| 1862 | for (k = rowStart[i]; k < rowStart[i] + rowLength[i]; k++) { |
---|
| 1863 | int iColumn = column[k]; |
---|
| 1864 | // See if all elements help |
---|
| 1865 | if (columnLength[iColumn] == 1) { |
---|
| 1866 | double currentValue = newSolution[iColumn]; |
---|
| 1867 | double elementValue = elementByRow[k]; |
---|
| 1868 | double lowerValue = lower[iColumn]; |
---|
| 1869 | double upperValue = upper[iColumn]; |
---|
| 1870 | double gap = rowUpper[i] - rowLower[i]; |
---|
| 1871 | double absElement = fabs(elementValue); |
---|
| 1872 | if (thisInfeasibility*elementValue > 0.0) { |
---|
| 1873 | // we want to reduce |
---|
| 1874 | if ((currentValue - lowerValue)*absElement >= absInfeasibility) { |
---|
| 1875 | // possible - check if integer |
---|
| 1876 | double distance = absInfeasibility / absElement; |
---|
| 1877 | double thisCost = -direction * objective[iColumn] * distance; |
---|
| 1878 | if (integerType[iColumn]) { |
---|
| 1879 | distance = ceil(distance - primalTolerance); |
---|
| 1880 | if (currentValue - distance >= lowerValue - primalTolerance) { |
---|
| 1881 | if (absInfeasibility - distance*absElement < -gap - primalTolerance) |
---|
| 1882 | thisCost = 1.0e100; // no good |
---|
| 1883 | else |
---|
| 1884 | thisCost = -direction * objective[iColumn] * distance; |
---|
| 1885 | } else { |
---|
| 1886 | thisCost = 1.0e100; // no good |
---|
| 1887 | } |
---|
| 1888 | } |
---|
| 1889 | if (thisCost < bestCost) { |
---|
| 1890 | bestCost = thisCost; |
---|
| 1891 | iBest = iColumn; |
---|
| 1892 | addCost = thisCost; |
---|
| 1893 | newValue = currentValue - distance; |
---|
| 1894 | changeRowActivity = -distance * elementValue; |
---|
| 1895 | } |
---|
| 1896 | } |
---|
| 1897 | } else { |
---|
| 1898 | // we want to increase |
---|
| 1899 | if ((upperValue - currentValue)*absElement >= absInfeasibility) { |
---|
| 1900 | // possible - check if integer |
---|
| 1901 | double distance = absInfeasibility / absElement; |
---|
| 1902 | double thisCost = direction * objective[iColumn] * distance; |
---|
| 1903 | if (integerType[iColumn]) { |
---|
| 1904 | distance = ceil(distance - 1.0e-7); |
---|
| 1905 | assert (currentValue - distance <= upperValue + primalTolerance); |
---|
| 1906 | if (absInfeasibility - distance*absElement < -gap - primalTolerance) |
---|
| 1907 | thisCost = 1.0e100; // no good |
---|
| 1908 | else |
---|
| 1909 | thisCost = direction * objective[iColumn] * distance; |
---|
| 1910 | } |
---|
| 1911 | if (thisCost < bestCost) { |
---|
| 1912 | bestCost = thisCost; |
---|
| 1913 | iBest = iColumn; |
---|
| 1914 | addCost = thisCost; |
---|
| 1915 | newValue = currentValue + distance; |
---|
| 1916 | changeRowActivity = distance * elementValue; |
---|
| 1917 | } |
---|
| 1918 | } |
---|
| 1919 | } |
---|
| 1920 | } |
---|
[91] | 1921 | } |
---|
[1286] | 1922 | if (iBest >= 0) { |
---|
| 1923 | /*printf("Infeasibility of %g on row %d cost %g\n", |
---|
| 1924 | thisInfeasibility,i,addCost);*/ |
---|
| 1925 | newSolution[iBest] = newValue; |
---|
| 1926 | thisInfeasibility = 0.0; |
---|
| 1927 | newSolutionValue += addCost; |
---|
| 1928 | rowActivity[i] += changeRowActivity; |
---|
| 1929 | } |
---|
| 1930 | penalty += fabs(thisInfeasibility); |
---|
[91] | 1931 | } |
---|
| 1932 | } |
---|
[1286] | 1933 | if (penalty) { |
---|
| 1934 | // see if feasible using any |
---|
| 1935 | // first continuous |
---|
| 1936 | double penaltyChange = 0.0; |
---|
| 1937 | int iColumn; |
---|
| 1938 | for (iColumn = 0; iColumn < numberColumns; iColumn++) { |
---|
| 1939 | if (integerType[iColumn]) |
---|
| 1940 | continue; |
---|
| 1941 | double currentValue = newSolution[iColumn]; |
---|
| 1942 | double lowerValue = lower[iColumn]; |
---|
| 1943 | double upperValue = upper[iColumn]; |
---|
| 1944 | int j; |
---|
| 1945 | int anyBadDown = 0; |
---|
| 1946 | int anyBadUp = 0; |
---|
| 1947 | double upImprovement = 0.0; |
---|
| 1948 | double downImprovement = 0.0; |
---|
| 1949 | for (j = columnStart[iColumn]; |
---|
| 1950 | j < columnStart[iColumn] + columnLength[iColumn]; j++) { |
---|
| 1951 | int iRow = row[j]; |
---|
| 1952 | if (rowUpper[iRow] > rowLower[iRow]) { |
---|
| 1953 | double value = element[j]; |
---|
| 1954 | if (rowActivity[iRow] > rowUpper[iRow] + primalTolerance) { |
---|
| 1955 | // infeasible above |
---|
| 1956 | downImprovement += value; |
---|
| 1957 | upImprovement -= value; |
---|
| 1958 | if (value > 0.0) |
---|
| 1959 | anyBadUp++; |
---|
| 1960 | else |
---|
| 1961 | anyBadDown++; |
---|
| 1962 | } else if (rowActivity[iRow] > rowUpper[iRow] - primalTolerance) { |
---|
| 1963 | // feasible at ub |
---|
| 1964 | if (value > 0.0) { |
---|
| 1965 | upImprovement -= value; |
---|
| 1966 | anyBadUp++; |
---|
| 1967 | } else { |
---|
| 1968 | downImprovement += value; |
---|
| 1969 | anyBadDown++; |
---|
| 1970 | } |
---|
| 1971 | } else if (rowActivity[iRow] > rowLower[iRow] + primalTolerance) { |
---|
| 1972 | // feasible in interior |
---|
| 1973 | } else if (rowActivity[iRow] > rowLower[iRow] - primalTolerance) { |
---|
| 1974 | // feasible at lb |
---|
| 1975 | if (value < 0.0) { |
---|
| 1976 | upImprovement += value; |
---|
| 1977 | anyBadUp++; |
---|
| 1978 | } else { |
---|
| 1979 | downImprovement -= value; |
---|
| 1980 | anyBadDown++; |
---|
| 1981 | } |
---|
| 1982 | } else { |
---|
| 1983 | // infeasible below |
---|
| 1984 | downImprovement -= value; |
---|
| 1985 | upImprovement += value; |
---|
| 1986 | if (value < 0.0) |
---|
| 1987 | anyBadUp++; |
---|
| 1988 | else |
---|
| 1989 | anyBadDown++; |
---|
| 1990 | } |
---|
| 1991 | } else { |
---|
| 1992 | // equality row |
---|
| 1993 | double value = element[j]; |
---|
| 1994 | if (rowActivity[iRow] > rowUpper[iRow] + primalTolerance) { |
---|
| 1995 | // infeasible above |
---|
| 1996 | downImprovement += value; |
---|
| 1997 | upImprovement -= value; |
---|
| 1998 | if (value > 0.0) |
---|
| 1999 | anyBadUp++; |
---|
| 2000 | else |
---|
| 2001 | anyBadDown++; |
---|
| 2002 | } else if (rowActivity[iRow] < rowLower[iRow] - primalTolerance) { |
---|
| 2003 | // infeasible below |
---|
| 2004 | downImprovement -= value; |
---|
| 2005 | upImprovement += value; |
---|
| 2006 | if (value < 0.0) |
---|
| 2007 | anyBadUp++; |
---|
| 2008 | else |
---|
| 2009 | anyBadDown++; |
---|
| 2010 | } else { |
---|
| 2011 | // feasible - no good |
---|
| 2012 | anyBadUp = -1; |
---|
| 2013 | anyBadDown = -1; |
---|
| 2014 | break; |
---|
| 2015 | } |
---|
| 2016 | } |
---|
[91] | 2017 | } |
---|
[1286] | 2018 | // could change tests for anyBad |
---|
| 2019 | if (anyBadUp) |
---|
| 2020 | upImprovement = 0.0; |
---|
| 2021 | if (anyBadDown) |
---|
| 2022 | downImprovement = 0.0; |
---|
| 2023 | double way = 0.0; |
---|
| 2024 | double improvement = 0.0; |
---|
| 2025 | if (downImprovement > 0.0 && currentValue > lowerValue) { |
---|
| 2026 | way = -1.0; |
---|
| 2027 | improvement = downImprovement; |
---|
| 2028 | } else if (upImprovement > 0.0 && currentValue < upperValue) { |
---|
| 2029 | way = 1.0; |
---|
| 2030 | improvement = upImprovement; |
---|
[91] | 2031 | } |
---|
[1286] | 2032 | if (way) { |
---|
| 2033 | // can improve |
---|
| 2034 | double distance; |
---|
| 2035 | if (way > 0.0) |
---|
| 2036 | distance = upperValue - currentValue; |
---|
| 2037 | else |
---|
| 2038 | distance = currentValue - lowerValue; |
---|
| 2039 | for (j = columnStart[iColumn]; |
---|
| 2040 | j < columnStart[iColumn] + columnLength[iColumn]; j++) { |
---|
| 2041 | int iRow = row[j]; |
---|
| 2042 | double value = element[j] * way; |
---|
| 2043 | if (rowActivity[iRow] > rowUpper[iRow] + primalTolerance) { |
---|
| 2044 | // infeasible above |
---|
| 2045 | assert (value < 0.0); |
---|
| 2046 | double gap = rowActivity[iRow] - rowUpper[iRow]; |
---|
| 2047 | if (gap + value*distance < 0.0) |
---|
| 2048 | distance = -gap / value; |
---|
| 2049 | } else if (rowActivity[iRow] < rowLower[iRow] - primalTolerance) { |
---|
| 2050 | // infeasible below |
---|
| 2051 | assert (value > 0.0); |
---|
| 2052 | double gap = rowActivity[iRow] - rowLower[iRow]; |
---|
| 2053 | if (gap + value*distance > 0.0) |
---|
| 2054 | distance = -gap / value; |
---|
| 2055 | } else { |
---|
| 2056 | // feasible |
---|
| 2057 | if (value > 0) { |
---|
| 2058 | double gap = rowActivity[iRow] - rowUpper[iRow]; |
---|
| 2059 | if (gap + value*distance > 0.0) |
---|
| 2060 | distance = -gap / value; |
---|
| 2061 | } else { |
---|
| 2062 | double gap = rowActivity[iRow] - rowLower[iRow]; |
---|
| 2063 | if (gap + value*distance < 0.0) |
---|
| 2064 | distance = -gap / value; |
---|
| 2065 | } |
---|
| 2066 | } |
---|
| 2067 | } |
---|
| 2068 | //move |
---|
| 2069 | penaltyChange += improvement * distance; |
---|
| 2070 | distance *= way; |
---|
| 2071 | newSolution[iColumn] += distance; |
---|
| 2072 | newSolutionValue += direction * objective[iColumn] * distance; |
---|
| 2073 | for (j = columnStart[iColumn]; |
---|
| 2074 | j < columnStart[iColumn] + columnLength[iColumn]; j++) { |
---|
| 2075 | int iRow = row[j]; |
---|
| 2076 | double value = element[j]; |
---|
| 2077 | rowActivity[iRow] += distance * value; |
---|
| 2078 | } |
---|
[91] | 2079 | } |
---|
| 2080 | } |
---|
[1286] | 2081 | // and now all if improving |
---|
| 2082 | double lastChange = penaltyChange ? 1.0 : 0.0; |
---|
| 2083 | while (lastChange > 1.0e-2) { |
---|
| 2084 | lastChange = 0; |
---|
| 2085 | for (iColumn = 0; iColumn < numberColumns; iColumn++) { |
---|
| 2086 | bool isInteger = (integerType[iColumn] != 0); |
---|
| 2087 | double currentValue = newSolution[iColumn]; |
---|
| 2088 | double lowerValue = lower[iColumn]; |
---|
| 2089 | double upperValue = upper[iColumn]; |
---|
| 2090 | int j; |
---|
| 2091 | int anyBadDown = 0; |
---|
| 2092 | int anyBadUp = 0; |
---|
| 2093 | double upImprovement = 0.0; |
---|
| 2094 | double downImprovement = 0.0; |
---|
| 2095 | for (j = columnStart[iColumn]; |
---|
| 2096 | j < columnStart[iColumn] + columnLength[iColumn]; j++) { |
---|
| 2097 | int iRow = row[j]; |
---|
| 2098 | double value = element[j]; |
---|
| 2099 | if (isInteger) { |
---|
| 2100 | if (value > 0.0) { |
---|
| 2101 | if (rowActivity[iRow] + value > rowUpper[iRow] + primalTolerance) |
---|
| 2102 | anyBadUp++; |
---|
| 2103 | if (rowActivity[iRow] - value < rowLower[iRow] - primalTolerance) |
---|
| 2104 | anyBadDown++; |
---|
| 2105 | } else { |
---|
| 2106 | if (rowActivity[iRow] - value > rowUpper[iRow] + primalTolerance) |
---|
| 2107 | anyBadDown++; |
---|
| 2108 | if (rowActivity[iRow] + value < rowLower[iRow] - primalTolerance) |
---|
| 2109 | anyBadUp++; |
---|
| 2110 | } |
---|
| 2111 | } |
---|
| 2112 | if (rowUpper[iRow] > rowLower[iRow]) { |
---|
| 2113 | if (rowActivity[iRow] > rowUpper[iRow] + primalTolerance) { |
---|
| 2114 | // infeasible above |
---|
| 2115 | downImprovement += value; |
---|
| 2116 | upImprovement -= value; |
---|
| 2117 | if (value > 0.0) |
---|
| 2118 | anyBadUp++; |
---|
| 2119 | else |
---|
| 2120 | anyBadDown++; |
---|
| 2121 | } else if (rowActivity[iRow] > rowUpper[iRow] - primalTolerance) { |
---|
| 2122 | // feasible at ub |
---|
| 2123 | if (value > 0.0) { |
---|
| 2124 | upImprovement -= value; |
---|
| 2125 | anyBadUp++; |
---|
| 2126 | } else { |
---|
| 2127 | downImprovement += value; |
---|
| 2128 | anyBadDown++; |
---|
| 2129 | } |
---|
| 2130 | } else if (rowActivity[iRow] > rowLower[iRow] + primalTolerance) { |
---|
| 2131 | // feasible in interior |
---|
| 2132 | } else if (rowActivity[iRow] > rowLower[iRow] - primalTolerance) { |
---|
| 2133 | // feasible at lb |
---|
| 2134 | if (value < 0.0) { |
---|
| 2135 | upImprovement += value; |
---|
| 2136 | anyBadUp++; |
---|
| 2137 | } else { |
---|
| 2138 | downImprovement -= value; |
---|
| 2139 | anyBadDown++; |
---|
| 2140 | } |
---|
| 2141 | } else { |
---|
| 2142 | // infeasible below |
---|
| 2143 | downImprovement -= value; |
---|
| 2144 | upImprovement += value; |
---|
| 2145 | if (value < 0.0) |
---|
| 2146 | anyBadUp++; |
---|
| 2147 | else |
---|
| 2148 | anyBadDown++; |
---|
| 2149 | } |
---|
| 2150 | } else { |
---|
| 2151 | // equality row |
---|
| 2152 | if (rowActivity[iRow] > rowUpper[iRow] + primalTolerance) { |
---|
| 2153 | // infeasible above |
---|
| 2154 | downImprovement += value; |
---|
| 2155 | upImprovement -= value; |
---|
| 2156 | if (value > 0.0) |
---|
| 2157 | anyBadUp++; |
---|
| 2158 | else |
---|
| 2159 | anyBadDown++; |
---|
| 2160 | } else if (rowActivity[iRow] < rowLower[iRow] - primalTolerance) { |
---|
| 2161 | // infeasible below |
---|
| 2162 | downImprovement -= value; |
---|
| 2163 | upImprovement += value; |
---|
| 2164 | if (value < 0.0) |
---|
| 2165 | anyBadUp++; |
---|
| 2166 | else |
---|
| 2167 | anyBadDown++; |
---|
| 2168 | } else { |
---|
| 2169 | // feasible - no good |
---|
| 2170 | anyBadUp = -1; |
---|
| 2171 | anyBadDown = -1; |
---|
| 2172 | break; |
---|
| 2173 | } |
---|
| 2174 | } |
---|
| 2175 | } |
---|
| 2176 | // could change tests for anyBad |
---|
| 2177 | if (anyBadUp) |
---|
| 2178 | upImprovement = 0.0; |
---|
| 2179 | if (anyBadDown) |
---|
| 2180 | downImprovement = 0.0; |
---|
| 2181 | double way = 0.0; |
---|
| 2182 | double improvement = 0.0; |
---|
| 2183 | if (downImprovement > 0.0 && currentValue > lowerValue) { |
---|
| 2184 | way = -1.0; |
---|
| 2185 | improvement = downImprovement; |
---|
| 2186 | } else if (upImprovement > 0.0 && currentValue < upperValue) { |
---|
| 2187 | way = 1.0; |
---|
| 2188 | improvement = upImprovement; |
---|
| 2189 | } |
---|
| 2190 | if (way) { |
---|
| 2191 | // can improve |
---|
| 2192 | double distance = COIN_DBL_MAX; |
---|
| 2193 | for (j = columnStart[iColumn]; |
---|
| 2194 | j < columnStart[iColumn] + columnLength[iColumn]; j++) { |
---|
| 2195 | int iRow = row[j]; |
---|
| 2196 | double value = element[j] * way; |
---|
| 2197 | if (rowActivity[iRow] > rowUpper[iRow] + primalTolerance) { |
---|
| 2198 | // infeasible above |
---|
| 2199 | assert (value < 0.0); |
---|
| 2200 | double gap = rowActivity[iRow] - rowUpper[iRow]; |
---|
| 2201 | if (gap + value*distance < 0.0) { |
---|
| 2202 | // If integer then has to move by 1 |
---|
| 2203 | if (!isInteger) |
---|
| 2204 | distance = -gap / value; |
---|
| 2205 | else |
---|
| 2206 | distance = CoinMax(-gap / value, 1.0); |
---|
| 2207 | } |
---|
| 2208 | } else if (rowActivity[iRow] < rowLower[iRow] - primalTolerance) { |
---|
| 2209 | // infeasible below |
---|
| 2210 | assert (value > 0.0); |
---|
| 2211 | double gap = rowActivity[iRow] - rowLower[iRow]; |
---|
| 2212 | if (gap + value*distance > 0.0) { |
---|
| 2213 | // If integer then has to move by 1 |
---|
| 2214 | if (!isInteger) |
---|
| 2215 | distance = -gap / value; |
---|
| 2216 | else |
---|
| 2217 | distance = CoinMax(-gap / value, 1.0); |
---|
| 2218 | } |
---|
| 2219 | } else { |
---|
| 2220 | // feasible |
---|
| 2221 | if (value > 0) { |
---|
| 2222 | double gap = rowActivity[iRow] - rowUpper[iRow]; |
---|
| 2223 | if (gap + value*distance > 0.0) |
---|
| 2224 | distance = -gap / value; |
---|
| 2225 | } else { |
---|
| 2226 | double gap = rowActivity[iRow] - rowLower[iRow]; |
---|
| 2227 | if (gap + value*distance < 0.0) |
---|
| 2228 | distance = -gap / value; |
---|
| 2229 | } |
---|
| 2230 | } |
---|
| 2231 | } |
---|
| 2232 | if (isInteger) |
---|
| 2233 | distance = floor(distance + 1.05e-8); |
---|
| 2234 | if (!distance) { |
---|
| 2235 | // should never happen |
---|
| 2236 | //printf("zero distance in CbcRounding - debug\n"); |
---|
| 2237 | } |
---|
| 2238 | //move |
---|
| 2239 | lastChange += improvement * distance; |
---|
| 2240 | distance *= way; |
---|
| 2241 | newSolution[iColumn] += distance; |
---|
| 2242 | newSolutionValue += direction * objective[iColumn] * distance; |
---|
| 2243 | for (j = columnStart[iColumn]; |
---|
| 2244 | j < columnStart[iColumn] + columnLength[iColumn]; j++) { |
---|
| 2245 | int iRow = row[j]; |
---|
| 2246 | double value = element[j]; |
---|
| 2247 | rowActivity[iRow] += distance * value; |
---|
| 2248 | } |
---|
| 2249 | } |
---|
| 2250 | } |
---|
| 2251 | penaltyChange += lastChange; |
---|
[91] | 2252 | } |
---|
[1286] | 2253 | penalty -= penaltyChange; |
---|
| 2254 | if (penalty < 1.0e-5*fabs(penaltyChange)) { |
---|
| 2255 | // recompute |
---|
| 2256 | penalty = 0.0; |
---|
| 2257 | for (i = 0; i < numberRows; i++) { |
---|
| 2258 | double value = rowActivity[i]; |
---|
| 2259 | if (value < rowLower[i] - primalTolerance) |
---|
| 2260 | penalty += rowLower[i] - value; |
---|
| 2261 | else if (value > rowUpper[i] + primalTolerance) |
---|
| 2262 | penalty += value - rowUpper[i]; |
---|
[91] | 2263 | } |
---|
| 2264 | } |
---|
| 2265 | } |
---|
[2] | 2266 | |
---|
[1286] | 2267 | // Could also set SOS (using random) and repeat |
---|
| 2268 | if (!penalty) { |
---|
| 2269 | // See if we can do better |
---|
| 2270 | //seed_++; |
---|
| 2271 | //CoinSeedRandom(seed_); |
---|
| 2272 | // Random number between 0 and 1. |
---|
| 2273 | double randomNumber = randomNumberGenerator_.randomDouble(); |
---|
| 2274 | int iPass; |
---|
| 2275 | int start[2]; |
---|
| 2276 | int end[2]; |
---|
| 2277 | int iRandom = static_cast<int> (randomNumber * (static_cast<double> (numberIntegers))); |
---|
| 2278 | start[0] = iRandom; |
---|
| 2279 | end[0] = numberIntegers; |
---|
| 2280 | start[1] = 0; |
---|
| 2281 | end[1] = iRandom; |
---|
| 2282 | for (iPass = 0; iPass < 2; iPass++) { |
---|
| 2283 | int i; |
---|
| 2284 | for (i = start[iPass]; i < end[iPass]; i++) { |
---|
| 2285 | int iColumn = integerVariable[i]; |
---|
[201] | 2286 | #ifndef NDEBUG |
---|
[1286] | 2287 | double value = newSolution[iColumn]; |
---|
| 2288 | assert (fabs(floor(value + 0.5) - value) < integerTolerance); |
---|
[201] | 2289 | #endif |
---|
[1286] | 2290 | double cost = direction * objective[iColumn]; |
---|
| 2291 | double move = 0.0; |
---|
| 2292 | if (cost > 0.0) |
---|
| 2293 | move = -1.0; |
---|
| 2294 | else if (cost < 0.0) |
---|
| 2295 | move = 1.0; |
---|
| 2296 | while (move) { |
---|
| 2297 | bool good = true; |
---|
| 2298 | double newValue = newSolution[iColumn] + move; |
---|
| 2299 | if (newValue < lower[iColumn] - primalTolerance || |
---|
| 2300 | newValue > upper[iColumn] + primalTolerance) { |
---|
| 2301 | move = 0.0; |
---|
| 2302 | } else { |
---|
| 2303 | // see if we can move |
---|
| 2304 | int j; |
---|
| 2305 | for (j = columnStart[iColumn]; |
---|
| 2306 | j < columnStart[iColumn] + columnLength[iColumn]; j++) { |
---|
| 2307 | int iRow = row[j]; |
---|
| 2308 | double newActivity = rowActivity[iRow] + move * element[j]; |
---|
| 2309 | if (newActivity < rowLower[iRow] - primalTolerance || |
---|
| 2310 | newActivity > rowUpper[iRow] + primalTolerance) { |
---|
| 2311 | good = false; |
---|
| 2312 | break; |
---|
| 2313 | } |
---|
| 2314 | } |
---|
| 2315 | if (good) { |
---|
| 2316 | newSolution[iColumn] = newValue; |
---|
| 2317 | newSolutionValue += move * cost; |
---|
| 2318 | int j; |
---|
| 2319 | for (j = columnStart[iColumn]; |
---|
| 2320 | j < columnStart[iColumn] + columnLength[iColumn]; j++) { |
---|
| 2321 | int iRow = row[j]; |
---|
| 2322 | rowActivity[iRow] += move * element[j]; |
---|
| 2323 | } |
---|
| 2324 | } else { |
---|
| 2325 | move = 0.0; |
---|
| 2326 | } |
---|
| 2327 | } |
---|
| 2328 | } |
---|
| 2329 | } |
---|
| 2330 | } |
---|
| 2331 | // Just in case of some stupidity |
---|
| 2332 | double objOffset = 0.0; |
---|
| 2333 | solver->getDblParam(OsiObjOffset, objOffset); |
---|
| 2334 | newSolutionValue = -objOffset; |
---|
| 2335 | for ( i = 0 ; i < numberColumns ; i++ ) |
---|
| 2336 | newSolutionValue += objective[i] * newSolution[i]; |
---|
| 2337 | newSolutionValue *= direction; |
---|
| 2338 | //printf("new solution value %g %g\n",newSolutionValue,solutionValue); |
---|
| 2339 | if (newSolutionValue < solutionValue) { |
---|
| 2340 | // paranoid check |
---|
| 2341 | memset(rowActivity, 0, numberRows*sizeof(double)); |
---|
| 2342 | for (i = 0; i < numberColumns; i++) { |
---|
| 2343 | int j; |
---|
| 2344 | double value = newSolution[i]; |
---|
| 2345 | if (value) { |
---|
| 2346 | for (j = columnStart[i]; |
---|
| 2347 | j < columnStart[i] + columnLength[i]; j++) { |
---|
| 2348 | int iRow = row[j]; |
---|
| 2349 | rowActivity[iRow] += value * element[j]; |
---|
| 2350 | } |
---|
| 2351 | } |
---|
| 2352 | } |
---|
| 2353 | // check was approximately feasible |
---|
| 2354 | bool feasible = true; |
---|
| 2355 | for (i = 0; i < numberRows; i++) { |
---|
| 2356 | if (rowActivity[i] < rowLower[i]) { |
---|
| 2357 | if (rowActivity[i] < rowLower[i] - 1000.0*primalTolerance) |
---|
| 2358 | feasible = false; |
---|
| 2359 | } else if (rowActivity[i] > rowUpper[i]) { |
---|
| 2360 | if (rowActivity[i] > rowUpper[i] + 1000.0*primalTolerance) |
---|
| 2361 | feasible = false; |
---|
| 2362 | } |
---|
| 2363 | } |
---|
| 2364 | if (feasible) { |
---|
| 2365 | // new solution |
---|
| 2366 | memcpy(betterSolution, newSolution, numberColumns*sizeof(double)); |
---|
| 2367 | solutionValue = newSolutionValue; |
---|
| 2368 | //printf("** Solution of %g found by rounding\n",newSolutionValue); |
---|
| 2369 | returnCode = 1; |
---|
| 2370 | } else { |
---|
| 2371 | // Can easily happen |
---|
| 2372 | //printf("Debug CbcRounding giving bad solution\n"); |
---|
| 2373 | } |
---|
| 2374 | } |
---|
[2] | 2375 | } |
---|
[838] | 2376 | #ifdef NEW_ROUNDING |
---|
[1286] | 2377 | if (!returnCode) { |
---|
[1393] | 2378 | #ifdef JJF_ZERO |
---|
[1286] | 2379 | // back to starting point |
---|
| 2380 | memcpy(newSolution, solution, numberColumns*sizeof(double)); |
---|
| 2381 | memset(rowActivity, 0, numberRows*sizeof(double)); |
---|
| 2382 | for (i = 0; i < numberColumns; i++) { |
---|
| 2383 | int j; |
---|
| 2384 | double value = newSolution[i]; |
---|
| 2385 | if (value < lower[i]) { |
---|
| 2386 | value = lower[i]; |
---|
| 2387 | newSolution[i] = value; |
---|
| 2388 | } else if (value > upper[i]) { |
---|
| 2389 | value = upper[i]; |
---|
| 2390 | newSolution[i] = value; |
---|
| 2391 | } |
---|
| 2392 | if (value) { |
---|
| 2393 | for (j = columnStart[i]; |
---|
| 2394 | j < columnStart[i] + columnLength[i]; j++) { |
---|
| 2395 | int iRow = row[j]; |
---|
| 2396 | rowActivity[iRow] += value * element[j]; |
---|
| 2397 | } |
---|
| 2398 | } |
---|
| 2399 | } |
---|
| 2400 | // check was feasible - if not adjust (cleaning may move) |
---|
| 2401 | for (i = 0; i < numberRows; i++) { |
---|
| 2402 | if (rowActivity[i] < rowLower[i]) { |
---|
| 2403 | //assert (rowActivity[i]>rowLower[i]-1000.0*primalTolerance); |
---|
| 2404 | rowActivity[i] = rowLower[i]; |
---|
| 2405 | } else if (rowActivity[i] > rowUpper[i]) { |
---|
| 2406 | //assert (rowActivity[i]<rowUpper[i]+1000.0*primalTolerance); |
---|
| 2407 | rowActivity[i] = rowUpper[i]; |
---|
| 2408 | } |
---|
| 2409 | } |
---|
[838] | 2410 | #endif |
---|
[1286] | 2411 | int * candidate = new int [numberColumns]; |
---|
| 2412 | int nCandidate = 0; |
---|
| 2413 | for (iColumn = 0; iColumn < numberColumns; iColumn++) { |
---|
| 2414 | bool isInteger = (integerType[iColumn] != 0); |
---|
| 2415 | if (isInteger) { |
---|
| 2416 | double currentValue = newSolution[iColumn]; |
---|
| 2417 | if (fabs(currentValue - floor(currentValue + 0.5)) > 1.0e-8) |
---|
| 2418 | candidate[nCandidate++] = iColumn; |
---|
| 2419 | } |
---|
| 2420 | } |
---|
| 2421 | if (true) { |
---|
| 2422 | // Rounding as in Berthold |
---|
| 2423 | while (nCandidate) { |
---|
| 2424 | double infeasibility = 1.0e-7; |
---|
| 2425 | int iRow = -1; |
---|
| 2426 | for (i = 0; i < numberRows; i++) { |
---|
| 2427 | double value = 0.0; |
---|
| 2428 | if (rowActivity[i] < rowLower[i]) { |
---|
| 2429 | value = rowLower[i] - rowActivity[i]; |
---|
| 2430 | } else if (rowActivity[i] > rowUpper[i]) { |
---|
| 2431 | value = rowActivity[i] - rowUpper[i]; |
---|
| 2432 | } |
---|
| 2433 | if (value > infeasibility) { |
---|
| 2434 | infeasibility = value; |
---|
| 2435 | iRow = i; |
---|
| 2436 | } |
---|
| 2437 | } |
---|
| 2438 | if (iRow >= 0) { |
---|
| 2439 | // infeasible |
---|
| 2440 | } else { |
---|
| 2441 | // feasible |
---|
| 2442 | } |
---|
| 2443 | } |
---|
| 2444 | } else { |
---|
| 2445 | // Shifting as in Berthold |
---|
| 2446 | } |
---|
| 2447 | delete [] candidate; |
---|
[838] | 2448 | } |
---|
| 2449 | #endif |
---|
[1286] | 2450 | delete [] newSolution; |
---|
| 2451 | delete [] rowActivity; |
---|
| 2452 | return returnCode; |
---|
[2] | 2453 | } |
---|
| 2454 | // update model |
---|
| 2455 | void CbcRounding::setModel(CbcModel * model) |
---|
| 2456 | { |
---|
[1286] | 2457 | model_ = model; |
---|
| 2458 | // Get a copy of original matrix (and by row for rounding); |
---|
| 2459 | assert(model_->solver()); |
---|
| 2460 | if (model_->solver()->getNumRows()) { |
---|
| 2461 | matrix_ = *model_->solver()->getMatrixByCol(); |
---|
| 2462 | matrixByRow_ = *model_->solver()->getMatrixByRow(); |
---|
| 2463 | // make sure model okay for heuristic |
---|
| 2464 | validate(); |
---|
| 2465 | } |
---|
[2] | 2466 | } |
---|
[72] | 2467 | // Validate model i.e. sets when_ to 0 if necessary (may be NULL) |
---|
[1286] | 2468 | void |
---|
| 2469 | CbcRounding::validate() |
---|
[72] | 2470 | { |
---|
[1286] | 2471 | if (model_ && (when() % 100) < 10) { |
---|
| 2472 | if (model_->numberIntegers() != |
---|
| 2473 | model_->numberObjects() && (model_->numberObjects() || |
---|
| 2474 | (model_->specialOptions()&1024) == 0)) { |
---|
| 2475 | int numberOdd = 0; |
---|
| 2476 | for (int i = 0; i < model_->numberObjects(); i++) { |
---|
| 2477 | if (!model_->object(i)->canDoHeuristics()) |
---|
| 2478 | numberOdd++; |
---|
| 2479 | } |
---|
| 2480 | if (numberOdd) |
---|
| 2481 | setWhen(0); |
---|
| 2482 | } |
---|
[1271] | 2483 | } |
---|
[838] | 2484 | #ifdef NEW_ROUNDING |
---|
[1286] | 2485 | int numberColumns = matrix_.getNumCols(); |
---|
| 2486 | down_ = new unsigned short [numberColumns]; |
---|
| 2487 | up_ = new unsigned short [numberColumns]; |
---|
| 2488 | equal_ = new unsigned short [numberColumns]; |
---|
| 2489 | // Column copy |
---|
| 2490 | const double * element = matrix_.getElements(); |
---|
| 2491 | const int * row = matrix_.getIndices(); |
---|
| 2492 | const CoinBigIndex * columnStart = matrix_.getVectorStarts(); |
---|
| 2493 | const int * columnLength = matrix_.getVectorLengths(); |
---|
| 2494 | const double * rowLower = model.solver()->getRowLower(); |
---|
| 2495 | const double * rowUpper = model.solver()->getRowUpper(); |
---|
| 2496 | for (int i = 0; i < numberColumns; i++) { |
---|
| 2497 | int down = 0; |
---|
| 2498 | int up = 0; |
---|
| 2499 | int equal = 0; |
---|
| 2500 | if (columnLength[i] > 65535) { |
---|
| 2501 | equal[0] = 65535; |
---|
| 2502 | break; // unlikely to work |
---|
| 2503 | } |
---|
| 2504 | for (CoinBigIndex j = columnStart[i]; |
---|
| 2505 | j < columnStart[i] + columnLength[i]; j++) { |
---|
| 2506 | int iRow = row[j]; |
---|
| 2507 | if (rowLower[iRow] > -1.0e20 && rowUpper[iRow] < 1.0e20) { |
---|
| 2508 | equal++; |
---|
| 2509 | } else if (element[j] > 0.0) { |
---|
| 2510 | if (rowUpper[iRow] < 1.0e20) |
---|
| 2511 | up++; |
---|
| 2512 | else |
---|
| 2513 | down--; |
---|
| 2514 | } else { |
---|
| 2515 | if (rowLower[iRow] > -1.0e20) |
---|
| 2516 | up++; |
---|
| 2517 | else |
---|
| 2518 | down--; |
---|
| 2519 | } |
---|
| 2520 | } |
---|
| 2521 | down_[i] = (unsigned short) down; |
---|
| 2522 | up_[i] = (unsigned short) up; |
---|
| 2523 | equal_[i] = (unsigned short) equal; |
---|
[838] | 2524 | } |
---|
| 2525 | #else |
---|
[1286] | 2526 | down_ = NULL; |
---|
| 2527 | up_ = NULL; |
---|
| 2528 | equal_ = NULL; |
---|
| 2529 | #endif |
---|
[72] | 2530 | } |
---|
[2] | 2531 | |
---|
[264] | 2532 | // Default Constructor |
---|
[1286] | 2533 | CbcHeuristicPartial::CbcHeuristicPartial() |
---|
| 2534 | : CbcHeuristic() |
---|
[854] | 2535 | { |
---|
[1286] | 2536 | fixPriority_ = 10000; |
---|
[854] | 2537 | } |
---|
| 2538 | |
---|
| 2539 | // Constructor from model |
---|
| 2540 | CbcHeuristicPartial::CbcHeuristicPartial(CbcModel & model, int fixPriority, int numberNodes) |
---|
[1286] | 2541 | : CbcHeuristic(model) |
---|
[854] | 2542 | { |
---|
[1286] | 2543 | fixPriority_ = fixPriority; |
---|
| 2544 | setNumberNodes(numberNodes); |
---|
| 2545 | validate(); |
---|
[854] | 2546 | } |
---|
| 2547 | |
---|
[1286] | 2548 | // Destructor |
---|
[854] | 2549 | CbcHeuristicPartial::~CbcHeuristicPartial () |
---|
| 2550 | { |
---|
| 2551 | } |
---|
| 2552 | |
---|
| 2553 | // Clone |
---|
| 2554 | CbcHeuristic * |
---|
| 2555 | CbcHeuristicPartial::clone() const |
---|
| 2556 | { |
---|
[1286] | 2557 | return new CbcHeuristicPartial(*this); |
---|
[854] | 2558 | } |
---|
| 2559 | // Create C++ lines to get to current state |
---|
[1286] | 2560 | void |
---|
| 2561 | CbcHeuristicPartial::generateCpp( FILE * fp) |
---|
[854] | 2562 | { |
---|
[1286] | 2563 | CbcHeuristicPartial other; |
---|
| 2564 | fprintf(fp, "0#include \"CbcHeuristic.hpp\"\n"); |
---|
| 2565 | fprintf(fp, "3 CbcHeuristicPartial partial(*cbcModel);\n"); |
---|
| 2566 | CbcHeuristic::generateCpp(fp, "partial"); |
---|
| 2567 | if (fixPriority_ != other.fixPriority_) |
---|
| 2568 | fprintf(fp, "3 partial.setFixPriority(%d);\n", fixPriority_); |
---|
| 2569 | else |
---|
| 2570 | fprintf(fp, "4 partial.setFixPriority(%d);\n", fixPriority_); |
---|
| 2571 | fprintf(fp, "3 cbcModel->addHeuristic(&partial);\n"); |
---|
[854] | 2572 | } |
---|
| 2573 | //#define NEW_PARTIAL |
---|
[1286] | 2574 | // Copy constructor |
---|
[854] | 2575 | CbcHeuristicPartial::CbcHeuristicPartial(const CbcHeuristicPartial & rhs) |
---|
[1286] | 2576 | : |
---|
| 2577 | CbcHeuristic(rhs), |
---|
| 2578 | fixPriority_(rhs.fixPriority_) |
---|
[854] | 2579 | { |
---|
| 2580 | } |
---|
| 2581 | |
---|
[1286] | 2582 | // Assignment operator |
---|
| 2583 | CbcHeuristicPartial & |
---|
| 2584 | CbcHeuristicPartial::operator=( const CbcHeuristicPartial & rhs) |
---|
[854] | 2585 | { |
---|
[1286] | 2586 | if (this != &rhs) { |
---|
| 2587 | CbcHeuristic::operator=(rhs); |
---|
| 2588 | fixPriority_ = rhs.fixPriority_; |
---|
| 2589 | } |
---|
| 2590 | return *this; |
---|
[854] | 2591 | } |
---|
| 2592 | |
---|
| 2593 | // Resets stuff if model changes |
---|
[1286] | 2594 | void |
---|
[854] | 2595 | CbcHeuristicPartial::resetModel(CbcModel * model) |
---|
| 2596 | { |
---|
[1286] | 2597 | model_ = model; |
---|
| 2598 | // Get a copy of original matrix (and by row for partial); |
---|
| 2599 | assert(model_->solver()); |
---|
| 2600 | validate(); |
---|
[854] | 2601 | } |
---|
| 2602 | // See if partial will give solution |
---|
| 2603 | // Sets value of solution |
---|
| 2604 | // Assumes rhs for original matrix still okay |
---|
[1286] | 2605 | // At present only works with integers |
---|
[854] | 2606 | // Fix values if asked for |
---|
| 2607 | // Returns 1 if solution, 0 if not |
---|
| 2608 | int |
---|
| 2609 | CbcHeuristicPartial::solution(double & solutionValue, |
---|
[1286] | 2610 | double * betterSolution) |
---|
[854] | 2611 | { |
---|
[1286] | 2612 | // Return if already done |
---|
| 2613 | if (fixPriority_ < 0) |
---|
| 2614 | return 0; // switched off |
---|
| 2615 | const double * hotstartSolution = model_->hotstartSolution(); |
---|
| 2616 | const int * hotstartPriorities = model_->hotstartPriorities(); |
---|
| 2617 | if (!hotstartSolution) |
---|
| 2618 | return 0; |
---|
| 2619 | OsiSolverInterface * solver = model_->solver(); |
---|
[854] | 2620 | |
---|
[1286] | 2621 | int numberIntegers = model_->numberIntegers(); |
---|
| 2622 | const int * integerVariable = model_->integerVariable(); |
---|
[854] | 2623 | |
---|
[1286] | 2624 | OsiSolverInterface * newSolver = model_->continuousSolver()->clone(); |
---|
| 2625 | const double * colLower = newSolver->getColLower(); |
---|
| 2626 | const double * colUpper = newSolver->getColUpper(); |
---|
| 2627 | |
---|
| 2628 | double primalTolerance; |
---|
| 2629 | solver->getDblParam(OsiPrimalTolerance, primalTolerance); |
---|
| 2630 | |
---|
| 2631 | int i; |
---|
| 2632 | int numberFixed = 0; |
---|
| 2633 | int returnCode = 0; |
---|
| 2634 | |
---|
| 2635 | for (i = 0; i < numberIntegers; i++) { |
---|
| 2636 | int iColumn = integerVariable[i]; |
---|
| 2637 | if (abs(hotstartPriorities[iColumn]) <= fixPriority_) { |
---|
| 2638 | double value = hotstartSolution[iColumn]; |
---|
| 2639 | double lower = colLower[iColumn]; |
---|
| 2640 | double upper = colUpper[iColumn]; |
---|
| 2641 | value = CoinMax(value, lower); |
---|
| 2642 | value = CoinMin(value, upper); |
---|
| 2643 | if (fabs(value - floor(value + 0.5)) < 1.0e-8) { |
---|
| 2644 | value = floor(value + 0.5); |
---|
| 2645 | newSolver->setColLower(iColumn, value); |
---|
| 2646 | newSolver->setColUpper(iColumn, value); |
---|
| 2647 | numberFixed++; |
---|
| 2648 | } |
---|
| 2649 | } |
---|
[854] | 2650 | } |
---|
[1286] | 2651 | if (numberFixed > numberIntegers / 5 - 100000000) { |
---|
[854] | 2652 | #ifdef COIN_DEVELOP |
---|
[1286] | 2653 | printf("%d integers fixed\n", numberFixed); |
---|
[854] | 2654 | #endif |
---|
[1286] | 2655 | returnCode = smallBranchAndBound(newSolver, numberNodes_, betterSolution, solutionValue, |
---|
| 2656 | model_->getCutoff(), "CbcHeuristicPartial"); |
---|
| 2657 | if (returnCode < 0) |
---|
| 2658 | returnCode = 0; // returned on size |
---|
| 2659 | //printf("return code %d",returnCode); |
---|
| 2660 | if ((returnCode&2) != 0) { |
---|
| 2661 | // could add cut |
---|
| 2662 | returnCode &= ~2; |
---|
| 2663 | //printf("could add cut with %d elements (if all 0-1)\n",nFix); |
---|
| 2664 | } else { |
---|
| 2665 | //printf("\n"); |
---|
| 2666 | } |
---|
[854] | 2667 | } |
---|
[1286] | 2668 | fixPriority_ = -1; // switch off |
---|
| 2669 | |
---|
| 2670 | delete newSolver; |
---|
| 2671 | return returnCode; |
---|
[854] | 2672 | } |
---|
| 2673 | // update model |
---|
| 2674 | void CbcHeuristicPartial::setModel(CbcModel * model) |
---|
| 2675 | { |
---|
[1286] | 2676 | model_ = model; |
---|
| 2677 | assert(model_->solver()); |
---|
| 2678 | // make sure model okay for heuristic |
---|
| 2679 | validate(); |
---|
[854] | 2680 | } |
---|
| 2681 | // Validate model i.e. sets when_ to 0 if necessary (may be NULL) |
---|
[1286] | 2682 | void |
---|
| 2683 | CbcHeuristicPartial::validate() |
---|
[854] | 2684 | { |
---|
[1286] | 2685 | if (model_ && (when() % 100) < 10) { |
---|
| 2686 | if (model_->numberIntegers() != |
---|
| 2687 | model_->numberObjects()) |
---|
| 2688 | setWhen(0); |
---|
| 2689 | } |
---|
[854] | 2690 | } |
---|
[1013] | 2691 | bool |
---|
[1271] | 2692 | CbcHeuristicPartial::shouldHeurRun(int /*whereFrom*/) |
---|
[1013] | 2693 | { |
---|
[1286] | 2694 | return true; |
---|
[1013] | 2695 | } |
---|
[854] | 2696 | |
---|
| 2697 | // Default Constructor |
---|
[1286] | 2698 | CbcSerendipity::CbcSerendipity() |
---|
| 2699 | : CbcHeuristic() |
---|
[264] | 2700 | { |
---|
| 2701 | } |
---|
| 2702 | |
---|
| 2703 | // Constructor from model |
---|
| 2704 | CbcSerendipity::CbcSerendipity(CbcModel & model) |
---|
[1286] | 2705 | : CbcHeuristic(model) |
---|
[264] | 2706 | { |
---|
| 2707 | } |
---|
| 2708 | |
---|
[1286] | 2709 | // Destructor |
---|
[264] | 2710 | CbcSerendipity::~CbcSerendipity () |
---|
| 2711 | { |
---|
| 2712 | } |
---|
| 2713 | |
---|
| 2714 | // Clone |
---|
| 2715 | CbcHeuristic * |
---|
| 2716 | CbcSerendipity::clone() const |
---|
| 2717 | { |
---|
[1286] | 2718 | return new CbcSerendipity(*this); |
---|
[264] | 2719 | } |
---|
[356] | 2720 | // Create C++ lines to get to current state |
---|
[1286] | 2721 | void |
---|
| 2722 | CbcSerendipity::generateCpp( FILE * fp) |
---|
[356] | 2723 | { |
---|
[1286] | 2724 | fprintf(fp, "0#include \"CbcHeuristic.hpp\"\n"); |
---|
| 2725 | fprintf(fp, "3 CbcSerendipity serendipity(*cbcModel);\n"); |
---|
| 2726 | CbcHeuristic::generateCpp(fp, "serendipity"); |
---|
| 2727 | fprintf(fp, "3 cbcModel->addHeuristic(&serendipity);\n"); |
---|
[356] | 2728 | } |
---|
[264] | 2729 | |
---|
[1286] | 2730 | // Copy constructor |
---|
[264] | 2731 | CbcSerendipity::CbcSerendipity(const CbcSerendipity & rhs) |
---|
[1286] | 2732 | : |
---|
| 2733 | CbcHeuristic(rhs) |
---|
[264] | 2734 | { |
---|
| 2735 | } |
---|
| 2736 | |
---|
[1286] | 2737 | // Assignment operator |
---|
| 2738 | CbcSerendipity & |
---|
| 2739 | CbcSerendipity::operator=( const CbcSerendipity & rhs) |
---|
[640] | 2740 | { |
---|
[1286] | 2741 | if (this != &rhs) { |
---|
| 2742 | CbcHeuristic::operator=(rhs); |
---|
| 2743 | } |
---|
| 2744 | return *this; |
---|
[640] | 2745 | } |
---|
| 2746 | |
---|
[264] | 2747 | // Returns 1 if solution, 0 if not |
---|
| 2748 | int |
---|
| 2749 | CbcSerendipity::solution(double & solutionValue, |
---|
[1286] | 2750 | double * betterSolution) |
---|
[264] | 2751 | { |
---|
[1286] | 2752 | if (!model_) |
---|
| 2753 | return 0; |
---|
| 2754 | if (!inputSolution_) { |
---|
| 2755 | // get information on solver type |
---|
| 2756 | OsiAuxInfo * auxInfo = model_->solver()->getAuxiliaryInfo(); |
---|
| 2757 | OsiBabSolver * auxiliaryInfo = dynamic_cast< OsiBabSolver *> (auxInfo); |
---|
| 2758 | if (auxiliaryInfo) { |
---|
| 2759 | return auxiliaryInfo->solution(solutionValue, betterSolution, model_->solver()->getNumCols()); |
---|
| 2760 | } else { |
---|
| 2761 | return 0; |
---|
| 2762 | } |
---|
[940] | 2763 | } else { |
---|
[1286] | 2764 | int numberColumns = model_->getNumCols(); |
---|
| 2765 | double value = inputSolution_[numberColumns]; |
---|
| 2766 | int returnCode = 0; |
---|
| 2767 | if (value < solutionValue) { |
---|
| 2768 | solutionValue = value; |
---|
| 2769 | memcpy(betterSolution, inputSolution_, numberColumns*sizeof(double)); |
---|
| 2770 | returnCode = 1; |
---|
| 2771 | } |
---|
| 2772 | delete [] inputSolution_; |
---|
| 2773 | inputSolution_ = NULL; |
---|
| 2774 | model_ = NULL; // switch off |
---|
| 2775 | return returnCode; |
---|
[940] | 2776 | } |
---|
[264] | 2777 | } |
---|
| 2778 | // update model |
---|
| 2779 | void CbcSerendipity::setModel(CbcModel * model) |
---|
| 2780 | { |
---|
[1286] | 2781 | model_ = model; |
---|
[264] | 2782 | } |
---|
| 2783 | // Resets stuff if model changes |
---|
[1286] | 2784 | void |
---|
[264] | 2785 | CbcSerendipity::resetModel(CbcModel * model) |
---|
| 2786 | { |
---|
[1286] | 2787 | model_ = model; |
---|
[264] | 2788 | } |
---|
[961] | 2789 | |
---|
[1286] | 2790 | |
---|
[961] | 2791 | // Default Constructor |
---|
[1286] | 2792 | CbcHeuristicJustOne::CbcHeuristicJustOne() |
---|
| 2793 | : CbcHeuristic(), |
---|
| 2794 | probabilities_(NULL), |
---|
| 2795 | heuristic_(NULL), |
---|
| 2796 | numberHeuristics_(0) |
---|
[961] | 2797 | { |
---|
| 2798 | } |
---|
| 2799 | |
---|
| 2800 | // Constructor from model |
---|
| 2801 | CbcHeuristicJustOne::CbcHeuristicJustOne(CbcModel & model) |
---|
[1286] | 2802 | : CbcHeuristic(model), |
---|
| 2803 | probabilities_(NULL), |
---|
| 2804 | heuristic_(NULL), |
---|
| 2805 | numberHeuristics_(0) |
---|
[961] | 2806 | { |
---|
| 2807 | } |
---|
| 2808 | |
---|
[1286] | 2809 | // Destructor |
---|
[961] | 2810 | CbcHeuristicJustOne::~CbcHeuristicJustOne () |
---|
| 2811 | { |
---|
[1286] | 2812 | for (int i = 0; i < numberHeuristics_; i++) |
---|
| 2813 | delete heuristic_[i]; |
---|
| 2814 | delete [] heuristic_; |
---|
| 2815 | delete [] probabilities_; |
---|
[961] | 2816 | } |
---|
| 2817 | |
---|
| 2818 | // Clone |
---|
| 2819 | CbcHeuristicJustOne * |
---|
| 2820 | CbcHeuristicJustOne::clone() const |
---|
| 2821 | { |
---|
[1286] | 2822 | return new CbcHeuristicJustOne(*this); |
---|
[961] | 2823 | } |
---|
| 2824 | |
---|
| 2825 | // Create C++ lines to get to current state |
---|
[1286] | 2826 | void |
---|
| 2827 | CbcHeuristicJustOne::generateCpp( FILE * fp) |
---|
[961] | 2828 | { |
---|
[1286] | 2829 | CbcHeuristicJustOne other; |
---|
| 2830 | fprintf(fp, "0#include \"CbcHeuristicJustOne.hpp\"\n"); |
---|
| 2831 | fprintf(fp, "3 CbcHeuristicJustOne heuristicJustOne(*cbcModel);\n"); |
---|
| 2832 | CbcHeuristic::generateCpp(fp, "heuristicJustOne"); |
---|
| 2833 | fprintf(fp, "3 cbcModel->addHeuristic(&heuristicJustOne);\n"); |
---|
[961] | 2834 | } |
---|
| 2835 | |
---|
[1286] | 2836 | // Copy constructor |
---|
[961] | 2837 | CbcHeuristicJustOne::CbcHeuristicJustOne(const CbcHeuristicJustOne & rhs) |
---|
[1286] | 2838 | : |
---|
| 2839 | CbcHeuristic(rhs), |
---|
| 2840 | probabilities_(NULL), |
---|
| 2841 | heuristic_(NULL), |
---|
| 2842 | numberHeuristics_(rhs.numberHeuristics_) |
---|
[961] | 2843 | { |
---|
[1286] | 2844 | if (numberHeuristics_) { |
---|
| 2845 | probabilities_ = CoinCopyOfArray(rhs.probabilities_, numberHeuristics_); |
---|
| 2846 | heuristic_ = new CbcHeuristic * [numberHeuristics_]; |
---|
| 2847 | for (int i = 0; i < numberHeuristics_; i++) |
---|
| 2848 | heuristic_[i] = rhs.heuristic_[i]->clone(); |
---|
| 2849 | } |
---|
[961] | 2850 | } |
---|
| 2851 | |
---|
[1286] | 2852 | // Assignment operator |
---|
| 2853 | CbcHeuristicJustOne & |
---|
| 2854 | CbcHeuristicJustOne::operator=( const CbcHeuristicJustOne & rhs) |
---|
[961] | 2855 | { |
---|
[1286] | 2856 | if (this != &rhs) { |
---|
| 2857 | CbcHeuristic::operator=(rhs); |
---|
| 2858 | for (int i = 0; i < numberHeuristics_; i++) |
---|
| 2859 | delete heuristic_[i]; |
---|
| 2860 | delete [] heuristic_; |
---|
| 2861 | delete [] probabilities_; |
---|
| 2862 | probabilities_ = NULL; |
---|
| 2863 | heuristic_ = NULL; |
---|
| 2864 | numberHeuristics_ = rhs.numberHeuristics_; |
---|
| 2865 | if (numberHeuristics_) { |
---|
| 2866 | probabilities_ = CoinCopyOfArray(rhs.probabilities_, numberHeuristics_); |
---|
| 2867 | heuristic_ = new CbcHeuristic * [numberHeuristics_]; |
---|
| 2868 | for (int i = 0; i < numberHeuristics_; i++) |
---|
| 2869 | heuristic_[i] = rhs.heuristic_[i]->clone(); |
---|
| 2870 | } |
---|
[961] | 2871 | } |
---|
[1286] | 2872 | return *this; |
---|
[961] | 2873 | } |
---|
| 2874 | // Sets value of solution |
---|
| 2875 | // Returns 1 if solution, 0 if not |
---|
| 2876 | int |
---|
| 2877 | CbcHeuristicJustOne::solution(double & solutionValue, |
---|
[1286] | 2878 | double * betterSolution) |
---|
[961] | 2879 | { |
---|
| 2880 | #ifdef DIVE_DEBUG |
---|
[1286] | 2881 | std::cout << "solutionValue = " << solutionValue << std::endl; |
---|
[961] | 2882 | #endif |
---|
[1286] | 2883 | ++numCouldRun_; |
---|
[961] | 2884 | |
---|
[1286] | 2885 | // test if the heuristic can run |
---|
| 2886 | if (!shouldHeurRun_randomChoice() || !numberHeuristics_) |
---|
| 2887 | return 0; |
---|
| 2888 | double randomNumber = randomNumberGenerator_.randomDouble(); |
---|
| 2889 | int i; |
---|
| 2890 | for (i = 0; i < numberHeuristics_; i++) { |
---|
| 2891 | if (randomNumber < probabilities_[i]) |
---|
| 2892 | break; |
---|
| 2893 | } |
---|
| 2894 | assert (i < numberHeuristics_); |
---|
| 2895 | int returnCode; |
---|
| 2896 | //model_->unsetDivingHasRun(); |
---|
[961] | 2897 | #ifdef COIN_DEVELOP |
---|
[1286] | 2898 | printf("JustOne running %s\n", |
---|
| 2899 | heuristic_[i]->heuristicName()); |
---|
[961] | 2900 | #endif |
---|
[1286] | 2901 | returnCode = heuristic_[i]->solution(solutionValue, betterSolution); |
---|
[961] | 2902 | #ifdef COIN_DEVELOP |
---|
[1286] | 2903 | if (returnCode) |
---|
| 2904 | printf("JustOne running %s found solution\n", |
---|
| 2905 | heuristic_[i]->heuristicName()); |
---|
[961] | 2906 | #endif |
---|
[1286] | 2907 | return returnCode; |
---|
[961] | 2908 | } |
---|
| 2909 | // Resets stuff if model changes |
---|
[1286] | 2910 | void |
---|
[961] | 2911 | CbcHeuristicJustOne::resetModel(CbcModel * model) |
---|
| 2912 | { |
---|
[1286] | 2913 | CbcHeuristic::resetModel(model); |
---|
| 2914 | for (int i = 0; i < numberHeuristics_; i++) |
---|
| 2915 | heuristic_[i]->resetModel(model); |
---|
[961] | 2916 | } |
---|
| 2917 | // update model (This is needed if cliques update matrix etc) |
---|
[1286] | 2918 | void |
---|
[961] | 2919 | CbcHeuristicJustOne::setModel(CbcModel * model) |
---|
| 2920 | { |
---|
[1286] | 2921 | CbcHeuristic::setModel(model); |
---|
| 2922 | for (int i = 0; i < numberHeuristics_; i++) |
---|
| 2923 | heuristic_[i]->setModel(model); |
---|
[961] | 2924 | } |
---|
| 2925 | // Validate model i.e. sets when_ to 0 if necessary (may be NULL) |
---|
[1286] | 2926 | void |
---|
[961] | 2927 | CbcHeuristicJustOne::validate() |
---|
| 2928 | { |
---|
[1286] | 2929 | CbcHeuristic::validate(); |
---|
| 2930 | for (int i = 0; i < numberHeuristics_; i++) |
---|
| 2931 | heuristic_[i]->validate(); |
---|
[961] | 2932 | } |
---|
| 2933 | // Adds an heuristic with probability |
---|
[1286] | 2934 | void |
---|
[961] | 2935 | CbcHeuristicJustOne::addHeuristic(const CbcHeuristic * heuristic, double probability) |
---|
| 2936 | { |
---|
[1286] | 2937 | CbcHeuristic * thisOne = heuristic->clone(); |
---|
| 2938 | thisOne->setWhen(-999); |
---|
| 2939 | CbcHeuristic ** tempH = CoinCopyOfArrayPartial(heuristic_, numberHeuristics_ + 1, |
---|
| 2940 | numberHeuristics_); |
---|
| 2941 | delete [] heuristic_; |
---|
| 2942 | heuristic_ = tempH; |
---|
| 2943 | heuristic_[numberHeuristics_] = thisOne; |
---|
| 2944 | double * tempP = CoinCopyOfArrayPartial(probabilities_, numberHeuristics_ + 1, |
---|
| 2945 | numberHeuristics_); |
---|
| 2946 | delete [] probabilities_; |
---|
| 2947 | probabilities_ = tempP; |
---|
| 2948 | probabilities_[numberHeuristics_] = probability; |
---|
| 2949 | numberHeuristics_++; |
---|
[961] | 2950 | } |
---|
| 2951 | // Normalize probabilities |
---|
[1286] | 2952 | void |
---|
[961] | 2953 | CbcHeuristicJustOne::normalizeProbabilities() |
---|
| 2954 | { |
---|
[1286] | 2955 | double sum = 0.0; |
---|
| 2956 | for (int i = 0; i < numberHeuristics_; i++) |
---|
| 2957 | sum += probabilities_[i]; |
---|
| 2958 | double multiplier = 1.0 / sum; |
---|
| 2959 | sum = 0.0; |
---|
| 2960 | for (int i = 0; i < numberHeuristics_; i++) { |
---|
| 2961 | sum += probabilities_[i]; |
---|
| 2962 | probabilities_[i] = sum * multiplier; |
---|
| 2963 | } |
---|
| 2964 | assert (fabs(probabilities_[numberHeuristics_-1] - 1.0) < 1.0e-5); |
---|
| 2965 | probabilities_[numberHeuristics_-1] = 1.000001; |
---|
[961] | 2966 | } |
---|
[1432] | 2967 | |
---|