1 /* $Id$
2 *
3 * Name: StrongBranchingSetupList.cpp
4 * Authors: Andreas Waechter
5 * Pietro Belotti
6 * Francois Margot, Carnegie Mellon University
7 * Purpose: Guts of setup list (including orbital branching)
8 *
9 * This file is licensed under the Eclipse Public License (EPL)
10 */
11
12 #include "CouenneObject.hpp"
13 #include "BonChooseVariable.hpp"
14 #include "CouenneChooseStrong.hpp"
15 #include "CouenneProblem.hpp"
16
17 // The recommended ones:
18 #define FM_SORT_STRONG
19 #define FM_SEC_SORT_USEFUL
20 #define USE_NOT_TRUSTED
21
22 //#define TRACE_STRONG
23 //#define TRACE_STRONG2
24 //#define FM_ALWAYS_SORT
25 //#define USE_SMALL_GAP
26 //#define OLD_STYLE
27
28 using namespace Ipopt;
29 using namespace Couenne;
30
31 const CouNumber estProdEps = 1e-6;
32
33 #ifdef COIN_HAS_NTY
34 #include "Nauty.h"
35 #endif
36
37 // service types for orbital branching
38
39 struct objStrongPri {
40
41 int objIndex_;
42
43 int priority_;
44 double value_;
45 };
46
compStrongPri(struct objStrongPri * one,struct objStrongPri * two)47 inline bool compStrongPri (struct objStrongPri *one, struct objStrongPri *two) {
48
49 return (one -> priority_ < two -> priority_ ||
50 ((one -> priority_ == two -> priority_) &&
51 (one -> value_ > two -> value_)));
52 }
53
54 /****************************************************************************/
55 // Copied from BonChooseVariable.cpp and modified slightly
56 //
57 // If FM_SORT_STRONG is used:
58 // Select unsatisfied objects first on priority, then usefulness.
59 //
60 // If USE_NOT_TRUSTED is also defined, modify usefulness of a fraction
61 // of unsatisfied objects with minimum priority (most fractional first)
62 // to make them more attractive. Number of such objects is
63 // number_not_trusted_ on return.
64
65 // Additional options working with FM_SORT_STRONG (at most one of the two):
66 // if FM_ALWAYS_SORT is also defined exact sorting is done. Otherwise,
67 // on return all objects in list[0..numberOnList_] have either smaller
68 // priority or equal priority and usefulness not worse than other
69 // unsatisfied objects.
70 //
71 // if FM_SEC_SORT_USEFUL is defined, objects are selected by priority
72 // then usefulness and the final list is sorted according to usefulness.
73 //
74 //
75 // If FM_SORT_STRONG is not used:
76 // Select unsatisfied objects first on priority, then usefulness
77 // but in a weird way: Only guarantee is that objects with minimum
78 // priority will be first in the list, objects with higher priority
79 // appearing after them in no predictable order. Then
80 // objects (with priority matching the smallest priority value among
81 // unsatisfied objects, most fractional first) have their usefulness
82 // modified to make them more attractive. Number of such objects is
83 // number_not_trusted_ on return. List is then sorted according to usefulness.
84 //
85 // Recommended settings: one of
86 // i) define FM_SORT_STRONG USE_NOT_TRUSTED FM_SEC_SORT_USEFUL
87 // ii) no flags defined (default)
88
gutsOfSetupList(OsiBranchingInformation * info,bool initialize)89 int CouenneChooseStrong::gutsOfSetupList(OsiBranchingInformation *info,
90 bool initialize)
91 {
92 if (numberBeforeTrustedList_ < 0) {
93 number_not_trusted_ = 1;
94 printf("CouenneChooseStrong::gutsOfSetupList(): Did not think we were using this; Please double check ...\n");
95 exit(1);
96 return OsiChooseVariable::setupList(info, initialize);
97 }
98 if (initialize) {
99 status_=-2;
100 delete [] goodSolution_;
101 bestObjectIndex_=-1;
102 numberStrongDone_=0;
103 numberStrongIterations_ = 0;
104 numberStrongFixed_ = 0;
105 goodSolution_ = NULL;
106 goodObjectiveValue_ = COIN_DBL_MAX;
107 number_not_trusted_=0;
108 }
109 else {
110 throw CoinError(CNAME,"setupList","Should not be called with initialize==false");
111 }
112 numberOnList_=0;
113 numberUnsatisfied_=0;
114 int numberObjects = solver_->numberObjects(); // FIXME: why not info -> solver_ ?
115 assert (numberObjects);
116 if (numberObjects>pseudoCosts_.numberObjects()) {
117 //std::cout<<"Number objects "<<numberObjects<<std::endl;
118 //AW : How could that ever happen?
119 //PB : It happens for instance when SOS constraints are added. They are added after the creation of this.
120 // assert(false && "Right now, all old content is deleted!");
121 // redo useful arrays
122 int saveNumberBeforeTrusted = pseudoCosts_.numberBeforeTrusted();
123 pseudoCosts_.initialize(numberObjects);
124 pseudoCosts_.setNumberBeforeTrusted(saveNumberBeforeTrusted);
125 }
126
127 int bestPriority = COIN_INT_MAX;
128 //int i;
129
130 #ifdef FM_SORT_STRONG
131 int numStr = numberStrong_;
132 if(isRootNode(info)) {
133 numStr = numberStrongRoot_;
134 }
135 int maximumStrong = CoinMin(numStr, numberObjects) ;
136 int lastPrio = problem_->getLastPrioSort();
137 int card_vPriority = 0;
138 int posEnd_vPriority = numberObjects;
139 double *vPriority = new double [numberObjects];
140 double *infeasVal = new double [numberObjects];
141 int max_most_fra = setup_pseudo_frac_ > 0. ? (int)floor(setup_pseudo_frac_*(double)maximumStrong): 0;
142 if (setup_pseudo_frac_ > 0.) {
143 max_most_fra = CoinMax(1, max_most_fra);
144 }
145 #else /* not FM_SORT_STRONG */
146
147 int putOther = numberObjects;
148 double check = -COIN_DBL_MAX;
149 int checkIndex = 0;
150 int maximumStrong = CoinMin(CoinMax(numberStrong_,numberStrongRoot_),
151 numberObjects) ;
152 for (int i=0;i<numberObjects;i++) {
153 list_[i]=-1;
154 useful_[i]=0.0;
155 }
156 // We make a second list for most fractional variables
157 int* list2 = NULL;
158 double* useful2 = NULL;
159 double check2 = -COIN_DBL_MAX;
160 int checkIndex2=0;
161 int max_most_fra = setup_pseudo_frac_ > 0. ? (int)floor(setup_pseudo_frac_*(double)maximumStrong): 0;
162 if (setup_pseudo_frac_ > 0.) {
163 max_most_fra = CoinMax(1, max_most_fra);
164 }
165 if (max_most_fra) {
166 list2 = new int[max_most_fra];
167 useful2 = new double[max_most_fra];
168 for (int i=0;i<max_most_fra;i++) {
169 list2[i]=-1;
170 useful2[i]=0.0;
171 }
172 }
173 #endif /* not FM_SORT_STRONG */
174
175 #ifdef FM_CHECK
176 const double* upTotalChange = pseudoCosts_.upTotalChange();
177 const double* downTotalChange = pseudoCosts_.downTotalChange();
178 int pseudoNum = pseudoCosts_.numberObjects();
179 for(int i=0; i<pseudoNum; i++) {
180 if(isnan(upTotalChange[i]) || isinf(upTotalChange[i])) {
181 printf("CouenneChooseStrong::gutsOfSetupList(): upTotalChange[%d]: not a number or infinite\n", i);
182 exit(1);
183 }
184 if(isnan(downTotalChange[i]) || isinf(downTotalChange[i])) {
185 printf("CouenneChooseStrong::gutsOfSetupList(): downTotalChange[%d]: not a number or infinite\n", i);
186 exit(1);
187 }
188 }
189 #endif
190
191 double upMultiplier, downMultiplier;
192 computeMultipliers (upMultiplier, downMultiplier);
193
194 // Say feasible
195 bool feasible = true;
196 const double MAXMIN_CRITERION = maxminCrit(info);
197
198 OsiObject **objectOrig = info -> solver_ -> objects ();
199
200 std::vector <int> objectInd;
201
202 numberObjects = info -> solver_ -> numberObjects ();
203
204 //
205 // Strong Orbital branching
206 //
207
208 ///////////////////////////////////////////////////////////////////
209 //
210 // Possibly reduce the set of objects to take into account orbital
211 // branching.
212 //
213 // * Identify objects related to a variable instead of e.g. SOS
214 // * Identify orbits
215 // * For each orbit:
216 // Keep only one object referring to that orbit
217 //
218 // No more objects than #orbits should be included in order to
219 // save SB time. Solving strong branching LPs for two variables in
220 // the same orbit is a waste of time given that, in theory, the
221 // branching rules on these two variables are equivalent.
222
223 #ifdef COIN_HAS_NTY
224
225 bool useOrbitalBranching = problem_ -> orbitalBranching ();
226
227 if (useOrbitalBranching) {
228
229 int n = problem_ -> nVars ();
230
231 // problem_ -> ChangeBounds (info -> lower_, info -> upper_, n);
232 // problem_ -> Compute_Symmetry ();
233
234 //problem_ -> Print_Orbits ();
235
236 std::vector<std::vector<int> > *orbits = problem_ -> getNtyInfo () -> getOrbits ();
237
238 // bail out if there are only trivial (size 1) orbits
239
240 bool nonTrivialOrbits = false;
241
242 for (std::vector <std::vector<int> >::iterator i = orbits -> begin ();
243 i != orbits -> end (); ++i)
244
245 if (i -> size () >= 2) {
246 nonTrivialOrbits = true;
247 break;
248 }
249
250 //
251 // Only do this if there is at least one nontrivial orbit
252 //
253
254 if (nonTrivialOrbits) {
255
256 //printf ("-----------------------------------------------------\n");
257
258 // build map variable -> object (i.e. the inverse of object
259 // [i] -> columnNumber ())
260
261 int *varObj = new int [n];
262
263 CoinFillN (varObj, n, -1);
264
265 for (unsigned int i = 0; i < numberObjects; i++) {
266
267 int indVar = objectOrig [i] -> columnNumber ();
268
269 if ((indVar >= 0) &&
270 (indVar < n))
271 varObj [indVar] = i;
272
273 //if ((indVar >= 0) && (indVar < n)) printf ("varObj [%d] = %d\n", indVar, i);
274 }
275
276 // Objects in orbits aren't just variables, but also
277 // constants. Variable indices are therefore mixed with
278 // others, we need to consider only variables.
279
280 for (std::vector <std::vector<int> >::iterator i = orbits -> begin ();
281 i != orbits -> end (); ++i) {
282
283 int orbSize = i -> size ();
284
285 if (orbSize <= 0)
286 continue;
287
288 if (orbSize == 1) {
289
290 int orbVar = (*i) [0];
291
292 if ((orbVar < n) &&
293 (orbVar >= 0)) { // single-variable orbit, not much to do
294
295 if ((varObj [orbVar] >= 0) &&
296 (objectOrig [varObj [orbVar]] -> checkInfeasibility (info) > COUENNE_EPS))
297 objectInd.push_back (varObj [orbVar]); // variable associated with object
298
299 //if ((varObj [orbVar] >= 0) && (objectOrig [varObj [orbVar]] -> checkInfeasibility (info) > COUENNE_EPS))
300 //printf ("added trivial orbit object %d [x%d]\n", varObj [orbVar], orbVar);
301
302 continue;
303 }
304 }
305
306 // Orbit is nontrivial. Sort its variables' objects
307 // according to (non-decreasing) priority.
308
309 std::vector <struct objStrongPri *> orbitObj; // pre-size vector
310
311 int
312 minPri = COIN_INT_MAX,
313 maxPri = -COIN_INT_MAX;
314
315 double
316 minValue = COIN_DBL_MAX,
317 maxValue = -COIN_DBL_MAX;
318
319 for (std::vector<int>::iterator j = i -> begin ();
320 j != i -> end (); ++j)
321
322 if ((*j < n) && (*j >= 0)) {
323
324 int objInd = varObj [*j];
325
326 if (objInd < 0)
327 continue;
328
329 int pri = objectOrig [objInd] -> priority ();
330
331 if (pri < minPri) minPri = pri;
332 if (pri > maxPri) maxPri = pri;
333
334 double
335 newValue,
336 infeas = objectOrig [objInd] -> checkInfeasibility (info),
337 //infeas = objectOrig [(*j) -> objIndex_] -> infeasibility (info, way),
338 value = computeUsefulness (MAXMIN_CRITERION,
339 upMultiplier, downMultiplier, infeas,
340 objectOrig [objInd], objInd,
341 newValue); // output parameter (ignored)
342
343 if (value < minValue) minValue = infeas;
344 if (value > maxValue) maxValue = infeas;
345
346 //printf ("%d(x%d,%d,%g(%g)) ", objInd, *j, pri, infeas, value); fflush (stdout);
347
348 struct objStrongPri *obj = new struct objStrongPri;
349
350 obj -> objIndex_ = objInd;
351 obj -> priority_ = pri;
352 obj -> value_ = infeas;
353
354 orbitObj. push_back (obj);
355 }
356
357 // If minPri < maxPri (unlikely in orbits), sort objects so
358 // scan below is straightforward
359
360 if (minPri < maxPri)
361 std::sort (orbitObj.begin (), orbitObj.end (), compStrongPri);
362
363 // Scan objects in non-decreasing order of priority. Store
364 // in objects (the array of real objects) the one with null
365 // infeasibility and minimum priority.
366
367 for (std::vector <struct objStrongPri *>::iterator j = orbitObj. begin ();
368 j != orbitObj. end (); ++j) {
369
370 //printf ("checking object (%d,%d) --> %e\n", (*j) -> objIndex_, (*j) -> priority_, (*j) -> value_);
371
372 if ((*j) -> value_ > COUENNE_EPS) {
373
374 // Found object of this orbit that is good enough (and
375 // has highest priority)
376
377 objectInd.push_back ((*j) -> objIndex_);
378 break;
379 }
380 }
381
382 for (std::vector <struct objStrongPri *>::iterator j = orbitObj. begin ();
383 j != orbitObj. end (); ++j)
384 delete (*j);
385 }
386
387 numberObjects = objectInd.size ();
388
389 // printf ("there are in total %d objects\n", numberObjects);
390
391 // for (int i=0; i<numberObjects; i++) {
392
393 // printf ("obj %d [%d]: ", i, objectInd [i]); fflush (stdout);
394
395 // OsiObject *obj = info -> solver_ -> objects () [objectInd [i]];
396 // //int way;
397
398 // printf ("x%d [%g,%g] %g\n",
399 // obj -> columnNumber (),
400 // info -> lower_ [obj -> columnNumber ()],
401 // info -> upper_ [obj -> columnNumber ()],
402 // obj -> checkInfeasibility (info));
403 // //obj -> infeasibility (info,way));
404 // }
405
406 delete [] varObj;
407 }
408 }
409 #endif
410
411 bool firstPass = false; // not important; useful for making two
412 // passes, picking different objects
413
414 OsiObject **object = info -> solver_ -> objects ();
415
416 while (numberOnList_ == 0) { // FIXME: add iteration limit
417
418 for (unsigned int i = 0; i < numberObjects; i++) {
419
420 int indexObj = ((objectInd.size () > 0) && (i < objectInd.size ())) ? objectInd [i] : i;
421
422 int way;
423 //double value = object [indexObj] -> checkInfeasibility (info);
424 double value = object [indexObj] -> infeasibility (info, way);
425
426 //printf ("object %d[%d]: %g\n", i, indexObj, value);
427
428 #ifdef FM_SORT_STRONG
429 infeasVal[i] = value;
430 #endif
431
432 double lbForInfeas = 0.0;
433 if(value > lbForInfeas) {
434 numberUnsatisfied_++;
435 if(value >= 1e50) {
436 // infeasible
437 feasible=false;
438 break;
439 }
440 int priorityLevel = object[indexObj]->priority();
441
442 #ifdef FM_SORT_STRONG
443 if(priorityLevel < bestPriority) {
444 bestPriority = priorityLevel;
445 }
446 if(priorityLevel > lastPrio) {
447 posEnd_vPriority--;
448 vPriority[posEnd_vPriority] = priorityLevel;
449 list_[posEnd_vPriority] = indexObj;
450 }
451 else {
452 vPriority[card_vPriority] = priorityLevel;
453 list_[card_vPriority] = indexObj;
454 card_vPriority++;
455 }
456 #else /* not FM_SORT_STRONG */
457 // Better priority? Flush choices.
458 if(priorityLevel < bestPriority) {
459 for (int j=maximumStrong-1; j>=0; j--) {
460 if(list_[j] >= 0) {
461 int iObject = list_[j];
462 list_[j]=-1;
463 useful_[j]=0.0;
464 list_[--putOther]=iObject;
465 }
466 }
467 maximumStrong = CoinMin(maximumStrong,putOther);
468 bestPriority = priorityLevel;
469 check = -COIN_DBL_MAX;
470 checkIndex = 0;
471 check2 = -COIN_DBL_MAX;
472 checkIndex2 = 0;
473 number_not_trusted_ = 0;
474 if(max_most_fra > 0) {
475 for(int j=0; j<max_most_fra; j++) {
476 list2[j]=-1;
477 useful2[j]=0.0;
478 }
479 }
480 }
481 if(priorityLevel == bestPriority) {
482 // Modify value
483 double value2;
484 value = computeUsefulness(MAXMIN_CRITERION,
485 upMultiplier, downMultiplier, value,
486 object[indexObj], indexObj, value2);
487 if(value > check) {
488 //add to list
489 int iObject = list_[checkIndex];
490 if(iObject >= 0) {
491 assert (list_[putOther-1]<0);
492 list_[--putOther]=iObject; // to end
493 }
494 list_[checkIndex]= indexObj;
495 assert (checkIndex<putOther);
496 useful_[checkIndex]=value;
497 // find worst
498 check=COIN_DBL_MAX;
499 maximumStrong = CoinMin(maximumStrong,putOther);
500 for (int j=0; j<maximumStrong; j++) {
501 if(list_[j]>=0) {
502 if (useful_[j]<check) {
503 check=useful_[j];
504 checkIndex=j;
505 }
506 }
507 else {
508 check=0.0;
509 checkIndex = j;
510 break;
511 }
512 }
513 }
514 else {
515 // to end
516 assert (list_[putOther-1]<0);
517 list_[--putOther] = indexObj;
518 maximumStrong = CoinMin(maximumStrong,putOther);
519 }
520
521 if((max_most_fra > 0) && (value2 > check2)) {
522 // add to list of integer infeasibilities
523 number_not_trusted_++;
524 list2[checkIndex2] = indexObj;
525 useful2[checkIndex2]=value2;
526 // find worst
527 check2=COIN_DBL_MAX;
528 for(int j=0; j<max_most_fra; j++) {
529 if(list2[j] >= 0) {
530 if(useful2[j] < check2) {
531 check2=useful2[j];
532 checkIndex2=j;
533 }
534 }
535 else {
536 check2=0.0;
537 checkIndex2 = j;
538 break;
539 }
540 }
541 }
542 }
543 else {
544 // worse priority
545 // to end
546 assert (list_[putOther-1]<0);
547 list_[--putOther]= indexObj;
548 maximumStrong = CoinMin(maximumStrong,putOther);
549 }
550 #endif /* not FM_SORT_STRONG */
551 }
552 }
553
554 #ifdef FM_SORT_STRONG
555
556 #ifdef FM_CHECK
557 if(card_vPriority - posEnd_vPriority + numberObjects != numberUnsatisfied_) {
558 printf("CouenneChooseStrong::gutsOfSetupList(): ### ERROR: card_vPriority: %d posEnd_vPriority: %d numberUnsatisfied: %d numberObjects: %d\n",
559 card_vPriority, posEnd_vPriority, numberUnsatisfied_, numberObjects);
560 exit(1);
561 }
562 #endif
563
564 numberOnList_ = 0;
565 if(feasible) {
566 int card_smallerThanPrio = card_vPriority;
567 if(posEnd_vPriority > card_vPriority) {
568 for(int i=posEnd_vPriority; i<numberObjects; i++) {
569 list_[card_vPriority] = list_[i];
570 list_[i] = -1;
571 vPriority[card_vPriority] = vPriority[i];
572 card_vPriority++;
573 }
574 }
575 else {
576 card_vPriority = numberUnsatisfied_;
577 }
578 // correct bounds if card_smallThanPrio >= maximumStrong
579 int sortFrom = 0;
580 int sortUpTo = card_smallerThanPrio;
581 if(card_smallerThanPrio < maximumStrong) {
582 sortFrom = card_smallerThanPrio;
583 sortUpTo = card_vPriority;
584 }
585 if(card_vPriority > 0) {
586 numberOnList_ = (card_vPriority < maximumStrong ? card_vPriority : maximumStrong);
587
588 #ifdef FM_ALWAYS_SORT /* FM_SORT_STRONG */
589 bool alwaysSort = true;
590 #else
591 bool alwaysSort = false;
592 #endif
593 if(alwaysSort) {
594 sortFrom = 0;
595 sortUpTo = card_vPriority;
596 }
597 if((sortUpTo > maximumStrong) || alwaysSort){
598 // sort list_[card_sortFrom..card_sortUpTo-1] according to priority
599 CoinSort_2(vPriority + sortFrom, vPriority + sortUpTo,
600 list_ + sortFrom);
601 }
602 for(int i=0; i<card_vPriority; i++) {
603 int indObj = list_[i];
604 double value = 0, value2;
605 value = computeUsefulness(MAXMIN_CRITERION,
606 upMultiplier, downMultiplier, value,
607 object[indObj], indObj, value2);
608
609 #ifdef OLD_USEFULLNESS /* FM_SORT_STRONG */
610 useful_[i] = -value; //printf ("useful_ [%d] <-- %g\n", i, -value);
611 #else
612 if ((sortCrit_ & 1) == 0) {
613 useful_[i] = -value; //printf ("useful_ [%d] <-- %g\n", i, -value);
614 }
615 else {
616 useful_[i] = value; //printf ("useful_ [%d] <-- %g\n", i, value);
617 }
618 #endif
619
620 #ifdef USE_NOT_TRUSTED
621 if(value2 < -COIN_DBL_MAX / 10) { // object with trusted pseudo-cost
622 infeasVal[i] = -COIN_DBL_MAX;
623 }
624 #endif
625 }
626
627 #ifdef USE_NOT_TRUSTED /* FM_SORT_STRONG */
628 // adjust usefulness of objects having priority bestPriority
629 if((card_vPriority > maximumStrong) &&
630 (vPriority[maximumStrong] < bestPriority + COUENNE_EPS)) {
631 // not all objects with bestPriority will be selected
632
633 int cardFrac = 0;
634 int *fracInd = new int[card_vPriority]; // holds position
635 // in list_
636 double *fracVal = new double[card_vPriority];
637
638 // Find all untrusted objects with min priority
639 for(int i=0; i<card_vPriority; i++) {
640 //int indObj = list_[i]; // FIXME: why not used?
641 if(vPriority[i] < bestPriority + COUENNE_EPS) {
642 if(infeasVal[i] > -COIN_DBL_MAX/10) {
643 fracInd[cardFrac] = i;
644 fracVal[cardFrac] = -infeasVal[i];
645 cardFrac++;
646 }
647 }
648 }
649
650 if(max_most_fra > 0) {
651
652 // if more than max_most_fra, sort to pick the ones with max viol
653 if(cardFrac > max_most_fra) {
654 CoinSort_2(fracVal, fracVal+cardFrac, fracInd);
655 }
656 for(int i=0; i<cardFrac; i++) {
657 useful_[fracInd[i]] =
658 -1e150*(1. + infeasVal[fracInd[i]]);
659 //-1e150*(1. + infeasVal[list_[fracInd[i]]]); // FIXME: check if uncommented is correct
660
661 // printf ("useful_ [fracInd[%d]", i);
662 // printf (" = %d] <--", fracInd [i]);
663 // printf (" %g", useful_ [fracInd [i]]);
664 // //printf (" [list[%d]=%d]", fracInd [i], list_ [fracInd [i]]);
665 // //printf (" inf=%g\n", infeasVal [list_ [fracInd [i]]]);
666 // printf (" [%d]", fracInd [i]);
667 // printf (" inf=%g\n", infeasVal [fracInd [i]]);
668
669 number_not_trusted_++;
670 if(i == max_most_fra - 1) {
671 break;
672 }
673 }
674 }
675 delete[] fracInd;
676 delete[] fracVal;
677 }
678 #endif /* USE_NOT_TRUSTED and FM_SORT_STRONG */
679 }
680
681 //printf ("card_vprio = %d\n", card_vPriority);
682
683 #ifdef FM_SEC_SORT_USEFUL
684 CoinSort_2(useful_, useful_ + card_vPriority, list_);
685 #else /* FM_SORT_STRONG not FM_SEC_SORT_USEFUL */
686 #ifdef FM_ALWAYS_SORT /* FM_SORT_STRONG */
687 int from = 0, upto = 1;
688 while(upto < card_vPriority) {
689 while(vPriority[upto] == vPriority[from]) {
690 upto++;
691 if(upto == card_vPriority) {
692 break;
693 }
694 }
695 CoinSort_2(useful_+from, useful_+upto, list_+from);
696 from = upto;
697 upto = from+1;
698 }
699 #else /* FM_SORT_STRONG not FM_ALWAYS_SORT */
700 if(sortUpTo > maximumStrong) {
701 // compute from, upto such that
702 // vPriority[k] == vPriority[maximumStrong] for k in [from..upto-1]
703 int from = maximumStrong-1, upto = maximumStrong;
704 int msPrio = vPriority[maximumStrong-1];
705 problem_->setLastPrioSort(msPrio);
706 while((from > -1) && (vPriority[from] == msPrio)) {
707 from--;
708 }
709 from++;
710 while((upto < sortUpTo) && (vPriority[upto] == msPrio)) {
711 upto++;
712 }
713 // sort list[from]..list[upto-1] according to
714 // useful_[from]..useful_[upto-1]
715 CoinSort_2(useful_+from, useful_+upto, list_+from);
716 }
717
718 #endif /* FM_SORT_STRONG not FM_ALWAYS_SORT */
719
720 #ifdef FM_CHECK
721 // priority of last selected object
722 double ckPrio = (card_vPriority < numberUnsatisfied_ ?
723 vPriority[card_vPriority] : 100000);
724 double ckUse = (card_vPriority < numberUnsatisfied_ ?
725 useful_[card_vPriority] : 100000);
726 for(int i=0; i<card_vPriority; i++) {
727 int indObj = list_[i];
728 if(object[indObj]->priority() > ckPrio + 1e-3) {
729 printf("CouenneChooseStrong::gutsOfSetupList(): ### ERROR: object[%d]->priority(): %d > ckPrio: %d\n",
730 indObj, object[indObj]->priority(), ckPrio);
731 exit(1);
732 }
733 if(fabs(object[indObj]->priority() - ckPrio) < 1e-3) {
734 if(useful_[i] > ckUse + 1e-3) {
735 printf("CouenneChooseStrong::gutsOfSetupList(): ### ERROR: object[%d]->useful: %f > ckUse: %d\n",
736 indObj, useful_[i], ckUse);
737 exit(1);
738 }
739 }
740 }
741 for(int i=card_vPriority; i<numberUnsatisfied_; i++) {
742 int indObj = list_[i];
743 if(object[indObj]->priority() < ckPrio - 1e-3) {
744 printf("CouenneChooseStrong::gutsOfSetupList(): ### ERROR: object[%d]->priority(): %d < ckPrio: %d\n",
745 indObj, object[indObj]->priority(), ckPrio);
746 exit(1);
747 }
748 if(fabs(object[indObj]->priority() - ckPrio) < 1e-3) {
749 if(useful_[i] < ckUse - 1e-3) {
750 printf("CouenneChooseStrong::gutsOfSetupList(): ### ERROR: object[%d]->useful: %f < ckUse: %d\n",
751 indObj, useful_[i], ckUse);
752 exit(1);
753 }
754 }
755 }
756 #endif /* CHECK */
757 #endif /* FM_SORT_STRONG not FM_ALWAYS_SORT */
758 }
759 else {
760 numberUnsatisfied_ = -1;
761 }
762 #else /* not FM_SORT_STRONG */
763 // Get list
764 numberOnList_=0;
765 if (feasible) {
766 maximumStrong = CoinMin(maximumStrong,putOther);
767 for (int i=0;i<maximumStrong;i++) {
768 if (list_[i]>=0) {
769 #ifdef OLD_USEFULLNESS
770 list_[numberOnList_]=list_[i];
771 useful_[numberOnList_++]=-useful_[i];
772
773 #else
774 list_[numberOnList_]=list_[i];
775 if ((sortCrit_ & 1) == 0) {
776 useful_[numberOnList_++]=-useful_[i];
777 }
778 else useful_[numberOnList_++] = useful_[i];
779 #endif
780 message(CANDIDATE_LIST2)<<numberOnList_-1
781 <<list_[numberOnList_-1]<<numberOnList_-1<<useful_[numberOnList_-1]
782 <<CoinMessageEol;
783 }
784 }
785 if (numberOnList_) {
786 int tmp_on_list = 0;
787 if (max_most_fra > 0 && numberOnList_ >= maximumStrong) {
788 // If we want to force non-trusted in the list, give them huge
789 // weight here
790 number_not_trusted_=0;
791 for (int i=0;i<max_most_fra;i++) {
792 if (list2[i]>=0) {
793 list2[number_not_trusted_] = list2[i];
794 useful2[number_not_trusted_++] = useful2[i];
795 message(CANDIDATE_LIST3)<<number_not_trusted_-1
796 <<list2[number_not_trusted_-1]<<number_not_trusted_-1
797 <<useful2[number_not_trusted_-1]<<CoinMessageEol;
798 }
799 }
800 if (number_not_trusted_) {
801 CoinSort_2(list_,list_+numberOnList_,useful_);
802 CoinSort_2(list2,list2+number_not_trusted_,useful2);
803 int i1=0;
804 int i2=0;
805 for (int i=0; i<numberObjects; i++) {
806 bool found1 = (list_[i1]==i);
807 bool found2 = (list2[i2]==i);
808 if (found1 && found2) {
809
810 #ifdef OLD_USEFULLNESS
811 useful_[i1] = 1e150*(1.+useful2[i2]);
812 #else
813 useful_[i1] = -1e150*(1.+useful2[i2]);
814 #endif
815 list2[i2] = -1;
816 }
817 if (found1) i1++;
818 if (found2) i2++;
819 if (i2==max_most_fra) break;
820 }
821 for (int i=0; i<number_not_trusted_; i++) {
822 if (list2[i] >= 0) {
823 list_[numberOnList_+tmp_on_list] = list2[i];
824
825 #ifdef OLD_USEFULLNESS
826 useful_[numberOnList_+tmp_on_list] = 1e150*(1.+useful2[i]);
827 #else
828 useful_[numberOnList_+tmp_on_list] = -1e150*(1.+useful2[i]);
829 #endif
830 tmp_on_list++;
831 }
832 }
833 }
834 }
835 // Sort
836 CoinSort_2(useful_,useful_+numberOnList_+tmp_on_list,list_);
837 // move others
838 int i = numberOnList_;
839 for (;putOther<numberObjects;putOther++)
840 list_[i++]=list_[putOther];
841 assert (i==numberUnsatisfied_);
842 if (!CoinMax(numberStrong_,numberStrongRoot_))
843 numberOnList_=0;
844 }
845 }
846 else {
847 // not feasible
848 numberUnsatisfied_=-1;
849 }
850 #endif /* not FM_SORT_STRONG */
851
852 if(!firstPass) {
853
854 //printf ("bailed out of while numberOnList_ == 0\n");
855 break;
856 }
857 firstPass = false;
858 } /* while(numberOnList_ == 0) */
859
860 #ifdef TRACE_STRONG
861 if(problem_->doPrint_) {
862 printf("numberStrong_: %d maximumStrong: %d\n",
863 numberStrong_, maximumStrong);
864 }
865 #endif
866
867 #ifdef FM_SORT_STRONG
868 delete [] vPriority;
869 delete [] infeasVal;
870 #else /* not FM_SORT_STRONG */
871 delete [] list2;
872 delete [] useful2;
873 #endif /* not FM_SORT_STRONG */
874
875 // Get rid of any shadow prices info
876 info->defaultDual_ = -1.0; // switch off
877 delete [] info->usefulRegion_;
878 delete [] info->indexRegion_;
879
880 int way;
881 if (bb_log_level_>3) {
882 //for (int i=0; i<Min(numberUnsatisfied_,numberStrong_); i++)
883 for (int i=0; i<numberOnList_; i++){
884 message(CANDIDATE_LIST)<<i<< list_[i]<< i<< useful_[i]
885 <<object[list_[i]]->infeasibility(info,way)
886 //<<object[list_[i]]->checkInfeasibility(info)
887 <<CoinMessageEol;
888 }
889 }
890
891 #ifdef COIN_HAS_NTY
892 // if (useOrbitalBranching &&
893 // (objectOrig != object))
894 // delete [] object;
895 #endif
896
897 // return -1 if infeasible to differentiate with numberOnList_==0
898 // when feasible
899 if(numberUnsatisfied_ == -1) {
900 return(-1);
901 }
902 return numberOnList_;
903 }
904
905