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

Last change on this file since 1132 was 1132, checked in by forrest, 10 years ago

chnages to try and make faster

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