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

Last change on this file since 1121 was 1121, checked in by forrest, 11 years ago

compiler warnings, deterministic parallel and stability

  • 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 <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    numberSolutions_(0),
145    treeSize_(0),
146    breadthDepth_(5)
147{
148  test_=this;
149}
150
151// Constructor with weight
152CbcCompareDefault::CbcCompareDefault (double weight) 
153  : CbcCompareBase(),
154    weight_(weight) ,
155    saveWeight_(0.0),
156    numberSolutions_(0),
157    treeSize_(0),
158    breadthDepth_(5)
159{
160  test_=this;
161}
162
163
164// Copy constructor
165CbcCompareDefault::CbcCompareDefault ( const CbcCompareDefault & rhs)
166  :CbcCompareBase(rhs)
167
168{
169  weight_=rhs.weight_;
170  saveWeight_ = rhs.saveWeight_;
171  numberSolutions_=rhs.numberSolutions_;
172  treeSize_ = rhs.treeSize_;
173  breadthDepth_ = rhs.breadthDepth_;
174}
175
176// Clone
177CbcCompareBase *
178CbcCompareDefault::clone() const
179{
180  return new CbcCompareDefault(*this);
181}
182
183// Assignment operator
184CbcCompareDefault & 
185CbcCompareDefault::operator=( const CbcCompareDefault& rhs)
186{
187  if (this!=&rhs) {
188    CbcCompareBase::operator=(rhs);
189    weight_=rhs.weight_;
190    saveWeight_ = rhs.saveWeight_;
191    numberSolutions_=rhs.numberSolutions_;
192    treeSize_ = rhs.treeSize_;
193    breadthDepth_ = rhs.breadthDepth_;
194  }
195  return *this;
196}
197
198// Destructor
199CbcCompareDefault::~CbcCompareDefault ()
200{
201}
202
203// Returns true if y better than x
204bool 
205CbcCompareDefault::test (CbcNode * x, CbcNode * y)
206{
207#if 0
208  // always choose *smallest* depth if one or both <= breadthDepth_
209  int depthX = x->depth();
210  int depthY = y->depth();
211  if (depthX<=breadthDepth_||depthY<=breadthDepth_) {
212    if (depthX!=depthY)
213      return depthX > depthY;
214    else
215      return equalityTest(x,y); // so ties will be broken in consistent manner
216  }
217  if (weight_==-1.0||weight_==-3.0) {
218    int adjust =  (weight_==-3.0) ? 10000 : 0;
219    // before solution
220    /*printf("x %d %d %g, y %d %d %g\n",
221       x->numberUnsatisfied(),x->depth(),x->objectiveValue(),
222       y->numberUnsatisfied(),y->depth(),y->objectiveValue()); */
223    if (x->numberUnsatisfied() > y->numberUnsatisfied()+adjust) {
224      return true;
225    } else if (x->numberUnsatisfied() < y->numberUnsatisfied()-adjust) {
226      return false;
227    } else {
228      int depthX = x->depth();
229      int depthY = y->depth();
230      if (depthX!=depthY)
231        return depthX < depthY;
232      else
233        return equalityTest(x,y); // so ties will be broken in consistent manner
234    }
235  } else {
236    // after solution
237    double weight = CoinMax(weight_,0.0);
238    double testX =  x->objectiveValue()+ weight*x->numberUnsatisfied();
239    double testY = y->objectiveValue() + weight*y->numberUnsatisfied();
240    if (testX!=testY)
241      return testX > testY;
242    else
243      return equalityTest(x,y); // so ties will be broken in consistent manner
244  }
245#else
246  if ((weight_==-1.0&&(y->depth()>breadthDepth_&&x->depth()>breadthDepth_))||weight_==-3.0||weight_==-2.0) {
247    int adjust =  (weight_==-3.0) ? 10000 : 0;
248    // before solution
249    /*printf("x %d %d %g, y %d %d %g\n",
250       x->numberUnsatisfied(),x->depth(),x->objectiveValue(),
251       y->numberUnsatisfied(),y->depth(),y->objectiveValue()); */
252    if (x->numberUnsatisfied() > y->numberUnsatisfied()+adjust) {
253      return true;
254    } else if (x->numberUnsatisfied() < y->numberUnsatisfied()-adjust) {
255      return false;
256    } else {
257      int depthX = x->depth();
258      int depthY = y->depth();
259      if (depthX!=depthY)
260        return depthX < depthY;
261      else
262        return equalityTest(x,y); // so ties will be broken in consistent manner
263    }
264  } else {
265    // always choose *greatest* depth if both <= breadthDepth_ otherwise <= breadthDepth_ if just one
266    int depthX = x->depth();
267    int depthY = y->depth();
268    /*if ((depthX==4&&depthY==5)||(depthX==5&&depthY==4))
269      printf("X %x depth %d, Y %x depth %d, breadth %d\n",
270      x,depthX,y,depthY,breadthDepth_);*/
271    if (depthX<=breadthDepth_||depthY<=breadthDepth_) {
272      if (depthX<=breadthDepth_&&depthY<=breadthDepth_) {
273        if (depthX!=depthY) {
274          return depthX < depthY;
275        }
276      } else {
277        assert (depthX!=depthY) ;
278        return depthX > depthY;
279      }
280    }
281    // after solution
282    double weight = CoinMax(weight_,0.0);
283    double testX =  x->objectiveValue()+ weight*x->numberUnsatisfied();
284    double testY = y->objectiveValue() + weight*y->numberUnsatisfied();
285    if (testX!=testY)
286      return testX > testY;
287    else
288      return equalityTest(x,y); // so ties will be broken in consistent manner
289  }
290#endif
291}
292// This allows method to change behavior as it is called
293// after each solution
294void 
295CbcCompareDefault::newSolution(CbcModel * model,
296                               double objectiveAtContinuous,
297                               int numberInfeasibilitiesAtContinuous) 
298{
299  if (model->getSolutionCount()==model->getNumberHeuristicSolutions()&&
300      model->getSolutionCount()<5&&model->getNodeCount()<500)
301    return; // solution was got by rounding
302  // set to get close to this solution
303  double costPerInteger = 
304    (model->getObjValue()-objectiveAtContinuous)/
305    static_cast<double> (numberInfeasibilitiesAtContinuous);
306  weight_ = 0.95*costPerInteger;
307  saveWeight_ = 0.95*weight_;
308  numberSolutions_++;
309  if (numberSolutions_>5)
310    weight_ =0.0; // this searches on objective
311}
312// This allows method to change behavior
313bool 
314CbcCompareDefault::every1000Nodes(CbcModel * model, int numberNodes)
315{
316#if 0
317  // was
318  if (numberNodes>10000)
319    weight_ =0.0; // this searches on objective
320  // get size of tree
321  treeSize_ = model->tree()->size();
322#else
323  double saveWeight=weight_;
324  int numberNodes1000 = numberNodes/1000;
325  if (numberNodes>10000) {
326    weight_ =0.0; // this searches on objective
327    // but try a bit of other stuff
328    if ((numberNodes1000%4)==1)
329      weight_=saveWeight_;
330  } else if (numberNodes==1000&&weight_==-2.0) {
331    weight_=-1.0; // Go to depth first
332  }
333  // get size of tree
334  treeSize_ = model->tree()->size();
335  if (treeSize_>10000) {
336    int n1 = model->solver()->getNumRows()+model->solver()->getNumCols();
337    int n2 = model->numberObjects();
338    double size = n1*0.1 + n2*2.0;
339    // set weight to reduce size most of time
340    if (treeSize_*(size+100.0)>5.0e7)
341      weight_=-3.0;
342    else if ((numberNodes1000%4)==0&&treeSize_*size>1.0e6)
343      weight_=-1.0;
344    else if ((numberNodes1000%4)==1)
345      weight_=0.0;
346    else
347      weight_=saveWeight_;
348  }
349#endif
350  //return numberNodes==11000; // resort if first time
351  return (weight_!=saveWeight);
352}
353
354// Create C++ lines to get to current state
355void
356CbcCompareDefault::generateCpp( FILE * fp) 
357{
358  CbcCompareDefault other;
359  fprintf(fp,"0#include \"CbcCompareActual.hpp\"\n");
360  fprintf(fp,"3  CbcCompareDefault compare;\n");
361  if (weight_!=other.weight_)
362    fprintf(fp,"3  compare.setWeight(%g);\n",weight_);
363  fprintf(fp,"3  cbcModel->setNodeComparison(compare);\n");
364}
365
366/** Default Constructor
367
368*/
369CbcCompareEstimate::CbcCompareEstimate ()
370  : CbcCompareBase()
371{
372  test_=this;
373}
374
375// Copy constructor
376CbcCompareEstimate::CbcCompareEstimate ( const CbcCompareEstimate & rhs)
377  :CbcCompareBase(rhs)
378
379{
380}
381
382// Clone
383CbcCompareBase *
384CbcCompareEstimate::clone() const
385{
386  return new CbcCompareEstimate(*this);
387}
388
389// Assignment operator
390CbcCompareEstimate & 
391CbcCompareEstimate::operator=( const CbcCompareEstimate& rhs)
392{
393  if (this!=&rhs) {
394    CbcCompareBase::operator=(rhs);
395  }
396  return *this;
397}
398
399// Destructor
400CbcCompareEstimate::~CbcCompareEstimate ()
401{
402}
403
404// Returns true if y better than x
405bool 
406CbcCompareEstimate::test (CbcNode * x, CbcNode * y)
407{
408  double testX = x->guessedObjectiveValue();
409  double testY = y->guessedObjectiveValue();
410  if (testX!=testY)
411    return testX > testY;
412  else
413    return equalityTest(x,y); // so ties will be broken in consistent manner
414}
415
416// Create C++ lines to get to current state
417void
418CbcCompareEstimate::generateCpp( FILE * fp) 
419{
420  fprintf(fp,"0#include \"CbcCompareActual.hpp\"\n");
421  fprintf(fp,"3  CbcCompareEstimate compare;\n");
422  fprintf(fp,"3  cbcModel->setNodeComparison(compare);\n");
423}
Note: See TracBrowser for help on using the repository browser.