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

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

Creating new stable branch 2.4 from trunk (rev 1270)

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 11.6 KB
Line 
1/* $Id: CbcCompareActual.cpp 1271 2009-11-05 15:57:25Z forrest $ */
2// Copyright (C) 2004, 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#include <cassert>
9#include <cstdlib>
10#include <cmath>
11#include <cfloat>
12//#define CBC_DEBUG
13
14#include "CbcMessage.hpp"
15#include "CbcModel.hpp"
16#include "CbcTree.hpp"
17#include "CbcCompareActual.hpp"
18#include "CoinError.hpp"
19
20
21/** Default Constructor
22
23*/
24CbcCompareDepth::CbcCompareDepth ()
25  : CbcCompareBase()
26{
27  test_=this;
28}
29
30// Copy constructor
31CbcCompareDepth::CbcCompareDepth ( const CbcCompareDepth & rhs)
32  :CbcCompareBase(rhs)
33
34{
35}
36
37// Clone
38CbcCompareBase *
39CbcCompareDepth::clone() const
40{
41  return new CbcCompareDepth(*this);
42}
43
44// Assignment operator
45CbcCompareDepth & 
46CbcCompareDepth::operator=( const CbcCompareDepth& rhs)
47{
48  if (this!=&rhs) {
49    CbcCompareBase::operator=(rhs);
50  }
51  return *this;
52}
53
54// Destructor
55CbcCompareDepth::~CbcCompareDepth ()
56{
57}
58
59// Returns true if y better than x
60bool 
61CbcCompareDepth::test (CbcNode * x, CbcNode * y)
62{
63  int testX = x->depth();
64  int testY = y->depth();
65  if (testX!=testY)
66    return testX < testY;
67  else
68    return equalityTest(x,y); // so ties will be broken in consistent manner
69}
70// Create C++ lines to get to current state
71void
72CbcCompareDepth::generateCpp( FILE * fp) 
73{
74  fprintf(fp,"0#include \"CbcCompareActual.hpp\"\n");
75  fprintf(fp,"3  CbcCompareDepth compare;\n");
76  fprintf(fp,"3  cbcModel->setNodeComparison(compare);\n");
77}
78
79/** Default Constructor
80
81*/
82CbcCompareObjective::CbcCompareObjective ()
83  : CbcCompareBase()
84{
85  test_=this;
86}
87
88// Copy constructor
89CbcCompareObjective::CbcCompareObjective ( const CbcCompareObjective & rhs)
90  :CbcCompareBase(rhs)
91
92{
93}
94
95// Clone
96CbcCompareBase *
97CbcCompareObjective::clone() const
98{
99  return new CbcCompareObjective(*this);
100}
101
102// Assignment operator
103CbcCompareObjective & 
104CbcCompareObjective::operator=( const CbcCompareObjective& rhs)
105{
106  if (this!=&rhs) {
107    CbcCompareBase::operator=(rhs);
108  }
109  return *this;
110}
111
112// Destructor
113CbcCompareObjective::~CbcCompareObjective ()
114{
115}
116
117// Returns true if y better than x
118bool 
119CbcCompareObjective::test (CbcNode * x, CbcNode * y)
120{
121  double testX = x->objectiveValue();
122  double testY = y->objectiveValue();
123  if (testX!=testY)
124    return testX > testY;
125  else
126    return equalityTest(x,y); // so ties will be broken in consistent manner
127}
128// Create C++ lines to get to current state
129void
130CbcCompareObjective::generateCpp( FILE * fp) 
131{
132  fprintf(fp,"0#include \"CbcCompareActual.hpp\"\n");
133  fprintf(fp,"3  CbcCompareObjective compare;\n");
134  fprintf(fp,"3  cbcModel->setNodeComparison(compare);\n");
135}
136
137
138/** Default Constructor
139
140*/
141CbcCompareDefault::CbcCompareDefault ()
142  : CbcCompareBase(),
143    weight_(-1.0),
144    saveWeight_(0.0),
145    cutoff_(COIN_DBL_MAX),
146    bestPossible_(-COIN_DBL_MAX),
147    numberSolutions_(0),
148    treeSize_(0),
149    breadthDepth_(5)
150{
151  test_=this;
152}
153
154// Constructor with weight
155CbcCompareDefault::CbcCompareDefault (double weight) 
156  : CbcCompareBase(),
157    weight_(weight) ,
158    saveWeight_(0.0),
159    cutoff_(COIN_DBL_MAX),
160    bestPossible_(-COIN_DBL_MAX),
161    numberSolutions_(0),
162    treeSize_(0),
163    breadthDepth_(5)
164{
165  test_=this;
166}
167
168
169// Copy constructor
170CbcCompareDefault::CbcCompareDefault ( const CbcCompareDefault & rhs)
171  :CbcCompareBase(rhs)
172
173{
174  weight_=rhs.weight_;
175  saveWeight_ = rhs.saveWeight_;
176  cutoff_ = rhs.cutoff_;
177  bestPossible_ = rhs.bestPossible_;
178  numberSolutions_=rhs.numberSolutions_;
179  treeSize_ = rhs.treeSize_;
180  breadthDepth_ = rhs.breadthDepth_;
181}
182
183// Clone
184CbcCompareBase *
185CbcCompareDefault::clone() const
186{
187  return new CbcCompareDefault(*this);
188}
189
190// Assignment operator
191CbcCompareDefault & 
192CbcCompareDefault::operator=( const CbcCompareDefault& rhs)
193{
194  if (this!=&rhs) {
195    CbcCompareBase::operator=(rhs);
196    weight_=rhs.weight_;
197    saveWeight_ = rhs.saveWeight_;
198    cutoff_ = rhs.cutoff_;
199    bestPossible_ = rhs.bestPossible_;
200    numberSolutions_=rhs.numberSolutions_;
201    treeSize_ = rhs.treeSize_;
202    breadthDepth_ = rhs.breadthDepth_;
203  }
204  return *this;
205}
206
207// Destructor
208CbcCompareDefault::~CbcCompareDefault ()
209{
210}
211
212// Returns true if y better than x
213bool 
214CbcCompareDefault::test (CbcNode * x, CbcNode * y)
215{
216#if 0
217  // always choose *smallest* depth if one or both <= breadthDepth_
218  int depthX = x->depth();
219  int depthY = y->depth();
220  if (depthX<=breadthDepth_||depthY<=breadthDepth_) {
221    if (depthX!=depthY)
222      return depthX > depthY;
223    else
224      return equalityTest(x,y); // so ties will be broken in consistent manner
225  }
226  if (weight_==-1.0||weight_==-3.0) {
227    int adjust =  (weight_==-3.0) ? 10000 : 0;
228    // before solution
229    /*printf("x %d %d %g, y %d %d %g\n",
230       x->numberUnsatisfied(),x->depth(),x->objectiveValue(),
231       y->numberUnsatisfied(),y->depth(),y->objectiveValue()); */
232    if (x->numberUnsatisfied() > y->numberUnsatisfied()+adjust) {
233      return true;
234    } else if (x->numberUnsatisfied() < y->numberUnsatisfied()-adjust) {
235      return false;
236    } else {
237      int depthX = x->depth();
238      int depthY = y->depth();
239      if (depthX!=depthY)
240        return depthX < depthY;
241      else
242        return equalityTest(x,y); // so ties will be broken in consistent manner
243    }
244  } else {
245    // after solution
246    double weight = CoinMax(weight_,0.0);
247    double testX =  x->objectiveValue()+ weight*x->numberUnsatisfied();
248    double testY = y->objectiveValue() + weight*y->numberUnsatisfied();
249    if (testX!=testY)
250      return testX > testY;
251    else
252      return equalityTest(x,y); // so ties will be broken in consistent manner
253  }
254#else
255  //weight_=0.0;
256  if ((weight_==-1.0&&(y->depth()>breadthDepth_&&x->depth()>breadthDepth_))||weight_==-3.0||weight_==-2.0) {
257    int adjust =  (weight_==-3.0) ? 10000 : 0;
258    // before solution
259    /*printf("x %d %d %g, y %d %d %g\n",
260       x->numberUnsatisfied(),x->depth(),x->objectiveValue(),
261       y->numberUnsatisfied(),y->depth(),y->objectiveValue()); */
262    if (x->numberUnsatisfied() > y->numberUnsatisfied()+adjust) {
263      return true;
264    } else if (x->numberUnsatisfied() < y->numberUnsatisfied()-adjust) {
265      return false;
266    } else {
267      int depthX = x->depth();
268      int depthY = y->depth();
269      if (depthX!=depthY)
270        return depthX < depthY;
271      else
272        return equalityTest(x,y); // so ties will be broken in consistent manner
273    }
274  } else {
275    // always choose *greatest* depth if both <= breadthDepth_ otherwise <= breadthDepth_ if just one
276    int depthX = x->depth();
277    int depthY = y->depth();
278    /*if ((depthX==4&&depthY==5)||(depthX==5&&depthY==4))
279      printf("X %x depth %d, Y %x depth %d, breadth %d\n",
280      x,depthX,y,depthY,breadthDepth_);*/
281    if (depthX<=breadthDepth_||depthY<=breadthDepth_) {
282      if (depthX<=breadthDepth_&&depthY<=breadthDepth_) {
283        if (depthX!=depthY) {
284          return depthX < depthY;
285        }
286      } else {
287        assert (depthX!=depthY) ;
288        return depthX > depthY;
289      }
290    }
291    // after solution ?
292#define THRESH2 0.999
293#define TRY_THIS 0
294#if TRY_THIS==0
295    double weight = CoinMax(weight_,1.0e-9);
296    double testX =  x->objectiveValue()+ weight*x->numberUnsatisfied();
297    double testY = y->objectiveValue() + weight*y->numberUnsatisfied();
298#elif TRY_THIS==1
299    /* compute what weight would have to be to hit target
300       then reverse sign as large weight good */
301    double target = (1.0-THRESH2)*bestPossible_ + THRESH2*cutoff_;
302    double weight;
303    weight = (target-x->objectiveValue())/
304      static_cast<double>(x->numberUnsatisfied());
305    double testX = - weight;
306    weight = (target-y->objectiveValue())/
307      static_cast<double>(y->numberUnsatisfied());
308    double testY = - weight;
309#elif TRY_THIS==2
310    // Use estimates
311    double testX = x->guessedObjectiveValue();
312    double testY = y->guessedObjectiveValue();
313#elif TRY_THIS==3
314#define THRESH 0.95
315    // Use estimates
316    double testX = x->guessedObjectiveValue();
317    double testY = y->guessedObjectiveValue();
318    if (x->objectiveValue()-bestPossible_>THRESH*(cutoff_-bestPossible_))
319      testX *= 2.0; // make worse
320    if (y->objectiveValue()-bestPossible_>THRESH*(cutoff_-bestPossible_))
321      testY *= 2.0; // make worse
322#endif
323    if (testX!=testY)
324      return testX > testY;
325    else
326      return equalityTest(x,y); // so ties will be broken in consistent manner
327  }
328#endif
329}
330// This allows method to change behavior as it is called
331// after each solution
332void 
333CbcCompareDefault::newSolution(CbcModel * model,
334                               double objectiveAtContinuous,
335                               int numberInfeasibilitiesAtContinuous) 
336{
337  cutoff_ = model->getCutoff();
338  if (model->getSolutionCount()==model->getNumberHeuristicSolutions()&&
339      model->getSolutionCount()<5&&model->getNodeCount()<500)
340    return; // solution was got by rounding
341  // set to get close to this solution
342  double costPerInteger = 
343    (model->getObjValue()-objectiveAtContinuous)/
344    static_cast<double> (numberInfeasibilitiesAtContinuous);
345  weight_ = 0.95*costPerInteger;
346  saveWeight_ = 0.95*weight_;
347  numberSolutions_++;
348  //if (numberSolutions_>5)
349  //weight_ =0.0; // this searches on objective
350}
351// This allows method to change behavior
352bool 
353CbcCompareDefault::every1000Nodes(CbcModel * model, int numberNodes)
354{
355#if 0
356  // was
357  if (numberNodes>10000)
358    weight_ =0.0; // this searches on objective
359  // get size of tree
360  treeSize_ = model->tree()->size();
361#else
362  double saveWeight=weight_;
363  int numberNodes1000 = numberNodes/1000;
364  if (numberNodes>10000) {
365    weight_ =0.0; // this searches on objective
366    // but try a bit of other stuff
367    if ((numberNodes1000%4)==1)
368      weight_=saveWeight_;
369  } else if (numberNodes==1000&&weight_==-2.0) {
370    weight_=-1.0; // Go to depth first
371  }
372  // get size of tree
373  treeSize_ = model->tree()->size();
374  if (treeSize_>10000) {
375    int n1 = model->solver()->getNumRows()+model->solver()->getNumCols();
376    int n2 = model->numberObjects();
377    double size = n1*0.1 + n2*2.0;
378    // set weight to reduce size most of time
379    if (treeSize_*(size+100.0)>5.0e7)
380      weight_=-3.0;
381    else if ((numberNodes1000%4)==0&&treeSize_*size>1.0e6)
382      weight_=-1.0;
383    else if ((numberNodes1000%4)==1)
384      weight_=0.0;
385    else
386      weight_=saveWeight_;
387  }
388#endif
389  //return numberNodes==11000; // resort if first time
390  return (weight_!=saveWeight);
391}
392
393// Create C++ lines to get to current state
394void
395CbcCompareDefault::generateCpp( FILE * fp) 
396{
397  CbcCompareDefault other;
398  fprintf(fp,"0#include \"CbcCompareActual.hpp\"\n");
399  fprintf(fp,"3  CbcCompareDefault compare;\n");
400  if (weight_!=other.weight_)
401    fprintf(fp,"3  compare.setWeight(%g);\n",weight_);
402  fprintf(fp,"3  cbcModel->setNodeComparison(compare);\n");
403}
404
405/** Default Constructor
406
407*/
408CbcCompareEstimate::CbcCompareEstimate ()
409  : CbcCompareBase()
410{
411  test_=this;
412}
413
414// Copy constructor
415CbcCompareEstimate::CbcCompareEstimate ( const CbcCompareEstimate & rhs)
416  :CbcCompareBase(rhs)
417
418{
419}
420
421// Clone
422CbcCompareBase *
423CbcCompareEstimate::clone() const
424{
425  return new CbcCompareEstimate(*this);
426}
427
428// Assignment operator
429CbcCompareEstimate & 
430CbcCompareEstimate::operator=( const CbcCompareEstimate& rhs)
431{
432  if (this!=&rhs) {
433    CbcCompareBase::operator=(rhs);
434  }
435  return *this;
436}
437
438// Destructor
439CbcCompareEstimate::~CbcCompareEstimate ()
440{
441}
442
443// Returns true if y better than x
444bool 
445CbcCompareEstimate::test (CbcNode * x, CbcNode * y)
446{
447  double testX = x->guessedObjectiveValue();
448  double testY = y->guessedObjectiveValue();
449  if (testX!=testY)
450    return testX > testY;
451  else
452    return equalityTest(x,y); // so ties will be broken in consistent manner
453}
454
455// Create C++ lines to get to current state
456void
457CbcCompareEstimate::generateCpp( FILE * fp) 
458{
459  fprintf(fp,"0#include \"CbcCompareActual.hpp\"\n");
460  fprintf(fp,"3  CbcCompareEstimate compare;\n");
461  fprintf(fp,"3  cbcModel->setNodeComparison(compare);\n");
462}
Note: See TracBrowser for help on using the repository browser.