source: trunk/Cbc/src/CbcHeuristicDivePseudoCost.cpp

Last change on this file was 2467, checked in by unxusr, 10 months ago

spaces after angles

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 8.2 KB
Line 
1/* $Id: CbcHeuristicDivePseudoCost.cpp 2467 2019-01-03 21:26:29Z unxusr $ */
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 "CbcHeuristicDivePseudoCost.hpp"
12#include "CbcStrategy.hpp"
13#include "CbcBranchDynamic.hpp"
14
15// Default Constructor
16CbcHeuristicDivePseudoCost::CbcHeuristicDivePseudoCost()
17  : CbcHeuristicDive()
18{
19}
20
21// Constructor from model
22CbcHeuristicDivePseudoCost::CbcHeuristicDivePseudoCost(CbcModel &model)
23  : CbcHeuristicDive(model)
24{
25}
26
27// Destructor
28CbcHeuristicDivePseudoCost::~CbcHeuristicDivePseudoCost()
29{
30}
31
32// Clone
33CbcHeuristicDivePseudoCost *
34CbcHeuristicDivePseudoCost::clone() const
35{
36  return new CbcHeuristicDivePseudoCost(*this);
37}
38
39// Create C++ lines to get to current state
40void CbcHeuristicDivePseudoCost::generateCpp(FILE *fp)
41{
42  CbcHeuristicDivePseudoCost other;
43  fprintf(fp, "0#include \"CbcHeuristicDivePseudoCost.hpp\"\n");
44  fprintf(fp, "3  CbcHeuristicDivePseudoCost heuristicDivePseudoCost(*cbcModel);\n");
45  CbcHeuristic::generateCpp(fp, "heuristicDivePseudoCost");
46  fprintf(fp, "3  cbcModel->addHeuristic(&heuristicDivePseudoCost);\n");
47}
48
49// Copy constructor
50CbcHeuristicDivePseudoCost::CbcHeuristicDivePseudoCost(const CbcHeuristicDivePseudoCost &rhs)
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 CbcHeuristicDivePseudoCost::selectVariableToBranch(OsiSolverInterface *solver,
66  const double *newSolution,
67  int &bestColumn,
68  int &bestRound)
69{
70  int numberIntegers = model_->numberIntegers();
71  const int *integerVariable = model_->integerVariable();
72  double integerTolerance = model_->getDblParam(CbcModel::CbcIntegerTolerance);
73
74  // get the LP relaxation solution at the root node
75  double *rootNodeLPSol = model_->continuousSolution();
76
77  // get pseudo costs
78  double *pseudoCostDown = downArray_;
79  double *pseudoCostUp = upArray_;
80
81  bestColumn = -1;
82  bestRound = -1; // -1 rounds down, +1 rounds up
83  double bestScore = -1.0;
84  bool allTriviallyRoundableSoFar = true;
85  int bestPriority = COIN_INT_MAX;
86  for (int i = 0; i < numberIntegers; i++) {
87    int iColumn = integerVariable[i];
88    if (!isHeuristicInteger(solver, iColumn))
89      continue;
90    double rootValue = rootNodeLPSol[iColumn];
91    double value = newSolution[iColumn];
92    double fraction = value - floor(value);
93    int round = 0;
94    if (fabs(floor(value + 0.5) - value) > integerTolerance) {
95      if (allTriviallyRoundableSoFar || (downLocks_[i] > 0 && upLocks_[i] > 0)) {
96
97        if (allTriviallyRoundableSoFar && downLocks_[i] > 0 && upLocks_[i] > 0) {
98          allTriviallyRoundableSoFar = false;
99          bestScore = -1.0;
100        }
101
102        double pCostDown = pseudoCostDown[i];
103        double pCostUp = pseudoCostUp[i];
104        assert(pCostDown >= 0.0 && pCostUp >= 0.0);
105
106        if (allTriviallyRoundableSoFar && downLocks_[i] == 0 && upLocks_[i] > 0)
107          round = 1;
108        else if (allTriviallyRoundableSoFar && downLocks_[i] > 0 && upLocks_[i] == 0)
109          round = -1;
110        else if (value - rootValue < -0.4)
111          round = -1;
112        else if (value - rootValue > 0.4)
113          round = 1;
114        else if (fraction < 0.3)
115          round = -1;
116        else if (fraction > 0.7)
117          round = 1;
118        else if (pCostDown < pCostUp)
119          round = -1;
120        else
121          round = 1;
122
123        // calculate score
124        double score;
125        if (round == 1)
126          score = fraction * (pCostDown + 1.0) / (pCostUp + 1.0);
127        else
128          score = (1.0 - fraction) * (pCostUp + 1.0) / (pCostDown + 1.0);
129
130        // if variable is binary, increase its chance of being selected
131        if (solver->isBinary(iColumn))
132          score *= 1000.0;
133
134        // if priorities then use
135        if (priority_) {
136          int thisRound = static_cast< int >(priority_[i].direction);
137          if ((thisRound & 1) != 0)
138            round = ((thisRound & 2) == 0) ? -1 : +1;
139          if (priority_[i].priority > bestPriority) {
140            score = COIN_DBL_MAX;
141          } else if (priority_[i].priority < bestPriority) {
142            bestPriority = static_cast< int >(priority_[i].priority);
143            bestScore = COIN_DBL_MAX;
144          }
145        }
146        if (score > bestScore) {
147          bestColumn = iColumn;
148          bestScore = score;
149          bestRound = round;
150        }
151      }
152    }
153  }
154
155  return allTriviallyRoundableSoFar;
156}
157void CbcHeuristicDivePseudoCost::initializeData()
158{
159  int numberIntegers = model_->numberIntegers();
160  if (!downArray_) {
161    downArray_ = new double[numberIntegers];
162    upArray_ = new double[numberIntegers];
163  }
164  // get pseudo costs
165  model_->fillPseudoCosts(downArray_, upArray_);
166  // allow for -999 -> force to run
167  int diveOptions = (when_ > 0) ? when_ / 100 : 0;
168  if (diveOptions) {
169    // pseudo shadow prices
170    int k = diveOptions % 100;
171    if (diveOptions >= 100)
172      k += 32;
173    model_->pseudoShadow(k - 1);
174    int numberInts = CoinMin(model_->numberObjects(), numberIntegers);
175    OsiObject **objects = model_->objects();
176    for (int i = 0; i < numberInts; i++) {
177      CbcSimpleIntegerDynamicPseudoCost *obj1 = dynamic_cast< CbcSimpleIntegerDynamicPseudoCost * >(objects[i]);
178      if (obj1) {
179        //int iColumn = obj1->columnNumber();
180        double downPseudoCost = 1.0e-2 * obj1->downDynamicPseudoCost();
181        double downShadow = obj1->downShadowPrice();
182        double upPseudoCost = 1.0e-2 * obj1->upDynamicPseudoCost();
183        double upShadow = obj1->upShadowPrice();
184        downPseudoCost = CoinMax(downPseudoCost, downShadow);
185        downPseudoCost = CoinMax(downPseudoCost, 0.001 * upShadow);
186        downArray_[i] = downPseudoCost;
187        upPseudoCost = CoinMax(upPseudoCost, upShadow);
188        upPseudoCost = CoinMax(upPseudoCost, 0.001 * downShadow);
189        upArray_[i] = upPseudoCost;
190      }
191    }
192  }
193}
194// Fix other variables at bounds
195int CbcHeuristicDivePseudoCost::fixOtherVariables(OsiSolverInterface *solver,
196  const double *solution,
197  PseudoReducedCost *candidate,
198  const double *random)
199{
200  const double *lower = solver->getColLower();
201  const double *upper = solver->getColUpper();
202  double integerTolerance = model_->getDblParam(CbcModel::CbcIntegerTolerance);
203  double primalTolerance;
204  solver->getDblParam(OsiPrimalTolerance, primalTolerance);
205
206  int numberIntegers = model_->numberIntegers();
207  const int *integerVariable = model_->integerVariable();
208  const double *reducedCost = solver->getReducedCost();
209  bool fixGeneralIntegers = (switches_ & 65536) != 0;
210  // fix other integer variables that are at their bounds
211  int cnt = 0;
212  int numberFree = 0;
213  int numberFixedAlready = 0;
214  for (int i = 0; i < numberIntegers; i++) {
215    int iColumn = integerVariable[i];
216    if (!isHeuristicInteger(solver, iColumn))
217      continue;
218    if (upper[iColumn] > lower[iColumn]) {
219      numberFree++;
220      double value = solution[iColumn];
221      if (value - lower[iColumn] <= integerTolerance) {
222        candidate[cnt].var = iColumn;
223        candidate[cnt++].pseudoRedCost = CoinMax(1.0e-2 * reducedCost[iColumn],
224                                           downArray_[i])
225          * random[i];
226      } else if (upper[iColumn] - value <= integerTolerance) {
227        candidate[cnt].var = iColumn;
228        candidate[cnt++].pseudoRedCost = CoinMax(-1.0e-2 * reducedCost[iColumn],
229                                           downArray_[i])
230          * random[i];
231      } else if (fixGeneralIntegers && fabs(floor(value + 0.5) - value) <= integerTolerance) {
232        candidate[cnt].var = iColumn;
233        candidate[cnt++].pseudoRedCost = CoinMax(-1.0e-6 * reducedCost[iColumn],
234                                           1.0e-4 * downArray_[i])
235          * random[i];
236      }
237    } else {
238      numberFixedAlready++;
239    }
240  }
241#ifdef CLP_INVESTIGATE
242  printf("cutoff %g obj %g - %d free, %d fixed\n",
243    model_->getCutoff(), solver->getObjValue(), numberFree,
244    numberFixedAlready);
245#endif
246  return cnt;
247  //return CbcHeuristicDive::fixOtherVariables(solver, solution,
248  //                                 candidate, random);
249}
250
251/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
252*/
Note: See TracBrowser for help on using the repository browser.