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

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

Broke up CbcCompareActual?.cpp into CbcCompareDepth?, CbcCompareDefault?, CbcCompareObjective? and CbcCompareEstimate?.
Carved CbcCutModifier? and CbcCutSubsetModifier? out of CbcCutGenerator?.
Updated spreadsheets.

File size: 9.5 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{
31    test_ = this;
32}
33
34// Constructor with weight
35CbcCompareDefault::CbcCompareDefault (double weight)
36        : CbcCompareBase(),
37        weight_(weight) ,
38        saveWeight_(0.0),
39        cutoff_(COIN_DBL_MAX),
40        bestPossible_(-COIN_DBL_MAX),
41        numberSolutions_(0),
42        treeSize_(0),
43        breadthDepth_(5)
44{
45    test_ = this;
46}
47
48
49// Copy constructor
50CbcCompareDefault::CbcCompareDefault ( const CbcCompareDefault & rhs)
51        : CbcCompareBase(rhs)
52
53{
54    weight_ = rhs.weight_;
55    saveWeight_ = rhs.saveWeight_;
56    cutoff_ = rhs.cutoff_;
57    bestPossible_ = rhs.bestPossible_;
58    numberSolutions_ = rhs.numberSolutions_;
59    treeSize_ = rhs.treeSize_;
60    breadthDepth_ = rhs.breadthDepth_;
61}
62
63// Clone
64CbcCompareBase *
65CbcCompareDefault::clone() const
66{
67    return new CbcCompareDefault(*this);
68}
69
70// Assignment operator
71CbcCompareDefault &
72CbcCompareDefault::operator=( const CbcCompareDefault & rhs)
73{
74    if (this != &rhs) {
75        CbcCompareBase::operator=(rhs);
76        weight_ = rhs.weight_;
77        saveWeight_ = rhs.saveWeight_;
78        cutoff_ = rhs.cutoff_;
79        bestPossible_ = rhs.bestPossible_;
80        numberSolutions_ = rhs.numberSolutions_;
81        treeSize_ = rhs.treeSize_;
82        breadthDepth_ = rhs.breadthDepth_;
83    }
84    return *this;
85}
86
87// Destructor
88CbcCompareDefault::~CbcCompareDefault ()
89{
90}
91
92// Returns true if y better than x
93bool
94CbcCompareDefault::test (CbcNode * x, CbcNode * y)
95{
96#if 0
97    // always choose *smallest* depth if one or both <= breadthDepth_
98    int depthX = x->depth();
99    int depthY = y->depth();
100    if (depthX <= breadthDepth_ || depthY <= breadthDepth_) {
101        if (depthX != depthY)
102            return depthX > depthY;
103        else
104            return equalityTest(x, y); // so ties will be broken in consistent manner
105    }
106    if (weight_ == -1.0 || weight_ == -3.0) {
107        int adjust =  (weight_ == -3.0) ? 10000 : 0;
108        // before solution
109        /*printf("x %d %d %g, y %d %d %g\n",
110           x->numberUnsatisfied(),x->depth(),x->objectiveValue(),
111           y->numberUnsatisfied(),y->depth(),y->objectiveValue()); */
112        if (x->numberUnsatisfied() > y->numberUnsatisfied() + adjust) {
113            return true;
114        } else if (x->numberUnsatisfied() < y->numberUnsatisfied() - adjust) {
115            return false;
116        } else {
117            int depthX = x->depth();
118            int depthY = y->depth();
119            if (depthX != depthY)
120                return depthX < depthY;
121            else
122                return equalityTest(x, y); // so ties will be broken in consistent manner
123        }
124    } else {
125        // after solution
126        double weight = CoinMax(weight_, 0.0);
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#else
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#endif
209}
210// This allows method to change behavior as it is called
211// after each solution
212void
213CbcCompareDefault::newSolution(CbcModel * model,
214                               double objectiveAtContinuous,
215                               int numberInfeasibilitiesAtContinuous)
216{
217    cutoff_ = model->getCutoff();
218    if (model->getSolutionCount() == model->getNumberHeuristicSolutions() &&
219            model->getSolutionCount() < 5 && model->getNodeCount() < 500)
220        return; // solution was got by rounding
221    // set to get close to this solution
222    double costPerInteger =
223        (model->getObjValue() - objectiveAtContinuous) /
224        static_cast<double> (numberInfeasibilitiesAtContinuous);
225    weight_ = 0.95 * costPerInteger;
226    saveWeight_ = 0.95 * weight_;
227    numberSolutions_++;
228    //if (numberSolutions_>5)
229    //weight_ =0.0; // this searches on objective
230}
231// This allows method to change behavior
232bool
233CbcCompareDefault::every1000Nodes(CbcModel * model, int numberNodes)
234{
235#if 0
236    // was
237    if (numberNodes > 10000)
238        weight_ = 0.0; // this searches on objective
239    // get size of tree
240    treeSize_ = model->tree()->size();
241#else
242    double saveWeight = weight_;
243    int numberNodes1000 = numberNodes / 1000;
244    if (numberNodes > 10000) {
245        weight_ = 0.0; // this searches on objective
246        // but try a bit of other stuff
247        if ((numberNodes1000 % 4) == 1)
248            weight_ = saveWeight_;
249    } else if (numberNodes == 1000 && weight_ == -2.0) {
250        weight_ = -1.0; // Go to depth first
251    }
252    // get size of tree
253    treeSize_ = model->tree()->size();
254    if (treeSize_ > 10000) {
255        int n1 = model->solver()->getNumRows() + model->solver()->getNumCols();
256        int n2 = model->numberObjects();
257        double size = n1 * 0.1 + n2 * 2.0;
258        // set weight to reduce size most of time
259        if (treeSize_*(size + 100.0) > 5.0e7)
260            weight_ = -3.0;
261        else if ((numberNodes1000 % 4) == 0 && treeSize_*size > 1.0e6)
262            weight_ = -1.0;
263        else if ((numberNodes1000 % 4) == 1)
264            weight_ = 0.0;
265        else
266            weight_ = saveWeight_;
267    }
268#endif
269    //return numberNodes==11000; // resort if first time
270    return (weight_ != saveWeight);
271}
272
273// Create C++ lines to get to current state
274void
275CbcCompareDefault::generateCpp( FILE * fp)
276{
277    CbcCompareDefault other;
278    fprintf(fp, "0#include \"CbcCompareActual.hpp\"\n");
279    fprintf(fp, "3  CbcCompareDefault compare;\n");
280    if (weight_ != other.weight_)
281        fprintf(fp, "3  compare.setWeight(%g);\n", weight_);
282    fprintf(fp, "3  cbcModel->setNodeComparison(compare);\n");
283}
284
Note: See TracBrowser for help on using the repository browser.