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 heur_clique.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief LNS heuristic using a clique partition to restrict the search neighborhood 28 * @brief clique primal heuristic 29 * @author Stefan Heinz 30 * @author Michael Winkler 31 * @author Gerald Gamrath 32 * 33 * @todo allow smaller fixing rate for probing LP? 34 * @todo allow smaller fixing rate after presolve if total number of variables is small (<= 1000)? 35 * 36 * More details about the heuristic can be found in@n 37 * Structure-Based Primal Heuristics for Mixed Integer Programming@n 38 * Gerald Gamrath, Timo Berthold, Stefan Heinz, and Michael Winkler@n 39 * Optimization in the Real World, Volume 13 of the series Mathematics for Industry, pp 37-53@n 40 * Preliminary version available as <a href="https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/5551">ZIB-Report 15-26</a>. 41 */ 42 43 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 44 45 #include "blockmemshell/memory.h" 46 #include "scip/cons_logicor.h" 47 #include "scip/heur_clique.h" 48 #include "scip/heur_locks.h" 49 #include "scip/pub_heur.h" 50 #include "scip/pub_implics.h" 51 #include "scip/pub_message.h" 52 #include "scip/pub_misc.h" 53 #include "scip/pub_misc_sort.h" 54 #include "scip/pub_var.h" 55 #include "scip/scip_branch.h" 56 #include "scip/scip_cons.h" 57 #include "scip/scip_copy.h" 58 #include "scip/scip_general.h" 59 #include "scip/scip_heur.h" 60 #include "scip/scip_lp.h" 61 #include "scip/scip_mem.h" 62 #include "scip/scip_message.h" 63 #include "scip/scip_numerics.h" 64 #include "scip/scip_param.h" 65 #include "scip/scip_prob.h" 66 #include "scip/scip_probing.h" 67 #include "scip/scip_sol.h" 68 #include "scip/scip_solve.h" 69 #include "scip/scip_solvingstats.h" 70 #include "scip/scip_timing.h" 71 #include "scip/scip_tree.h" 72 #include "scip/scip_var.h" 73 #include <string.h> 74 75 76 #define HEUR_NAME "clique" 77 #define HEUR_DESC "LNS heuristic using a clique partition to restrict the search neighborhood" 78 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_PROP 79 #define HEUR_PRIORITY 5000 80 #define HEUR_FREQ 0 81 #define HEUR_FREQOFS 0 82 #define HEUR_MAXDEPTH -1 83 #define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE 84 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */ 85 86 #define DEFAULT_MAXNODES 5000LL /**< maximum number of nodes to regard in the subproblem */ 87 #define DEFAULT_MININTFIXINGRATE 0.65 /**< minimum percentage of integer variables that have to be fixed */ 88 #define DEFAULT_MINMIPFIXINGRATE 0.65 /**< minimum percentage of variables that have to be fixed within sub-SCIP 89 * (integer and continuous) */ 90 #define DEFAULT_MINIMPROVE 0.01 /**< factor by which clique heuristic should at least improve the 91 * incumbent */ 92 #define DEFAULT_MINNODES 500LL /**< minimum number of nodes to regard in the subproblem */ 93 #define DEFAULT_NODESOFS 500LL /**< number of nodes added to the contingent of the total nodes */ 94 #define DEFAULT_NODESQUOT 0.1 /**< subproblem nodes in relation to nodes of the original problem */ 95 #define DEFAULT_MAXPROPROUNDS 2 /**< maximum number of propagation rounds during probing */ 96 #define DEFAULT_MAXBACKTRACKS 10 /**< maximum number of backtracks during the fixing process */ 97 #define DEFAULT_COPYCUTS TRUE /**< should all active cuts from the cutpool of the 98 * original scip be copied to constraints of the subscip */ 99 #define DEFAULT_USELOCKFIXINGS FALSE /**< should more variables be fixed based on variable locks if 100 * the fixing rate was not reached? */ 101 102 103 /* 104 * Data structures 105 */ 106 107 /** primal heuristic data */ 108 struct SCIP_HeurData 109 { 110 SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */ 111 SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */ 112 SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */ 113 SCIP_Longint usednodes; /**< nodes already used by clique heuristic in earlier calls */ 114 SCIP_Real minintfixingrate; /**< minimum percentage of integer variables that have to be fixed */ 115 SCIP_Real minmipfixingrate; /**< minimum percentage of variables that have to be fixed within sub-SCIP 116 * (integer and continuous) */ 117 SCIP_Real minimprove; /**< factor by which clique heuristic should at least improve the incumbent */ 118 SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */ 119 int maxproprounds; /**< maximum number of propagation rounds during probing */ 120 int maxbacktracks; /**< maximum number of backtracks during the fixing process */ 121 SCIP_Bool copycuts; /**< should all active cuts from cutpool be copied to constraints in 122 * subproblem? 123 */ 124 SCIP_Bool uselockfixings; /**< should more variables be fixed based on variable locks if 125 * the fixing rate was not reached? 126 */ 127 }; 128 129 /* 130 * Local methods 131 */ 132 133 /** comparison method for sorting cliques by their size */ 134 static 135 SCIP_DECL_SORTINDCOMP(compCliquesSize) 136 { 137 int* cliquesizes = (int*)dataptr; 138 139 return cliquesizes[ind2] - cliquesizes[ind1]; 140 } 141 142 static 143 int getCliqueUnfixedVars( 144 SCIP_CLIQUE* clique 145 ) 146 { 147 SCIP_VAR** cliquevars; 148 SCIP_VAR* var; 149 int ncliquevars; 150 int nunfixed = 0; 151 int v; 152 153 ncliquevars = SCIPcliqueGetNVars(clique); 154 cliquevars = SCIPcliqueGetVars(clique); 155 156 for( v = 0; v < ncliquevars; ++v ) 157 { 158 var = cliquevars[v]; 159 160 /* is variable unfixed? */ 161 if( SCIPvarGetUbLocal(var) > SCIPvarGetLbLocal(var) + 0.5 ) 162 ++nunfixed; 163 } 164 165 return nunfixed; 166 } 167 168 /** apply clique fixing using probing */ 169 static 170 SCIP_RETCODE applyCliqueFixings( 171 SCIP* scip, /**< original SCIP data structure */ 172 SCIP_HEURDATA* heurdata, /**< structure containing heurdata */ 173 SCIP_Bool enabledconflicts, /**< was conflict analysis enabled before the heuristic call? */ 174 SCIP_VAR** onefixvars, /**< array to store all variables which are fixed to one in the cliques */ 175 SCIP_Shortbool* onefixvals, /**< array to store the values of all variables fixed to one in the cliques */ 176 int* nonefixvars, /**< pointer to store the number of variables fixed to one */ 177 SCIP_Bool* cutoff /**< pointer to store whether the propagation stopped with infeasibility */ 178 ) 179 { 180 SCIP_CLIQUE** cliques; 181 SCIP_CLIQUE* clique; 182 SCIP_VAR** cliquevars; 183 SCIP_VAR* var; 184 SCIP_Bool* cliquevals; 185 SCIP_Bool* propagated; 186 int* cliquesizes; 187 int* permutation; 188 SCIP_Real bestobj; 189 SCIP_Real obj; 190 SCIP_Bool alreadyone; 191 SCIP_Bool newnode; 192 int probingdepthofonefix; 193 int ncliquevars; 194 int ncliques; 195 int bestpos; 196 int firstclique; 197 int bestclique; 198 int cliquesize; 199 int bestcliquesize; 200 int nbacktracks = 0; 201 int v = 0; 202 int c; 203 int i; 204 205 assert(scip != NULL); 206 assert(heurdata != NULL); 207 assert(onefixvars != NULL); 208 assert(nonefixvars != NULL); 209 assert(cutoff != NULL); 210 211 cliques = SCIPgetCliques(scip); 212 ncliques = SCIPgetNCliques(scip); 213 214 /* allocate memory */ 215 SCIP_CALL( SCIPallocBufferArray(scip, &cliquesizes, ncliques) ); 216 SCIP_CALL( SCIPallocBufferArray(scip, &permutation, ncliques) ); 217 SCIP_CALL( SCIPallocClearBufferArray(scip, &propagated, ncliques) ); 218 219 for( c = ncliques - 1; c >= 0; --c ) 220 { 221 cliquesizes[c] = SCIPcliqueGetNVars(cliques[c]); 222 } 223 224 SCIPsort(permutation, compCliquesSize, (void*)cliquesizes, ncliques); 225 226 #ifndef NDEBUG 227 for( c = ncliques - 1; c >= 1; --c ) 228 { 229 assert(cliquesizes[permutation[c]] <= cliquesizes[permutation[c-1]]); 230 } 231 #endif 232 233 *cutoff = FALSE; 234 probingdepthofonefix = 0; 235 firstclique = 0; 236 237 SCIP_CALL( SCIPnewProbingNode(scip) ); 238 239 /* @todo maybe try to fix more than one variable to one in each probing node, to gain faster results */ 240 for( c = 0; c < ncliques; ++c ) 241 { 242 bestpos = -1; 243 bestobj = SCIPinfinity(scip); 244 alreadyone = FALSE; 245 newnode = FALSE; 246 247 bestclique = firstclique; 248 249 if( bestclique >= ncliques ) 250 break; 251 252 bestcliquesize = getCliqueUnfixedVars(cliques[permutation[bestclique]]); 253 assert(!propagated[permutation[bestclique]]); 254 255 for( i = firstclique + 1; i < ncliques; ++i) 256 { 257 if( cliquesizes[permutation[i]] < bestcliquesize ) 258 break; 259 260 if( propagated[permutation[i]] ) 261 continue; 262 263 cliquesize = getCliqueUnfixedVars(cliques[permutation[i]]); 264 265 if( cliquesize > bestcliquesize ) 266 { 267 bestclique = i; 268 bestcliquesize = cliquesize; 269 } 270 else if( cliquesize == 0 ) 271 { 272 propagated[permutation[i]] = TRUE; 273 } 274 } 275 clique = cliques[permutation[bestclique]]; 276 propagated[permutation[bestclique]] = TRUE; 277 278 while( firstclique < ncliques && propagated[permutation[firstclique]] ) 279 ++firstclique; 280 281 ncliquevars = SCIPcliqueGetNVars(clique); 282 cliquevars = SCIPcliqueGetVars(clique); 283 cliquevals = SCIPcliqueGetValues(clique); 284 285 for( v = 0; v < ncliquevars; ++v ) 286 { 287 var = cliquevars[v]; 288 289 /* variable is already fixed */ 290 if( SCIPvarGetUbLocal(var) < SCIPvarGetLbLocal(var) + 0.5 ) 291 { 292 SCIPdebugMsg(scip, "<%s> is already fixed to %g\n", SCIPvarGetName(var), SCIPvarGetUbLocal(var)); 293 294 /* clique variable is fixed to 1 */ 295 if( cliquevals[v] == (SCIPvarGetLbLocal(var) > 0.5) ) 296 { 297 assert(!alreadyone); 298 alreadyone = TRUE; 299 break; 300 } 301 continue; 302 } 303 304 obj = cliquevals[v] ? SCIPvarGetObj(var) : -SCIPvarGetObj(var); 305 306 /* @todo use a tiebreaker (locks?) */ 307 if( obj < bestobj ) 308 { 309 /* variable is not the best one in the clique anymore, fix it to 0 */ 310 if( bestpos >= 0 ) 311 { 312 if( cliquevals[bestpos] ) 313 { 314 SCIP_CALL( SCIPfixVarProbing(scip, cliquevars[bestpos], 0.0) ); 315 } 316 else 317 { 318 SCIP_CALL( SCIPfixVarProbing(scip, cliquevars[bestpos], 1.0) ); 319 } 320 SCIPdebugMsg(scip, "fixed <%s> to %g\n", SCIPvarGetName(cliquevars[bestpos]), SCIPvarGetUbLocal(cliquevars[bestpos])); 321 newnode = TRUE; 322 } 323 324 bestobj = obj; 325 bestpos = v; 326 } 327 /* variable is not the best one in the clique, fix it to 0 */ 328 else 329 { 330 assert(bestpos >= 0); 331 332 if( cliquevals[v] ) 333 { 334 SCIP_CALL( SCIPfixVarProbing(scip, var, 0.0) ); 335 } 336 else 337 { 338 SCIP_CALL( SCIPfixVarProbing(scip, var, 1.0) ); 339 } 340 SCIPdebugMsg(scip, "fixed <%s> to %g\n", SCIPvarGetName(var), SCIPvarGetUbLocal(var)); 341 newnode = TRUE; 342 } 343 } 344 /* we found a variable in the clique which is already fixed to 1 */ 345 if( alreadyone ) 346 { 347 /* fix (so far) best candidate to 0 */ 348 if( bestpos >= 0 ) 349 { 350 if( cliquevals[bestpos] ) 351 { 352 SCIP_CALL( SCIPfixVarProbing(scip, cliquevars[bestpos], 0.0) ); 353 } 354 else 355 { 356 SCIP_CALL( SCIPfixVarProbing(scip, cliquevars[bestpos], 1.0) ); 357 } 358 SCIPdebugMsg(scip, "fixed <%s> to %g\n", SCIPvarGetName(cliquevars[bestpos]), SCIPvarGetUbLocal(cliquevars[bestpos])); 359 newnode = TRUE; 360 } 361 362 /* fix all variables not yet processed to 0 */ 363 for( ; v < ncliquevars; ++v ) 364 { 365 var = cliquevars[v]; 366 367 if( SCIPvarGetUbLocal(var) < SCIPvarGetLbLocal(var) + 0.5 ) 368 continue; 369 370 if( cliquevals[v] ) 371 { 372 SCIP_CALL( SCIPfixVarProbing(scip, var, 0.0) ); 373 } 374 else 375 { 376 SCIP_CALL( SCIPfixVarProbing(scip, var, 1.0) ); 377 } 378 SCIPdebugMsg(scip, "fixed <%s> to %g\n", SCIPvarGetName(var), SCIPvarGetUbLocal(var)); 379 newnode = TRUE; 380 } 381 } 382 /* fix the best variable to 1 */ 383 else if( bestpos >= 0 ) 384 { 385 assert(bestpos <= ncliquevars); 386 387 probingdepthofonefix = SCIPgetProbingDepth(scip); 388 onefixvars[(*nonefixvars)] = cliquevars[bestpos]; 389 390 /* @todo should we even fix the best candidate to 1? */ 391 if( cliquevals[bestpos] ) 392 { 393 SCIP_CALL( SCIPfixVarProbing(scip, cliquevars[bestpos], 1.0) ); 394 onefixvals[(*nonefixvars)] = 1; 395 } 396 else 397 { 398 SCIP_CALL( SCIPfixVarProbing(scip, cliquevars[bestpos], 0.0) ); 399 onefixvals[(*nonefixvars)] = 0; 400 } 401 SCIPdebugMsg(scip, "fixed <%s> to %g*\n", SCIPvarGetName(cliquevars[bestpos]), SCIPvarGetUbLocal(cliquevars[bestpos])); 402 ++(*nonefixvars); 403 newnode = TRUE; 404 } 405 406 if( newnode ) 407 { 408 /* propagate fixings */ 409 SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, cutoff, NULL) ); 410 411 SCIPdebugMsg(scip, "propagate fixings of clique %d: cutoff=%u\n", c, *cutoff); 412 413 if( SCIPisStopped(scip) ) 414 break; 415 416 /* stop if we reached the depth limit */ 417 if( SCIP_MAXTREEDEPTH <= SCIPgetDepth(scip) ) 418 break; 419 420 /* probing detected infeasibility: backtrack */ 421 if( *cutoff ) 422 { 423 if( *nonefixvars > 0 ) 424 { 425 if( probingdepthofonefix > 0 ) 426 { 427 SCIP_CALL( SCIPbacktrackProbing(scip, probingdepthofonefix - 1) ); 428 probingdepthofonefix = 0; 429 ++nbacktracks; 430 431 /* because of the limited number of propagation rounds, it may happen that conflict analysis finds a 432 * valid global fixing for the last fixed variable that conflicts with applying the reverse fixing 433 * after backtracking; in that case, we ran into a deadend and stop 434 */ 435 if( SCIPvarGetLbLocal(onefixvars[*nonefixvars - 1]) < 1.5 - onefixvals[*nonefixvars - 1] 436 && SCIPvarGetUbLocal(onefixvars[*nonefixvars - 1]) > 0.5 - onefixvals[*nonefixvars - 1] ) 437 { 438 /* fix the last variable, which was fixed to 1 and led to the cutoff, to 0 */ 439 SCIP_CALL( SCIPfixVarProbing(scip, onefixvars[*nonefixvars - 1], 1.0 - onefixvals[*nonefixvars - 1]) ); 440 --(*nonefixvars); 441 442 /* propagate fixings */ 443 SCIP_CALL( SCIPpropagateProbing(scip, heurdata->maxproprounds, cutoff, NULL) ); 444 445 SCIPdebugMsg(scip, "backtrack %d was %sfeasible\n", nbacktracks, (*cutoff ? "in" : "")); 446 } 447 #ifndef NDEBUG 448 else 449 assert(*cutoff == TRUE); 450 #endif 451 } 452 if( *cutoff ) 453 { 454 SCIPdebugMsg(scip, "probing was infeasible after %d backtracks\n", nbacktracks); 455 #ifndef NOCONFLICT 456 if( enabledconflicts ) 457 { 458 SCIP_CONS* conflictcons; 459 char consname[SCIP_MAXSTRLEN]; 460 461 /* create own conflict */ 462 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "conf%" SCIP_LONGINT_FORMAT "", SCIPgetNNodes(scip)); 463 464 /* get variables for the conflict */ 465 for( i = 0; i < *nonefixvars; ++i ) 466 { 467 /* if the variable was fixed to 1 by the heuristic, get its negated variable */ 468 if( onefixvals[i] ) 469 { 470 SCIP_CALL( SCIPgetNegatedVar(scip, onefixvars[i], &onefixvars[i]) ); 471 } 472 } 473 474 /* create conflict constraint */ 475 SCIP_CALL( SCIPcreateConsLogicor(scip, &conflictcons, consname, *nonefixvars, onefixvars, 476 FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE, TRUE, TRUE, FALSE) ); 477 SCIP_CALL( SCIPaddConflict(scip, SCIPgetFocusNode(scip), conflictcons, NULL, SCIP_CONFTYPE_PROPAGATION, FALSE) ); 478 SCIPdebugPrintCons(scip, conflictcons, NULL); 479 } 480 #endif 481 break; 482 } 483 else if( nbacktracks > heurdata->maxbacktracks ) 484 { 485 SCIPdebugMsg(scip, "interrupt probing after %d backtracks\n", nbacktracks); 486 break; 487 } 488 } 489 /* we had a cutoff without a single one-fixing, so the current problem seems to be infeasible already */ 490 else 491 break; 492 } 493 494 SCIP_CALL( SCIPnewProbingNode(scip) ); 495 } 496 } 497 assert((*nonefixvars > 0) || probingdepthofonefix == 0 ); 498 499 SCIPfreeBufferArray(scip, &propagated); 500 SCIPfreeBufferArray(scip, &permutation); 501 SCIPfreeBufferArray(scip, &cliquesizes); 502 503 SCIPdebugMsg(scip, "fixed %d of %d variables in probing\n", v, SCIPgetNBinVars(scip)); 504 SCIPdebugMsg(scip, "applied %d of %d cliques in probing\n", c, ncliques); 505 SCIPdebugMsg(scip, "probing was %sfeasible\n", (*cutoff) ? "in" : ""); 506 507 return SCIP_OKAY; 508 } 509 510 /* 511 * Callback methods of primal heuristic 512 */ 513 514 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */ 515 static 516 SCIP_DECL_HEURCOPY(heurCopyClique) 517 { /*lint --e{715}*/ 518 assert(scip != NULL); 519 assert(heur != NULL); 520 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 521 522 /* call inclusion method of primal heuristic */ 523 SCIP_CALL( SCIPincludeHeurClique(scip) ); 524 525 return SCIP_OKAY; 526 } 527 528 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 529 static 530 SCIP_DECL_HEURFREE(heurFreeClique) 531 { /*lint --e{715}*/ 532 SCIP_HEURDATA* heurdata; 533 534 assert(heur != NULL); 535 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 536 assert(scip != NULL); 537 538 /* free heuristic data */ 539 heurdata = SCIPheurGetData(heur); 540 assert(heurdata != NULL); 541 542 SCIPfreeBlockMemory(scip, &heurdata); 543 SCIPheurSetData(heur, NULL); 544 545 return SCIP_OKAY; 546 } 547 548 549 /** initialization method of primal heuristic (called after problem was transformed) */ 550 static 551 SCIP_DECL_HEURINIT(heurInitClique) 552 { /*lint --e{715}*/ 553 SCIP_HEURDATA* heurdata; 554 555 assert(heur != NULL); 556 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 557 assert(scip != NULL); 558 559 /* reset heuristic data */ 560 heurdata = SCIPheurGetData(heur); 561 assert(heurdata != NULL); 562 563 heurdata->usednodes = 0; 564 565 return SCIP_OKAY; 566 } 567 568 /** execution method of primal heuristic */ 569 static 570 SCIP_DECL_HEUREXEC(heurExecClique) 571 { /*lint --e{715}*/ 572 SCIP_HEURDATA* heurdata; 573 SCIP_VAR** vars; 574 SCIP_Real lowerbound; 575 int nvars; 576 int nbinvars; 577 int oldnpscands; 578 int npscands; 579 int i; 580 SCIP_Bool cutoff; 581 SCIP_Bool lperror; 582 583 SCIP_VAR** onefixvars; 584 SCIP_Shortbool* onefixvals; 585 int nonefixvars; 586 SCIP_Bool enabledconflicts; 587 SCIP_LPSOLSTAT lpstatus; 588 SCIP_CONS* conflictcons; 589 SCIP_Bool solvelp; 590 char consname[SCIP_MAXSTRLEN]; 591 592 SCIP_Longint nstallnodes; 593 594 assert(heur != NULL); 595 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0); 596 assert(scip != NULL); 597 assert(result != NULL); 598 599 *result = SCIP_DIDNOTRUN; 600 601 /* get heuristic's data */ 602 heurdata = SCIPheurGetData(heur); 603 assert(heurdata != NULL); 604 605 nbinvars = SCIPgetNBinVars(scip); 606 607 if( nbinvars < 2 ) 608 return SCIP_OKAY; 609 610 /* check for necessary information to apply this heuristic */ 611 if( SCIPgetNCliques(scip) == 0 ) 612 return SCIP_OKAY; 613 614 lowerbound = SCIPgetLowerbound(scip); 615 616 /* calculate the maximal number of branching nodes until heuristic is aborted */ 617 nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip)); 618 619 /* reward clique heuristic if it succeeded often */ 620 nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0)); 621 nstallnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-MIP as 100 nodes */ 622 nstallnodes += heurdata->nodesofs; 623 624 /* determine the node limit for the current process */ 625 nstallnodes -= heurdata->usednodes; 626 nstallnodes = MIN(nstallnodes, heurdata->maxnodes); 627 628 /* check whether we have enough nodes left to call subproblem solving */ 629 if( nstallnodes < heurdata->minnodes ) 630 { 631 SCIPdebugMsg(scip, "skipping " HEUR_NAME ": nstallnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->minnodes); 632 return SCIP_OKAY; 633 } 634 635 oldnpscands = SCIPgetNPseudoBranchCands(scip); 636 onefixvars = NULL; 637 onefixvals = NULL; 638 639 /* disable conflict analysis, because we can it better than SCIP itself, cause we have more information */ 640 SCIP_CALL( SCIPgetBoolParam(scip, "conflict/enable", &enabledconflicts) ); 641 642 if( !SCIPisParamFixed(scip, "conflict/enable") ) 643 { 644 SCIP_CALL( SCIPsetBoolParam(scip, "conflict/enable", FALSE) ); 645 } 646 647 solvelp = SCIPhasCurrentNodeLP(scip); 648 649 if( !SCIPisLPConstructed(scip) && solvelp ) 650 { 651 SCIP_CALL( SCIPconstructLP(scip, &cutoff) ); 652 653 /* manually cut off the node if the LP construction detected infeasibility (heuristics cannot return such a result) */ 654 if( cutoff ) 655 { 656 SCIP_CALL( SCIPcutoffNode(scip, SCIPgetCurrentNode(scip)) ); 657 goto TERMINATE; 658 } 659 660 SCIP_CALL( SCIPflushLP(scip) ); 661 } 662 663 /* refresh nbinvars in case constructLP suddenly added new ones */ 664 nbinvars = SCIPgetNBinVars(scip); 665 assert(nbinvars >= 2); 666 667 *result = SCIP_DIDNOTFIND; 668 669 /* start probing */ 670 SCIP_CALL( SCIPstartProbing(scip) ); 671 672 #ifdef COLLECTSTATISTICS 673 SCIPenableVarHistory(scip); 674 #endif 675 676 /* allocate memory for all variables which will be fixed to one during probing */ 677 SCIP_CALL(SCIPallocBufferArray(scip, &onefixvars, nbinvars) ); 678 SCIP_CALL(SCIPallocBufferArray(scip, &onefixvals, nbinvars) ); 679 nonefixvars = 0; 680 681 /* apply fixings due to clique information */ 682 SCIP_CALL( applyCliqueFixings(scip, heurdata, enabledconflicts, onefixvars, onefixvals, &nonefixvars, &cutoff) ); 683 684 if( cutoff || SCIPisStopped(scip) ) 685 goto TERMINATE; 686 687 /* check that we had enough fixings */ 688 npscands = SCIPgetNPseudoBranchCands(scip); 689 690 SCIPdebugMsg(scip, "npscands=%d, oldnpscands=%d, heurdata->minintfixingrate=%g\n", npscands, oldnpscands, heurdata->minintfixingrate); 691 692 if( npscands > oldnpscands * (1.0 - heurdata->minintfixingrate) ) 693 { 694 if( heurdata->uselockfixings && npscands <= 2.0 * oldnpscands * (1.0 - heurdata->minintfixingrate) ) 695 { 696 SCIP_Bool allrowsfulfilled = FALSE; 697 698 SCIP_CALL( SCIPapplyLockFixings(scip, NULL, &cutoff, &allrowsfulfilled) ); 699 700 if( cutoff || SCIPisStopped(scip) ) 701 { 702 SCIPdebugMsg(scip, "cutoff or timeout in locks fixing\n"); 703 goto TERMINATE; 704 } 705 706 npscands = SCIPgetNPseudoBranchCands(scip); 707 708 SCIPdebugMsg(scip, "after lockfixings: npscands=%d, oldnpscands=%d, allrowsfulfilled=%u, heurdata->minintfixingrate=%g\n", 709 npscands, oldnpscands, allrowsfulfilled, heurdata->minintfixingrate); 710 711 if( !allrowsfulfilled && npscands > oldnpscands * (1 - heurdata->minintfixingrate) ) 712 { 713 SCIPdebugMsg(scip, "--> too few fixings\n"); 714 715 goto TERMINATE; 716 } 717 } 718 else 719 { 720 SCIPdebugMsg(scip, "--> too few fixings\n"); 721 722 goto TERMINATE; 723 } 724 } 725 726 /*************************** Probing LP Solving ***************************/ 727 728 lpstatus = SCIP_LPSOLSTAT_ERROR; 729 lperror = FALSE; 730 731 /* solve lp only if the problem is still feasible */ 732 if( solvelp ) 733 { 734 char strbuf[SCIP_MAXSTRLEN]; 735 int ncols; 736 737 /* print message if relatively large LP is solved from scratch, since this could lead to a longer period during 738 * which the user sees no output; more detailed probing stats only in debug mode */ 739 ncols = SCIPgetNLPCols(scip); 740 if( !SCIPisLPSolBasic(scip) && ncols > 1000 ) 741 { 742 int nunfixedcols = SCIPgetNUnfixedLPCols(scip); 743 744 if( nunfixedcols > 0.5 * ncols ) 745 { 746 SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, 747 "Heuristic " HEUR_NAME " solving LP from scratch with %.1f %% unfixed columns (%d of %d) ...\n", 748 100.0 * (nunfixedcols / (SCIP_Real)ncols), nunfixedcols, ncols); 749 } 750 } 751 SCIPdebugMsg(scip, "Heuristic " HEUR_NAME " probing LP: %s\n", 752 SCIPsnprintfProbingStats(scip, strbuf, SCIP_MAXSTRLEN)); 753 754 /* solve LP; errors in the LP solver should not kill the overall solving process, if the LP is just needed for a 755 * heuristic. hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, 756 * SCIP will stop. 757 */ 758 SCIPdebugMsg(scip, "starting solving clique-lp at time %g\n", SCIPgetSolvingTime(scip)); 759 #ifdef NDEBUG 760 { 761 SCIP_Bool retstat; 762 retstat = SCIPsolveProbingLP(scip, -1, &lperror, NULL); 763 if( retstat != SCIP_OKAY ) 764 { 765 SCIPwarningMessage(scip, "Error while solving LP in clique heuristic; LP solve terminated with code <%d>\n", 766 retstat); 767 } 768 } 769 #else 770 SCIP_CALL( SCIPsolveProbingLP(scip, -1, &lperror, NULL) ); 771 #endif 772 SCIPdebugMsg(scip, "ending solving clique-lp at time %g\n", SCIPgetSolvingTime(scip)); 773 774 lpstatus = SCIPgetLPSolstat(scip); 775 776 SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip)); 777 SCIPdebugMsg(scip, " -> error=%u, status=%d\n", lperror, lpstatus); 778 } 779 780 /* check if this is a feasible solution */ 781 if( lpstatus == SCIP_LPSOLSTAT_OPTIMAL && !lperror ) 782 { 783 SCIP_SOL* sol; 784 SCIP_Bool stored; 785 SCIP_Bool success; 786 787 assert(!cutoff); 788 789 lowerbound = SCIPgetLPObjval(scip); 790 791 /* create a solution from the current LP solution */ 792 SCIP_CALL( SCIPcreateSol(scip, &sol, heur) ); 793 SCIP_CALL( SCIPlinkLPSol(scip, sol) ); 794 795 SCIP_CALL( SCIProundSol(scip, sol, &success) ); 796 797 if( success ) 798 { 799 SCIPdebugMsg(scip, "clique heuristic found roundable primal solution: obj=%g\n", 800 SCIPgetSolOrigObj(scip, sol)); 801 802 /* check solution for feasibility, and add it to solution store if possible. 803 * Neither integrality nor feasibility of LP rows have to be checked, because they 804 * are guaranteed by the heuristic at this stage. 805 */ 806 #ifdef SCIP_DEBUG 807 SCIP_CALL( SCIPtrySol(scip, sol, TRUE, TRUE, TRUE, TRUE, TRUE, &stored) ); 808 #else 809 SCIP_CALL( SCIPtrySol(scip, sol, FALSE, FALSE, TRUE, FALSE, FALSE, &stored) ); 810 #endif 811 812 if( stored ) 813 { 814 SCIPdebugMsg(scip, "found feasible solution:\n"); 815 SCIPdebug( SCIP_CALL( SCIPprintSol(scip, sol, NULL, FALSE) ) ); 816 *result = SCIP_FOUNDSOL; 817 } 818 819 SCIP_CALL( SCIPfreeSol(scip, &sol) ); 820 821 /* we found a solution, so we are done */ 822 goto TERMINATE; 823 } 824 825 SCIP_CALL( SCIPfreeSol(scip, &sol) ); 826 } 827 /*************************** END Probing LP Solving ***************************/ 828 829 /*************************** Create Conflict ***************************/ 830 if( enabledconflicts && SCIPallColsInLP(scip) && 831 (lpstatus == SCIP_LPSOLSTAT_INFEASIBLE || lpstatus == SCIP_LPSOLSTAT_OBJLIMIT) ) 832 { 833 #ifndef NOCONFLICT 834 /* create own conflict */ 835 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "conf%" SCIP_LONGINT_FORMAT "", SCIPgetNNodes(scip)); 836 837 /* get variables for the conflict */ 838 for( i = 0; i < nonefixvars; ++i ) 839 { 840 /* if the variable was fixed to 1 by the heuristic, get its negated variable */ 841 if( onefixvals[i] ) 842 { 843 SCIP_CALL( SCIPgetNegatedVar(scip, onefixvars[i], &onefixvars[i]) ); 844 } 845 } 846 847 /* create conflict constraint */ 848 SCIP_CALL( SCIPcreateConsLogicor(scip, &conflictcons, consname, nonefixvars, onefixvars, 849 FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE, TRUE, TRUE, FALSE) ); 850 SCIP_CALL( SCIPaddConflict(scip, SCIPgetFocusNode(scip), conflictcons, NULL, SCIP_CONFTYPE_INFEASLP, FALSE) ); 851 SCIPdebugPrintCons(scip, conflictcons, NULL); 852 #endif 853 goto TERMINATE; 854 } 855 /*************************** End Conflict ***************************/ 856 857 /*************************** Start Subscip Solving ***************************/ 858 /* no solution has been found yet and the subproblem is still feasible --> fix all other variables by subscip if 859 * necessary 860 */ 861 if( !lperror ) 862 { 863 SCIP* subscip; 864 SCIP_VAR** subvars; 865 SCIP_HASHMAP* varmap; 866 SCIP_Bool valid; 867 868 /* check whether there is enough time and memory left */ 869 SCIP_CALL( SCIPcheckCopyLimits(scip, &valid) ); 870 871 if( !valid ) 872 goto TERMINATE; 873 874 /* get all variables */ 875 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) ); 876 877 /* create subproblem */ 878 SCIP_CALL( SCIPcreate(&subscip) ); 879 880 /* allocate temporary memory for subscip variables */ 881 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) ); 882 883 /* create the variable mapping hash map */ 884 SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(subscip), nvars) ); 885 886 SCIP_CALL( SCIPcopyConsCompression(scip, subscip, varmap, NULL, "_clique", NULL, NULL, 0, FALSE, FALSE, FALSE, 887 TRUE, &valid) ); 888 889 if( heurdata->copycuts ) 890 { 891 /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */ 892 SCIP_CALL( SCIPcopyCuts(scip, subscip, varmap, NULL, FALSE, NULL) ); 893 } 894 895 for( i = 0; i < nvars; i++ ) 896 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, vars[i]); 897 898 /* free hash map */ 899 SCIPhashmapFree(&varmap); 900 901 /* do not abort subproblem on CTRL-C */ 902 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) ); 903 904 #ifdef SCIP_DEBUG 905 /* for debugging, enable full output */ 906 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) ); 907 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) ); 908 #else 909 /* disable statistic timing inside sub SCIP and output to console */ 910 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) ); 911 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) ); 912 #endif 913 914 /* set limits for the subproblem */ 915 SCIP_CALL( SCIPcopyLimits(scip, subscip) ); 916 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", nstallnodes) ); 917 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", heurdata->maxnodes) ); 918 919 /* speed up sub-SCIP by not checking dual LP feasibility */ 920 SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) ); 921 922 /* forbid call of heuristics and separators solving sub-CIPs */ 923 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) ); 924 925 /* disable cutting plane separation */ 926 SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) ); 927 928 /* disable expensive presolving */ 929 SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) ); 930 931 /* use inference branching */ 932 if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") ) 933 { 934 SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) ); 935 } 936 937 /* if there is already a solution, add an objective cutoff */ 938 if( SCIPgetNSols(scip) > 0 ) 939 { 940 SCIP_Real upperbound; 941 SCIP_Real minimprove; 942 SCIP_Real cutoffbound; 943 944 minimprove = heurdata->minimprove; 945 assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) ); 946 947 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip); 948 949 if( !SCIPisInfinity(scip, -1.0 * lowerbound) ) 950 { 951 cutoffbound = (1-minimprove) * SCIPgetUpperbound(scip) + minimprove * lowerbound; 952 } 953 else 954 { 955 if( SCIPgetUpperbound ( scip ) >= 0 ) 956 cutoffbound = (1 - minimprove) * SCIPgetUpperbound(scip); 957 else 958 cutoffbound = (1 + minimprove) * SCIPgetUpperbound(scip); 959 } 960 cutoffbound = MIN(upperbound, cutoffbound); 961 SCIP_CALL( SCIPsetObjlimit(subscip, cutoffbound) ); 962 SCIPdebugMsg(scip, "setting objlimit for subscip to %g\n", cutoffbound); 963 } 964 965 SCIPdebugMsg(scip, "starting solving clique-submip at time %g\n", SCIPgetSolvingTime(scip)); 966 967 /* solve the subproblem */ 968 /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic. 969 * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. 970 */ 971 SCIP_CALL_ABORT( SCIPpresolve(subscip) ); 972 973 SCIPdebugMsg(scip, "clique heuristic presolved subproblem at time %g : %d vars, %d cons; fixing value = %g\n", SCIPgetSolvingTime(scip), SCIPgetNVars(subscip), SCIPgetNConss(subscip), ((nvars - SCIPgetNVars(subscip)) / (SCIP_Real)nvars)); 974 975 /* after presolving, we should have at least reached a certain fixing rate over ALL variables (including continuous) 976 * to ensure that not only the MIP but also the LP relaxation is easy enough 977 */ 978 if( ((nvars - SCIPgetNVars(subscip)) / (SCIP_Real)nvars) >= heurdata->minmipfixingrate ) 979 { 980 SCIP_Bool success; 981 982 SCIPdebugMsg(scip, "solving subproblem: nstallnodes=%" SCIP_LONGINT_FORMAT ", maxnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->maxnodes); 983 984 SCIP_CALL_ABORT( SCIPsolve(subscip) ); 985 SCIPdebug( SCIP_CALL( SCIPprintStatistics(subscip, NULL) ) ); 986 987 SCIPdebugMsg(scip, "ending solving clique-submip at time %g, status = %d\n", SCIPgetSolvingTime(scip), SCIPgetStatus(subscip)); 988 989 /* check, whether a solution was found; due to numerics, it might happen that not all solutions are feasible -> 990 * try all solutions until one was accepted 991 */ 992 SCIP_CALL( SCIPtranslateSubSols(scip, subscip, heur, subvars, &success, NULL) ); 993 if( success ) 994 *result = SCIP_FOUNDSOL; 995 996 #ifndef NOCONFLICT 997 /* if subscip was infeasible, add a conflict */ 998 if( SCIPgetStatus(subscip) == SCIP_STATUS_INFEASIBLE ) 999 { 1000 /* create own conflict */ 1001 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "conf%" SCIP_LONGINT_FORMAT "", SCIPgetNNodes(scip)); 1002 1003 /* get variables for the conflict */ 1004 for( i = 0; i < nonefixvars; ++i ) 1005 { 1006 /* if the variable was fixed to 1 by the heuristic, get its negated variable */ 1007 if( onefixvals[i] ) 1008 { 1009 SCIP_CALL( SCIPgetNegatedVar(scip, onefixvars[i], &onefixvars[i]) ); 1010 } 1011 } 1012 1013 /* create conflict constraint */ 1014 SCIP_CALL( SCIPcreateConsLogicor(scip, &conflictcons, consname, nonefixvars, onefixvars, 1015 FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE, TRUE, TRUE, FALSE) ); 1016 SCIP_CALL( SCIPaddConsNode(scip, SCIPgetFocusNode(scip), conflictcons, NULL) ); 1017 SCIPdebugPrintCons(scip, conflictcons, NULL); 1018 SCIP_CALL( SCIPreleaseCons(scip, &conflictcons) ); 1019 } 1020 #endif 1021 } 1022 1023 #ifdef SCIP_DEBUG 1024 SCIP_CALL( SCIPprintStatistics(subscip, NULL) ); 1025 #endif 1026 1027 /* free subproblem */ 1028 SCIPfreeBufferArray(scip, &subvars); 1029 SCIP_CALL( SCIPfree(&subscip) ); 1030 } 1031 1032 /*************************** End Subscip Solving ***************************/ 1033 1034 TERMINATE: 1035 1036 /* reset the conflict analysis */ 1037 if( !SCIPisParamFixed(scip, "conflict/enable") ) 1038 { 1039 SCIP_CALL( SCIPsetBoolParam(scip, "conflict/enable", enabledconflicts) ); 1040 } 1041 1042 /* free conflict variables */ 1043 SCIPfreeBufferArrayNull(scip, &onefixvals); 1044 SCIPfreeBufferArrayNull(scip, &onefixvars); 1045 1046 /* end probing */ 1047 if( SCIPinProbing(scip) ) 1048 { 1049 SCIP_CALL( SCIPendProbing(scip) ); 1050 } 1051 1052 return SCIP_OKAY; 1053 } 1054 1055 /* 1056 * primal heuristic specific interface methods 1057 */ 1058 1059 /** creates the clique primal heuristic and includes it in SCIP */ 1060 SCIP_RETCODE SCIPincludeHeurClique( 1061 SCIP* scip /**< SCIP data structure */ 1062 ) 1063 { 1064 SCIP_HEURDATA* heurdata; 1065 SCIP_HEUR* heur; 1066 1067 /* create clique primal heuristic data */ 1068 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 1069 1070 /* include primal heuristic */ 1071 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 1072 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 1073 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecClique, heurdata) ); 1074 1075 assert(heur != NULL); 1076 1077 /* set non-NULL pointers to callback methods */ 1078 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyClique) ); 1079 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeClique) ); 1080 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitClique) ); 1081 1082 /* add clique primal heuristic parameters */ 1083 1084 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minintfixingrate", 1085 "minimum percentage of integer variables that have to be fixable", 1086 &heurdata->minintfixingrate, FALSE, DEFAULT_MININTFIXINGRATE, 0.0, 1.0, NULL, NULL) ); 1087 1088 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minmipfixingrate", 1089 "minimum percentage of fixed variables in the sub-MIP", 1090 &heurdata->minmipfixingrate, FALSE, DEFAULT_MINMIPFIXINGRATE, 0.0, 1.0, NULL, NULL) ); 1091 1092 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes", 1093 "maximum number of nodes to regard in the subproblem", 1094 &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 1095 1096 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs", 1097 "number of nodes added to the contingent of the total nodes", 1098 &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 1099 1100 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes", 1101 "minimum number of nodes required to start the subproblem", 1102 &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 1103 1104 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot", 1105 "contingent of sub problem nodes in relation to the number of nodes of the original problem", 1106 &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) ); 1107 1108 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove", 1109 "factor by which " HEUR_NAME " heuristic should at least improve the incumbent", 1110 &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) ); 1111 1112 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxproprounds", 1113 "maximum number of propagation rounds during probing (-1 infinity)", 1114 &heurdata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -1, INT_MAX/4, NULL, NULL) ); 1115 1116 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts", 1117 "should all active cuts from cutpool be copied to constraints in subproblem?", 1118 &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) ); 1119 1120 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/uselockfixings", 1121 "should more variables be fixed based on variable locks if the fixing rate was not reached?", 1122 &heurdata->uselockfixings, TRUE, DEFAULT_USELOCKFIXINGS, NULL, NULL) ); 1123 1124 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxbacktracks", 1125 "maximum number of backtracks during the fixing process", 1126 &heurdata->maxbacktracks, TRUE, DEFAULT_MAXBACKTRACKS, -1, INT_MAX/4, NULL, NULL) ); 1127 1128 return SCIP_OKAY; 1129 } 1130