[1271] | 1 | /* $Id: CbcHeuristicDiveGuided.cpp 1173 2009-06-04 09:44:10Z forrest $ */ |
---|
[868] | 2 | // Copyright (C) 2008, 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 | |
---|
[868] | 6 | #if defined(_MSC_VER) |
---|
| 7 | // Turn off compiler warning about long names |
---|
| 8 | # pragma warning(disable:4786) |
---|
| 9 | #endif |
---|
| 10 | |
---|
| 11 | #include "CbcHeuristicDiveGuided.hpp" |
---|
| 12 | #include "CbcStrategy.hpp" |
---|
| 13 | |
---|
| 14 | // Default Constructor |
---|
[1286] | 15 | CbcHeuristicDiveGuided::CbcHeuristicDiveGuided() |
---|
| 16 | : CbcHeuristicDive() |
---|
[868] | 17 | { |
---|
| 18 | } |
---|
| 19 | |
---|
| 20 | // Constructor from model |
---|
| 21 | CbcHeuristicDiveGuided::CbcHeuristicDiveGuided(CbcModel & model) |
---|
[1286] | 22 | : CbcHeuristicDive(model) |
---|
[868] | 23 | { |
---|
| 24 | } |
---|
| 25 | |
---|
[1286] | 26 | // Destructor |
---|
[868] | 27 | CbcHeuristicDiveGuided::~CbcHeuristicDiveGuided () |
---|
| 28 | { |
---|
| 29 | } |
---|
| 30 | |
---|
| 31 | // Clone |
---|
| 32 | CbcHeuristicDiveGuided * |
---|
| 33 | CbcHeuristicDiveGuided::clone() const |
---|
| 34 | { |
---|
[1286] | 35 | return new CbcHeuristicDiveGuided(*this); |
---|
[868] | 36 | } |
---|
| 37 | |
---|
| 38 | // Create C++ lines to get to current state |
---|
[1286] | 39 | void |
---|
| 40 | CbcHeuristicDiveGuided::generateCpp( FILE * fp) |
---|
[868] | 41 | { |
---|
[1286] | 42 | CbcHeuristicDiveGuided other; |
---|
| 43 | fprintf(fp, "0#include \"CbcHeuristicDiveGuided.hpp\"\n"); |
---|
| 44 | fprintf(fp, "3 CbcHeuristicDiveGuided heuristicDiveGuided(*cbcModel);\n"); |
---|
| 45 | CbcHeuristic::generateCpp(fp, "heuristicDiveGuided"); |
---|
| 46 | fprintf(fp, "3 cbcModel->addHeuristic(&heuristicDiveGuided);\n"); |
---|
[868] | 47 | } |
---|
| 48 | |
---|
[1286] | 49 | // Copy constructor |
---|
[868] | 50 | CbcHeuristicDiveGuided::CbcHeuristicDiveGuided(const CbcHeuristicDiveGuided & rhs) |
---|
[1286] | 51 | : |
---|
| 52 | CbcHeuristicDive(rhs) |
---|
[868] | 53 | { |
---|
| 54 | } |
---|
| 55 | |
---|
[1286] | 56 | // Assignment operator |
---|
| 57 | CbcHeuristicDiveGuided & |
---|
| 58 | CbcHeuristicDiveGuided::operator=( const CbcHeuristicDiveGuided & rhs) |
---|
[868] | 59 | { |
---|
[1286] | 60 | if (this != &rhs) { |
---|
| 61 | CbcHeuristicDive::operator=(rhs); |
---|
| 62 | } |
---|
| 63 | return *this; |
---|
[868] | 64 | } |
---|
| 65 | |
---|
[912] | 66 | bool |
---|
| 67 | CbcHeuristicDiveGuided::canHeuristicRun() |
---|
[868] | 68 | { |
---|
[1286] | 69 | double* bestIntegerSolution = model_->bestSolution(); |
---|
| 70 | if (bestIntegerSolution == NULL) |
---|
| 71 | return false; // no integer solution available. Switch off heuristic |
---|
[912] | 72 | |
---|
[1286] | 73 | return CbcHeuristicDive::canHeuristicRun(); |
---|
[868] | 74 | } |
---|
| 75 | |
---|
[944] | 76 | bool |
---|
[912] | 77 | CbcHeuristicDiveGuided::selectVariableToBranch(OsiSolverInterface* solver, |
---|
[1286] | 78 | const double* newSolution, |
---|
| 79 | int& bestColumn, |
---|
| 80 | int& bestRound) |
---|
[868] | 81 | { |
---|
[1286] | 82 | double* bestIntegerSolution = model_->bestSolution(); |
---|
[868] | 83 | |
---|
[1286] | 84 | int numberIntegers = model_->numberIntegers(); |
---|
| 85 | const int * integerVariable = model_->integerVariable(); |
---|
| 86 | double integerTolerance = model_->getDblParam(CbcModel::CbcIntegerTolerance); |
---|
[868] | 87 | |
---|
[1286] | 88 | bestColumn = -1; |
---|
| 89 | bestRound = -1; // -1 rounds down, +1 rounds up |
---|
| 90 | double bestFraction = DBL_MAX; |
---|
| 91 | bool allTriviallyRoundableSoFar = true; |
---|
| 92 | for (int i = 0; i < numberIntegers; i++) { |
---|
| 93 | int iColumn = integerVariable[i]; |
---|
| 94 | double value = newSolution[iColumn]; |
---|
| 95 | double fraction = value - floor(value); |
---|
| 96 | int round = 0; |
---|
| 97 | if (fabs(floor(value + 0.5) - value) > integerTolerance) { |
---|
| 98 | if (allTriviallyRoundableSoFar || (downLocks_[i] > 0 && upLocks_[i] > 0)) { |
---|
[944] | 99 | |
---|
[1286] | 100 | if (allTriviallyRoundableSoFar && downLocks_[i] > 0 && upLocks_[i] > 0) { |
---|
| 101 | allTriviallyRoundableSoFar = false; |
---|
| 102 | bestFraction = DBL_MAX; |
---|
| 103 | } |
---|
[944] | 104 | |
---|
[1286] | 105 | if (value >= bestIntegerSolution[iColumn]) |
---|
| 106 | round = -1; |
---|
| 107 | else { |
---|
| 108 | round = 1; |
---|
| 109 | fraction = 1.0 - fraction; |
---|
| 110 | } |
---|
[868] | 111 | |
---|
[1286] | 112 | // if variable is not binary, penalize it |
---|
| 113 | if (!solver->isBinary(iColumn)) |
---|
| 114 | fraction *= 1000.0; |
---|
| 115 | |
---|
| 116 | if (fraction < bestFraction) { |
---|
| 117 | bestColumn = iColumn; |
---|
| 118 | bestFraction = fraction; |
---|
| 119 | bestRound = round; |
---|
| 120 | } |
---|
| 121 | } |
---|
| 122 | } |
---|
[868] | 123 | } |
---|
[1286] | 124 | return allTriviallyRoundableSoFar; |
---|
[868] | 125 | } |
---|
[1432] | 126 | |
---|