1 // $Id$
2 // Copyright (C) 2004, 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 #include <cassert>
7 #include <cmath>
8 #include <cfloat>
9 //#define CBC_DEBUG
10 
11 #include "CoinPragma.hpp"
12 #include "CbcMessage.hpp"
13 #include "CbcModel.hpp"
14 #include "CbcTree.hpp"
15 #include "CbcCompareUser.hpp"
16 #include "CoinError.hpp"
17 #include "CoinHelperFunctions.hpp"
18 
19 /** Default Constructor
20 
21 */
CbcCompareUser()22 CbcCompareUser::CbcCompareUser()
23   : CbcCompareBase()
24   , weight_(-1.0)
25   , saveWeight_(0.0)
26   , numberSolutions_(0)
27   , count_(0)
28   , treeSize_(0)
29 {
30   test_ = this;
31 }
32 
33 // Constructor with weight
CbcCompareUser(double weight)34 CbcCompareUser::CbcCompareUser(double weight)
35   : CbcCompareBase()
36   , weight_(weight)
37   , saveWeight_(0.0)
38   , numberSolutions_(0)
39   , count_(0)
40   , treeSize_(0)
41 {
42   test_ = this;
43 }
44 
45 // Copy constructor
CbcCompareUser(const CbcCompareUser & rhs)46 CbcCompareUser::CbcCompareUser(const CbcCompareUser &rhs)
47   : CbcCompareBase(rhs)
48 
49 {
50   weight_ = rhs.weight_;
51   saveWeight_ = rhs.saveWeight_;
52   numberSolutions_ = rhs.numberSolutions_;
53   count_ = rhs.count_;
54   treeSize_ = rhs.treeSize_;
55 }
56 
57 // Clone
58 CbcCompareBase *
clone() const59 CbcCompareUser::clone() const
60 {
61   return new CbcCompareUser(*this);
62 }
63 
64 // Assignment operator
65 CbcCompareUser &
operator =(const CbcCompareUser & rhs)66 CbcCompareUser::operator=(const CbcCompareUser &rhs)
67 {
68   if (this != &rhs) {
69     CbcCompareBase::operator=(rhs);
70     weight_ = rhs.weight_;
71     saveWeight_ = rhs.saveWeight_;
72     numberSolutions_ = rhs.numberSolutions_;
73     count_ = rhs.count_;
74     treeSize_ = rhs.treeSize_;
75   }
76   return *this;
77 }
78 
79 // Destructor
~CbcCompareUser()80 CbcCompareUser::~CbcCompareUser()
81 {
82 }
83 // For moment go to default
84 #if 0
85 // Returns true if y better than x
86 bool
87 CbcCompareUser::test (CbcNode * x, CbcNode * y)
88 {
89   if (x) {
90     if (y) {
91       if (weight_==-1.0) {
92         // before solution
93         /* printf("x %d %d %g, y %d %d %g\n",
94            x->numberUnsatisfied(),x->depth(),x->objectiveValue(),
95            y->numberUnsatisfied(),y->depth(),y->objectiveValue()); */
96         if (x->numberUnsatisfied() > y->numberUnsatisfied())
97           return true;
98         else if (x->numberUnsatisfied() < y->numberUnsatisfied())
99           return false;
100         else
101           return x->depth() < y->depth();
102       } else {
103         // after solution
104         double weight = CoinMax(weight_,0.0);
105         return x->objectiveValue()+ weight*x->numberUnsatisfied() >
106           y->objectiveValue() + weight*y->numberUnsatisfied();
107         //return x->guessedObjectiveValue()>y->guessedObjectiveValue();
108       }
109     } else {
110       return false;
111     }
112   } else {
113     return true;
114   }
115 }
116 // This allows method to change behavior as it is called
117 // after each solution
118 void
119 CbcCompareUser::newSolution(CbcModel * model,
120 			       double objectiveAtContinuous,
121 			       int numberInfeasibilitiesAtContinuous)
122 {
123   // set to get close to this solution
124   double costPerInteger =
125     (model->getObjValue()-objectiveAtContinuous)/
126     ((double) numberInfeasibilitiesAtContinuous);
127   weight_ = 0.95*costPerInteger;
128   saveWeight_=weight_;
129   if (model->getSolutionCount()==model->getNumberHeuristicSolutions())
130     return; // solution was got by rounding
131   numberSolutions_++;
132   if (numberSolutions_>5)
133     weight_ =0.0; // this searches on objective
134   return (true) ;
135 }
136 // This allows method to change behavior
137 bool
138 CbcCompareUser::every1000Nodes(CbcModel * model, int numberNodes)
139 {
140   if (numberNodes>10000)
141     weight_ =0.0; // this searches on objective
142   else if (numberNodes==1000&&weight_==-2.0)
143     weight_=-1.0; // Go to depth first
144   // get size of tree
145   treeSize_ = model->tree()->size();
146   if (treeSize_>10000) {
147     // set weight to reduce size most of time
148     if (treeSize_>20000)
149       weight_=-1.0;
150     else if ((numberNodes%4000)!=0)
151       weight_=-1.0;
152     else
153       weight_=saveWeight_;
154   }
155   return numberNodes==11000; // resort if first time
156 }
157 // Returns true if wants code to do scan with alternate criterion
158 bool
159 CbcCompareUser::fullScan() const
160 {
161   count_++;
162   if (weight_)
163     return (count_%10)==0;
164   else
165     return false;
166 }
167 // This is alternate test function
168 bool
169 CbcCompareUser::alternateTest (CbcNode * x, CbcNode * y)
170 {
171   if (x) {
172     if (y) {
173       return x->objectiveValue() >
174         y->objectiveValue() ;
175     } else {
176       return false;
177     }
178   } else {
179     return true;
180   }
181 }
182 #else
183 
184 // Returns true if y better than x
test(CbcNode * x,CbcNode * y)185 bool CbcCompareUser::test(CbcNode *x, CbcNode *y)
186 {
187   if (weight_ == -1.0 && (y->depth() > 7 || x->depth() > 7)) {
188     // before solution
189     /* printf("x %d %d %g, y %d %d %g\n",
190        x->numberUnsatisfied(),x->depth(),x->objectiveValue(),
191        y->numberUnsatisfied(),y->depth(),y->objectiveValue()); */
192     if (x->numberUnsatisfied() > y->numberUnsatisfied()) {
193       return true;
194     } else if (x->numberUnsatisfied() < y->numberUnsatisfied()) {
195       return false;
196     } else {
197       int testX = x->depth();
198       int testY = y->depth();
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   } else {
205     // after solution
206     double weight = CoinMax(weight_, 0.0);
207     double testX = x->objectiveValue() + weight * x->numberUnsatisfied();
208     double testY = y->objectiveValue() + weight * y->numberUnsatisfied();
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 // This allows method to change behavior as it is called
216 // after each solution
newSolution(CbcModel * model,double objectiveAtContinuous,int numberInfeasibilitiesAtContinuous)217 bool CbcCompareUser::newSolution(CbcModel *model,
218   double objectiveAtContinuous,
219   int numberInfeasibilitiesAtContinuous)
220 {
221   if (model->getSolutionCount() == model->getNumberHeuristicSolutions() && model->getSolutionCount() < 5 && model->getNodeCount() < 500)
222     return (false); // solution was got by rounding
223   // set to get close to this solution
224   double costPerInteger = (model->getObjValue() - objectiveAtContinuous) / ((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   return (true);
231 }
232 // This allows method to change behavior
every1000Nodes(CbcModel * model,int numberNodes)233 bool CbcCompareUser::every1000Nodes(CbcModel *model, int numberNodes)
234 {
235   double saveWeight = weight_;
236   int numberNodes1000 = numberNodes / 1000;
237   if (numberNodes > 10000) {
238     weight_ = 0.0; // this searches on objective
239     // but try a bit of other stuff
240     if ((numberNodes1000 % 4) == 1)
241       weight_ = saveWeight_;
242   } else if (numberNodes == 1000 && weight_ == -2.0) {
243     weight_ = -1.0; // Go to depth first
244   }
245   // get size of tree
246   treeSize_ = model->tree()->size();
247   if (treeSize_ > 10000) {
248     int n1 = model->solver()->getNumRows() + model->solver()->getNumCols();
249     int n2 = model->numberObjects();
250     double size = n1 * 0.1 + n2 * 2.0;
251     // set weight to reduce size most of time
252     if (treeSize_ * size > 5.0e7)
253       weight_ = -1.0;
254     else if ((numberNodes1000 % 4) == 0 && treeSize_ * size > 1.0e6)
255       weight_ = -1.0;
256     else if ((numberNodes1000 % 4) == 1)
257       weight_ = 0.0;
258     else
259       weight_ = saveWeight_;
260   }
261   return (weight_ != saveWeight);
262 }
263 // Returns true if wants code to do scan with alternate criterion
fullScan() const264 bool CbcCompareUser::fullScan() const
265 {
266   return false;
267 }
268 // This is alternate test function
alternateTest(CbcNode * x,CbcNode * y)269 bool CbcCompareUser::alternateTest(CbcNode *x, CbcNode *y)
270 {
271   // not used
272   abort();
273   return false;
274 }
275 #endif
276