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

Last change on this file since 1799 was 1799, checked in by forrest, 7 years ago

more logical comparison and out assert on pi for sos

File size: 11.1 KB
Line 
1// $Id$
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    //weight_=0.0;
142    if ((weight_ == -1.0 && (y->depth() > breadthDepth_ && x->depth() > breadthDepth_)) || weight_ == -3.0 || weight_ == -2.0) {
143        int adjust =  (weight_ == -3.0) ? 10000 : 0;
144        // before solution
145        /*printf("x %d %d %g, y %d %d %g\n",
146           x->numberUnsatisfied(),x->depth(),x->objectiveValue(),
147           y->numberUnsatisfied(),y->depth(),y->objectiveValue()); */
148        if (x->numberUnsatisfied() > y->numberUnsatisfied() + adjust) {
149            return true;
150        } else if (x->numberUnsatisfied() < y->numberUnsatisfied() - adjust) {
151            return false;
152        } else {
153            int depthX = x->depth();
154            int depthY = y->depth();
155            if (depthX != depthY)
156                return depthX < depthY;
157            else
158                return equalityTest(x, y); // so ties will be broken in consistent manner
159        }
160    } else {
161        // always choose *greatest* depth if both <= breadthDepth_ otherwise <= breadthDepth_ if just one
162        int depthX = x->depth();
163        int depthY = y->depth();
164        /*if ((depthX==4&&depthY==5)||(depthX==5&&depthY==4))
165          printf("X %x depth %d, Y %x depth %d, breadth %d\n",
166          x,depthX,y,depthY,breadthDepth_);*/
167        if (depthX <= breadthDepth_ || depthY <= breadthDepth_) {
168            if (depthX <= breadthDepth_ && depthY <= breadthDepth_) {
169                if (depthX != depthY) {
170                    return depthX < depthY;
171                }
172            } else {
173                assert (depthX != depthY) ;
174                return depthX < depthY;
175            }
176        }
177        // after solution ?
178#define THRESH2 0.999
179#define TRY_THIS 0
180#if TRY_THIS==0
181        double weight = CoinMax(weight_, 1.0e-9);
182        double testX =  x->objectiveValue() + weight * x->numberUnsatisfied();
183        double testY = y->objectiveValue() + weight * y->numberUnsatisfied();
184#elif TRY_THIS==1
185        /* compute what weight would have to be to hit target
186           then reverse sign as large weight good */
187        double target = (1.0 - THRESH2) * bestPossible_ + THRESH2 * cutoff_;
188        double weight;
189        weight = (target - x->objectiveValue()) /
190                 static_cast<double>(x->numberUnsatisfied());
191        double testX = - weight;
192        weight = (target - y->objectiveValue()) /
193                 static_cast<double>(y->numberUnsatisfied());
194        double testY = - weight;
195#elif TRY_THIS==2
196        // Use estimates
197        double testX = x->guessedObjectiveValue();
198        double testY = y->guessedObjectiveValue();
199#elif TRY_THIS==3
200#define THRESH 0.95
201        // Use estimates
202        double testX = x->guessedObjectiveValue();
203        double testY = y->guessedObjectiveValue();
204        if (x->objectiveValue() - bestPossible_ > THRESH*(cutoff_ - bestPossible_))
205            testX *= 2.0; // make worse
206        if (y->objectiveValue() - bestPossible_ > THRESH*(cutoff_ - bestPossible_))
207            testY *= 2.0; // make worse
208#endif
209        if (testX != testY)
210            return testX > testY;
211        else
212            return equalityTest(x, y); // so ties will be broken in consistent manner
213    }
214}
215/*
216  Change the weight attached to unsatisfied integer variables, unless it's
217  fairly early on in the search and all solutions to date are heuristic.
218*/
219bool
220CbcCompareDefault::newSolution(CbcModel * model,
221                               double objectiveAtContinuous,
222                               int numberInfeasibilitiesAtContinuous)
223{
224    cutoff_ = model->getCutoff();
225    if (model->getSolutionCount() == model->getNumberHeuristicSolutions() &&
226            model->getSolutionCount() < 5 && model->getNodeCount() < 500)
227        return (false) ; // solution was got by rounding
228    // set to get close to this solution
229    double costPerInteger =
230        (model->getObjValue() - objectiveAtContinuous) /
231        static_cast<double> (numberInfeasibilitiesAtContinuous);
232    weight_ = 0.95 * costPerInteger;
233    saveWeight_ = 0.95 * weight_;
234    numberSolutions_++;
235    //if (numberSolutions_>5)
236    //weight_ =0.0; // this searches on objective
237    return (true) ;
238}
239// This allows method to change behavior
240bool
241CbcCompareDefault::every1000Nodes(CbcModel * model, int numberNodes)
242{
243#ifdef JJF_ZERO
244    // was
245    if (numberNodes > 10000)
246        weight_ = 0.0; // this searches on objective
247    // get size of tree
248    treeSize_ = model->tree()->size();
249#else
250    double saveWeight = weight_;
251    int numberNodes1000 = numberNodes / 1000;
252    if (numberNodes > 10000) {
253        weight_ = 0.0; // this searches on objective
254        // but try a bit of other stuff
255        if ((numberNodes1000 % 4) == 1)
256            weight_ = saveWeight_;
257    } else if (numberNodes == 1000 && weight_ == -2.0) {
258        weight_ = -1.0; // Go to depth first
259    }
260    // get size of tree
261    treeSize_ = model->tree()->size();
262    if (treeSize_ > 10000) {
263        int n1 = model->solver()->getNumRows() + model->solver()->getNumCols();
264        int n2 = model->numberObjects();
265        double size = n1 * 0.1 + n2 * 2.0;
266        // set weight to reduce size most of time
267        if (treeSize_*(size + 100.0) > 5.0e7)
268            weight_ = -3.0;
269        else if ((numberNodes1000 % 4) == 0 && treeSize_*size > 1.0e6)
270            weight_ = -1.0;
271        else if ((numberNodes1000 % 4) == 1)
272            weight_ = 0.0;
273        else
274            weight_ = saveWeight_;
275    }
276#endif
277    //return numberNodes==11000; // resort if first time
278    return (weight_ != saveWeight);
279}
280// Start dive
281void
282CbcCompareDefault::startDive(CbcModel * model)
283{
284    // Get best - using ? criterion
285    double saveWeight = weight_;
286    weight_ = 0.5 * saveWeight_; //0.0;
287    // Switch off to get best
288    startNodeNumber_ = -1;
289    afterNodeNumber_ = -1;
290    CbcNode * best = model->tree()->bestAlternate();
291    startNodeNumber_ = best->nodeNumber();
292    // send signal to setComparison
293    setupForDiving_ = true ;
294    /*
295      TODO (review when fixing cleanDive and setComparison)
296      Both afterNodeNumber_ and weight_ must not change
297      after setComparison is invoked, as that will change
298      the behaviour of test(). I replaced the overload on
299      afterNodeNumber_ (magic number -2) with a boolean. Weight_
300      is more problematic. Either it's correct before calling
301      setComparison, or it needs to be cut from the tie-breaking
302      part of test() during a dive, or there needs to be a new
303      attribute to save and restore it around the dive. Otherwise
304      heap checks fail in debug builds with Visual Studio.
305     
306      Given that weight_ was restored immediately after the call
307      to setComparison, there should be no change in behaviour
308      in terms of calls to test().
309      -- lh, 100921 --
310    */
311    afterNodeNumber_ = model->tree()->maximumNodeNumber();
312    weight_ = saveWeight ;
313    // redo tree
314    model->tree()->setComparison(*this);
315    setupForDiving_ = false ;
316}
317// Clean up dive
318void
319CbcCompareDefault::cleanDive()
320{
321    if (setupForDiving_ == false) {
322        // switch off
323        startNodeNumber_ = -1;
324        afterNodeNumber_ = -1;
325    }
326}
327
328// Create C++ lines to get to current state
329void
330CbcCompareDefault::generateCpp( FILE * fp)
331{
332    CbcCompareDefault other;
333    fprintf(fp, "0#include \"CbcCompareActual.hpp\"\n");
334    fprintf(fp, "3  CbcCompareDefault compare;\n");
335    if (weight_ != other.weight_)
336        fprintf(fp, "3  compare.setWeight(%g);\n", weight_);
337    fprintf(fp, "3  cbcModel->setNodeComparison(compare);\n");
338}
339
Note: See TracBrowser for help on using the repository browser.