source: stable/2.0/Cbc/src/CbcCompareActual.cpp @ 905

Last change on this file since 905 was 905, checked in by ladanyi, 13 years ago

include cstdlib before cmath to get things to compile on AIX with xlC (same as changeset 904 in trunk)

  • 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    ((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>5.0e7)
341      weight_=-1.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.