source: trunk/Cbc/src/CbcCompareActual.cpp @ 1136

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

take out assert

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