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

Last change on this file since 862 was 858, checked in by forrest, 12 years ago

force more to depth first if tree too big

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 10.3 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||weight_==-2.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==4&&depthY==5)||(depthX==5&&depthY==4))
268      printf("X %x depth %d, Y %x depth %d, breadth %d\n",
269      x,depthX,y,depthY,breadthDepth_);*/
270    if (depthX<=breadthDepth_||depthY<=breadthDepth_) {
271      if (depthX<=breadthDepth_&&depthY<=breadthDepth_) {
272        if (depthX!=depthY) {
273          return depthX < depthY;
274        }
275      } else {
276        assert (depthX!=depthY) ;
277        return depthX > depthY;
278      }
279    }
280    // after solution
281    double weight = CoinMax(weight_,0.0);
282    double testX =  x->objectiveValue()+ weight*x->numberUnsatisfied();
283    double testY = y->objectiveValue() + weight*y->numberUnsatisfied();
284    if (testX!=testY)
285      return testX > testY;
286    else
287      return equalityTest(x,y); // so ties will be broken in consistent manner
288  }
289#endif
290}
291// This allows method to change behavior as it is called
292// after each solution
293void 
294CbcCompareDefault::newSolution(CbcModel * model,
295                               double objectiveAtContinuous,
296                               int numberInfeasibilitiesAtContinuous) 
297{
298  if (model->getSolutionCount()==model->getNumberHeuristicSolutions()&&
299      model->getSolutionCount()<5&&model->getNodeCount()<500)
300    return; // solution was got by rounding
301  // set to get close to this solution
302  double costPerInteger = 
303    (model->getObjValue()-objectiveAtContinuous)/
304    ((double) numberInfeasibilitiesAtContinuous);
305  weight_ = 0.95*costPerInteger;
306  saveWeight_ = 0.95*weight_;
307  numberSolutions_++;
308  if (numberSolutions_>5)
309    weight_ =0.0; // this searches on objective
310}
311// This allows method to change behavior
312bool 
313CbcCompareDefault::every1000Nodes(CbcModel * model, int numberNodes)
314{
315#if 0
316  // was
317  if (numberNodes>10000)
318    weight_ =0.0; // this searches on objective
319  // get size of tree
320  treeSize_ = model->tree()->size();
321#else
322  double saveWeight=weight_;
323  int numberNodes1000 = numberNodes/1000;
324  if (numberNodes>10000) {
325    weight_ =0.0; // this searches on objective
326    // but try a bit of other stuff
327    if ((numberNodes1000%4)==1)
328      weight_=saveWeight_;
329  } else if (numberNodes==1000&&weight_==-2.0) {
330    weight_=-1.0; // Go to depth first
331  }
332  // get size of tree
333  treeSize_ = model->tree()->size();
334  if (treeSize_>10000) {
335    int n1 = model->solver()->getNumRows()+model->solver()->getNumCols();
336    int n2 = model->numberObjects();
337    double size = n1*0.1 + n2*2.0;
338    // set weight to reduce size most of time
339    if (treeSize_*(size+100.0)>5.0e7)
340      weight_=-3.0;
341    else if ((numberNodes1000%4)==0&&treeSize_*size>1.0e6)
342      weight_=-1.0;
343    else if ((numberNodes1000%4)==1)
344      weight_=0.0;
345    else
346      weight_=saveWeight_;
347  }
348#endif
349  //return numberNodes==11000; // resort if first time
350  return (weight_!=saveWeight);
351}
352
353// Create C++ lines to get to current state
354void
355CbcCompareDefault::generateCpp( FILE * fp) 
356{
357  CbcCompareDefault other;
358  fprintf(fp,"0#include \"CbcCompareActual.hpp\"\n");
359  fprintf(fp,"3  CbcCompareDefault compare;\n");
360  if (weight_!=other.weight_)
361    fprintf(fp,"3  compare.setWeight(%g);\n",weight_);
362  fprintf(fp,"3  cbcModel->setNodeComparison(compare);\n");
363}
364
365/** Default Constructor
366
367*/
368CbcCompareEstimate::CbcCompareEstimate ()
369  : CbcCompareBase()
370{
371  test_=this;
372}
373
374// Copy constructor
375CbcCompareEstimate::CbcCompareEstimate ( const CbcCompareEstimate & rhs)
376  :CbcCompareBase(rhs)
377
378{
379}
380
381// Clone
382CbcCompareBase *
383CbcCompareEstimate::clone() const
384{
385  return new CbcCompareEstimate(*this);
386}
387
388// Assignment operator
389CbcCompareEstimate & 
390CbcCompareEstimate::operator=( const CbcCompareEstimate& rhs)
391{
392  if (this!=&rhs) {
393    CbcCompareBase::operator=(rhs);
394  }
395  return *this;
396}
397
398// Destructor
399CbcCompareEstimate::~CbcCompareEstimate ()
400{
401}
402
403// Returns true if y better than x
404bool 
405CbcCompareEstimate::test (CbcNode * x, CbcNode * y)
406{
407  double testX = x->guessedObjectiveValue();
408  double testY = y->guessedObjectiveValue();
409  if (testX!=testY)
410    return testX > testY;
411  else
412    return equalityTest(x,y); // so ties will be broken in consistent manner
413}
414
415// Create C++ lines to get to current state
416void
417CbcCompareEstimate::generateCpp( FILE * fp) 
418{
419  fprintf(fp,"0#include \"CbcCompareActual.hpp\"\n");
420  fprintf(fp,"3  CbcCompareEstimate compare;\n");
421  fprintf(fp,"3  cbcModel->setNodeComparison(compare);\n");
422}
Note: See TracBrowser for help on using the repository browser.