1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (C) 2002-2022 Konrad-Zuse-Zentrum */ 7 /* fuer Informationstechnik Berlin */ 8 /* */ 9 /* SCIP is distributed under the terms of the ZIB Academic License. */ 10 /* */ 11 /* You should have received a copy of the ZIB Academic License */ 12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */ 13 /* */ 14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 15 16 /**@file cutsel_dynamic.c 17 * @ingroup DEFPLUGINS_CUTSEL 18 * @brief dynamic cut selector 19 * @author Christoph Graczyk 20 */ 21 22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 23 24 #include <assert.h> 25 26 27 #include "scip/scip_cutsel.h" 28 #include "scip/scip_cut.h" 29 #include "scip/scip_lp.h" 30 #include "scip/scip_randnumgen.h" 31 #include "scip/cutsel_dynamic.h" 32 33 34 #define CUTSEL_NAME "dynamic" 35 #define CUTSEL_DESC "dynamic orthogonality for hybrid cutsel" 36 #define CUTSEL_PRIORITY 7000 37 38 #define RANDSEED 0x5EED 39 40 #define DEFAULT_EFFICACYWEIGHT 1.0 /**< weight of efficacy in score calculation */ 41 #define DEFAULT_DIRCUTOFFDISTWEIGHT 0.0 /**< weight of directed cutoff distance in score calculation */ 42 #define DEFAULT_OBJPARALWEIGHT 0.0 /**< weight of objective parallelism in score calculation */ 43 #define DEFAULT_INTSUPPORTWEIGHT 0.0 /**< weight of integral support in cut score calculation */ 44 #define DEFAULT_MINORTHO 0.9 /**< minimal orthogonality in percent for a cut to enter the LP */ 45 #define DEFAULT_MINGAIN 0.01 /**< minimal efficacy gain for a cut to enter the LP */ 46 #define DEFAULT_MAXDEPTH (-1) /**< maximum depth at which this cutselector is used (-1 : all nodes) */ 47 #define DEFAULT_FILTERMODE 'd' /**< filtering strategy during cut selection ( 48 * 'd'ynamic- and 'f'ull dynamic parallelism) */ 49 50 51 /* 52 * Data structures 53 */ 54 55 /** cut selector data */ 56 struct SCIP_CutselData 57 { 58 SCIP_RANDNUMGEN* randnumgen; /**< random generator for tiebreaking */ 59 SCIP_Real objparalweight; /**< weight of objective parallelism in cut score calculation */ 60 SCIP_Real efficacyweight; /**< weight of efficacy in cut score calculation */ 61 SCIP_Real dircutoffdistweight;/**< weight of directed cutoff distance in cut score calculation */ 62 SCIP_Real intsupportweight; /**< weight of integral support in cut score calculation */ 63 SCIP_Real mingain; /**< minimal projection efficacy gain for a cut to enter the LP in percent */ 64 SCIP_Real minortho; /**< minimal orthogonality for a cut to enter the LP */ 65 int maxdepth; /**< maximum depth at which this cutselector is used (-1 : all nodes) */ 66 char filtermode; /**< filtering strategy during cut selection ( 67 * 'd'ynamic- and 'f'ull dynamic parallelism) */ 68 }; 69 70 /* 71 * Local methods 72 */ 73 74 /* put your local methods here, and declare them static */ 75 76 /** returns the maximum score of cuts; if scores is not NULL, then stores the individual score of each cut in scores */ 77 static 78 void scoring( 79 SCIP* scip, /**< SCIP data structure */ 80 SCIP_ROW** cuts, /**< array with cuts to score */ 81 SCIP_RANDNUMGEN* randnumgen, /**< random number generator for tie-breaking, or NULL */ 82 SCIP_Real dircutoffdistweight,/**< weight of directed cutoff distance in cut score calculation */ 83 SCIP_Real efficacyweight, /**< weight of efficacy in cut score calculation */ 84 SCIP_Real objparalweight, /**< weight of objective parallelism in cut score calculation */ 85 SCIP_Real intsupportweight, /**< weight of integral support in cut score calculation */ 86 int* currentncuts, /**< current number of cuts in cuts array */ 87 SCIP_Real* scores /**< array to store the score of cuts or NULL */ 88 ) 89 { 90 SCIP_Real maxscore = 0.0; 91 SCIP_SOL* sol; 92 int i; 93 int ncuts = *currentncuts; 94 95 sol = SCIPgetBestSol(scip); 96 97 /* if there is an incumbent and the factor is not 0.0, compute directed cutoff distances for the incumbent */ 98 if( sol != NULL && dircutoffdistweight > 0.0 ) 99 { 100 for( i = ncuts-1; i >= 0; --i ) 101 { 102 SCIP_Real score; 103 SCIP_Real objparallelism; 104 SCIP_Real intsupport; 105 SCIP_Real efficacy; 106 107 if( intsupportweight > 0.0 ) 108 intsupport = intsupportweight * SCIPgetRowNumIntCols(scip, cuts[i]) / (SCIP_Real) SCIProwGetNNonz(cuts[i]); 109 else 110 intsupport = 0.0; 111 112 if( objparalweight > 0.0 ) 113 objparallelism = objparalweight * SCIPgetRowObjParallelism(scip, cuts[i]); 114 else 115 objparallelism = 0.0; 116 117 efficacy = SCIPgetCutEfficacy(scip, NULL, cuts[i]); 118 119 if( SCIProwIsLocal(cuts[i]) ) 120 { 121 score = dircutoffdistweight * efficacy; 122 } 123 else 124 { 125 score = SCIPgetCutLPSolCutoffDistance(scip, sol, cuts[i]); 126 score = dircutoffdistweight * MAX(score, efficacy); 127 } 128 129 efficacy *= efficacyweight; 130 score += objparallelism + intsupport + efficacy; 131 132 /* add small term to prefer global pool cuts */ 133 if( SCIProwIsInGlobalCutpool(cuts[i]) ) 134 score += 1e-4; 135 136 if( randnumgen != NULL) 137 { 138 score += SCIPrandomGetReal(randnumgen, 0.0, 1e-6); 139 } 140 141 maxscore = MAX(maxscore, score); 142 143 if( scores != NULL) 144 { 145 if( SCIPisLE(scip, score, 0.0) ) 146 { 147 --ncuts; 148 SCIPswapPointers((void**) &cuts[i], (void**) &cuts[ncuts]); 149 SCIPswapReals(&scores[i], &scores[ncuts]); 150 } 151 else 152 scores[i] = score; 153 } 154 } 155 } 156 else 157 { 158 /* in case there is no solution add the directed cutoff distance weight to the efficacy weight 159 * since the efficacy underestimates the directed cuttoff distance 160 */ 161 efficacyweight += dircutoffdistweight; 162 163 /*lint -e{850} i is modified in the body of the for loop */ 164 for( i = ncuts-1; i >= 0; --i ) 165 { 166 SCIP_Real score; 167 SCIP_Real objparallelism; 168 SCIP_Real intsupport; 169 SCIP_Real efficacy; 170 171 if( intsupportweight > 0.0 ) 172 intsupport = intsupportweight * SCIPgetRowNumIntCols(scip, cuts[i]) / (SCIP_Real) SCIProwGetNNonz(cuts[i]); 173 else 174 intsupport = 0.0; 175 176 if( objparalweight > 0.0 ) 177 objparallelism = objparalweight * SCIPgetRowObjParallelism(scip, cuts[i]); 178 else 179 objparallelism = 0.0; 180 181 efficacy = efficacyweight > 0.0 ? efficacyweight * SCIPgetCutEfficacy(scip, NULL, cuts[i]) : 0.0; 182 183 score = objparallelism + intsupport + efficacy; 184 185 /* add small term to prefer global pool cuts */ 186 if( SCIProwIsInGlobalCutpool(cuts[i]) ) 187 score += 1e-4; 188 189 if( randnumgen != NULL) 190 { 191 score += SCIPrandomGetReal(randnumgen, 0.0, 1e-6); 192 } 193 194 maxscore = MAX(maxscore, score); 195 196 if( scores != NULL) 197 { 198 if( SCIPisLE(scip, score, 0.0) ) 199 { 200 --ncuts; 201 SCIPswapPointers((void**) &cuts[i], (void**) &cuts[ncuts]); 202 SCIPswapReals(&scores[i], &scores[ncuts]); 203 } 204 else 205 scores[i] = score; 206 } 207 } 208 } 209 *currentncuts = ncuts; 210 } 211 212 /** compute projectioncut score for cuts from a given bestcut. **/ 213 static 214 SCIP_RETCODE computeProjectionScore( 215 SCIP* scip, /**< SCIP data structure */ 216 SCIP_ROW* bestcut, /**< cut to filter orthogonality with */ 217 SCIP_ROW* cut, /**< cut to perform scoring on */ 218 SCIP_Real* score /**< score for cut */ 219 ) 220 { 221 SCIP_Real efficacy; 222 SCIP_Real currentbestefficacy; 223 SCIP_Real cosineangle; 224 225 SCIPdebugMsg(scip, "\ncomputeProjectionScore.\n\n"); 226 currentbestefficacy = SCIPgetCutEfficacy(scip, NULL, bestcut); 227 SCIPdebugMsg(scip, "currentbestefficacy = %g\n", currentbestefficacy); 228 229 efficacy = SCIPgetCutEfficacy(scip, NULL, cut); 230 SCIPdebugMsg(scip, "efficacy[%s] = %g\n", SCIProwGetName(cut), efficacy); 231 232 cosineangle = SCIProwGetParallelism(bestcut, cut, 'e'); 233 if( SCIPisEQ(scip, cosineangle, 1.0)) 234 *score = -SCIPinfinity(scip); 235 else 236 { 237 *score = SQRT(currentbestefficacy * currentbestefficacy + efficacy * efficacy 238 - 2 * fabs(currentbestefficacy) * fabs(efficacy) * cosineangle) 239 / SQRT((1 - (cosineangle * cosineangle))); 240 *score -= currentbestefficacy; 241 } 242 SCIPdebugMsg(scip, "Projectionscore[%s] = %g\n", SCIProwGetName(cut), *score); 243 return SCIP_OKAY; 244 } 245 246 /** move the cut with the highest score to the first position in the array; there must be at least one cut */ 247 static 248 void selectBestCut( 249 SCIP_ROW** cuts, /**< array with cuts to perform selection algorithm */ 250 SCIP_Real* scores, /**< array with scores of cuts to perform selection algorithm */ 251 int ncuts /**< number of cuts in given array */ 252 ) 253 { 254 int i; 255 int bestpos; 256 SCIP_Real bestscore; 257 258 assert(ncuts > 0); 259 assert(cuts != NULL); 260 assert(scores != NULL); 261 262 bestscore = scores[0]; 263 bestpos = 0; 264 265 for( i = 1; i < ncuts; ++i ) 266 { 267 if( scores[i] > bestscore ) 268 { 269 bestpos = i; 270 bestscore = scores[i]; 271 } 272 } 273 274 SCIPswapPointers((void**) &cuts[bestpos], (void**) &cuts[0]); 275 SCIPswapReals(&scores[bestpos], &scores[0]); 276 } 277 278 /** filters the given array of cuts to enforce a maximum parallelism constraint 279 * w.r.t the given cut; moves filtered cuts to the end of the array and returns number of selected cuts */ 280 static 281 int filterWithDynamicParallelism( 282 SCIP* scip, /**< SCIP data structure */ 283 SCIP_ROW* bestcut, /**< cut to filter orthogonality with */ 284 SCIP_ROW** cuts, /**< array with cuts to perform selection algorithm */ 285 SCIP_Real* scores, /**< array with scores of cuts to perform selection algorithm */ 286 SCIP_Real mingain, /**< minimum gain enforced on the two-cut efficacy */ 287 SCIP_Real maxparall, /**< maximal parallelism for all cuts that are not good */ 288 int ncuts /**< number of cuts in given array */ 289 ) 290 { 291 int i; 292 SCIP_Bool filter; 293 SCIP_Real bestcutefficacy; 294 295 SCIPdebugMsg(scip, "\nfilterWithDynamicParallelism.\n\n"); 296 297 assert(bestcut != NULL); 298 assert(ncuts == 0 || cuts != NULL); 299 assert(ncuts == 0 || scores != NULL); 300 301 bestcutefficacy = SCIPgetCutEfficacy(scip, NULL, bestcut); 302 303 /*lint -e{850} i is modified in the body of the for loop */ 304 for( i = ncuts-1; i >= 0; --i ) 305 { 306 SCIP_Real thisparall; 307 SCIP_Real cosine; 308 SCIP_Real currentcutefficacy; 309 SCIP_Real minmaxparall; 310 311 currentcutefficacy = SCIPgetCutEfficacy(scip, NULL, cuts[i]); 312 313 if( SCIPisGE(scip, bestcutefficacy, currentcutefficacy)) 314 { 315 cosine = SCIProwGetParallelism(bestcut, cuts[i], 's'); 316 thisparall = cosine * bestcutefficacy / currentcutefficacy; 317 SCIPdebugMsg(scip, "Thisparall(%g) = cosine(%g) * (bestcutefficacy(%g)/ currentcutefficacy(%g))\n\n", thisparall, 318 cosine, bestcutefficacy, currentcutefficacy); 319 } 320 else 321 { 322 cosine = SCIProwGetParallelism(cuts[i], bestcut, 's'); 323 thisparall = cosine * currentcutefficacy / bestcutefficacy; 324 SCIPdebugMsg(scip, "Thisparall(%g) = cosine(%g) * (currentcutefficacy(%g) / bestcutefficacy(%g))\n\n", thisparall, 325 cosine, currentcutefficacy, bestcutefficacy); 326 } 327 328 /* compute the max-minimum angle for given the given cuts to enforce 329 * norm(d) >= (1+mingain)*eff1 for non-negative cosine angle */ 330 minmaxparall = MAX( (bestcutefficacy * bestcutefficacy 331 + currentcutefficacy * currentcutefficacy 332 - (1 + mingain) * bestcutefficacy * (1 + mingain) * bestcutefficacy * (1 - cosine * cosine)) 333 / (2 * bestcutefficacy * currentcutefficacy), 334 maxparall ); 335 filter = ( SCIPisGE(scip, thisparall, 1.0) || SCIPisGT(scip, cosine, minmaxparall) ); 336 337 SCIPdebugMsg(scip, "Filter = %u\n", filter); 338 339 if( filter ) 340 { 341 --ncuts; 342 SCIPswapPointers((void**) &cuts[i], (void**) &cuts[ncuts]); 343 SCIPswapReals(&scores[i], &scores[ncuts]); 344 } 345 } 346 347 return ncuts; 348 } 349 350 351 /* 352 * Callback methods of cut selector 353 */ 354 355 /** copy method for cut selector plugin (called when SCIP copies plugins) */ 356 static 357 SCIP_DECL_CUTSELCOPY(cutselCopyDynamic) 358 { /*lint --e{715}*/ 359 assert(scip != NULL); 360 assert(cutsel != NULL); 361 assert(strcmp(SCIPcutselGetName(cutsel), CUTSEL_NAME) == 0); 362 363 /* call inclusion method of cut selector */ 364 SCIP_CALL( SCIPincludeCutselDynamic(scip) ); 365 366 return SCIP_OKAY; 367 } 368 369 /** destructor of cut selector to free user data (called when SCIP is exiting) */ 370 /**! [SnippetCutselFreeDynamic] */ 371 static 372 SCIP_DECL_CUTSELFREE(cutselFreeDynamic) 373 { /*lint --e{715}*/ 374 SCIP_CUTSELDATA* cutseldata; 375 376 cutseldata = SCIPcutselGetData(cutsel); 377 378 SCIPfreeBlockMemory(scip, &cutseldata); 379 380 SCIPcutselSetData(cutsel, NULL); 381 382 return SCIP_OKAY; 383 } 384 /**! [SnippetCutselFreeDynamic] */ 385 386 /** initialization method of cut selector (called after problem was transformed) */ 387 static 388 SCIP_DECL_CUTSELINIT(cutselInitDynamic) 389 { /*lint --e{715}*/ 390 SCIP_CUTSELDATA* cutseldata; 391 392 cutseldata = SCIPcutselGetData(cutsel); 393 assert(cutseldata != NULL); 394 395 SCIP_CALL( SCIPcreateRandom(scip, &(cutseldata)->randnumgen, RANDSEED, TRUE) ); 396 397 return SCIP_OKAY; 398 } 399 400 /** deinitialization method of cut selector (called before transformed problem is freed) */ 401 static 402 SCIP_DECL_CUTSELEXIT(cutselExitDynamic) 403 { /*lint --e{715}*/ 404 SCIP_CUTSELDATA* cutseldata; 405 406 cutseldata = SCIPcutselGetData(cutsel); 407 assert(cutseldata != NULL); 408 assert(cutseldata->randnumgen != NULL); 409 410 SCIPfreeRandom(scip, &cutseldata->randnumgen); 411 412 return SCIP_OKAY; 413 } 414 415 /** cut selection method of cut selector */ 416 static 417 SCIP_DECL_CUTSELSELECT(cutselSelectDynamic) { /*lint --e{715}*/ 418 SCIP_CUTSELDATA *cutseldata; 419 420 assert(cutsel != NULL); 421 assert(result != NULL); 422 423 *result = SCIP_SUCCESS; 424 425 cutseldata = SCIPcutselGetData(cutsel); 426 assert(cutseldata != NULL); 427 if (cutseldata->maxdepth != -1 && cutseldata->maxdepth < SCIPgetDepth(scip)) 428 { 429 *result = SCIP_DIDNOTFIND; 430 return SCIP_OKAY; 431 } 432 433 SCIP_CALL( SCIPselectCutsDynamic( scip, cuts, forcedcuts, cutseldata->randnumgen, cutseldata->filtermode, 434 cutseldata->mingain, 1-cutseldata->minortho, cutseldata->dircutoffdistweight, cutseldata->efficacyweight, 435 cutseldata->objparalweight, cutseldata->intsupportweight, ncuts, nforcedcuts, 436 maxnselectedcuts, nselectedcuts) ); 437 438 return SCIP_OKAY; 439 } 440 441 442 /* 443 * cut selector specific interface methods 444 */ 445 446 /** creates the dynamic cut selector and includes it in SCIP */ 447 SCIP_RETCODE SCIPincludeCutselDynamic( 448 SCIP* scip /**< SCIP data structure */ 449 ) 450 { 451 SCIP_CUTSELDATA* cutseldata; 452 SCIP_CUTSEL* cutsel; 453 454 /* create dynamic cut selector data */ 455 SCIP_CALL( SCIPallocBlockMemory(scip, &cutseldata) ); 456 BMSclearMemory(cutseldata); 457 458 SCIP_CALL( SCIPincludeCutselBasic(scip, &cutsel, CUTSEL_NAME, CUTSEL_DESC, CUTSEL_PRIORITY, cutselSelectDynamic, 459 cutseldata) ); 460 461 assert(cutsel != NULL); 462 463 /* set non fundamental callbacks via setter functions */ 464 SCIP_CALL( SCIPsetCutselCopy(scip, cutsel, cutselCopyDynamic) ); 465 466 SCIP_CALL( SCIPsetCutselFree(scip, cutsel, cutselFreeDynamic) ); 467 SCIP_CALL( SCIPsetCutselInit(scip, cutsel, cutselInitDynamic) ); 468 SCIP_CALL( SCIPsetCutselExit(scip, cutsel, cutselExitDynamic) ); 469 470 /* add dynamic cut selector parameters */ 471 SCIP_CALL( SCIPaddRealParam(scip, 472 "cutselection/" CUTSEL_NAME "/efficacyweight", 473 "weight of efficacy in cut score calculation", 474 &cutseldata->efficacyweight, FALSE, 475 DEFAULT_EFFICACYWEIGHT, 0.0, SCIP_INVALID / 10.0, NULL, NULL) ); 476 477 SCIP_CALL( SCIPaddRealParam(scip, 478 "cutselection/" CUTSEL_NAME "/dircutoffdistweight", 479 "weight of directed cutoff distance in cut score calculation", 480 &cutseldata->dircutoffdistweight, FALSE, 481 DEFAULT_DIRCUTOFFDISTWEIGHT, 0.0, SCIP_INVALID / 10.0, NULL, NULL) ); 482 483 SCIP_CALL( SCIPaddRealParam(scip, 484 "cutselection/" CUTSEL_NAME "/objparalweight", 485 "weight of objective parallelism in cut score calculation", 486 &cutseldata->objparalweight, FALSE, 487 DEFAULT_OBJPARALWEIGHT, 0.0, SCIP_INVALID / 10.0, NULL, NULL) ); 488 489 SCIP_CALL( SCIPaddRealParam(scip, 490 "cutselection/" CUTSEL_NAME "/intsupportweight", 491 "weight of integral support in cut score calculation", 492 &cutseldata->intsupportweight, FALSE, 493 DEFAULT_INTSUPPORTWEIGHT, 0.0, SCIP_INVALID / 10.0, NULL, NULL) ); 494 495 SCIP_CALL( SCIPaddRealParam(scip, 496 "cutselection/" CUTSEL_NAME "/mingain", 497 "minimal efficacy gain for a cut to enter the LP", 498 &cutseldata->mingain, FALSE, 499 DEFAULT_MINGAIN, 0.0, 1.0, NULL, NULL) ); 500 501 SCIP_CALL( SCIPaddCharParam(scip, 502 "cutselection/" CUTSEL_NAME "/filtermode", 503 "filtering strategy during cut selection", 504 &cutseldata->filtermode, FALSE, 505 DEFAULT_FILTERMODE, "df", NULL, NULL) ); 506 507 SCIP_CALL( SCIPaddRealParam(scip, 508 "cutselection/" CUTSEL_NAME "/minortho", 509 "minimal orthogonality for a cut to enter the LP", 510 &cutseldata->minortho, FALSE, 511 DEFAULT_MINORTHO, 0.0, 1.0, NULL, NULL) ); 512 513 SCIP_CALL( SCIPaddIntParam(scip, 514 "cutselection/" CUTSEL_NAME "/maxdepth", 515 "maximum depth at which this cutselector is employed", 516 &cutseldata->maxdepth, FALSE, 517 DEFAULT_MAXDEPTH, -1, SCIP_MAXTREEDEPTH, NULL, NULL) ); 518 519 return SCIP_OKAY; 520 } 521 522 523 /** perform a cut selection algorithm for the given array of cuts 524 * 525 * This is the selection method of the dynamic cut selector which implements 526 * the dynamic orthognality filtering based on the ratio of efficacies. 527 * The input cuts array gets resorted s.t the selected cuts come first and the remaining 528 * ones are the end. 529 */ 530 SCIP_RETCODE SCIPselectCutsDynamic( 531 SCIP* scip, /**< SCIP data structure */ 532 SCIP_ROW** cuts, /**< array with cuts to perform selection algorithm */ 533 SCIP_ROW** forcedcuts, /**< array with forced cuts */ 534 SCIP_RANDNUMGEN* randnumgen, /**< random number generator for tie-breaking, or NULL */ 535 char filtermode, /**< filtering strategy during cut selection ( 536 * 'd'ynamic- and 'f'ull dynamic parallelism) */ 537 SCIP_Real mingain, /**< minimum efficacy gain in percentage to filter cuts */ 538 SCIP_Real maxparall, /**< maximal parallelism for all cuts that are not good */ 539 SCIP_Real dircutoffdistweight,/**< weight of directed cutoff distance in cut score calculation */ 540 SCIP_Real efficacyweight, /**< weight of efficacy in cut score calculation */ 541 SCIP_Real objparalweight, /**< weight of objective parallelism in cut score calculation */ 542 SCIP_Real intsupportweight, /**< weight of integral support in cut score calculation */ 543 int ncuts, /**< number of cuts in cuts array */ 544 int nforcedcuts, /**< number of forced cuts */ 545 int maxselectedcuts, /**< maximal number of cuts from cuts array to select */ 546 int* nselectedcuts /**< pointer to return number of selected cuts from cuts array */ 547 ) 548 { 549 SCIP_ROW* selectedcut; 550 SCIP_Real* scores; 551 SCIP_Real* forcedscores; 552 SCIP_Real* scoresptr; 553 int ngoodforcedcuts; 554 int i; 555 556 assert(cuts != NULL && ncuts > 0); 557 assert(forcedcuts != NULL || nforcedcuts == 0); 558 assert(nselectedcuts != NULL); 559 560 *nselectedcuts = 0; 561 ngoodforcedcuts = 0; 562 563 SCIP_CALL( SCIPallocBufferArray(scip, &scores, ncuts) ); 564 565 /* compute scores of cuts and max score of cuts and forced cuts (used to define goodscore) */ 566 scoring(scip, cuts, randnumgen, dircutoffdistweight, efficacyweight, objparalweight, intsupportweight, &ncuts, 567 scores); 568 scoresptr = scores; 569 570 SCIPdebugMsg(scip, "nforcedcuts = %i.\n", nforcedcuts); 571 572 /* perform cut selection algorithm for the cuts */ 573 574 /* forced cuts are going to be selected so use them to filter cuts */ 575 for( i = 0; i < nforcedcuts && ncuts > 0; ++i ) 576 ncuts = filterWithDynamicParallelism(scip, forcedcuts[i], cuts, scores, mingain, maxparall, ncuts); 577 578 /* if all cuts are already filtered, we can stop */ 579 if( ncuts <= 0 ) 580 goto TERMINATE; 581 582 /* if the maximal number of cuts was selected, we can stop here */ 583 if( *nselectedcuts == maxselectedcuts ) 584 goto TERMINATE; 585 586 if( filtermode == 'f' && nforcedcuts > 0 ) 587 { 588 SCIP_CALL( SCIPallocBufferArray(scip, &forcedscores, nforcedcuts) ); 589 ngoodforcedcuts = nforcedcuts; 590 scoring(scip, forcedcuts, randnumgen, dircutoffdistweight, efficacyweight, objparalweight, intsupportweight, 591 &ngoodforcedcuts, forcedscores); 592 593 if( ngoodforcedcuts != 0 ) 594 { 595 selectBestCut(forcedcuts, forcedscores, ngoodforcedcuts); 596 SCIPfreeBufferArray(scip, &forcedscores); 597 SCIPdebugMsg(scip, "best forced cut: %s.\n", SCIProwGetName(forcedcuts[0])); 598 599 for( i = 0; i < ncuts; i++ ) 600 { 601 SCIP_CALL( computeProjectionScore(scip, forcedcuts[0], cuts[i], &scores[i]) ); 602 SCIPdebugMsg(scip, "scores[%i] = %g\n", i, scores[i]); 603 } 604 } 605 } 606 607 if( ngoodforcedcuts == 0 ) 608 { 609 assert(filtermode == 'd' || ngoodforcedcuts == 0); 610 selectBestCut(cuts, scores, ncuts); 611 612 selectedcut = cuts[0]; 613 SCIPdebugMsg(scip, "selectedcut = %s.\n", SCIProwGetName(selectedcut)); 614 615 ++(*nselectedcuts); 616 617 /* if the maximal number of cuts was selected, we can stop here */ 618 if( *nselectedcuts == maxselectedcuts ) 619 goto TERMINATE; 620 621 /* move the pointers to the next position and filter the remaining cuts to enforce the dynamic parallelism constraint */ 622 ++cuts; 623 ++scores; 624 --ncuts; 625 626 ncuts = filterWithDynamicParallelism(scip, selectedcut, cuts, scores, mingain, maxparall, ncuts); 627 628 if( filtermode == 'f' ) 629 { 630 for( i = 0; i < ncuts; i++ ) 631 { 632 SCIP_CALL( computeProjectionScore(scip, selectedcut, cuts[i], &scores[i]) ); 633 } 634 } 635 } 636 637 SCIPdebugMsg(scip, "ncuts after forced cut filter = %i.\n", ncuts); 638 639 /* now greedily select the remaining cuts */ 640 while( ncuts > 0 ) 641 { 642 selectBestCut(cuts, scores, ncuts); 643 selectedcut = cuts[0]; 644 SCIPdebugMsg(scip, "selectedcut = %s.\n", SCIProwGetName(selectedcut)); 645 646 ++(*nselectedcuts); 647 648 /* if the maximal number of cuts was selected, we can stop here */ 649 if( *nselectedcuts == maxselectedcuts ) 650 goto TERMINATE; 651 652 /* move the pointers to the next position and filter the remaining cuts to enforce the dynamic parallelism constraint */ 653 ++cuts; 654 ++scores; 655 --ncuts; 656 657 ncuts = filterWithDynamicParallelism(scip, selectedcut, cuts, scores, mingain, maxparall, ncuts); 658 659 if( filtermode == 'f' ) 660 { 661 for( i = 0; i < ncuts; i++ ) 662 { 663 SCIP_CALL( computeProjectionScore(scip, selectedcut, cuts[i], &scores[i]) ); 664 SCIPdebugMsg(scip, "nonforcedscores[%i] = %g\n", i, scores[i]); 665 } 666 } 667 } 668 669 TERMINATE: 670 SCIPfreeBufferArray(scip, &scoresptr); 671 return SCIP_OKAY; 672 } 673