#include <SbbBranchUser.hpp>
Inheritance diagram for SbbBranchUserDecision:
Public Member Functions | |
| SbbBranchUserDecision (const SbbBranchUserDecision &) | |
| virtual SbbBranchDecision * | clone () const |
| Clone. | |
| virtual void | initialize (SbbModel *model) |
| Initialize i.e. before start of choosing at a node. | |
| virtual int | betterBranch (SbbBranchingObject *thisOne, SbbBranchingObject *bestSoFar, double changeUp, int numberInfeasibilitiesUp, double changeDown, int numberInfeasibilitiesDown) |
| virtual int | bestBranch (SbbBranchingObject **objects, int numberObjects, int numberUnsatisfied, double *changeUp, int *numberInfeasibilitiesUp, double *changeDown, int *numberInfeasibilitiesDown, double objectiveValue) |
| Compare N branching objects. Return index of best and sets way of branching in chosen object. | |
Private Member Functions | |
| SbbBranchUserDecision & | operator= (const SbbBranchUserDecision &rhs) |
| Illegal Assignment operator. | |
Definition at line 10 of file SbbBranchUser.hpp.
|
||||||||||||||||||||||||||||||||||||
|
Compare N branching objects. Return index of best and sets way of branching in chosen object. This routine is used only after strong branching. This is reccommended version as it can be more sophisticated Reimplemented from SbbBranchDecision. Definition at line 73 of file SbbBranchUser.cpp. References SbbModel::getCutoff(), SbbModel::getNumberHeuristicSolutions(), SbbModel::getSolutionCount(), and SbbBranchingObject::model().
00078 {
00079
00080 int bestWay=0;
00081 int whichObject = -1;
00082 if (numberObjects) {
00083 SbbModel * model = objects[0]->model();
00084 // at continuous
00085 //double continuousObjective = model->getContinuousObjective();
00086 //int continuousInfeasibilities = model->getContinuousInfeasibilities();
00087
00088 // average cost to get rid of infeasibility
00089 //double averageCostPerInfeasibility =
00090 //(objectiveValue-continuousObjective)/
00091 //(double) (abs(continuousInfeasibilities-numberUnsatisfied)+1);
00092 /* beforeSolution is :
00093 0 - before any solution
00094 n - n heuristic solutions but no branched one
00095 -1 - branched solution found
00096 */
00097 #if 0
00098 int beforeSolution;
00099 int numberSolutions = model->getSolutionCount();
00100 if (numberSolutions) {
00101 int numberHeuristic = model->getNumberHeuristicSolutions();
00102 if (numberHeuristic<numberSolutions)
00103 beforeSolution = -1;
00104 else
00105 beforeSolution = numberHeuristic;
00106 } else {
00107 beforeSolution=0;
00108 }
00109 int bestNumber=INT_MAX;
00110 double bestCriterion=-1.0;
00111 if (!beforeSolution) {
00112 // before solution - choose smallest number
00113 // could add in depth as well
00114 for (int i = 0 ; i < numberObjects ; i++) {
00115 int thisNumber = min(numberInfeasibilitiesUp[i],numberInfeasibilitiesDown[i]);
00116 if (thisNumber<=bestNumber) {
00117 int betterWay=0;
00118 if (numberInfeasibilitiesUp[i]<numberInfeasibilitiesDown[i]) {
00119 if (numberInfeasibilitiesUp[i]<bestNumber) {
00120 betterWay = 1;
00121 } else {
00122 if (changeUp[i]<bestCriterion)
00123 betterWay=1;
00124 }
00125 } else if (numberInfeasibilitiesUp[i]>numberInfeasibilitiesDown[i]) {
00126 if (numberInfeasibilitiesDown[i]<bestNumber) {
00127 betterWay = -1;
00128 } else {
00129 if (changeDown[i]<bestCriterion)
00130 betterWay=-1;
00131 }
00132 } else {
00133 // up and down have same number
00134 bool better=false;
00135 if (numberInfeasibilitiesUp[i]<bestNumber) {
00136 better=true;
00137 } else if (numberInfeasibilitiesUp[i]==bestNumber) {
00138 if (min(changeUp[i],changeDown[i])<bestCriterion)
00139 better=true;;
00140 }
00141 if (better) {
00142 // see which way
00143 if (changeUp[i]<=changeDown[i])
00144 betterWay=1;
00145 else
00146 betterWay=-1;
00147 }
00148 }
00149 if (betterWay) {
00150 bestCriterion = min(changeUp[i],changeDown[i]);
00151 bestNumber = thisNumber;
00152 whichObject = i;
00153 bestWay = betterWay;
00154 }
00155 }
00156 }
00157 } else if (beforeSolution>0) {
00158 // got heuristic solutions
00159 // so balance stuff (see if number unsat getting better)
00160 for (int i = 0 ; i < numberObjects ; i++) {
00161 int betterWay=0;
00162 if (changeUp[i]<=changeDown[i]) {
00163 if (changeUp[i]>bestCriterion)
00164 betterWay=1;
00165 } else {
00166 if (changeDown[i]>bestCriterion)
00167 betterWay=-1;
00168 }
00169 if (betterWay) {
00170 bestCriterion = min(changeUp[i],changeDown[i]);
00171 whichObject = i;
00172 bestWay = betterWay;
00173 }
00174 }
00175 } else {
00176 // got a branching solution
00177 for (int i = 0 ; i < numberObjects ; i++) {
00178 int betterWay=0;
00179 if (changeUp[i]<=changeDown[i]) {
00180 if (changeUp[i]>bestCriterion)
00181 betterWay=1;
00182 } else {
00183 if (changeDown[i]>bestCriterion)
00184 betterWay=-1;
00185 }
00186 if (betterWay) {
00187 bestCriterion = min(changeUp[i],changeDown[i]);
00188 whichObject = i;
00189 bestWay = betterWay;
00190 }
00191 }
00192 }
00193 #else
00194 int numberSolutions = model->getSolutionCount();
00195 double cutoff = model->getCutoff();
00196 int method=0;
00197 int i;
00198 if (numberSolutions) {
00199 int numberHeuristic = model->getNumberHeuristicSolutions();
00200 if (numberHeuristic<numberSolutions) {
00201 method = 1;
00202 } else {
00203 method = 2;
00204 // look further
00205 for ( i = 0 ; i < numberObjects ; i++) {
00206 int numberNext = numberInfeasibilitiesUp[i];
00207
00208 if (numberNext<numberUnsatisfied) {
00209 int numberUp = numberUnsatisfied - numberInfeasibilitiesUp[i];
00210 double perUnsatisfied = changeUp[i]/(double) numberUp;
00211 double estimatedObjective = objectiveValue + numberUnsatisfied * perUnsatisfied;
00212 if (estimatedObjective<cutoff)
00213 method=3;
00214 }
00215 numberNext = numberInfeasibilitiesDown[i];
00216 if (numberNext<numberUnsatisfied) {
00217 int numberDown = numberUnsatisfied - numberInfeasibilitiesDown[i];
00218 double perUnsatisfied = changeDown[i]/(double) numberDown;
00219 double estimatedObjective = objectiveValue + numberUnsatisfied * perUnsatisfied;
00220 if (estimatedObjective<cutoff)
00221 method=3;
00222 }
00223 }
00224 }
00225 method=2;
00226 } else {
00227 method = 0;
00228 }
00229 /* Methods :
00230 0 - fewest infeasibilities
00231 1 - largest min change in objective
00232 2 - as 1 but use sum of changes if min close
00233 3 - predicted best solution
00234 */
00235 int bestNumber=INT_MAX;
00236 double bestCriterion=-1.0;
00237 double alternativeCriterion = -1.0;
00238 double bestEstimate = 1.0e100;
00239 switch (method) {
00240 case 0:
00241 // could add in depth as well
00242 for ( i = 0 ; i < numberObjects ; i++) {
00243 int thisNumber = min(numberInfeasibilitiesUp[i],numberInfeasibilitiesDown[i]);
00244 if (thisNumber<=bestNumber) {
00245 int betterWay=0;
00246 if (numberInfeasibilitiesUp[i]<numberInfeasibilitiesDown[i]) {
00247 if (numberInfeasibilitiesUp[i]<bestNumber) {
00248 betterWay = 1;
00249 } else {
00250 if (changeUp[i]<bestCriterion)
00251 betterWay=1;
00252 }
00253 } else if (numberInfeasibilitiesUp[i]>numberInfeasibilitiesDown[i]) {
00254 if (numberInfeasibilitiesDown[i]<bestNumber) {
00255 betterWay = -1;
00256 } else {
00257 if (changeDown[i]<bestCriterion)
00258 betterWay=-1;
00259 }
00260 } else {
00261 // up and down have same number
00262 bool better=false;
00263 if (numberInfeasibilitiesUp[i]<bestNumber) {
00264 better=true;
00265 } else if (numberInfeasibilitiesUp[i]==bestNumber) {
00266 if (min(changeUp[i],changeDown[i])<bestCriterion)
00267 better=true;;
00268 }
00269 if (better) {
00270 // see which way
00271 if (changeUp[i]<=changeDown[i])
00272 betterWay=1;
00273 else
00274 betterWay=-1;
00275 }
00276 }
00277 if (betterWay) {
00278 bestCriterion = min(changeUp[i],changeDown[i]);
00279 bestNumber = thisNumber;
00280 whichObject = i;
00281 bestWay = betterWay;
00282 }
00283 }
00284 }
00285 break;
00286 case 1:
00287 for ( i = 0 ; i < numberObjects ; i++) {
00288 int betterWay=0;
00289 if (changeUp[i]<=changeDown[i]) {
00290 if (changeUp[i]>bestCriterion)
00291 betterWay=1;
00292 } else {
00293 if (changeDown[i]>bestCriterion)
00294 betterWay=-1;
00295 }
00296 if (betterWay) {
00297 bestCriterion = min(changeUp[i],changeDown[i]);
00298 whichObject = i;
00299 bestWay = betterWay;
00300 }
00301 }
00302 break;
00303 case 2:
00304 for ( i = 0 ; i < numberObjects ; i++) {
00305 double change = min(changeUp[i],changeDown[i]);
00306 double sum = changeUp[i] + changeDown[i];
00307 bool take=false;
00308 if (change>1.1*bestCriterion)
00309 take=true;
00310 else if (change>0.9*bestCriterion&&sum+change>bestCriterion+alternativeCriterion)
00311 take=true;
00312 if (take) {
00313 if (changeUp[i]<=changeDown[i]) {
00314 if (changeUp[i]>bestCriterion)
00315 bestWay=1;
00316 } else {
00317 if (changeDown[i]>bestCriterion)
00318 bestWay=-1;
00319 }
00320 bestCriterion = change;
00321 alternativeCriterion = sum;
00322 whichObject = i;
00323 }
00324 }
00325 break;
00326 case 3:
00327 for ( i = 0 ; i < numberObjects ; i++) {
00328 int numberNext = numberInfeasibilitiesUp[i];
00329
00330 if (numberNext<numberUnsatisfied) {
00331 int numberUp = numberUnsatisfied - numberInfeasibilitiesUp[i];
00332 double perUnsatisfied = changeUp[i]/(double) numberUp;
00333 double estimatedObjective = objectiveValue + numberUnsatisfied * perUnsatisfied;
00334 if (estimatedObjective<bestEstimate) {
00335 bestEstimate = estimatedObjective;
00336 bestWay=1;
00337 whichObject=i;
00338 }
00339 }
00340 numberNext = numberInfeasibilitiesDown[i];
00341 if (numberNext<numberUnsatisfied) {
00342 int numberDown = numberUnsatisfied - numberInfeasibilitiesDown[i];
00343 double perUnsatisfied = changeDown[i]/(double) numberDown;
00344 double estimatedObjective = objectiveValue + numberUnsatisfied * perUnsatisfied;
00345 if (estimatedObjective<bestEstimate) {
00346 bestEstimate = estimatedObjective;
00347 bestWay=-1;
00348 whichObject=i;
00349 }
00350 }
00351 }
00352 break;
00353 }
00354 #endif
00355 // set way in best
00356 objects[whichObject]->way(bestWay);
00357 }
00358 return whichObject;
00359 }
|
|
||||||||||||||||||||||||||||
|
Returns nonzero if branching on first object is "better" than on second (if second NULL first wins). This is only used after strong branching. The initial selection is done by infeasibility() for each SbbObject return code +1 for up branch preferred, -1 for down Implements SbbBranchDecision. Definition at line 56 of file SbbBranchUser.cpp.
00060 {
00061 printf("Now obsolete SbbBranchUserDecision::betterBranch\n");
00062 abort();
00063 return 0;
00064 }
|
1.3.5