1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright 2002-2022 Zuse Institute Berlin */ 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 heur_indicatordiving.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief LP diving heuristic that fixes indicator variables controlling semicontinuous variables 28 * @author Katrin Halbig 29 * @author Alexander Hoen 30 * 31 * A diving heuristic iteratively rounds some fractional variables or variables determined by constraint handlers, 32 * and resolves the LP relaxation. Thereby simulating a depth-first-search in the tree. 33 * 34 * Indicatordiving focuses on indicator variables, which control semicontinuous variables. 35 * If the semicontinuous variable is unbounded, the indicator constraint is not part of the LP and, 36 * therefore, the indicator variable is not set to an useful value in the LP solution. 37 * 38 * For these indicator variables the score depends on the LP value and the bounds of the corresponding semicontinuous variable. 39 * If parameter usevarbounds=TRUE, also varbound constraints modeling semicontinuous variables are considered. 40 * For all other variables the Farkas score (scaled) is returned. 41 */ 42 43 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 44 45 #include <assert.h> 46 47 #include "scip/cons_indicator.h" 48 #include "scip/cons_varbound.h" 49 #include "scip/heur_indicatordiving.h" 50 #include "scip/heuristics.h" 51 #include "scip/pub_cons.h" 52 #include "scip/pub_heur.h" 53 #include "scip/pub_message.h" 54 #include "scip/pub_misc.h" 55 #include "scip/pub_var.h" 56 #include "scip/scip_cons.h" 57 #include "scip/scip_heur.h" 58 #include "scip/scip_mem.h" 59 #include "scip/scip_numerics.h" 60 #include "scip/scip_param.h" 61 #include "scip/scip_probing.h" 62 #include "scip/scip_sol.h" 63 #include "scip/scip_tree.h" 64 #include "scip/scip_prob.h" 65 #include "scip/scip_message.h" 66 67 #define HEUR_NAME "indicatordiving" 68 #define HEUR_DESC "LP diving heuristic that fixes indicator variables controlling semicontinuous variables" 69 #define HEUR_DISPCHAR 'I' 70 #define HEUR_PRIORITY -150000 71 #define HEUR_FREQ 0 72 #define HEUR_FREQOFS 0 73 #define HEUR_MAXDEPTH -1 74 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE 75 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */ 76 #define DIVESET_DIVETYPES SCIP_DIVETYPE_INTEGRALITY /**< bit mask that represents all supported dive types */ 77 #define DIVESET_ISPUBLIC FALSE /**< is this dive set publicly available (ie., can be used by other primal heuristics?) */ 78 79 80 /* 81 * Default parameter settings 82 */ 83 84 #define DEFAULT_MINRELDEPTH 0.0 /**< minimal relative depth to start diving */ 85 #define DEFAULT_MAXRELDEPTH 1.0 /**< maximal relative depth to start diving */ 86 #define DEFAULT_MAXLPITERQUOT 0.05 /**< maximal fraction of diving LP iterations compared to node LP iterations */ 87 #define DEFAULT_MAXLPITEROFS 1000 /**< additional number of allowed LP iterations */ 88 #define DEFAULT_MAXDIVEUBQUOT 0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) 89 * where diving is performed (0.0: no limit) */ 90 #define DEFAULT_MAXDIVEAVGQUOT 0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) 91 * where diving is performed (0.0: no limit) */ 92 #define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */ 93 #define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */ 94 #define DEFAULT_BACKTRACK TRUE /**< use one level of backtracking if infeasibility is encountered? */ 95 #define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15 /**< percentage of immediate domain changes during probing to trigger LP resolve */ 96 #define DEFAULT_LPSOLVEFREQ 30 /**< LP solve frequency for diving heuristics */ 97 #define DEFAULT_ONLYLPBRANCHCANDS FALSE /**< should only LP branching candidates be considered instead of the slower but 98 * more general constraint handler diving variable selection? */ 99 #define DEFAULT_RANDSEED 11 /**< initial seed for random number generation */ 100 101 /* 102 * Heuristic specific parameters 103 */ 104 #define DEFAULT_ROUNDINGFRAC 0.5 /**< default setting for parameter roundingfrac */ 105 #define DEFAULT_ROUNDINGMODE 0 /**< default setting for parameter roundingmode */ 106 #define DEFAULT_SEMICONTSCOREMODE 0 /**< default setting for parameter semicontscoremode */ 107 #define DEFAULT_USEVARBOUNDS TRUE /**< default setting for parameter usevarbounds */ 108 #define DEFAULT_RUNWITHOUTSCINDS FALSE /**< default setting for parameter runwithoutscinds */ 109 110 enum IndicatorDivingRoundingMode 111 { 112 ROUNDING_CONSERVATIVE = 0, 113 ROUNDING_AGGRESSIVE = 1 114 }; 115 typedef enum IndicatorDivingRoundingMode INDICATORDIVINGROUNDINGMODE; 116 117 /** data structure to store information of a semicontinuous variable 118 * 119 * For a variable x (not stored in the struct), this stores the data of nbnds implications 120 * bvars[i] = 0 -> x = vals[i] 121 * bvars[i] = 1 -> lbs[i] <= x <= ubs[i] 122 * where bvars[i] are binary variables. 123 */ 124 struct SCVarData 125 { 126 SCIP_Real* vals0; /**< values of the variable when the corresponding bvars[i] = 0 */ 127 SCIP_Real* lbs1; /**< global lower bounds of the variable when the corresponding bvars[i] = 1 */ 128 SCIP_Real* ubs1; /**< global upper bounds of the variable when the corresponding bvars[i] = 1 */ 129 SCIP_VAR** bvars; /**< the binary variables on which the variable domain depends */ 130 int nbnds; /**< number of suitable on/off bounds the var has */ 131 int bndssize; /**< size of the arrays */ 132 }; 133 typedef struct SCVarData SCVARDATA; 134 135 136 /** locally defined heuristic data */ 137 struct SCIP_HeurData 138 { 139 SCIP_SOL* sol; /**< working solution */ 140 SCIP_CONSHDLR* indicatorconshdlr; /**< indicator constraint handler */ 141 SCIP_CONSHDLR* varboundconshdlr; /**< varbound constraint handler */ 142 SCIP_HASHMAP* scvars; /**< hashmap to store semicontinuous variables */ 143 SCIP_HASHMAP* indicatormap; /**< hashmap to store indicator constraints of binary variables */ 144 SCIP_HASHMAP* varboundmap; /**< hashmap to store varbound constraints of binary variables */ 145 SCIP_Real roundingfrac; /**< in violation case all fractional below this value are fixed to constant */ 146 int roundingmode; /**< decides which roundingmode is selected (0: conservative (default), 1: aggressive) */ 147 int semicontscoremode; /**< which values of semi-continuous variables should get a high score? (0: low (default), 1: middle, 2: high) */ 148 SCIP_Bool usevarbounds; /**< should varbound constraints be considered? */ 149 SCIP_Bool runwithoutscinds; /**< should heur run if there are no indicator constraints modeling semicont. vars? */ 150 SCIP_Bool gotoindconss; /**< can we skip the candidate var until indicator conss handler determines the candidate var? */ 151 SCIP_Bool containsviolindconss;/**< contains current solution violated indicator constraints? (only unbounded) */ 152 SCIP_Bool newnode; /**< are we at a new probing node? */ 153 int probingdepth; /**< current probing depth */ 154 }; 155 156 /* 157 * Local methods 158 */ 159 160 /** checks if constraint is violated but not fixed, i.e., it will be a diving candidate variable */ 161 static 162 SCIP_Bool isViolatedAndNotFixed( 163 SCIP* scip, /**< SCIP data structure */ 164 SCIP_SOL* sol, /**< pointer to solution */ 165 SCIP_CONS* cons /**< pointer to indicator constraint */ 166 ) 167 { 168 SCIP_VAR* binvar; 169 SCIP_Real solval; 170 171 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), "indicator") == 0); 172 173 if( !SCIPisViolatedIndicator(scip, cons, sol) ) 174 return FALSE; 175 176 binvar = SCIPgetBinaryVarIndicator(cons); 177 solval = SCIPgetSolVal(scip, sol, binvar); 178 179 return (SCIPisFeasIntegral(scip, solval) && SCIPvarGetLbLocal(binvar) < SCIPvarGetUbLocal(binvar) - 0.5); 180 } 181 182 /** releases all data from given hashmap filled with SCVarData and the hashmap itself */ 183 static 184 SCIP_RETCODE releaseSCHashmap( 185 SCIP* scip, /**< SCIP data structure */ 186 SCIP_HASHMAP* hashmap /**< hashmap to be freed */ 187 ) 188 { 189 SCIP_HASHMAPENTRY* entry; 190 SCVARDATA* data; 191 int c; 192 193 if( hashmap != NULL ) 194 { 195 for( c = 0; c < SCIPhashmapGetNEntries( hashmap ); c++ ) 196 { 197 entry = SCIPhashmapGetEntry( hashmap, c); 198 if( entry != NULL ) 199 { 200 data = (SCVARDATA*) SCIPhashmapEntryGetImage(entry); 201 SCIPfreeBlockMemoryArray(scip, &data->ubs1, data->bndssize); 202 SCIPfreeBlockMemoryArray(scip, &data->lbs1, data->bndssize); 203 SCIPfreeBlockMemoryArray(scip, &data->vals0, data->bndssize); 204 SCIPfreeBlockMemoryArray(scip, &data->bvars, data->bndssize); 205 SCIPfreeBlockMemory(scip, &data); 206 } 207 } 208 SCIPhashmapFree(&hashmap); 209 assert(hashmap == NULL); 210 } 211 212 return SCIP_OKAY; 213 } 214 215 /** checks if variable is indicator variable and stores corresponding indicator constraint; additionally, if we are at a 216 * new probing node, it checks whether there are violated but not fixed indicator constraints 217 */ 218 static 219 SCIP_RETCODE checkAndGetIndicator( 220 SCIP* scip, /**< SCIP data structure */ 221 SCIP_VAR* cand, /**< candidate variable */ 222 SCIP_HASHMAP* map, /**< pointer to hashmap containing indicator conss */ 223 SCIP_CONS** cons, /**< pointer to store indicator constraint */ 224 SCIP_Bool* isindicator, /**< pointer to store whether candidate variable is indicator variable */ 225 SCIP_Bool* containsviolindconss,/**< pointer to store whether there are violated and not fixed (unbounded) indicator constraints */ 226 SCIP_Bool newnode, /**< are we at a new probing node? */ 227 SCIP_SOL* sol, /**< pointer to solution */ 228 SCIP_CONSHDLR* conshdlr /**< constraint handler */ 229 ) 230 { 231 assert(scip != NULL); 232 assert(cand != NULL); 233 assert(map != NULL); 234 assert(cons != NULL); 235 assert(isindicator != NULL); 236 assert(sol != NULL); 237 238 *cons = NULL; 239 *isindicator = FALSE; 240 241 *cons = (SCIP_CONS*) SCIPhashmapGetImage(map, cand); 242 if( *cons != NULL ) 243 *isindicator = TRUE; 244 245 /* since we are at a new probing node, check if there are violated and not fixed indicator constraints */ 246 if( newnode ) 247 { 248 SCIP_CONS** indicatorconss; 249 int nconss; 250 int c; 251 252 indicatorconss = SCIPconshdlrGetConss(conshdlr); 253 nconss = SCIPconshdlrGetNActiveConss(conshdlr); 254 *containsviolindconss = FALSE; 255 256 for( c = 0; c < nconss; c++ ) 257 { 258 *containsviolindconss = *containsviolindconss || isViolatedAndNotFixed(scip, sol, indicatorconss[c]); 259 260 if( *containsviolindconss ) 261 break; 262 } 263 } 264 265 return SCIP_OKAY; 266 } 267 268 /** checks if variable is binary variable of varbound constraint and stores corresponding varbound constraint */ 269 static 270 SCIP_RETCODE checkAndGetVarbound( 271 SCIP* scip, /**< SCIP data structure */ 272 SCIP_VAR* cand, /**< candidate variable */ 273 SCIP_HASHMAP* map, /**< pointer to hashmap containing varbound conss */ 274 SCIP_CONS** cons, /**< pointer to store varbound constraint */ 275 SCIP_Bool* isvarbound /**< pointer to store whether candidate variable is indicator variable */ 276 ) 277 { 278 assert(scip != NULL); 279 assert(cand != NULL); 280 assert(map != NULL); 281 assert(cons != NULL); 282 assert(isvarbound != NULL); 283 284 *cons = NULL; 285 *isvarbound = FALSE; 286 287 if( SCIPvarGetType(cand) != SCIP_VARTYPE_BINARY ) 288 return SCIP_OKAY; 289 290 *cons = (SCIP_CONS*) SCIPhashmapGetImage(map, cand); 291 if( *cons != NULL ) 292 *isvarbound = TRUE; 293 294 return SCIP_OKAY; 295 } 296 297 /** adds an indicator to the data of a semicontinuous variable */ 298 static 299 SCIP_RETCODE addSCVarIndicator( 300 SCIP* scip, /**< SCIP data structure */ 301 SCVARDATA* scvdata, /**< semicontinuous variable data */ 302 SCIP_VAR* indicator, /**< indicator to be added */ 303 SCIP_Real val0, /**< value of the variable when indicator == 0 */ 304 SCIP_Real lb1, /**< lower bound of the variable when indicator == 1 */ 305 SCIP_Real ub1 /**< upper bound of the variable when indicator == 1 */ 306 ) 307 { 308 int newsize; 309 int i; 310 SCIP_Bool found; 311 int pos; 312 313 assert(scvdata != NULL); 314 assert(indicator != NULL); 315 316 /* find the position where to insert */ 317 if( scvdata->bvars == NULL ) 318 { 319 assert(scvdata->nbnds == 0 && scvdata->bndssize == 0); 320 found = FALSE; 321 pos = 0; 322 } 323 else 324 { 325 found = SCIPsortedvecFindPtr((void**)scvdata->bvars, SCIPvarComp, (void*)indicator, scvdata->nbnds, &pos); 326 } 327 328 if( found ) 329 return SCIP_OKAY; 330 331 /* ensure sizes */ 332 if( scvdata->nbnds + 1 > scvdata->bndssize ) 333 { 334 newsize = SCIPcalcMemGrowSize(scip, scvdata->nbnds + 1); 335 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &scvdata->bvars, scvdata->bndssize, newsize) ); 336 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &scvdata->vals0, scvdata->bndssize, newsize) ); 337 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &scvdata->lbs1, scvdata->bndssize, newsize) ); 338 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &scvdata->ubs1, scvdata->bndssize, newsize) ); 339 scvdata->bndssize = newsize; 340 } 341 assert(scvdata->nbnds + 1 <= scvdata->bndssize); 342 assert(scvdata->bvars != NULL); 343 344 /* move entries if needed */ 345 for( i = scvdata->nbnds; i > pos; --i ) 346 { 347 scvdata->bvars[i] = scvdata->bvars[i-1]; 348 scvdata->vals0[i] = scvdata->vals0[i-1]; 349 scvdata->lbs1[i] = scvdata->lbs1[i-1]; 350 scvdata->ubs1[i] = scvdata->ubs1[i-1]; 351 } 352 353 scvdata->bvars[pos] = indicator; 354 scvdata->vals0[pos] = val0; 355 scvdata->lbs1[pos] = lb1; 356 scvdata->ubs1[pos] = ub1; 357 ++scvdata->nbnds; 358 359 return SCIP_OKAY; 360 } 361 362 /** checks if a variable is semicontinuous and stores it data in the hashmap scvars 363 * 364 * A variable x is semicontinuous if its bounds depend on at least one binary variable called the indicator, 365 * and indicator == 0 => x == x^0 for some real constant x^0. 366 */ 367 static 368 SCIP_RETCODE varIsSemicontinuous( 369 SCIP* scip, /**< SCIP data structure */ 370 SCIP_VAR* var, /**< the variable to check */ 371 SCIP_HASHMAP* scvars, /**< semicontinuous variable information */ 372 SCIP_Real constant, /**< value which should be equal to the constant */ 373 SCIP_Bool* result /**< buffer to store whether var is semicontinuous */ 374 ) 375 { 376 SCIP_Real lb0; 377 SCIP_Real ub0; 378 SCIP_Real lb1; 379 SCIP_Real ub1; 380 SCIP_Real glb; 381 SCIP_Real gub; 382 SCIP_Bool exists; 383 int c; 384 int pos; 385 SCIP_VAR** vlbvars; 386 SCIP_VAR** vubvars; 387 SCIP_Real* vlbcoefs; 388 SCIP_Real* vubcoefs; 389 SCIP_Real* vlbconstants; 390 SCIP_Real* vubconstants; 391 int nvlbs; 392 int nvubs; 393 SCVARDATA* scvdata; 394 SCIP_VAR* bvar; 395 396 assert(scip != NULL); 397 assert(var != NULL); 398 assert(scvars != NULL); 399 assert(result != NULL); 400 401 scvdata = (SCVARDATA*) SCIPhashmapGetImage(scvars, (void*)var); 402 if( scvdata != NULL ) 403 { 404 *result = TRUE; 405 return SCIP_OKAY; 406 } 407 408 vlbvars = SCIPvarGetVlbVars(var); 409 vubvars = SCIPvarGetVubVars(var); 410 vlbcoefs = SCIPvarGetVlbCoefs(var); 411 vubcoefs = SCIPvarGetVubCoefs(var); 412 vlbconstants = SCIPvarGetVlbConstants(var); 413 vubconstants = SCIPvarGetVubConstants(var); 414 nvlbs = SCIPvarGetNVlbs(var); 415 nvubs = SCIPvarGetNVubs(var); 416 glb = SCIPvarGetLbGlobal(var); 417 gub = SCIPvarGetUbGlobal(var); 418 419 pos = -1; 420 421 *result = FALSE; 422 423 /* Scan through lower bounds; for each binary vlbvar save the corresponding lb0 and lb1. 424 * Then check if there is an upper bound with this vlbvar and save ub0 and ub1. 425 * If the found bounds imply that the var value is fixed to some val0 when vlbvar = 0, 426 * save vlbvar and val0 to scvdata. 427 */ 428 for( c = 0; c < nvlbs; ++c ) 429 { 430 if( SCIPvarGetType(vlbvars[c]) != SCIP_VARTYPE_BINARY ) 431 continue; 432 433 bvar = vlbvars[c]; 434 435 lb0 = MAX(vlbconstants[c], glb); 436 lb1 = MAX(vlbconstants[c] + vlbcoefs[c], glb); 437 438 /* look for bvar in vubvars */ 439 if( vubvars != NULL ) 440 exists = SCIPsortedvecFindPtr((void**)vubvars, SCIPvarComp, bvar, nvubs, &pos); 441 else 442 exists = FALSE; 443 444 if( exists ) 445 { 446 /* save the upper bounds */ 447 ub0 = MIN(vubconstants[pos], gub); 448 ub1 = MIN(vubconstants[pos] + vubcoefs[pos], gub); 449 } 450 else 451 { 452 /* if there is no upper bound with vubvar = bvar, use global var bounds */ 453 ub0 = gub; 454 ub1 = gub; 455 } 456 457 /* the 'off' domain of a semicontinuous var should reduce to a single point (constant) and be different from the 'on' domain */ 458 if( SCIPisEQ(scip, lb0, constant) && (!SCIPisEQ(scip, lb0, lb1) || !SCIPisEQ(scip, ub0, ub1)) ) 459 { 460 if( scvdata == NULL ) 461 { 462 SCIP_CALL( SCIPallocClearBlockMemory(scip, &scvdata) ); 463 } 464 SCIP_CALL( addSCVarIndicator(scip, scvdata, bvar, lb0, lb1, ub1) ); 465 } 466 } 467 468 /* look for vubvars that have not been processed yet */ 469 assert(vubvars != NULL || nvubs == 0); 470 for( c = 0; c < nvubs; ++c ) 471 { 472 if( SCIPvarGetType(vubvars[c]) != SCIP_VARTYPE_BINARY ) /*lint !e613*/ 473 continue; 474 475 bvar = vubvars[c]; /*lint !e613*/ 476 477 /* skip vars that are in vlbvars */ 478 if( vlbvars != NULL && SCIPsortedvecFindPtr((void**)vlbvars, SCIPvarComp, bvar, nvlbs, &pos) ) 479 continue; 480 481 lb0 = glb; 482 lb1 = glb; 483 ub0 = MIN(vubconstants[c], gub); 484 ub1 = MIN(vubconstants[c] + vubcoefs[c], gub); 485 486 /* the 'off' domain of a semicontinuous var should reduce to a single point (constant) and be different from the 'on' domain */ 487 if( SCIPisEQ(scip, lb0, constant) && (!SCIPisEQ(scip, lb0, lb1) || !SCIPisEQ(scip, ub0, ub1)) ) 488 { 489 if( scvdata == NULL ) 490 { 491 SCIP_CALL( SCIPallocClearBlockMemory(scip, &scvdata) ); 492 } 493 494 SCIP_CALL( addSCVarIndicator(scip, scvdata, bvar, lb0, lb1, ub1) ); 495 } 496 } 497 498 if( scvdata != NULL ) 499 { 500 #ifdef SCIP_DEBUG 501 SCIPdebugMsg(scip, "var <%s> has global bounds [%f, %f] and the following on/off bounds:\n", SCIPvarGetName(var), glb, gub); 502 for( c = 0; c < scvdata->nbnds; ++c ) 503 { 504 SCIPdebugMsg(scip, " c = %d, bvar <%s>: val0 = %f\n", c, SCIPvarGetName(scvdata->bvars[c]), scvdata->vals0[c]); 505 } 506 #endif 507 SCIP_CALL( SCIPhashmapInsert(scvars, var, scvdata) ); 508 *result = TRUE; 509 } 510 511 return SCIP_OKAY; 512 } 513 514 /** checks if there are unfixed indicator variables modeling semicont. vars */ 515 static 516 SCIP_RETCODE hasUnfixedSCIndicator( 517 SCIP* scip, /**< SCIP data structure */ 518 SCIP_CONSHDLR* conshdlr, /**< indicator constraint handler */ 519 SCIP_HASHMAP* scvars, /**< semicontinuous variable information */ 520 SCIP_Bool* hasunfixedscindconss /**< pointer to store if there are unfixed indicator variables modeling semicont. vars */ 521 ) 522 { 523 SCIP_CONS** indicatorconss; 524 SCIP_VAR** consvars; 525 SCIP_Real* consvals; 526 int nconss; 527 int i; 528 529 *hasunfixedscindconss = FALSE; 530 indicatorconss = SCIPconshdlrGetConss(conshdlr); 531 nconss = SCIPconshdlrGetNConss(conshdlr); 532 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, 2) ); 533 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, 2) ); 534 535 for( i = 0; i < nconss; i++ ) 536 { 537 SCIP_VAR *binvar; 538 SCIP_VAR* semicontinuousvar; 539 SCIP_CONS* lincons; 540 SCIP_Real rhs; 541 int nconsvars; 542 SCIP_Bool success; 543 int v; 544 545 binvar = SCIPgetBinaryVarIndicator(indicatorconss[i]); 546 547 /* check if indicator variable is unfixed */ 548 if( SCIPvarGetLbLocal(binvar) < SCIPvarGetUbLocal(binvar) - 0.5 ) 549 { 550 lincons = SCIPgetLinearConsIndicator(indicatorconss[i]); 551 rhs = SCIPconsGetRhs(scip, lincons, &success); 552 SCIP_CALL( SCIPgetConsNVars(scip, lincons, &nconsvars, &success) ); 553 554 /* check if constraint contains only two variables with finite rhs */ 555 /* TODO: allow also indicators for lower bounds */ 556 if( nconsvars == 2 && !SCIPisInfinity(scip, rhs) ) 557 { 558 SCIP_CALL( SCIPgetConsVars(scip, lincons, consvars, nconsvars, &success) ); 559 SCIP_CALL( SCIPgetConsVals(scip, lincons, consvals, nconsvars, &success) ); 560 561 for( v = 0; v < nconsvars ; v++ ) 562 { 563 if( consvars[v] == SCIPgetSlackVarIndicator(indicatorconss[i]) ) /* note that we have exact two variables */ 564 continue; 565 566 semicontinuousvar = consvars[v]; 567 SCIP_CALL( varIsSemicontinuous(scip, semicontinuousvar, scvars, rhs, &success) ); 568 569 /* check if semicontinuous variable */ 570 if( success ) 571 { 572 *hasunfixedscindconss = TRUE; 573 break; 574 } 575 } 576 if( *hasunfixedscindconss ) 577 break; 578 } 579 } 580 } 581 SCIPfreeBufferArray(scip, &consvals); 582 SCIPfreeBufferArray(scip, &consvars); 583 return SCIP_OKAY; 584 } 585 586 /** creates and initializes hashmaps 587 * 588 * indicatormap: binary var -> indicator constraint 589 * varboundmap: binary var -> varbound constraint 590 * 591 * Currently exactly one constraint is assigned to a binary variable (per hashmap), 592 * but a binary variable can also control more than one constraint. 593 * TODO: Allow more than one corresponding indicator/varbound constraint per binary variable. 594 */ 595 static 596 SCIP_RETCODE createMaps( 597 SCIP* scip, /**< SCIP data structure */ 598 SCIP_CONSHDLR* indicatorconshdlr, /**< indicator constraint handler */ 599 SCIP_CONSHDLR* varboundconshdlr, /**< varbound constraint handler */ 600 SCIP_Bool usevarbounds, /**< should varbound constraints be considered? */ 601 SCIP_HASHMAP** indicatormap, /**< hashmap to store indicator constraints of binary variables */ 602 SCIP_HASHMAP** varboundmap /**< hashmap to store varbound constraints of binary variables */ 603 ) 604 { 605 SCIP_CONS** conss; 606 int nconss; 607 int i; 608 609 assert(strcmp(SCIPconshdlrGetName(indicatorconshdlr), "indicator") == 0); 610 assert(strcmp(SCIPconshdlrGetName(varboundconshdlr), "varbound") == 0); 611 612 /* indicator constraints */ 613 nconss = SCIPconshdlrGetNConss(indicatorconshdlr); 614 conss = SCIPconshdlrGetConss(indicatorconshdlr); 615 SCIP_CALL( SCIPhashmapCreate(indicatormap, SCIPblkmem(scip), nconss) ); 616 for( i = 0; i < nconss; i++ ) 617 { 618 if( !SCIPhashmapExists(*indicatormap, SCIPgetBinaryVarIndicator(conss[i])) ) 619 { 620 SCIP_CALL( SCIPhashmapInsert(*indicatormap, SCIPgetBinaryVarIndicator(conss[i]), conss[i]) ); 621 } 622 } 623 624 /* varbound constraints */ 625 if( usevarbounds ) 626 { 627 nconss = SCIPconshdlrGetNConss(varboundconshdlr); 628 conss = SCIPconshdlrGetConss(varboundconshdlr); 629 SCIP_CALL( SCIPhashmapCreate(varboundmap, SCIPblkmem(scip), nconss) ); 630 for( i = 0; i < nconss; i++ ) 631 { 632 if( !SCIPhashmapExists(*varboundmap, SCIPgetVbdvarVarbound(scip, conss[i])) ) 633 { 634 SCIP_CALL( SCIPhashmapInsert(*varboundmap, SCIPgetVbdvarVarbound(scip, conss[i]), conss[i]) ); 635 } 636 } 637 } 638 return SCIP_OKAY; 639 } 640 641 #define MIN_RAND 1e-06 642 #define MAX_RAND 1e-05 643 644 /** calculate score and preferred rounding direction for the candidate variable */ 645 static 646 void getScoreOfFarkasDiving( 647 SCIP* scip, /**< SCIP data structure */ 648 SCIP_DIVESET* diveset, /**< diving settings */ 649 SCIP_VAR* cand, /**< candidate variable */ 650 SCIP_Real candsfrac, /**< fractional part of solution value of candidate variable */ 651 SCIP_Bool* roundup, /**< pointer to store whether the preferred rounding direction is upwards */ 652 SCIP_Real* score /**< pointer for diving score value */ 653 ) 654 { 655 SCIP_RANDNUMGEN* randnumgen; 656 SCIP_Real obj; 657 658 randnumgen = SCIPdivesetGetRandnumgen(diveset); 659 assert(randnumgen != NULL); 660 661 obj = SCIPvarGetObj(cand); 662 663 /* dive towards the pseudosolution, at the same time approximate the contribution to 664 * a potential Farkas-proof (infeasibility proof) by y^TA_i = c_i. 665 */ 666 if( SCIPisNegative(scip, obj) ) 667 *roundup = TRUE; 668 else if( SCIPisPositive(scip, obj) ) 669 *roundup = FALSE; 670 else 671 { 672 if( SCIPisEQ(scip, candsfrac, 0.5) ) 673 *roundup = !SCIPrandomGetInt(randnumgen, 0, 1); 674 else 675 *roundup = (candsfrac > 0.5); 676 } 677 678 /* larger score is better */ 679 *score = REALABS(obj) + SCIPrandomGetReal(randnumgen, MIN_RAND, MAX_RAND); 680 681 /* prefer decisions on binary variables */ 682 if( SCIPvarGetType(cand) != SCIP_VARTYPE_BINARY ) 683 *score = -1.0 / *score; 684 } 685 686 687 /* 688 * Callback methods 689 */ 690 691 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 692 static 693 SCIP_DECL_HEURCOPY(heurCopyIndicatordiving) 694 { /*lint --e{715}*/ 695 assert(scip != NULL); 696 assert(heur != NULL); 697 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 698 699 /* call inclusion method of primal heuristic */ 700 SCIP_CALL( SCIPincludeHeurIndicatordiving(scip) ); 701 702 return SCIP_OKAY; 703 } 704 705 706 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 707 static 708 SCIP_DECL_HEURFREE(heurFreeIndicatordiving) 709 { /*lint --e{715}*/ 710 SCIP_HEURDATA* heurdata; 711 712 assert(heur != NULL); 713 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 714 assert(scip != NULL); 715 716 /* free heuristic data */ 717 heurdata = SCIPheurGetData(heur); 718 assert(heurdata != NULL); 719 720 SCIPfreeBlockMemory(scip, &heurdata); 721 SCIPheurSetData(heur, NULL); 722 723 return SCIP_OKAY; 724 } 725 726 727 /** initialization method of primal heuristic (called after problem was transformed) */ 728 static 729 SCIP_DECL_HEURINIT(heurInitIndicatordiving) 730 { /*lint --e{715}*/ 731 SCIP_HEURDATA* heurdata; 732 733 assert(heur != NULL); 734 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 735 assert(scip != NULL); 736 737 /* get heuristic data */ 738 heurdata = SCIPheurGetData(heur); 739 assert(heurdata != NULL); 740 741 /* create working data */ 742 SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) ); 743 SCIP_CALL( SCIPhashmapCreate( &heurdata->scvars, SCIPblkmem( scip ), SCIPgetNVars(scip) )); 744 745 heurdata->indicatorconshdlr = SCIPfindConshdlr(scip, "indicator"); 746 heurdata->varboundconshdlr = SCIPfindConshdlr(scip, "varbound"); 747 748 return SCIP_OKAY; 749 } 750 751 752 /** deinitialization method of primal heuristic (called before transformed problem is freed) */ 753 static 754 SCIP_DECL_HEUREXIT(heurExitIndicatordiving) 755 { /*lint --e{715}*/ 756 SCIP_HEURDATA* heurdata; 757 758 assert(heur != NULL); 759 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 760 assert(scip != NULL); 761 762 /* get heuristic data */ 763 heurdata = SCIPheurGetData(heur); 764 assert(heurdata != NULL); 765 766 /* free working data */ 767 SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) ); 768 SCIP_CALL( releaseSCHashmap(scip, heurdata->scvars) ); 769 770 return SCIP_OKAY; 771 } 772 773 774 /** execution method of primal heuristic */ 775 static 776 SCIP_DECL_HEUREXEC(heurExecIndicatordiving) 777 { /*lint --e{715}*/ 778 SCIP_HEURDATA* heurdata; 779 SCIP_DIVESET* diveset; 780 SCIP_Bool hasunfixedscindconss; /* are there unfixed indicator variables modeling a semicont. variable? */ 781 782 heurdata = SCIPheurGetData(heur); 783 assert(heurdata != NULL); 784 785 assert(SCIPheurGetNDivesets(heur) > 0); 786 assert(SCIPheurGetDivesets(heur) != NULL); 787 diveset = SCIPheurGetDivesets(heur)[0]; 788 assert(diveset != NULL); 789 790 assert(result != NULL); 791 *result = SCIP_DIDNOTRUN; 792 793 /* check if there are unfixed indicator variables modeling semicont. vars */ 794 SCIP_CALL( hasUnfixedSCIndicator(scip, heurdata->indicatorconshdlr, heurdata->scvars, &hasunfixedscindconss) ); 795 796 /* skip heuristic if problem doesn't contain unfixed indicator variables, 797 * or if there are no varbound constraints which should be considered 798 */ 799 if( !hasunfixedscindconss && (!heurdata->runwithoutscinds || !heurdata->usevarbounds || SCIPconshdlrGetNConss(heurdata->varboundconshdlr) == 0) ) 800 return SCIP_OKAY; 801 802 SCIPdebugMsg(scip, "call heurExecIndicatordiving at depth %d \n", SCIPgetDepth(scip)); 803 804 /* create and initialize hashmaps */ 805 SCIP_CALL( createMaps(scip, heurdata->indicatorconshdlr, heurdata->varboundconshdlr, heurdata->usevarbounds, &heurdata->indicatormap, &heurdata->varboundmap) ); 806 807 /* (re-)set flags */ 808 heurdata->gotoindconss = FALSE; 809 heurdata->containsviolindconss = FALSE; 810 heurdata->newnode = TRUE; 811 heurdata->probingdepth = -1; 812 813 SCIP_CALL( SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, -1L, -1, -1.0, SCIP_DIVECONTEXT_SINGLE) ); 814 815 /* free hashmaps since constraints can get removed/modified till the next call */ 816 if( heurdata->usevarbounds ) 817 SCIPhashmapFree(&heurdata->varboundmap); 818 SCIPhashmapFree(&heurdata->indicatormap); 819 820 SCIPdebugMsg(scip, "leave heurExecIndicatordiving\n"); 821 822 return SCIP_OKAY; 823 } 824 825 826 /** calculate score and preferred rounding direction for the candidate variable */ 827 static 828 SCIP_DECL_DIVESETGETSCORE(divesetGetScoreIndicatordiving) 829 { /*lint --e{715}*/ 830 SCIP_HEUR* heur; 831 SCIP_HEURDATA* heurdata; 832 SCIP_RANDNUMGEN* randnumgen; 833 SCIP_VAR** consvars; 834 SCIP_CONS* indicatorcons; 835 SCIP_CONS* varboundcons; 836 SCIP_CONS* lincons; 837 SCIP_VAR* nonoptionvar; /* second variable in linear cons which is not the option variable (indicator: slackvar, varbound: binary var) */ 838 SCIP_VAR* semicontinuousvar; 839 SCIP_Real lpsolsemicontinuous; 840 SCVARDATA* scdata; 841 SCIP_Real* consvals; 842 SCIP_Real side; 843 int nconsvars; 844 int idxbvars; /* index of bounding variable in hashmap scdata */ 845 SCIP_Bool isindicatorvar; 846 SCIP_Bool isvbdvar; /* variable bounding variable in varbound */ 847 SCIP_Bool issemicont; /* indicates whether variable has (maybe) required semicont. properties */ 848 SCIP_Bool fixconstant; /* should we fix the semicontinuous variable to its constant? */ 849 SCIP_Bool success; 850 int v; 851 int b; 852 853 varboundcons = NULL; 854 semicontinuousvar = NULL; 855 scdata = NULL; 856 lpsolsemicontinuous = 0.0; 857 idxbvars = -1; 858 isvbdvar = FALSE; 859 issemicont = TRUE; 860 861 heur = SCIPdivesetGetHeur(diveset); 862 assert(heur != NULL); 863 heurdata = SCIPheurGetData(heur); 864 assert(heurdata != NULL); 865 866 randnumgen = SCIPdivesetGetRandnumgen(diveset); 867 assert(randnumgen != NULL); 868 869 /* check if we are at a new probing node; since diving heuristics backtrack at most one probing node, we are at a new 870 * node iff the probing depth increased */ 871 if( heurdata->probingdepth < SCIPgetProbingDepth(scip) ) 872 heurdata->newnode = TRUE; 873 else 874 { 875 assert(heurdata->probingdepth == SCIPgetProbingDepth(scip)); 876 heurdata->newnode = FALSE; 877 } 878 heurdata->probingdepth = SCIPgetProbingDepth(scip); 879 880 /* skip if current candidate can not be determined by the indicator constraint handler and violated indicator 881 * constraints still exists */ 882 if( !(SCIPisFeasIntegral(scip, candsol) && SCIPvarGetLbLocal(cand) < SCIPvarGetUbLocal(cand) - 0.5) 883 && heurdata->gotoindconss ) 884 { 885 *score = SCIP_REAL_MIN; 886 *roundup = FALSE; 887 return SCIP_OKAY; 888 } 889 else 890 heurdata->gotoindconss = FALSE; 891 892 /* check if candidate variable is indicator variable */ 893 SCIP_CALL( checkAndGetIndicator(scip, cand, heurdata->indicatormap, &indicatorcons, &isindicatorvar, 894 &heurdata->containsviolindconss, heurdata->newnode, heurdata->sol, heurdata->indicatorconshdlr) ); 895 896 /* skip candidate in next calls since we have violated indicator constraints but current candidate is not determined 897 * by the indicator constraint handler */ 898 if( heurdata->containsviolindconss && 899 !((SCIPisFeasIntegral(scip, candsol) && SCIPvarGetLbLocal(cand) < SCIPvarGetUbLocal(cand) - 0.5) && isindicatorvar) ) 900 { 901 heurdata->gotoindconss = TRUE; 902 *score = SCIP_REAL_MIN; 903 *roundup = FALSE; 904 return SCIP_OKAY; 905 } 906 907 /* check if candidate variable is bounding variable */ 908 if( heurdata->usevarbounds && !isindicatorvar ) 909 { 910 SCIP_CALL( checkAndGetVarbound(scip, cand, heurdata->varboundmap, &varboundcons, &isvbdvar) ); 911 } 912 913 /* Return 914 * - if candidate variable is neither a indicator variable nor a variable bounding variable 915 * - or if candidate variable is not an indicator variable but there will be indicator variables as candidates 916 * - or if candidate variable is not an indicator variable and varbound constraints are not considered. 917 */ 918 if( !isindicatorvar && (!isvbdvar || heurdata->containsviolindconss || !heurdata->usevarbounds) ) 919 { 920 *score = SCIP_REAL_MIN; 921 *roundup = FALSE; 922 923 if( !heurdata->containsviolindconss && !isvbdvar ) 924 { 925 getScoreOfFarkasDiving(scip, diveset, cand, candsfrac, roundup, score); 926 *score = (*score / (100 + fabs(*score))) * 100 - 200; /* scale to [-300,-100] */ 927 } 928 return SCIP_OKAY; 929 } 930 931 SCIPdebugMsg(scip, "cand: %s, candsol: %.2f, candobjcoeff: %f\n", SCIPvarGetName(cand), candsol, SCIPvarGetObj(cand)); 932 933 if( isindicatorvar ) /* prefer indicator constraint */ 934 { 935 SCIP_Real rhs; 936 937 lincons = SCIPgetLinearConsIndicator(indicatorcons); 938 nonoptionvar = SCIPgetSlackVarIndicator(indicatorcons); 939 rhs = SCIPconsGetRhs(scip, lincons, &success); 940 issemicont = SCIPisInfinity(scip, -SCIPconsGetLhs(scip, lincons, &success)); /* TODO: allow also indicators for lower bounds */ 941 side = rhs; 942 } 943 else if( isvbdvar ) 944 { 945 SCIP_Real rhs; 946 SCIP_Real lhs; 947 948 lincons = varboundcons; 949 nonoptionvar = SCIPgetVbdvarVarbound(scip, varboundcons); 950 rhs = SCIPconsGetRhs(scip, lincons, &success); 951 lhs = SCIPconsGetLhs(scip, lincons, &success); 952 side = SCIPisInfinity(scip, rhs) ? lhs : rhs; 953 assert(!SCIPisInfinity(scip, side)); 954 } 955 else 956 { 957 assert(FALSE); 958 } 959 SCIPdebugPrintCons(scip, lincons, NULL); 960 961 SCIP_CALL( SCIPgetConsNVars(scip, lincons, &nconsvars, &success) ); 962 963 if( nconsvars != 2 || !issemicont ) 964 { 965 getScoreOfFarkasDiving(scip, diveset, cand, candsfrac, roundup, score); 966 *score = (*score / (100 + fabs(*score))) * 100 - 200; /* scale to [-300,-100] */ 967 return SCIP_OKAY; 968 } 969 970 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nconsvars) ); 971 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, nconsvars) ); 972 SCIP_CALL( SCIPgetConsVars(scip, lincons, consvars, nconsvars, &success) ); 973 SCIP_CALL( SCIPgetConsVals(scip, lincons, consvals, nconsvars, &success) ); 974 975 issemicont = FALSE; 976 for( v = 0; v < nconsvars ; v++ ) 977 { 978 if( consvars[v] == nonoptionvar ) /* note that we have exact two variables */ 979 continue; 980 981 semicontinuousvar = consvars[v]; 982 lpsolsemicontinuous = SCIPvarGetLPSol( semicontinuousvar ); 983 SCIPdebugMsg(scip, "%s lp sol %f %f\n", SCIPvarGetName( semicontinuousvar ), lpsolsemicontinuous, 984 consvals[v] ); 985 SCIP_CALL( varIsSemicontinuous(scip, semicontinuousvar, heurdata->scvars, side, &success) ); 986 987 /* only allow semicontinuous variables */ 988 if( success ) 989 { 990 assert(SCIPhashmapExists(heurdata->scvars, (void*) semicontinuousvar)); 991 scdata = (SCVARDATA*) SCIPhashmapGetImage(heurdata->scvars, (void*) semicontinuousvar); 992 assert(scdata != NULL); 993 994 for( b = 0; b < scdata->nbnds; b++ ) 995 { 996 if( (scdata->bvars[b] == cand || (SCIPvarIsNegated(cand) && scdata->bvars[0] == SCIPvarGetNegationVar(cand))) 997 && SCIPisEQ(scip, side, scdata->vals0[b]) ) 998 { 999 1000 /* TODO: handle also more general variables; 1001 * currently we handle only variables with domain vals0 < lb1 <= ub1 */ 1002 if( SCIPisGE(scip, lpsolsemicontinuous, scdata->vals0[b]) && SCIPisLE(scip, lpsolsemicontinuous, scdata->ubs1[b]) ) 1003 { 1004 issemicont = TRUE; 1005 idxbvars = b; 1006 break; 1007 } 1008 } 1009 } 1010 } 1011 } 1012 1013 /* only continue if semicontinuous variable */ 1014 if( !issemicont ) 1015 { 1016 getScoreOfFarkasDiving(scip, diveset, cand, candsfrac, roundup, score); 1017 *score = (*score / (100 + fabs(*score))) * 100 - 200; /* scale to [-300,-100] */ 1018 SCIPfreeBufferArray(scip, &consvals); 1019 SCIPfreeBufferArray(scip, &consvars); 1020 return SCIP_OKAY; 1021 } 1022 assert(idxbvars >= 0); 1023 assert(scdata != NULL); 1024 1025 /* Case: Variable is in range [lb1,ub1] */ 1026 if( SCIPisGE(scip, lpsolsemicontinuous, scdata->lbs1[idxbvars]) && SCIPisLE(scip, lpsolsemicontinuous, scdata->ubs1[idxbvars])) 1027 { 1028 *score = SCIPrandomGetReal(randnumgen, -1.0, 0.0); 1029 fixconstant = FALSE; 1030 } 1031 /* Case: Variable is equal to constant */ 1032 else if( SCIPisEQ(scip, lpsolsemicontinuous, scdata->vals0[idxbvars]) ) 1033 { 1034 *score = SCIPrandomGetReal(randnumgen, -1.0, 0.0); 1035 fixconstant = TRUE; 1036 } 1037 /* Case: Variable is between constant and lb1 */ 1038 else if( SCIPisGT(scip, lpsolsemicontinuous, scdata->vals0[idxbvars]) && SCIPisLT(scip, lpsolsemicontinuous, scdata->lbs1[idxbvars]) ) 1039 { 1040 SCIP_Real shiftedlpsolsemicontinuous = lpsolsemicontinuous; 1041 SCIP_Real shiftedlbs1 = scdata->lbs1[idxbvars]; 1042 1043 /* handle case if constant of semicont. var is not zero -> shift values */ 1044 if( !SCIPisZero(scip, scdata->vals0[idxbvars]) ) 1045 { 1046 shiftedlpsolsemicontinuous -= scdata->vals0[idxbvars]; 1047 shiftedlbs1 -= scdata->vals0[idxbvars]; 1048 } 1049 1050 *score = 100 * (shiftedlbs1 - shiftedlpsolsemicontinuous) / shiftedlbs1; 1051 assert(*score>0); 1052 1053 switch( (INDICATORDIVINGROUNDINGMODE)heurdata->roundingmode ) 1054 { 1055 case ROUNDING_CONSERVATIVE: 1056 fixconstant = (*score > (1 - heurdata->roundingfrac) * 100); 1057 break; 1058 case ROUNDING_AGGRESSIVE: 1059 fixconstant = (*score <= (1 - heurdata->roundingfrac) * 100); 1060 break; 1061 } 1062 1063 switch( heurdata->semicontscoremode ) 1064 { 1065 case 0: 1066 break; 1067 case 1: 1068 if( shiftedlpsolsemicontinuous < shiftedlbs1 * heurdata->roundingfrac ) 1069 *score = 100 * (shiftedlpsolsemicontinuous / (heurdata->roundingfrac * shiftedlbs1)); 1070 else 1071 *score = 100 * (-shiftedlpsolsemicontinuous / ((1 - heurdata->roundingfrac) * shiftedlbs1) + (1 / (1 - heurdata->roundingfrac)) ); 1072 break; 1073 case 2: 1074 *score = 100 - *score; 1075 break; 1076 default: 1077 return SCIP_INVALIDDATA; 1078 } 1079 assert(*score>0); 1080 } 1081 else 1082 { 1083 assert(FALSE); 1084 } 1085 1086 /* Set roundup depending on whether we have an indicator constraint or a varbound constraint: 1087 * - indicator constraint: roundup == fix to constant 1088 * - varbound constraint: roundup == push to range 1089 */ 1090 *roundup = isindicatorvar ? fixconstant : !fixconstant; /*lint !e644*/ 1091 1092 /* free memory */ 1093 SCIPfreeBufferArray(scip, &consvals); 1094 SCIPfreeBufferArray(scip, &consvars); 1095 1096 return SCIP_OKAY; 1097 } 1098 1099 1100 /** callback to check preconditions for diving, e.g., if an incumbent solution is available */ 1101 static 1102 SCIP_DECL_DIVESETAVAILABLE(divesetAvailableIndicatordiving) 1103 { 1104 /* Skip if problem doesn't contain indicator constraints. 1105 * If varbound constraints should be considered, skip only if there are also no varbound constraints. 1106 */ 1107 *available = SCIPconshdlrGetNActiveConss(SCIPfindConshdlr(scip, "indicator")) == 0; 1108 1109 if( !*available ) 1110 { 1111 SCIP_HEUR* heur; 1112 SCIP_HEURDATA* heurdata; 1113 1114 heur = SCIPdivesetGetHeur(diveset); 1115 assert(heur != NULL); 1116 heurdata = SCIPheurGetData(heur); 1117 assert(heurdata != NULL); 1118 1119 if( heurdata->runwithoutscinds && heurdata->usevarbounds ) 1120 { 1121 *available = SCIPconshdlrGetNActiveConss(SCIPfindConshdlr(scip, "varbound")) == 0; 1122 } 1123 } 1124 1125 return SCIP_OKAY; 1126 } 1127 1128 /* 1129 * heuristic specific interface methods 1130 */ 1131 1132 /** creates the indicatordiving heuristic and includes it in SCIP */ 1133 SCIP_RETCODE SCIPincludeHeurIndicatordiving( 1134 SCIP* scip /**< SCIP data structure */ 1135 ) 1136 { 1137 SCIP_HEURDATA* heurdata; 1138 SCIP_HEUR* heur; 1139 1140 /* create indicatordiving primal heuristic data */ 1141 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 1142 1143 heur = NULL; 1144 1145 /* include primal heuristic */ 1146 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 1147 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 1148 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecIndicatordiving, heurdata) ); 1149 1150 assert(heur != NULL); 1151 1152 /* set non fundamental callbacks via setter functions */ 1153 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyIndicatordiving) ); 1154 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeIndicatordiving) ); 1155 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitIndicatordiving) ); 1156 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitIndicatordiving) ); 1157 1158 /* create a diveset (this will automatically install some additional parameters for the heuristic)*/ 1159 SCIP_CALL( SCIPcreateDiveset(scip, NULL, heur, HEUR_NAME, DEFAULT_MINRELDEPTH, DEFAULT_MAXRELDEPTH, DEFAULT_MAXLPITERQUOT, 1160 DEFAULT_MAXDIVEUBQUOT, DEFAULT_MAXDIVEAVGQUOT, DEFAULT_MAXDIVEUBQUOTNOSOL, DEFAULT_MAXDIVEAVGQUOTNOSOL, DEFAULT_LPRESOLVEDOMCHGQUOT, 1161 DEFAULT_LPSOLVEFREQ, DEFAULT_MAXLPITEROFS, DEFAULT_RANDSEED, DEFAULT_BACKTRACK, DEFAULT_ONLYLPBRANCHCANDS, 1162 DIVESET_ISPUBLIC, DIVESET_DIVETYPES, divesetGetScoreIndicatordiving, divesetAvailableIndicatordiving) ); 1163 1164 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/roundingfrac", 1165 "in violation case all fractional below this value are fixed to constant", 1166 &heurdata->roundingfrac, FALSE, DEFAULT_ROUNDINGFRAC, 0.0, 1.0, NULL, NULL) ); 1167 1168 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/roundingmode", 1169 "decides which roundingmode is selected (0: conservative, 1: aggressive)", 1170 &heurdata->roundingmode, FALSE, DEFAULT_ROUNDINGMODE, 0, 1, NULL, NULL) ); 1171 1172 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/semicontscoremode", 1173 "which values of semi-continuous variables should get a high score? (0: low, 1: middle, 2: high)", 1174 &heurdata->semicontscoremode, FALSE, DEFAULT_SEMICONTSCOREMODE, 0, 2, NULL, NULL) ); 1175 1176 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usevarbounds", 1177 "should varbound constraints be considered?", 1178 &heurdata->usevarbounds, FALSE, DEFAULT_USEVARBOUNDS, NULL, NULL) ); 1179 1180 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/runwithoutscinds", 1181 "should heur run if there are no indicator constraints modeling semicont. vars?", 1182 &heurdata->runwithoutscinds, FALSE, DEFAULT_RUNWITHOUTSCINDS, NULL, NULL) ); 1183 1184 return SCIP_OKAY; 1185 } 1186