source: stable/2.4/Cbc/src/CbcHeuristicDivePseudoCost.cpp @ 1271

Last change on this file since 1271 was 1271, checked in by forrest, 11 years ago

Creating new stable branch 2.4 from trunk (rev 1270)

File size: 6.7 KB
Line 
1/* $Id: CbcHeuristicDivePseudoCost.cpp 1240 2009-10-02 18:41:44Z forrest $ */
2// Copyright (C) 2008, International Business Machines
3// Corporation and others.  All Rights Reserved.
4#if defined(_MSC_VER)
5// Turn off compiler warning about long names
6#  pragma warning(disable:4786)
7#endif
8
9#include "CbcHeuristicDivePseudoCost.hpp"
10#include "CbcStrategy.hpp"
11#include "CbcBranchDynamic.hpp"
12
13// Default Constructor
14CbcHeuristicDivePseudoCost::CbcHeuristicDivePseudoCost() 
15  :CbcHeuristicDive()
16{
17}
18
19// Constructor from model
20CbcHeuristicDivePseudoCost::CbcHeuristicDivePseudoCost(CbcModel & model)
21  :CbcHeuristicDive(model)
22{
23}
24
25// Destructor
26CbcHeuristicDivePseudoCost::~CbcHeuristicDivePseudoCost ()
27{
28}
29
30// Clone
31CbcHeuristicDivePseudoCost *
32CbcHeuristicDivePseudoCost::clone() const
33{
34  return new CbcHeuristicDivePseudoCost(*this);
35}
36
37// Create C++ lines to get to current state
38void 
39CbcHeuristicDivePseudoCost::generateCpp( FILE * fp) 
40{
41  CbcHeuristicDivePseudoCost other;
42  fprintf(fp,"0#include \"CbcHeuristicDivePseudoCost.hpp\"\n");
43  fprintf(fp,"3  CbcHeuristicDivePseudoCost heuristicDivePseudoCost(*cbcModel);\n");
44  CbcHeuristic::generateCpp(fp,"heuristicDivePseudoCost");
45  fprintf(fp,"3  cbcModel->addHeuristic(&heuristicDivePseudoCost);\n");
46}
47
48// Copy constructor
49CbcHeuristicDivePseudoCost::CbcHeuristicDivePseudoCost(const CbcHeuristicDivePseudoCost & rhs)
50:
51  CbcHeuristicDive(rhs)
52{
53}
54
55// Assignment operator
56CbcHeuristicDivePseudoCost & 
57CbcHeuristicDivePseudoCost::operator=( const CbcHeuristicDivePseudoCost& rhs)
58{
59  if (this!=&rhs) {
60    CbcHeuristicDive::operator=(rhs);
61  }
62  return *this;
63}
64
65bool
66CbcHeuristicDivePseudoCost::selectVariableToBranch(OsiSolverInterface* solver,
67                                                   const double* newSolution,
68                                                   int& bestColumn,
69                                                   int& bestRound)
70{
71  int numberIntegers = model_->numberIntegers();
72  const int * integerVariable = model_->integerVariable();
73  double integerTolerance = model_->getDblParam(CbcModel::CbcIntegerTolerance);
74
75  // get the LP relaxation solution at the root node
76  double * rootNodeLPSol = model_->continuousSolution();
77
78  // get pseudo costs
79  double * pseudoCostDown = downArray_;
80  double * pseudoCostUp = upArray_;
81
82  bestColumn = -1;
83  bestRound = -1; // -1 rounds down, +1 rounds up
84  double bestScore = -1.0;
85  bool allTriviallyRoundableSoFar = true;
86  for (int i=0; i<numberIntegers; i++) {
87    int iColumn = integerVariable[i];
88    double rootValue=rootNodeLPSol[iColumn];
89    double value=newSolution[iColumn];
90    double fraction=value-floor(value);
91    int round = 0;
92    if (fabs(floor(value+0.5)-value)>integerTolerance) {
93      if (allTriviallyRoundableSoFar||(downLocks_[i]>0&&upLocks_[i]>0)) {
94
95        if (allTriviallyRoundableSoFar&&downLocks_[i]>0&&upLocks_[i]>0) {
96          allTriviallyRoundableSoFar = false;
97          bestScore = -1.0;
98        }
99
100        double pCostDown = pseudoCostDown[i];
101        double pCostUp = pseudoCostUp[i];
102        assert(pCostDown >= 0.0 && pCostUp >= 0.0);
103
104        if(allTriviallyRoundableSoFar&&downLocks_[i]==0&&upLocks_[i]>0)
105            round = 1;
106        else if(allTriviallyRoundableSoFar&&downLocks_[i]>0&&upLocks_[i]==0)
107          round = -1;
108        else if(value - rootValue < -0.4)
109          round = -1;
110        else if(value - rootValue > 0.4)
111          round = 1;
112        else if(fraction < 0.3)
113          round = -1;
114        else if(fraction > 0.7)
115          round = 1;
116        else if(pCostDown < pCostUp)
117          round = -1;
118        else
119          round = 1;
120
121        // calculate score
122        double score;
123        if(round == 1)
124          score = fraction * (pCostDown + 1.0) / (pCostUp + 1.0);
125        else
126          score = (1.0 - fraction) * (pCostUp + 1.0) / (pCostDown + 1.0);
127
128        // if variable is binary, increase its chance of being selected
129        if(solver->isBinary(iColumn))
130          score *= 1000.0;
131       
132        if(score > bestScore) {
133          bestColumn = iColumn;
134          bestScore = score;
135          bestRound = round;
136        }
137      }
138    }
139  }
140
141  return allTriviallyRoundableSoFar;
142}
143void
144CbcHeuristicDivePseudoCost::initializeData()
145{
146  int numberIntegers = model_->numberIntegers();
147  if (!downArray_) {
148    downArray_ = new double [numberIntegers];
149    upArray_ = new double [numberIntegers];
150  }
151  // get pseudo costs
152  model_->fillPseudoCosts(downArray_, upArray_);
153  int diveOptions = when_/100;
154  if (diveOptions) {
155    // pseudo shadow prices
156    int k = diveOptions%100;
157    if (diveOptions>=100) 
158      k +=32;
159    model_->pseudoShadow(k-1);
160    int numberInts=CoinMin(model_->numberObjects(),numberIntegers);
161    OsiObject ** objects = model_->objects();
162    for (int i=0;i<numberInts;i++) {
163      CbcSimpleIntegerDynamicPseudoCost * obj1 =
164        dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(objects[i]) ;
165      if (obj1) {
166        //int iColumn = obj1->columnNumber();
167        double downPseudoCost = 1.0e-2*obj1->downDynamicPseudoCost();
168        double downShadow = obj1->downShadowPrice();
169        double upPseudoCost = 1.0e-2*obj1->upDynamicPseudoCost();
170        double upShadow = obj1->upShadowPrice();
171        downPseudoCost = CoinMax(downPseudoCost,downShadow);
172        downPseudoCost = CoinMax(downPseudoCost,0.001*upShadow);
173        downArray_[i]=downPseudoCost;
174        upPseudoCost = CoinMax(upPseudoCost,upShadow);
175        upPseudoCost = CoinMax(upPseudoCost,0.001*downShadow);
176        upArray_[i]=upPseudoCost;
177      }
178    }
179  }
180}
181// Fix other variables at bounds
182int 
183CbcHeuristicDivePseudoCost::fixOtherVariables(OsiSolverInterface * solver,
184                                              const double * solution,
185                                              PseudoReducedCost * candidate,
186                                              const double * random)
187{
188  const double * lower = solver->getColLower();
189  const double * upper = solver->getColUpper();
190  double integerTolerance = model_->getDblParam(CbcModel::CbcIntegerTolerance);
191  double primalTolerance;
192  solver->getDblParam(OsiPrimalTolerance,primalTolerance);
193
194  int numberIntegers = model_->numberIntegers();
195  const int * integerVariable = model_->integerVariable();
196  const double* reducedCost = solver->getReducedCost();
197  // fix other integer variables that are at their bounds
198  int cnt=0;
199  int numberFree=0;
200  int numberFixedAlready=0;
201  for (int i=0; i<numberIntegers; i++) {
202    int iColumn = integerVariable[i];
203    if (upper[iColumn]>lower[iColumn]) {
204      numberFree++;
205      double value=solution[iColumn];
206      if(value-lower[iColumn]<=integerTolerance) {
207        candidate[cnt].var = iColumn;
208        candidate[cnt++].pseudoRedCost = CoinMax(1.0e-2*reducedCost[iColumn],
209                                                 downArray_[i])*random[i];
210      } else if(upper[iColumn]-value<=integerTolerance) {
211        candidate[cnt].var = iColumn;
212        candidate[cnt++].pseudoRedCost = CoinMax(-1.0e-2*reducedCost[iColumn],
213                                                 downArray_[i])*random[i];
214      }
215    } else {
216      numberFixedAlready++;
217    }
218  }
219#ifdef CLP_INVESTIGATE
220  printf("cutoff %g obj %g - %d free, %d fixed\n",
221         model_->getCutoff(),solver->getObjValue(),numberFree,
222         numberFixedAlready);
223#endif
224  return cnt;
225  //return CbcHeuristicDive::fixOtherVariables(solver, solution,
226  //                                 candidate, random);
227}
Note: See TracBrowser for help on using the repository browser.