source: trunk/Cbc/src/CbcHeuristicDivePseudoCost.cpp @ 945

Last change on this file since 945 was 945, checked in by jpgoncal, 11 years ago

Added two new versions of diving heuristics.

File size: 3.8 KB
Line 
1// Copyright (C) 2008, International Business Machines
2// Corporation and others.  All Rights Reserved.
3#if defined(_MSC_VER)
4// Turn off compiler warning about long names
5#  pragma warning(disable:4786)
6#endif
7
8#include "CbcHeuristicDivePseudoCost.hpp"
9#include "CbcStrategy.hpp"
10
11// Default Constructor
12CbcHeuristicDivePseudoCost::CbcHeuristicDivePseudoCost() 
13  :CbcHeuristicDive()
14{
15}
16
17// Constructor from model
18CbcHeuristicDivePseudoCost::CbcHeuristicDivePseudoCost(CbcModel & model)
19  :CbcHeuristicDive(model)
20{
21}
22
23// Destructor
24CbcHeuristicDivePseudoCost::~CbcHeuristicDivePseudoCost ()
25{
26}
27
28// Clone
29CbcHeuristicDivePseudoCost *
30CbcHeuristicDivePseudoCost::clone() const
31{
32  return new CbcHeuristicDivePseudoCost(*this);
33}
34
35// Create C++ lines to get to current state
36void 
37CbcHeuristicDivePseudoCost::generateCpp( FILE * fp) 
38{
39  CbcHeuristicDivePseudoCost other;
40  fprintf(fp,"0#include \"CbcHeuristicDivePseudoCost.hpp\"\n");
41  fprintf(fp,"3  CbcHeuristicDivePseudoCost heuristicDivePseudoCost(*cbcModel);\n");
42  CbcHeuristic::generateCpp(fp,"heuristicDivePseudoCost");
43  fprintf(fp,"3  cbcModel->addHeuristic(&heuristicDivePseudoCost);\n");
44}
45
46// Copy constructor
47CbcHeuristicDivePseudoCost::CbcHeuristicDivePseudoCost(const CbcHeuristicDivePseudoCost & rhs)
48:
49  CbcHeuristicDive(rhs)
50{
51}
52
53// Assignment operator
54CbcHeuristicDivePseudoCost & 
55CbcHeuristicDivePseudoCost::operator=( const CbcHeuristicDivePseudoCost& rhs)
56{
57  if (this!=&rhs) {
58    CbcHeuristicDive::operator=(rhs);
59  }
60  return *this;
61}
62
63bool
64CbcHeuristicDivePseudoCost::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  // get pseudo costs
77  double * pseudoCostDown = new double[numberIntegers];
78  double * pseudoCostUp = new double[numberIntegers];
79  model_->fillPseudoCosts(pseudoCostDown, pseudoCostUp);
80
81  bestColumn = -1;
82  bestRound = -1; // -1 rounds down, +1 rounds up
83  double bestScore = -1.0;
84  bool allTriviallyRoundableSoFar = true;
85  for (int i=0; i<numberIntegers; i++) {
86    int iColumn = integerVariable[i];
87    double rootValue=rootNodeLPSol[iColumn];
88    double value=newSolution[iColumn];
89    double fraction=value-floor(value);
90    int round = 0;
91    if (fabs(floor(value+0.5)-value)>integerTolerance) {
92      if (allTriviallyRoundableSoFar||(downLocks_[i]>0&&upLocks_[i]>0)) {
93
94        if (allTriviallyRoundableSoFar&&downLocks_[i]>0&&upLocks_[i]>0) {
95          allTriviallyRoundableSoFar = false;
96          bestScore = -1.0;
97        }
98
99        double pCostDown = pseudoCostDown[i];
100        double pCostUp = pseudoCostUp[i];
101        assert(pCostDown >= 0.0 && pCostUp >= 0.0);
102
103        if(allTriviallyRoundableSoFar&&downLocks_[i]==0&&upLocks_[i]>0)
104            round = 1;
105        else if(allTriviallyRoundableSoFar&&downLocks_[i]>0&&upLocks_[i]==0)
106          round = -1;
107        else if(value - rootValue < -0.4)
108          round = -1;
109        else if(value - rootValue > 0.4)
110          round = 1;
111        else if(fraction < 0.3)
112          round = -1;
113        else if(fraction > 0.7)
114          round = 1;
115        else if(pCostDown < pCostUp)
116          round = -1;
117        else
118          round = 1;
119
120        // calculate score
121        double score;
122        if(round == 1)
123          score = fraction * (pCostDown + 1.0) / (pCostUp + 1.0);
124        else
125          score = (1.0 - fraction) * (pCostUp + 1.0) / (pCostDown + 1.0);
126
127        // if variable is binary, increase its chance of being selected
128        if(solver->isBinary(iColumn))
129          score *= 1000.0;
130       
131        if(score > bestScore) {
132          bestColumn = iColumn;
133          bestScore = score;
134          bestRound = round;
135        }
136      }
137    }
138  }
139
140  delete [] pseudoCostDown;
141  delete [] pseudoCostUp;
142
143  return allTriviallyRoundableSoFar;
144}
Note: See TracBrowser for help on using the repository browser.