source: trunk/Cbc/src/CbcHeuristicDiveLineSearch.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.1 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 "CbcHeuristicDiveLineSearch.hpp"
9#include "CbcStrategy.hpp"
10
11// Default Constructor
12CbcHeuristicDiveLineSearch::CbcHeuristicDiveLineSearch() 
13  :CbcHeuristicDive()
14{
15}
16
17// Constructor from model
18CbcHeuristicDiveLineSearch::CbcHeuristicDiveLineSearch(CbcModel & model)
19  :CbcHeuristicDive(model)
20{
21}
22
23// Destructor
24CbcHeuristicDiveLineSearch::~CbcHeuristicDiveLineSearch ()
25{
26}
27
28// Clone
29CbcHeuristicDiveLineSearch *
30CbcHeuristicDiveLineSearch::clone() const
31{
32  return new CbcHeuristicDiveLineSearch(*this);
33}
34
35// Create C++ lines to get to current state
36void 
37CbcHeuristicDiveLineSearch::generateCpp( FILE * fp) 
38{
39  CbcHeuristicDiveLineSearch other;
40  fprintf(fp,"0#include \"CbcHeuristicDiveLineSearch.hpp\"\n");
41  fprintf(fp,"3  CbcHeuristicDiveLineSearch heuristicDiveLineSearch(*cbcModel);\n");
42  CbcHeuristic::generateCpp(fp,"heuristicDiveLineSearch");
43  fprintf(fp,"3  cbcModel->addHeuristic(&heuristicDiveLineSearch);\n");
44}
45
46// Copy constructor
47CbcHeuristicDiveLineSearch::CbcHeuristicDiveLineSearch(const CbcHeuristicDiveLineSearch & rhs)
48:
49  CbcHeuristicDive(rhs)
50{
51}
52
53// Assignment operator
54CbcHeuristicDiveLineSearch & 
55CbcHeuristicDiveLineSearch::operator=( const CbcHeuristicDiveLineSearch& rhs)
56{
57  if (this!=&rhs) {
58    CbcHeuristicDive::operator=(rhs);
59  }
60  return *this;
61}
62
63bool
64CbcHeuristicDiveLineSearch::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 = DBL_MAX;
79  bool allTriviallyRoundableSoFar = true;
80  for (int i=0; i<numberIntegers; i++) {
81    int iColumn = integerVariable[i];
82    double rootValue=rootNodeLPSol[iColumn];
83    double value=newSolution[iColumn];
84    double fraction=value-floor(value);
85    int round = 0;
86    if (fabs(floor(value+0.5)-value)>integerTolerance) {
87      if (allTriviallyRoundableSoFar||(downLocks_[i]>0&&upLocks_[i]>0)) {
88
89        if (allTriviallyRoundableSoFar&&downLocks_[i]>0&&upLocks_[i]>0) {
90          allTriviallyRoundableSoFar = false;
91          bestRelDistance = DBL_MAX;
92        }
93
94        double relDistance;
95        if(value < rootValue) {
96          round = -1;
97          relDistance = fraction / (rootValue - value);
98        }
99        else if(value > rootValue) {
100          round = 1;
101          relDistance = (1.0 - fraction) / (value - rootValue);
102        }
103        else {
104          round = -1;
105          relDistance = DBL_MAX;
106        }
107         
108        // if variable is not binary, penalize it
109        if(!solver->isBinary(iColumn))
110          relDistance *= 1000.0;
111       
112        if(relDistance < bestRelDistance) {
113          bestColumn = iColumn;
114          bestRelDistance = relDistance;
115          bestRound = round;
116        }
117      }
118    }
119  }
120  return allTriviallyRoundableSoFar;
121}
Note: See TracBrowser for help on using the repository browser.