source: trunk/Cbc/src/CbcCompareDefault.cpp @ 2464

Last change on this file since 2464 was 2464, checked in by unxusr, 11 months ago

.clang-format with proposal for formatting code

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 10.5 KB
Line 
1// $Id: CbcCompareDefault.cpp 2464 2019-01-03 19:03:23Z unxusr $
2// Copyright (C) 2002, 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//Edwin 11/25/09 carved out of CbcCompareActual
7
8#if defined(_MSC_VER)
9// Turn off compiler warning about long names
10#pragma warning(disable : 4786)
11#endif
12#include <cassert>
13#include <cstdlib>
14#include <cmath>
15#include <cfloat>
16//#define CBC_DEBUG
17
18#include "CbcMessage.hpp"
19#include "CbcModel.hpp"
20#include "CbcTree.hpp"
21#include "CbcCompareActual.hpp"
22#include "CoinError.hpp"
23#include "CbcCompareDefault.hpp"
24/** Default Constructor
25
26*/
27CbcCompareDefault::CbcCompareDefault()
28  : CbcCompareBase()
29  , weight_(-1.0)
30  , saveWeight_(0.0)
31  , cutoff_(COIN_DBL_MAX)
32  , bestPossible_(-COIN_DBL_MAX)
33  , numberSolutions_(0)
34  , treeSize_(0)
35  , breadthDepth_(5)
36  , startNodeNumber_(-1)
37  , afterNodeNumber_(-1)
38  , setupForDiving_(false)
39{
40  test_ = this;
41}
42
43// Constructor with weight
44CbcCompareDefault::CbcCompareDefault(double weight)
45  : CbcCompareBase()
46  , weight_(weight)
47  , saveWeight_(0.0)
48  , cutoff_(COIN_DBL_MAX)
49  , bestPossible_(-COIN_DBL_MAX)
50  , numberSolutions_(0)
51  , treeSize_(0)
52  , breadthDepth_(5)
53  , startNodeNumber_(-1)
54  , afterNodeNumber_(-1)
55  , setupForDiving_(false)
56{
57  test_ = this;
58}
59
60// Copy constructor
61CbcCompareDefault::CbcCompareDefault(const CbcCompareDefault &rhs)
62  : CbcCompareBase(rhs)
63
64{
65  weight_ = rhs.weight_;
66  saveWeight_ = rhs.saveWeight_;
67  cutoff_ = rhs.cutoff_;
68  bestPossible_ = rhs.bestPossible_;
69  numberSolutions_ = rhs.numberSolutions_;
70  treeSize_ = rhs.treeSize_;
71  breadthDepth_ = rhs.breadthDepth_;
72  startNodeNumber_ = rhs.startNodeNumber_;
73  afterNodeNumber_ = rhs.afterNodeNumber_;
74  setupForDiving_ = rhs.setupForDiving_;
75}
76
77// Clone
78CbcCompareBase *
79CbcCompareDefault::clone() const
80{
81  return new CbcCompareDefault(*this);
82}
83
84// Assignment operator
85CbcCompareDefault &
86CbcCompareDefault::operator=(const CbcCompareDefault &rhs)
87{
88  if (this != &rhs) {
89    CbcCompareBase::operator=(rhs);
90    weight_ = rhs.weight_;
91    saveWeight_ = rhs.saveWeight_;
92    cutoff_ = rhs.cutoff_;
93    bestPossible_ = rhs.bestPossible_;
94    numberSolutions_ = rhs.numberSolutions_;
95    treeSize_ = rhs.treeSize_;
96    breadthDepth_ = rhs.breadthDepth_;
97    startNodeNumber_ = rhs.startNodeNumber_;
98    afterNodeNumber_ = rhs.afterNodeNumber_;
99    setupForDiving_ = rhs.setupForDiving_;
100  }
101  return *this;
102}
103
104// Destructor
105CbcCompareDefault::~CbcCompareDefault()
106{
107}
108
109// Returns true if y better than x
110bool CbcCompareDefault::test(CbcNode *x, CbcNode *y)
111{
112  if (startNodeNumber_ >= 0) {
113    // Diving
114    int nX = x->nodeNumber();
115    int nY = y->nodeNumber();
116    if (nY == startNodeNumber_)
117      return true;
118    else if (nX == startNodeNumber_)
119      return false;
120    if (nX >= afterNodeNumber_ && nY < afterNodeNumber_)
121      return false;
122    else if (nY >= afterNodeNumber_ && nX < afterNodeNumber_)
123      return true;
124    // treat as depth first
125    int depthX = x->depth();
126    int depthY = y->depth();
127    if (depthX != depthY) {
128      return depthX < depthY;
129    } else {
130      double weight = CoinMax(weight_, 1.0e-9);
131      double testX = x->objectiveValue() + weight * x->numberUnsatisfied();
132      double testY = y->objectiveValue() + weight * y->numberUnsatisfied();
133      if (testX != testY)
134        return testX > testY;
135      else
136        return equalityTest(x, y); // so ties will be broken in consistent manner
137    }
138  }
139  if (!weight_) {
140    double testX = x->objectiveValue() + 1.0e-9 * x->numberUnsatisfied();
141    double testY = y->objectiveValue() + 1.0e-9 * y->numberUnsatisfied();
142    if (testX != testY)
143      return testX > testY;
144    else
145      return equalityTest(x, y); // so ties will be broken in consistent manner
146  }
147  //weight_=0.0;
148  if ((weight_ == -1.0 && (y->depth() > breadthDepth_ && x->depth() > breadthDepth_)) || weight_ == -3.0 || weight_ == -2.0) {
149    int adjust = (weight_ == -3.0) ? 10000 : 0;
150    // before solution
151    /*printf("x %d %d %g, y %d %d %g\n",
152           x->numberUnsatisfied(),x->depth(),x->objectiveValue(),
153           y->numberUnsatisfied(),y->depth(),y->objectiveValue()); */
154    if (x->numberUnsatisfied() > y->numberUnsatisfied() + adjust) {
155      return true;
156    } else if (x->numberUnsatisfied() < y->numberUnsatisfied() - adjust) {
157      return false;
158    } else {
159      int depthX = x->depth();
160      int depthY = y->depth();
161      if (depthX != depthY)
162        return depthX < depthY;
163      else
164        return equalityTest(x, y); // so ties will be broken in consistent manner
165    }
166  } else {
167    // always choose *greatest* depth if both <= breadthDepth_ otherwise <= breadthDepth_ if just one
168    int depthX = x->depth();
169    int depthY = y->depth();
170    /*if ((depthX==4&&depthY==5)||(depthX==5&&depthY==4))
171          printf("X %x depth %d, Y %x depth %d, breadth %d\n",
172          x,depthX,y,depthY,breadthDepth_);*/
173    if (depthX <= breadthDepth_ || depthY <= breadthDepth_) {
174      if (depthX <= breadthDepth_ && depthY <= breadthDepth_) {
175        if (depthX != depthY) {
176          return depthX < depthY;
177        }
178      } else {
179        assert(depthX != depthY);
180        return depthX < depthY;
181      }
182    }
183    // after solution ?
184#define THRESH2 0.999
185#define TRY_THIS 0
186#if TRY_THIS == 0
187    double weight = CoinMax(weight_, 1.0e-9);
188    double testX = x->objectiveValue() + weight * x->numberUnsatisfied();
189    double testY = y->objectiveValue() + weight * y->numberUnsatisfied();
190#elif TRY_THIS == 1
191    /* compute what weight would have to be to hit target
192           then reverse sign as large weight good */
193    double target = (1.0 - THRESH2) * bestPossible_ + THRESH2 * cutoff_;
194    double weight;
195    weight = (target - x->objectiveValue()) / static_cast<double>(x->numberUnsatisfied());
196    double testX = -weight;
197    weight = (target - y->objectiveValue()) / static_cast<double>(y->numberUnsatisfied());
198    double testY = -weight;
199#elif TRY_THIS == 2
200    // Use estimates
201    double testX = x->guessedObjectiveValue();
202    double testY = y->guessedObjectiveValue();
203#elif TRY_THIS == 3
204#define THRESH 0.95
205    // Use estimates
206    double testX = x->guessedObjectiveValue();
207    double testY = y->guessedObjectiveValue();
208    if (x->objectiveValue() - bestPossible_ > THRESH * (cutoff_ - bestPossible_))
209      testX *= 2.0; // make worse
210    if (y->objectiveValue() - bestPossible_ > THRESH * (cutoff_ - bestPossible_))
211      testY *= 2.0; // make worse
212#endif
213    if (testX != testY)
214      return testX > testY;
215    else
216      return equalityTest(x, y); // so ties will be broken in consistent manner
217  }
218}
219/*
220  Change the weight attached to unsatisfied integer variables, unless it's
221  fairly early on in the search and all solutions to date are heuristic.
222*/
223bool CbcCompareDefault::newSolution(CbcModel *model,
224  double objectiveAtContinuous,
225  int numberInfeasibilitiesAtContinuous)
226{
227  cutoff_ = model->getCutoff();
228  if (model->getSolutionCount() == model->getNumberHeuristicSolutions() && model->getSolutionCount() < 5 && model->getNodeCount() < 500)
229    return (false); // solution was got by rounding
230  // set to get close to this solution
231  double costPerInteger = (model->getObjValue() - objectiveAtContinuous) / static_cast<double>(numberInfeasibilitiesAtContinuous);
232  weight_ = 0.95 * costPerInteger;
233  saveWeight_ = 0.95 * weight_;
234  numberSolutions_++;
235  //if (numberSolutions_>5)
236  //weight_ =0.0; // this searches on objective
237  return (true);
238}
239// This allows method to change behavior
240bool CbcCompareDefault::every1000Nodes(CbcModel *model, int numberNodes)
241{
242#ifdef JJF_ZERO
243  // was
244  if (numberNodes > 10000)
245    weight_ = 0.0; // this searches on objective
246  // get size of tree
247  treeSize_ = model->tree()->size();
248#else
249  double saveWeight = weight_;
250  int numberNodes1000 = numberNodes / 1000;
251  if (numberNodes > 10000) {
252    weight_ = 0.0; // this searches on objective
253    // but try a bit of other stuff
254    if ((numberNodes1000 % 4) == 1)
255      weight_ = saveWeight_;
256  } else if (numberNodes == 1000 && weight_ == -2.0) {
257    weight_ = -1.0; // Go to depth first
258  }
259  // get size of tree
260  treeSize_ = model->tree()->size();
261  if (treeSize_ > 10000) {
262    int n1 = model->solver()->getNumRows() + model->solver()->getNumCols();
263    int n2 = model->numberObjects();
264    double size = n1 * 0.1 + n2 * 2.0;
265    // set weight to reduce size most of time
266    if (treeSize_ * (size + 100.0) > 5.0e7)
267      weight_ = -3.0;
268    else if ((numberNodes1000 % 4) == 0 && treeSize_ * size > 1.0e6)
269      weight_ = -1.0;
270    else if ((numberNodes1000 % 4) == 1)
271      weight_ = 0.0;
272    else
273      weight_ = saveWeight_;
274  }
275#endif
276  //return numberNodes==11000; // resort if first time
277  return (weight_ != saveWeight);
278}
279// Start dive
280void CbcCompareDefault::startDive(CbcModel *model)
281{
282  // Get best - using ? criterion
283  double saveWeight = weight_;
284  weight_ = 0.5 * saveWeight_; //0.0;
285  // Switch off to get best
286  startNodeNumber_ = -1;
287  afterNodeNumber_ = -1;
288  CbcNode *best = model->tree()->bestAlternate();
289  startNodeNumber_ = best->nodeNumber();
290  // send signal to setComparison
291  setupForDiving_ = true;
292  /*
293      TODO (review when fixing cleanDive and setComparison)
294      Both afterNodeNumber_ and weight_ must not change
295      after setComparison is invoked, as that will change
296      the behaviour of test(). I replaced the overload on
297      afterNodeNumber_ (magic number -2) with a boolean. Weight_
298      is more problematic. Either it's correct before calling
299      setComparison, or it needs to be cut from the tie-breaking
300      part of test() during a dive, or there needs to be a new
301      attribute to save and restore it around the dive. Otherwise
302      heap checks fail in debug builds with Visual Studio.
303     
304      Given that weight_ was restored immediately after the call
305      to setComparison, there should be no change in behaviour
306      in terms of calls to test().
307      -- lh, 100921 --
308    */
309  afterNodeNumber_ = model->tree()->maximumNodeNumber();
310  weight_ = saveWeight;
311  // redo tree
312  model->tree()->setComparison(*this);
313  setupForDiving_ = false;
314}
315// Clean up dive
316void CbcCompareDefault::cleanDive()
317{
318  if (setupForDiving_ == false) {
319    // switch off
320    startNodeNumber_ = -1;
321    afterNodeNumber_ = -1;
322  }
323}
324
325// Create C++ lines to get to current state
326void CbcCompareDefault::generateCpp(FILE *fp)
327{
328  CbcCompareDefault other;
329  fprintf(fp, "0#include \"CbcCompareActual.hpp\"\n");
330  fprintf(fp, "3  CbcCompareDefault compare;\n");
331  if (weight_ != other.weight_)
332    fprintf(fp, "3  compare.setWeight(%g);\n", weight_);
333  fprintf(fp, "3  cbcModel->setNodeComparison(compare);\n");
334}
Note: See TracBrowser for help on using the repository browser.