1 | // Copyright (C) 2002, International Business Machines |
---|
2 | // Corporation and others. All Rights Reserved. |
---|
3 | #if defined(_MSC_VER) |
---|
4 | // Turn off compiler warning about long names |
---|
5 | # pragma warning(disable:4786) |
---|
6 | #endif |
---|
7 | #include <cassert> |
---|
8 | #include <cmath> |
---|
9 | #include <cfloat> |
---|
10 | //#define CBC_DEBUG |
---|
11 | |
---|
12 | #include "OsiSolverInterface.hpp" |
---|
13 | #include "OsiSolverBranch.hpp" |
---|
14 | #include "CbcModel.hpp" |
---|
15 | #include "CbcMessage.hpp" |
---|
16 | #include "CbcBranchActual.hpp" |
---|
17 | #include "CoinSort.hpp" |
---|
18 | #include "CoinError.hpp" |
---|
19 | |
---|
20 | // Default Constructor |
---|
21 | CbcClique::CbcClique () |
---|
22 | : CbcObject(), |
---|
23 | numberMembers_(0), |
---|
24 | numberNonSOSMembers_(0), |
---|
25 | members_(NULL), |
---|
26 | type_(NULL), |
---|
27 | cliqueType_(-1), |
---|
28 | slack_(-1) |
---|
29 | { |
---|
30 | } |
---|
31 | |
---|
32 | // Useful constructor (which are integer indices) |
---|
33 | CbcClique::CbcClique (CbcModel * model, int cliqueType, int numberMembers, |
---|
34 | const int * which, const char * type, int identifier,int slack) |
---|
35 | : CbcObject(model) |
---|
36 | { |
---|
37 | id_=identifier; |
---|
38 | numberMembers_=numberMembers; |
---|
39 | if (numberMembers_) { |
---|
40 | members_ = new int[numberMembers_]; |
---|
41 | memcpy(members_,which,numberMembers_*sizeof(int)); |
---|
42 | type_ = new char[numberMembers_]; |
---|
43 | if (type) { |
---|
44 | memcpy(type_,type,numberMembers_*sizeof(char)); |
---|
45 | } else { |
---|
46 | for (int i=0;i<numberMembers_;i++) |
---|
47 | type_[i]=1; |
---|
48 | } |
---|
49 | } else { |
---|
50 | members_ = NULL; |
---|
51 | type_ = NULL; |
---|
52 | } |
---|
53 | // Find out how many non sos |
---|
54 | int i; |
---|
55 | numberNonSOSMembers_=0; |
---|
56 | for (i=0;i<numberMembers_;i++) |
---|
57 | if (!type_[i]) |
---|
58 | numberNonSOSMembers_++; |
---|
59 | cliqueType_ = cliqueType; |
---|
60 | slack_ = slack; |
---|
61 | } |
---|
62 | |
---|
63 | // Copy constructor |
---|
64 | CbcClique::CbcClique ( const CbcClique & rhs) |
---|
65 | :CbcObject(rhs) |
---|
66 | { |
---|
67 | numberMembers_ = rhs.numberMembers_; |
---|
68 | numberNonSOSMembers_ = rhs.numberNonSOSMembers_; |
---|
69 | if (numberMembers_) { |
---|
70 | members_ = new int[numberMembers_]; |
---|
71 | memcpy(members_,rhs.members_,numberMembers_*sizeof(int)); |
---|
72 | type_ = new char[numberMembers_]; |
---|
73 | memcpy(type_,rhs.type_,numberMembers_*sizeof(char)); |
---|
74 | } else { |
---|
75 | members_ = NULL; |
---|
76 | type_ = NULL; |
---|
77 | } |
---|
78 | cliqueType_ = rhs.cliqueType_; |
---|
79 | slack_ = rhs.slack_; |
---|
80 | } |
---|
81 | |
---|
82 | // Clone |
---|
83 | CbcObject * |
---|
84 | CbcClique::clone() const |
---|
85 | { |
---|
86 | return new CbcClique(*this); |
---|
87 | } |
---|
88 | |
---|
89 | // Assignment operator |
---|
90 | CbcClique & |
---|
91 | CbcClique::operator=( const CbcClique& rhs) |
---|
92 | { |
---|
93 | if (this!=&rhs) { |
---|
94 | CbcObject::operator=(rhs); |
---|
95 | delete [] members_; |
---|
96 | delete [] type_; |
---|
97 | numberMembers_ = rhs.numberMembers_; |
---|
98 | numberNonSOSMembers_ = rhs.numberNonSOSMembers_; |
---|
99 | if (numberMembers_) { |
---|
100 | members_ = new int[numberMembers_]; |
---|
101 | memcpy(members_,rhs.members_,numberMembers_*sizeof(int)); |
---|
102 | type_ = new char[numberMembers_]; |
---|
103 | memcpy(type_,rhs.type_,numberMembers_*sizeof(char)); |
---|
104 | } else { |
---|
105 | members_ = NULL; |
---|
106 | type_ = NULL; |
---|
107 | } |
---|
108 | cliqueType_ = rhs.cliqueType_; |
---|
109 | slack_ = rhs.slack_; |
---|
110 | } |
---|
111 | return *this; |
---|
112 | } |
---|
113 | |
---|
114 | // Destructor |
---|
115 | CbcClique::~CbcClique () |
---|
116 | { |
---|
117 | delete [] members_; |
---|
118 | delete [] type_; |
---|
119 | } |
---|
120 | |
---|
121 | // Infeasibility - large is 0.5 |
---|
122 | double |
---|
123 | CbcClique::infeasibility(int & preferredWay) const |
---|
124 | { |
---|
125 | int numberUnsatis=0, numberFree=0; |
---|
126 | int j; |
---|
127 | const int * integer = model_->integerVariable(); |
---|
128 | OsiSolverInterface * solver = model_->solver(); |
---|
129 | const double * solution = model_->testSolution(); |
---|
130 | const double * lower = solver->getColLower(); |
---|
131 | const double * upper = solver->getColUpper(); |
---|
132 | double largestValue=0.0; |
---|
133 | double integerTolerance = |
---|
134 | model_->getDblParam(CbcModel::CbcIntegerTolerance); |
---|
135 | double * sort = new double[numberMembers_]; |
---|
136 | |
---|
137 | double slackValue=0.0; |
---|
138 | for (j=0;j<numberMembers_;j++) { |
---|
139 | int sequence = members_[j]; |
---|
140 | int iColumn = integer[sequence]; |
---|
141 | double value = solution[iColumn]; |
---|
142 | value = CoinMax(value, lower[iColumn]); |
---|
143 | value = CoinMin(value, upper[iColumn]); |
---|
144 | double nearest = floor(value+0.5); |
---|
145 | double distance = fabs(value-nearest); |
---|
146 | if (distance>integerTolerance) { |
---|
147 | if (!type_[j]) |
---|
148 | value = 1.0-value; // non SOS |
---|
149 | // if slack then choose that |
---|
150 | if (j==slack_&&value>0.05) |
---|
151 | slackValue = value; |
---|
152 | largestValue = CoinMax(value,largestValue); |
---|
153 | sort[numberUnsatis++]=-value; |
---|
154 | } else if (upper[iColumn]>lower[iColumn]) { |
---|
155 | numberFree++; |
---|
156 | } |
---|
157 | } |
---|
158 | preferredWay=1; |
---|
159 | double otherWay = 0.0; |
---|
160 | if (numberUnsatis) { |
---|
161 | // sort |
---|
162 | std::sort(sort,sort+numberUnsatis); |
---|
163 | for (j=0;j<numberUnsatis;j++) { |
---|
164 | if ((j&1)!=0) |
---|
165 | otherWay += -sort[j]; |
---|
166 | } |
---|
167 | // Need to think more |
---|
168 | double value = 0.2*numberUnsatis+0.01*(numberMembers_-numberFree); |
---|
169 | if (fabs(largestValue-0.5)<0.1) { |
---|
170 | // close to half |
---|
171 | value +=0.1; |
---|
172 | } |
---|
173 | if (slackValue) { |
---|
174 | // branching on slack |
---|
175 | value += slackValue; |
---|
176 | } |
---|
177 | // scale other way |
---|
178 | otherWay *= value/(1.0-otherWay); |
---|
179 | delete [] sort; |
---|
180 | return value; |
---|
181 | } else { |
---|
182 | delete [] sort; |
---|
183 | return 0.0; // satisfied |
---|
184 | } |
---|
185 | } |
---|
186 | |
---|
187 | // This looks at solution and sets bounds to contain solution |
---|
188 | void |
---|
189 | CbcClique::feasibleRegion() |
---|
190 | { |
---|
191 | int j; |
---|
192 | const int * integer = model_->integerVariable(); |
---|
193 | OsiSolverInterface * solver = model_->solver(); |
---|
194 | const double * solution = model_->testSolution(); |
---|
195 | const double * lower = solver->getColLower(); |
---|
196 | const double * upper = solver->getColUpper(); |
---|
197 | #ifndef NDEBUG |
---|
198 | double integerTolerance = |
---|
199 | model_->getDblParam(CbcModel::CbcIntegerTolerance); |
---|
200 | #endif |
---|
201 | for (j=0;j<numberMembers_;j++) { |
---|
202 | int sequence = members_[j]; |
---|
203 | int iColumn = integer[sequence]; |
---|
204 | double value = solution[iColumn]; |
---|
205 | value = CoinMax(value, lower[iColumn]); |
---|
206 | value = CoinMin(value, upper[iColumn]); |
---|
207 | double nearest = floor(value+0.5); |
---|
208 | #ifndef NDEBUG |
---|
209 | double distance = fabs(value-nearest); |
---|
210 | assert(distance<=integerTolerance); |
---|
211 | #endif |
---|
212 | solver->setColLower(iColumn,nearest); |
---|
213 | solver->setColUpper(iColumn,nearest); |
---|
214 | } |
---|
215 | } |
---|
216 | // Redoes data when sequence numbers change |
---|
217 | void |
---|
218 | CbcClique::redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns) |
---|
219 | { |
---|
220 | model_=model; |
---|
221 | int n2=0; |
---|
222 | for (int j=0;j<numberMembers_;j++) { |
---|
223 | int iColumn = members_[j]; |
---|
224 | int i; |
---|
225 | for (i=0;i<numberColumns;i++) { |
---|
226 | if (originalColumns[i]==iColumn) |
---|
227 | break; |
---|
228 | } |
---|
229 | if (i<numberColumns) { |
---|
230 | members_[n2]=i; |
---|
231 | type_[n2++]=type_[j]; |
---|
232 | } |
---|
233 | } |
---|
234 | if (n2<numberMembers_) { |
---|
235 | //printf("** SOS number of members reduced from %d to %d!\n",numberMembers_,n2); |
---|
236 | numberMembers_=n2; |
---|
237 | } |
---|
238 | // Find out how many non sos |
---|
239 | int i; |
---|
240 | numberNonSOSMembers_=0; |
---|
241 | for (i=0;i<numberMembers_;i++) |
---|
242 | if (!type_[i]) |
---|
243 | numberNonSOSMembers_++; |
---|
244 | } |
---|
245 | |
---|
246 | |
---|
247 | // Creates a branching object |
---|
248 | CbcBranchingObject * |
---|
249 | CbcClique::createBranch(int way) |
---|
250 | { |
---|
251 | int numberUnsatis=0; |
---|
252 | int j; |
---|
253 | int nUp=0; |
---|
254 | int nDown=0; |
---|
255 | int numberFree=numberMembers_; |
---|
256 | const int * integer = model_->integerVariable(); |
---|
257 | OsiSolverInterface * solver = model_->solver(); |
---|
258 | const double * solution = model_->testSolution(); |
---|
259 | const double * lower = solver->getColLower(); |
---|
260 | const double * upper = solver->getColUpper(); |
---|
261 | int * upList = new int[numberMembers_]; |
---|
262 | int * downList = new int[numberMembers_]; |
---|
263 | double * sort = new double[numberMembers_]; |
---|
264 | double integerTolerance = |
---|
265 | model_->getDblParam(CbcModel::CbcIntegerTolerance); |
---|
266 | |
---|
267 | double slackValue=0.0; |
---|
268 | for (j=0;j<numberMembers_;j++) { |
---|
269 | int sequence = members_[j]; |
---|
270 | int iColumn = integer[sequence]; |
---|
271 | double value = solution[iColumn]; |
---|
272 | value = CoinMax(value, lower[iColumn]); |
---|
273 | value = CoinMin(value, upper[iColumn]); |
---|
274 | double nearest = floor(value+0.5); |
---|
275 | double distance = fabs(value-nearest); |
---|
276 | if (distance>integerTolerance) { |
---|
277 | if (!type_[j]) |
---|
278 | value = 1.0-value; // non SOS |
---|
279 | // if slack then choose that |
---|
280 | if (j==slack_&&value>0.05) |
---|
281 | slackValue = value; |
---|
282 | value = -value; // for sort |
---|
283 | upList[numberUnsatis]=j; |
---|
284 | sort[numberUnsatis++]=value; |
---|
285 | } else if (upper[iColumn]>lower[iColumn]) { |
---|
286 | upList[--numberFree]=j; |
---|
287 | } |
---|
288 | } |
---|
289 | assert (numberUnsatis); |
---|
290 | if (!slackValue) { |
---|
291 | // sort |
---|
292 | CoinSort_2(sort,sort+numberUnsatis,upList); |
---|
293 | // put first in up etc |
---|
294 | int kWay=1; |
---|
295 | for (j=0;j<numberUnsatis;j++) { |
---|
296 | if (kWay>0) |
---|
297 | upList[nUp++]=upList[j]; |
---|
298 | else |
---|
299 | downList[nDown++]=upList[j]; |
---|
300 | kWay = -kWay; |
---|
301 | } |
---|
302 | for (j=numberFree;j<numberMembers_;j++) { |
---|
303 | if (kWay>0) |
---|
304 | upList[nUp++]=upList[j]; |
---|
305 | else |
---|
306 | downList[nDown++]=upList[j]; |
---|
307 | kWay = -kWay; |
---|
308 | } |
---|
309 | } else { |
---|
310 | // put slack to 0 in first way |
---|
311 | nUp = 1; |
---|
312 | upList[0]=slack_; |
---|
313 | for (j=0;j<numberUnsatis;j++) { |
---|
314 | downList[nDown++]=upList[j]; |
---|
315 | } |
---|
316 | for (j=numberFree;j<numberMembers_;j++) { |
---|
317 | downList[nDown++]=upList[j]; |
---|
318 | } |
---|
319 | } |
---|
320 | // create object |
---|
321 | CbcBranchingObject * branch; |
---|
322 | if (numberMembers_ <=64) |
---|
323 | branch = new CbcCliqueBranchingObject(model_,this,way, |
---|
324 | nDown,downList,nUp,upList); |
---|
325 | else |
---|
326 | branch = new CbcLongCliqueBranchingObject(model_,this,way, |
---|
327 | nDown,downList,nUp,upList); |
---|
328 | delete [] upList; |
---|
329 | delete [] downList; |
---|
330 | delete [] sort; |
---|
331 | return branch; |
---|
332 | } |
---|
333 | |
---|
334 | // Default Constructor |
---|
335 | CbcSOS::CbcSOS () |
---|
336 | : CbcObject(), |
---|
337 | members_(NULL), |
---|
338 | weights_(NULL), |
---|
339 | numberMembers_(0), |
---|
340 | sosType_(-1), |
---|
341 | integerValued_(false) |
---|
342 | { |
---|
343 | } |
---|
344 | |
---|
345 | // Useful constructor (which are indices) |
---|
346 | CbcSOS::CbcSOS (CbcModel * model, int numberMembers, |
---|
347 | const int * which, const double * weights, int identifier,int type) |
---|
348 | : CbcObject(model), |
---|
349 | numberMembers_(numberMembers), |
---|
350 | sosType_(type) |
---|
351 | { |
---|
352 | id_=identifier; |
---|
353 | integerValued_ = type==1; |
---|
354 | if (integerValued_) { |
---|
355 | // check all members integer |
---|
356 | OsiSolverInterface * solver = model->solver(); |
---|
357 | if (solver) { |
---|
358 | for (int i=0;i<numberMembers_;i++) { |
---|
359 | if (!solver->isInteger(which[i])) |
---|
360 | integerValued_=false; |
---|
361 | } |
---|
362 | } else { |
---|
363 | // can't tell |
---|
364 | integerValued_=false; |
---|
365 | } |
---|
366 | } |
---|
367 | if (numberMembers_) { |
---|
368 | members_ = new int[numberMembers_]; |
---|
369 | weights_ = new double[numberMembers_]; |
---|
370 | memcpy(members_,which,numberMembers_*sizeof(int)); |
---|
371 | if (weights) { |
---|
372 | memcpy(weights_,weights,numberMembers_*sizeof(double)); |
---|
373 | } else { |
---|
374 | for (int i=0;i<numberMembers_;i++) |
---|
375 | weights_[i]=i; |
---|
376 | } |
---|
377 | // sort so weights increasing |
---|
378 | CoinSort_2(weights_,weights_+numberMembers_,members_); |
---|
379 | double last = -COIN_DBL_MAX; |
---|
380 | int i; |
---|
381 | for (i=0;i<numberMembers_;i++) { |
---|
382 | double possible = CoinMax(last+1.0e-10,weights_[i]); |
---|
383 | weights_[i] = possible; |
---|
384 | last=possible; |
---|
385 | } |
---|
386 | } else { |
---|
387 | members_ = NULL; |
---|
388 | weights_ = NULL; |
---|
389 | } |
---|
390 | assert (sosType_>0&&sosType_<3); |
---|
391 | } |
---|
392 | |
---|
393 | // Copy constructor |
---|
394 | CbcSOS::CbcSOS ( const CbcSOS & rhs) |
---|
395 | :CbcObject(rhs) |
---|
396 | { |
---|
397 | numberMembers_ = rhs.numberMembers_; |
---|
398 | sosType_ = rhs.sosType_; |
---|
399 | integerValued_ = rhs.integerValued_; |
---|
400 | if (numberMembers_) { |
---|
401 | members_ = new int[numberMembers_]; |
---|
402 | weights_ = new double[numberMembers_]; |
---|
403 | memcpy(members_,rhs.members_,numberMembers_*sizeof(int)); |
---|
404 | memcpy(weights_,rhs.weights_,numberMembers_*sizeof(double)); |
---|
405 | } else { |
---|
406 | members_ = NULL; |
---|
407 | weights_ = NULL; |
---|
408 | } |
---|
409 | } |
---|
410 | |
---|
411 | // Clone |
---|
412 | CbcObject * |
---|
413 | CbcSOS::clone() const |
---|
414 | { |
---|
415 | return new CbcSOS(*this); |
---|
416 | } |
---|
417 | |
---|
418 | // Assignment operator |
---|
419 | CbcSOS & |
---|
420 | CbcSOS::operator=( const CbcSOS& rhs) |
---|
421 | { |
---|
422 | if (this!=&rhs) { |
---|
423 | CbcObject::operator=(rhs); |
---|
424 | delete [] members_; |
---|
425 | delete [] weights_; |
---|
426 | numberMembers_ = rhs.numberMembers_; |
---|
427 | sosType_ = rhs.sosType_; |
---|
428 | integerValued_ = rhs.integerValued_; |
---|
429 | if (numberMembers_) { |
---|
430 | members_ = new int[numberMembers_]; |
---|
431 | weights_ = new double[numberMembers_]; |
---|
432 | memcpy(members_,rhs.members_,numberMembers_*sizeof(int)); |
---|
433 | memcpy(weights_,rhs.weights_,numberMembers_*sizeof(double)); |
---|
434 | } else { |
---|
435 | members_ = NULL; |
---|
436 | weights_ = NULL; |
---|
437 | } |
---|
438 | } |
---|
439 | return *this; |
---|
440 | } |
---|
441 | |
---|
442 | // Destructor |
---|
443 | CbcSOS::~CbcSOS () |
---|
444 | { |
---|
445 | delete [] members_; |
---|
446 | delete [] weights_; |
---|
447 | } |
---|
448 | |
---|
449 | // Infeasibility - large is 0.5 |
---|
450 | double |
---|
451 | CbcSOS::infeasibility(int & preferredWay) const |
---|
452 | { |
---|
453 | int j; |
---|
454 | int firstNonZero=-1; |
---|
455 | int lastNonZero = -1; |
---|
456 | OsiSolverInterface * solver = model_->solver(); |
---|
457 | const double * solution = model_->testSolution(); |
---|
458 | //const double * lower = solver->getColLower(); |
---|
459 | const double * upper = solver->getColUpper(); |
---|
460 | //double largestValue=0.0; |
---|
461 | double integerTolerance = |
---|
462 | model_->getDblParam(CbcModel::CbcIntegerTolerance); |
---|
463 | double weight = 0.0; |
---|
464 | double sum =0.0; |
---|
465 | |
---|
466 | // check bounds etc |
---|
467 | double lastWeight=-1.0e100; |
---|
468 | for (j=0;j<numberMembers_;j++) { |
---|
469 | int iColumn = members_[j]; |
---|
470 | if (lastWeight>=weights_[j]-1.0e-7) |
---|
471 | throw CoinError("Weights too close together in SOS","infeasibility","CbcSOS"); |
---|
472 | double value = CoinMax(0.0,solution[iColumn]); |
---|
473 | sum += value; |
---|
474 | if (value>integerTolerance&&upper[iColumn]) { |
---|
475 | // Possibly due to scaling a fixed variable might slip through |
---|
476 | if (value>upper[iColumn]) { |
---|
477 | value=upper[iColumn]; |
---|
478 | // Could change to #ifdef CBC_DEBUG |
---|
479 | #ifndef NDEBUG |
---|
480 | if (model_->messageHandler()->logLevel()>2) |
---|
481 | printf("** Variable %d (%d) has value %g and upper bound of %g\n", |
---|
482 | iColumn,j,value,upper[iColumn]); |
---|
483 | #endif |
---|
484 | } |
---|
485 | weight += weights_[j]*value; |
---|
486 | if (firstNonZero<0) |
---|
487 | firstNonZero=j; |
---|
488 | lastNonZero=j; |
---|
489 | } |
---|
490 | } |
---|
491 | preferredWay=1; |
---|
492 | if (lastNonZero-firstNonZero>=sosType_) { |
---|
493 | // find where to branch |
---|
494 | assert (sum>0.0); |
---|
495 | weight /= sum; |
---|
496 | //int iWhere; |
---|
497 | //for (iWhere=firstNonZero;iWhere<lastNonZero;iWhere++) |
---|
498 | //if (weight<weights_[iWhere+1]) |
---|
499 | //break; |
---|
500 | // probably best to use pseudo duals |
---|
501 | double value = lastNonZero-firstNonZero+1; |
---|
502 | value *= 0.5/((double) numberMembers_); |
---|
503 | return value; |
---|
504 | } else { |
---|
505 | return 0.0; // satisfied |
---|
506 | } |
---|
507 | } |
---|
508 | |
---|
509 | // This looks at solution and sets bounds to contain solution |
---|
510 | void |
---|
511 | CbcSOS::feasibleRegion() |
---|
512 | { |
---|
513 | int j; |
---|
514 | int firstNonZero=-1; |
---|
515 | int lastNonZero = -1; |
---|
516 | OsiSolverInterface * solver = model_->solver(); |
---|
517 | const double * solution = model_->testSolution(); |
---|
518 | //const double * lower = solver->getColLower(); |
---|
519 | const double * upper = solver->getColUpper(); |
---|
520 | double integerTolerance = |
---|
521 | model_->getDblParam(CbcModel::CbcIntegerTolerance); |
---|
522 | double weight = 0.0; |
---|
523 | double sum =0.0; |
---|
524 | |
---|
525 | for (j=0;j<numberMembers_;j++) { |
---|
526 | int iColumn = members_[j]; |
---|
527 | double value = CoinMax(0.0,solution[iColumn]); |
---|
528 | sum += value; |
---|
529 | if (value>integerTolerance&&upper[iColumn]) { |
---|
530 | weight += weights_[j]*value; |
---|
531 | if (firstNonZero<0) |
---|
532 | firstNonZero=j; |
---|
533 | lastNonZero=j; |
---|
534 | } |
---|
535 | } |
---|
536 | assert (lastNonZero-firstNonZero<sosType_) ; |
---|
537 | for (j=0;j<firstNonZero;j++) { |
---|
538 | int iColumn = members_[j]; |
---|
539 | solver->setColUpper(iColumn,0.0); |
---|
540 | } |
---|
541 | for (j=lastNonZero+1;j<numberMembers_;j++) { |
---|
542 | int iColumn = members_[j]; |
---|
543 | solver->setColUpper(iColumn,0.0); |
---|
544 | } |
---|
545 | } |
---|
546 | // Redoes data when sequence numbers change |
---|
547 | void |
---|
548 | CbcSOS::redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns) |
---|
549 | { |
---|
550 | model_=model; |
---|
551 | int n2=0; |
---|
552 | for (int j=0;j<numberMembers_;j++) { |
---|
553 | int iColumn = members_[j]; |
---|
554 | int i; |
---|
555 | for (i=0;i<numberColumns;i++) { |
---|
556 | if (originalColumns[i]==iColumn) |
---|
557 | break; |
---|
558 | } |
---|
559 | if (i<numberColumns) { |
---|
560 | members_[n2]=i; |
---|
561 | weights_[n2++]=weights_[j]; |
---|
562 | } |
---|
563 | } |
---|
564 | if (n2<numberMembers_) { |
---|
565 | //printf("** SOS number of members reduced from %d to %d!\n",numberMembers_,n2); |
---|
566 | numberMembers_=n2; |
---|
567 | } |
---|
568 | } |
---|
569 | |
---|
570 | |
---|
571 | // Creates a branching object |
---|
572 | CbcBranchingObject * |
---|
573 | CbcSOS::createBranch(int way) |
---|
574 | { |
---|
575 | int j; |
---|
576 | const double * solution = model_->testSolution(); |
---|
577 | double integerTolerance = |
---|
578 | model_->getDblParam(CbcModel::CbcIntegerTolerance); |
---|
579 | OsiSolverInterface * solver = model_->solver(); |
---|
580 | const double * upper = solver->getColUpper(); |
---|
581 | int firstNonFixed=-1; |
---|
582 | int lastNonFixed=-1; |
---|
583 | int firstNonZero=-1; |
---|
584 | int lastNonZero = -1; |
---|
585 | double weight = 0.0; |
---|
586 | double sum =0.0; |
---|
587 | for (j=0;j<numberMembers_;j++) { |
---|
588 | int iColumn = members_[j]; |
---|
589 | if (upper[iColumn]) { |
---|
590 | double value = CoinMax(0.0,solution[iColumn]); |
---|
591 | sum += value; |
---|
592 | if (firstNonFixed<0) |
---|
593 | firstNonFixed=j; |
---|
594 | lastNonFixed=j; |
---|
595 | if (value>integerTolerance) { |
---|
596 | weight += weights_[j]*value; |
---|
597 | if (firstNonZero<0) |
---|
598 | firstNonZero=j; |
---|
599 | lastNonZero=j; |
---|
600 | } |
---|
601 | } |
---|
602 | } |
---|
603 | assert (lastNonZero-firstNonZero>=sosType_) ; |
---|
604 | // find where to branch |
---|
605 | assert (sum>0.0); |
---|
606 | weight /= sum; |
---|
607 | int iWhere; |
---|
608 | double separator=0.0; |
---|
609 | for (iWhere=firstNonZero;iWhere<lastNonZero;iWhere++) |
---|
610 | if (weight<weights_[iWhere+1]) |
---|
611 | break; |
---|
612 | if (sosType_==1) { |
---|
613 | // SOS 1 |
---|
614 | separator = 0.5 *(weights_[iWhere]+weights_[iWhere+1]); |
---|
615 | } else { |
---|
616 | // SOS 2 |
---|
617 | if (iWhere==firstNonFixed) |
---|
618 | iWhere++;; |
---|
619 | if (iWhere==lastNonFixed-1) |
---|
620 | iWhere = lastNonFixed-2; |
---|
621 | separator = weights_[iWhere+1]; |
---|
622 | } |
---|
623 | // create object |
---|
624 | CbcBranchingObject * branch; |
---|
625 | branch = new CbcSOSBranchingObject(model_,this,way,separator); |
---|
626 | return branch; |
---|
627 | } |
---|
628 | |
---|
629 | /* Create an OsiSolverBranch object |
---|
630 | |
---|
631 | This returns NULL if branch not represented by bound changes |
---|
632 | */ |
---|
633 | OsiSolverBranch * |
---|
634 | CbcSOS::solverBranch() const |
---|
635 | { |
---|
636 | int j; |
---|
637 | const double * solution = model_->testSolution(); |
---|
638 | double integerTolerance = |
---|
639 | model_->getDblParam(CbcModel::CbcIntegerTolerance); |
---|
640 | OsiSolverInterface * solver = model_->solver(); |
---|
641 | const double * upper = solver->getColUpper(); |
---|
642 | int firstNonFixed=-1; |
---|
643 | int lastNonFixed=-1; |
---|
644 | int firstNonZero=-1; |
---|
645 | int lastNonZero = -1; |
---|
646 | double weight = 0.0; |
---|
647 | double sum =0.0; |
---|
648 | double * fix = new double[numberMembers_]; |
---|
649 | int * which = new int[numberMembers_]; |
---|
650 | for (j=0;j<numberMembers_;j++) { |
---|
651 | int iColumn = members_[j]; |
---|
652 | // fix all on one side or other (even if fixed) |
---|
653 | fix[j]=0.0; |
---|
654 | which[j]=iColumn; |
---|
655 | if (upper[iColumn]) { |
---|
656 | double value = CoinMax(0.0,solution[iColumn]); |
---|
657 | sum += value; |
---|
658 | if (firstNonFixed<0) |
---|
659 | firstNonFixed=j; |
---|
660 | lastNonFixed=j; |
---|
661 | if (value>integerTolerance) { |
---|
662 | weight += weights_[j]*value; |
---|
663 | if (firstNonZero<0) |
---|
664 | firstNonZero=j; |
---|
665 | lastNonZero=j; |
---|
666 | } |
---|
667 | } |
---|
668 | } |
---|
669 | assert (lastNonZero-firstNonZero>=sosType_) ; |
---|
670 | // find where to branch |
---|
671 | assert (sum>0.0); |
---|
672 | weight /= sum; |
---|
673 | // down branch fixes ones above weight to 0 |
---|
674 | int iWhere; |
---|
675 | int iDownStart=0; |
---|
676 | int iUpEnd=0; |
---|
677 | for (iWhere=firstNonZero;iWhere<lastNonZero;iWhere++) |
---|
678 | if (weight<weights_[iWhere+1]) |
---|
679 | break; |
---|
680 | if (sosType_==1) { |
---|
681 | // SOS 1 |
---|
682 | iUpEnd=iWhere+1; |
---|
683 | iDownStart=iUpEnd; |
---|
684 | } else { |
---|
685 | // SOS 2 |
---|
686 | if (iWhere==firstNonFixed) |
---|
687 | iWhere++;; |
---|
688 | if (iWhere==lastNonFixed-1) |
---|
689 | iWhere = lastNonFixed-2; |
---|
690 | iUpEnd=iWhere+1; |
---|
691 | iDownStart=iUpEnd+1; |
---|
692 | } |
---|
693 | // |
---|
694 | OsiSolverBranch * branch = new OsiSolverBranch(); |
---|
695 | branch->addBranch(-1,0,NULL,NULL,numberMembers_-iDownStart,which+iDownStart,fix); |
---|
696 | branch->addBranch(1,0,NULL,NULL,iUpEnd,which,fix); |
---|
697 | delete [] fix; |
---|
698 | delete [] which; |
---|
699 | return branch; |
---|
700 | } |
---|
701 | // Construct an OsiSOS object |
---|
702 | OsiSOS * |
---|
703 | CbcSOS::osiObject(const OsiSolverInterface * solver) const |
---|
704 | { |
---|
705 | OsiSOS * obj = new OsiSOS(solver,numberMembers_,members_,weights_,sosType_); |
---|
706 | obj->setPriority(priority()); |
---|
707 | return obj; |
---|
708 | } |
---|
709 | |
---|
710 | /** Default Constructor |
---|
711 | |
---|
712 | Equivalent to an unspecified binary variable. |
---|
713 | */ |
---|
714 | CbcSimpleInteger::CbcSimpleInteger () |
---|
715 | : CbcObject(), |
---|
716 | originalLower_(0.0), |
---|
717 | originalUpper_(1.0), |
---|
718 | breakEven_(0.5), |
---|
719 | columnNumber_(-1), |
---|
720 | preferredWay_(0) |
---|
721 | { |
---|
722 | } |
---|
723 | |
---|
724 | /** Useful constructor |
---|
725 | |
---|
726 | Loads actual upper & lower bounds for the specified variable. |
---|
727 | */ |
---|
728 | CbcSimpleInteger::CbcSimpleInteger ( CbcModel * model, int iColumn, double breakEven) |
---|
729 | : CbcObject(model) |
---|
730 | { |
---|
731 | columnNumber_ = iColumn ; |
---|
732 | originalLower_ = model->solver()->getColLower()[columnNumber_] ; |
---|
733 | originalUpper_ = model->solver()->getColUpper()[columnNumber_] ; |
---|
734 | breakEven_ = breakEven; |
---|
735 | assert (breakEven_>0.0&&breakEven_<1.0); |
---|
736 | preferredWay_ = 0; |
---|
737 | } |
---|
738 | |
---|
739 | |
---|
740 | // Copy constructor |
---|
741 | CbcSimpleInteger::CbcSimpleInteger ( const CbcSimpleInteger & rhs) |
---|
742 | :CbcObject(rhs) |
---|
743 | |
---|
744 | { |
---|
745 | columnNumber_ = rhs.columnNumber_; |
---|
746 | originalLower_ = rhs.originalLower_; |
---|
747 | originalUpper_ = rhs.originalUpper_; |
---|
748 | breakEven_ = rhs.breakEven_; |
---|
749 | preferredWay_ = rhs.preferredWay_; |
---|
750 | } |
---|
751 | |
---|
752 | // Clone |
---|
753 | CbcObject * |
---|
754 | CbcSimpleInteger::clone() const |
---|
755 | { |
---|
756 | return new CbcSimpleInteger(*this); |
---|
757 | } |
---|
758 | |
---|
759 | // Assignment operator |
---|
760 | CbcSimpleInteger & |
---|
761 | CbcSimpleInteger::operator=( const CbcSimpleInteger& rhs) |
---|
762 | { |
---|
763 | if (this!=&rhs) { |
---|
764 | CbcObject::operator=(rhs); |
---|
765 | columnNumber_ = rhs.columnNumber_; |
---|
766 | originalLower_ = rhs.originalLower_; |
---|
767 | originalUpper_ = rhs.originalUpper_; |
---|
768 | breakEven_ = rhs.breakEven_; |
---|
769 | preferredWay_ = rhs.preferredWay_; |
---|
770 | } |
---|
771 | return *this; |
---|
772 | } |
---|
773 | |
---|
774 | // Destructor |
---|
775 | CbcSimpleInteger::~CbcSimpleInteger () |
---|
776 | { |
---|
777 | } |
---|
778 | // Construct an OsiSimpleInteger object |
---|
779 | OsiSimpleInteger * |
---|
780 | CbcSimpleInteger::osiObject() const |
---|
781 | { |
---|
782 | OsiSimpleInteger * obj = new OsiSimpleInteger(columnNumber_, |
---|
783 | originalLower_,originalUpper_); |
---|
784 | obj->setPriority(priority()); |
---|
785 | return obj; |
---|
786 | } |
---|
787 | |
---|
788 | double |
---|
789 | CbcSimpleInteger::infeasibility(const OsiSolverInterface * solver, const OsiBranchingInformation * info, |
---|
790 | int & preferredWay) const |
---|
791 | { |
---|
792 | double value = info->solution_[columnNumber_]; |
---|
793 | value = CoinMax(value, info->lower_[columnNumber_]); |
---|
794 | value = CoinMin(value, info->upper_[columnNumber_]); |
---|
795 | double nearest = floor(value+(1.0-breakEven_)); |
---|
796 | assert (breakEven_>0.0&&breakEven_<1.0); |
---|
797 | if (nearest>value) |
---|
798 | preferredWay=1; |
---|
799 | else |
---|
800 | preferredWay=-1; |
---|
801 | if (preferredWay_) |
---|
802 | preferredWay=preferredWay_; |
---|
803 | double weight = fabs(value-nearest); |
---|
804 | // normalize so weight is 0.5 at break even |
---|
805 | if (nearest<value) |
---|
806 | weight = (0.5/breakEven_)*weight; |
---|
807 | else |
---|
808 | weight = (0.5/(1.0-breakEven_))*weight; |
---|
809 | if (fabs(value-nearest)<=info->integerTolerance_) |
---|
810 | return 0.0; |
---|
811 | else |
---|
812 | return weight; |
---|
813 | } |
---|
814 | double |
---|
815 | CbcSimpleInteger::feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const |
---|
816 | { |
---|
817 | double value = info->solution_[columnNumber_]; |
---|
818 | double newValue = CoinMax(value, info->lower_[columnNumber_]); |
---|
819 | newValue = CoinMin(newValue, info->upper_[columnNumber_]); |
---|
820 | newValue = floor(newValue+0.5); |
---|
821 | solver->setColLower(columnNumber_,newValue); |
---|
822 | solver->setColUpper(columnNumber_,newValue); |
---|
823 | return fabs(value-newValue); |
---|
824 | } |
---|
825 | |
---|
826 | /* Create an OsiSolverBranch object |
---|
827 | |
---|
828 | This returns NULL if branch not represented by bound changes |
---|
829 | */ |
---|
830 | OsiSolverBranch * |
---|
831 | CbcSimpleInteger::solverBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info) const |
---|
832 | { |
---|
833 | double value = info->solution_[columnNumber_]; |
---|
834 | value = CoinMax(value, info->lower_[columnNumber_]); |
---|
835 | value = CoinMin(value, info->upper_[columnNumber_]); |
---|
836 | assert (info->upper_[columnNumber_]>info->lower_[columnNumber_]); |
---|
837 | #ifndef NDEBUG |
---|
838 | double nearest = floor(value+0.5); |
---|
839 | assert (fabs(value-nearest)>info->integerTolerance_); |
---|
840 | #endif |
---|
841 | OsiSolverBranch * branch = new OsiSolverBranch(); |
---|
842 | branch->addBranch(columnNumber_,value); |
---|
843 | return branch; |
---|
844 | } |
---|
845 | // Creates a branching object |
---|
846 | CbcBranchingObject * |
---|
847 | CbcSimpleInteger::createBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) |
---|
848 | { |
---|
849 | double value = info->solution_[columnNumber_]; |
---|
850 | value = CoinMax(value, info->lower_[columnNumber_]); |
---|
851 | value = CoinMin(value, info->upper_[columnNumber_]); |
---|
852 | assert (info->upper_[columnNumber_]>info->lower_[columnNumber_]); |
---|
853 | if (!info->hotstartSolution_) { |
---|
854 | #ifndef NDEBUG |
---|
855 | double nearest = floor(value+0.5); |
---|
856 | assert (fabs(value-nearest)>info->integerTolerance_); |
---|
857 | #endif |
---|
858 | } else { |
---|
859 | double targetValue = info->hotstartSolution_[columnNumber_]; |
---|
860 | if (way>0) |
---|
861 | value = targetValue-0.1; |
---|
862 | else |
---|
863 | value = targetValue+0.1; |
---|
864 | } |
---|
865 | CbcBranchingObject * branch = new CbcIntegerBranchingObject(model_,columnNumber_,way, |
---|
866 | value); |
---|
867 | branch->setOriginalObject(this); |
---|
868 | return branch; |
---|
869 | } |
---|
870 | /* Column number if single column object -1 otherwise, |
---|
871 | so returns >= 0 |
---|
872 | Used by heuristics |
---|
873 | */ |
---|
874 | int |
---|
875 | CbcSimpleInteger::columnNumber() const |
---|
876 | { |
---|
877 | return columnNumber_; |
---|
878 | } |
---|
879 | /* Reset variable bounds to their original values. |
---|
880 | |
---|
881 | Bounds may be tightened, so it may be good to be able to set this info in object. |
---|
882 | */ |
---|
883 | void |
---|
884 | CbcSimpleInteger::resetBounds(const OsiSolverInterface * solver) |
---|
885 | { |
---|
886 | originalLower_ = solver->getColLower()[columnNumber_] ; |
---|
887 | originalUpper_ = solver->getColUpper()[columnNumber_] ; |
---|
888 | } |
---|
889 | |
---|
890 | /* Change column numbers after preprocessing |
---|
891 | */ |
---|
892 | void |
---|
893 | CbcSimpleInteger::resetSequenceEtc(int numberColumns, const int * originalColumns) |
---|
894 | { |
---|
895 | int iColumn; |
---|
896 | for (iColumn=0;iColumn<numberColumns;iColumn++) { |
---|
897 | if (columnNumber_==originalColumns[iColumn]) |
---|
898 | break; |
---|
899 | } |
---|
900 | assert (iColumn<numberColumns); |
---|
901 | columnNumber_ = iColumn; |
---|
902 | } |
---|
903 | |
---|
904 | // Infeasibility - large is 0.5 |
---|
905 | double |
---|
906 | CbcSimpleInteger::infeasibility(int & preferredWay) const |
---|
907 | { |
---|
908 | OsiBranchingInformation info(model_->solver(),model_->normalSolver(),false); |
---|
909 | return infeasibility(model_->solver(),&info,preferredWay); |
---|
910 | } |
---|
911 | |
---|
912 | // This looks at solution and sets bounds to contain solution |
---|
913 | /** More precisely: it first forces the variable within the existing |
---|
914 | bounds, and then tightens the bounds to fix the variable at the |
---|
915 | nearest integer value. |
---|
916 | */ |
---|
917 | void |
---|
918 | CbcSimpleInteger::feasibleRegion() |
---|
919 | { |
---|
920 | abort(); |
---|
921 | } |
---|
922 | CbcBranchingObject * |
---|
923 | CbcSimpleInteger::createBranch( int way) |
---|
924 | { |
---|
925 | abort(); |
---|
926 | return NULL; |
---|
927 | } |
---|
928 | // Default Constructor |
---|
929 | CbcIntegerBranchingObject::CbcIntegerBranchingObject() |
---|
930 | :CbcBranchingObject() |
---|
931 | { |
---|
932 | down_[0] = 0.0; |
---|
933 | down_[1] = 0.0; |
---|
934 | up_[0] = 0.0; |
---|
935 | up_[1] = 0.0; |
---|
936 | #ifdef FUNNY_BRANCHING |
---|
937 | variables_ = NULL; |
---|
938 | newBounds_ = NULL; |
---|
939 | numberExtraChangedBounds_ = 0; |
---|
940 | #endif |
---|
941 | } |
---|
942 | // Useful constructor |
---|
943 | CbcIntegerBranchingObject::CbcIntegerBranchingObject (CbcModel * model, |
---|
944 | int variable, int way , double value) |
---|
945 | :CbcBranchingObject(model,variable,way,value) |
---|
946 | { |
---|
947 | int iColumn = variable; |
---|
948 | down_[0] = model_->solver()->getColLower()[iColumn]; |
---|
949 | down_[1] = floor(value_); |
---|
950 | up_[0] = ceil(value_); |
---|
951 | up_[1] = model->getColUpper()[iColumn]; |
---|
952 | #ifdef FUNNY_BRANCHING |
---|
953 | variables_ = NULL; |
---|
954 | newBounds_ = NULL; |
---|
955 | numberExtraChangedBounds_ = 0; |
---|
956 | #endif |
---|
957 | } |
---|
958 | // Useful constructor for fixing |
---|
959 | CbcIntegerBranchingObject::CbcIntegerBranchingObject (CbcModel * model, |
---|
960 | int variable, int way, |
---|
961 | double lowerValue, |
---|
962 | double upperValue) |
---|
963 | :CbcBranchingObject(model,variable,way,lowerValue) |
---|
964 | { |
---|
965 | setNumberBranchesLeft(1); |
---|
966 | down_[0] = lowerValue; |
---|
967 | down_[1] = upperValue; |
---|
968 | up_[0] = lowerValue; |
---|
969 | up_[1] = upperValue; |
---|
970 | #ifdef FUNNY_BRANCHING |
---|
971 | variables_ = NULL; |
---|
972 | newBounds_ = NULL; |
---|
973 | numberExtraChangedBounds_ = 0; |
---|
974 | #endif |
---|
975 | } |
---|
976 | |
---|
977 | |
---|
978 | // Copy constructor |
---|
979 | CbcIntegerBranchingObject::CbcIntegerBranchingObject ( const CbcIntegerBranchingObject & rhs) :CbcBranchingObject(rhs) |
---|
980 | { |
---|
981 | down_[0] = rhs.down_[0]; |
---|
982 | down_[1] = rhs.down_[1]; |
---|
983 | up_[0] = rhs.up_[0]; |
---|
984 | up_[1] = rhs.up_[1]; |
---|
985 | #ifdef FUNNY_BRANCHING |
---|
986 | numberExtraChangedBounds_ = rhs.numberExtraChangedBounds_; |
---|
987 | int size = numberExtraChangedBounds_*(sizeof(double)+sizeof(int)); |
---|
988 | char * temp = new char [size]; |
---|
989 | newBounds_ = (double *) temp; |
---|
990 | variables_ = (int *) (newBounds_+numberExtraChangedBounds_); |
---|
991 | |
---|
992 | int i ; |
---|
993 | for (i=0;i<numberExtraChangedBounds_;i++) { |
---|
994 | variables_[i]=rhs.variables_[i]; |
---|
995 | newBounds_[i]=rhs.newBounds_[i]; |
---|
996 | } |
---|
997 | #endif |
---|
998 | } |
---|
999 | |
---|
1000 | // Assignment operator |
---|
1001 | CbcIntegerBranchingObject & |
---|
1002 | CbcIntegerBranchingObject::operator=( const CbcIntegerBranchingObject& rhs) |
---|
1003 | { |
---|
1004 | if (this != &rhs) { |
---|
1005 | CbcBranchingObject::operator=(rhs); |
---|
1006 | down_[0] = rhs.down_[0]; |
---|
1007 | down_[1] = rhs.down_[1]; |
---|
1008 | up_[0] = rhs.up_[0]; |
---|
1009 | up_[1] = rhs.up_[1]; |
---|
1010 | #ifdef FUNNY_BRANCHING |
---|
1011 | delete [] newBounds_; |
---|
1012 | numberExtraChangedBounds_ = rhs.numberExtraChangedBounds_; |
---|
1013 | int size = numberExtraChangedBounds_*(sizeof(double)+sizeof(int)); |
---|
1014 | char * temp = new char [size]; |
---|
1015 | newBounds_ = (double *) temp; |
---|
1016 | variables_ = (int *) (newBounds_+numberExtraChangedBounds_); |
---|
1017 | |
---|
1018 | int i ; |
---|
1019 | for (i=0;i<numberExtraChangedBounds_;i++) { |
---|
1020 | variables_[i]=rhs.variables_[i]; |
---|
1021 | newBounds_[i]=rhs.newBounds_[i]; |
---|
1022 | } |
---|
1023 | #endif |
---|
1024 | } |
---|
1025 | return *this; |
---|
1026 | } |
---|
1027 | CbcBranchingObject * |
---|
1028 | CbcIntegerBranchingObject::clone() const |
---|
1029 | { |
---|
1030 | return (new CbcIntegerBranchingObject(*this)); |
---|
1031 | } |
---|
1032 | |
---|
1033 | |
---|
1034 | // Destructor |
---|
1035 | CbcIntegerBranchingObject::~CbcIntegerBranchingObject () |
---|
1036 | { |
---|
1037 | // for debugging threads |
---|
1038 | way_=-23456789; |
---|
1039 | #ifdef FUNNY_BRANCHING |
---|
1040 | delete [] newBounds_; |
---|
1041 | #endif |
---|
1042 | } |
---|
1043 | |
---|
1044 | /* |
---|
1045 | Perform a branch by adjusting the bounds of the specified variable. Note |
---|
1046 | that each arm of the branch advances the object to the next arm by |
---|
1047 | advancing the value of way_. |
---|
1048 | |
---|
1049 | Providing new values for the variable's lower and upper bounds for each |
---|
1050 | branching direction gives a little bit of additional flexibility and will |
---|
1051 | be easily extensible to multi-way branching. |
---|
1052 | Returns change in guessed objective on next branch |
---|
1053 | */ |
---|
1054 | double |
---|
1055 | CbcIntegerBranchingObject::branch() |
---|
1056 | { |
---|
1057 | // for debugging threads |
---|
1058 | if (way_<-1||way_>100000) { |
---|
1059 | printf("way %d, left %d, iCol %d, variable %d\n", |
---|
1060 | way_,numberBranchesLeft(), |
---|
1061 | originalCbcObject_->columnNumber(),variable_); |
---|
1062 | assert (way_!=-23456789); |
---|
1063 | } |
---|
1064 | decrementNumberBranchesLeft(); |
---|
1065 | if (down_[1]==-COIN_DBL_MAX) |
---|
1066 | return 0.0; |
---|
1067 | int iColumn = originalCbcObject_->columnNumber(); |
---|
1068 | assert (variable_==iColumn); |
---|
1069 | double olb,oub ; |
---|
1070 | olb = model_->solver()->getColLower()[iColumn] ; |
---|
1071 | oub = model_->solver()->getColUpper()[iColumn] ; |
---|
1072 | #ifdef COIN_DEVELOP |
---|
1073 | if (olb!=down_[0]||oub!=up_[1]) { |
---|
1074 | if (way_>0) |
---|
1075 | printf("branching up on var %d: [%g,%g] => [%g,%g] - other [%g,%g]\n", |
---|
1076 | iColumn,olb,oub,up_[0],up_[1],down_[0],down_[1]) ; |
---|
1077 | else |
---|
1078 | printf("branching down on var %d: [%g,%g] => [%g,%g] - other [%g,%g]\n", |
---|
1079 | iColumn,olb,oub,down_[0],down_[1],up_[0],up_[1]) ; |
---|
1080 | } |
---|
1081 | #endif |
---|
1082 | if (way_<0) { |
---|
1083 | #ifdef CBC_DEBUG |
---|
1084 | { double olb,oub ; |
---|
1085 | olb = model_->solver()->getColLower()[iColumn] ; |
---|
1086 | oub = model_->solver()->getColUpper()[iColumn] ; |
---|
1087 | printf("branching down on var %d: [%g,%g] => [%g,%g]\n", |
---|
1088 | iColumn,olb,oub,down_[0],down_[1]) ; } |
---|
1089 | #endif |
---|
1090 | model_->solver()->setColLower(iColumn,down_[0]); |
---|
1091 | model_->solver()->setColUpper(iColumn,down_[1]); |
---|
1092 | //#define CBC_PRINT2 |
---|
1093 | #ifdef CBC_PRINT2 |
---|
1094 | printf("%d branching down has bounds %g %g",iColumn,down_[0],down_[1]); |
---|
1095 | #endif |
---|
1096 | #ifdef FUNNY_BRANCHING |
---|
1097 | // branch - do extra bounds |
---|
1098 | for (int i=0;i<numberExtraChangedBounds_;i++) { |
---|
1099 | int variable = variables_[i]; |
---|
1100 | if ((variable&0x40000000)!=0) { |
---|
1101 | // for going down |
---|
1102 | int k = variable&0x3fffffff; |
---|
1103 | assert (k!=iColumn); |
---|
1104 | if ((variable&0x80000000)==0) { |
---|
1105 | // lower bound changing |
---|
1106 | #ifdef CBC_PRINT2 |
---|
1107 | printf(" extra for %d changes lower from %g to %g", |
---|
1108 | k,model_->solver()->getColLower()[k],newBounds_[i]); |
---|
1109 | #endif |
---|
1110 | model_->solver()->setColLower(k,newBounds_[i]); |
---|
1111 | } else { |
---|
1112 | // upper bound changing |
---|
1113 | #ifdef CBC_PRINT2 |
---|
1114 | printf(" extra for %d changes upper from %g to %g", |
---|
1115 | k,model_->solver()->getColUpper()[k],newBounds_[i]); |
---|
1116 | #endif |
---|
1117 | model_->solver()->setColUpper(k,newBounds_[i]); |
---|
1118 | } |
---|
1119 | } |
---|
1120 | } |
---|
1121 | #endif |
---|
1122 | #ifdef CBC_PRINT2 |
---|
1123 | printf("\n"); |
---|
1124 | #endif |
---|
1125 | way_=1; |
---|
1126 | } else { |
---|
1127 | #ifdef CBC_DEBUG |
---|
1128 | { double olb,oub ; |
---|
1129 | olb = model_->solver()->getColLower()[iColumn] ; |
---|
1130 | oub = model_->solver()->getColUpper()[iColumn] ; |
---|
1131 | printf("branching up on var %d: [%g,%g] => [%g,%g]\n", |
---|
1132 | iColumn,olb,oub,up_[0],up_[1]) ; } |
---|
1133 | #endif |
---|
1134 | model_->solver()->setColLower(iColumn,up_[0]); |
---|
1135 | model_->solver()->setColUpper(iColumn,up_[1]); |
---|
1136 | #ifdef CBC_PRINT2 |
---|
1137 | printf("%d branching up has bounds %g %g",iColumn,up_[0],up_[1]); |
---|
1138 | #endif |
---|
1139 | #ifdef FUNNY_BRANCHING |
---|
1140 | // branch - do extra bounds |
---|
1141 | for (int i=0;i<numberExtraChangedBounds_;i++) { |
---|
1142 | int variable = variables_[i]; |
---|
1143 | if ((variable&0x40000000)==0) { |
---|
1144 | // for going up |
---|
1145 | int k = variable&0x3fffffff; |
---|
1146 | assert (k!=iColumn); |
---|
1147 | if ((variable&0x80000000)==0) { |
---|
1148 | // lower bound changing |
---|
1149 | #ifdef CBC_PRINT2 |
---|
1150 | printf(" extra for %d changes lower from %g to %g", |
---|
1151 | k,model_->solver()->getColLower()[k],newBounds_[i]); |
---|
1152 | #endif |
---|
1153 | model_->solver()->setColLower(k,newBounds_[i]); |
---|
1154 | } else { |
---|
1155 | // upper bound changing |
---|
1156 | #ifdef CBC_PRINT2 |
---|
1157 | printf(" extra for %d changes upper from %g to %g", |
---|
1158 | k,model_->solver()->getColUpper()[k],newBounds_[i]); |
---|
1159 | #endif |
---|
1160 | model_->solver()->setColUpper(k,newBounds_[i]); |
---|
1161 | } |
---|
1162 | } |
---|
1163 | } |
---|
1164 | #endif |
---|
1165 | #ifdef CBC_PRINT2 |
---|
1166 | printf("\n"); |
---|
1167 | #endif |
---|
1168 | way_=-1; // Swap direction |
---|
1169 | } |
---|
1170 | double nlb = model_->solver()->getColLower()[iColumn]; |
---|
1171 | double nub = model_->solver()->getColUpper()[iColumn]; |
---|
1172 | if (nlb<olb) { |
---|
1173 | #ifndef NDEBUG |
---|
1174 | printf("bad lb change for column %d from %g to %g\n",iColumn,olb,nlb); |
---|
1175 | #endif |
---|
1176 | model_->solver()->setColLower(iColumn,CoinMin(olb,nub)); |
---|
1177 | nlb=olb; |
---|
1178 | } |
---|
1179 | if (nub>oub) { |
---|
1180 | #ifndef NDEBUG |
---|
1181 | printf("bad ub change for column %d from %g to %g\n",iColumn,oub,nub); |
---|
1182 | #endif |
---|
1183 | model_->solver()->setColUpper(iColumn,CoinMax(oub,nlb)); |
---|
1184 | } |
---|
1185 | #ifndef NDEBUG |
---|
1186 | if (nlb<olb+1.0e-8&&nub>oub-1.0e-8&&false) |
---|
1187 | printf("bad null change for column %d - bounds %g,%g\n",iColumn,olb,oub); |
---|
1188 | #endif |
---|
1189 | return 0.0; |
---|
1190 | } |
---|
1191 | #ifdef FUNNY_BRANCHING |
---|
1192 | // Deactivate bounds for branching |
---|
1193 | void |
---|
1194 | CbcIntegerBranchingObject::deactivate() |
---|
1195 | { |
---|
1196 | down_[1]=-COIN_DBL_MAX; |
---|
1197 | } |
---|
1198 | int |
---|
1199 | CbcIntegerBranchingObject::applyExtraBounds(int iColumn, double lower, double upper, int way) |
---|
1200 | { |
---|
1201 | // branch - do bounds |
---|
1202 | |
---|
1203 | int i; |
---|
1204 | int found=0; |
---|
1205 | if (variable_==iColumn) { |
---|
1206 | printf("odd applyExtra %d\n",iColumn); |
---|
1207 | if (way<0) { |
---|
1208 | down_[0]=CoinMax(lower,down_[0]); |
---|
1209 | down_[1]=CoinMin(upper,down_[1]); |
---|
1210 | assert (down_[0]<=down_[1]); |
---|
1211 | } else { |
---|
1212 | up_[0]=CoinMax(lower,up_[0]); |
---|
1213 | up_[1]=CoinMin(upper,up_[1]); |
---|
1214 | assert (up_[0]<=up_[1]); |
---|
1215 | } |
---|
1216 | return 0; |
---|
1217 | } |
---|
1218 | int check = (way<0) ? 0x40000000 : 0; |
---|
1219 | double newLower=lower; |
---|
1220 | double newUpper=upper; |
---|
1221 | for (i=0;i<numberExtraChangedBounds_;i++) { |
---|
1222 | int variable = variables_[i]; |
---|
1223 | if ((variable&0x40000000)==check) { |
---|
1224 | int k = variable&0x3fffffff; |
---|
1225 | if (k==iColumn) { |
---|
1226 | if ((variable&0x80000000)==0) { |
---|
1227 | // lower bound changing |
---|
1228 | found |= 1; |
---|
1229 | newBounds_[i] = CoinMax(lower,newBounds_[i]); |
---|
1230 | newLower = newBounds_[i]; |
---|
1231 | } else { |
---|
1232 | // upper bound changing |
---|
1233 | found |= 2; |
---|
1234 | newBounds_[i] = CoinMin(upper,newBounds_[i]); |
---|
1235 | newUpper = newBounds_[i]; |
---|
1236 | } |
---|
1237 | } |
---|
1238 | } |
---|
1239 | } |
---|
1240 | int nAdd=0; |
---|
1241 | if ((found&2)==0) { |
---|
1242 | // need to add new upper |
---|
1243 | nAdd++; |
---|
1244 | } |
---|
1245 | if ((found&1)==0) { |
---|
1246 | // need to add new lower |
---|
1247 | nAdd++; |
---|
1248 | } |
---|
1249 | if (nAdd) { |
---|
1250 | int size = (numberExtraChangedBounds_+nAdd)*(sizeof(double)+sizeof(int)); |
---|
1251 | char * temp = new char [size]; |
---|
1252 | double * newBounds = (double *) temp; |
---|
1253 | int * variables = (int *) (newBounds+numberExtraChangedBounds_+nAdd); |
---|
1254 | |
---|
1255 | int i ; |
---|
1256 | for (i=0;i<numberExtraChangedBounds_;i++) { |
---|
1257 | variables[i]=variables_[i]; |
---|
1258 | newBounds[i]=newBounds_[i]; |
---|
1259 | } |
---|
1260 | delete [] newBounds_; |
---|
1261 | newBounds_ = newBounds; |
---|
1262 | variables_ = variables; |
---|
1263 | if ((found&2)==0) { |
---|
1264 | // need to add new upper |
---|
1265 | int variable = iColumn | 0x80000000; |
---|
1266 | variables_[numberExtraChangedBounds_]=variable; |
---|
1267 | newBounds_[numberExtraChangedBounds_++]=newUpper; |
---|
1268 | } |
---|
1269 | if ((found&1)==0) { |
---|
1270 | // need to add new lower |
---|
1271 | int variable = iColumn; |
---|
1272 | variables_[numberExtraChangedBounds_]=variable; |
---|
1273 | newBounds_[numberExtraChangedBounds_++]=newLower; |
---|
1274 | } |
---|
1275 | } |
---|
1276 | |
---|
1277 | return (newUpper>=newLower) ? 0 : 1; |
---|
1278 | } |
---|
1279 | #endif |
---|
1280 | // Print what would happen |
---|
1281 | void |
---|
1282 | CbcIntegerBranchingObject::print() |
---|
1283 | { |
---|
1284 | int iColumn = originalCbcObject_->columnNumber(); |
---|
1285 | assert (variable_==iColumn); |
---|
1286 | if (way_<0) { |
---|
1287 | { double olb,oub ; |
---|
1288 | olb = model_->solver()->getColLower()[iColumn] ; |
---|
1289 | oub = model_->solver()->getColUpper()[iColumn] ; |
---|
1290 | printf("CbcInteger would branch down on var %d (int var %d): [%g,%g] => [%g,%g]\n", |
---|
1291 | iColumn,variable_,olb,oub,down_[0],down_[1]) ; } |
---|
1292 | } else { |
---|
1293 | { double olb,oub ; |
---|
1294 | olb = model_->solver()->getColLower()[iColumn] ; |
---|
1295 | oub = model_->solver()->getColUpper()[iColumn] ; |
---|
1296 | printf("CbcInteger would branch up on var %d (int var %d): [%g,%g] => [%g,%g]\n", |
---|
1297 | iColumn,variable_,olb,oub,up_[0],up_[1]) ; } |
---|
1298 | } |
---|
1299 | } |
---|
1300 | |
---|
1301 | |
---|
1302 | /** Default Constructor |
---|
1303 | |
---|
1304 | Equivalent to an unspecified binary variable. |
---|
1305 | */ |
---|
1306 | CbcSimpleIntegerPseudoCost::CbcSimpleIntegerPseudoCost () |
---|
1307 | : CbcSimpleInteger(), |
---|
1308 | downPseudoCost_(1.0e-5), |
---|
1309 | upPseudoCost_(1.0e-5), |
---|
1310 | upDownSeparator_(-1.0), |
---|
1311 | method_(0) |
---|
1312 | { |
---|
1313 | } |
---|
1314 | |
---|
1315 | /** Useful constructor |
---|
1316 | |
---|
1317 | Loads actual upper & lower bounds for the specified variable. |
---|
1318 | */ |
---|
1319 | CbcSimpleIntegerPseudoCost::CbcSimpleIntegerPseudoCost (CbcModel * model, |
---|
1320 | int iColumn, double breakEven) |
---|
1321 | : CbcSimpleInteger(model,iColumn,breakEven) |
---|
1322 | { |
---|
1323 | const double * cost = model->getObjCoefficients(); |
---|
1324 | double costValue = CoinMax(1.0e-5,fabs(cost[iColumn])); |
---|
1325 | // treat as if will cost what it says up |
---|
1326 | upPseudoCost_=costValue; |
---|
1327 | // and balance at breakeven |
---|
1328 | downPseudoCost_=((1.0-breakEven_)*upPseudoCost_)/breakEven_; |
---|
1329 | upDownSeparator_ = -1.0; |
---|
1330 | method_=0; |
---|
1331 | } |
---|
1332 | |
---|
1333 | /** Useful constructor |
---|
1334 | |
---|
1335 | Loads actual upper & lower bounds for the specified variable. |
---|
1336 | */ |
---|
1337 | CbcSimpleIntegerPseudoCost::CbcSimpleIntegerPseudoCost (CbcModel * model, |
---|
1338 | int iColumn, double downPseudoCost, |
---|
1339 | double upPseudoCost) |
---|
1340 | : CbcSimpleInteger(model,iColumn) |
---|
1341 | { |
---|
1342 | downPseudoCost_ = CoinMax(1.0e-10,downPseudoCost); |
---|
1343 | upPseudoCost_ = CoinMax(1.0e-10,upPseudoCost); |
---|
1344 | breakEven_ = upPseudoCost_/(upPseudoCost_+downPseudoCost_); |
---|
1345 | upDownSeparator_ = -1.0; |
---|
1346 | method_=0; |
---|
1347 | } |
---|
1348 | // Useful constructor - passed and model index and pseudo costs |
---|
1349 | CbcSimpleIntegerPseudoCost::CbcSimpleIntegerPseudoCost (CbcModel * model, int dummy,int iColumn, |
---|
1350 | double downPseudoCost, double upPseudoCost) |
---|
1351 | { |
---|
1352 | CbcSimpleIntegerPseudoCost(model,iColumn,downPseudoCost,upPseudoCost); |
---|
1353 | columnNumber_=iColumn; |
---|
1354 | } |
---|
1355 | |
---|
1356 | // Copy constructor |
---|
1357 | CbcSimpleIntegerPseudoCost::CbcSimpleIntegerPseudoCost ( const CbcSimpleIntegerPseudoCost & rhs) |
---|
1358 | :CbcSimpleInteger(rhs), |
---|
1359 | downPseudoCost_(rhs.downPseudoCost_), |
---|
1360 | upPseudoCost_(rhs.upPseudoCost_), |
---|
1361 | upDownSeparator_(rhs.upDownSeparator_), |
---|
1362 | method_(rhs.method_) |
---|
1363 | |
---|
1364 | { |
---|
1365 | } |
---|
1366 | |
---|
1367 | // Clone |
---|
1368 | CbcObject * |
---|
1369 | CbcSimpleIntegerPseudoCost::clone() const |
---|
1370 | { |
---|
1371 | return new CbcSimpleIntegerPseudoCost(*this); |
---|
1372 | } |
---|
1373 | |
---|
1374 | // Assignment operator |
---|
1375 | CbcSimpleIntegerPseudoCost & |
---|
1376 | CbcSimpleIntegerPseudoCost::operator=( const CbcSimpleIntegerPseudoCost& rhs) |
---|
1377 | { |
---|
1378 | if (this!=&rhs) { |
---|
1379 | CbcSimpleInteger::operator=(rhs); |
---|
1380 | downPseudoCost_=rhs.downPseudoCost_; |
---|
1381 | upPseudoCost_=rhs.upPseudoCost_; |
---|
1382 | upDownSeparator_=rhs.upDownSeparator_; |
---|
1383 | method_=rhs.method_; |
---|
1384 | } |
---|
1385 | return *this; |
---|
1386 | } |
---|
1387 | |
---|
1388 | // Destructor |
---|
1389 | CbcSimpleIntegerPseudoCost::~CbcSimpleIntegerPseudoCost () |
---|
1390 | { |
---|
1391 | } |
---|
1392 | // Creates a branching object |
---|
1393 | CbcBranchingObject * |
---|
1394 | CbcSimpleIntegerPseudoCost::createBranch(int way) |
---|
1395 | { |
---|
1396 | OsiSolverInterface * solver = model_->solver(); |
---|
1397 | const double * solution = model_->testSolution(); |
---|
1398 | const double * lower = solver->getColLower(); |
---|
1399 | const double * upper = solver->getColUpper(); |
---|
1400 | double value = solution[columnNumber_]; |
---|
1401 | value = CoinMax(value, lower[columnNumber_]); |
---|
1402 | value = CoinMin(value, upper[columnNumber_]); |
---|
1403 | #ifndef NDEBUG |
---|
1404 | double nearest = floor(value+0.5); |
---|
1405 | double integerTolerance = |
---|
1406 | model_->getDblParam(CbcModel::CbcIntegerTolerance); |
---|
1407 | assert (upper[columnNumber_]>lower[columnNumber_]); |
---|
1408 | #endif |
---|
1409 | if (!model_->hotstartSolution()) { |
---|
1410 | assert (fabs(value-nearest)>integerTolerance); |
---|
1411 | } else { |
---|
1412 | const double * hotstartSolution = model_->hotstartSolution(); |
---|
1413 | double targetValue = hotstartSolution[columnNumber_]; |
---|
1414 | if (way>0) |
---|
1415 | value = targetValue-0.1; |
---|
1416 | else |
---|
1417 | value = targetValue+0.1; |
---|
1418 | } |
---|
1419 | CbcIntegerPseudoCostBranchingObject * newObject = |
---|
1420 | new CbcIntegerPseudoCostBranchingObject(model_,columnNumber_,way, |
---|
1421 | value); |
---|
1422 | double up = upPseudoCost_*(ceil(value)-value); |
---|
1423 | double down = downPseudoCost_*(value-floor(value)); |
---|
1424 | double changeInGuessed=up-down; |
---|
1425 | if (way>0) |
---|
1426 | changeInGuessed = - changeInGuessed; |
---|
1427 | changeInGuessed=CoinMax(0.0,changeInGuessed); |
---|
1428 | //if (way>0) |
---|
1429 | //changeInGuessed += 1.0e8; // bias to stay up |
---|
1430 | newObject->setChangeInGuessed(changeInGuessed); |
---|
1431 | newObject->setOriginalObject(this); |
---|
1432 | return newObject; |
---|
1433 | } |
---|
1434 | // Infeasibility - large is 0.5 |
---|
1435 | double |
---|
1436 | CbcSimpleIntegerPseudoCost::infeasibility(int & preferredWay) const |
---|
1437 | { |
---|
1438 | OsiSolverInterface * solver = model_->solver(); |
---|
1439 | const double * solution = model_->testSolution(); |
---|
1440 | const double * lower = solver->getColLower(); |
---|
1441 | const double * upper = solver->getColUpper(); |
---|
1442 | if (upper[columnNumber_]==lower[columnNumber_]) { |
---|
1443 | // fixed |
---|
1444 | preferredWay=1; |
---|
1445 | return 0.0; |
---|
1446 | } |
---|
1447 | double value = solution[columnNumber_]; |
---|
1448 | value = CoinMax(value, lower[columnNumber_]); |
---|
1449 | value = CoinMin(value, upper[columnNumber_]); |
---|
1450 | /*printf("%d %g %g %g %g\n",columnNumber_,value,lower[columnNumber_], |
---|
1451 | solution[columnNumber_],upper[columnNumber_]);*/ |
---|
1452 | double nearest = floor(value+0.5); |
---|
1453 | double integerTolerance = |
---|
1454 | model_->getDblParam(CbcModel::CbcIntegerTolerance); |
---|
1455 | double below = floor(value+integerTolerance); |
---|
1456 | double above = below+1.0; |
---|
1457 | if (above>upper[columnNumber_]) { |
---|
1458 | above=below; |
---|
1459 | below = above -1; |
---|
1460 | } |
---|
1461 | double downCost = CoinMax((value-below)*downPseudoCost_,0.0); |
---|
1462 | double upCost = CoinMax((above-value)*upPseudoCost_,0.0); |
---|
1463 | if (downCost>=upCost) |
---|
1464 | preferredWay=1; |
---|
1465 | else |
---|
1466 | preferredWay=-1; |
---|
1467 | // See if up down choice set |
---|
1468 | if (upDownSeparator_>0.0) { |
---|
1469 | preferredWay = (value-below>=upDownSeparator_) ? 1 : -1; |
---|
1470 | } |
---|
1471 | if (preferredWay_) |
---|
1472 | preferredWay=preferredWay_; |
---|
1473 | if (fabs(value-nearest)<=integerTolerance) { |
---|
1474 | return 0.0; |
---|
1475 | } else { |
---|
1476 | // can't get at model so 1,2 don't make sense |
---|
1477 | assert(method_<1||method_>2); |
---|
1478 | if (!method_) |
---|
1479 | return CoinMin(downCost,upCost); |
---|
1480 | else |
---|
1481 | return CoinMax(downCost,upCost); |
---|
1482 | } |
---|
1483 | } |
---|
1484 | |
---|
1485 | // Return "up" estimate |
---|
1486 | double |
---|
1487 | CbcSimpleIntegerPseudoCost::upEstimate() const |
---|
1488 | { |
---|
1489 | OsiSolverInterface * solver = model_->solver(); |
---|
1490 | const double * solution = model_->testSolution(); |
---|
1491 | const double * lower = solver->getColLower(); |
---|
1492 | const double * upper = solver->getColUpper(); |
---|
1493 | double value = solution[columnNumber_]; |
---|
1494 | value = CoinMax(value, lower[columnNumber_]); |
---|
1495 | value = CoinMin(value, upper[columnNumber_]); |
---|
1496 | if (upper[columnNumber_]==lower[columnNumber_]) { |
---|
1497 | // fixed |
---|
1498 | return 0.0; |
---|
1499 | } |
---|
1500 | double integerTolerance = |
---|
1501 | model_->getDblParam(CbcModel::CbcIntegerTolerance); |
---|
1502 | double below = floor(value+integerTolerance); |
---|
1503 | double above = below+1.0; |
---|
1504 | if (above>upper[columnNumber_]) { |
---|
1505 | above=below; |
---|
1506 | below = above -1; |
---|
1507 | } |
---|
1508 | double upCost = CoinMax((above-value)*upPseudoCost_,0.0); |
---|
1509 | return upCost; |
---|
1510 | } |
---|
1511 | // Return "down" estimate |
---|
1512 | double |
---|
1513 | CbcSimpleIntegerPseudoCost::downEstimate() const |
---|
1514 | { |
---|
1515 | OsiSolverInterface * solver = model_->solver(); |
---|
1516 | const double * solution = model_->testSolution(); |
---|
1517 | const double * lower = solver->getColLower(); |
---|
1518 | const double * upper = solver->getColUpper(); |
---|
1519 | double value = solution[columnNumber_]; |
---|
1520 | value = CoinMax(value, lower[columnNumber_]); |
---|
1521 | value = CoinMin(value, upper[columnNumber_]); |
---|
1522 | if (upper[columnNumber_]==lower[columnNumber_]) { |
---|
1523 | // fixed |
---|
1524 | return 0.0; |
---|
1525 | } |
---|
1526 | double integerTolerance = |
---|
1527 | model_->getDblParam(CbcModel::CbcIntegerTolerance); |
---|
1528 | double below = floor(value+integerTolerance); |
---|
1529 | double above = below+1.0; |
---|
1530 | if (above>upper[columnNumber_]) { |
---|
1531 | above=below; |
---|
1532 | below = above -1; |
---|
1533 | } |
---|
1534 | double downCost = CoinMax((value-below)*downPseudoCost_,0.0); |
---|
1535 | return downCost; |
---|
1536 | } |
---|
1537 | |
---|
1538 | // Default Constructor |
---|
1539 | CbcIntegerPseudoCostBranchingObject::CbcIntegerPseudoCostBranchingObject() |
---|
1540 | :CbcIntegerBranchingObject() |
---|
1541 | { |
---|
1542 | changeInGuessed_=1.0e-5; |
---|
1543 | } |
---|
1544 | |
---|
1545 | // Useful constructor |
---|
1546 | CbcIntegerPseudoCostBranchingObject::CbcIntegerPseudoCostBranchingObject (CbcModel * model, |
---|
1547 | int variable, int way , double value) |
---|
1548 | :CbcIntegerBranchingObject(model,variable,way,value) |
---|
1549 | { |
---|
1550 | } |
---|
1551 | // Useful constructor for fixing |
---|
1552 | CbcIntegerPseudoCostBranchingObject::CbcIntegerPseudoCostBranchingObject (CbcModel * model, |
---|
1553 | int variable, int way, |
---|
1554 | double lowerValue, |
---|
1555 | double upperValue) |
---|
1556 | :CbcIntegerBranchingObject(model,variable,way,lowerValue) |
---|
1557 | { |
---|
1558 | changeInGuessed_=1.0e100; |
---|
1559 | } |
---|
1560 | |
---|
1561 | |
---|
1562 | // Copy constructor |
---|
1563 | CbcIntegerPseudoCostBranchingObject::CbcIntegerPseudoCostBranchingObject ( |
---|
1564 | const CbcIntegerPseudoCostBranchingObject & rhs) |
---|
1565 | :CbcIntegerBranchingObject(rhs) |
---|
1566 | { |
---|
1567 | changeInGuessed_ = rhs.changeInGuessed_; |
---|
1568 | } |
---|
1569 | |
---|
1570 | // Assignment operator |
---|
1571 | CbcIntegerPseudoCostBranchingObject & |
---|
1572 | CbcIntegerPseudoCostBranchingObject::operator=( const CbcIntegerPseudoCostBranchingObject& rhs) |
---|
1573 | { |
---|
1574 | if (this != &rhs) { |
---|
1575 | CbcIntegerBranchingObject::operator=(rhs); |
---|
1576 | changeInGuessed_ = rhs.changeInGuessed_; |
---|
1577 | } |
---|
1578 | return *this; |
---|
1579 | } |
---|
1580 | CbcBranchingObject * |
---|
1581 | CbcIntegerPseudoCostBranchingObject::clone() const |
---|
1582 | { |
---|
1583 | return (new CbcIntegerPseudoCostBranchingObject(*this)); |
---|
1584 | } |
---|
1585 | |
---|
1586 | |
---|
1587 | // Destructor |
---|
1588 | CbcIntegerPseudoCostBranchingObject::~CbcIntegerPseudoCostBranchingObject () |
---|
1589 | { |
---|
1590 | } |
---|
1591 | |
---|
1592 | /* |
---|
1593 | Perform a branch by adjusting the bounds of the specified variable. Note |
---|
1594 | that each arm of the branch advances the object to the next arm by |
---|
1595 | advancing the value of way_. |
---|
1596 | |
---|
1597 | Providing new values for the variable's lower and upper bounds for each |
---|
1598 | branching direction gives a little bit of additional flexibility and will |
---|
1599 | be easily extensible to multi-way branching. |
---|
1600 | Returns change in guessed objective on next branch |
---|
1601 | */ |
---|
1602 | double |
---|
1603 | CbcIntegerPseudoCostBranchingObject::branch() |
---|
1604 | { |
---|
1605 | CbcIntegerBranchingObject::branch(); |
---|
1606 | return changeInGuessed_; |
---|
1607 | } |
---|
1608 | |
---|
1609 | |
---|
1610 | // Default Constructor |
---|
1611 | CbcCliqueBranchingObject::CbcCliqueBranchingObject() |
---|
1612 | :CbcBranchingObject() |
---|
1613 | { |
---|
1614 | clique_ = NULL; |
---|
1615 | downMask_[0]=0; |
---|
1616 | downMask_[1]=0; |
---|
1617 | upMask_[0]=0; |
---|
1618 | upMask_[1]=0; |
---|
1619 | } |
---|
1620 | |
---|
1621 | // Useful constructor |
---|
1622 | CbcCliqueBranchingObject::CbcCliqueBranchingObject (CbcModel * model, |
---|
1623 | const CbcClique * clique, |
---|
1624 | int way , |
---|
1625 | int numberOnDownSide, const int * down, |
---|
1626 | int numberOnUpSide, const int * up) |
---|
1627 | :CbcBranchingObject(model,clique->id(),way,0.5) |
---|
1628 | { |
---|
1629 | clique_ = clique; |
---|
1630 | downMask_[0]=0; |
---|
1631 | downMask_[1]=0; |
---|
1632 | upMask_[0]=0; |
---|
1633 | upMask_[1]=0; |
---|
1634 | int i; |
---|
1635 | for (i=0;i<numberOnDownSide;i++) { |
---|
1636 | int sequence = down[i]; |
---|
1637 | int iWord = sequence>>5; |
---|
1638 | int iBit = sequence - 32*iWord; |
---|
1639 | unsigned int k = 1<<iBit; |
---|
1640 | downMask_[iWord] |= k; |
---|
1641 | } |
---|
1642 | for (i=0;i<numberOnUpSide;i++) { |
---|
1643 | int sequence = up[i]; |
---|
1644 | int iWord = sequence>>5; |
---|
1645 | int iBit = sequence - 32*iWord; |
---|
1646 | unsigned int k = 1<<iBit; |
---|
1647 | upMask_[iWord] |= k; |
---|
1648 | } |
---|
1649 | } |
---|
1650 | |
---|
1651 | // Copy constructor |
---|
1652 | CbcCliqueBranchingObject::CbcCliqueBranchingObject ( const CbcCliqueBranchingObject & rhs) :CbcBranchingObject(rhs) |
---|
1653 | { |
---|
1654 | clique_=rhs.clique_; |
---|
1655 | downMask_[0]=rhs.downMask_[0]; |
---|
1656 | downMask_[1]=rhs.downMask_[1]; |
---|
1657 | upMask_[0]=rhs.upMask_[0]; |
---|
1658 | upMask_[1]=rhs.upMask_[1]; |
---|
1659 | } |
---|
1660 | |
---|
1661 | // Assignment operator |
---|
1662 | CbcCliqueBranchingObject & |
---|
1663 | CbcCliqueBranchingObject::operator=( const CbcCliqueBranchingObject& rhs) |
---|
1664 | { |
---|
1665 | if (this != &rhs) { |
---|
1666 | CbcBranchingObject::operator=(rhs); |
---|
1667 | clique_=rhs.clique_; |
---|
1668 | downMask_[0]=rhs.downMask_[0]; |
---|
1669 | downMask_[1]=rhs.downMask_[1]; |
---|
1670 | upMask_[0]=rhs.upMask_[0]; |
---|
1671 | upMask_[1]=rhs.upMask_[1]; |
---|
1672 | } |
---|
1673 | return *this; |
---|
1674 | } |
---|
1675 | CbcBranchingObject * |
---|
1676 | CbcCliqueBranchingObject::clone() const |
---|
1677 | { |
---|
1678 | return (new CbcCliqueBranchingObject(*this)); |
---|
1679 | } |
---|
1680 | |
---|
1681 | |
---|
1682 | // Destructor |
---|
1683 | CbcCliqueBranchingObject::~CbcCliqueBranchingObject () |
---|
1684 | { |
---|
1685 | } |
---|
1686 | double |
---|
1687 | CbcCliqueBranchingObject::branch() |
---|
1688 | { |
---|
1689 | decrementNumberBranchesLeft(); |
---|
1690 | int iWord; |
---|
1691 | int numberMembers = clique_->numberMembers(); |
---|
1692 | const int * which = clique_->members(); |
---|
1693 | const int * integerVariables = model_->integerVariable(); |
---|
1694 | int numberWords=(numberMembers+31)>>5; |
---|
1695 | // *** for way - up means fix all those in down section |
---|
1696 | if (way_<0) { |
---|
1697 | #ifdef FULL_PRINT |
---|
1698 | printf("Down Fix "); |
---|
1699 | #endif |
---|
1700 | for (iWord=0;iWord<numberWords;iWord++) { |
---|
1701 | int i; |
---|
1702 | for (i=0;i<32;i++) { |
---|
1703 | unsigned int k = 1<<i; |
---|
1704 | if ((upMask_[iWord]&k)!=0) { |
---|
1705 | int iColumn = which[i+32*iWord]; |
---|
1706 | #ifdef FULL_PRINT |
---|
1707 | printf("%d ",i+32*iWord); |
---|
1708 | #endif |
---|
1709 | // fix weak way |
---|
1710 | if (clique_->type(i+32*iWord)) |
---|
1711 | model_->solver()->setColUpper(integerVariables[iColumn],0.0); |
---|
1712 | else |
---|
1713 | model_->solver()->setColLower(integerVariables[iColumn],1.0); |
---|
1714 | } |
---|
1715 | } |
---|
1716 | } |
---|
1717 | way_=1; // Swap direction |
---|
1718 | } else { |
---|
1719 | #ifdef FULL_PRINT |
---|
1720 | printf("Up Fix "); |
---|
1721 | #endif |
---|
1722 | for (iWord=0;iWord<numberWords;iWord++) { |
---|
1723 | int i; |
---|
1724 | for (i=0;i<32;i++) { |
---|
1725 | unsigned int k = 1<<i; |
---|
1726 | if ((downMask_[iWord]&k)!=0) { |
---|
1727 | int iColumn = which[i+32*iWord]; |
---|
1728 | #ifdef FULL_PRINT |
---|
1729 | printf("%d ",i+32*iWord); |
---|
1730 | #endif |
---|
1731 | // fix weak way |
---|
1732 | if (clique_->type(i+32*iWord)) |
---|
1733 | model_->solver()->setColUpper(integerVariables[iColumn],0.0); |
---|
1734 | else |
---|
1735 | model_->solver()->setColLower(integerVariables[iColumn],1.0); |
---|
1736 | } |
---|
1737 | } |
---|
1738 | } |
---|
1739 | way_=-1; // Swap direction |
---|
1740 | } |
---|
1741 | #ifdef FULL_PRINT |
---|
1742 | printf("\n"); |
---|
1743 | #endif |
---|
1744 | return 0.0; |
---|
1745 | } |
---|
1746 | // Print what would happen |
---|
1747 | void |
---|
1748 | CbcCliqueBranchingObject::print() |
---|
1749 | { |
---|
1750 | int iWord; |
---|
1751 | int numberMembers = clique_->numberMembers(); |
---|
1752 | const int * which = clique_->members(); |
---|
1753 | const int * integerVariables = model_->integerVariable(); |
---|
1754 | int numberWords=(numberMembers+31)>>5; |
---|
1755 | // *** for way - up means fix all those in down section |
---|
1756 | if (way_<0) { |
---|
1757 | printf("Clique - Down Fix "); |
---|
1758 | for (iWord=0;iWord<numberWords;iWord++) { |
---|
1759 | int i; |
---|
1760 | for (i=0;i<32;i++) { |
---|
1761 | unsigned int k = 1<<i; |
---|
1762 | if ((upMask_[iWord]&k)!=0) { |
---|
1763 | int iColumn = which[i+32*iWord]; |
---|
1764 | printf("%d ",integerVariables[iColumn]); |
---|
1765 | } |
---|
1766 | } |
---|
1767 | } |
---|
1768 | } else { |
---|
1769 | printf("Clique - Up Fix "); |
---|
1770 | for (iWord=0;iWord<numberWords;iWord++) { |
---|
1771 | int i; |
---|
1772 | for (i=0;i<32;i++) { |
---|
1773 | unsigned int k = 1<<i; |
---|
1774 | if ((downMask_[iWord]&k)!=0) { |
---|
1775 | int iColumn = which[i+32*iWord]; |
---|
1776 | printf("%d ",integerVariables[iColumn]); |
---|
1777 | } |
---|
1778 | } |
---|
1779 | } |
---|
1780 | } |
---|
1781 | printf("\n"); |
---|
1782 | } |
---|
1783 | |
---|
1784 | // Default Constructor |
---|
1785 | CbcLongCliqueBranchingObject::CbcLongCliqueBranchingObject() |
---|
1786 | :CbcBranchingObject() |
---|
1787 | { |
---|
1788 | clique_=NULL; |
---|
1789 | downMask_=NULL; |
---|
1790 | upMask_=NULL; |
---|
1791 | } |
---|
1792 | |
---|
1793 | // Useful constructor |
---|
1794 | CbcLongCliqueBranchingObject::CbcLongCliqueBranchingObject (CbcModel * model, |
---|
1795 | const CbcClique * clique, |
---|
1796 | int way , |
---|
1797 | int numberOnDownSide, const int * down, |
---|
1798 | int numberOnUpSide, const int * up) |
---|
1799 | :CbcBranchingObject(model,clique->id(),way,0.5) |
---|
1800 | { |
---|
1801 | clique_ = clique; |
---|
1802 | int numberMembers = clique_->numberMembers(); |
---|
1803 | int numberWords=(numberMembers+31)>>5; |
---|
1804 | downMask_ = new unsigned int [numberWords]; |
---|
1805 | upMask_ = new unsigned int [numberWords]; |
---|
1806 | memset(downMask_,0,numberWords*sizeof(unsigned int)); |
---|
1807 | memset(upMask_,0,numberWords*sizeof(unsigned int)); |
---|
1808 | int i; |
---|
1809 | for (i=0;i<numberOnDownSide;i++) { |
---|
1810 | int sequence = down[i]; |
---|
1811 | int iWord = sequence>>5; |
---|
1812 | int iBit = sequence - 32*iWord; |
---|
1813 | unsigned int k = 1<<iBit; |
---|
1814 | downMask_[iWord] |= k; |
---|
1815 | } |
---|
1816 | for (i=0;i<numberOnUpSide;i++) { |
---|
1817 | int sequence = up[i]; |
---|
1818 | int iWord = sequence>>5; |
---|
1819 | int iBit = sequence - 32*iWord; |
---|
1820 | unsigned int k = 1<<iBit; |
---|
1821 | upMask_[iWord] |= k; |
---|
1822 | } |
---|
1823 | } |
---|
1824 | |
---|
1825 | // Copy constructor |
---|
1826 | CbcLongCliqueBranchingObject::CbcLongCliqueBranchingObject ( const CbcLongCliqueBranchingObject & rhs) :CbcBranchingObject(rhs) |
---|
1827 | { |
---|
1828 | clique_=rhs.clique_; |
---|
1829 | if (rhs.downMask_) { |
---|
1830 | int numberMembers = clique_->numberMembers(); |
---|
1831 | int numberWords=(numberMembers+31)>>5; |
---|
1832 | downMask_ = new unsigned int [numberWords]; |
---|
1833 | memcpy(downMask_,rhs.downMask_,numberWords*sizeof(unsigned int)); |
---|
1834 | upMask_ = new unsigned int [numberWords]; |
---|
1835 | memcpy(upMask_,rhs.upMask_,numberWords*sizeof(unsigned int)); |
---|
1836 | } else { |
---|
1837 | downMask_=NULL; |
---|
1838 | upMask_=NULL; |
---|
1839 | } |
---|
1840 | } |
---|
1841 | |
---|
1842 | // Assignment operator |
---|
1843 | CbcLongCliqueBranchingObject & |
---|
1844 | CbcLongCliqueBranchingObject::operator=( const CbcLongCliqueBranchingObject& rhs) |
---|
1845 | { |
---|
1846 | if (this != &rhs) { |
---|
1847 | CbcBranchingObject::operator=(rhs); |
---|
1848 | clique_=rhs.clique_; |
---|
1849 | delete [] downMask_; |
---|
1850 | delete [] upMask_; |
---|
1851 | if (rhs.downMask_) { |
---|
1852 | int numberMembers = clique_->numberMembers(); |
---|
1853 | int numberWords=(numberMembers+31)>>5; |
---|
1854 | downMask_ = new unsigned int [numberWords]; |
---|
1855 | memcpy(downMask_,rhs.downMask_,numberWords*sizeof(unsigned int)); |
---|
1856 | upMask_ = new unsigned int [numberWords]; |
---|
1857 | memcpy(upMask_,rhs.upMask_,numberWords*sizeof(unsigned int)); |
---|
1858 | } else { |
---|
1859 | downMask_=NULL; |
---|
1860 | upMask_=NULL; |
---|
1861 | } |
---|
1862 | } |
---|
1863 | return *this; |
---|
1864 | } |
---|
1865 | CbcBranchingObject * |
---|
1866 | CbcLongCliqueBranchingObject::clone() const |
---|
1867 | { |
---|
1868 | return (new CbcLongCliqueBranchingObject(*this)); |
---|
1869 | } |
---|
1870 | |
---|
1871 | |
---|
1872 | // Destructor |
---|
1873 | CbcLongCliqueBranchingObject::~CbcLongCliqueBranchingObject () |
---|
1874 | { |
---|
1875 | delete [] downMask_; |
---|
1876 | delete [] upMask_; |
---|
1877 | } |
---|
1878 | double |
---|
1879 | CbcLongCliqueBranchingObject::branch() |
---|
1880 | { |
---|
1881 | decrementNumberBranchesLeft(); |
---|
1882 | int iWord; |
---|
1883 | int numberMembers = clique_->numberMembers(); |
---|
1884 | const int * which = clique_->members(); |
---|
1885 | const int * integerVariables = model_->integerVariable(); |
---|
1886 | int numberWords=(numberMembers+31)>>5; |
---|
1887 | // *** for way - up means fix all those in down section |
---|
1888 | if (way_<0) { |
---|
1889 | #ifdef FULL_PRINT |
---|
1890 | printf("Down Fix "); |
---|
1891 | #endif |
---|
1892 | for (iWord=0;iWord<numberWords;iWord++) { |
---|
1893 | int i; |
---|
1894 | for (i=0;i<32;i++) { |
---|
1895 | unsigned int k = 1<<i; |
---|
1896 | if ((upMask_[iWord]&k)!=0) { |
---|
1897 | int iColumn = which[i+32*iWord]; |
---|
1898 | #ifdef FULL_PRINT |
---|
1899 | printf("%d ",i+32*iWord); |
---|
1900 | #endif |
---|
1901 | // fix weak way |
---|
1902 | if (clique_->type(i+32*iWord)) |
---|
1903 | model_->solver()->setColUpper(integerVariables[iColumn],0.0); |
---|
1904 | else |
---|
1905 | model_->solver()->setColLower(integerVariables[iColumn],1.0); |
---|
1906 | } |
---|
1907 | } |
---|
1908 | } |
---|
1909 | way_=1; // Swap direction |
---|
1910 | } else { |
---|
1911 | #ifdef FULL_PRINT |
---|
1912 | printf("Up Fix "); |
---|
1913 | #endif |
---|
1914 | for (iWord=0;iWord<numberWords;iWord++) { |
---|
1915 | int i; |
---|
1916 | for (i=0;i<32;i++) { |
---|
1917 | unsigned int k = 1<<i; |
---|
1918 | if ((downMask_[iWord]&k)!=0) { |
---|
1919 | int iColumn = which[i+32*iWord]; |
---|
1920 | #ifdef FULL_PRINT |
---|
1921 | printf("%d ",i+32*iWord); |
---|
1922 | #endif |
---|
1923 | // fix weak way |
---|
1924 | if (clique_->type(i+32*iWord)) |
---|
1925 | model_->solver()->setColUpper(integerVariables[iColumn],0.0); |
---|
1926 | else |
---|
1927 | model_->solver()->setColLower(integerVariables[iColumn],1.0); |
---|
1928 | } |
---|
1929 | } |
---|
1930 | } |
---|
1931 | way_=-1; // Swap direction |
---|
1932 | } |
---|
1933 | #ifdef FULL_PRINT |
---|
1934 | printf("\n"); |
---|
1935 | #endif |
---|
1936 | return 0.0; |
---|
1937 | } |
---|
1938 | void |
---|
1939 | CbcLongCliqueBranchingObject::print() |
---|
1940 | { |
---|
1941 | int iWord; |
---|
1942 | int numberMembers = clique_->numberMembers(); |
---|
1943 | const int * which = clique_->members(); |
---|
1944 | const int * integerVariables = model_->integerVariable(); |
---|
1945 | int numberWords=(numberMembers+31)>>5; |
---|
1946 | // *** for way - up means fix all those in down section |
---|
1947 | if (way_<0) { |
---|
1948 | printf("Clique - Down Fix "); |
---|
1949 | for (iWord=0;iWord<numberWords;iWord++) { |
---|
1950 | int i; |
---|
1951 | for (i=0;i<32;i++) { |
---|
1952 | unsigned int k = 1<<i; |
---|
1953 | if ((upMask_[iWord]&k)!=0) { |
---|
1954 | int iColumn = which[i+32*iWord]; |
---|
1955 | printf("%d ",integerVariables[iColumn]); |
---|
1956 | } |
---|
1957 | } |
---|
1958 | } |
---|
1959 | } else { |
---|
1960 | printf("Clique - Up Fix "); |
---|
1961 | for (iWord=0;iWord<numberWords;iWord++) { |
---|
1962 | int i; |
---|
1963 | for (i=0;i<32;i++) { |
---|
1964 | unsigned int k = 1<<i; |
---|
1965 | if ((downMask_[iWord]&k)!=0) { |
---|
1966 | int iColumn = which[i+32*iWord]; |
---|
1967 | printf("%d ",integerVariables[iColumn]); |
---|
1968 | } |
---|
1969 | } |
---|
1970 | } |
---|
1971 | } |
---|
1972 | printf("\n"); |
---|
1973 | } |
---|
1974 | // Default Constructor |
---|
1975 | CbcSOSBranchingObject::CbcSOSBranchingObject() |
---|
1976 | :CbcBranchingObject() |
---|
1977 | { |
---|
1978 | set_ = NULL; |
---|
1979 | separator_=0.0; |
---|
1980 | } |
---|
1981 | |
---|
1982 | // Useful constructor |
---|
1983 | CbcSOSBranchingObject::CbcSOSBranchingObject (CbcModel * model, |
---|
1984 | const CbcSOS * set, |
---|
1985 | int way , |
---|
1986 | double separator) |
---|
1987 | :CbcBranchingObject(model,set->id(),way,0.5) |
---|
1988 | { |
---|
1989 | set_ = set; |
---|
1990 | separator_ = separator; |
---|
1991 | } |
---|
1992 | |
---|
1993 | // Copy constructor |
---|
1994 | CbcSOSBranchingObject::CbcSOSBranchingObject ( const CbcSOSBranchingObject & rhs) :CbcBranchingObject(rhs) |
---|
1995 | { |
---|
1996 | set_=rhs.set_; |
---|
1997 | separator_ = rhs.separator_; |
---|
1998 | } |
---|
1999 | |
---|
2000 | // Assignment operator |
---|
2001 | CbcSOSBranchingObject & |
---|
2002 | CbcSOSBranchingObject::operator=( const CbcSOSBranchingObject& rhs) |
---|
2003 | { |
---|
2004 | if (this != &rhs) { |
---|
2005 | CbcBranchingObject::operator=(rhs); |
---|
2006 | set_=rhs.set_; |
---|
2007 | separator_ = rhs.separator_; |
---|
2008 | } |
---|
2009 | return *this; |
---|
2010 | } |
---|
2011 | CbcBranchingObject * |
---|
2012 | CbcSOSBranchingObject::clone() const |
---|
2013 | { |
---|
2014 | return (new CbcSOSBranchingObject(*this)); |
---|
2015 | } |
---|
2016 | |
---|
2017 | |
---|
2018 | // Destructor |
---|
2019 | CbcSOSBranchingObject::~CbcSOSBranchingObject () |
---|
2020 | { |
---|
2021 | } |
---|
2022 | double |
---|
2023 | CbcSOSBranchingObject::branch() |
---|
2024 | { |
---|
2025 | decrementNumberBranchesLeft(); |
---|
2026 | int numberMembers = set_->numberMembers(); |
---|
2027 | const int * which = set_->members(); |
---|
2028 | const double * weights = set_->weights(); |
---|
2029 | OsiSolverInterface * solver = model_->solver(); |
---|
2030 | //const double * lower = solver->getColLower(); |
---|
2031 | //const double * upper = solver->getColUpper(); |
---|
2032 | // *** for way - up means fix all those in down section |
---|
2033 | if (way_<0) { |
---|
2034 | int i; |
---|
2035 | for ( i=0;i<numberMembers;i++) { |
---|
2036 | if (weights[i] > separator_) |
---|
2037 | break; |
---|
2038 | } |
---|
2039 | assert (i<numberMembers); |
---|
2040 | for (;i<numberMembers;i++) |
---|
2041 | solver->setColUpper(which[i],0.0); |
---|
2042 | way_=1; // Swap direction |
---|
2043 | } else { |
---|
2044 | int i; |
---|
2045 | for ( i=0;i<numberMembers;i++) { |
---|
2046 | if (weights[i] >= separator_) |
---|
2047 | break; |
---|
2048 | else |
---|
2049 | solver->setColUpper(which[i],0.0); |
---|
2050 | } |
---|
2051 | assert (i<numberMembers); |
---|
2052 | way_=-1; // Swap direction |
---|
2053 | } |
---|
2054 | return 0.0; |
---|
2055 | } |
---|
2056 | // Print what would happen |
---|
2057 | void |
---|
2058 | CbcSOSBranchingObject::print() |
---|
2059 | { |
---|
2060 | int numberMembers = set_->numberMembers(); |
---|
2061 | const int * which = set_->members(); |
---|
2062 | const double * weights = set_->weights(); |
---|
2063 | OsiSolverInterface * solver = model_->solver(); |
---|
2064 | //const double * lower = solver->getColLower(); |
---|
2065 | const double * upper = solver->getColUpper(); |
---|
2066 | int first=numberMembers; |
---|
2067 | int last=-1; |
---|
2068 | int numberFixed=0; |
---|
2069 | int numberOther=0; |
---|
2070 | int i; |
---|
2071 | for ( i=0;i<numberMembers;i++) { |
---|
2072 | double bound = upper[which[i]]; |
---|
2073 | if (bound) { |
---|
2074 | first = CoinMin(first,i); |
---|
2075 | last = CoinMax(last,i); |
---|
2076 | } |
---|
2077 | } |
---|
2078 | // *** for way - up means fix all those in down section |
---|
2079 | if (way_<0) { |
---|
2080 | printf("SOS Down"); |
---|
2081 | for ( i=0;i<numberMembers;i++) { |
---|
2082 | double bound = upper[which[i]]; |
---|
2083 | if (weights[i] > separator_) |
---|
2084 | break; |
---|
2085 | else if (bound) |
---|
2086 | numberOther++; |
---|
2087 | } |
---|
2088 | assert (i<numberMembers); |
---|
2089 | for (;i<numberMembers;i++) { |
---|
2090 | double bound = upper[which[i]]; |
---|
2091 | if (bound) |
---|
2092 | numberFixed++; |
---|
2093 | } |
---|
2094 | } else { |
---|
2095 | printf("SOS Up"); |
---|
2096 | for ( i=0;i<numberMembers;i++) { |
---|
2097 | double bound = upper[which[i]]; |
---|
2098 | if (weights[i] >= separator_) |
---|
2099 | break; |
---|
2100 | else if (bound) |
---|
2101 | numberFixed++; |
---|
2102 | } |
---|
2103 | assert (i<numberMembers); |
---|
2104 | for (;i<numberMembers;i++) { |
---|
2105 | double bound = upper[which[i]]; |
---|
2106 | if (bound) |
---|
2107 | numberOther++; |
---|
2108 | } |
---|
2109 | } |
---|
2110 | printf(" - at %g, free range %d (%g) => %d (%g), %d would be fixed, %d other way\n", |
---|
2111 | separator_,which[first],weights[first],which[last],weights[last],numberFixed,numberOther); |
---|
2112 | } |
---|
2113 | |
---|
2114 | // Default Constructor |
---|
2115 | CbcBranchDefaultDecision::CbcBranchDefaultDecision() |
---|
2116 | :CbcBranchDecision() |
---|
2117 | { |
---|
2118 | bestCriterion_ = 0.0; |
---|
2119 | bestChangeUp_ = 0.0; |
---|
2120 | bestNumberUp_ = 0; |
---|
2121 | bestChangeDown_ = 0.0; |
---|
2122 | bestObject_ = NULL; |
---|
2123 | bestNumberDown_ = 0; |
---|
2124 | } |
---|
2125 | |
---|
2126 | // Copy constructor |
---|
2127 | CbcBranchDefaultDecision::CbcBranchDefaultDecision ( |
---|
2128 | const CbcBranchDefaultDecision & rhs) |
---|
2129 | :CbcBranchDecision(rhs) |
---|
2130 | { |
---|
2131 | bestCriterion_ = rhs.bestCriterion_; |
---|
2132 | bestChangeUp_ = rhs.bestChangeUp_; |
---|
2133 | bestNumberUp_ = rhs.bestNumberUp_; |
---|
2134 | bestChangeDown_ = rhs.bestChangeDown_; |
---|
2135 | bestNumberDown_ = rhs.bestNumberDown_; |
---|
2136 | bestObject_ = rhs.bestObject_; |
---|
2137 | model_ = rhs.model_; |
---|
2138 | } |
---|
2139 | |
---|
2140 | CbcBranchDefaultDecision::~CbcBranchDefaultDecision() |
---|
2141 | { |
---|
2142 | } |
---|
2143 | |
---|
2144 | // Clone |
---|
2145 | CbcBranchDecision * |
---|
2146 | CbcBranchDefaultDecision::clone() const |
---|
2147 | { |
---|
2148 | return new CbcBranchDefaultDecision(*this); |
---|
2149 | } |
---|
2150 | |
---|
2151 | // Initialize i.e. before start of choosing at a node |
---|
2152 | void |
---|
2153 | CbcBranchDefaultDecision::initialize(CbcModel * model) |
---|
2154 | { |
---|
2155 | bestCriterion_ = 0.0; |
---|
2156 | bestChangeUp_ = 0.0; |
---|
2157 | bestNumberUp_ = 0; |
---|
2158 | bestChangeDown_ = 0.0; |
---|
2159 | bestNumberDown_ = 0; |
---|
2160 | bestObject_ = NULL; |
---|
2161 | model_ = model; |
---|
2162 | } |
---|
2163 | |
---|
2164 | |
---|
2165 | /* |
---|
2166 | Simple default decision algorithm. Compare based on infeasibility (numInfUp, |
---|
2167 | numInfDn) until a solution is found by search, then switch to change in |
---|
2168 | objective (changeUp, changeDn). Note that bestSoFar is remembered in |
---|
2169 | bestObject_, so the parameter bestSoFar is unused. |
---|
2170 | */ |
---|
2171 | |
---|
2172 | int |
---|
2173 | CbcBranchDefaultDecision::betterBranch(CbcBranchingObject * thisOne, |
---|
2174 | CbcBranchingObject * bestSoFar, |
---|
2175 | double changeUp, int numInfUp, |
---|
2176 | double changeDn, int numInfDn) |
---|
2177 | { |
---|
2178 | bool beforeSolution = cbcModel()->getSolutionCount()== |
---|
2179 | cbcModel()->getNumberHeuristicSolutions();; |
---|
2180 | int betterWay=0; |
---|
2181 | if (beforeSolution) { |
---|
2182 | if (!bestObject_) { |
---|
2183 | bestNumberUp_=COIN_INT_MAX; |
---|
2184 | bestNumberDown_=COIN_INT_MAX; |
---|
2185 | } |
---|
2186 | // before solution - choose smallest number |
---|
2187 | // could add in depth as well |
---|
2188 | int bestNumber = CoinMin(bestNumberUp_,bestNumberDown_); |
---|
2189 | if (numInfUp<numInfDn) { |
---|
2190 | if (numInfUp<bestNumber) { |
---|
2191 | betterWay = 1; |
---|
2192 | } else if (numInfUp==bestNumber) { |
---|
2193 | if (changeUp<bestCriterion_) |
---|
2194 | betterWay=1; |
---|
2195 | } |
---|
2196 | } else if (numInfUp>numInfDn) { |
---|
2197 | if (numInfDn<bestNumber) { |
---|
2198 | betterWay = -1; |
---|
2199 | } else if (numInfDn==bestNumber) { |
---|
2200 | if (changeDn<bestCriterion_) |
---|
2201 | betterWay=-1; |
---|
2202 | } |
---|
2203 | } else { |
---|
2204 | // up and down have same number |
---|
2205 | bool better=false; |
---|
2206 | if (numInfUp<bestNumber) { |
---|
2207 | better=true; |
---|
2208 | } else if (numInfUp==bestNumber) { |
---|
2209 | if (min(changeUp,changeDn)<bestCriterion_) |
---|
2210 | better=true;; |
---|
2211 | } |
---|
2212 | if (better) { |
---|
2213 | // see which way |
---|
2214 | if (changeUp<=changeDn) |
---|
2215 | betterWay=1; |
---|
2216 | else |
---|
2217 | betterWay=-1; |
---|
2218 | } |
---|
2219 | } |
---|
2220 | } else { |
---|
2221 | if (!bestObject_) { |
---|
2222 | bestCriterion_=-1.0; |
---|
2223 | } |
---|
2224 | // got a solution |
---|
2225 | if (changeUp<=changeDn) { |
---|
2226 | if (changeUp>bestCriterion_) |
---|
2227 | betterWay=1; |
---|
2228 | } else { |
---|
2229 | if (changeDn>bestCriterion_) |
---|
2230 | betterWay=-1; |
---|
2231 | } |
---|
2232 | } |
---|
2233 | if (betterWay) { |
---|
2234 | bestCriterion_ = CoinMin(changeUp,changeDn); |
---|
2235 | bestChangeUp_ = changeUp; |
---|
2236 | bestNumberUp_ = numInfUp; |
---|
2237 | bestChangeDown_ = changeDn; |
---|
2238 | bestNumberDown_ = numInfDn; |
---|
2239 | bestObject_=thisOne; |
---|
2240 | // See if user is overriding way |
---|
2241 | if (thisOne->object()&&thisOne->object()->preferredWay()) |
---|
2242 | betterWay = thisOne->object()->preferredWay(); |
---|
2243 | } |
---|
2244 | return betterWay; |
---|
2245 | } |
---|
2246 | /* Sets or gets best criterion so far */ |
---|
2247 | void |
---|
2248 | CbcBranchDefaultDecision::setBestCriterion(double value) |
---|
2249 | { |
---|
2250 | bestCriterion_ = value; |
---|
2251 | } |
---|
2252 | double |
---|
2253 | CbcBranchDefaultDecision::getBestCriterion() const |
---|
2254 | { |
---|
2255 | return bestCriterion_; |
---|
2256 | } |
---|
2257 | |
---|
2258 | /* Compare N branching objects. Return index of best |
---|
2259 | and sets way of branching in chosen object. |
---|
2260 | |
---|
2261 | This routine is used only after strong branching. |
---|
2262 | */ |
---|
2263 | |
---|
2264 | int |
---|
2265 | CbcBranchDefaultDecision::bestBranch (CbcBranchingObject ** objects, int numberObjects, |
---|
2266 | int numberUnsatisfied, |
---|
2267 | double * changeUp, int * numberInfeasibilitiesUp, |
---|
2268 | double * changeDown, int * numberInfeasibilitiesDown, |
---|
2269 | double objectiveValue) |
---|
2270 | { |
---|
2271 | |
---|
2272 | int bestWay=0; |
---|
2273 | int whichObject = -1; |
---|
2274 | if (numberObjects) { |
---|
2275 | CbcModel * model = cbcModel(); |
---|
2276 | // at continuous |
---|
2277 | //double continuousObjective = model->getContinuousObjective(); |
---|
2278 | //int continuousInfeasibilities = model->getContinuousInfeasibilities(); |
---|
2279 | |
---|
2280 | // average cost to get rid of infeasibility |
---|
2281 | //double averageCostPerInfeasibility = |
---|
2282 | //(objectiveValue-continuousObjective)/ |
---|
2283 | //(double) (abs(continuousInfeasibilities-numberUnsatisfied)+1); |
---|
2284 | /* beforeSolution is : |
---|
2285 | 0 - before any solution |
---|
2286 | n - n heuristic solutions but no branched one |
---|
2287 | -1 - branched solution found |
---|
2288 | */ |
---|
2289 | int numberSolutions = model->getSolutionCount(); |
---|
2290 | double cutoff = model->getCutoff(); |
---|
2291 | int method=0; |
---|
2292 | int i; |
---|
2293 | if (numberSolutions) { |
---|
2294 | int numberHeuristic = model->getNumberHeuristicSolutions(); |
---|
2295 | if (numberHeuristic<numberSolutions) { |
---|
2296 | method = 1; |
---|
2297 | } else { |
---|
2298 | method = 2; |
---|
2299 | // look further |
---|
2300 | for ( i = 0 ; i < numberObjects ; i++) { |
---|
2301 | int numberNext = numberInfeasibilitiesUp[i]; |
---|
2302 | |
---|
2303 | if (numberNext<numberUnsatisfied) { |
---|
2304 | int numberUp = numberUnsatisfied - numberInfeasibilitiesUp[i]; |
---|
2305 | double perUnsatisfied = changeUp[i]/(double) numberUp; |
---|
2306 | double estimatedObjective = objectiveValue + numberUnsatisfied * perUnsatisfied; |
---|
2307 | if (estimatedObjective<cutoff) |
---|
2308 | method=3; |
---|
2309 | } |
---|
2310 | numberNext = numberInfeasibilitiesDown[i]; |
---|
2311 | if (numberNext<numberUnsatisfied) { |
---|
2312 | int numberDown = numberUnsatisfied - numberInfeasibilitiesDown[i]; |
---|
2313 | double perUnsatisfied = changeDown[i]/(double) numberDown; |
---|
2314 | double estimatedObjective = objectiveValue + numberUnsatisfied * perUnsatisfied; |
---|
2315 | if (estimatedObjective<cutoff) |
---|
2316 | method=3; |
---|
2317 | } |
---|
2318 | } |
---|
2319 | } |
---|
2320 | method=2; |
---|
2321 | } else { |
---|
2322 | method = 0; |
---|
2323 | } |
---|
2324 | // Uncomment next to force method 4 |
---|
2325 | //method=4; |
---|
2326 | /* Methods : |
---|
2327 | 0 - fewest infeasibilities |
---|
2328 | 1 - largest min change in objective |
---|
2329 | 2 - as 1 but use sum of changes if min close |
---|
2330 | 3 - predicted best solution |
---|
2331 | 4 - take cheapest up branch if infeasibilities same |
---|
2332 | */ |
---|
2333 | int bestNumber=COIN_INT_MAX; |
---|
2334 | double bestCriterion=-1.0e50; |
---|
2335 | double alternativeCriterion = -1.0; |
---|
2336 | double bestEstimate = 1.0e100; |
---|
2337 | switch (method) { |
---|
2338 | case 0: |
---|
2339 | // could add in depth as well |
---|
2340 | for ( i = 0 ; i < numberObjects ; i++) { |
---|
2341 | int thisNumber = min(numberInfeasibilitiesUp[i],numberInfeasibilitiesDown[i]); |
---|
2342 | if (thisNumber<=bestNumber) { |
---|
2343 | int betterWay=0; |
---|
2344 | if (numberInfeasibilitiesUp[i]<numberInfeasibilitiesDown[i]) { |
---|
2345 | if (numberInfeasibilitiesUp[i]<bestNumber) { |
---|
2346 | betterWay = 1; |
---|
2347 | } else { |
---|
2348 | if (changeUp[i]<bestCriterion) |
---|
2349 | betterWay=1; |
---|
2350 | } |
---|
2351 | } else if (numberInfeasibilitiesUp[i]>numberInfeasibilitiesDown[i]) { |
---|
2352 | if (numberInfeasibilitiesDown[i]<bestNumber) { |
---|
2353 | betterWay = -1; |
---|
2354 | } else { |
---|
2355 | if (changeDown[i]<bestCriterion) |
---|
2356 | betterWay=-1; |
---|
2357 | } |
---|
2358 | } else { |
---|
2359 | // up and down have same number |
---|
2360 | bool better=false; |
---|
2361 | if (numberInfeasibilitiesUp[i]<bestNumber) { |
---|
2362 | better=true; |
---|
2363 | } else if (numberInfeasibilitiesUp[i]==bestNumber) { |
---|
2364 | if (min(changeUp[i],changeDown[i])<bestCriterion) |
---|
2365 | better=true;; |
---|
2366 | } |
---|
2367 | if (better) { |
---|
2368 | // see which way |
---|
2369 | if (changeUp[i]<=changeDown[i]) |
---|
2370 | betterWay=1; |
---|
2371 | else |
---|
2372 | betterWay=-1; |
---|
2373 | } |
---|
2374 | } |
---|
2375 | if (betterWay) { |
---|
2376 | bestCriterion = min(changeUp[i],changeDown[i]); |
---|
2377 | bestNumber = thisNumber; |
---|
2378 | whichObject = i; |
---|
2379 | bestWay = betterWay; |
---|
2380 | } |
---|
2381 | } |
---|
2382 | } |
---|
2383 | break; |
---|
2384 | case 1: |
---|
2385 | for ( i = 0 ; i < numberObjects ; i++) { |
---|
2386 | int betterWay=0; |
---|
2387 | if (changeUp[i]<=changeDown[i]) { |
---|
2388 | if (changeUp[i]>bestCriterion) |
---|
2389 | betterWay=1; |
---|
2390 | } else { |
---|
2391 | if (changeDown[i]>bestCriterion) |
---|
2392 | betterWay=-1; |
---|
2393 | } |
---|
2394 | if (betterWay) { |
---|
2395 | bestCriterion = min(changeUp[i],changeDown[i]); |
---|
2396 | whichObject = i; |
---|
2397 | bestWay = betterWay; |
---|
2398 | } |
---|
2399 | } |
---|
2400 | break; |
---|
2401 | case 2: |
---|
2402 | for ( i = 0 ; i < numberObjects ; i++) { |
---|
2403 | double change = min(changeUp[i],changeDown[i]); |
---|
2404 | double sum = changeUp[i] + changeDown[i]; |
---|
2405 | bool take=false; |
---|
2406 | if (change>1.1*bestCriterion) |
---|
2407 | take=true; |
---|
2408 | else if (change>0.9*bestCriterion&&sum+change>bestCriterion+alternativeCriterion) |
---|
2409 | take=true; |
---|
2410 | if (take) { |
---|
2411 | if (changeUp[i]<=changeDown[i]) { |
---|
2412 | if (changeUp[i]>bestCriterion) |
---|
2413 | bestWay=1; |
---|
2414 | } else { |
---|
2415 | if (changeDown[i]>bestCriterion) |
---|
2416 | bestWay=-1; |
---|
2417 | } |
---|
2418 | bestCriterion = change; |
---|
2419 | alternativeCriterion = sum; |
---|
2420 | whichObject = i; |
---|
2421 | } |
---|
2422 | } |
---|
2423 | break; |
---|
2424 | case 3: |
---|
2425 | for ( i = 0 ; i < numberObjects ; i++) { |
---|
2426 | int numberNext = numberInfeasibilitiesUp[i]; |
---|
2427 | |
---|
2428 | if (numberNext<numberUnsatisfied) { |
---|
2429 | int numberUp = numberUnsatisfied - numberInfeasibilitiesUp[i]; |
---|
2430 | double perUnsatisfied = changeUp[i]/(double) numberUp; |
---|
2431 | double estimatedObjective = objectiveValue + numberUnsatisfied * perUnsatisfied; |
---|
2432 | if (estimatedObjective<bestEstimate) { |
---|
2433 | bestEstimate = estimatedObjective; |
---|
2434 | bestWay=1; |
---|
2435 | whichObject=i; |
---|
2436 | } |
---|
2437 | } |
---|
2438 | numberNext = numberInfeasibilitiesDown[i]; |
---|
2439 | if (numberNext<numberUnsatisfied) { |
---|
2440 | int numberDown = numberUnsatisfied - numberInfeasibilitiesDown[i]; |
---|
2441 | double perUnsatisfied = changeDown[i]/(double) numberDown; |
---|
2442 | double estimatedObjective = objectiveValue + numberUnsatisfied * perUnsatisfied; |
---|
2443 | if (estimatedObjective<bestEstimate) { |
---|
2444 | bestEstimate = estimatedObjective; |
---|
2445 | bestWay=-1; |
---|
2446 | whichObject=i; |
---|
2447 | } |
---|
2448 | } |
---|
2449 | } |
---|
2450 | break; |
---|
2451 | case 4: |
---|
2452 | // if number infeas same then cheapest up |
---|
2453 | // first get best number or when going down |
---|
2454 | // now choose smallest change up amongst equal number infeas |
---|
2455 | for ( i = 0 ; i < numberObjects ; i++) { |
---|
2456 | int thisNumber = min(numberInfeasibilitiesUp[i],numberInfeasibilitiesDown[i]); |
---|
2457 | if (thisNumber<=bestNumber) { |
---|
2458 | int betterWay=0; |
---|
2459 | if (numberInfeasibilitiesUp[i]<numberInfeasibilitiesDown[i]) { |
---|
2460 | if (numberInfeasibilitiesUp[i]<bestNumber) { |
---|
2461 | betterWay = 1; |
---|
2462 | } else { |
---|
2463 | if (changeUp[i]<bestCriterion) |
---|
2464 | betterWay=1; |
---|
2465 | } |
---|
2466 | } else if (numberInfeasibilitiesUp[i]>numberInfeasibilitiesDown[i]) { |
---|
2467 | if (numberInfeasibilitiesDown[i]<bestNumber) { |
---|
2468 | betterWay = -1; |
---|
2469 | } else { |
---|
2470 | if (changeDown[i]<bestCriterion) |
---|
2471 | betterWay=-1; |
---|
2472 | } |
---|
2473 | } else { |
---|
2474 | // up and down have same number |
---|
2475 | bool better=false; |
---|
2476 | if (numberInfeasibilitiesUp[i]<bestNumber) { |
---|
2477 | better=true; |
---|
2478 | } else if (numberInfeasibilitiesUp[i]==bestNumber) { |
---|
2479 | if (min(changeUp[i],changeDown[i])<bestCriterion) |
---|
2480 | better=true;; |
---|
2481 | } |
---|
2482 | if (better) { |
---|
2483 | // see which way |
---|
2484 | if (changeUp[i]<=changeDown[i]) |
---|
2485 | betterWay=1; |
---|
2486 | else |
---|
2487 | betterWay=-1; |
---|
2488 | } |
---|
2489 | } |
---|
2490 | if (betterWay) { |
---|
2491 | bestCriterion = min(changeUp[i],changeDown[i]); |
---|
2492 | bestNumber = thisNumber; |
---|
2493 | whichObject = i; |
---|
2494 | bestWay = betterWay; |
---|
2495 | } |
---|
2496 | } |
---|
2497 | } |
---|
2498 | bestCriterion=1.0e50; |
---|
2499 | for ( i = 0 ; i < numberObjects ; i++) { |
---|
2500 | int thisNumber = numberInfeasibilitiesUp[i]; |
---|
2501 | if (thisNumber==bestNumber&&changeUp) { |
---|
2502 | if (changeUp[i]<bestCriterion) { |
---|
2503 | bestCriterion = changeUp[i]; |
---|
2504 | whichObject = i; |
---|
2505 | bestWay = 1; |
---|
2506 | } |
---|
2507 | } |
---|
2508 | } |
---|
2509 | break; |
---|
2510 | } |
---|
2511 | // set way in best |
---|
2512 | if (whichObject>=0) { |
---|
2513 | CbcBranchingObject * bestObject = objects[whichObject]; |
---|
2514 | if (bestObject->object()&&bestObject->object()->preferredWay()) |
---|
2515 | bestWay = bestObject->object()->preferredWay(); |
---|
2516 | bestObject->way(bestWay); |
---|
2517 | } else { |
---|
2518 | printf("debug\n"); |
---|
2519 | } |
---|
2520 | } |
---|
2521 | return whichObject; |
---|
2522 | } |
---|
2523 | |
---|
2524 | // Default Constructor |
---|
2525 | CbcFollowOn::CbcFollowOn () |
---|
2526 | : CbcObject(), |
---|
2527 | rhs_(NULL) |
---|
2528 | { |
---|
2529 | } |
---|
2530 | |
---|
2531 | // Useful constructor |
---|
2532 | CbcFollowOn::CbcFollowOn (CbcModel * model) |
---|
2533 | : CbcObject(model) |
---|
2534 | { |
---|
2535 | assert (model); |
---|
2536 | OsiSolverInterface * solver = model_->solver(); |
---|
2537 | matrix_ = *solver->getMatrixByCol(); |
---|
2538 | matrix_.removeGaps(); |
---|
2539 | matrix_.setExtraGap(0.0); |
---|
2540 | matrixByRow_ = *solver->getMatrixByRow(); |
---|
2541 | int numberRows = matrix_.getNumRows(); |
---|
2542 | |
---|
2543 | rhs_ = new int[numberRows]; |
---|
2544 | int i; |
---|
2545 | const double * rowLower = solver->getRowLower(); |
---|
2546 | const double * rowUpper = solver->getRowUpper(); |
---|
2547 | // Row copy |
---|
2548 | const double * elementByRow = matrixByRow_.getElements(); |
---|
2549 | const int * column = matrixByRow_.getIndices(); |
---|
2550 | const CoinBigIndex * rowStart = matrixByRow_.getVectorStarts(); |
---|
2551 | const int * rowLength = matrixByRow_.getVectorLengths(); |
---|
2552 | for (i=0;i<numberRows;i++) { |
---|
2553 | rhs_[i]=0; |
---|
2554 | double value = rowLower[i]; |
---|
2555 | if (value==rowUpper[i]) { |
---|
2556 | if (floor(value)==value&&value>=1.0&&value<10.0) { |
---|
2557 | // check elements |
---|
2558 | bool good=true; |
---|
2559 | for (int j=rowStart[i];j<rowStart[i]+rowLength[i];j++) { |
---|
2560 | int iColumn = column[j]; |
---|
2561 | if (!solver->isBinary(iColumn)) |
---|
2562 | good=false; |
---|
2563 | double elValue = elementByRow[j]; |
---|
2564 | if (floor(elValue)!=elValue||value<1.0) |
---|
2565 | good=false; |
---|
2566 | } |
---|
2567 | if (good) |
---|
2568 | rhs_[i]=(int) value; |
---|
2569 | } |
---|
2570 | } |
---|
2571 | } |
---|
2572 | } |
---|
2573 | |
---|
2574 | // Copy constructor |
---|
2575 | CbcFollowOn::CbcFollowOn ( const CbcFollowOn & rhs) |
---|
2576 | :CbcObject(rhs), |
---|
2577 | matrix_(rhs.matrix_), |
---|
2578 | matrixByRow_(rhs.matrixByRow_) |
---|
2579 | { |
---|
2580 | int numberRows = matrix_.getNumRows(); |
---|
2581 | rhs_= CoinCopyOfArray(rhs.rhs_,numberRows); |
---|
2582 | } |
---|
2583 | |
---|
2584 | // Clone |
---|
2585 | CbcObject * |
---|
2586 | CbcFollowOn::clone() const |
---|
2587 | { |
---|
2588 | return new CbcFollowOn(*this); |
---|
2589 | } |
---|
2590 | |
---|
2591 | // Assignment operator |
---|
2592 | CbcFollowOn & |
---|
2593 | CbcFollowOn::operator=( const CbcFollowOn& rhs) |
---|
2594 | { |
---|
2595 | if (this!=&rhs) { |
---|
2596 | CbcObject::operator=(rhs); |
---|
2597 | delete [] rhs_; |
---|
2598 | matrix_ = rhs.matrix_; |
---|
2599 | matrixByRow_ = rhs.matrixByRow_; |
---|
2600 | int numberRows = matrix_.getNumRows(); |
---|
2601 | rhs_= CoinCopyOfArray(rhs.rhs_,numberRows); |
---|
2602 | } |
---|
2603 | return *this; |
---|
2604 | } |
---|
2605 | |
---|
2606 | // Destructor |
---|
2607 | CbcFollowOn::~CbcFollowOn () |
---|
2608 | { |
---|
2609 | delete [] rhs_; |
---|
2610 | } |
---|
2611 | // As some computation is needed in more than one place - returns row |
---|
2612 | int |
---|
2613 | CbcFollowOn::gutsOfFollowOn(int & otherRow, int & preferredWay) const |
---|
2614 | { |
---|
2615 | int whichRow=-1; |
---|
2616 | otherRow=-1; |
---|
2617 | int numberRows = matrix_.getNumRows(); |
---|
2618 | |
---|
2619 | int i; |
---|
2620 | // For sorting |
---|
2621 | int * sort = new int [numberRows]; |
---|
2622 | int * isort = new int [numberRows]; |
---|
2623 | // Column copy |
---|
2624 | //const double * element = matrix_.getElements(); |
---|
2625 | const int * row = matrix_.getIndices(); |
---|
2626 | const CoinBigIndex * columnStart = matrix_.getVectorStarts(); |
---|
2627 | const int * columnLength = matrix_.getVectorLengths(); |
---|
2628 | // Row copy |
---|
2629 | const double * elementByRow = matrixByRow_.getElements(); |
---|
2630 | const int * column = matrixByRow_.getIndices(); |
---|
2631 | const CoinBigIndex * rowStart = matrixByRow_.getVectorStarts(); |
---|
2632 | const int * rowLength = matrixByRow_.getVectorLengths(); |
---|
2633 | OsiSolverInterface * solver = model_->solver(); |
---|
2634 | const double * columnLower = solver->getColLower(); |
---|
2635 | const double * columnUpper = solver->getColUpper(); |
---|
2636 | const double * solution = solver->getColSolution(); |
---|
2637 | double integerTolerance = model_->getDblParam(CbcModel::CbcIntegerTolerance); |
---|
2638 | int nSort=0; |
---|
2639 | for (i=0;i<numberRows;i++) { |
---|
2640 | if (rhs_[i]) { |
---|
2641 | // check elements |
---|
2642 | double smallest=1.0e10; |
---|
2643 | double largest=0.0; |
---|
2644 | int rhsValue=rhs_[i]; |
---|
2645 | int number1=0; |
---|
2646 | int numberUnsatisfied=0; |
---|
2647 | for (int j=rowStart[i];j<rowStart[i]+rowLength[i];j++) { |
---|
2648 | int iColumn = column[j]; |
---|
2649 | double value = elementByRow[j]; |
---|
2650 | double solValue = solution[iColumn]; |
---|
2651 | if (columnLower[iColumn]!=columnUpper[iColumn]) { |
---|
2652 | smallest = CoinMin(smallest,value); |
---|
2653 | largest = CoinMax(largest,value); |
---|
2654 | if (value==1.0) |
---|
2655 | number1++; |
---|
2656 | if (solValue<1.0-integerTolerance&&solValue>integerTolerance) |
---|
2657 | numberUnsatisfied++; |
---|
2658 | } else { |
---|
2659 | rhsValue -= (int)(value*floor(solValue+0.5)); |
---|
2660 | } |
---|
2661 | } |
---|
2662 | if (numberUnsatisfied>1) { |
---|
2663 | if (smallest<largest) { |
---|
2664 | // probably no good but check a few things |
---|
2665 | assert (largest<=rhsValue); |
---|
2666 | if (number1==1&&largest==rhsValue) |
---|
2667 | printf("could fix\n"); |
---|
2668 | } else if (largest==rhsValue) { |
---|
2669 | sort[nSort]=i; |
---|
2670 | isort[nSort++]=-numberUnsatisfied; |
---|
2671 | } |
---|
2672 | } |
---|
2673 | } |
---|
2674 | } |
---|
2675 | if (nSort>1) { |
---|
2676 | CoinSort_2(isort,isort+nSort,sort); |
---|
2677 | CoinZeroN(isort,numberRows); |
---|
2678 | double * other = new double[numberRows]; |
---|
2679 | CoinZeroN(other,numberRows); |
---|
2680 | int * which = new int[numberRows]; |
---|
2681 | //#define COUNT |
---|
2682 | #ifndef COUNT |
---|
2683 | bool beforeSolution = model_->getSolutionCount()==0; |
---|
2684 | #endif |
---|
2685 | for (int k=0;k<nSort-1;k++) { |
---|
2686 | i=sort[k]; |
---|
2687 | int numberUnsatisfied = 0; |
---|
2688 | int n=0; |
---|
2689 | int j; |
---|
2690 | for (j=rowStart[i];j<rowStart[i]+rowLength[i];j++) { |
---|
2691 | int iColumn = column[j]; |
---|
2692 | if (columnLower[iColumn]!=columnUpper[iColumn]) { |
---|
2693 | double solValue = solution[iColumn]-columnLower[iColumn]; |
---|
2694 | if (solValue<1.0-integerTolerance&&solValue>integerTolerance) { |
---|
2695 | numberUnsatisfied++; |
---|
2696 | for (int jj=columnStart[iColumn];jj<columnStart[iColumn]+columnLength[iColumn];jj++) { |
---|
2697 | int iRow = row[jj]; |
---|
2698 | if (rhs_[iRow]) { |
---|
2699 | other[iRow]+=solValue; |
---|
2700 | if (isort[iRow]) { |
---|
2701 | isort[iRow]++; |
---|
2702 | } else { |
---|
2703 | isort[iRow]=1; |
---|
2704 | which[n++]=iRow; |
---|
2705 | } |
---|
2706 | } |
---|
2707 | } |
---|
2708 | } |
---|
2709 | } |
---|
2710 | } |
---|
2711 | double total=0.0; |
---|
2712 | // Take out row |
---|
2713 | double sumThis=other[i]; |
---|
2714 | other[i]=0.0; |
---|
2715 | assert (numberUnsatisfied==isort[i]); |
---|
2716 | // find one nearest half if solution, one if before solution |
---|
2717 | int iBest=-1; |
---|
2718 | double dtarget=0.5*total; |
---|
2719 | #ifdef COUNT |
---|
2720 | int target = (numberUnsatisfied+1)>>1; |
---|
2721 | int best=numberUnsatisfied; |
---|
2722 | #else |
---|
2723 | double best; |
---|
2724 | if (beforeSolution) |
---|
2725 | best=dtarget; |
---|
2726 | else |
---|
2727 | best=1.0e30; |
---|
2728 | #endif |
---|
2729 | for (j=0;j<n;j++) { |
---|
2730 | int iRow = which[j]; |
---|
2731 | double dvalue=other[iRow]; |
---|
2732 | other[iRow]=0.0; |
---|
2733 | #ifdef COUNT |
---|
2734 | int value = isort[iRow]; |
---|
2735 | #endif |
---|
2736 | isort[iRow]=0; |
---|
2737 | if (fabs(dvalue)<1.0e-8||fabs(sumThis-dvalue)<1.0e-8) |
---|
2738 | continue; |
---|
2739 | if (dvalue<integerTolerance||dvalue>1.0-integerTolerance) |
---|
2740 | continue; |
---|
2741 | #ifdef COUNT |
---|
2742 | if (abs(value-target)<best&&value!=numberUnsatisfied) { |
---|
2743 | best=abs(value-target); |
---|
2744 | iBest=iRow; |
---|
2745 | if (dvalue<dtarget) |
---|
2746 | preferredWay=1; |
---|
2747 | else |
---|
2748 | preferredWay=-1; |
---|
2749 | } |
---|
2750 | #else |
---|
2751 | if (beforeSolution) { |
---|
2752 | if (fabs(dvalue-dtarget)>best) { |
---|
2753 | best = fabs(dvalue-dtarget); |
---|
2754 | iBest=iRow; |
---|
2755 | if (dvalue<dtarget) |
---|
2756 | preferredWay=1; |
---|
2757 | else |
---|
2758 | preferredWay=-1; |
---|
2759 | } |
---|
2760 | } else { |
---|
2761 | if (fabs(dvalue-dtarget)<best) { |
---|
2762 | best = fabs(dvalue-dtarget); |
---|
2763 | iBest=iRow; |
---|
2764 | if (dvalue<dtarget) |
---|
2765 | preferredWay=1; |
---|
2766 | else |
---|
2767 | preferredWay=-1; |
---|
2768 | } |
---|
2769 | } |
---|
2770 | #endif |
---|
2771 | } |
---|
2772 | if (iBest>=0) { |
---|
2773 | whichRow=i; |
---|
2774 | otherRow=iBest; |
---|
2775 | break; |
---|
2776 | } |
---|
2777 | } |
---|
2778 | delete [] which; |
---|
2779 | delete [] other; |
---|
2780 | } |
---|
2781 | delete [] sort; |
---|
2782 | delete [] isort; |
---|
2783 | return whichRow; |
---|
2784 | } |
---|
2785 | |
---|
2786 | // Infeasibility - large is 0.5 |
---|
2787 | double |
---|
2788 | CbcFollowOn::infeasibility(int & preferredWay) const |
---|
2789 | { |
---|
2790 | int otherRow=0; |
---|
2791 | int whichRow = gutsOfFollowOn(otherRow,preferredWay); |
---|
2792 | if (whichRow<0) |
---|
2793 | return 0.0; |
---|
2794 | else |
---|
2795 | return 2.0* model_->getDblParam(CbcModel::CbcIntegerTolerance); |
---|
2796 | } |
---|
2797 | |
---|
2798 | // This looks at solution and sets bounds to contain solution |
---|
2799 | void |
---|
2800 | CbcFollowOn::feasibleRegion() |
---|
2801 | { |
---|
2802 | } |
---|
2803 | |
---|
2804 | |
---|
2805 | // Creates a branching object |
---|
2806 | CbcBranchingObject * |
---|
2807 | CbcFollowOn::createBranch(int way) |
---|
2808 | { |
---|
2809 | int otherRow=0; |
---|
2810 | int preferredWay; |
---|
2811 | int whichRow = gutsOfFollowOn(otherRow,preferredWay); |
---|
2812 | assert(way==preferredWay); |
---|
2813 | assert (whichRow>=0); |
---|
2814 | int numberColumns = matrix_.getNumCols(); |
---|
2815 | |
---|
2816 | // Column copy |
---|
2817 | //const double * element = matrix_.getElements(); |
---|
2818 | const int * row = matrix_.getIndices(); |
---|
2819 | const CoinBigIndex * columnStart = matrix_.getVectorStarts(); |
---|
2820 | const int * columnLength = matrix_.getVectorLengths(); |
---|
2821 | // Row copy |
---|
2822 | //const double * elementByRow = matrixByRow_.getElements(); |
---|
2823 | const int * column = matrixByRow_.getIndices(); |
---|
2824 | const CoinBigIndex * rowStart = matrixByRow_.getVectorStarts(); |
---|
2825 | const int * rowLength = matrixByRow_.getVectorLengths(); |
---|
2826 | OsiSolverInterface * solver = model_->solver(); |
---|
2827 | const double * columnLower = solver->getColLower(); |
---|
2828 | const double * columnUpper = solver->getColUpper(); |
---|
2829 | //const double * solution = solver->getColSolution(); |
---|
2830 | int nUp=0; |
---|
2831 | int nDown=0; |
---|
2832 | int * upList = new int[numberColumns]; |
---|
2833 | int * downList = new int[numberColumns]; |
---|
2834 | int j; |
---|
2835 | for (j=rowStart[whichRow];j<rowStart[whichRow]+rowLength[whichRow];j++) { |
---|
2836 | int iColumn = column[j]; |
---|
2837 | if (columnLower[iColumn]!=columnUpper[iColumn]) { |
---|
2838 | bool up=true; |
---|
2839 | for (int jj=columnStart[iColumn];jj<columnStart[iColumn]+columnLength[iColumn];jj++) { |
---|
2840 | int iRow = row[jj]; |
---|
2841 | if (iRow==otherRow) { |
---|
2842 | up=false; |
---|
2843 | break; |
---|
2844 | } |
---|
2845 | } |
---|
2846 | if (up) |
---|
2847 | upList[nUp++]=iColumn; |
---|
2848 | else |
---|
2849 | downList[nDown++]=iColumn; |
---|
2850 | } |
---|
2851 | } |
---|
2852 | //printf("way %d\n",way); |
---|
2853 | // create object |
---|
2854 | //printf("would fix %d down and %d up\n",nDown,nUp); |
---|
2855 | CbcBranchingObject * branch |
---|
2856 | = new CbcFixingBranchingObject(model_,way, |
---|
2857 | nDown,downList,nUp,upList); |
---|
2858 | delete [] upList; |
---|
2859 | delete [] downList; |
---|
2860 | return branch; |
---|
2861 | } |
---|
2862 | // Default Constructor |
---|
2863 | CbcFixingBranchingObject::CbcFixingBranchingObject() |
---|
2864 | :CbcBranchingObject() |
---|
2865 | { |
---|
2866 | numberDown_=0; |
---|
2867 | numberUp_=0; |
---|
2868 | downList_=NULL; |
---|
2869 | upList_=NULL; |
---|
2870 | } |
---|
2871 | |
---|
2872 | // Useful constructor |
---|
2873 | CbcFixingBranchingObject::CbcFixingBranchingObject (CbcModel * model, |
---|
2874 | int way , |
---|
2875 | int numberOnDownSide, const int * down, |
---|
2876 | int numberOnUpSide, const int * up) |
---|
2877 | :CbcBranchingObject(model,0,way,0.5) |
---|
2878 | { |
---|
2879 | numberDown_=numberOnDownSide; |
---|
2880 | numberUp_=numberOnUpSide; |
---|
2881 | downList_ = CoinCopyOfArray(down,numberDown_); |
---|
2882 | upList_ = CoinCopyOfArray(up,numberUp_); |
---|
2883 | } |
---|
2884 | |
---|
2885 | // Copy constructor |
---|
2886 | CbcFixingBranchingObject::CbcFixingBranchingObject ( const CbcFixingBranchingObject & rhs) :CbcBranchingObject(rhs) |
---|
2887 | { |
---|
2888 | numberDown_=rhs.numberDown_; |
---|
2889 | numberUp_=rhs.numberUp_; |
---|
2890 | downList_ = CoinCopyOfArray(rhs.downList_,numberDown_); |
---|
2891 | upList_ = CoinCopyOfArray(rhs.upList_,numberUp_); |
---|
2892 | } |
---|
2893 | |
---|
2894 | // Assignment operator |
---|
2895 | CbcFixingBranchingObject & |
---|
2896 | CbcFixingBranchingObject::operator=( const CbcFixingBranchingObject& rhs) |
---|
2897 | { |
---|
2898 | if (this != &rhs) { |
---|
2899 | CbcBranchingObject::operator=(rhs); |
---|
2900 | delete [] downList_; |
---|
2901 | delete [] upList_; |
---|
2902 | numberDown_=rhs.numberDown_; |
---|
2903 | numberUp_=rhs.numberUp_; |
---|
2904 | downList_ = CoinCopyOfArray(rhs.downList_,numberDown_); |
---|
2905 | upList_ = CoinCopyOfArray(rhs.upList_,numberUp_); |
---|
2906 | } |
---|
2907 | return *this; |
---|
2908 | } |
---|
2909 | CbcBranchingObject * |
---|
2910 | CbcFixingBranchingObject::clone() const |
---|
2911 | { |
---|
2912 | return (new CbcFixingBranchingObject(*this)); |
---|
2913 | } |
---|
2914 | |
---|
2915 | |
---|
2916 | // Destructor |
---|
2917 | CbcFixingBranchingObject::~CbcFixingBranchingObject () |
---|
2918 | { |
---|
2919 | delete [] downList_; |
---|
2920 | delete [] upList_; |
---|
2921 | } |
---|
2922 | double |
---|
2923 | CbcFixingBranchingObject::branch() |
---|
2924 | { |
---|
2925 | decrementNumberBranchesLeft(); |
---|
2926 | OsiSolverInterface * solver = model_->solver(); |
---|
2927 | const double * columnLower = solver->getColLower(); |
---|
2928 | int i; |
---|
2929 | // *** for way - up means fix all those in up section |
---|
2930 | if (way_<0) { |
---|
2931 | #ifdef FULL_PRINT |
---|
2932 | printf("Down Fix "); |
---|
2933 | #endif |
---|
2934 | //printf("Down Fix %d\n",numberDown_); |
---|
2935 | for (i=0;i<numberDown_;i++) { |
---|
2936 | int iColumn = downList_[i]; |
---|
2937 | model_->solver()->setColUpper(iColumn,columnLower[iColumn]); |
---|
2938 | #ifdef FULL_PRINT |
---|
2939 | printf("Setting bound on %d to lower bound\n",iColumn); |
---|
2940 | #endif |
---|
2941 | } |
---|
2942 | way_=1; // Swap direction |
---|
2943 | } else { |
---|
2944 | #ifdef FULL_PRINT |
---|
2945 | printf("Up Fix "); |
---|
2946 | #endif |
---|
2947 | //printf("Up Fix %d\n",numberUp_); |
---|
2948 | for (i=0;i<numberUp_;i++) { |
---|
2949 | int iColumn = upList_[i]; |
---|
2950 | model_->solver()->setColUpper(iColumn,columnLower[iColumn]); |
---|
2951 | #ifdef FULL_PRINT |
---|
2952 | printf("Setting bound on %d to lower bound\n",iColumn); |
---|
2953 | #endif |
---|
2954 | } |
---|
2955 | way_=-1; // Swap direction |
---|
2956 | } |
---|
2957 | #ifdef FULL_PRINT |
---|
2958 | printf("\n"); |
---|
2959 | #endif |
---|
2960 | return 0.0; |
---|
2961 | } |
---|
2962 | void |
---|
2963 | CbcFixingBranchingObject::print() |
---|
2964 | { |
---|
2965 | int i; |
---|
2966 | // *** for way - up means fix all those in up section |
---|
2967 | if (way_<0) { |
---|
2968 | printf("Down Fix "); |
---|
2969 | for (i=0;i<numberDown_;i++) { |
---|
2970 | int iColumn = downList_[i]; |
---|
2971 | printf("%d ",iColumn); |
---|
2972 | } |
---|
2973 | } else { |
---|
2974 | printf("Up Fix "); |
---|
2975 | for (i=0;i<numberUp_;i++) { |
---|
2976 | int iColumn = upList_[i]; |
---|
2977 | printf("%d ",iColumn); |
---|
2978 | } |
---|
2979 | } |
---|
2980 | printf("\n"); |
---|
2981 | } |
---|
2982 | // Default Constructor |
---|
2983 | CbcNWay::CbcNWay () |
---|
2984 | : CbcObject(), |
---|
2985 | numberMembers_(0), |
---|
2986 | members_(NULL), |
---|
2987 | consequence_(NULL) |
---|
2988 | { |
---|
2989 | } |
---|
2990 | |
---|
2991 | // Useful constructor (which are integer indices) |
---|
2992 | CbcNWay::CbcNWay (CbcModel * model, int numberMembers, |
---|
2993 | const int * which, int identifier) |
---|
2994 | : CbcObject(model) |
---|
2995 | { |
---|
2996 | id_=identifier; |
---|
2997 | numberMembers_=numberMembers; |
---|
2998 | if (numberMembers_) { |
---|
2999 | members_ = new int[numberMembers_]; |
---|
3000 | memcpy(members_,which,numberMembers_*sizeof(int)); |
---|
3001 | } else { |
---|
3002 | members_ = NULL; |
---|
3003 | } |
---|
3004 | consequence_ = NULL; |
---|
3005 | } |
---|
3006 | |
---|
3007 | // Copy constructor |
---|
3008 | CbcNWay::CbcNWay ( const CbcNWay & rhs) |
---|
3009 | :CbcObject(rhs) |
---|
3010 | { |
---|
3011 | numberMembers_ = rhs.numberMembers_; |
---|
3012 | consequence_ = NULL; |
---|
3013 | if (numberMembers_) { |
---|
3014 | members_ = new int[numberMembers_]; |
---|
3015 | memcpy(members_,rhs.members_,numberMembers_*sizeof(int)); |
---|
3016 | if (rhs.consequence_) { |
---|
3017 | consequence_ = new CbcConsequence * [numberMembers_]; |
---|
3018 | for (int i=0;i<numberMembers_;i++) { |
---|
3019 | if (rhs.consequence_[i]) |
---|
3020 | consequence_[i]= rhs.consequence_[i]->clone(); |
---|
3021 | else |
---|
3022 | consequence_[i]=NULL; |
---|
3023 | } |
---|
3024 | } |
---|
3025 | } else { |
---|
3026 | members_ = NULL; |
---|
3027 | } |
---|
3028 | } |
---|
3029 | |
---|
3030 | // Clone |
---|
3031 | CbcObject * |
---|
3032 | CbcNWay::clone() const |
---|
3033 | { |
---|
3034 | return new CbcNWay(*this); |
---|
3035 | } |
---|
3036 | |
---|
3037 | // Assignment operator |
---|
3038 | CbcNWay & |
---|
3039 | CbcNWay::operator=( const CbcNWay& rhs) |
---|
3040 | { |
---|
3041 | if (this!=&rhs) { |
---|
3042 | CbcObject::operator=(rhs); |
---|
3043 | delete [] members_; |
---|
3044 | numberMembers_ = rhs.numberMembers_; |
---|
3045 | if (consequence_) { |
---|
3046 | for (int i=0;i<numberMembers_;i++) |
---|
3047 | delete consequence_[i]; |
---|
3048 | delete [] consequence_; |
---|
3049 | consequence_=NULL; |
---|
3050 | } |
---|
3051 | if (numberMembers_) { |
---|
3052 | members_ = new int[numberMembers_]; |
---|
3053 | memcpy(members_,rhs.members_,numberMembers_*sizeof(int)); |
---|
3054 | } else { |
---|
3055 | members_ = NULL; |
---|
3056 | } |
---|
3057 | if (rhs.consequence_) { |
---|
3058 | consequence_ = new CbcConsequence * [numberMembers_]; |
---|
3059 | for (int i=0;i<numberMembers_;i++) { |
---|
3060 | if (rhs.consequence_[i]) |
---|
3061 | consequence_[i]= rhs.consequence_[i]->clone(); |
---|
3062 | else |
---|
3063 | consequence_[i]=NULL; |
---|
3064 | } |
---|
3065 | } |
---|
3066 | } |
---|
3067 | return *this; |
---|
3068 | } |
---|
3069 | |
---|
3070 | // Destructor |
---|
3071 | CbcNWay::~CbcNWay () |
---|
3072 | { |
---|
3073 | delete [] members_; |
---|
3074 | if (consequence_) { |
---|
3075 | for (int i=0;i<numberMembers_;i++) |
---|
3076 | delete consequence_[i]; |
---|
3077 | delete [] consequence_; |
---|
3078 | } |
---|
3079 | } |
---|
3080 | // Set up a consequence for a single member |
---|
3081 | void |
---|
3082 | CbcNWay::setConsequence(int iColumn, const CbcConsequence & consequence) |
---|
3083 | { |
---|
3084 | if (!consequence_) { |
---|
3085 | consequence_ = new CbcConsequence * [numberMembers_]; |
---|
3086 | for (int i=0;i<numberMembers_;i++) |
---|
3087 | consequence_[i]=NULL; |
---|
3088 | } |
---|
3089 | for (int i=0;i<numberMembers_;i++) { |
---|
3090 | if (members_[i]==iColumn) { |
---|
3091 | consequence_[i]=consequence.clone(); |
---|
3092 | break; |
---|
3093 | } |
---|
3094 | } |
---|
3095 | } |
---|
3096 | |
---|
3097 | // Applies a consequence for a single member |
---|
3098 | void |
---|
3099 | CbcNWay::applyConsequence(int iSequence, int state) const |
---|
3100 | { |
---|
3101 | assert (state==-9999||state==9999); |
---|
3102 | if (consequence_) { |
---|
3103 | CbcConsequence * consequence = consequence_[iSequence]; |
---|
3104 | if (consequence) |
---|
3105 | consequence->applyToSolver(model_->solver(),state); |
---|
3106 | } |
---|
3107 | } |
---|
3108 | |
---|
3109 | // Infeasibility - large is 0.5 |
---|
3110 | double |
---|
3111 | CbcNWay::infeasibility(int & preferredWay) const |
---|
3112 | { |
---|
3113 | int numberUnsatis=0; |
---|
3114 | int j; |
---|
3115 | OsiSolverInterface * solver = model_->solver(); |
---|
3116 | const double * solution = model_->testSolution(); |
---|
3117 | const double * lower = solver->getColLower(); |
---|
3118 | const double * upper = solver->getColUpper(); |
---|
3119 | double largestValue=0.0; |
---|
3120 | |
---|
3121 | double integerTolerance = |
---|
3122 | model_->getDblParam(CbcModel::CbcIntegerTolerance); |
---|
3123 | |
---|
3124 | for (j=0;j<numberMembers_;j++) { |
---|
3125 | int iColumn = members_[j]; |
---|
3126 | double value = solution[iColumn]; |
---|
3127 | value = CoinMax(value, lower[iColumn]); |
---|
3128 | value = CoinMin(value, upper[iColumn]); |
---|
3129 | double distance = CoinMin(value-lower[iColumn],upper[iColumn]-value); |
---|
3130 | if (distance>integerTolerance) { |
---|
3131 | numberUnsatis++; |
---|
3132 | largestValue = CoinMax(distance,largestValue); |
---|
3133 | } |
---|
3134 | } |
---|
3135 | preferredWay=1; |
---|
3136 | if (numberUnsatis) { |
---|
3137 | return largestValue; |
---|
3138 | } else { |
---|
3139 | return 0.0; // satisfied |
---|
3140 | } |
---|
3141 | } |
---|
3142 | |
---|
3143 | // This looks at solution and sets bounds to contain solution |
---|
3144 | void |
---|
3145 | CbcNWay::feasibleRegion() |
---|
3146 | { |
---|
3147 | int j; |
---|
3148 | OsiSolverInterface * solver = model_->solver(); |
---|
3149 | const double * solution = model_->testSolution(); |
---|
3150 | const double * lower = solver->getColLower(); |
---|
3151 | const double * upper = solver->getColUpper(); |
---|
3152 | double integerTolerance = |
---|
3153 | model_->getDblParam(CbcModel::CbcIntegerTolerance); |
---|
3154 | for (j=0;j<numberMembers_;j++) { |
---|
3155 | int iColumn = members_[j]; |
---|
3156 | double value = solution[iColumn]; |
---|
3157 | value = CoinMax(value, lower[iColumn]); |
---|
3158 | value = CoinMin(value, upper[iColumn]); |
---|
3159 | if (value>=upper[iColumn]-integerTolerance) { |
---|
3160 | solver->setColLower(iColumn,upper[iColumn]); |
---|
3161 | } else { |
---|
3162 | assert (value<=lower[iColumn]+integerTolerance); |
---|
3163 | solver->setColUpper(iColumn,lower[iColumn]); |
---|
3164 | } |
---|
3165 | } |
---|
3166 | } |
---|
3167 | // Redoes data when sequence numbers change |
---|
3168 | void |
---|
3169 | CbcNWay::redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns) |
---|
3170 | { |
---|
3171 | model_=model; |
---|
3172 | int n2=0; |
---|
3173 | for (int j=0;j<numberMembers_;j++) { |
---|
3174 | int iColumn = members_[j]; |
---|
3175 | int i; |
---|
3176 | for (i=0;i<numberColumns;i++) { |
---|
3177 | if (originalColumns[i]==iColumn) |
---|
3178 | break; |
---|
3179 | } |
---|
3180 | if (i<numberColumns) { |
---|
3181 | members_[n2]=i; |
---|
3182 | consequence_[n2++]=consequence_[j]; |
---|
3183 | } else { |
---|
3184 | delete consequence_[j]; |
---|
3185 | } |
---|
3186 | } |
---|
3187 | if (n2<numberMembers_) { |
---|
3188 | printf("** NWay number of members reduced from %d to %d!\n",numberMembers_,n2); |
---|
3189 | numberMembers_=n2; |
---|
3190 | } |
---|
3191 | } |
---|
3192 | |
---|
3193 | |
---|
3194 | // Creates a branching object |
---|
3195 | CbcBranchingObject * |
---|
3196 | CbcNWay::createBranch(int way) |
---|
3197 | { |
---|
3198 | int numberFree=0; |
---|
3199 | int j; |
---|
3200 | |
---|
3201 | OsiSolverInterface * solver = model_->solver(); |
---|
3202 | const double * solution = model_->testSolution(); |
---|
3203 | const double * lower = solver->getColLower(); |
---|
3204 | const double * upper = solver->getColUpper(); |
---|
3205 | int * list = new int[numberMembers_]; |
---|
3206 | double * sort = new double[numberMembers_]; |
---|
3207 | |
---|
3208 | for (j=0;j<numberMembers_;j++) { |
---|
3209 | int iColumn = members_[j]; |
---|
3210 | double value = solution[iColumn]; |
---|
3211 | value = CoinMax(value, lower[iColumn]); |
---|
3212 | value = CoinMin(value, upper[iColumn]); |
---|
3213 | if (upper[iColumn]>lower[iColumn]) { |
---|
3214 | double distance = upper[iColumn]-value; |
---|
3215 | list[numberFree]=j; |
---|
3216 | sort[numberFree++]=distance; |
---|
3217 | } |
---|
3218 | } |
---|
3219 | assert (numberFree); |
---|
3220 | // sort |
---|
3221 | CoinSort_2(sort,sort+numberFree,list); |
---|
3222 | // create object |
---|
3223 | CbcBranchingObject * branch; |
---|
3224 | branch = new CbcNWayBranchingObject(model_,this,numberFree,list); |
---|
3225 | branch->setOriginalObject(this); |
---|
3226 | delete [] list; |
---|
3227 | delete [] sort; |
---|
3228 | return branch; |
---|
3229 | } |
---|
3230 | |
---|
3231 | // Default Constructor |
---|
3232 | CbcNWayBranchingObject::CbcNWayBranchingObject() |
---|
3233 | :CbcBranchingObject() |
---|
3234 | { |
---|
3235 | order_=NULL; |
---|
3236 | object_=NULL; |
---|
3237 | numberInSet_=0; |
---|
3238 | way_=0; |
---|
3239 | } |
---|
3240 | |
---|
3241 | // Useful constructor |
---|
3242 | CbcNWayBranchingObject::CbcNWayBranchingObject (CbcModel * model, |
---|
3243 | const CbcNWay * nway, |
---|
3244 | int number, const int * order) |
---|
3245 | :CbcBranchingObject(model,nway->id(),-1,0.5) |
---|
3246 | { |
---|
3247 | numberBranches_ = number; |
---|
3248 | order_ = new int [number]; |
---|
3249 | object_=nway; |
---|
3250 | numberInSet_=number; |
---|
3251 | memcpy(order_,order,number*sizeof(int)); |
---|
3252 | } |
---|
3253 | |
---|
3254 | // Copy constructor |
---|
3255 | CbcNWayBranchingObject::CbcNWayBranchingObject ( const CbcNWayBranchingObject & rhs) :CbcBranchingObject(rhs) |
---|
3256 | { |
---|
3257 | numberInSet_=rhs.numberInSet_; |
---|
3258 | object_=rhs.object_; |
---|
3259 | if (numberInSet_) { |
---|
3260 | order_ = new int [numberInSet_]; |
---|
3261 | memcpy(order_,rhs.order_,numberInSet_*sizeof(int)); |
---|
3262 | } else { |
---|
3263 | order_=NULL; |
---|
3264 | } |
---|
3265 | } |
---|
3266 | |
---|
3267 | // Assignment operator |
---|
3268 | CbcNWayBranchingObject & |
---|
3269 | CbcNWayBranchingObject::operator=( const CbcNWayBranchingObject& rhs) |
---|
3270 | { |
---|
3271 | if (this != &rhs) { |
---|
3272 | CbcBranchingObject::operator=(rhs); |
---|
3273 | object_=rhs.object_; |
---|
3274 | delete [] order_; |
---|
3275 | numberInSet_=rhs.numberInSet_; |
---|
3276 | if (numberInSet_) { |
---|
3277 | order_ = new int [numberInSet_]; |
---|
3278 | memcpy(order_,rhs.order_,numberInSet_*sizeof(int)); |
---|
3279 | } else { |
---|
3280 | order_=NULL; |
---|
3281 | } |
---|
3282 | } |
---|
3283 | return *this; |
---|
3284 | } |
---|
3285 | CbcBranchingObject * |
---|
3286 | CbcNWayBranchingObject::clone() const |
---|
3287 | { |
---|
3288 | return (new CbcNWayBranchingObject(*this)); |
---|
3289 | } |
---|
3290 | |
---|
3291 | |
---|
3292 | // Destructor |
---|
3293 | CbcNWayBranchingObject::~CbcNWayBranchingObject () |
---|
3294 | { |
---|
3295 | delete [] order_; |
---|
3296 | } |
---|
3297 | double |
---|
3298 | CbcNWayBranchingObject::branch() |
---|
3299 | { |
---|
3300 | int which = branchIndex_; |
---|
3301 | branchIndex_++; |
---|
3302 | assert (numberBranchesLeft()>=0); |
---|
3303 | if (which==0) { |
---|
3304 | // first branch so way_ may mean something |
---|
3305 | assert (way_==-1||way_==1); |
---|
3306 | if (way_==-1) |
---|
3307 | which++; |
---|
3308 | } else if (which==1) { |
---|
3309 | // second branch so way_ may mean something |
---|
3310 | assert (way_==-1||way_==1); |
---|
3311 | if (way_==-1) |
---|
3312 | which--; |
---|
3313 | // switch way off |
---|
3314 | way_=0; |
---|
3315 | } |
---|
3316 | const double * lower = model_->solver()->getColLower(); |
---|
3317 | const double * upper = model_->solver()->getColUpper(); |
---|
3318 | const int * members = object_->members(); |
---|
3319 | for (int j=0;j<numberInSet_;j++) { |
---|
3320 | int iSequence = order_[j]; |
---|
3321 | int iColumn = members[iSequence]; |
---|
3322 | if (j!=which) { |
---|
3323 | model_->solver()->setColUpper(iColumn,lower[iColumn]); |
---|
3324 | //model_->solver()->setColLower(iColumn,lower[iColumn]); |
---|
3325 | assert (lower[iColumn]>-1.0e20); |
---|
3326 | // apply any consequences |
---|
3327 | object_->applyConsequence(iSequence,-9999); |
---|
3328 | } else { |
---|
3329 | model_->solver()->setColLower(iColumn,upper[iColumn]); |
---|
3330 | //model_->solver()->setColUpper(iColumn,upper[iColumn]); |
---|
3331 | #ifdef FULL_PRINT |
---|
3332 | printf("Up Fix %d to %g\n",iColumn,upper[iColumn]); |
---|
3333 | #endif |
---|
3334 | assert (upper[iColumn]<1.0e20); |
---|
3335 | // apply any consequences |
---|
3336 | object_->applyConsequence(iSequence,9999); |
---|
3337 | } |
---|
3338 | } |
---|
3339 | return 0.0; |
---|
3340 | } |
---|
3341 | void |
---|
3342 | CbcNWayBranchingObject::print() |
---|
3343 | { |
---|
3344 | printf("NWay - Up Fix "); |
---|
3345 | const int * members = object_->members(); |
---|
3346 | for (int j=0;j<way_;j++) { |
---|
3347 | int iColumn = members[order_[j]]; |
---|
3348 | printf("%d ",iColumn); |
---|
3349 | } |
---|
3350 | printf("\n"); |
---|
3351 | } |
---|
3352 | |
---|
3353 | // Default Constructor |
---|
3354 | CbcFixVariable::CbcFixVariable () |
---|
3355 | : CbcConsequence(), |
---|
3356 | numberStates_(0), |
---|
3357 | states_(NULL), |
---|
3358 | startLower_(NULL), |
---|
3359 | startUpper_(NULL), |
---|
3360 | newBound_(NULL), |
---|
3361 | variable_(NULL) |
---|
3362 | { |
---|
3363 | } |
---|
3364 | |
---|
3365 | // One useful Constructor |
---|
3366 | CbcFixVariable::CbcFixVariable (int numberStates,const int * states, const int * numberNewLower, |
---|
3367 | const int ** newLowerValue, |
---|
3368 | const int ** lowerColumn, |
---|
3369 | const int * numberNewUpper, const int ** newUpperValue, |
---|
3370 | const int ** upperColumn) |
---|
3371 | : CbcConsequence(), |
---|
3372 | states_(NULL), |
---|
3373 | startLower_(NULL), |
---|
3374 | startUpper_(NULL), |
---|
3375 | newBound_(NULL), |
---|
3376 | variable_(NULL) |
---|
3377 | { |
---|
3378 | // How much space |
---|
3379 | numberStates_ = numberStates; |
---|
3380 | if (numberStates_) { |
---|
3381 | states_ = new int[numberStates_]; |
---|
3382 | memcpy(states_,states,numberStates_*sizeof(int)); |
---|
3383 | int i; |
---|
3384 | int n=0; |
---|
3385 | startLower_ = new int[numberStates_+1]; |
---|
3386 | startUpper_ = new int[numberStates_+1]; |
---|
3387 | startLower_[0]=0; |
---|
3388 | //count |
---|
3389 | for (i=0;i<numberStates_;i++) { |
---|
3390 | n += numberNewLower[i]; |
---|
3391 | startUpper_[i]=n; |
---|
3392 | n += numberNewUpper[i]; |
---|
3393 | startLower_[i+1]=n; |
---|
3394 | } |
---|
3395 | newBound_ = new double [n]; |
---|
3396 | variable_ = new int [n]; |
---|
3397 | n=0; |
---|
3398 | for (i=0;i<numberStates_;i++) { |
---|
3399 | int j; |
---|
3400 | int k; |
---|
3401 | const int * bound; |
---|
3402 | const int * variable; |
---|
3403 | k=numberNewLower[i]; |
---|
3404 | bound = newLowerValue[i]; |
---|
3405 | variable = lowerColumn[i]; |
---|
3406 | for (j=0;j<k;j++) { |
---|
3407 | newBound_[n]=bound[j]; |
---|
3408 | variable_[n++]=variable[j]; |
---|
3409 | } |
---|
3410 | k=numberNewUpper[i]; |
---|
3411 | bound = newUpperValue[i]; |
---|
3412 | variable = upperColumn[i]; |
---|
3413 | for (j=0;j<k;j++) { |
---|
3414 | newBound_[n]=bound[j]; |
---|
3415 | variable_[n++]=variable[j]; |
---|
3416 | } |
---|
3417 | } |
---|
3418 | } |
---|
3419 | } |
---|
3420 | |
---|
3421 | // Copy constructor |
---|
3422 | CbcFixVariable::CbcFixVariable ( const CbcFixVariable & rhs) |
---|
3423 | :CbcConsequence(rhs) |
---|
3424 | { |
---|
3425 | numberStates_ = rhs.numberStates_; |
---|
3426 | states_ = NULL; |
---|
3427 | startLower_ = NULL; |
---|
3428 | startUpper_ = NULL; |
---|
3429 | newBound_ = NULL; |
---|
3430 | variable_ = NULL; |
---|
3431 | if (numberStates_) { |
---|
3432 | states_ = CoinCopyOfArray(rhs.states_,numberStates_); |
---|
3433 | startLower_ = CoinCopyOfArray(rhs.startLower_,numberStates_+1); |
---|
3434 | startUpper_ = CoinCopyOfArray(rhs.startUpper_,numberStates_+1); |
---|
3435 | int n=startLower_[numberStates_]; |
---|
3436 | newBound_ = CoinCopyOfArray(rhs.newBound_,n); |
---|
3437 | variable_ = CoinCopyOfArray(rhs.variable_,n); |
---|
3438 | } |
---|
3439 | } |
---|
3440 | |
---|
3441 | // Clone |
---|
3442 | CbcConsequence * |
---|
3443 | CbcFixVariable::clone() const |
---|
3444 | { |
---|
3445 | return new CbcFixVariable(*this); |
---|
3446 | } |
---|
3447 | |
---|
3448 | // Assignment operator |
---|
3449 | CbcFixVariable & |
---|
3450 | CbcFixVariable::operator=( const CbcFixVariable& rhs) |
---|
3451 | { |
---|
3452 | if (this!=&rhs) { |
---|
3453 | CbcConsequence::operator=(rhs); |
---|
3454 | delete [] states_; |
---|
3455 | delete [] startLower_; |
---|
3456 | delete [] startUpper_; |
---|
3457 | delete [] newBound_; |
---|
3458 | delete [] variable_; |
---|
3459 | states_ = NULL; |
---|
3460 | startLower_ = NULL; |
---|
3461 | startUpper_ = NULL; |
---|
3462 | newBound_ = NULL; |
---|
3463 | variable_ = NULL; |
---|
3464 | numberStates_ = rhs.numberStates_; |
---|
3465 | if (numberStates_) { |
---|
3466 | states_ = CoinCopyOfArray(rhs.states_,numberStates_); |
---|
3467 | startLower_ = CoinCopyOfArray(rhs.startLower_,numberStates_+1); |
---|
3468 | startUpper_ = CoinCopyOfArray(rhs.startUpper_,numberStates_+1); |
---|
3469 | int n=startLower_[numberStates_]; |
---|
3470 | newBound_ = CoinCopyOfArray(rhs.newBound_,n); |
---|
3471 | variable_ = CoinCopyOfArray(rhs.variable_,n); |
---|
3472 | } |
---|
3473 | } |
---|
3474 | return *this; |
---|
3475 | } |
---|
3476 | |
---|
3477 | // Destructor |
---|
3478 | CbcFixVariable::~CbcFixVariable () |
---|
3479 | { |
---|
3480 | delete [] states_; |
---|
3481 | delete [] startLower_; |
---|
3482 | delete [] startUpper_; |
---|
3483 | delete [] newBound_; |
---|
3484 | delete [] variable_; |
---|
3485 | } |
---|
3486 | // Set up a startLower for a single member |
---|
3487 | void |
---|
3488 | CbcFixVariable::applyToSolver(OsiSolverInterface * solver, int state) const |
---|
3489 | { |
---|
3490 | assert (state==-9999||state==9999); |
---|
3491 | // Find state |
---|
3492 | int find; |
---|
3493 | for (find=0;find<numberStates_;find++) |
---|
3494 | if (states_[find]==state) |
---|
3495 | break; |
---|
3496 | if (find==numberStates_) |
---|
3497 | return; |
---|
3498 | int i; |
---|
3499 | // Set new lower bounds |
---|
3500 | for (i=startLower_[find];i<startUpper_[find];i++) { |
---|
3501 | int iColumn = variable_[i]; |
---|
3502 | double value = newBound_[i]; |
---|
3503 | double oldValue = solver->getColLower()[iColumn]; |
---|
3504 | //printf("for %d old lower bound %g, new %g",iColumn,oldValue,value); |
---|
3505 | solver->setColLower(iColumn,CoinMax(value,oldValue)); |
---|
3506 | //printf(" => %g\n",solver->getColLower()[iColumn]); |
---|
3507 | } |
---|
3508 | // Set new upper bounds |
---|
3509 | for (i=startUpper_[find];i<startLower_[find+1];i++) { |
---|
3510 | int iColumn = variable_[i]; |
---|
3511 | double value = newBound_[i]; |
---|
3512 | double oldValue = solver->getColUpper()[iColumn]; |
---|
3513 | //printf("for %d old upper bound %g, new %g",iColumn,oldValue,value); |
---|
3514 | solver->setColUpper(iColumn,CoinMin(value,oldValue)); |
---|
3515 | //printf(" => %g\n",solver->getColUpper()[iColumn]); |
---|
3516 | } |
---|
3517 | } |
---|
3518 | |
---|
3519 | // Default Constructor |
---|
3520 | CbcDummyBranchingObject::CbcDummyBranchingObject(CbcModel * model) |
---|
3521 | :CbcBranchingObject(model,0,0,0.5) |
---|
3522 | { |
---|
3523 | setNumberBranchesLeft(1); |
---|
3524 | } |
---|
3525 | |
---|
3526 | |
---|
3527 | // Copy constructor |
---|
3528 | CbcDummyBranchingObject::CbcDummyBranchingObject ( const CbcDummyBranchingObject & rhs) :CbcBranchingObject(rhs) |
---|
3529 | { |
---|
3530 | } |
---|
3531 | |
---|
3532 | // Assignment operator |
---|
3533 | CbcDummyBranchingObject & |
---|
3534 | CbcDummyBranchingObject::operator=( const CbcDummyBranchingObject& rhs) |
---|
3535 | { |
---|
3536 | if (this != &rhs) { |
---|
3537 | CbcBranchingObject::operator=(rhs); |
---|
3538 | } |
---|
3539 | return *this; |
---|
3540 | } |
---|
3541 | CbcBranchingObject * |
---|
3542 | CbcDummyBranchingObject::clone() const |
---|
3543 | { |
---|
3544 | return (new CbcDummyBranchingObject(*this)); |
---|
3545 | } |
---|
3546 | |
---|
3547 | |
---|
3548 | // Destructor |
---|
3549 | CbcDummyBranchingObject::~CbcDummyBranchingObject () |
---|
3550 | { |
---|
3551 | } |
---|
3552 | |
---|
3553 | /* |
---|
3554 | Perform a dummy branch |
---|
3555 | */ |
---|
3556 | double |
---|
3557 | CbcDummyBranchingObject::branch() |
---|
3558 | { |
---|
3559 | decrementNumberBranchesLeft(); |
---|
3560 | return 0.0; |
---|
3561 | } |
---|
3562 | // Print what would happen |
---|
3563 | void |
---|
3564 | CbcDummyBranchingObject::print() |
---|
3565 | { |
---|
3566 | printf("Dummy branch\n"); |
---|
3567 | } |
---|