source: stable/2.6/Cbc/src/CbcCompareDefault.cpp @ 2122

Last change on this file since 2122 was 1506, checked in by lou, 9 years ago

Fix `Invalid heap' error in cl debug builds. Add validateHeap method to CbcTree? for future debugging.

File size: 10.9 KB
Line 
1//Edwin 11/25/09 carved out of CbcCompareActual
2#if defined(_MSC_VER)
3// Turn off compiler warning about long names
4#  pragma warning(disable:4786)
5#endif
6#include <cassert>
7#include <cstdlib>
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#include "CbcCompareDefault.hpp"
18/** Default Constructor
19
20*/
21CbcCompareDefault::CbcCompareDefault ()
22        : CbcCompareBase(),
23        weight_(-1.0),
24        saveWeight_(0.0),
25        cutoff_(COIN_DBL_MAX),
26        bestPossible_(-COIN_DBL_MAX),
27        numberSolutions_(0),
28        treeSize_(0),
29        breadthDepth_(5),
30        startNodeNumber_(-1),
31        afterNodeNumber_(-1),
32        setupForDiving_(false)
33{
34    test_ = this;
35}
36
37// Constructor with weight
38CbcCompareDefault::CbcCompareDefault (double weight)
39        : CbcCompareBase(),
40        weight_(weight) ,
41        saveWeight_(0.0),
42        cutoff_(COIN_DBL_MAX),
43        bestPossible_(-COIN_DBL_MAX),
44        numberSolutions_(0),
45        treeSize_(0),
46        breadthDepth_(5),
47        startNodeNumber_(-1),
48        afterNodeNumber_(-1),
49        setupForDiving_(false)
50{
51    test_ = this;
52}
53
54
55// Copy constructor
56CbcCompareDefault::CbcCompareDefault ( const CbcCompareDefault & rhs)
57        : CbcCompareBase(rhs)
58
59{
60    weight_ = rhs.weight_;
61    saveWeight_ = rhs.saveWeight_;
62    cutoff_ = rhs.cutoff_;
63    bestPossible_ = rhs.bestPossible_;
64    numberSolutions_ = rhs.numberSolutions_;
65    treeSize_ = rhs.treeSize_;
66    breadthDepth_ = rhs.breadthDepth_;
67    startNodeNumber_ = rhs.startNodeNumber_;
68    afterNodeNumber_ = rhs.afterNodeNumber_;
69    setupForDiving_ = rhs.setupForDiving_ ;
70}
71
72// Clone
73CbcCompareBase *
74CbcCompareDefault::clone() const
75{
76    return new CbcCompareDefault(*this);
77}
78
79// Assignment operator
80CbcCompareDefault &
81CbcCompareDefault::operator=( const CbcCompareDefault & rhs)
82{
83    if (this != &rhs) {
84        CbcCompareBase::operator=(rhs);
85        weight_ = rhs.weight_;
86        saveWeight_ = rhs.saveWeight_;
87        cutoff_ = rhs.cutoff_;
88        bestPossible_ = rhs.bestPossible_;
89        numberSolutions_ = rhs.numberSolutions_;
90        treeSize_ = rhs.treeSize_;
91        breadthDepth_ = rhs.breadthDepth_;
92        startNodeNumber_ = rhs.startNodeNumber_;
93        afterNodeNumber_ = rhs.afterNodeNumber_;
94        setupForDiving_ = rhs.setupForDiving_ ;
95    }
96    return *this;
97}
98
99// Destructor
100CbcCompareDefault::~CbcCompareDefault ()
101{
102}
103
104// Returns true if y better than x
105bool
106CbcCompareDefault::test (CbcNode * x, CbcNode * y)
107{
108    if (startNodeNumber_ >= 0) {
109        // Diving
110        int nX = x->nodeNumber();
111        int nY = y->nodeNumber();
112        if (nY == startNodeNumber_)
113            return true;
114        else if (nX == startNodeNumber_)
115            return false;
116        if (nX >= afterNodeNumber_ && nY < afterNodeNumber_)
117            return false;
118        else if (nY >= afterNodeNumber_ && nX < afterNodeNumber_)
119            return true;
120        // treat as depth first
121        int depthX = x->depth();
122        int depthY = y->depth();
123        if (depthX != depthY) {
124            return depthX < depthY;
125        } else {
126            double weight = CoinMax(weight_, 1.0e-9);
127            double testX =  x->objectiveValue() + weight * x->numberUnsatisfied();
128            double testY = y->objectiveValue() + weight * y->numberUnsatisfied();
129            if (testX != testY)
130                return testX > testY;
131            else
132                return equalityTest(x, y); // so ties will be broken in consistent manner
133        }
134    }
135    //weight_=0.0;
136    if ((weight_ == -1.0 && (y->depth() > breadthDepth_ && x->depth() > breadthDepth_)) || weight_ == -3.0 || weight_ == -2.0) {
137        int adjust =  (weight_ == -3.0) ? 10000 : 0;
138        // before solution
139        /*printf("x %d %d %g, y %d %d %g\n",
140           x->numberUnsatisfied(),x->depth(),x->objectiveValue(),
141           y->numberUnsatisfied(),y->depth(),y->objectiveValue()); */
142        if (x->numberUnsatisfied() > y->numberUnsatisfied() + adjust) {
143            return true;
144        } else if (x->numberUnsatisfied() < y->numberUnsatisfied() - adjust) {
145            return false;
146        } else {
147            int depthX = x->depth();
148            int depthY = y->depth();
149            if (depthX != depthY)
150                return depthX < depthY;
151            else
152                return equalityTest(x, y); // so ties will be broken in consistent manner
153        }
154    } else {
155        // always choose *greatest* depth if both <= breadthDepth_ otherwise <= breadthDepth_ if just one
156        int depthX = x->depth();
157        int depthY = y->depth();
158        /*if ((depthX==4&&depthY==5)||(depthX==5&&depthY==4))
159          printf("X %x depth %d, Y %x depth %d, breadth %d\n",
160          x,depthX,y,depthY,breadthDepth_);*/
161        if (depthX <= breadthDepth_ || depthY <= breadthDepth_) {
162            if (depthX <= breadthDepth_ && depthY <= breadthDepth_) {
163                if (depthX != depthY) {
164                    return depthX < depthY;
165                }
166            } else {
167                assert (depthX != depthY) ;
168                return depthX > depthY;
169            }
170        }
171        // after solution ?
172#define THRESH2 0.999
173#define TRY_THIS 0
174#if TRY_THIS==0
175        double weight = CoinMax(weight_, 1.0e-9);
176        double testX =  x->objectiveValue() + weight * x->numberUnsatisfied();
177        double testY = y->objectiveValue() + weight * y->numberUnsatisfied();
178#elif TRY_THIS==1
179        /* compute what weight would have to be to hit target
180           then reverse sign as large weight good */
181        double target = (1.0 - THRESH2) * bestPossible_ + THRESH2 * cutoff_;
182        double weight;
183        weight = (target - x->objectiveValue()) /
184                 static_cast<double>(x->numberUnsatisfied());
185        double testX = - weight;
186        weight = (target - y->objectiveValue()) /
187                 static_cast<double>(y->numberUnsatisfied());
188        double testY = - weight;
189#elif TRY_THIS==2
190        // Use estimates
191        double testX = x->guessedObjectiveValue();
192        double testY = y->guessedObjectiveValue();
193#elif TRY_THIS==3
194#define THRESH 0.95
195        // Use estimates
196        double testX = x->guessedObjectiveValue();
197        double testY = y->guessedObjectiveValue();
198        if (x->objectiveValue() - bestPossible_ > THRESH*(cutoff_ - bestPossible_))
199            testX *= 2.0; // make worse
200        if (y->objectiveValue() - bestPossible_ > THRESH*(cutoff_ - bestPossible_))
201            testY *= 2.0; // make worse
202#endif
203        if (testX != testY)
204            return testX > testY;
205        else
206            return equalityTest(x, y); // so ties will be broken in consistent manner
207    }
208}
209/*
210  Change the weight attached to unsatisfied integer variables, unless it's
211  fairly early on in the search and all solutions to date are heuristic.
212*/
213bool
214CbcCompareDefault::newSolution(CbcModel * model,
215                               double objectiveAtContinuous,
216                               int numberInfeasibilitiesAtContinuous)
217{
218    cutoff_ = model->getCutoff();
219    if (model->getSolutionCount() == model->getNumberHeuristicSolutions() &&
220            model->getSolutionCount() < 5 && model->getNodeCount() < 500)
221        return (false) ; // solution was got by rounding
222    // set to get close to this solution
223    double costPerInteger =
224        (model->getObjValue() - objectiveAtContinuous) /
225        static_cast<double> (numberInfeasibilitiesAtContinuous);
226    weight_ = 0.95 * costPerInteger;
227    saveWeight_ = 0.95 * weight_;
228    numberSolutions_++;
229    //if (numberSolutions_>5)
230    //weight_ =0.0; // this searches on objective
231    return (true) ;
232}
233// This allows method to change behavior
234bool
235CbcCompareDefault::every1000Nodes(CbcModel * model, int numberNodes)
236{
237#ifdef JJF_ZERO
238    // was
239    if (numberNodes > 10000)
240        weight_ = 0.0; // this searches on objective
241    // get size of tree
242    treeSize_ = model->tree()->size();
243#else
244    double saveWeight = weight_;
245    int numberNodes1000 = numberNodes / 1000;
246    if (numberNodes > 10000) {
247        weight_ = 0.0; // this searches on objective
248        // but try a bit of other stuff
249        if ((numberNodes1000 % 4) == 1)
250            weight_ = saveWeight_;
251    } else if (numberNodes == 1000 && weight_ == -2.0) {
252        weight_ = -1.0; // Go to depth first
253    }
254    // get size of tree
255    treeSize_ = model->tree()->size();
256    if (treeSize_ > 10000) {
257        int n1 = model->solver()->getNumRows() + model->solver()->getNumCols();
258        int n2 = model->numberObjects();
259        double size = n1 * 0.1 + n2 * 2.0;
260        // set weight to reduce size most of time
261        if (treeSize_*(size + 100.0) > 5.0e7)
262            weight_ = -3.0;
263        else if ((numberNodes1000 % 4) == 0 && treeSize_*size > 1.0e6)
264            weight_ = -1.0;
265        else if ((numberNodes1000 % 4) == 1)
266            weight_ = 0.0;
267        else
268            weight_ = saveWeight_;
269    }
270#endif
271    //return numberNodes==11000; // resort if first time
272    return (weight_ != saveWeight);
273}
274// Start dive
275void
276CbcCompareDefault::startDive(CbcModel * model)
277{
278    // Get best - using ? criterion
279    double saveWeight = weight_;
280    weight_ = 0.5 * saveWeight_; //0.0;
281    // Switch off to get best
282    startNodeNumber_ = -1;
283    afterNodeNumber_ = -1;
284    CbcNode * best = model->tree()->bestAlternate();
285    startNodeNumber_ = best->nodeNumber();
286    // send signal to setComparison
287    setupForDiving_ = true ;
288    /*
289      TODO (review when fixing cleanDive and setComparison)
290      Both afterNodeNumber_ and weight_ must not change
291      after setComparison is invoked, as that will change
292      the behaviour of test(). I replaced the overload on
293      afterNodeNumber_ (magic number -2) with a boolean. Weight_
294      is more problematic. Either it's correct before calling
295      setComparison, or it needs to be cut from the tie-breaking
296      part of test() during a dive, or there needs to be a new
297      attribute to save and restore it around the dive. Otherwise
298      heap checks fail in debug builds with Visual Studio.
299     
300      Given that weight_ was restored immediately after the call
301      to setComparison, there should be no change in behaviour
302      in terms of calls to test().
303      -- lh, 100921 --
304    */
305    afterNodeNumber_ = model->tree()->maximumNodeNumber();
306    weight_ = saveWeight ;
307    // redo tree
308    model->tree()->setComparison(*this);
309    setupForDiving_ = false ;
310}
311// Clean up dive
312void
313CbcCompareDefault::cleanDive()
314{
315    if (setupForDiving_ == false) {
316        // switch off
317        startNodeNumber_ = -1;
318        afterNodeNumber_ = -1;
319    }
320}
321
322// Create C++ lines to get to current state
323void
324CbcCompareDefault::generateCpp( FILE * fp)
325{
326    CbcCompareDefault other;
327    fprintf(fp, "0#include \"CbcCompareActual.hpp\"\n");
328    fprintf(fp, "3  CbcCompareDefault compare;\n");
329    if (weight_ != other.weight_)
330        fprintf(fp, "3  compare.setWeight(%g);\n", weight_);
331    fprintf(fp, "3  cbcModel->setNodeComparison(compare);\n");
332}
333
Note: See TracBrowser for help on using the repository browser.