source: branches/sandbox/Cbc/src/CbcCompareDefault.cpp @ 1393

Last change on this file since 1393 was 1393, checked in by lou, 10 years ago

Mark #if 0 with JJF_ZERO and #if 1 with JJF_ONE as a historical reference
point.

File size: 9.8 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{
33    test_ = this;
34}
35
36// Constructor with weight
37CbcCompareDefault::CbcCompareDefault (double weight)
38        : CbcCompareBase(),
39        weight_(weight) ,
40        saveWeight_(0.0),
41        cutoff_(COIN_DBL_MAX),
42        bestPossible_(-COIN_DBL_MAX),
43        numberSolutions_(0),
44        treeSize_(0),
45        breadthDepth_(5),
46        startNodeNumber_(-1),
47        afterNodeNumber_(-1)
48{
49    test_ = this;
50}
51
52
53// Copy constructor
54CbcCompareDefault::CbcCompareDefault ( const CbcCompareDefault & rhs)
55        : CbcCompareBase(rhs)
56
57{
58    weight_ = rhs.weight_;
59    saveWeight_ = rhs.saveWeight_;
60    cutoff_ = rhs.cutoff_;
61    bestPossible_ = rhs.bestPossible_;
62    numberSolutions_ = rhs.numberSolutions_;
63    treeSize_ = rhs.treeSize_;
64    breadthDepth_ = rhs.breadthDepth_;
65    startNodeNumber_ = rhs.startNodeNumber_;
66    afterNodeNumber_ = rhs.afterNodeNumber_;
67}
68
69// Clone
70CbcCompareBase *
71CbcCompareDefault::clone() const
72{
73    return new CbcCompareDefault(*this);
74}
75
76// Assignment operator
77CbcCompareDefault &
78CbcCompareDefault::operator=( const CbcCompareDefault & rhs)
79{
80    if (this != &rhs) {
81        CbcCompareBase::operator=(rhs);
82        weight_ = rhs.weight_;
83        saveWeight_ = rhs.saveWeight_;
84        cutoff_ = rhs.cutoff_;
85        bestPossible_ = rhs.bestPossible_;
86        numberSolutions_ = rhs.numberSolutions_;
87        treeSize_ = rhs.treeSize_;
88        breadthDepth_ = rhs.breadthDepth_;
89        startNodeNumber_ = rhs.startNodeNumber_;
90        afterNodeNumber_ = rhs.afterNodeNumber_;
91    }
92    return *this;
93}
94
95// Destructor
96CbcCompareDefault::~CbcCompareDefault ()
97{
98}
99
100// Returns true if y better than x
101bool
102CbcCompareDefault::test (CbcNode * x, CbcNode * y)
103{
104    if (startNodeNumber_ >= 0) {
105        // Diving
106        int nX = x->nodeNumber();
107        int nY = y->nodeNumber();
108        if (nY == startNodeNumber_)
109            return true;
110        else if (nX == startNodeNumber_)
111            return false;
112        if (nX >= afterNodeNumber_ && nY < afterNodeNumber_)
113            return false;
114        else if (nY >= afterNodeNumber_ && nX < afterNodeNumber_)
115            return true;
116        // treat as depth first
117        int depthX = x->depth();
118        int depthY = y->depth();
119        if (depthX != depthY) {
120            return depthX < depthY;
121        } else {
122            double weight = CoinMax(weight_, 1.0e-9);
123            double testX =  x->objectiveValue() + weight * x->numberUnsatisfied();
124            double testY = y->objectiveValue() + weight * y->numberUnsatisfied();
125            if (testX != testY)
126                return testX > testY;
127            else
128                return equalityTest(x, y); // so ties will be broken in consistent manner
129        }
130    }
131    //weight_=0.0;
132    if ((weight_ == -1.0 && (y->depth() > breadthDepth_ && x->depth() > breadthDepth_)) || weight_ == -3.0 || weight_ == -2.0) {
133        int adjust =  (weight_ == -3.0) ? 10000 : 0;
134        // before solution
135        /*printf("x %d %d %g, y %d %d %g\n",
136           x->numberUnsatisfied(),x->depth(),x->objectiveValue(),
137           y->numberUnsatisfied(),y->depth(),y->objectiveValue()); */
138        if (x->numberUnsatisfied() > y->numberUnsatisfied() + adjust) {
139            return true;
140        } else if (x->numberUnsatisfied() < y->numberUnsatisfied() - adjust) {
141            return false;
142        } else {
143            int depthX = x->depth();
144            int depthY = y->depth();
145            if (depthX != depthY)
146                return depthX < depthY;
147            else
148                return equalityTest(x, y); // so ties will be broken in consistent manner
149        }
150    } else {
151        // always choose *greatest* depth if both <= breadthDepth_ otherwise <= breadthDepth_ if just one
152        int depthX = x->depth();
153        int depthY = y->depth();
154        /*if ((depthX==4&&depthY==5)||(depthX==5&&depthY==4))
155          printf("X %x depth %d, Y %x depth %d, breadth %d\n",
156          x,depthX,y,depthY,breadthDepth_);*/
157        if (depthX <= breadthDepth_ || depthY <= breadthDepth_) {
158            if (depthX <= breadthDepth_ && depthY <= breadthDepth_) {
159                if (depthX != depthY) {
160                    return depthX < depthY;
161                }
162            } else {
163                assert (depthX != depthY) ;
164                return depthX > depthY;
165            }
166        }
167        // after solution ?
168#define THRESH2 0.999
169#define TRY_THIS 0
170#if TRY_THIS==0
171        double weight = CoinMax(weight_, 1.0e-9);
172        double testX =  x->objectiveValue() + weight * x->numberUnsatisfied();
173        double testY = y->objectiveValue() + weight * y->numberUnsatisfied();
174#elif TRY_THIS==1
175        /* compute what weight would have to be to hit target
176           then reverse sign as large weight good */
177        double target = (1.0 - THRESH2) * bestPossible_ + THRESH2 * cutoff_;
178        double weight;
179        weight = (target - x->objectiveValue()) /
180                 static_cast<double>(x->numberUnsatisfied());
181        double testX = - weight;
182        weight = (target - y->objectiveValue()) /
183                 static_cast<double>(y->numberUnsatisfied());
184        double testY = - weight;
185#elif TRY_THIS==2
186        // Use estimates
187        double testX = x->guessedObjectiveValue();
188        double testY = y->guessedObjectiveValue();
189#elif TRY_THIS==3
190#define THRESH 0.95
191        // Use estimates
192        double testX = x->guessedObjectiveValue();
193        double testY = y->guessedObjectiveValue();
194        if (x->objectiveValue() - bestPossible_ > THRESH*(cutoff_ - bestPossible_))
195            testX *= 2.0; // make worse
196        if (y->objectiveValue() - bestPossible_ > THRESH*(cutoff_ - bestPossible_))
197            testY *= 2.0; // make worse
198#endif
199        if (testX != testY)
200            return testX > testY;
201        else
202            return equalityTest(x, y); // so ties will be broken in consistent manner
203    }
204}
205// This allows method to change behavior as it is called
206// after each solution
207void
208CbcCompareDefault::newSolution(CbcModel * model,
209                               double objectiveAtContinuous,
210                               int numberInfeasibilitiesAtContinuous)
211{
212    cutoff_ = model->getCutoff();
213    if (model->getSolutionCount() == model->getNumberHeuristicSolutions() &&
214            model->getSolutionCount() < 5 && model->getNodeCount() < 500)
215        return; // solution was got by rounding
216    // set to get close to this solution
217    double costPerInteger =
218        (model->getObjValue() - objectiveAtContinuous) /
219        static_cast<double> (numberInfeasibilitiesAtContinuous);
220    weight_ = 0.95 * costPerInteger;
221    saveWeight_ = 0.95 * weight_;
222    numberSolutions_++;
223    //if (numberSolutions_>5)
224    //weight_ =0.0; // this searches on objective
225}
226// This allows method to change behavior
227bool
228CbcCompareDefault::every1000Nodes(CbcModel * model, int numberNodes)
229{
230#ifdef JJF_ZERO
231    // was
232    if (numberNodes > 10000)
233        weight_ = 0.0; // this searches on objective
234    // get size of tree
235    treeSize_ = model->tree()->size();
236#else
237    double saveWeight = weight_;
238    int numberNodes1000 = numberNodes / 1000;
239    if (numberNodes > 10000) {
240        weight_ = 0.0; // this searches on objective
241        // but try a bit of other stuff
242        if ((numberNodes1000 % 4) == 1)
243            weight_ = saveWeight_;
244    } else if (numberNodes == 1000 && weight_ == -2.0) {
245        weight_ = -1.0; // Go to depth first
246    }
247    // get size of tree
248    treeSize_ = model->tree()->size();
249    if (treeSize_ > 10000) {
250        int n1 = model->solver()->getNumRows() + model->solver()->getNumCols();
251        int n2 = model->numberObjects();
252        double size = n1 * 0.1 + n2 * 2.0;
253        // set weight to reduce size most of time
254        if (treeSize_*(size + 100.0) > 5.0e7)
255            weight_ = -3.0;
256        else if ((numberNodes1000 % 4) == 0 && treeSize_*size > 1.0e6)
257            weight_ = -1.0;
258        else if ((numberNodes1000 % 4) == 1)
259            weight_ = 0.0;
260        else
261            weight_ = saveWeight_;
262    }
263#endif
264    //return numberNodes==11000; // resort if first time
265    return (weight_ != saveWeight);
266}
267// Start dive
268void
269CbcCompareDefault::startDive(CbcModel * model)
270{
271    // Get best - using ? criterion
272    double saveWeight = weight_;
273    weight_ = 0.5 * saveWeight_; //0.0;
274    // Switch off to get best
275    startNodeNumber_ = -1;
276    afterNodeNumber_ = -1;
277    CbcNode * best = model->tree()->bestAlternate();
278    startNodeNumber_ = best->nodeNumber();
279    // send signal to setComparison
280    afterNodeNumber_ = -2;
281    // redo tree
282    model->tree()->setComparison(*this);
283    afterNodeNumber_ = model->tree()->maximumNodeNumber();
284    weight_ = saveWeight;
285}
286// Clean up dive
287void
288CbcCompareDefault::cleanDive()
289{
290    if (afterNodeNumber_ != -2) {
291        // switch off
292        startNodeNumber_ = -1;
293        afterNodeNumber_ = -1;
294    }
295}
296
297// Create C++ lines to get to current state
298void
299CbcCompareDefault::generateCpp( FILE * fp)
300{
301    CbcCompareDefault other;
302    fprintf(fp, "0#include \"CbcCompareActual.hpp\"\n");
303    fprintf(fp, "3  CbcCompareDefault compare;\n");
304    if (weight_ != other.weight_)
305        fprintf(fp, "3  compare.setWeight(%g);\n", weight_);
306    fprintf(fp, "3  cbcModel->setNodeComparison(compare);\n");
307}
308
Note: See TracBrowser for help on using the repository browser.