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

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

for C and minor change to compare

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