1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB) */ 7 /* */ 8 /* Licensed under the Apache License, Version 2.0 (the "License"); */ 9 /* you may not use this file except in compliance with the License. */ 10 /* You may obtain a copy of the License at */ 11 /* */ 12 /* http://www.apache.org/licenses/LICENSE-2.0 */ 13 /* */ 14 /* Unless required by applicable law or agreed to in writing, software */ 15 /* distributed under the License is distributed on an "AS IS" BASIS, */ 16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ 17 /* See the License for the specific language governing permissions and */ 18 /* limitations under the License. */ 19 /* */ 20 /* You should have received a copy of the Apache-2.0 license */ 21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */ 22 /* */ 23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 24 25 /**@file cutsel_hybrid.c 26 * @ingroup DEFPLUGINS_CUTSEL 27 * @brief hybrid cut selector 28 * @author Leona Gottwald 29 * @author Felipe Serrano 30 * @author Mark Turner 31 */ 32 33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 34 35 #include <assert.h> 36 37 #include "scip/scip_cutsel.h" 38 #include "scip/scip_cut.h" 39 #include "scip/scip_lp.h" 40 #include "scip/scip_randnumgen.h" 41 #include "scip/cutsel_hybrid.h" 42 43 44 #define CUTSEL_NAME "hybrid" 45 #define CUTSEL_DESC "weighted sum of efficacy, dircutoffdist, objparal, and intsupport" 46 #define CUTSEL_PRIORITY 8000 47 48 #define RANDSEED 0x5EED 49 #define GOODSCORE 0.9 50 #define BADSCORE 0.0 51 52 #define DEFAULT_EFFICACYWEIGHT 1.0 /**< weight of efficacy in score calculation */ 53 #define DEFAULT_DIRCUTOFFDISTWEIGHT 0.0 /**< weight of directed cutoff distance in score calculation */ 54 #define DEFAULT_OBJPARALWEIGHT 0.1 /**< weight of objective parallelism in score calculation */ 55 #define DEFAULT_INTSUPPORTWEIGHT 0.1 /**< weight of integral support in cut score calculation */ 56 #define DEFAULT_MINORTHO 0.90 /**< minimal orthogonality for a cut to enter the LP */ 57 #define DEFAULT_MINORTHOROOT 0.90 /**< minimal orthogonality for a cut to enter the LP in the root node */ 58 59 /* 60 * Data structures 61 */ 62 63 /** cut selector data */ 64 struct SCIP_CutselData 65 { 66 SCIP_RANDNUMGEN* randnumgen; /**< random generator for tiebreaking */ 67 SCIP_Real goodscore; /**< threshold for score of cut relative to best score to be considered good, 68 * so that less strict filtering is applied */ 69 SCIP_Real badscore; /**< threshold for score of cut relative to best score to be discarded */ 70 SCIP_Real objparalweight; /**< weight of objective parallelism in cut score calculation */ 71 SCIP_Real efficacyweight; /**< weight of efficacy in cut score calculation */ 72 SCIP_Real dircutoffdistweight;/**< weight of directed cutoff distance in cut score calculation */ 73 SCIP_Real intsupportweight; /**< weight of integral support in cut score calculation */ 74 SCIP_Real minortho; /**< minimal orthogonality for a cut to enter the LP */ 75 SCIP_Real minorthoroot; /**< minimal orthogonality for a cut to enter the LP in the root node */ 76 }; 77 78 79 /* 80 * Local methods 81 */ 82 83 /** returns the maximum score of cuts; if scores is not NULL, then stores the individual score of each cut in scores */ 84 static 85 SCIP_Real scoring( 86 SCIP* scip, /**< SCIP data structure */ 87 SCIP_ROW** cuts, /**< array with cuts to score */ 88 SCIP_RANDNUMGEN* randnumgen, /**< random number generator for tie-breaking, or NULL */ 89 SCIP_Real dircutoffdistweight,/**< weight of directed cutoff distance in cut score calculation */ 90 SCIP_Real efficacyweight, /**< weight of efficacy in cut score calculation */ 91 SCIP_Real objparalweight, /**< weight of objective parallelism in cut score calculation */ 92 SCIP_Real intsupportweight, /**< weight of integral support in cut score calculation */ 93 int ncuts, /**< number of cuts in cuts array */ 94 SCIP_Real* scores /**< array to store the score of cuts or NULL */ 95 ) 96 { 97 SCIP_Real maxscore = 0.0; 98 SCIP_SOL* sol; 99 int i; 100 101 sol = SCIPgetBestSol(scip); 102 103 /* if there is an incumbent and the factor is not 0.0, compute directed cutoff distances for the incumbent */ 104 if( sol != NULL && dircutoffdistweight > 0.0 ) 105 { 106 for( i = 0; i < ncuts; ++i ) 107 { 108 SCIP_Real score; 109 SCIP_Real objparallelism; 110 SCIP_Real intsupport; 111 SCIP_Real efficacy; 112 113 if( intsupportweight > 0.0 ) 114 intsupport = intsupportweight * SCIPgetRowNumIntCols(scip, cuts[i]) / (SCIP_Real) SCIProwGetNNonz(cuts[i]); 115 else 116 intsupport = 0.0; 117 118 if( objparalweight > 0.0 ) 119 objparallelism = objparalweight * SCIPgetRowObjParallelism(scip, cuts[i]); 120 else 121 objparallelism = 0.0; 122 123 efficacy = SCIPgetCutEfficacy(scip, NULL, cuts[i]); 124 125 if( SCIProwIsLocal(cuts[i]) ) 126 { 127 score = dircutoffdistweight * efficacy; 128 } 129 else 130 { 131 score = SCIPgetCutLPSolCutoffDistance(scip, sol, cuts[i]); 132 score = dircutoffdistweight * MAX(score, efficacy); 133 } 134 135 efficacy *= efficacyweight; 136 score += objparallelism + intsupport + efficacy; 137 138 /* add small term to prefer global pool cuts */ 139 if( SCIProwIsInGlobalCutpool(cuts[i]) ) 140 score += 1e-4; 141 142 if( randnumgen != NULL ) 143 { 144 score += SCIPrandomGetReal(randnumgen, 0.0, 1e-6); 145 } 146 147 maxscore = MAX(maxscore, score); 148 149 if( scores != NULL ) 150 scores[i] = score; 151 } 152 } 153 else 154 { 155 /* in case there is no solution add the directed cutoff distance weight to the efficacy weight 156 * since the efficacy underestimates the directed cuttoff distance 157 */ 158 efficacyweight += dircutoffdistweight; 159 for( i = 0; i < ncuts; ++i ) 160 { 161 SCIP_Real score; 162 SCIP_Real objparallelism; 163 SCIP_Real intsupport; 164 SCIP_Real efficacy; 165 166 if( intsupportweight > 0.0 ) 167 intsupport = intsupportweight * SCIPgetRowNumIntCols(scip, cuts[i]) / (SCIP_Real) SCIProwGetNNonz(cuts[i]); 168 else 169 intsupport = 0.0; 170 171 if( objparalweight > 0.0 ) 172 objparallelism = objparalweight * SCIPgetRowObjParallelism(scip, cuts[i]); 173 else 174 objparallelism = 0.0; 175 176 efficacy = efficacyweight > 0.0 ? efficacyweight * SCIPgetCutEfficacy(scip, NULL, cuts[i]) : 0.0; 177 178 score = objparallelism + intsupport + efficacy; 179 180 /* add small term to prefer global pool cuts */ 181 if( SCIProwIsInGlobalCutpool(cuts[i]) ) 182 score += 1e-4; 183 184 if( randnumgen != NULL ) 185 { 186 score += SCIPrandomGetReal(randnumgen, 0.0, 1e-6); 187 } 188 189 maxscore = MAX(maxscore, score); 190 191 if( scores != NULL ) 192 scores[i] = score; 193 } 194 } 195 return maxscore; 196 } 197 198 199 /** move the cut with the highest score to the first position in the array; there must be at least one cut */ 200 static 201 void selectBestCut( 202 SCIP_ROW** cuts, /**< array with cuts to perform selection algorithm */ 203 SCIP_Real* scores, /**< array with scores of cuts to perform selection algorithm */ 204 int ncuts /**< number of cuts in given array */ 205 ) 206 { 207 int i; 208 int bestpos; 209 SCIP_Real bestscore; 210 211 assert(ncuts > 0); 212 assert(cuts != NULL); 213 assert(scores != NULL); 214 215 bestscore = scores[0]; 216 bestpos = 0; 217 218 for( i = 1; i < ncuts; ++i ) 219 { 220 if( scores[i] > bestscore ) 221 { 222 bestpos = i; 223 bestscore = scores[i]; 224 } 225 } 226 227 SCIPswapPointers((void**) &cuts[bestpos], (void**) &cuts[0]); 228 SCIPswapReals(&scores[bestpos], &scores[0]); 229 } 230 231 /** filters the given array of cuts to enforce a maximum parallelism constraint 232 * w.r.t the given cut; moves filtered cuts to the end of the array and returns number of selected cuts */ 233 static 234 int filterWithParallelism( 235 SCIP_ROW* cut, /**< cut to filter orthogonality with */ 236 SCIP_ROW** cuts, /**< array with cuts to perform selection algorithm */ 237 SCIP_Real* scores, /**< array with scores of cuts to perform selection algorithm */ 238 int ncuts, /**< number of cuts in given array */ 239 SCIP_Real goodscore, /**< threshold for the score to be considered a good cut */ 240 SCIP_Real goodmaxparall, /**< maximal parallelism for good cuts */ 241 SCIP_Real maxparall /**< maximal parallelism for all cuts that are not good */ 242 ) 243 { 244 int i; 245 246 assert( cut != NULL ); 247 assert( ncuts == 0 || cuts != NULL ); 248 assert( ncuts == 0 || scores != NULL ); 249 250 for( i = ncuts - 1; i >= 0; --i ) 251 { 252 SCIP_Real thisparall; 253 SCIP_Real thismaxparall; 254 255 thisparall = SCIProwGetParallelism(cut, cuts[i], 'e'); 256 thismaxparall = scores[i] >= goodscore ? goodmaxparall : maxparall; 257 258 if( thisparall > thismaxparall ) 259 { 260 --ncuts; 261 SCIPswapPointers((void**) &cuts[i], (void**) &cuts[ncuts]); 262 SCIPswapReals(&scores[i], &scores[ncuts]); 263 } 264 } 265 266 return ncuts; 267 } 268 269 270 /* 271 * Callback methods of cut selector 272 */ 273 274 275 /** copy method for cut selector plugin (called when SCIP copies plugins) */ 276 static 277 SCIP_DECL_CUTSELCOPY(cutselCopyHybrid) 278 { /*lint --e{715}*/ 279 assert(scip != NULL); 280 assert(cutsel != NULL); 281 assert(strcmp(SCIPcutselGetName(cutsel), CUTSEL_NAME) == 0); 282 283 /* call inclusion method of cut selector */ 284 SCIP_CALL( SCIPincludeCutselHybrid(scip) ); 285 286 return SCIP_OKAY; 287 } 288 289 /** destructor of cut selector to free user data (called when SCIP is exiting) */ 290 /**! [SnippetCutselFreeHybrid] */ 291 static 292 SCIP_DECL_CUTSELFREE(cutselFreeHybrid) 293 { /*lint --e{715}*/ 294 SCIP_CUTSELDATA* cutseldata; 295 296 cutseldata = SCIPcutselGetData(cutsel); 297 298 SCIPfreeBlockMemory(scip, &cutseldata); 299 300 SCIPcutselSetData(cutsel, NULL); 301 302 return SCIP_OKAY; 303 } 304 /**! [SnippetCutselFreeHybrid] */ 305 306 /** initialization method of cut selector (called after problem was transformed) */ 307 static 308 SCIP_DECL_CUTSELINIT(cutselInitHybrid) 309 { /*lint --e{715}*/ 310 SCIP_CUTSELDATA* cutseldata; 311 312 cutseldata = SCIPcutselGetData(cutsel); 313 assert(cutseldata != NULL); 314 315 SCIP_CALL( SCIPcreateRandom(scip, &(cutseldata)->randnumgen, RANDSEED, TRUE) ); 316 317 return SCIP_OKAY; 318 } 319 320 /** deinitialization method of cut selector (called before transformed problem is freed) */ 321 static 322 SCIP_DECL_CUTSELEXIT(cutselExitHybrid) 323 { /*lint --e{715}*/ 324 SCIP_CUTSELDATA* cutseldata; 325 326 cutseldata = SCIPcutselGetData(cutsel); 327 assert(cutseldata != NULL); 328 assert(cutseldata->randnumgen != NULL); 329 330 SCIPfreeRandom(scip, &cutseldata->randnumgen); 331 332 return SCIP_OKAY; 333 } 334 335 /** cut selection method of cut selector */ 336 static 337 SCIP_DECL_CUTSELSELECT(cutselSelectHybrid) 338 { /*lint --e{715}*/ 339 SCIP_CUTSELDATA* cutseldata; 340 SCIP_Real goodmaxparall; 341 SCIP_Real maxparall; 342 343 assert(cutsel != NULL); 344 assert(result != NULL); 345 346 *result = SCIP_SUCCESS; 347 348 cutseldata = SCIPcutselGetData(cutsel); 349 assert(cutseldata != NULL); 350 351 SCIP_Real minortho = cutseldata->minortho; 352 if( root ) 353 minortho = cutseldata->minorthoroot; 354 355 maxparall = 1.0 - minortho; 356 goodmaxparall = MAX(0.5, 1.0 - minortho); 357 358 SCIP_CALL( SCIPselectCutsHybrid(scip, cuts, forcedcuts, cutseldata->randnumgen, cutseldata->goodscore, cutseldata->badscore, 359 goodmaxparall, maxparall, cutseldata->dircutoffdistweight, cutseldata->efficacyweight, 360 cutseldata->objparalweight, cutseldata->intsupportweight, ncuts, nforcedcuts, maxnselectedcuts, nselectedcuts) ); 361 362 return SCIP_OKAY; 363 } 364 365 366 /* 367 * cut selector specific interface methods 368 */ 369 370 /** creates the hybrid cut selector and includes it in SCIP */ 371 SCIP_RETCODE SCIPincludeCutselHybrid( 372 SCIP* scip /**< SCIP data structure */ 373 ) 374 { 375 SCIP_CUTSELDATA* cutseldata; 376 SCIP_CUTSEL* cutsel; 377 378 /* create hybrid cut selector data */ 379 SCIP_CALL( SCIPallocBlockMemory(scip, &cutseldata) ); 380 BMSclearMemory(cutseldata); 381 cutseldata->goodscore = GOODSCORE; 382 cutseldata->badscore = BADSCORE; 383 384 SCIP_CALL( SCIPincludeCutselBasic(scip, &cutsel, CUTSEL_NAME, CUTSEL_DESC, CUTSEL_PRIORITY, cutselSelectHybrid, 385 cutseldata) ); 386 387 assert(cutsel != NULL); 388 389 /* set non fundamental callbacks via setter functions */ 390 SCIP_CALL( SCIPsetCutselCopy(scip, cutsel, cutselCopyHybrid) ); 391 392 SCIP_CALL( SCIPsetCutselFree(scip, cutsel, cutselFreeHybrid) ); 393 SCIP_CALL( SCIPsetCutselInit(scip, cutsel, cutselInitHybrid) ); 394 SCIP_CALL( SCIPsetCutselExit(scip, cutsel, cutselExitHybrid) ); 395 396 /* add hybrid cut selector parameters */ 397 SCIP_CALL( SCIPaddRealParam(scip, 398 "cutselection/" CUTSEL_NAME "/efficacyweight", 399 "weight of efficacy in cut score calculation", 400 &cutseldata->efficacyweight, FALSE, DEFAULT_EFFICACYWEIGHT, 0.0, SCIP_INVALID/10.0, NULL, NULL) ); 401 402 SCIP_CALL( SCIPaddRealParam(scip, 403 "cutselection/" CUTSEL_NAME "/dircutoffdistweight", 404 "weight of directed cutoff distance in cut score calculation", 405 &cutseldata->dircutoffdistweight, FALSE, DEFAULT_DIRCUTOFFDISTWEIGHT, 0.0, SCIP_INVALID/10.0, NULL, NULL) ); 406 407 SCIP_CALL( SCIPaddRealParam(scip, 408 "cutselection/" CUTSEL_NAME "/objparalweight", 409 "weight of objective parallelism in cut score calculation", 410 &cutseldata->objparalweight, FALSE, DEFAULT_OBJPARALWEIGHT, 0.0, SCIP_INVALID/10.0, NULL, NULL) ); 411 412 SCIP_CALL( SCIPaddRealParam(scip, 413 "cutselection/" CUTSEL_NAME "/intsupportweight", 414 "weight of integral support in cut score calculation", 415 &cutseldata->intsupportweight, FALSE, DEFAULT_INTSUPPORTWEIGHT, 0.0, SCIP_INVALID/10.0, NULL, NULL) ); 416 417 SCIP_CALL( SCIPaddRealParam(scip, 418 "cutselection/" CUTSEL_NAME "/minortho", 419 "minimal orthogonality for a cut to enter the LP", 420 &cutseldata->minortho, FALSE, DEFAULT_MINORTHO, 0.0, 1.0, NULL, NULL) ); 421 422 SCIP_CALL( SCIPaddRealParam(scip, 423 "cutselection/" CUTSEL_NAME "/minorthoroot", 424 "minimal orthogonality for a cut to enter the LP in the root node", 425 &cutseldata->minorthoroot, FALSE, DEFAULT_MINORTHOROOT, 0.0, 1.0, NULL, NULL) ); 426 427 return SCIP_OKAY; 428 } 429 430 431 /** perform a cut selection algorithm for the given array of cuts 432 * 433 * This is the selection method of the hybrid cut selector which uses a weighted sum of the 434 * efficacy, parallelism, directed cutoff distance, and the integral support. 435 * The input cuts array gets resorted s.t the selected cuts come first and the remaining 436 * ones are the end. 437 */ 438 SCIP_RETCODE SCIPselectCutsHybrid( 439 SCIP* scip, /**< SCIP data structure */ 440 SCIP_ROW** cuts, /**< array with cuts to perform selection algorithm */ 441 SCIP_ROW** forcedcuts, /**< array with forced cuts */ 442 SCIP_RANDNUMGEN* randnumgen, /**< random number generator for tie-breaking, or NULL */ 443 SCIP_Real goodscorefac, /**< factor of best score among the given cuts to consider a cut good 444 * and filter with less strict settings of the maximum parallelism */ 445 SCIP_Real badscorefac, /**< factor of best score among the given cuts to consider a cut bad 446 * and discard it regardless of its parallelism to other cuts */ 447 SCIP_Real goodmaxparall, /**< maximum parallelism for good cuts */ 448 SCIP_Real maxparall, /**< maximum parallelism for non-good cuts */ 449 SCIP_Real dircutoffdistweight,/**< weight of directed cutoff distance in cut score calculation */ 450 SCIP_Real efficacyweight, /**< weight of efficacy in cut score calculation */ 451 SCIP_Real objparalweight, /**< weight of objective parallelism in cut score calculation */ 452 SCIP_Real intsupportweight, /**< weight of integral support in cut score calculation */ 453 int ncuts, /**< number of cuts in cuts array */ 454 int nforcedcuts, /**< number of forced cuts */ 455 int maxselectedcuts, /**< maximal number of cuts from cuts array to select */ 456 int* nselectedcuts /**< pointer to return number of selected cuts from cuts array */ 457 ) 458 { 459 SCIP_Real* scores; 460 SCIP_Real* scoresptr; 461 SCIP_Real maxforcedscores; 462 SCIP_Real maxnonforcedscores; 463 SCIP_Real goodscore; 464 SCIP_Real badscore; 465 int i; 466 467 assert(cuts != NULL && ncuts > 0); 468 assert(forcedcuts != NULL || nforcedcuts == 0); 469 assert(nselectedcuts != NULL); 470 471 *nselectedcuts = 0; 472 473 SCIP_CALL( SCIPallocBufferArray(scip, &scores, ncuts) ); 474 475 /* compute scores of cuts and max score of cuts and forced cuts (used to define goodscore) */ 476 maxforcedscores = scoring(scip, forcedcuts, randnumgen, dircutoffdistweight, efficacyweight, objparalweight, intsupportweight, nforcedcuts, NULL); 477 maxnonforcedscores = scoring(scip, cuts, randnumgen, dircutoffdistweight, efficacyweight, objparalweight, intsupportweight, ncuts, scores); 478 479 goodscore = MAX(maxforcedscores, maxnonforcedscores); 480 481 /* compute values for filtering cuts */ 482 badscore = goodscore * badscorefac; 483 goodscore *= goodscorefac; 484 485 /* perform cut selection algorithm for the cuts */ 486 487 /* forced cuts are going to be selected so use them to filter cuts */ 488 for( i = 0; i < nforcedcuts && ncuts > 0; ++i ) 489 { 490 ncuts = filterWithParallelism(forcedcuts[i], cuts, scores, ncuts, goodscore, goodmaxparall, maxparall); 491 } 492 493 /* now greedily select the remaining cuts */ 494 scoresptr = scores; 495 while( ncuts > 0 ) 496 { 497 SCIP_ROW* selectedcut; 498 499 selectBestCut(cuts, scores, ncuts); 500 selectedcut = cuts[0]; 501 502 /* if the best cut of the remaining cuts is considered bad, we discard it and all remaining cuts */ 503 if( scores[0] < badscore ) 504 break; 505 506 ++(*nselectedcuts); 507 508 /* if the maximal number of cuts was selected, we can stop here */ 509 if( *nselectedcuts == maxselectedcuts ) 510 break; 511 512 /* move the pointers to the next position and filter the remaining cuts to enforce the maximum parallelism constraint */ 513 ++cuts; 514 ++scores; 515 --ncuts; 516 517 ncuts = filterWithParallelism(selectedcut, cuts, scores, ncuts, goodscore, goodmaxparall, maxparall); 518 } 519 520 SCIPfreeBufferArray(scip, &scoresptr); 521 522 return SCIP_OKAY; 523 } 524