source: trunk/Cbc/src/CbcCompareDefault.cpp @ 1899

Last change on this file since 1899 was 1899, checked in by stefan, 6 years ago

fixup svn properties

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