1 /* $Id$ */
2 // Copyright (C) 2008, International Business Machines
3 // Corporation and others. All Rights Reserved.
4 // This code is licensed under the terms of the Eclipse Public License (EPL).
5
6 #if defined(_MSC_VER)
7 // Turn off compiler warning about long names
8 #pragma warning(disable : 4786)
9 #endif
10
11 #include "CbcHeuristicDiveLineSearch.hpp"
12 #include "CbcStrategy.hpp"
13
14 // Default Constructor
CbcHeuristicDiveLineSearch()15 CbcHeuristicDiveLineSearch::CbcHeuristicDiveLineSearch()
16 : CbcHeuristicDive()
17 {
18 }
19
20 // Constructor from model
CbcHeuristicDiveLineSearch(CbcModel & model)21 CbcHeuristicDiveLineSearch::CbcHeuristicDiveLineSearch(CbcModel &model)
22 : CbcHeuristicDive(model)
23 {
24 }
25
26 // Destructor
~CbcHeuristicDiveLineSearch()27 CbcHeuristicDiveLineSearch::~CbcHeuristicDiveLineSearch()
28 {
29 }
30
31 // Clone
32 CbcHeuristicDiveLineSearch *
clone() const33 CbcHeuristicDiveLineSearch::clone() const
34 {
35 return new CbcHeuristicDiveLineSearch(*this);
36 }
37
38 // Create C++ lines to get to current state
generateCpp(FILE * fp)39 void CbcHeuristicDiveLineSearch::generateCpp(FILE *fp)
40 {
41 CbcHeuristicDiveLineSearch other;
42 fprintf(fp, "0#include \"CbcHeuristicDiveLineSearch.hpp\"\n");
43 fprintf(fp, "3 CbcHeuristicDiveLineSearch heuristicDiveLineSearch(*cbcModel);\n");
44 CbcHeuristic::generateCpp(fp, "heuristicDiveLineSearch");
45 fprintf(fp, "3 cbcModel->addHeuristic(&heuristicDiveLineSearch);\n");
46 }
47
48 // Copy constructor
CbcHeuristicDiveLineSearch(const CbcHeuristicDiveLineSearch & rhs)49 CbcHeuristicDiveLineSearch::CbcHeuristicDiveLineSearch(const CbcHeuristicDiveLineSearch &rhs)
50 : CbcHeuristicDive(rhs)
51 {
52 }
53
54 // Assignment operator
55 CbcHeuristicDiveLineSearch &
operator =(const CbcHeuristicDiveLineSearch & rhs)56 CbcHeuristicDiveLineSearch::operator=(const CbcHeuristicDiveLineSearch &rhs)
57 {
58 if (this != &rhs) {
59 CbcHeuristicDive::operator=(rhs);
60 }
61 return *this;
62 }
63
selectVariableToBranch(OsiSolverInterface * solver,const double * newSolution,int & bestColumn,int & bestRound)64 bool CbcHeuristicDiveLineSearch::selectVariableToBranch(OsiSolverInterface *solver,
65 const double *newSolution,
66 int &bestColumn,
67 int &bestRound)
68 {
69 int numberIntegers = model_->numberIntegers();
70 const int *integerVariable = model_->integerVariable();
71 double integerTolerance = model_->getDblParam(CbcModel::CbcIntegerTolerance);
72
73 // get the LP relaxation solution at the root node
74 double *rootNodeLPSol = model_->continuousSolution();
75
76 bestColumn = -1;
77 bestRound = -1; // -1 rounds down, +1 rounds up
78 double bestRelDistance = COIN_DBL_MAX;
79 bool allTriviallyRoundableSoFar = true;
80 int bestPriority = COIN_INT_MAX;
81 for (int i = 0; i < numberIntegers; i++) {
82 int iColumn = integerVariable[i];
83 if (!isHeuristicInteger(solver, iColumn))
84 continue;
85 double rootValue = rootNodeLPSol[iColumn];
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)) {
91
92 if (allTriviallyRoundableSoFar && downLocks_[i] > 0 && upLocks_[i] > 0) {
93 allTriviallyRoundableSoFar = false;
94 bestRelDistance = COIN_DBL_MAX;
95 }
96
97 double relDistance;
98 if (value < rootValue) {
99 round = -1;
100 relDistance = fraction / (rootValue - value);
101 } else if (value > rootValue) {
102 round = 1;
103 relDistance = (1.0 - fraction) / (value - rootValue);
104 } else {
105 round = -1;
106 relDistance = COIN_DBL_MAX;
107 }
108
109 // if variable is not binary, penalize it
110 if (!solver->isBinary(iColumn))
111 relDistance *= 1000.0;
112
113 // if priorities then use
114 if (priority_) {
115 int thisRound = static_cast< int >(priority_[i].direction);
116 if ((thisRound & 1) != 0)
117 round = ((thisRound & 2) == 0) ? -1 : +1;
118 if (priority_[i].priority > bestPriority) {
119 relDistance = COIN_DBL_MAX;
120 } else if (priority_[i].priority < bestPriority) {
121 bestPriority = static_cast< int >(priority_[i].priority);
122 bestRelDistance = COIN_DBL_MAX;
123 }
124 }
125 if (relDistance < bestRelDistance) {
126 bestColumn = iColumn;
127 bestRelDistance = relDistance;
128 bestRound = round;
129 }
130 }
131 }
132 }
133 return allTriviallyRoundableSoFar;
134 }
135
136 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
137 */
138