[1854] | 1 | /* $Id: CbcHeuristicDiveVectorLength.cpp 1902 2013-04-10 16:58:16Z 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 "CbcHeuristicDiveVectorLength.hpp" |
---|
| 12 | #include "CbcStrategy.hpp" |
---|
| 13 | |
---|
| 14 | // Default Constructor |
---|
[1286] | 15 | CbcHeuristicDiveVectorLength::CbcHeuristicDiveVectorLength() |
---|
| 16 | : CbcHeuristicDive() |
---|
[868] | 17 | { |
---|
| 18 | } |
---|
| 19 | |
---|
| 20 | // Constructor from model |
---|
| 21 | CbcHeuristicDiveVectorLength::CbcHeuristicDiveVectorLength(CbcModel & model) |
---|
[1286] | 22 | : CbcHeuristicDive(model) |
---|
[868] | 23 | { |
---|
| 24 | } |
---|
| 25 | |
---|
[1286] | 26 | // Destructor |
---|
[868] | 27 | CbcHeuristicDiveVectorLength::~CbcHeuristicDiveVectorLength () |
---|
| 28 | { |
---|
| 29 | } |
---|
| 30 | |
---|
| 31 | // Clone |
---|
| 32 | CbcHeuristicDiveVectorLength * |
---|
| 33 | CbcHeuristicDiveVectorLength::clone() const |
---|
| 34 | { |
---|
[1286] | 35 | return new CbcHeuristicDiveVectorLength(*this); |
---|
[868] | 36 | } |
---|
| 37 | |
---|
| 38 | // Create C++ lines to get to current state |
---|
[1286] | 39 | void |
---|
| 40 | CbcHeuristicDiveVectorLength::generateCpp( FILE * fp) |
---|
[868] | 41 | { |
---|
[1286] | 42 | CbcHeuristicDiveVectorLength other; |
---|
| 43 | fprintf(fp, "0#include \"CbcHeuristicDiveVectorLength.hpp\"\n"); |
---|
| 44 | fprintf(fp, "3 CbcHeuristicDiveVectorLength heuristicDiveVectorLength(*cbcModel);\n"); |
---|
| 45 | CbcHeuristic::generateCpp(fp, "heuristicDiveVectorLength"); |
---|
| 46 | fprintf(fp, "3 cbcModel->addHeuristic(&heuristicDiveVectorLength);\n"); |
---|
[868] | 47 | } |
---|
| 48 | |
---|
[1286] | 49 | // Copy constructor |
---|
[868] | 50 | CbcHeuristicDiveVectorLength::CbcHeuristicDiveVectorLength(const CbcHeuristicDiveVectorLength & rhs) |
---|
[1286] | 51 | : |
---|
| 52 | CbcHeuristicDive(rhs) |
---|
[868] | 53 | { |
---|
| 54 | } |
---|
| 55 | |
---|
[1286] | 56 | // Assignment operator |
---|
| 57 | CbcHeuristicDiveVectorLength & |
---|
| 58 | CbcHeuristicDiveVectorLength::operator=( const CbcHeuristicDiveVectorLength & rhs) |
---|
[868] | 59 | { |
---|
[1286] | 60 | if (this != &rhs) { |
---|
| 61 | CbcHeuristicDive::operator=(rhs); |
---|
| 62 | } |
---|
| 63 | return *this; |
---|
[868] | 64 | } |
---|
| 65 | |
---|
[944] | 66 | bool |
---|
[912] | 67 | CbcHeuristicDiveVectorLength::selectVariableToBranch(OsiSolverInterface* solver, |
---|
[1286] | 68 | const double* newSolution, |
---|
| 69 | int& bestColumn, |
---|
| 70 | int& bestRound) |
---|
[868] | 71 | { |
---|
[1286] | 72 | const double * objective = solver->getObjCoefficients(); |
---|
| 73 | double direction = solver->getObjSense(); // 1 for min, -1 for max |
---|
[868] | 74 | |
---|
[1286] | 75 | const int * columnLength = matrix_.getVectorLengths(); |
---|
| 76 | int numberIntegers = model_->numberIntegers(); |
---|
| 77 | const int * integerVariable = model_->integerVariable(); |
---|
| 78 | double integerTolerance = model_->getDblParam(CbcModel::CbcIntegerTolerance); |
---|
[868] | 79 | |
---|
[1286] | 80 | bestColumn = -1; |
---|
| 81 | bestRound = -1; // -1 rounds down, +1 rounds up |
---|
[1643] | 82 | double bestScore = COIN_DBL_MAX; |
---|
[1286] | 83 | bool allTriviallyRoundableSoFar = true; |
---|
| 84 | for (int i = 0; i < numberIntegers; i++) { |
---|
| 85 | int iColumn = integerVariable[i]; |
---|
| 86 | double value = newSolution[iColumn]; |
---|
| 87 | double fraction = value - floor(value); |
---|
| 88 | int round = 0; |
---|
| 89 | if (fabs(floor(value + 0.5) - value) > integerTolerance) { |
---|
| 90 | if (allTriviallyRoundableSoFar || (downLocks_[i] > 0 && upLocks_[i] > 0)) { |
---|
[944] | 91 | |
---|
[1286] | 92 | if (allTriviallyRoundableSoFar && downLocks_[i] > 0 && upLocks_[i] > 0) { |
---|
| 93 | allTriviallyRoundableSoFar = false; |
---|
[1643] | 94 | bestScore = COIN_DBL_MAX; |
---|
[1286] | 95 | } |
---|
[944] | 96 | |
---|
[1286] | 97 | // the variable cannot be rounded |
---|
| 98 | double obj = direction * objective[iColumn]; |
---|
| 99 | if (obj >= 0.0) |
---|
| 100 | round = 1; // round up |
---|
| 101 | else |
---|
| 102 | round = -1; // round down |
---|
| 103 | double objDelta; |
---|
| 104 | if (round == 1) |
---|
| 105 | objDelta = (1.0 - fraction) * obj; |
---|
| 106 | else |
---|
| 107 | objDelta = - fraction * obj; |
---|
[868] | 108 | |
---|
[1286] | 109 | // we want the smaller score |
---|
| 110 | double score = objDelta / (static_cast<double> (columnLength[iColumn]) + 1.0); |
---|
[868] | 111 | |
---|
[1286] | 112 | // if variable is not binary, penalize it |
---|
| 113 | if (!solver->isBinary(iColumn)) |
---|
| 114 | score *= 1000.0; |
---|
| 115 | |
---|
| 116 | if (score < bestScore) { |
---|
| 117 | bestColumn = iColumn; |
---|
| 118 | bestScore = score; |
---|
| 119 | bestRound = round; |
---|
| 120 | } |
---|
| 121 | } |
---|
| 122 | } |
---|
[868] | 123 | } |
---|
[1286] | 124 | return allTriviallyRoundableSoFar; |
---|
[868] | 125 | } |
---|
[1432] | 126 | |
---|