source: branches/devel/Cbc/src/CbcCompareActual.cpp @ 606

Last change on this file since 606 was 574, checked in by forrest, 13 years ago

probably breaking everything

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