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