source: branches/sandbox/Cbc/src/CbcCompareActual.cpp @ 1286

Last change on this file since 1286 was 1286, checked in by EdwinStraver, 10 years ago

Changed formatting using AStyle -A4 -p

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 12.8 KB
Line 
1/* $Id: CbcCompareActual.cpp 1286 2009-11-09 23:33:07Z EdwinStraver $ */
2// Copyright (C) 2004, International Business Machines
3// Corporation and others.  All Rights Reserved.
4#if defined(_MSC_VER)
5// Turn off compiler warning about long names
6#  pragma warning(disable:4786)
7#endif
8#include <cassert>
9#include <cstdlib>
10#include <cmath>
11#include <cfloat>
12//#define CBC_DEBUG
13
14#include "CbcMessage.hpp"
15#include "CbcModel.hpp"
16#include "CbcTree.hpp"
17#include "CbcCompareActual.hpp"
18#include "CoinError.hpp"
19
20
21/** Default Constructor
22
23*/
24CbcCompareDepth::CbcCompareDepth ()
25        : CbcCompareBase()
26{
27    test_ = this;
28}
29
30// Copy constructor
31CbcCompareDepth::CbcCompareDepth ( const CbcCompareDepth & rhs)
32        : CbcCompareBase(rhs)
33
34{
35}
36
37// Clone
38CbcCompareBase *
39CbcCompareDepth::clone() const
40{
41    return new CbcCompareDepth(*this);
42}
43
44// Assignment operator
45CbcCompareDepth &
46CbcCompareDepth::operator=( const CbcCompareDepth & rhs)
47{
48    if (this != &rhs) {
49        CbcCompareBase::operator=(rhs);
50    }
51    return *this;
52}
53
54// Destructor
55CbcCompareDepth::~CbcCompareDepth ()
56{
57}
58
59// Returns true if y better than x
60bool
61CbcCompareDepth::test (CbcNode * x, CbcNode * y)
62{
63    int testX = x->depth();
64    int testY = y->depth();
65    if (testX != testY)
66        return testX < testY;
67    else
68        return equalityTest(x, y); // so ties will be broken in consistent manner
69}
70// Create C++ lines to get to current state
71void
72CbcCompareDepth::generateCpp( FILE * fp)
73{
74    fprintf(fp, "0#include \"CbcCompareActual.hpp\"\n");
75    fprintf(fp, "3  CbcCompareDepth compare;\n");
76    fprintf(fp, "3  cbcModel->setNodeComparison(compare);\n");
77}
78
79/** Default Constructor
80
81*/
82CbcCompareObjective::CbcCompareObjective ()
83        : CbcCompareBase()
84{
85    test_ = this;
86}
87
88// Copy constructor
89CbcCompareObjective::CbcCompareObjective ( const CbcCompareObjective & rhs)
90        : CbcCompareBase(rhs)
91
92{
93}
94
95// Clone
96CbcCompareBase *
97CbcCompareObjective::clone() const
98{
99    return new CbcCompareObjective(*this);
100}
101
102// Assignment operator
103CbcCompareObjective &
104CbcCompareObjective::operator=( const CbcCompareObjective & rhs)
105{
106    if (this != &rhs) {
107        CbcCompareBase::operator=(rhs);
108    }
109    return *this;
110}
111
112// Destructor
113CbcCompareObjective::~CbcCompareObjective ()
114{
115}
116
117// Returns true if y better than x
118bool
119CbcCompareObjective::test (CbcNode * x, CbcNode * y)
120{
121    double testX = x->objectiveValue();
122    double testY = y->objectiveValue();
123    if (testX != testY)
124        return testX > testY;
125    else
126        return equalityTest(x, y); // so ties will be broken in consistent manner
127}
128// Create C++ lines to get to current state
129void
130CbcCompareObjective::generateCpp( FILE * fp)
131{
132    fprintf(fp, "0#include \"CbcCompareActual.hpp\"\n");
133    fprintf(fp, "3  CbcCompareObjective compare;\n");
134    fprintf(fp, "3  cbcModel->setNodeComparison(compare);\n");
135}
136
137
138/** Default Constructor
139
140*/
141CbcCompareDefault::CbcCompareDefault ()
142        : CbcCompareBase(),
143        weight_(-1.0),
144        saveWeight_(0.0),
145        cutoff_(COIN_DBL_MAX),
146        bestPossible_(-COIN_DBL_MAX),
147        numberSolutions_(0),
148        treeSize_(0),
149        breadthDepth_(5)
150{
151    test_ = this;
152}
153
154// Constructor with weight
155CbcCompareDefault::CbcCompareDefault (double weight)
156        : CbcCompareBase(),
157        weight_(weight) ,
158        saveWeight_(0.0),
159        cutoff_(COIN_DBL_MAX),
160        bestPossible_(-COIN_DBL_MAX),
161        numberSolutions_(0),
162        treeSize_(0),
163        breadthDepth_(5)
164{
165    test_ = this;
166}
167
168
169// Copy constructor
170CbcCompareDefault::CbcCompareDefault ( const CbcCompareDefault & rhs)
171        : CbcCompareBase(rhs)
172
173{
174    weight_ = rhs.weight_;
175    saveWeight_ = rhs.saveWeight_;
176    cutoff_ = rhs.cutoff_;
177    bestPossible_ = rhs.bestPossible_;
178    numberSolutions_ = rhs.numberSolutions_;
179    treeSize_ = rhs.treeSize_;
180    breadthDepth_ = rhs.breadthDepth_;
181}
182
183// Clone
184CbcCompareBase *
185CbcCompareDefault::clone() const
186{
187    return new CbcCompareDefault(*this);
188}
189
190// Assignment operator
191CbcCompareDefault &
192CbcCompareDefault::operator=( const CbcCompareDefault & rhs)
193{
194    if (this != &rhs) {
195        CbcCompareBase::operator=(rhs);
196        weight_ = rhs.weight_;
197        saveWeight_ = rhs.saveWeight_;
198        cutoff_ = rhs.cutoff_;
199        bestPossible_ = rhs.bestPossible_;
200        numberSolutions_ = rhs.numberSolutions_;
201        treeSize_ = rhs.treeSize_;
202        breadthDepth_ = rhs.breadthDepth_;
203    }
204    return *this;
205}
206
207// Destructor
208CbcCompareDefault::~CbcCompareDefault ()
209{
210}
211
212// Returns true if y better than x
213bool
214CbcCompareDefault::test (CbcNode * x, CbcNode * y)
215{
216#if 0
217    // always choose *smallest* depth if one or both <= breadthDepth_
218    int depthX = x->depth();
219    int depthY = y->depth();
220    if (depthX <= breadthDepth_ || depthY <= breadthDepth_) {
221        if (depthX != depthY)
222            return depthX > depthY;
223        else
224            return equalityTest(x, y); // so ties will be broken in consistent manner
225    }
226    if (weight_ == -1.0 || weight_ == -3.0) {
227        int adjust =  (weight_ == -3.0) ? 10000 : 0;
228        // before solution
229        /*printf("x %d %d %g, y %d %d %g\n",
230           x->numberUnsatisfied(),x->depth(),x->objectiveValue(),
231           y->numberUnsatisfied(),y->depth(),y->objectiveValue()); */
232        if (x->numberUnsatisfied() > y->numberUnsatisfied() + adjust) {
233            return true;
234        } else if (x->numberUnsatisfied() < y->numberUnsatisfied() - adjust) {
235            return false;
236        } else {
237            int depthX = x->depth();
238            int depthY = y->depth();
239            if (depthX != depthY)
240                return depthX < depthY;
241            else
242                return equalityTest(x, y); // so ties will be broken in consistent manner
243        }
244    } else {
245        // after solution
246        double weight = CoinMax(weight_, 0.0);
247        double testX =  x->objectiveValue() + weight * x->numberUnsatisfied();
248        double testY = y->objectiveValue() + weight * y->numberUnsatisfied();
249        if (testX != testY)
250            return testX > testY;
251        else
252            return equalityTest(x, y); // so ties will be broken in consistent manner
253    }
254#else
255    //weight_=0.0;
256    if ((weight_ == -1.0 && (y->depth() > breadthDepth_ && x->depth() > breadthDepth_)) || weight_ == -3.0 || weight_ == -2.0) {
257        int adjust =  (weight_ == -3.0) ? 10000 : 0;
258        // before solution
259        /*printf("x %d %d %g, y %d %d %g\n",
260           x->numberUnsatisfied(),x->depth(),x->objectiveValue(),
261           y->numberUnsatisfied(),y->depth(),y->objectiveValue()); */
262        if (x->numberUnsatisfied() > y->numberUnsatisfied() + adjust) {
263            return true;
264        } else if (x->numberUnsatisfied() < y->numberUnsatisfied() - adjust) {
265            return false;
266        } else {
267            int depthX = x->depth();
268            int depthY = y->depth();
269            if (depthX != depthY)
270                return depthX < depthY;
271            else
272                return equalityTest(x, y); // so ties will be broken in consistent manner
273        }
274    } else {
275        // always choose *greatest* depth if both <= breadthDepth_ otherwise <= breadthDepth_ if just one
276        int depthX = x->depth();
277        int depthY = y->depth();
278        /*if ((depthX==4&&depthY==5)||(depthX==5&&depthY==4))
279          printf("X %x depth %d, Y %x depth %d, breadth %d\n",
280          x,depthX,y,depthY,breadthDepth_);*/
281        if (depthX <= breadthDepth_ || depthY <= breadthDepth_) {
282            if (depthX <= breadthDepth_ && depthY <= breadthDepth_) {
283                if (depthX != depthY) {
284                    return depthX < depthY;
285                }
286            } else {
287                assert (depthX != depthY) ;
288                return depthX > depthY;
289            }
290        }
291        // after solution ?
292#define THRESH2 0.999
293#define TRY_THIS 0
294#if TRY_THIS==0
295        double weight = CoinMax(weight_, 1.0e-9);
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 TRY_THIS==3
314#define THRESH 0.95
315    // Use estimates
316    double testX = x->guessedObjectiveValue();
317    double testY = y->guessedObjectiveValue();
318    if (x->objectiveValue() - bestPossible_ > THRESH*(cutoff_ - bestPossible_))
319        testX *= 2.0; // make worse
320    if (y->objectiveValue() - bestPossible_ > THRESH*(cutoff_ - bestPossible_))
321        testY *= 2.0; // make worse
322#endif
323        if (testX != testY)
324            return testX > testY;
325        else
326            return equalityTest(x, y); // so ties will be broken in consistent manner
327    }
328#endif
329}
330// This allows method to change behavior as it is called
331// after each solution
332void
333CbcCompareDefault::newSolution(CbcModel * model,
334                               double objectiveAtContinuous,
335                               int numberInfeasibilitiesAtContinuous)
336{
337    cutoff_ = model->getCutoff();
338    if (model->getSolutionCount() == model->getNumberHeuristicSolutions() &&
339            model->getSolutionCount() < 5 && model->getNodeCount() < 500)
340        return; // solution was got by rounding
341    // set to get close to this solution
342    double costPerInteger =
343        (model->getObjValue() - objectiveAtContinuous) /
344        static_cast<double> (numberInfeasibilitiesAtContinuous);
345    weight_ = 0.95 * costPerInteger;
346    saveWeight_ = 0.95 * weight_;
347    numberSolutions_++;
348    //if (numberSolutions_>5)
349    //weight_ =0.0; // this searches on objective
350}
351// This allows method to change behavior
352bool
353CbcCompareDefault::every1000Nodes(CbcModel * model, int numberNodes)
354{
355#if 0
356    // was
357    if (numberNodes > 10000)
358        weight_ = 0.0; // this searches on objective
359    // get size of tree
360    treeSize_ = model->tree()->size();
361#else
362    double saveWeight = weight_;
363    int numberNodes1000 = numberNodes / 1000;
364    if (numberNodes > 10000) {
365        weight_ = 0.0; // this searches on objective
366        // but try a bit of other stuff
367        if ((numberNodes1000 % 4) == 1)
368            weight_ = saveWeight_;
369    } else if (numberNodes == 1000 && weight_ == -2.0) {
370        weight_ = -1.0; // Go to depth first
371    }
372    // get size of tree
373    treeSize_ = model->tree()->size();
374    if (treeSize_ > 10000) {
375        int n1 = model->solver()->getNumRows() + model->solver()->getNumCols();
376        int n2 = model->numberObjects();
377        double size = n1 * 0.1 + n2 * 2.0;
378        // set weight to reduce size most of time
379        if (treeSize_*(size + 100.0) > 5.0e7)
380            weight_ = -3.0;
381        else if ((numberNodes1000 % 4) == 0 && treeSize_*size > 1.0e6)
382            weight_ = -1.0;
383        else if ((numberNodes1000 % 4) == 1)
384            weight_ = 0.0;
385        else
386            weight_ = saveWeight_;
387    }
388#endif
389    //return numberNodes==11000; // resort if first time
390    return (weight_ != saveWeight);
391}
392
393// Create C++ lines to get to current state
394void
395CbcCompareDefault::generateCpp( FILE * fp)
396{
397    CbcCompareDefault other;
398    fprintf(fp, "0#include \"CbcCompareActual.hpp\"\n");
399    fprintf(fp, "3  CbcCompareDefault compare;\n");
400    if (weight_ != other.weight_)
401        fprintf(fp, "3  compare.setWeight(%g);\n", weight_);
402    fprintf(fp, "3  cbcModel->setNodeComparison(compare);\n");
403}
404
405/** Default Constructor
406
407*/
408CbcCompareEstimate::CbcCompareEstimate ()
409        : CbcCompareBase()
410{
411    test_ = this;
412}
413
414// Copy constructor
415CbcCompareEstimate::CbcCompareEstimate ( const CbcCompareEstimate & rhs)
416        : CbcCompareBase(rhs)
417
418{
419}
420
421// Clone
422CbcCompareBase *
423CbcCompareEstimate::clone() const
424{
425    return new CbcCompareEstimate(*this);
426}
427
428// Assignment operator
429CbcCompareEstimate &
430CbcCompareEstimate::operator=( const CbcCompareEstimate & rhs)
431{
432    if (this != &rhs) {
433        CbcCompareBase::operator=(rhs);
434    }
435    return *this;
436}
437
438// Destructor
439CbcCompareEstimate::~CbcCompareEstimate ()
440{
441}
442
443// Returns true if y better than x
444bool
445CbcCompareEstimate::test (CbcNode * x, CbcNode * y)
446{
447    double testX = x->guessedObjectiveValue();
448    double testY = y->guessedObjectiveValue();
449    if (testX != testY)
450        return testX > testY;
451    else
452        return equalityTest(x, y); // so ties will be broken in consistent manner
453}
454
455// Create C++ lines to get to current state
456void
457CbcCompareEstimate::generateCpp( FILE * fp)
458{
459    fprintf(fp, "0#include \"CbcCompareActual.hpp\"\n");
460    fprintf(fp, "3  CbcCompareEstimate compare;\n");
461    fprintf(fp, "3  cbcModel->setNodeComparison(compare);\n");
462}
Note: See TracBrowser for help on using the repository browser.