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_dualval.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief dualval primal heuristic 28 * @author Tobias Buchwald 29 * 30 * This heuristic tries to find solutions by taking the LP or NLP, rounding solution values, fixing the variables to the 31 * rounded values and then changing some of the values.To determine which variable is changed we give each variable a 32 * ranking dependent on its dualvalue. We work with a transformed problem that is always feasible and has objective = 0 33 * iff the original problem is also feasible. Thus we cannot expect to find really good solutions. 34 */ 35 36 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 37 38 #include "blockmemshell/memory.h" 39 #include "scip/type_expr.h" 40 #include "scip/cons_indicator.h" 41 #include "scip/cons_knapsack.h" 42 #include "scip/cons_linear.h" 43 #include "scip/cons_logicor.h" 44 #include "scip/cons_setppc.h" 45 #include "scip/cons_varbound.h" 46 #include "scip/heur_dualval.h" 47 #include "scip/pub_cons.h" 48 #include "scip/pub_event.h" 49 #include "scip/pub_heur.h" 50 #include "scip/pub_message.h" 51 #include "scip/pub_misc.h" 52 #include "scip/pub_misc_sort.h" 53 #include "scip/pub_nlp.h" 54 #include "scip/pub_sol.h" 55 #include "scip/pub_var.h" 56 #include "scip/scip_branch.h" 57 #include "scip/scip_cons.h" 58 #include "scip/scip_copy.h" 59 #include "scip/scip_event.h" 60 #include "scip/scip_general.h" 61 #include "scip/scip_heur.h" 62 #include "scip/scip_lp.h" 63 #include "scip/scip_mem.h" 64 #include "scip/scip_message.h" 65 #include "scip/scip_nlp.h" 66 #include "scip/scip_nlpi.h" 67 #include "scip/scip_numerics.h" 68 #include "scip/scip_param.h" 69 #include "scip/scip_prob.h" 70 #include "scip/scip_sol.h" 71 #include "scip/scip_solve.h" 72 #include "scip/scip_solvingstats.h" 73 #include "scip/scip_var.h" 74 #include <string.h> 75 76 #define HEUR_NAME "dualval" 77 #define HEUR_DESC "primal heuristic using dual values" 78 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS 79 #define HEUR_PRIORITY -10 80 #define HEUR_FREQ -1 81 #define HEUR_FREQOFS 0 82 #define HEUR_MAXDEPTH -1 83 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE 84 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */ 85 86 #define EVENTHDLR_NAME "lpsol_dualval" 87 #define EVENTHDLR_DESC "event handler for lp solution found" 88 89 /* default values for user parameters */ 90 /* boolean parameters */ 91 #define DEFAULT_FORCEIMPROVEMENTS FALSE /**< exit if objective doesn't improve */ 92 #define DEFAULT_ONLYCHEAPER TRUE /**< add constraint to ensure that discrete vars are improving */ 93 #define DEFAULT_ONLYLEAVES FALSE /**< disable the heuristic if it was not called at a leaf of the B&B tree */ 94 #define DEFAULT_RELAXINDICATORS FALSE /**< relax the indicator variables by introducing continuous copies */ 95 #define DEFAULT_RELAXCONTVARS FALSE /**< enable relaxation of continous variables */ 96 97 /* integer parameters */ 98 #define DEFAULT_HEURVERBLEVEL 0 /**< verblevel of the heuristic, default is 0 to display nothing */ 99 #define DEFAULT_NLPVERBLEVEL 0 /**< verblevel of the nlp solver, can be 0 or 1 */ 100 #define DEFAULT_RANKVALUE 10 /**< number of ranks that should be displayed when the heuristic is called */ 101 #define DEFAULT_MAXCALLS 25 /**< maximal number of recursive calls of the heuristic (if dynamicdepth is off) */ 102 #define DEFAULT_DYNAMICDEPTH 0 /**< says if and how the recursion depth is computed at runtime */ 103 #define DEFAULT_MAXEQUALRANKS 50 /**< maximal number of variables that may have maximal rank, quit if there are more, turn off by setting -1 */ 104 105 /* real value parameters */ 106 #define DEFAULT_MINGAP 5.0 /**< minimal gap for which we still run the heuristic, if gap is less we return without doing anything */ 107 #define DEFAULT_LAMBDASLACK 1.0 /**< value added to objective of slack variables, must not be zero */ 108 #define DEFAULT_LAMBDAOBJ 0.0 /**< scaling factor for the objective function */ 109 110 111 /**primal heuristic data */ 112 struct SCIP_HeurData 113 { 114 SCIP* subscip; /**< copy of CIP */ 115 SCIP_VAR** integervars; /**< array of all binary and integer variables of the original scip */ 116 SCIP_HASHMAP* varsciptosubscip; /**< mapping variables in SCIP to sub-SCIP variables */ 117 SCIP_HASHMAP* varsubsciptoscip; /**< mapping variables in sub-SCIP to SCIP variables */ 118 SCIP_HASHMAP* origsubscipConsMap; /**< maps constraints from the transformed problem to corresponding constraints in subproblem */ 119 SCIP_HASHMAP* switchedvars; /**< stores the last value of switched var to avoid cycling */ 120 SCIP_HASHMAP* switchedvars2; /**< stores the second last value of switched vars to avoid cycling */ 121 SCIP_HASHMAP* relaxcons; /**< maps subscip variables to their relaxation constraints */ 122 SCIP_HASHMAP* relaxconsindi; /**< maps indicator variables and their copies to relaxation constraint */ 123 SCIP_HASHMAP* slacktoindivarsmap; /**< maps slack variables of indicator constraint to indicator variable */ 124 SCIP_HASHMAP* indicators; /**< maps indicator variables to their indicator constraint */ 125 SCIP_HASHMAP* conss2nlrow; /**< maps constraint to the corresponding nlrow */ 126 SCIP_HASHMAP* dualvalues; /**< maps constraints of the subscip to their dual values */ 127 SCIP_HASHMAP* slack2var; /**< maps slack variables to the variable they actually relax */ 128 SCIP_HASHMAP* indicopymap; /**< maps indicator variables to their copy variables */ 129 SCIP_HASHMAP* indicopymapback; /**< maps copy variables to their indicator variables */ 130 SCIP_HASHMAP* slackvarlbMap; /**< mapping used indicators to slack variables lower bound*/ 131 SCIP_HASHMAP* slackvarubMap; /**< mapping used indicators to slack variables upper bound*/ 132 SCIP_CONS* objbound; /**< contraint for upper bound of the objective function */ 133 SCIP_Real prevobjective; /**< stores objective value (of the original) so we know if it improved */ 134 SCIP_Real mingap; /**< don't run the heuristic if the gap is less than mingap */ 135 SCIP_Real lambdaslack; /**< the value added to the objective function */ 136 SCIP_Real lambdaobj; /**< the value the original objective function is scaled with */ 137 int integervarssize; /**< size of integervars array */ 138 int nintegervars; /**< number of integer variables in the original problem */ 139 int heurverblevel; /**< verblevel, range is 0 to 4 */ 140 int nlpverblevel; /**< sets verblevel of the included nlp */ 141 int rankvalue; /**< print out the 'rankvalue' highest ranks during iterations */ 142 int maxcalls; /**< maximum number of allowed iterations */ 143 int nonimprovingRounds; /**< nr of rounds, where the algorithm has not improved */ 144 int dynamicdepth; /**< how should the number of calls be computed? */ 145 int maxequalranks; /**< maximum number of variables that may have maximal (absolute) rank */ 146 int nvars; /**< number of active transformed variables in SCIP */ 147 int nsubvars; /**< number of original variables in sub-SCIP */ 148 int usedcalls; /**< number of currently used iterations */ 149 SCIP_Bool isnlp; /**< tells us, whether we have nonlinearities in our program or not */ 150 SCIP_Bool forceimprovements; /**< whether we exit on nonimproving objective in the relaxation or not */ 151 SCIP_Bool prevInfeasible; /**< will tell us if the previous call led to an infeasible fixing */ 152 SCIP_Bool solfound; /**< parameter says, if we already found a solution and have to go back */ 153 SCIP_Bool subscipisvalid; /**< whether all constraints have been copied */ 154 SCIP_Bool switchdifferent; /**< tells us that we want to go up one level and switch another variable */ 155 SCIP_Bool triedsetupsubscip; /**< whether we have tried to setup a sub-SCIP */ 156 SCIP_Bool onlycheaper; /**< add constraint to ensure that discrete vars are improving */ 157 SCIP_Bool onlyleaves; /**< don't use heuristic if we are not in a leaf of the B&B tree */ 158 SCIP_Bool relaxindicators; /**< additionally relax indicator variables */ 159 SCIP_Bool relaxcontvars; /**< additionally relax continous variables */ 160 }; 161 162 /* 163 * event handler method 164 */ 165 166 /** initialization method of event handler (called after problem was transformed) */ 167 static 168 SCIP_DECL_EVENTINIT(eventInitLPsol) 169 { /*lint --e{715}*/ 170 assert(scip != NULL); 171 assert(eventhdlr != NULL); 172 173 /* notify SCIP that your event handler wants to react on the event type best solution found */ 174 SCIP_CALL( SCIPcatchEvent(scip, SCIP_EVENTTYPE_FIRSTLPSOLVED | SCIP_EVENTTYPE_LPSOLVED, eventhdlr, NULL, NULL) ); 175 176 return SCIP_OKAY; 177 } 178 179 /** deinitialization method of event handler (called before transformed problem is freed) */ 180 static 181 SCIP_DECL_EVENTEXIT(eventExitLPsol) 182 { /*lint --e{715}*/ 183 assert(scip != NULL); 184 assert(eventhdlr != NULL); 185 186 /* notify SCIP that your event handler wants to drop the event type best solution found */ 187 SCIP_CALL( SCIPdropEvent(scip, SCIP_EVENTTYPE_FIRSTLPSOLVED | SCIP_EVENTTYPE_LPSOLVED, eventhdlr, NULL, -1) ); 188 189 return SCIP_OKAY; 190 } 191 192 /** execution method of event handler */ 193 static 194 SCIP_DECL_EVENTEXEC(eventExecLPsol) 195 { /*lint --e{715}*/ 196 int i; 197 int nsubconss; 198 SCIP_HEURDATA* heurdata; 199 SCIP_CONS** subconss; 200 SCIP_Real* dualval; 201 202 assert(eventhdlr != NULL); 203 assert(event != NULL); 204 assert(scip != NULL); 205 assert(SCIPgetStage(scip) == SCIP_STAGE_SOLVING); 206 207 heurdata = (SCIP_HEURDATA* )SCIPeventhdlrGetData(eventhdlr); 208 nsubconss = SCIPgetNOrigConss(heurdata->subscip); 209 subconss = SCIPgetOrigConss(heurdata->subscip); 210 211 /* free memory of all entries and clear the hashmap before filling it */ 212 for( i = 0; i < nsubconss; i++ ) 213 { 214 dualval = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, subconss[i]); 215 if( dualval != NULL ) 216 SCIPfreeBlockMemoryArray(heurdata->subscip, &dualval, 1); 217 } 218 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->dualvalues) ); 219 220 /* insert dualvalues from LP into a hashmap */ 221 for( i = 0; i < nsubconss; i++ ) 222 { 223 SCIP_CONS* transcons = NULL; 224 SCIP_CALL( SCIPgetTransformedCons(heurdata->subscip, subconss[i], &transcons) ); 225 226 if( transcons == NULL ) 227 continue; 228 229 if( SCIPconsGetHdlr(transcons) != SCIPfindConshdlr(heurdata->subscip, "linear") ) 230 continue; 231 232 SCIP_CALL( SCIPallocBlockMemoryArray(heurdata->subscip, &dualval, 1) ); /*lint !e506*/ 233 *dualval = -SCIPgetDualsolLinear(heurdata->subscip, transcons ); 234 SCIP_CALL( SCIPhashmapInsert(heurdata->dualvalues, subconss[i], dualval) ); 235 } 236 if( heurdata->heurverblevel > 2 ) 237 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "LP solved event!\n"); 238 239 return SCIP_OKAY; 240 } 241 242 /** includes event handler for best solution found */ 243 static 244 SCIP_RETCODE SCIPincludeEventHdlrLPsol( 245 SCIP* scip, /**< SCIP data structure */ 246 SCIP_HEURDATA* heurdata /**< heuristic data */ 247 ) 248 { 249 SCIP_EVENTHDLRDATA* eventhdlrdata; 250 SCIP_EVENTHDLR* eventhdlr = NULL; 251 252 eventhdlrdata = (SCIP_EVENTHDLRDATA*)heurdata; 253 254 /* create event handler */ 255 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecLPsol, eventhdlrdata) ); 256 assert(eventhdlr != NULL); 257 258 SCIP_CALL( SCIPsetEventhdlrInit(scip, eventhdlr, eventInitLPsol) ); 259 SCIP_CALL( SCIPsetEventhdlrExit(scip, eventhdlr, eventExitLPsol) ); 260 261 return SCIP_OKAY; 262 } 263 264 /* 265 * Local methods 266 */ 267 268 /** releases all variables or constraints from given hash map */ 269 static 270 SCIP_RETCODE releaseHashmapEntries( 271 SCIP* scip, /**< SCIP data structure */ 272 SCIP_HASHMAP* hashmap, /**< hashmap */ 273 SCIP_Bool isvarmap /**< are the entries variables or constraints? */ 274 ) 275 { 276 int nentries; 277 int i; 278 279 assert(scip != NULL); 280 assert(hashmap != NULL); 281 282 nentries = SCIPhashmapGetNEntries(hashmap); 283 284 for( i = 0; i < nentries; ++i ) 285 { 286 SCIP_HASHMAPENTRY* entry; 287 entry = SCIPhashmapGetEntry(hashmap, i); 288 289 if( entry != NULL ) 290 { 291 if( isvarmap ) 292 { 293 SCIP_VAR* var; 294 var = (SCIP_VAR*) SCIPhashmapEntryGetImage(entry); 295 296 SCIP_CALL( SCIPreleaseVar(scip, &var) ); 297 } 298 else 299 { 300 SCIP_CONS* cons; 301 cons = (SCIP_CONS*) SCIPhashmapEntryGetImage(entry); 302 303 SCIP_CALL( SCIPreleaseCons(scip, &cons) ); 304 } 305 } 306 } 307 308 return SCIP_OKAY; 309 } 310 311 /** releases all NLP rows from given hash map */ 312 static 313 SCIP_RETCODE releaseHashmapNLPRows( 314 SCIP* scip, /**< SCIP data structure */ 315 SCIP_HASHMAP* hashmap /**< hashmap */ 316 ) 317 { 318 int nentries; 319 int i; 320 321 assert(scip != NULL); 322 assert(hashmap != NULL); 323 324 nentries = SCIPhashmapGetNEntries(hashmap); 325 326 for( i = 0; i < nentries; ++i ) 327 { 328 SCIP_HASHMAPENTRY* entry; 329 entry = SCIPhashmapGetEntry(hashmap, i); 330 if( entry != NULL ) 331 { 332 SCIP_NLROW* nlrow; 333 nlrow = (SCIP_NLROW*) SCIPhashmapEntryGetImage(entry); 334 335 SCIP_CALL( SCIPreleaseNlRow(scip, &nlrow) ); 336 } 337 } 338 339 return SCIP_OKAY; 340 } 341 342 343 /** adds linear constraints from a SCIP instance to its NLP */ 344 static 345 SCIP_RETCODE addLinearConstraints( 346 SCIP* scip, /**< SCIP data structure */ 347 SCIP_CONSHDLR* conshdlr, /**< constraint handler for linear constraints */ 348 SCIP_Bool addcombconss, /**< whether to add combinatorial linear constraints to NLP */ 349 SCIP_Bool addcontconss, /**< whether to add continuous linear constraints to NLP */ 350 SCIP_HEURDATA* heurdata /**< heuristic data structure */ 351 ) 352 { 353 SCIP_CONS** conss; 354 SCIP_VAR** vars; 355 SCIP_NLROW* nlrow; 356 int nconss; 357 int i; 358 int j; 359 int nvars; 360 SCIP_Bool iscombinatorial; 361 362 assert(scip != NULL); 363 assert(conshdlr != NULL); 364 365 nconss = SCIPconshdlrGetNActiveConss(conshdlr); 366 conss = SCIPconshdlrGetConss(conshdlr); 367 368 if( nconss == 0 ) 369 return SCIP_OKAY; 370 371 for( i = 0; i < nconss; ++i ) 372 { 373 /* skip local and redundant constraints */ 374 if( !SCIPconsIsEnabled(conss[i]) || !SCIPconsIsChecked(conss[i]) ) 375 continue; 376 377 /* under some circumstances, this method may be called even though the problem has been shown to be 378 * infeasible in presolve already. 379 * this infeasibility may come from a linear constraint with lhs > rhs 380 * the NLP does not allow such constraints, so we skip them here 381 */ 382 if( !SCIPisRelLE(scip, SCIPgetLhsLinear(scip, conss[i]), SCIPgetRhsLinear(scip, conss[i])) ) 383 continue; 384 385 nvars = SCIPgetNVarsLinear(scip, conss[i]); 386 vars = SCIPgetVarsLinear(scip, conss[i]); 387 388 /* check if constraint should be added, only need this check if we do not wanna any constraint anyway */ 389 if( !addcombconss || !addcontconss ) 390 { 391 iscombinatorial = TRUE; 392 393 for( j = 0; j < nvars; ++j ) 394 { 395 if( SCIPvarGetType(vars[j]) >= SCIP_VARTYPE_CONTINUOUS ) 396 { 397 iscombinatorial = FALSE; 398 break; 399 } 400 } 401 402 /* skip constraint, if not of interest */ 403 if( (iscombinatorial && !addcombconss) || (!iscombinatorial && !addcontconss) ) 404 continue; 405 } 406 407 SCIP_CALL( SCIPcreateNlRow(scip, &nlrow, SCIPconsGetName(conss[i]), 0.0, 408 SCIPgetNVarsLinear(scip, conss[i]), SCIPgetVarsLinear(scip, conss[i]), SCIPgetValsLinear(scip, conss[i]), NULL, 409 SCIPgetLhsLinear(scip, conss[i]), SCIPgetRhsLinear(scip, conss[i]), 410 SCIP_EXPRCURV_LINEAR) ); 411 412 SCIP_CALL( SCIPaddNlRow(scip, nlrow) ); 413 SCIP_CALL( SCIPhashmapInsert(heurdata->conss2nlrow, conss[i], nlrow) ); 414 SCIP_CALL( SCIPreleaseNlRow(scip, &nlrow) ); 415 } 416 417 return SCIP_OKAY; 418 } 419 420 /** adds variable bound constraints from a SCIP instance to its NLP */ 421 static 422 SCIP_RETCODE addVarboundConstraints( 423 SCIP* scip, /**< SCIP data structure */ 424 SCIP_CONSHDLR* conshdlr, /**< constraint handler for linear constraints */ 425 SCIP_Bool addcombconss, /**< whether to add combinatorial linear constraints to NLP */ 426 SCIP_Bool addcontconss, /**< whether to add continuous linear constraints to NLP */ 427 SCIP_HEURDATA* heurdata /**< heuristic data structure */ 428 ) 429 { 430 SCIP_CONS** conss; 431 int nconss; 432 SCIP_NLROW* nlrow; 433 int i; 434 SCIP_VAR* vars[2]; 435 SCIP_Real coefs[2]; 436 SCIP_Bool iscombinatorial; 437 438 assert(scip != NULL); 439 assert(conshdlr != NULL); 440 441 nconss = SCIPconshdlrGetNActiveConss(conshdlr); 442 conss = SCIPconshdlrGetConss(conshdlr); 443 444 if( nconss == 0 ) 445 return SCIP_OKAY; 446 447 for( i = 0; i < nconss; ++i ) 448 { 449 /* skip local and redundant constraints */ 450 if( !SCIPconsIsEnabled(conss[i]) || !SCIPconsIsChecked(conss[i]) ) 451 continue; 452 453 vars[0] = SCIPgetVarVarbound(scip, conss[i]); 454 vars[1] = SCIPgetVbdvarVarbound(scip, conss[i]); 455 456 iscombinatorial = SCIPvarGetType(vars[0]) < SCIP_VARTYPE_CONTINUOUS && SCIPvarGetType(vars[1]) < SCIP_VARTYPE_CONTINUOUS; 457 458 /* skip constraint, if not of interest */ 459 if( (iscombinatorial && !addcombconss) || (!iscombinatorial && !addcontconss) ) 460 continue; 461 462 coefs[0] = 1.0; 463 coefs[1] = SCIPgetVbdcoefVarbound(scip, conss[i]); 464 465 SCIP_CALL( SCIPcreateNlRow(scip, &nlrow, SCIPconsGetName(conss[i]), 0.0, 466 2, vars, coefs, NULL, 467 SCIPgetLhsVarbound(scip, conss[i]), SCIPgetRhsVarbound(scip, conss[i]), 468 SCIP_EXPRCURV_LINEAR) ); 469 470 SCIP_CALL( SCIPaddNlRow(scip, nlrow) ); 471 SCIP_CALL( SCIPhashmapInsert(heurdata->conss2nlrow, conss[i], nlrow) ); 472 } 473 474 return SCIP_OKAY; 475 } 476 477 478 /** adds logic-or constraints to NLP */ 479 static 480 SCIP_RETCODE addLogicOrConstraints( 481 SCIP* scip, /**< SCIP data structure */ 482 SCIP_CONSHDLR* conshdlr, /**< constraint handler for linear constraints */ 483 SCIP_HEURDATA* heurdata /**< heuristic data structure */ 484 ) 485 { 486 SCIP_CONS** conss; 487 int nconss; 488 SCIP_NLROW* nlrow; 489 int i; 490 int j; 491 SCIP_Real* coefs; 492 int coefssize; 493 int nvars; 494 495 assert(scip != NULL); 496 assert(conshdlr != NULL); 497 498 nconss = SCIPconshdlrGetNActiveConss(conshdlr); 499 if( !nconss ) 500 return SCIP_OKAY; 501 502 conss = SCIPconshdlrGetConss(conshdlr); 503 504 coefs = NULL; 505 coefssize = 0; 506 507 for( i = 0; i < nconss; ++i ) 508 { 509 /* skip local and redundant constraints */ 510 if( !SCIPconsIsEnabled(conss[i]) || !SCIPconsIsChecked(conss[i]) ) 511 continue; 512 513 nvars = SCIPgetNVarsLogicor(scip, conss[i]); 514 515 if( coefssize < nvars ) 516 { 517 if( coefs == NULL ) 518 { 519 SCIP_CALL( SCIPallocBufferArray(scip, &coefs, nvars) ); 520 } 521 else 522 { 523 SCIP_CALL( SCIPreallocBufferArray(scip, &coefs, nvars) ); 524 } 525 for( j = coefssize; j < nvars; ++j ) 526 coefs[j] = 1.0; 527 coefssize = nvars; 528 } 529 530 /* logic or constraints: 1 == sum_j x_j */ 531 SCIP_CALL( SCIPcreateNlRow(scip, &nlrow, SCIPconsGetName(conss[i]), 0.0, 532 nvars, SCIPgetVarsLogicor(scip, conss[i]), coefs, NULL, 533 1.0, SCIPinfinity(scip), 534 SCIP_EXPRCURV_LINEAR) ); 535 536 SCIP_CALL( SCIPaddNlRow(scip, nlrow) ); 537 SCIP_CALL( SCIPhashmapInsert(heurdata->conss2nlrow, conss[i], nlrow) ); 538 } 539 540 SCIPfreeBufferArrayNull(scip, &coefs); 541 542 return SCIP_OKAY; 543 } 544 545 /** adds setppc constraints to NLP */ 546 static 547 SCIP_RETCODE addSetppcConstraints( 548 SCIP* scip, /**< SCIP data structure */ 549 SCIP_CONSHDLR* conshdlr, /**< constraint handler for linear constraints */ 550 SCIP_HEURDATA* heurdata /**< heuristic data structure */ 551 ) 552 { 553 SCIP_CONS** conss; 554 int nconss; 555 SCIP_NLROW* nlrow; 556 int i; 557 int j; 558 SCIP_Real* coefs; 559 int coefssize; 560 int nvars; 561 SCIP_Real lhs; 562 SCIP_Real rhs; 563 564 assert(scip != NULL); 565 assert(conshdlr != NULL); 566 567 nconss = SCIPconshdlrGetNActiveConss(conshdlr); 568 if( nconss == 0 ) 569 return SCIP_OKAY; 570 571 conss = SCIPconshdlrGetConss(conshdlr); 572 573 coefs = NULL; 574 coefssize = 0; 575 576 for( i = 0; i < nconss; ++i ) 577 { 578 /* skip local and redundant constraints */ 579 if( !SCIPconsIsEnabled(conss[i]) || !SCIPconsIsChecked(conss[i]) ) 580 continue; 581 582 nvars = SCIPgetNVarsSetppc(scip, conss[i]); 583 584 if( coefssize < nvars ) 585 { 586 if( coefs == NULL ) 587 { 588 SCIP_CALL( SCIPallocBufferArray(scip, &coefs, nvars) ); 589 } 590 else 591 { 592 SCIP_CALL( SCIPreallocBufferArray(scip, &coefs, nvars) ); 593 } 594 for( j = coefssize; j < nvars; ++j ) 595 coefs[j] = 1.0; 596 coefssize = nvars; 597 } 598 599 /* setppc constraint: 1 ~ sum_j x_j */ 600 601 switch( SCIPgetTypeSetppc(scip, conss[i]) ) 602 { 603 case SCIP_SETPPCTYPE_PARTITIONING: 604 lhs = 1.0; 605 rhs = 1.0; 606 break; 607 608 case SCIP_SETPPCTYPE_PACKING: 609 lhs = -SCIPinfinity(scip); 610 rhs = 1.0; 611 break; 612 613 case SCIP_SETPPCTYPE_COVERING: 614 lhs = 1.0; 615 rhs = SCIPinfinity(scip); 616 break; 617 618 default: 619 SCIPerrorMessage("unexpected setppc type\n"); 620 return SCIP_ERROR; 621 } 622 623 SCIP_CALL( SCIPcreateNlRow(scip, &nlrow, SCIPconsGetName(conss[i]), 0.0, 624 nvars, SCIPgetVarsSetppc(scip, conss[i]), coefs, NULL, 625 lhs, rhs, 626 SCIP_EXPRCURV_LINEAR) ); 627 628 SCIP_CALL( SCIPaddNlRow(scip, nlrow) ); 629 SCIP_CALL( SCIPhashmapInsert(heurdata->conss2nlrow, conss[i], nlrow) ); 630 } 631 632 SCIPfreeBufferArrayNull(scip, &coefs); 633 634 return SCIP_OKAY; 635 } 636 637 /** adds knapsack constraints to NLP */ 638 static 639 SCIP_RETCODE addKnapsackConstraints( 640 SCIP* scip, /**< SCIP data structure */ 641 SCIP_CONSHDLR* conshdlr, /**< constraint handler for linear constraints */ 642 SCIP_HEURDATA* heurdata /**< heuristic data structure */ 643 ) 644 { 645 SCIP_CONS** conss; 646 int nconss; 647 SCIP_NLROW* nlrow; 648 int i; 649 int j; 650 SCIP_Real* coefs; 651 int coefssize; 652 int nvars; 653 654 assert(scip != NULL); 655 assert(conshdlr != NULL); 656 657 nconss = SCIPconshdlrGetNActiveConss(conshdlr); 658 if( nconss == 0 ) 659 return SCIP_OKAY; 660 661 conss = SCIPconshdlrGetConss(conshdlr); 662 assert(conss != NULL); 663 664 coefs = NULL; 665 coefssize = 0; 666 667 for( i = 0; i < nconss; ++i ) 668 { 669 SCIP_Longint* weights; 670 671 /* skip local and redundant constraints */ 672 if( !SCIPconsIsEnabled(conss[i]) || !SCIPconsIsChecked(conss[i]) ) 673 continue; 674 675 nvars = SCIPgetNVarsKnapsack(scip, conss[i]); 676 677 if( coefssize < nvars ) 678 { 679 if( coefs == NULL ) 680 { 681 SCIP_CALL( SCIPallocBufferArray(scip, &coefs, nvars) ); 682 } 683 else 684 { 685 SCIP_CALL( SCIPreallocBufferArray(scip, &coefs, nvars) ); 686 } 687 coefssize = nvars; 688 } 689 690 weights = SCIPgetWeightsKnapsack(scip, conss[i]); 691 for( j = 0; j < nvars; ++j ) 692 coefs[j] = (SCIP_Real)weights[j]; /*lint !e613*/ 693 694 SCIP_CALL( SCIPcreateNlRow(scip, &nlrow, SCIPconsGetName(conss[i]), 0.0, 695 nvars, SCIPgetVarsKnapsack(scip, conss[i]), coefs, NULL, 696 -SCIPinfinity(scip), (SCIP_Real)SCIPgetCapacityKnapsack(scip, conss[i]), 697 SCIP_EXPRCURV_LINEAR) ); 698 699 SCIP_CALL( SCIPaddNlRow(scip, nlrow) ); 700 SCIP_CALL( SCIPhashmapInsert(heurdata->conss2nlrow, conss[i], nlrow) ); 701 } 702 703 SCIPfreeBufferArrayNull(scip, &coefs); 704 705 return SCIP_OKAY; 706 } 707 708 709 /** adds combinatorial and/or continuous variants of linear constraints from a SCIP instance to its NLP */ 710 static 711 SCIP_RETCODE addLinearConstraintsToNlp( 712 SCIP* scip, /**< SCIP data structure */ 713 SCIP_Bool addcombconss, /**< whether to add combinatorial linear constraints to NLP */ 714 SCIP_Bool addcontconss, /**< whether to add continuous linear constraints to NLP */ 715 SCIP_HEURDATA* heurdata /**< heuristic data structure */ 716 ) 717 { 718 SCIP_CONSHDLR* conshdlr; 719 720 /* add linear constraints */ 721 conshdlr = SCIPfindConshdlr(scip, "linear"); 722 if( conshdlr != NULL ) 723 { 724 SCIP_CALL( addLinearConstraints(scip, conshdlr, addcombconss, addcontconss, heurdata) ); 725 } 726 727 /* add varbound constraints */ 728 conshdlr = SCIPfindConshdlr(scip, "varbound"); 729 if( conshdlr != NULL ) 730 { 731 SCIP_CALL( addVarboundConstraints(scip, conshdlr, addcombconss, addcontconss, heurdata) ); 732 } 733 734 if( addcombconss ) 735 { 736 /* add logic-or constraints */ 737 conshdlr = SCIPfindConshdlr(scip, "logicor"); 738 if( conshdlr != NULL ) 739 { 740 SCIP_CALL( addLogicOrConstraints(scip, conshdlr, heurdata) ); 741 } 742 743 /* add setppc constraints */ 744 conshdlr = SCIPfindConshdlr(scip, "setppc"); 745 if( conshdlr != NULL ) 746 { 747 SCIP_CALL( addSetppcConstraints(scip, conshdlr, heurdata) ); 748 } 749 750 /* add knapsack constraints */ 751 conshdlr = SCIPfindConshdlr(scip, "knapsack"); 752 if( conshdlr != NULL ) 753 { 754 SCIP_CALL( addKnapsackConstraints(scip, conshdlr, heurdata) ); 755 } 756 } 757 758 return SCIP_OKAY; 759 } 760 761 762 763 /** creates a SCIP_SOL in our SCIP space out of the SCIP_SOL from a sub-SCIP */ 764 static 765 SCIP_RETCODE createSolFromSubScipSol( 766 SCIP* scip, /**< SCIP data structure */ 767 SCIP_HEUR* heur, /**< heuristic data structure */ 768 SCIP_SOL** sol, /**< buffer to store solution value; if pointing to NULL, a new solution 769 * is created, otherwise values in the given one are overwritten */ 770 SCIP_SOL* subsol /**< solution of sub-SCIP */ 771 ) 772 { 773 SCIP_HEURDATA* heurdata; 774 SCIP_VAR** vars; 775 SCIP_VAR** subvars; 776 SCIP_VAR* var; 777 SCIP_VAR* subvar; 778 SCIP_Real scalar; 779 SCIP_Real constant; 780 SCIP_Real val; 781 int i; 782 int nvars; 783 784 heurdata = SCIPheurGetData(heur); 785 assert( heurdata != NULL ); 786 SCIP_CALL( SCIPgetOrigVarsData(heurdata->subscip, &subvars, &nvars, NULL, NULL, NULL, NULL) ); 787 788 if( *sol == NULL ) 789 { 790 SCIP_CALL( SCIPcreateOrigSol(scip, sol, heur) ); 791 } 792 793 vars = SCIPgetOrigVars(scip); 794 nvars = SCIPgetNOrigVars(scip); 795 796 for( i = 0; i < nvars; ++i ) 797 { 798 var = vars[i]; 799 800 constant = 0; 801 scalar = 1.0; 802 var = SCIPvarGetTransVar(var); 803 val = 0; 804 805 if( REALABS(scalar) > 0 ) 806 { 807 SCIP_Real transval = 0.0; 808 809 subvar = (SCIP_VAR*) SCIPhashmapGetImage(heurdata->varsciptosubscip, (void*)var); 810 if( subvar == NULL ) 811 { 812 SCIPdebugMsg(scip, "return14 : abort building solution since a variable was not in our list\n"); 813 814 SCIP_CALL( SCIPfreeSol(scip, sol) ); 815 return SCIP_OKAY; 816 } 817 818 if( SCIPvarIsBinary(subvar) ) 819 transval = SCIPvarGetLbGlobal(subvar); 820 else 821 { 822 SCIP_Real tconstant = 0.0; 823 SCIP_Real tscalar = 1.0; 824 SCIP_CALL( SCIPgetProbvarSum(heurdata->subscip, &subvar, &tscalar, &tconstant) ); 825 826 transval = 0.0; 827 828 if( REALABS(tscalar) > 0.0 ) 829 { 830 assert(subvar != NULL); 831 transval = SCIPgetSolVal(heurdata->subscip, subsol, subvar); 832 } 833 834 /* recompute aggregations */ 835 transval = tscalar * transval + tconstant; 836 } 837 val = scalar * transval + constant; 838 } 839 else 840 { 841 /* recompute aggregations */ 842 val = scalar * val + constant; 843 } 844 845 assert( val != SCIP_INVALID ); /*lint !e777*/ 846 SCIP_CALL( SCIPsetSolVal(scip, *sol, vars[i], val) ); 847 } 848 849 return SCIP_OKAY; 850 } 851 852 853 854 /** creates copy of CIP from problem in SCIP */ 855 static 856 SCIP_RETCODE createSubSCIP( 857 SCIP* scip, /**< SCIP data structure */ 858 SCIP_HEURDATA* heurdata /**< heuristic data structure */ 859 ) 860 { 861 SCIP_HASHMAP* varsmap; 862 SCIP_HASHMAP* conssmap; 863 SCIP_CONSHDLR* conshdlrindicator; 864 SCIP_CONSHDLR* conshdlrindi; 865 SCIP_CONSHDLR* conshdlrlin; 866 SCIP_CONSHDLR* conshdlrnonlin; 867 SCIP_CONSHDLR* conshdlrvarbound; 868 SCIP_CONSHDLR* conshdlrknapsack; 869 SCIP_CONSHDLR* conshdlrlogicor; 870 SCIP_CONSHDLR* conshdlrsetppc; 871 SCIP_CONSHDLR* currentconshdlr; 872 SCIP_CONS** conss; 873 SCIP_CONS* subcons; 874 SCIP_CONS* transcons; 875 SCIP_CONS* linindicons; 876 SCIP_CONS* indicons; 877 SCIP_CONS* cons = NULL; 878 SCIP_VAR** vars; 879 SCIP_VAR** subvars; 880 SCIP_VAR* var; 881 SCIP_VAR* tmpvar; 882 SCIP_VAR* subvar; 883 SCIP_VAR* slackvarpos; 884 SCIP_VAR* slackvarneg; 885 SCIP_VAR* indislackvarpos; 886 SCIP_VAR* indislackvarneg; 887 SCIP_VAR* indicatorcopy; 888 char probname[SCIP_MAXSTRLEN]; 889 char varname[SCIP_MAXSTRLEN]; 890 char consname[SCIP_MAXSTRLEN]; 891 SCIP_Real varobjective; 892 int nconss; 893 int nconsindicator; 894 int i; 895 int j; 896 int k; 897 int nvars; 898 int ncontvars; 899 SCIP_Bool feasible; 900 SCIP_Bool success; 901 902 assert( heurdata != NULL ); 903 assert( heurdata->subscip == NULL ); 904 905 heurdata->usedcalls = 0; 906 heurdata->solfound = FALSE; 907 heurdata->nonimprovingRounds = 0; 908 909 /* we can't change the vartype in some constraints, so we have to check that only the right constraints are present*/ 910 conshdlrindi = SCIPfindConshdlr(scip, "indicator"); 911 conshdlrlin = SCIPfindConshdlr(scip, "linear"); 912 conshdlrnonlin = SCIPfindConshdlr(scip, "nonlinear"); 913 conshdlrvarbound = SCIPfindConshdlr(scip, "varbound"); 914 conshdlrknapsack = SCIPfindConshdlr(scip, "knapsack"); 915 conshdlrlogicor = SCIPfindConshdlr(scip, "logicor"); 916 conshdlrsetppc = SCIPfindConshdlr(scip, "setppc"); 917 918 nconss = SCIPgetNOrigConss(scip); 919 conss = SCIPgetOrigConss(scip); 920 921 /* for each constraint ask if it has an allowed type */ 922 for (i = 0; i < nconss; i++ ) 923 { 924 cons = conss[i]; 925 currentconshdlr = SCIPconsGetHdlr(cons); 926 927 if( currentconshdlr == conshdlrindi || 928 currentconshdlr == conshdlrnonlin || 929 currentconshdlr == conshdlrvarbound || 930 currentconshdlr == conshdlrknapsack || 931 currentconshdlr == conshdlrlogicor || 932 currentconshdlr == conshdlrsetppc || 933 currentconshdlr == conshdlrlin ) 934 { 935 continue; 936 } 937 else 938 { 939 return SCIP_OKAY; 940 } 941 } 942 943 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, &ncontvars) ); 944 945 if( heurdata->dynamicdepth == 1 ) 946 { 947 heurdata->maxcalls = (int)SCIPfloor(scip, sqrt((double)(nvars - ncontvars))); 948 } 949 950 heurdata->triedsetupsubscip = TRUE; 951 952 /* initializing the subproblem */ 953 SCIP_CALL( SCIPcreate(&heurdata->subscip) ); 954 955 /* create variable hash mapping scip -> subscip */ 956 SCIP_CALL( SCIPhashmapCreate(&varsmap, SCIPblkmem(scip), nvars) ); 957 958 SCIP_CALL( SCIPhashmapCreate(&heurdata->switchedvars, SCIPblkmem(scip), heurdata->maxcalls) ); 959 SCIP_CALL( SCIPhashmapCreate(&heurdata->switchedvars2, SCIPblkmem(scip), heurdata->maxcalls) ); 960 961 /* create sub-SCIP copy of CIP, copy interesting plugins */ 962 success = TRUE; 963 SCIP_CALL( SCIPcopyPlugins(scip, heurdata->subscip, TRUE, FALSE, TRUE, FALSE, TRUE, 964 FALSE, FALSE, FALSE, TRUE, FALSE, TRUE, TRUE, FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE, &success) ); 965 966 if( success == FALSE ) 967 { 968 SCIPdebugMsg(scip, "In heur_dualval: failed to copy some plugins to sub-SCIP, continue anyway\n"); 969 } 970 971 /* copy parameter settings */ 972 SCIP_CALL( SCIPcopyParamSettings(scip, heurdata->subscip) ); 973 974 /* create problem in sub-SCIP */ 975 976 /* get name of the original problem and add "dualval" */ 977 (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN, "%s_dualval", SCIPgetProbName(scip)); 978 SCIP_CALL( SCIPcreateProb(heurdata->subscip, probname, NULL, NULL, NULL, NULL, NULL, NULL, NULL) ); 979 980 SCIP_CALL( SCIPincludeEventHdlrLPsol(heurdata->subscip, heurdata) ); 981 982 /* copy all variables */ 983 SCIP_CALL( SCIPcopyVars(scip, heurdata->subscip, varsmap, NULL, NULL, NULL, 0, TRUE) ); 984 985 /* copy as many constraints as possible */ 986 SCIP_CALL( SCIPhashmapCreate(&conssmap, SCIPblkmem(scip), SCIPgetNConss(scip)) ); 987 SCIP_CALL( SCIPcopyConss(scip, heurdata->subscip, varsmap, conssmap, TRUE, FALSE, &heurdata->subscipisvalid) ); 988 989 SCIP_CALL( SCIPhashmapCreate(&heurdata->origsubscipConsMap, SCIPblkmem(scip), SCIPgetNConss(scip)) ); 990 991 nconss = SCIPgetNOrigConss(scip); 992 conss = SCIPgetOrigConss(scip); 993 994 /* fill constraint mapping from original scip to the subscip */ 995 for( i = 0; i < nconss; ++i ) 996 { 997 transcons = NULL; 998 SCIP_CALL( SCIPgetTransformedCons(scip, conss[i], &transcons) ); 999 1000 subcons = (SCIP_CONS*)SCIPhashmapGetImage(conssmap, transcons); 1001 assert( subcons != NULL ); 1002 1003 SCIP_CALL( SCIPcaptureCons(heurdata->subscip, subcons) ); 1004 SCIP_CALL( SCIPhashmapInsert(heurdata->origsubscipConsMap, transcons, subcons) ); 1005 } 1006 1007 SCIP_CALL( SCIPhashmapCreate(&heurdata->conss2nlrow, SCIPblkmem(scip), SCIPgetNConss(scip)) ); 1008 1009 if( !heurdata->subscipisvalid ) 1010 { 1011 SCIPdebugMsg(scip, "In heur_dualval: failed to copy some constraints to sub-SCIP, continue anyway\n"); 1012 } 1013 1014 SCIP_CALL( SCIPgetVarsData(heurdata->subscip, &subvars, &heurdata->nsubvars, NULL, NULL, NULL, NULL) ); 1015 heurdata->nvars = nvars; 1016 1017 /* create hashmaps from scip transformed vars to subscip original vars, and vice versa 1018 * capture variables in SCIP and sub-SCIP 1019 * catch global bound change events */ 1020 SCIP_CALL( SCIPhashmapCreate(&heurdata->varsubsciptoscip, SCIPblkmem(scip), SCIPgetNOrigVars(scip)) ); 1021 SCIP_CALL( SCIPhashmapCreate(&heurdata->varsciptosubscip, SCIPblkmem(scip), SCIPgetNOrigVars(scip)) ); 1022 1023 /* we need to get all subscip variables, also those which are copies of fixed variables from the main scip, 1024 * therefore we iterate over the hashmap */ 1025 for( i = 0; i < SCIPhashmapGetNEntries(varsmap); ++i ) 1026 { 1027 SCIP_HASHMAPENTRY* entry; 1028 entry = SCIPhashmapGetEntry(varsmap, i); 1029 if( entry != NULL ) 1030 { 1031 var = (SCIP_VAR*) SCIPhashmapEntryGetOrigin(entry); 1032 subvar = (SCIP_VAR*) SCIPhashmapEntryGetImage(entry); 1033 1034 assert( SCIPvarGetProbindex(subvar) >= 0 ); 1035 assert( SCIPvarGetProbindex(subvar) <= heurdata->nsubvars ); 1036 1037 if( SCIPvarIsActive(var) ) 1038 { 1039 assert( SCIPvarGetProbindex(var) <= heurdata->nvars ); 1040 /* assert that we have no mapping for this var yet */ 1041 assert( SCIPhashmapGetImage(heurdata->varsciptosubscip,var) == NULL ); 1042 SCIP_CALL( SCIPhashmapInsert(heurdata->varsciptosubscip, var, subvar) ); 1043 } 1044 1045 assert( SCIPhashmapGetImage(heurdata->varsubsciptoscip, subvar) == NULL ); 1046 SCIP_CALL( SCIPhashmapInsert(heurdata->varsubsciptoscip, subvar, var) ); 1047 1048 SCIP_CALL( SCIPcaptureVar(scip, var) ); 1049 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, subvar) ); 1050 1051 assert( SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(var), SCIPvarGetLbGlobal(subvar)) ); 1052 assert( SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(var), SCIPvarGetUbGlobal(subvar)) ); 1053 } 1054 } 1055 1056 /* we map all slack variables of indicator constraints to their indicator variables */ 1057 conshdlrindicator = SCIPfindConshdlr(scip, "indicator"); 1058 nconsindicator = SCIPconshdlrGetNConss(conshdlrindicator); 1059 1060 SCIP_CALL( SCIPhashmapCreate(&heurdata->slacktoindivarsmap, SCIPblkmem(scip), nconsindicator) ); 1061 SCIP_CALL( SCIPhashmapCreate(&heurdata->indicators, SCIPblkmem(scip), nconsindicator) ); 1062 SCIP_CALL( SCIPhashmapCreate(&heurdata->indicopymap, SCIPblkmem(scip), nconsindicator) ); 1063 SCIP_CALL( SCIPhashmapCreate(&heurdata->indicopymapback, SCIPblkmem(scip), nconsindicator) ); 1064 SCIP_CALL( SCIPhashmapCreate(&heurdata->slackvarlbMap, SCIPblkmem(scip), SCIPgetNOrigVars(scip)) ); 1065 SCIP_CALL( SCIPhashmapCreate(&heurdata->slackvarubMap, SCIPblkmem(scip), SCIPgetNOrigVars(scip)) ); 1066 1067 for( i = 0; i < nconsindicator; i++ ) 1068 { 1069 SCIP_CONS** indicatorconss = SCIPconshdlrGetConss(conshdlrindicator); 1070 SCIP_CONS* currcons; 1071 1072 currcons = indicatorconss[i]; 1073 assert(currcons != NULL); 1074 1075 SCIP_CALL( SCIPhashmapInsert(heurdata->slacktoindivarsmap, SCIPgetSlackVarIndicator(currcons), 1076 SCIPgetBinaryVarIndicator(currcons)) ); 1077 SCIP_CALL( SCIPhashmapInsert(heurdata->indicators, SCIPgetBinaryVarIndicator(currcons), currcons) ); 1078 SCIP_CALL( SCIPcaptureCons(scip, currcons) ); 1079 SCIP_CALL( SCIPcaptureVar(scip, SCIPgetBinaryVarIndicator(currcons)) ); 1080 } 1081 1082 /* we introduce slackvariables s+ and s- for each constraint to ensure that the problem is feasible 1083 * we want to minimize over the sum of these variables, so set the objective to 1 */ 1084 SCIP_CALL( SCIPhashmapCreate(&heurdata->relaxcons, SCIPblkmem(scip), nvars) ); 1085 SCIP_CALL( SCIPhashmapCreate(&heurdata->relaxconsindi, SCIPblkmem(scip), nvars) ); 1086 SCIP_CALL( SCIPhashmapCreate(&heurdata->slack2var, SCIPblkmem(scip), nvars) ); 1087 1088 vars = SCIPgetOrigVars(scip); 1089 nvars = SCIPgetNOrigVars(scip); 1090 1091 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(heurdata->integervars), nvars) ); 1092 BMSclearMemoryArray(heurdata->integervars, nvars); 1093 heurdata->integervarssize = nvars; 1094 j = 0; 1095 1096 /* here we relax the variables (or indicator constraints, since indicator variables cannot be relaxed) */ 1097 for( i = 0; i < nvars; ++i ) 1098 { 1099 var = SCIPvarGetTransVar(vars[i]); 1100 assert( var != NULL ); 1101 1102 if( ! SCIPvarIsActive(var) ) 1103 continue; 1104 1105 if( ! SCIPvarIsIntegral(var) ) 1106 continue; 1107 1108 heurdata->integervars[j++] = vars[i]; 1109 1110 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var); 1111 if( var == NULL ) 1112 continue; 1113 1114 /* in this case our variable is an indicator variable */ 1115 if( SCIPhashmapGetImage(heurdata->indicators, SCIPhashmapGetImage(heurdata->varsubsciptoscip, var)) != NULL ) 1116 { 1117 /* we have to find all the indicator constraints of this variable */ 1118 for( k = 0; k < nconsindicator; k++ ) 1119 { 1120 SCIP_CONS** indicatorconss = SCIPconshdlrGetConss(conshdlrindicator); 1121 SCIP_CONS* currcons; 1122 SCIP_VAR* negatedvar; 1123 SCIP_VAR* indicatorbinvar; 1124 1125 currcons = indicatorconss[k]; 1126 assert(currcons != NULL); 1127 1128 indicatorbinvar = SCIPgetBinaryVarIndicator(currcons); 1129 assert(indicatorbinvar != NULL); 1130 1131 SCIP_CALL( SCIPgetNegatedVar(scip, (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsubsciptoscip, var), &negatedvar) ); 1132 1133 if( indicatorbinvar == SCIPhashmapGetImage(heurdata->varsubsciptoscip, var) || indicatorbinvar == negatedvar ) 1134 { 1135 /* case that we have a negated variable */ 1136 if( SCIPvarIsNegated(indicatorbinvar) ) 1137 { 1138 assert(indicatorbinvar == negatedvar); 1139 varobjective = SCIPvarGetObj(negatedvar); 1140 } 1141 else 1142 { 1143 assert(indicatorbinvar != negatedvar); 1144 varobjective = SCIPvarGetObj(indicatorbinvar); 1145 } 1146 1147 varobjective = heurdata->lambdaobj * REALABS(varobjective); 1148 1149 indicons = currcons; 1150 assert( indicons != NULL ); 1151 1152 indicons = (SCIP_CONS*)SCIPhashmapGetImage(conssmap, indicons); 1153 1154 assert( indicons != NULL ); 1155 linindicons = SCIPgetLinearConsIndicator(indicons); 1156 1157 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "relax_%s_pos3", SCIPconsGetName(linindicons)); 1158 SCIP_CALL( SCIPcreateVar(heurdata->subscip, &slackvarpos, varname, 0.0, SCIPinfinity(heurdata->subscip), 1159 heurdata->lambdaslack *100 + varobjective, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) ); 1160 SCIP_CALL( SCIPaddVar(heurdata->subscip, slackvarpos) ); 1161 1162 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "relax_%s_neg3", SCIPconsGetName(linindicons)); 1163 SCIP_CALL( SCIPcreateVar(heurdata->subscip, &slackvarneg, varname, 0.0, SCIPinfinity(heurdata->subscip), 1164 heurdata->lambdaslack * 100 + varobjective, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) ); 1165 SCIP_CALL( SCIPaddVar(heurdata->subscip, slackvarneg) ); 1166 1167 /* make a copy of the indicator to relax it if this parameter is set true */ 1168 if( heurdata->relaxindicators ) 1169 { 1170 SCIP_CONS* imagecons; 1171 1172 indicatorbinvar = SCIPgetBinaryVarIndicator(indicons); 1173 1174 SCIP_CALL( SCIPgetNegatedVar(heurdata->subscip, indicatorbinvar, &negatedvar) ); 1175 1176 if( SCIPhashmapGetImage(heurdata->indicopymap, indicatorbinvar) == NULL && 1177 SCIPhashmapGetImage(heurdata->indicopymap, negatedvar) == NULL) 1178 { 1179 SCIP_Bool negated = FALSE; 1180 1181 if (SCIPvarIsNegated(indicatorbinvar)) 1182 { 1183 indicatorbinvar = negatedvar; 1184 negated = TRUE; 1185 } 1186 1187 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "indicopy_%s", SCIPvarGetName(indicatorbinvar)); 1188 SCIP_CALL( SCIPcreateVar(heurdata->subscip, &indicatorcopy, varname, SCIPvarGetLbGlobal(indicatorbinvar), SCIPvarGetUbGlobal(indicatorbinvar), 1189 SCIPvarGetObj(indicatorbinvar), SCIP_VARTYPE_BINARY, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) ); 1190 1191 SCIP_CALL( SCIPaddVar(heurdata->subscip, indicatorcopy) ); 1192 1193 SCIP_CALL( SCIPhashmapInsert(heurdata->indicopymap, indicatorbinvar, indicatorcopy) ); 1194 SCIP_CALL( SCIPhashmapInsert(heurdata->indicopymapback, indicatorcopy, indicatorbinvar) ); 1195 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, indicatorbinvar) ); 1196 1197 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "relax_%s_pos1", SCIPvarGetName(indicatorbinvar)); 1198 SCIP_CALL( SCIPcreateVar(heurdata->subscip, &indislackvarpos, varname, 0.0, SCIPinfinity(heurdata->subscip), 1199 heurdata->lambdaslack * 100 + varobjective, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) ); 1200 SCIP_CALL( SCIPaddVar(heurdata->subscip, indislackvarpos) ); 1201 1202 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "relax_%s_neg1", SCIPvarGetName(indicatorbinvar)); 1203 SCIP_CALL( SCIPcreateVar(heurdata->subscip, &indislackvarneg, varname, 0.0, SCIPinfinity(heurdata->subscip), 1204 heurdata->lambdaslack * 100 + varobjective, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) ); 1205 SCIP_CALL( SCIPaddVar(heurdata->subscip, indislackvarneg) ); 1206 1207 /* create linking constraint */ 1208 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "linking_%s", SCIPvarGetName(indicatorbinvar)); 1209 cons = NULL; 1210 SCIP_CALL( SCIPcreateConsLinear( heurdata->subscip, &cons, consname, 0, NULL, NULL, 0.0, 0.0, 1211 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) ); 1212 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, indicatorbinvar, 1.0) ); 1213 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, indicatorcopy, -1.0) ); 1214 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, indislackvarpos, 1.0) ); 1215 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, indislackvarneg, -1.0) ); 1216 1217 SCIP_CALL( SCIPhashmapInsert(heurdata->relaxconsindi, indicatorbinvar, cons) ); 1218 SCIP_CALL( SCIPhashmapInsert(heurdata->relaxconsindi, indicatorcopy, cons) ); 1219 1220 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) ); 1221 SCIP_CALL( SCIPcaptureCons(heurdata->subscip, cons) ); 1222 1223 assert( SCIPhashmapGetImage(heurdata->indicopymap, indicatorbinvar) != NULL ); 1224 1225 if ( negated ) 1226 { 1227 SCIP_CALL( SCIPgetNegatedVar(heurdata->subscip, indicatorcopy, &indicatorcopy) ); 1228 } 1229 1230 SCIP_CALL( SCIPchgVarType(heurdata->subscip, indicatorbinvar, SCIP_VARTYPE_CONTINUOUS, &feasible) ); 1231 1232 SCIP_CALL( SCIPhashmapInsert(heurdata->slack2var, indislackvarpos, var) ); 1233 SCIP_CALL( SCIPhashmapInsert(heurdata->slack2var, indislackvarneg, var) ); 1234 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) ); 1235 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) ); 1236 SCIP_CALL( SCIPreleaseVar(heurdata->subscip, &indislackvarpos) ); 1237 SCIP_CALL( SCIPreleaseVar(heurdata->subscip, &indislackvarneg) ); 1238 } 1239 else 1240 { 1241 if (!SCIPvarIsNegated(indicatorbinvar)) 1242 indicatorcopy = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->indicopymap, indicatorbinvar); 1243 else 1244 { 1245 indicatorcopy = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->indicopymap, negatedvar); 1246 SCIP_CALL( SCIPgetNegatedVar(heurdata->subscip, indicatorcopy, &indicatorcopy) ); 1247 } 1248 } 1249 1250 cons = NULL; 1251 SCIP_CALL( SCIPcreateConsIndicatorLinCons(heurdata->subscip, &cons, SCIPconsGetName(indicons), indicatorcopy, 1252 SCIPgetLinearConsIndicator(indicons), SCIPgetSlackVarIndicator(indicons), SCIPconsIsInitial(indicons), 1253 SCIPconsIsSeparated(indicons), SCIPconsIsEnforced(indicons), SCIPconsIsChecked(indicons), 1254 SCIPconsIsPropagated(indicons), SCIPconsIsLocal(indicons), SCIPconsIsDynamic(indicons), 1255 SCIPconsIsRemovable(indicons), SCIPconsIsStickingAtNode(indicons)) ); 1256 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) ); 1257 1258 /* delete old indicator constraints so we can relax the indicator variables */ 1259 imagecons = (SCIP_CONS*) SCIPhashmapGetImage(heurdata->origsubscipConsMap, (void*)(currcons)); 1260 assert(imagecons != NULL); 1261 SCIP_CALL( SCIPreleaseCons(heurdata->subscip, &imagecons) ); 1262 SCIP_CALL( SCIPhashmapRemove(heurdata->origsubscipConsMap, currcons) ); 1263 SCIP_CALL( SCIPhashmapInsert(heurdata->origsubscipConsMap, currcons, cons) ); 1264 SCIPconsAddUpgradeLocks(SCIPgetLinearConsIndicator(indicons), -1); 1265 SCIP_CALL( SCIPdelCons(heurdata->subscip, indicons) ); 1266 } 1267 1268 SCIP_CALL( SCIPhashmapInsert(heurdata->slack2var, slackvarpos, var) ); 1269 SCIP_CALL( SCIPhashmapInsert(heurdata->slack2var, slackvarneg, var) ); 1270 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) ); 1271 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) ); 1272 1273 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, linindicons, slackvarpos, 1.0) ); 1274 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, linindicons, slackvarneg, -1.0) ); 1275 SCIP_CALL( SCIPreleaseVar(heurdata->subscip, &slackvarpos) ); 1276 SCIP_CALL( SCIPreleaseVar(heurdata->subscip, &slackvarneg) ); 1277 } 1278 } 1279 continue; 1280 } 1281 1282 if( heurdata->relaxindicators ) 1283 { 1284 /* relax the old indicator variables*/ 1285 for( k = 0; k < nvars; k++ ) 1286 { 1287 if( SCIPhashmapGetImage(heurdata->indicators, vars[k]) == NULL ) 1288 continue; 1289 1290 tmpvar = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, vars[k]); 1291 SCIP_CALL( SCIPchgVarType(heurdata->subscip, tmpvar, SCIP_VARTYPE_CONTINUOUS, &feasible) ); 1292 SCIP_CALL( SCIPchgVarLbGlobal(heurdata->subscip, tmpvar, -SCIPinfinity(heurdata->subscip)) ); 1293 SCIP_CALL( SCIPchgVarUbGlobal(heurdata->subscip, tmpvar, SCIPinfinity(heurdata->subscip)) ); 1294 } 1295 1296 /* we map all slack variables of indicator constraints to their indicator variables */ 1297 conshdlrindicator = SCIPfindConshdlr(scip, "indicator"); 1298 nconsindicator = SCIPconshdlrGetNConss(conshdlrindicator); 1299 1300 /* delete old hashmaps and fill with the new indicators*/ 1301 SCIP_CALL( releaseHashmapEntries(scip, heurdata->slacktoindivarsmap, TRUE) ); 1302 SCIP_CALL( releaseHashmapEntries(scip, heurdata->indicators, FALSE) ); 1303 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->slacktoindivarsmap) ); 1304 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->indicators) ); 1305 1306 /* fill hashmaps with new values */ 1307 for( k = 0; k < nconsindicator; k++ ) 1308 { 1309 SCIP_CONS** indicatorconss = SCIPconshdlrGetConss(conshdlrindicator); 1310 SCIP_CONS* currcons; 1311 1312 currcons = indicatorconss[k]; 1313 assert(currcons != NULL); 1314 1315 SCIP_CALL( SCIPcaptureVar(scip, SCIPgetBinaryVarIndicator(currcons)) ); 1316 SCIP_CALL( SCIPcaptureCons(scip, currcons) ); 1317 1318 SCIP_CALL( SCIPhashmapInsert(heurdata->slacktoindivarsmap, SCIPgetSlackVarIndicator(currcons), 1319 SCIPgetBinaryVarIndicator(currcons)) ); 1320 SCIP_CALL( SCIPhashmapInsert(heurdata->indicators, SCIPgetBinaryVarIndicator(currcons), currcons) ); 1321 } 1322 } 1323 1324 /* in this case, we have a normal variable */ 1325 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "relax_%s", SCIPvarGetName(var)); 1326 cons = NULL; 1327 SCIP_CALL( SCIPcreateConsLinear( heurdata->subscip, &cons, consname, 0, NULL, NULL, 0.0, 0.0, 1328 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) ); 1329 1330 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "relax_%s_pos0", SCIPvarGetName(var)); 1331 SCIP_CALL( SCIPcreateVar( heurdata->subscip, &slackvarpos, varname, 0.0, SCIPinfinity(heurdata->subscip), 1332 heurdata->lambdaslack * 100, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL,NULL) ); 1333 SCIP_CALL( SCIPaddVar(heurdata->subscip, slackvarpos) ); 1334 1335 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "relax_%s_neg0", SCIPvarGetName(var)); 1336 SCIP_CALL( SCIPcreateVar(heurdata->subscip, &slackvarneg, varname, 0.0, SCIPinfinity(heurdata->subscip), 1337 heurdata->lambdaslack * 100, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL,NULL) ); 1338 SCIP_CALL( SCIPaddVar(heurdata->subscip, slackvarneg) ); 1339 1340 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, var, 1.0) ); 1341 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, slackvarpos, 1.0) ); 1342 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, slackvarneg, -1.0) ); 1343 1344 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) ); 1345 1346 SCIP_CALL( SCIPhashmapInsert(heurdata->slack2var, slackvarpos, var) ); 1347 SCIP_CALL( SCIPhashmapInsert(heurdata->slack2var, slackvarneg, var) ); 1348 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) ); 1349 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) ); 1350 SCIP_CALL( SCIPhashmapInsert(heurdata->relaxcons, var, cons) ); 1351 SCIP_CALL( SCIPreleaseVar(heurdata->subscip, &slackvarpos) ); 1352 SCIP_CALL( SCIPreleaseVar(heurdata->subscip, &slackvarneg) ); 1353 1354 /* if the var is no indicator, relax it to a continuous variable */ 1355 if( SCIPhashmapGetImage(heurdata->indicators, SCIPhashmapGetImage(heurdata->varsubsciptoscip, var)) == NULL ) 1356 { 1357 SCIP_CALL( SCIPchgVarType(heurdata->subscip, var, SCIP_VARTYPE_CONTINUOUS, &feasible) ); 1358 SCIP_CALL( SCIPchgVarLbGlobal(heurdata->subscip, var, -SCIPinfinity(heurdata->subscip)) ); 1359 SCIP_CALL( SCIPchgVarUbGlobal(heurdata->subscip, var, SCIPinfinity(heurdata->subscip)) ); 1360 } 1361 } 1362 1363 /* set up relaxation constraints for continuous variables */ 1364 if( heurdata->relaxcontvars ) 1365 { 1366 for( i = 0; i < nvars; ++i ) 1367 { 1368 var = SCIPvarGetTransVar(vars[i]); 1369 assert( var != NULL ); 1370 1371 if( ! SCIPvarIsActive(var) ) 1372 continue; 1373 1374 if( SCIPvarIsIntegral(var) ) 1375 continue; 1376 1377 if( SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(var), SCIPvarGetLbGlobal(var)) ) 1378 continue; 1379 1380 if( (SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(var), SCIPinfinity(scip))) && (SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(var), -SCIPinfinity(scip))) ) 1381 continue; 1382 1383 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var); 1384 if( var == NULL ) 1385 continue; 1386 1387 /* in this case, we have a normal variable */ 1388 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "relax_ub_%s", SCIPvarGetName(var)); 1389 cons = NULL; 1390 SCIP_CALL( SCIPcreateConsLinear( heurdata->subscip, &cons, consname, 0, NULL, NULL, -SCIPinfinity(heurdata->subscip), SCIPvarGetUbGlobal(var), 1391 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) ); 1392 1393 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "relax_%s_pos2", SCIPvarGetName(var)); 1394 SCIP_CALL( SCIPcreateVar( heurdata->subscip, &slackvarpos, varname, 0.0, SCIPinfinity(heurdata->subscip), 1395 heurdata->lambdaslack, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL,NULL) ); 1396 SCIP_CALL( SCIPaddVar(heurdata->subscip, slackvarpos) ); 1397 1398 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, var, 1.0) ); 1399 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, slackvarpos, -1.0) ); 1400 1401 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) ); 1402 SCIP_CALL( SCIPreleaseCons(heurdata->subscip, &cons) ); 1403 SCIP_CALL( SCIPhashmapInsert(heurdata->slackvarubMap, var, slackvarpos) ); 1404 SCIP_CALL( SCIPhashmapInsert(heurdata->slack2var, slackvarpos, var) ); 1405 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) ); 1406 1407 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "relax_lb_%s", SCIPvarGetName(var)); 1408 cons = NULL; 1409 SCIP_CALL( SCIPcreateConsLinear( heurdata->subscip, &cons, consname, 0, NULL, NULL, SCIPvarGetLbGlobal(var), SCIPinfinity(heurdata->subscip), 1410 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) ); 1411 1412 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "relax_%s_neg2", SCIPvarGetName(var)); 1413 SCIP_CALL( SCIPcreateVar( heurdata->subscip, &slackvarneg, varname, 0.0, SCIPinfinity(heurdata->subscip), 1414 heurdata->lambdaslack, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL,NULL) ); 1415 SCIP_CALL( SCIPaddVar(heurdata->subscip, slackvarneg) ); 1416 1417 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, var, 1.0) ); 1418 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, slackvarneg, 1.0) ); 1419 1420 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) ); 1421 SCIP_CALL( SCIPreleaseCons(heurdata->subscip, &cons) ); 1422 SCIP_CALL( SCIPhashmapInsert(heurdata->slackvarlbMap, var, slackvarneg) ); 1423 SCIP_CALL( SCIPhashmapInsert(heurdata->slack2var, slackvarneg, var) ); 1424 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) ); 1425 1426 SCIP_CALL( SCIPchgVarLbGlobal(heurdata->subscip, var, -SCIPinfinity(heurdata->subscip)) ); 1427 SCIP_CALL( SCIPchgVarUbGlobal(heurdata->subscip, var, SCIPinfinity(heurdata->subscip)) ); 1428 } 1429 } 1430 1431 /* if we have a solution add constraint that the next solution must not be worse than the current one */ 1432 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "objbound"); 1433 SCIP_CALL( SCIPcreateConsLinear( heurdata->subscip, &cons, consname, 0, NULL, NULL, -SCIPinfinity(scip), 1434 SCIPinfinity(scip), TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) ); 1435 heurdata->objbound = cons; 1436 1437 for( i = 0; i < nvars; ++i ) 1438 { 1439 var = SCIPvarGetTransVar(vars[i]); 1440 assert( var != NULL ); 1441 1442 if( !SCIPvarIsActive(var) ) 1443 continue; 1444 1445 subvar = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var); 1446 if( subvar == NULL ) 1447 continue; 1448 1449 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, subvar, SCIPvarGetObj(var)) ); 1450 1451 SCIP_CALL( SCIPchgVarObj(heurdata->subscip, subvar, heurdata->lambdaobj * SCIPvarGetObj(subvar) ) ); 1452 } 1453 1454 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) ); 1455 SCIP_CALL( SCIPreleaseCons(heurdata->subscip, &cons) ); 1456 1457 /* do not need varsmap and conssmap anymore */ 1458 SCIPhashmapFree(&conssmap); 1459 SCIPhashmapFree(&varsmap); 1460 1461 /* enable SCIP output if needed */ 1462 if( heurdata->heurverblevel > 3 ) 1463 { 1464 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "display/verblevel", 4) ); 1465 } 1466 else 1467 { 1468 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "display/verblevel", 0) ); 1469 } 1470 1471 heurdata->nintegervars = j; 1472 1473 return SCIP_OKAY; 1474 } 1475 1476 1477 /** free sub-SCIP data structure */ 1478 static 1479 SCIP_RETCODE freeSubSCIP( 1480 SCIP* scip, /**< SCIP data structure */ 1481 SCIP_HEURDATA* heurdata /**< heuristic data structure */ 1482 ) 1483 { 1484 assert(scip != NULL); 1485 assert(heurdata != NULL); 1486 assert(heurdata->subscip != NULL); 1487 1488 heurdata->nsubvars = 0; 1489 heurdata->nvars = 0; 1490 1491 /* free sub-SCIP */ 1492 SCIP_CALL( SCIPfree(&heurdata->subscip) ); 1493 1494 return SCIP_OKAY; 1495 } 1496 1497 1498 /** create a solution from the values of current nonlinear program */ 1499 static 1500 SCIP_RETCODE createSolFromNLP( 1501 SCIP* scip, /**< SCIP data structure */ 1502 SCIP_HEUR* heur, /**< heuristic data structure */ 1503 SCIP_SOL** sol /**< buffer to store solution value; if pointing to NULL a new solution is 1504 * created, otherwise values in the given one are overwritten */ 1505 ) 1506 { 1507 SCIP_HEURDATA* heurdata; 1508 SCIP_VAR** subvars; 1509 SCIP_VAR* subvar; 1510 int i; 1511 int nsubvars; 1512 1513 assert(scip != NULL); 1514 assert(heur != NULL); 1515 assert(sol != NULL); 1516 1517 heurdata = SCIPheurGetData(heur); 1518 assert(heurdata != NULL); 1519 1520 if( *sol == NULL ) 1521 { 1522 SCIP_CALL( SCIPcreateSol(scip, sol, heur) ); 1523 } 1524 1525 /* sub-SCIP may have more variables than the number of active (transformed) variables in the main SCIP 1526 * since constraint copying may have required the copy of variables that are fixed in the main SCIP */ 1527 assert(heurdata->nsubvars <= SCIPgetNOrigVars(heurdata->subscip)); 1528 1529 SCIP_CALL( SCIPgetOrigVarsData(heurdata->subscip, &subvars, &nsubvars, NULL, NULL, NULL, NULL) ); 1530 1531 /* set solution values */ 1532 for( i = 0; i < nsubvars; ++i ) 1533 { 1534 subvar = subvars[i]; 1535 assert(subvar != NULL); 1536 1537 subvar = SCIPvarGetTransVar(subvar); 1538 1539 if( !SCIPvarIsActive(subvar) ) 1540 continue; 1541 1542 assert(SCIPvarGetNLPSol(subvar) != SCIP_INVALID);/*lint !e777*/ 1543 SCIP_CALL( SCIPsetSolVal(scip, *sol, subvar, SCIPvarGetNLPSol(subvar)) ); 1544 } 1545 1546 return SCIP_OKAY; 1547 } 1548 1549 #define BIG_VALUE 1E+10 1550 1551 /** method to fix the (relaxed) discrete variables */ 1552 static 1553 SCIP_RETCODE fixDiscreteVars( 1554 SCIP* scip, /**< SCIP data structure */ 1555 SCIP_HEURDATA* heurdata, /**< heuristic data structure */ 1556 SCIP_SOL* refpoint, /**< point to take fixation of discrete variables from; 1557 * if NULL, then LP solution is used */ 1558 SCIP_SOL** transsol /**< pointer to new created solution with fixed values as solution value */ 1559 ) 1560 { 1561 SCIP_Real fixval; 1562 SCIP_VAR* var; 1563 SCIP_VAR* subvar; 1564 SCIP_CONS* rcons; 1565 int i; 1566 1567 SCIP_CALL( SCIPcreateOrigSol(scip, transsol, NULL) ); 1568 1569 /* fix discrete variables */ 1570 for( i = 0; i < heurdata->nintegervars; i++ ) 1571 { 1572 var = heurdata->integervars[i]; 1573 assert(var != NULL); 1574 1575 var = SCIPvarGetTransVar(var); 1576 assert(var != NULL); 1577 subvar = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var); 1578 1579 if( subvar == NULL ) 1580 continue; 1581 1582 if ( SCIPhashmapGetImage(heurdata->indicopymap, subvar) != NULL ) 1583 subvar = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->indicopymap, subvar); 1584 1585 /* if we do not really have a startpoint, we set to 0.0 here and project on bounds below */ 1586 if( refpoint == NULL && SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL ) 1587 fixval = 0.0; 1588 else 1589 { 1590 /* get value of the variables (NULL as refpoint gives the current LP solution, otherwise the start point) */ 1591 fixval = SCIPgetSolVal(scip, refpoint, heurdata->integervars[i]); 1592 1593 /* take care that we do not fix variables to very large values (project on bounds below) */ 1594 if( REALABS(fixval) > BIG_VALUE ) 1595 fixval = 0.0; 1596 else 1597 { 1598 /* round fractional variables to the nearest integer, use exact integral value, if the variable is only 1599 * integral within numerical tolerances */ 1600 fixval = SCIPfloor(scip, fixval + 0.5); 1601 } 1602 } 1603 1604 /* adjust value to the global bounds of the corresponding SCIP variable */ 1605 fixval = MAX(fixval, SCIPvarGetLbGlobal(heurdata->integervars[i])); /*lint !e666*/ 1606 fixval = MIN(fixval, SCIPvarGetUbGlobal(heurdata->integervars[i])); /*lint !e666*/ 1607 1608 SCIP_CALL( SCIPsetSolVal(scip, *transsol, heurdata->integervars[i], fixval) ); 1609 1610 /* adjust the relaxation constraints to the new fixval */ 1611 rcons = (SCIP_CONS*) SCIPhashmapGetImage(heurdata->relaxcons, subvar); 1612 1613 fixval = MAX(fixval, SCIPvarGetLbGlobal(subvar));/*lint !e666*/ 1614 fixval = MIN(fixval, SCIPvarGetUbGlobal(subvar));/*lint !e666*/ 1615 if( rcons == NULL ) 1616 { 1617 SCIP_CALL( SCIPchgVarLbGlobal(heurdata->subscip, subvar, fixval) ); 1618 SCIP_CALL( SCIPchgVarUbGlobal(heurdata->subscip, subvar, fixval) ); 1619 continue; 1620 } 1621 1622 SCIP_CALL( SCIPchgLhsLinear(heurdata->subscip, rcons, fixval) ); 1623 SCIP_CALL( SCIPchgRhsLinear(heurdata->subscip, rcons, fixval) ); 1624 } 1625 1626 return SCIP_OKAY; 1627 } 1628 1629 /** method to free memory before leaving the heuristic or jumping up in the recursion */ 1630 static 1631 SCIP_RETCODE freeMemory( 1632 SCIP* scip, /**< scip data structure */ 1633 SCIP_HEURDATA* heurdata, /**< heuristic data structure */ 1634 SCIP_SOL* transsol, /**< sol that has to be freed */ 1635 SCIP_Real* absranks, /**< array of absolute rank values */ 1636 SCIP_Real* ranks, /**< array of rank values */ 1637 SCIP_VAR** sortedvars, /**< array of corresponding variables */ 1638 SCIP_Bool beforeswitching, /**< did we call this method before or after switching variables? */ 1639 SCIP_Bool clearswitchedvars /**< says if we should clear switchedvars or not */ 1640 ) 1641 { 1642 SCIP_VAR** subvars; 1643 SCIP_VAR* subvar; 1644 SCIP_VAR* var; 1645 SCIP_Real* val; 1646 int nsubvars; 1647 int nsubbinvars; 1648 int nsubintvars; 1649 int i; 1650 1651 if( clearswitchedvars ) 1652 { 1653 /* free memory of the solution values in the hashmaps */ 1654 for( i = 0; i < heurdata->nintegervars; i++ ) 1655 { 1656 var = heurdata->integervars[i]; 1657 1658 if( SCIPhashmapGetImage(heurdata->slacktoindivarsmap, var) != NULL ) 1659 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->slacktoindivarsmap, var); 1660 1661 val = (SCIP_Real*)SCIPhashmapGetImage(heurdata->switchedvars, var); 1662 if( val != NULL ) 1663 { 1664 SCIPfreeBlockMemoryArray(heurdata->subscip, &val, 1); 1665 } 1666 1667 val = (SCIP_Real*)SCIPhashmapGetImage(heurdata->switchedvars2, var); 1668 if( val != NULL ) 1669 { 1670 SCIPfreeBlockMemoryArray(heurdata->subscip, &val, 1); 1671 } 1672 } 1673 1674 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->switchedvars) ); 1675 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->switchedvars2) ); 1676 } 1677 1678 SCIPfreeBufferArrayNull( scip, &ranks ); 1679 SCIPfreeBufferArrayNull( scip, &absranks ); 1680 SCIPfreeBufferArrayNull( scip, &sortedvars ); 1681 1682 if( transsol != NULL ) 1683 { 1684 SCIP_CALL( SCIPfreeSol(scip, &transsol) ); 1685 } 1686 1687 if( beforeswitching ) 1688 { 1689 SCIP_CALL( SCIPfreeTransform(heurdata->subscip) ); 1690 } 1691 1692 /* undo fixing of discrete variables in sub-SCIP */ 1693 SCIP_CALL( SCIPgetOrigVarsData(heurdata->subscip, &subvars, &nsubvars, &nsubbinvars, &nsubintvars, NULL, NULL) ); 1694 1695 /* set bounds of discrete variables to original values */ 1696 for( i = nsubbinvars + nsubintvars - 1; i >= 0; --i ) 1697 { 1698 subvar = subvars[i]; 1699 assert(SCIPvarGetProbindex(subvar) == i); 1700 1701 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsubsciptoscip, subvar); 1702 1703 if (SCIPhashmapGetImage(heurdata->indicopymapback, subvar) != NULL) 1704 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsubsciptoscip, SCIPhashmapGetImage(heurdata->indicopymapback, subvar)); 1705 1706 assert(var != NULL); 1707 1708 SCIP_CALL( SCIPchgVarLbGlobal(heurdata->subscip, subvar, SCIPvarGetLbGlobal(var)) ); 1709 SCIP_CALL( SCIPchgVarUbGlobal(heurdata->subscip, subvar, SCIPvarGetUbGlobal(var)) ); 1710 } 1711 1712 return SCIP_OKAY; 1713 } 1714 1715 /** computes the ranks, saves them into an array and sorts the variables according to absolute ranks */ 1716 static 1717 SCIP_RETCODE computeRanks( 1718 SCIP* scip, /**< scip data structure */ 1719 SCIP_HEURDATA* heurdata, /**< heuristic data structure */ 1720 SCIP_Real* absranks, /**< array of absolute rank values */ 1721 SCIP_Real* ranks, /**< array of rank values */ 1722 SCIP_VAR** sortedvars /**< array of corresponding variables */ 1723 ) 1724 { 1725 SCIP_CONSHDLR* conshdlrindicator; 1726 SCIP_CONS* relaxcons; 1727 SCIP_CONS* indicons; 1728 SCIP_CONS* subcons; 1729 SCIP_CONS* transcons; 1730 SCIP_VAR* var; 1731 SCIP_Real* dualvalue; 1732 int nconsindicator; 1733 int j; 1734 int k; 1735 1736 conshdlrindicator = SCIPfindConshdlr(scip, "indicator"); 1737 nconsindicator = SCIPconshdlrGetNConss(conshdlrindicator); 1738 1739 /* Now we compute the rank of each variable */ 1740 for( j = 0; j < heurdata->nintegervars; j++ ) 1741 { 1742 sortedvars[j] = heurdata->integervars[j]; 1743 ranks[j] = 0; 1744 absranks[j] = 0; 1745 1746 if( sortedvars[j] == NULL ) 1747 break; 1748 1749 var = SCIPvarGetTransVar(sortedvars[j]); 1750 assert(var != NULL); 1751 1752 /* globally fixed variables get rank 0 */ 1753 if (SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var))) 1754 { 1755 ranks[j] = 0; 1756 continue; 1757 } 1758 else 1759 { 1760 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var); 1761 assert(var != NULL); 1762 relaxcons = (SCIP_CONS*)SCIPhashmapGetImage(heurdata->relaxcons, (void*)(var)); 1763 1764 /* get ranks */ 1765 if( relaxcons != NULL ) 1766 { 1767 SCIP_CALL( SCIPgetTransformedCons(heurdata->subscip, relaxcons, &transcons) ); 1768 dualvalue = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, (void*)transcons); 1769 1770 if( dualvalue == NULL ) 1771 dualvalue = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, (void*)(relaxcons)); 1772 1773 if( dualvalue == NULL ) 1774 continue; 1775 1776 assert(dualvalue != NULL); 1777 ranks[j] = (*dualvalue); 1778 } 1779 else /* if we have an indicator variable */ 1780 { 1781 assert(ranks[j] == 0.0); 1782 1783 if (SCIPhashmapGetImage(heurdata->relaxconsindi, (void*)(var)) != NULL) 1784 { 1785 subcons = (SCIP_CONS*)SCIPhashmapGetImage(heurdata->relaxconsindi, (void*)(var)); 1786 1787 dualvalue = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, (void*)(subcons)); 1788 1789 if( dualvalue == NULL ) 1790 continue; 1791 1792 assert(dualvalue != NULL); 1793 1794 ranks[j] = (*dualvalue); 1795 } 1796 1797 /* compute the rank of the indicators, we take the highest dualvalue of an indicator constraint */ 1798 for( k = 0; k < nconsindicator; k++ ) 1799 { 1800 SCIP_CONS** indicatorconss = SCIPconshdlrGetConss(conshdlrindicator); 1801 SCIP_CONS* currcons; 1802 SCIP_VAR* indicatorbinvar; 1803 1804 currcons = indicatorconss[k]; 1805 assert(currcons != NULL); 1806 1807 indicatorbinvar = SCIPgetBinaryVarIndicator(currcons); 1808 assert(indicatorbinvar != NULL); 1809 1810 if( indicatorbinvar == (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsubsciptoscip, var) 1811 || (SCIPvarIsNegated(indicatorbinvar) && indicatorbinvar == SCIPvarGetNegatedVar(var)) ) 1812 { 1813 indicons = currcons; 1814 assert(indicons != NULL); 1815 1816 subcons = (SCIP_CONS*)SCIPhashmapGetImage(heurdata->origsubscipConsMap, (void*)(indicons)); 1817 assert(subcons != NULL); 1818 1819 subcons = SCIPgetLinearConsIndicator(subcons); 1820 assert(subcons != NULL); 1821 1822 dualvalue = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, (void*)(subcons)); 1823 1824 if( dualvalue == NULL ) 1825 continue; 1826 1827 assert(dualvalue != NULL); 1828 1829 if( REALABS(ranks[j]) < REALABS(*dualvalue) ) 1830 ranks[j] = (*dualvalue); 1831 } 1832 } 1833 } 1834 } 1835 1836 /* take the absolute value of each rank */ 1837 absranks[j] = REALABS(ranks[j]); 1838 } 1839 1840 SCIPsortDownRealRealPtr(absranks, ranks, (void**)sortedvars, heurdata->nintegervars); 1841 1842 return SCIP_OKAY; 1843 } 1844 1845 /** compute maximal slack of a variable */ 1846 static 1847 SCIP_Real maximalslack( 1848 SCIP* scip, /**< scip data structure */ 1849 SCIP_HEURDATA* heurdata /**< heuristic data structure */ 1850 ) 1851 { 1852 SCIP_VAR* maxvar; 1853 SCIP_VAR* subvar; 1854 SCIP_SOL* bestsol; 1855 SCIP_Real maxslack; 1856 int i; 1857 int nsubvars; 1858 SCIP_Bool maxslackset; 1859 1860 /* compute maximal slack */ 1861 nsubvars = SCIPgetNOrigVars(heurdata->subscip); 1862 1863 /* save information about maximal violation */ 1864 maxvar = NULL; 1865 maxslack = -SCIPinfinity(heurdata->subscip); 1866 maxslackset = FALSE; 1867 1868 bestsol = SCIPgetBestSol(heurdata->subscip); 1869 1870 /* search for variable with maximal slack */ 1871 for( i = 0; i < nsubvars; i++ ) 1872 { 1873 subvar = SCIPgetOrigVars(heurdata->subscip)[i]; 1874 if( subvar == NULL) 1875 continue; 1876 1877 /* if variable is slack */ 1878 if( SCIPhashmapGetImage(heurdata->slack2var, subvar) != NULL ) 1879 { 1880 if( heurdata->isnlp ) 1881 { 1882 if( maxslack < SCIPvarGetNLPSol(subvar) ) 1883 { 1884 maxslack = SCIPvarGetNLPSol(subvar); 1885 maxvar = subvar; 1886 maxslackset = TRUE; 1887 } 1888 } 1889 else 1890 { 1891 assert(bestsol != NULL); 1892 if( maxslack < SCIPgetSolVal(heurdata->subscip, bestsol, subvar) ) 1893 { 1894 maxslack = SCIPgetSolVal(heurdata->subscip, bestsol, subvar); 1895 maxvar = subvar; 1896 maxslackset = TRUE; 1897 } 1898 } 1899 } 1900 } 1901 1902 if( ! maxslackset ) 1903 { 1904 maxslack = 0; 1905 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "could not find a variable with maximal slack!\n"); 1906 } 1907 1908 assert(maxslack >= 0); 1909 1910 if( heurdata->heurverblevel > 0 && maxslackset ) 1911 { 1912 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "maximum slack: %f %s\n", maxslack, SCIPvarGetName(maxvar)); 1913 } 1914 1915 return maxslack; 1916 } 1917 1918 /** method called after a solution is found which is feasible in the original problem, stores it and cleans up */ 1919 static 1920 SCIP_RETCODE storeSolution( 1921 SCIP* scip, /**< SCIP data structure */ 1922 SCIP_HEUR* heur, /**< heuristic data */ 1923 SCIP_RESULT* result, /**< pointer to store result of: did not run, solution found, 1924 * no solution found, or fixing is infeasible (cutoff) */ 1925 SCIP_SOL* transsol, /**< solution to fix variables */ 1926 SCIP_SOL* bestsol /**< solution we create a original scip solution from */ 1927 ) 1928 { 1929 SCIP_HEURDATA* heurdata; 1930 SCIP_SOL* sol = NULL; 1931 SCIP_Bool stored; 1932 SCIP_Real primalobj; 1933 1934 /* get heuristic's data */ 1935 heurdata = SCIPheurGetData(heur); 1936 assert(heurdata != NULL); 1937 SCIP_CALL( createSolFromSubScipSol(scip, heur, &sol, bestsol) ); 1938 1939 /* if this happens, there was an ipopt error - stop the heuristic for there is no good starting point */ 1940 if( heurdata->isnlp && SCIPgetNLPSolstat(heurdata->subscip) > SCIP_NLPSOLSTAT_FEASIBLE ) 1941 { 1942 *result = SCIP_DIDNOTFIND; 1943 heurdata->solfound = TRUE; 1944 1945 /* here we can be sure that we are in the nlp case */ 1946 assert( heurdata->isnlp ); 1947 SCIP_CALL( SCIPfreeSol(heurdata->subscip, &bestsol) ); 1948 1949 SCIP_CALL( freeMemory(scip, heurdata, transsol, NULL, NULL, NULL, TRUE, TRUE) ); 1950 1951 /* don't use the heuristic anymore if IPOPT doesn't give proper solution 1952 * (normally then this happens in most ipopt runs that may follow) */ 1953 SCIPheurSetFreq(heur, -1); 1954 1955 SCIPdebugMsg(scip, "return10 : turn off heuristic, ipopt error\n"); 1956 1957 if( heurdata->heurverblevel > 1 ) 1958 { 1959 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "turn off heuristic due to ipopt error"); 1960 } 1961 1962 return SCIP_OKAY; 1963 } 1964 1965 primalobj = SCIPinfinity(scip); 1966 1967 /* if there is a solution, try to add solution to storage and free it */ 1968 if( sol != NULL ) 1969 { 1970 primalobj = SCIPsolGetOrigObj(sol); 1971 1972 if( heurdata->heurverblevel > 0 ) 1973 { 1974 SCIP_CALL( SCIPtrySolFree(scip, &sol, TRUE, TRUE, TRUE, FALSE, TRUE, &stored) ); 1975 } 1976 else 1977 { 1978 SCIP_CALL( SCIPtrySolFree(scip, &sol, FALSE, FALSE, TRUE, FALSE, TRUE, &stored) ); 1979 } 1980 } 1981 else 1982 stored = FALSE; 1983 1984 if( stored && heurdata->heurverblevel > 1 ) 1985 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "accepted solution\n"); 1986 1987 if( heurdata->isnlp ) 1988 SCIP_CALL( SCIPfreeSol(heurdata->subscip, &bestsol) ); 1989 1990 SCIP_CALL( freeMemory(scip, heurdata, transsol, NULL, NULL, NULL, TRUE, TRUE) ); 1991 1992 if( !stored ) 1993 { 1994 *result = SCIP_DIDNOTFIND; 1995 heurdata->solfound = TRUE; 1996 1997 if( heurdata->heurverblevel >= 1 ) 1998 { 1999 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "return9 : found solution that was not stored, objective %f\n", primalobj);/*lint !e644*/ 2000 } 2001 2002 return SCIP_OKAY; 2003 } 2004 2005 heurdata->prevInfeasible = FALSE; 2006 heurdata->solfound = TRUE; 2007 *result = SCIP_FOUNDSOL; 2008 2009 if( heurdata->heurverblevel >= 1 ) 2010 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "return 9 : found and stored new solution, objective %lf\n", primalobj); 2011 2012 return SCIP_OKAY; 2013 } 2014 2015 /** main procedure of the dualval heuristic */ 2016 SCIP_RETCODE SCIPapplyHeurDualval( 2017 SCIP* scip, /**< original SCIP data structure */ 2018 SCIP_HEUR* heur, /**< heuristic data structure */ 2019 SCIP_RESULT* result, /**< pointer to store result of: did not run, solution found, no solution 2020 * found, or fixing is infeasible (cutoff) */ 2021 SCIP_SOL* refpoint /**< point to take fixation of discrete variables from; if NULL, then LP 2022 * solution is used */ 2023 ) 2024 { 2025 SCIP_HEURDATA* heurdata; 2026 SCIP_NLROW* nlrow; 2027 SCIP_SOL* transsol; 2028 SCIP_SOL* bestsol; 2029 SCIP_CONS** subconss; 2030 SCIP_CONS* rcons; 2031 SCIP_VAR** subvars; 2032 SCIP_VAR** sortedvars; 2033 SCIP_VAR* var; 2034 SCIP_VAR* subvar; 2035 SCIP_VAR* v; 2036 SCIP_RETCODE retcode; 2037 SCIP_Real* absranks; 2038 SCIP_Real* ranks; 2039 SCIP_Real* startpoint; 2040 SCIP_Real* dualval; 2041 SCIP_Real* lastval; 2042 SCIP_Real* seclastval; 2043 SCIP_Real* newval; 2044 SCIP_Real bound; 2045 SCIP_Real maxslack; 2046 SCIP_Real objvalue; 2047 int i; 2048 int k; 2049 int nsubvars; 2050 int nsubbinvars; 2051 int nsubintvars; 2052 int nsubconss; 2053 int maxequalranks; 2054 2055 assert(scip != NULL); 2056 assert(heur != NULL); 2057 2058 /* dio not run without nlp solver */ 2059 if( SCIPgetNNlpis(scip) <= 0 ) 2060 return SCIP_OKAY; 2061 2062 /* get heuristic's data */ 2063 heurdata = SCIPheurGetData(heur); 2064 assert(heurdata != NULL); 2065 2066 /* don't use the heuristic, if the gap is small so we don't expect to get better solutions than already found */ 2067 if( SCIPgetGap(scip) * 100 < heurdata->mingap ) 2068 { 2069 SCIPdebugMsg(scip, "return13 : gap is less than mingap\n"); 2070 return SCIP_OKAY; 2071 } 2072 2073 /* in the mode 'onlyleaves' don't run the heuristic if we are not in a leaf of the B&B tree */ 2074 if( heurdata->onlyleaves && (SCIPgetNLPBranchCands(scip) != 0 || SCIPgetNPseudoBranchCands(scip) != 0) ) 2075 return SCIP_OKAY; 2076 2077 /* try to setup subscip if not tried before */ 2078 if( heurdata->subscip == NULL && !heurdata->triedsetupsubscip ) 2079 { 2080 SCIP_CALL( createSubSCIP(scip, heurdata) ); 2081 } 2082 2083 /* quit the recursion if we have found a solution */ 2084 if( heurdata->solfound ) 2085 { 2086 SCIPdebugMsg(scip, "return1 : already found solution \n"); 2087 return SCIP_OKAY; 2088 } 2089 2090 *result = SCIP_DIDNOTRUN; 2091 2092 /* not initialized */ 2093 if( heurdata->subscip == NULL ) 2094 { 2095 SCIPdebugMsg(scip, "return2 : subscip is NULL\n"); 2096 return SCIP_OKAY; 2097 } 2098 2099 assert(heurdata->nsubvars > 0); 2100 assert(heurdata->varsubsciptoscip != NULL); 2101 2102 /* fix discrete variables in sub-SCIP */ 2103 SCIP_CALL( fixDiscreteVars(scip, heurdata, refpoint, &transsol) ); 2104 bound = SCIPgetUpperbound(scip); 2105 2106 if( heurdata->onlycheaper && !SCIPisInfinity(scip, bound) ) 2107 { 2108 SCIP_CALL( SCIPchgRhsLinear( heurdata->subscip, heurdata->objbound, bound) ); 2109 } 2110 2111 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "presolving/maxrounds", 1) ); 2112 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "propagating/maxroundsroot", 0) ); 2113 2114 SCIP_CALL( SCIPsetLongintParam(heurdata->subscip, "limits/nodes", 1LL) ); 2115 SCIP_CALL( SCIPpresolve(heurdata->subscip) ); 2116 2117 if( SCIPgetStatus(heurdata->subscip) == SCIP_STATUS_INFEASIBLE ) 2118 { 2119 SCIPdebugMsg(scip, "return 4 : subscip is infeasible\n"); 2120 2121 *result = SCIP_DIDNOTFIND; 2122 heurdata->prevInfeasible = TRUE; 2123 SCIP_CALL( freeMemory(scip, heurdata, transsol, NULL, NULL, NULL, TRUE, TRUE) ); 2124 2125 return SCIP_OKAY; 2126 } 2127 2128 /* If no NLP was constructed, then there were no nonlinearities after presolve. 2129 * So we increase the nodelimit to 1 and hope that SCIP will find some solution to this probably linear subproblem. 2130 */ 2131 SCIP_CALL( SCIPsetLongintParam(heurdata->subscip, "limits/nodes", 0LL) ); 2132 retcode = SCIPsolve(heurdata->subscip); 2133 heurdata->isnlp = TRUE; 2134 2135 bestsol = NULL; 2136 2137 /* we have no dualvalues, so give up */ 2138 if( SCIPgetStatus(heurdata->subscip) == SCIP_STATUS_OPTIMAL) 2139 { 2140 *result = SCIP_DIDNOTFIND; 2141 SCIP_CALL( freeMemory(scip, heurdata, transsol, NULL, NULL, NULL, TRUE, TRUE) ); 2142 2143 return SCIP_OKAY; 2144 } 2145 2146 if( ! SCIPisNLPConstructed(heurdata->subscip) && retcode == SCIP_OKAY ) 2147 { 2148 SCIP_CALL( SCIPsetLongintParam(heurdata->subscip, "limits/nodes", 1LL) ); 2149 SCIP_CALL( SCIPsolve(heurdata->subscip) ); 2150 heurdata->isnlp = FALSE; 2151 bestsol = SCIPgetBestSol(heurdata->subscip); 2152 } 2153 2154 if( heurdata->isnlp ) 2155 { 2156 /* add non-combinatorial linear constraints from subscip into subNLP */ 2157 SCIP_CALL( addLinearConstraintsToNlp(heurdata->subscip, FALSE, TRUE, heurdata) ); 2158 2159 SCIP_CALL( SCIPallocBufferArray(scip, &startpoint, SCIPgetNNLPVars(heurdata->subscip)) ); 2160 2161 /* set starting values (=refpoint, if not NULL; otherwise LP solution (or pseudo solution)) */ 2162 for( i = 0; i < SCIPgetNNLPVars(heurdata->subscip); ++i ) 2163 { 2164 SCIP_Real scalar = 1.0; 2165 SCIP_Real constant = 0.0; 2166 2167 subvar = SCIPgetNLPVars(heurdata->subscip)[i]; 2168 2169 /* gets corresponding original variable */ 2170 SCIP_CALL( SCIPvarGetOrigvarSum(&subvar, &scalar, &constant) ); 2171 if( subvar == NULL ) 2172 { 2173 startpoint[i] = constant; 2174 continue; 2175 } 2176 2177 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsubsciptoscip, subvar); 2178 if( var == NULL || REALABS( SCIPgetSolVal(scip, refpoint, var) ) > 1.0e+12 ) 2179 { 2180 SCIP_Real tmpmax; 2181 tmpmax = MAX( 0.0, SCIPvarGetLbGlobal(subvar) );/*lint !e666*/ 2182 startpoint[i] = MIN( tmpmax, SCIPvarGetUbGlobal(subvar) );/*lint !e666*/ 2183 } 2184 else 2185 /* scalar*subvar+constant corresponds to nlpvar[i], so nlpvar[i] gets value scalar*varval+constant */ 2186 startpoint[i] = scalar * SCIPgetSolVal(scip, refpoint, var) + constant; 2187 } 2188 2189 SCIP_CALL( SCIPsetNLPInitialGuess(heurdata->subscip, startpoint) ); 2190 2191 /* don't need startpoint array anymore */ 2192 SCIPfreeBufferArray( scip, &startpoint ); 2193 2194 SCIP_CALL( SCIPsolveNLP(heurdata->subscip, .verblevel = (unsigned short)heurdata->nlpverblevel) ); /*lint !e666*/ 2195 assert(SCIPisNLPConstructed(heurdata->subscip)); 2196 2197 /* in this case there was an error in ipopt, we try to give another startpoint */ 2198 if( SCIPgetNLPSolstat(heurdata->subscip) > SCIP_NLPSOLSTAT_FEASIBLE ) 2199 { 2200 SCIP_CALL( SCIPsetNLPInitialGuess(heurdata->subscip, NULL) ); 2201 SCIP_CALL( SCIPsolveNLP(heurdata->subscip, .verblevel = (unsigned short)heurdata->nlpverblevel) ); /*lint !e666*/ 2202 assert(SCIPisNLPConstructed(heurdata->subscip)); 2203 } 2204 2205 nsubconss = SCIPgetNOrigConss(heurdata->subscip); 2206 subconss = SCIPgetOrigConss(heurdata->subscip); 2207 2208 /* free memory of all entries and clear the hashmap before filling it */ 2209 for( i = 0; i < nsubconss; i++ ) 2210 { 2211 dualval = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, subconss[i]); 2212 SCIPfreeBlockMemoryArray(heurdata->subscip, &dualval, 1); 2213 } 2214 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->dualvalues) ); 2215 2216 /* save the dualvalues from our nlp solution */ 2217 for( i = 0; i < nsubconss; i++ ) 2218 { 2219 SCIP_CONS* transcons; 2220 2221 SCIP_CALL( SCIPgetTransformedCons(heurdata->subscip, subconss[i], &transcons) ); 2222 2223 if( transcons == NULL ) 2224 continue; 2225 2226 if( SCIPconsGetHdlr(transcons) != SCIPfindConshdlr(heurdata->subscip, "linear") ) 2227 continue; 2228 2229 nlrow = (SCIP_NLROW*)SCIPhashmapGetImage(heurdata->conss2nlrow, transcons); 2230 2231 if (nlrow != NULL) 2232 { 2233 SCIP_CALL( SCIPallocBlockMemoryArray(heurdata->subscip, &dualval, 1) ); /*lint !e506*/ 2234 *dualval = SCIPnlrowGetDualsol(nlrow); 2235 } 2236 else 2237 { 2238 SCIP_CALL( SCIPallocBlockMemoryArray(heurdata->subscip, &dualval, 1) ); /*lint !e506*/ 2239 *dualval = 0; 2240 } 2241 2242 SCIP_CALL( SCIPhashmapInsert(heurdata->dualvalues, subconss[i], dualval) ); 2243 } 2244 2245 bestsol = NULL; 2246 SCIP_CALL( createSolFromNLP(heurdata->subscip, heur, &bestsol) ); 2247 } 2248 2249 /* if we are infeasible, we can't do anything*/ 2250 if( SCIPgetStatus(heurdata->subscip) == SCIP_STATUS_INFEASIBLE ) 2251 { 2252 SCIPdebugMsg(scip, "return4 : the subscip is infeasible\n"); 2253 2254 SCIP_CALL( freeMemory(scip, heurdata, transsol, NULL, NULL, NULL, TRUE, TRUE) ); 2255 2256 return SCIP_OKAY; 2257 } 2258 2259 maxslack = maximalslack(scip, heurdata); 2260 SCIPdebugMsg(scip, "origObj: %f\n", SCIPgetSolOrigObj(heurdata->subscip, bestsol)); 2261 SCIP_CALL( SCIPgetOrigVarsData(heurdata->subscip, &subvars, &nsubvars, &nsubbinvars, &nsubintvars, NULL, NULL) ); 2262 objvalue = 0.0; 2263 assert(bestsol != NULL); 2264 2265 /* save information about maximal violation */ 2266 for( i = 0; i < nsubvars; i++ ) 2267 { 2268 subvar = SCIPgetOrigVars(heurdata->subscip)[i]; 2269 2270 if( SCIPhashmapGetImage(heurdata->slack2var, subvar) == NULL ) 2271 objvalue += SCIPvarGetObj(subvar) * SCIPgetSolVal(heurdata->subscip, bestsol, subvar); 2272 } 2273 2274 /* we stop the heuristic if it does not come "closer" to a feasible solution*/ 2275 if( heurdata->forceimprovements ) 2276 { 2277 if( SCIPisGE(scip, SCIPgetSolOrigObj(heurdata->subscip, bestsol) - objvalue, heurdata->prevobjective) && maxslack > 0 ) 2278 { 2279 heurdata->nonimprovingRounds++; 2280 SCIPdebugMsg(scip, "nonimpr rounds %d prevobj %f \n", heurdata->nonimprovingRounds, heurdata->prevobjective); 2281 2282 /* leave, if we have not improved some iterations*/ 2283 if( heurdata->nonimprovingRounds > heurdata->maxcalls/8 ) 2284 { 2285 *result = SCIP_DIDNOTFIND; 2286 2287 if( heurdata->isnlp ) 2288 { 2289 SCIP_CALL( SCIPfreeSol(heurdata->subscip, &bestsol) ); 2290 } 2291 2292 SCIP_CALL( freeMemory(scip, heurdata, transsol, NULL, NULL, NULL, TRUE, TRUE) ); 2293 2294 heurdata->solfound = TRUE; 2295 heurdata->switchdifferent = TRUE; 2296 2297 SCIPdebugMsg(scip, "return11 : solution did not improve\n"); 2298 2299 return SCIP_OKAY; 2300 } 2301 } 2302 } 2303 2304 heurdata->prevobjective = SCIPgetSolOrigObj(heurdata->subscip, bestsol) - objvalue; 2305 2306 /* in this case we found a feasible solution, store it, clean up and stop the heuristic*/ 2307 if( SCIPisFeasLE(heurdata->subscip, maxslack, 0.0) ) 2308 return storeSolution(scip, heur, result, transsol, bestsol); 2309 2310 SCIP_CALL( SCIPallocBufferArray(scip, &ranks, heurdata->nintegervars) ); 2311 SCIP_CALL( SCIPallocBufferArray(scip, &sortedvars, heurdata->nintegervars) ); 2312 SCIP_CALL( SCIPallocBufferArray(scip, &absranks, heurdata->nintegervars) ); 2313 2314 /* compute ranks and sort them in non-increasing order */ 2315 SCIP_CALL( computeRanks(scip, heurdata, absranks, ranks, sortedvars) ); 2316 2317 /* print out the highest ranks */ 2318 if( heurdata->heurverblevel > 1 ) 2319 { 2320 k = heurdata->rankvalue; 2321 2322 if( heurdata->nintegervars < heurdata->rankvalue ) 2323 k = heurdata->nintegervars; 2324 2325 for( i = 0; i < k; i++ ) 2326 { 2327 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "%i. rank: %f name: %s\n", i, ranks[i], SCIPvarGetName(sortedvars[i])); 2328 } 2329 } 2330 2331 /* free solution */ 2332 if( heurdata->isnlp ) 2333 SCIP_CALL( SCIPfreeSol(heurdata->subscip, &bestsol) ); 2334 2335 /* we don't allow more than a third of the variables to have the same rank */ 2336 maxequalranks = MIN(heurdata->maxequalranks, heurdata->nintegervars/3); 2337 2338 if( heurdata->maxequalranks >= 0 && SCIPisFeasEQ(heurdata->subscip, REALABS(ranks[0]), REALABS(ranks[maxequalranks])) ) 2339 { 2340 *result = SCIP_DIDNOTFIND; 2341 2342 SCIPdebugMsg(scip, "return12 : equal maxranks\n"); 2343 2344 SCIP_CALL( freeMemory(scip, heurdata, transsol, absranks, ranks, sortedvars, TRUE, TRUE ) ); 2345 return SCIP_OKAY; 2346 } 2347 2348 /* now we can start switching the variable values */ 2349 SCIP_CALL( SCIPfreeTransform(heurdata->subscip) ); 2350 2351 /* set bounds of fixed discrete variables to original values so we can switch */ 2352 for( k = 0; k < heurdata->nintegervars; ++k ) 2353 { 2354 var = heurdata->integervars[k]; 2355 if( var == NULL ) 2356 break; 2357 2358 var = SCIPvarGetTransVar(var); 2359 subvar = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var); 2360 2361 rcons = (SCIP_CONS*) SCIPhashmapGetImage(heurdata->relaxcons, subvar); 2362 if( rcons != NULL ) 2363 continue; 2364 2365 assert(var != NULL); 2366 assert(subvar != NULL); 2367 2368 if ( SCIPhashmapGetImage(heurdata->indicopymap, subvar) != NULL ) 2369 subvar = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->indicopymap, subvar); 2370 2371 SCIP_CALL( SCIPchgVarLbGlobal(heurdata->subscip, subvar, SCIPvarGetLbGlobal(heurdata->integervars[k])) ); 2372 SCIP_CALL( SCIPchgVarUbGlobal(heurdata->subscip, subvar, SCIPvarGetUbGlobal(heurdata->integervars[k])) ); 2373 } 2374 2375 /* switch variable with maximum ranking if possible */ 2376 for( i = 0; i < heurdata->nintegervars; i++ ) 2377 { 2378 v = sortedvars[i]; 2379 SCIP_CALL( SCIPallocBlockMemoryArray(heurdata->subscip, &newval, 1) ); /*lint !e506*/ 2380 2381 /* compute the new value of the variable */ 2382 2383 /* if we have an indicator constraint, we turn it off */ 2384 if( SCIPhashmapGetImage(heurdata->slacktoindivarsmap, v) != NULL ) 2385 { 2386 /* get the indicator var of this constraint */ 2387 v = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->slacktoindivarsmap, v); 2388 2389 /* set the value to 0 */ 2390 SCIP_CALL( SCIPsetSolVal(scip, transsol, v, 0.0) ); 2391 if( heurdata->heurverblevel > 1 ) 2392 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Setting value of %s%s to 0\n", SCIPvarIsNegated(v) ? "(negated) " : " ", SCIPvarGetName(v)); 2393 2394 *newval = 0.0; 2395 SCIP_CALL( SCIPhashmapInsert(heurdata->switchedvars, v, newval) ); 2396 } 2397 else 2398 { 2399 if( ranks[i] > 0 ) 2400 { 2401 if( SCIPvarIsBinary(v) && SCIPisEQ(scip, 1.0, SCIPgetSolVal(scip, transsol, v)) ) 2402 continue; 2403 2404 /* ignore fixed vars in input */ 2405 if( SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(v), SCIPvarGetUbGlobal(v)) ) 2406 continue; 2407 2408 *newval = SCIPgetSolVal(scip, transsol, v) + 1; 2409 } 2410 else 2411 { 2412 if( SCIPvarIsBinary(v) && SCIPisEQ(scip, 0.0, SCIPgetSolVal(scip, transsol, v)) ) 2413 continue; 2414 2415 if( SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(v), SCIPvarGetUbGlobal(v)) ) 2416 continue; 2417 2418 *newval = SCIPgetSolVal(scip, transsol, v) - 1; 2419 } 2420 } 2421 lastval = (SCIP_Real*)SCIPhashmapGetImage(heurdata->switchedvars, v); 2422 seclastval = (SCIP_Real*)SCIPhashmapGetImage(heurdata->switchedvars2, v); 2423 2424 /* we don't want to set a variable to a value it already had,or set a binary variable more than once */ 2425 if( (lastval != NULL && (SCIPvarIsBinary(v) || SCIPisFeasEQ(scip, *lastval, *newval))) || (seclastval != NULL && SCIPisFeasEQ(scip, *seclastval, *newval)) ) 2426 { 2427 SCIPfreeBlockMemoryArray(heurdata->subscip, &newval, 1); 2428 continue; 2429 } 2430 else /* update the switchedvars values, switchedvars2 is the second last and switchedvars the last value */ 2431 { 2432 if( seclastval != NULL ) 2433 SCIPfreeBlockMemoryArray(heurdata->subscip, &seclastval, 1); 2434 2435 SCIP_CALL( SCIPhashmapRemove(heurdata->switchedvars2, v) ); 2436 SCIP_CALL( SCIPhashmapInsert(heurdata->switchedvars2, v, lastval) ); 2437 SCIP_CALL( SCIPhashmapRemove(heurdata->switchedvars, v) ); 2438 SCIP_CALL( SCIPhashmapInsert(heurdata->switchedvars, v, newval) ); 2439 2440 if( heurdata->heurverblevel > 1 ) 2441 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Setting value of %s from %f to %f\n", SCIPvarGetName(v), SCIPgetSolVal(scip, transsol, v), *newval); 2442 2443 SCIP_CALL( SCIPsetSolVal(scip, transsol, v, *newval) ); 2444 } 2445 2446 /* if we have exceeded our iterations limit give up without any solution */ 2447 if( heurdata->usedcalls >= heurdata->maxcalls ) 2448 { 2449 SCIPdebugMsg(scip, "return5 : reached iteration limit\n"); 2450 2451 SCIP_CALL( freeMemory(scip, heurdata, transsol, absranks, ranks, sortedvars, FALSE, TRUE) ); 2452 *result = SCIP_DIDNOTFIND; 2453 return SCIP_OKAY; 2454 } 2455 2456 heurdata->usedcalls++; 2457 2458 if( heurdata->heurverblevel > 1 ) 2459 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "----- Total Calls: %d\n", heurdata->usedcalls); 2460 2461 /* recursive call of the heuristic */ 2462 SCIP_CALL( SCIPapplyHeurDualval(scip, heur, result, transsol) ); 2463 2464 /* just to go up in the recursion */ 2465 if( *result == SCIP_DIDNOTFIND || heurdata->solfound || heurdata->prevInfeasible ) 2466 { 2467 SCIPdebugMsg(scip, "return6 : go up\n"); 2468 2469 /* here we only go up one step and try another switch (switch the same variables again is forbidden 2470 * since they are contained in switchedvars) */ 2471 if( heurdata->switchdifferent ) 2472 { 2473 heurdata->switchdifferent = FALSE; 2474 heurdata->solfound = FALSE; 2475 *result = SCIP_DIDNOTRUN; 2476 heurdata->nonimprovingRounds -= 2; 2477 } 2478 2479 if( heurdata->prevInfeasible ) 2480 { 2481 heurdata->prevInfeasible = FALSE; 2482 heurdata->solfound = FALSE; 2483 *result = SCIP_DIDNOTRUN; 2484 heurdata->nonimprovingRounds++; 2485 } 2486 2487 SCIP_CALL( freeMemory(scip, heurdata, transsol, absranks, ranks, sortedvars, FALSE, FALSE) ); 2488 return SCIP_OKAY; 2489 } 2490 } 2491 2492 if( heurdata->subscip == NULL ) 2493 { 2494 /* something horrible must have happened that we decided to give up completely on this heuristic */ 2495 *result = SCIP_DIDNOTFIND; 2496 SCIPdebugMsg(scip, "return7 : subscip was set NULL\n"); 2497 2498 SCIP_CALL( freeMemory(scip, heurdata, transsol, absranks, ranks, sortedvars, FALSE, TRUE) ); 2499 return SCIP_OKAY; 2500 } 2501 assert(!SCIPisTransformed(heurdata->subscip)); 2502 2503 SCIPdebugMsg(scip, "return8 : cannot switch any variable\n"); 2504 2505 SCIP_CALL( freeMemory(scip, heurdata, transsol, absranks, ranks, sortedvars, FALSE, TRUE) ); 2506 2507 *result = SCIP_DIDNOTFIND; 2508 return SCIP_OKAY; 2509 } 2510 2511 2512 /* Callback methods of primal heuristic */ 2513 2514 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 2515 static 2516 SCIP_DECL_HEURFREE(heurFreeDualval) 2517 { 2518 SCIP_HEURDATA* heurdata; 2519 2520 assert(scip != NULL); 2521 assert(heur != NULL); 2522 2523 heurdata = SCIPheurGetData(heur); 2524 2525 SCIPfreeBlockMemory(scip, &heurdata); 2526 2527 return SCIP_OKAY; 2528 } 2529 2530 2531 /** initialization method of primal heuristic (called after problem was transformed) */ 2532 static 2533 SCIP_DECL_HEURINIT(heurInitDualval) 2534 { /*lint --e{715}*/ 2535 SCIP_HEURDATA* heurdata; 2536 2537 assert(scip != NULL); 2538 assert(heur != NULL); 2539 2540 /* skip setting up sub-SCIP if heuristic is disabled or we do not want to run the heuristic */ 2541 if( SCIPheurGetFreq(heur) < 0 ) 2542 return SCIP_OKAY; 2543 2544 SCIP_CALL( SCIPsetIntParam(scip, "presolving/maxrestarts", 0) ); 2545 2546 heurdata = SCIPheurGetData(heur); 2547 assert(heurdata != NULL); 2548 assert(heurdata->subscip == NULL); 2549 assert(!heurdata->triedsetupsubscip); 2550 2551 /* create sub-SCIP for later use */ 2552 SCIP_CALL( createSubSCIP(scip, heurdata) ); 2553 2554 /* creating sub-SCIP may fail if the solver interfaces did not copy into subscip */ 2555 if( heurdata->subscip == NULL ) 2556 return SCIP_OKAY; 2557 2558 /* if the heuristic is called at the root node, we want to be called directly after the initial root LP solve */ 2559 if( SCIPheurGetFreqofs(heur) == 0 ) 2560 SCIPheurSetTimingmask(heur, SCIP_HEURTIMING_DURINGLPLOOP | HEUR_TIMING); 2561 2562 SCIP_CALL( SCIPhashmapCreate(&heurdata->dualvalues, SCIPblkmem(scip), 512) ); 2563 2564 return SCIP_OKAY; 2565 } 2566 2567 /** deinitialization method of primal heuristic (called before transformed problem is freed) */ 2568 static 2569 SCIP_DECL_HEUREXIT(heurExitDualval) 2570 { /*lint --e{715}*/ 2571 SCIP_HEURDATA* heurdata; 2572 SCIP_CONS** subconss; 2573 SCIP_Real* dualval; 2574 int i; 2575 int nsubconss; 2576 2577 assert(scip != NULL); 2578 assert(heur != NULL); 2579 2580 heurdata = SCIPheurGetData(heur); 2581 assert(heurdata != NULL); 2582 2583 SCIPfreeBlockMemoryArrayNull(scip, &heurdata->integervars, heurdata->integervarssize); 2584 2585 if( heurdata->subscip != NULL) 2586 { 2587 nsubconss = SCIPgetNOrigConss(heurdata->subscip); 2588 subconss = SCIPgetOrigConss(heurdata->subscip); 2589 2590 /* free memory of all entries and clear the hashmap before filling it */ 2591 for( i = 0; i < nsubconss; i++ ) 2592 { 2593 dualval = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, subconss[i]); 2594 SCIPfreeBlockMemoryArrayNull(heurdata->subscip, &dualval, 1); 2595 } 2596 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->dualvalues) ); 2597 SCIPhashmapFree(&heurdata->dualvalues); 2598 2599 if( heurdata->varsciptosubscip != NULL ) 2600 { 2601 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->varsciptosubscip, TRUE) ); 2602 2603 SCIPhashmapFree(&heurdata->varsciptosubscip); 2604 } 2605 if( heurdata->origsubscipConsMap != NULL ) 2606 { 2607 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->origsubscipConsMap, FALSE) ); 2608 2609 SCIPhashmapFree(&heurdata->origsubscipConsMap); 2610 } 2611 if( heurdata->relaxcons != NULL ) 2612 { 2613 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->relaxcons, FALSE) ); 2614 2615 SCIPhashmapFree(&heurdata->relaxcons); 2616 } 2617 if( heurdata->conss2nlrow != NULL ) 2618 { 2619 SCIP_CALL( releaseHashmapNLPRows(heurdata->subscip, heurdata->conss2nlrow) ); 2620 2621 SCIPhashmapFree(&heurdata->conss2nlrow); 2622 } 2623 if( heurdata->slack2var != NULL ) 2624 { 2625 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->slack2var, TRUE) ); 2626 2627 SCIPhashmapFree(&heurdata->slack2var); 2628 } 2629 if( heurdata->indicopymap != NULL ) 2630 { 2631 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->indicopymap, TRUE) ); 2632 2633 SCIPhashmapFree(&heurdata->indicopymap); 2634 } 2635 if( heurdata->indicopymapback != NULL ) 2636 { 2637 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->indicopymapback, TRUE) ); 2638 2639 SCIPhashmapFree(&heurdata->indicopymapback); 2640 } 2641 if( heurdata->relaxconsindi != NULL ) 2642 { 2643 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->relaxconsindi, FALSE) ); 2644 2645 SCIPhashmapFree(&heurdata->relaxconsindi); 2646 } 2647 if( heurdata->slackvarlbMap != NULL ) 2648 { 2649 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->slackvarlbMap, TRUE) ); 2650 2651 SCIPhashmapFree(&heurdata->slackvarlbMap); 2652 } 2653 if( heurdata->slackvarubMap != NULL ) 2654 { 2655 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->slackvarubMap, TRUE) ); 2656 2657 SCIPhashmapFree(&heurdata->slackvarubMap); 2658 } 2659 2660 if( heurdata->subscip != NULL ) 2661 { 2662 SCIP_CALL( freeSubSCIP(scip, heurdata) ); 2663 } 2664 } 2665 2666 if( heurdata->varsubsciptoscip != NULL ) 2667 { 2668 SCIP_CALL( releaseHashmapEntries(scip, heurdata->varsubsciptoscip, TRUE) ); 2669 2670 SCIPhashmapFree(&heurdata->varsubsciptoscip); 2671 } 2672 if( heurdata->slacktoindivarsmap != NULL ) 2673 { 2674 SCIP_CALL( releaseHashmapEntries(scip, heurdata->slacktoindivarsmap, TRUE) ); 2675 2676 SCIPhashmapFree(&heurdata->slacktoindivarsmap); 2677 } 2678 if( heurdata->indicators != NULL ) 2679 { 2680 SCIP_CALL( releaseHashmapEntries(scip, heurdata->indicators, FALSE) ); 2681 2682 SCIPhashmapFree(&heurdata->indicators); 2683 } 2684 if( heurdata->switchedvars != NULL ) 2685 { 2686 SCIPhashmapFree(&heurdata->switchedvars); 2687 } 2688 if( heurdata->switchedvars2 != NULL ) 2689 { 2690 SCIPhashmapFree(&heurdata->switchedvars2); 2691 } 2692 2693 /* reset some flags and counters */ 2694 heurdata->triedsetupsubscip = FALSE; 2695 heurdata->usedcalls = 0; 2696 heurdata->solfound = FALSE; 2697 heurdata->prevInfeasible = FALSE; 2698 2699 assert(heurdata->subscip == NULL); 2700 assert(heurdata->varsubsciptoscip == NULL); 2701 assert(heurdata->varsciptosubscip == NULL); 2702 2703 return SCIP_OKAY; 2704 } 2705 2706 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */ 2707 static 2708 SCIP_DECL_HEURINITSOL(heurInitsolDualval) 2709 { 2710 SCIP_HEURDATA* heurdata; 2711 2712 assert(scip != NULL); 2713 assert(heur != NULL); 2714 2715 /* skip setting up sub-SCIP if heuristic is disabled or we do not want to run the heuristic */ 2716 if( SCIPheurGetFreq(heur) < 0 ) 2717 return SCIP_OKAY; 2718 2719 heurdata = SCIPheurGetData(heur); 2720 assert(heurdata != NULL); 2721 2722 /* creating sub-SCIP may fail if the solver interfaces did not copy into subscip */ 2723 if( heurdata->subscip == NULL ) 2724 return SCIP_OKAY; 2725 2726 /* if the heuristic is called at the root node, we want to be called directly after the initial root LP solve */ 2727 if( SCIPheurGetFreqofs(heur) == 0 ) 2728 SCIPheurSetTimingmask(heur, SCIP_HEURTIMING_DURINGLPLOOP | HEUR_TIMING); 2729 2730 return SCIP_OKAY; 2731 } 2732 2733 2734 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */ 2735 static 2736 SCIP_DECL_HEUREXITSOL(heurExitsolDualval) 2737 { 2738 assert(scip != NULL); 2739 assert(heur != NULL); 2740 2741 SCIPheurSetTimingmask(heur, HEUR_TIMING); 2742 2743 return SCIP_OKAY; 2744 } 2745 2746 2747 /** execution method of primal heuristic */ 2748 static 2749 SCIP_DECL_HEUREXEC(heurExecDualval) 2750 { /*lint --e{715}*/ 2751 SCIP_HEURDATA* heurdata; 2752 2753 assert(scip != NULL); 2754 assert(heur != NULL); 2755 assert(result != NULL); 2756 2757 /* get heuristic's data */ 2758 heurdata = SCIPheurGetData(heur); 2759 assert(heurdata != NULL); 2760 2761 /* obviously, we did not do anything yet */ 2762 *result = SCIP_DIDNOTRUN; 2763 2764 /* init data */ 2765 heurdata->usedcalls = 0; 2766 heurdata->prevInfeasible = FALSE; 2767 heurdata->solfound = FALSE; 2768 heurdata->nonimprovingRounds = 0; 2769 heurdata->prevobjective = INT_MAX; 2770 2771 SCIP_CALL( SCIPapplyHeurDualval(scip, heur, result, NULL) ); 2772 2773 /* SCIP does not like cutoff as return, so we say didnotfind, since we did not find a solution */ 2774 if( *result == SCIP_CUTOFF ) 2775 *result = SCIP_DIDNOTFIND; 2776 2777 /* reset timing, if it was changed temporary (at the root node) */ 2778 if( heurtiming != HEUR_TIMING ) 2779 SCIPheurSetTimingmask(heur, HEUR_TIMING); 2780 2781 return SCIP_OKAY; 2782 } 2783 2784 2785 /* primal heuristic specific interface methods */ 2786 2787 /** creates the dualval primal heuristic and includes it in SCIP */ 2788 SCIP_RETCODE SCIPincludeHeurDualval( 2789 SCIP* scip /**< SCIP data structure */ 2790 ) 2791 { 2792 SCIP_HEURDATA* heurdata = NULL; 2793 SCIP_HEUR* heur = NULL; 2794 2795 /* create dualval primal heuristic data */ 2796 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) ); 2797 BMSclearMemory(heurdata); 2798 2799 /* include primal heuristic */ 2800 2801 /* use SCIPincludeHeurBasic() plus setter functions if you want to set callbacks one-by-one and your code should 2802 * compile independent of new callbacks being added in future SCIP versions */ 2803 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 2804 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 2805 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecDualval, heurdata) ); 2806 2807 assert(heur != NULL); 2808 2809 /* set non fundamental callbacks via setter functions */ 2810 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeDualval) ); 2811 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitDualval) ); 2812 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitDualval) ); 2813 SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolDualval) ); 2814 SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolDualval) ); 2815 2816 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/forceimprovements", 2817 "exit if objective doesn't improve", 2818 &heurdata->forceimprovements, TRUE, DEFAULT_FORCEIMPROVEMENTS, NULL, NULL) ); 2819 2820 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/onlycheaper", 2821 "add constraint to ensure that discrete vars are improving", 2822 &heurdata->onlycheaper, TRUE, DEFAULT_ONLYCHEAPER, NULL, NULL) ); 2823 2824 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/onlyleaves", 2825 "disable the heuristic if it was not called at a leaf of the B&B tree", 2826 &heurdata->onlyleaves, FALSE, DEFAULT_ONLYLEAVES, NULL, NULL) ); 2827 2828 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/relaxindicators", 2829 "relax the indicator variables by introducing continuous copies", 2830 &heurdata->relaxindicators, FALSE, DEFAULT_RELAXINDICATORS, NULL, NULL) ); 2831 2832 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/relaxcontvars", 2833 "relax the continous variables", 2834 &heurdata->relaxcontvars, FALSE, DEFAULT_RELAXCONTVARS, NULL, NULL) ); 2835 2836 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/heurverblevel", 2837 "verblevel of the heuristic, default is 0 to display nothing", 2838 &heurdata->heurverblevel, FALSE, DEFAULT_HEURVERBLEVEL, 0, 4, NULL, NULL) ); 2839 2840 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nlpverblevel", 2841 "verblevel of the nlp solver, can be 0 or 1", 2842 &heurdata->nlpverblevel, FALSE, DEFAULT_NLPVERBLEVEL, 0, 1, NULL, NULL) ); 2843 2844 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/rankvalue", 2845 "number of ranks that should be displayed when the heuristic is called", 2846 &heurdata->rankvalue, FALSE, DEFAULT_RANKVALUE, 0, INT_MAX, NULL, NULL) ); 2847 2848 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxcalls", 2849 "maximal number of recursive calls of the heuristic (if dynamicdepth is off)", 2850 &heurdata->maxcalls, FALSE, DEFAULT_MAXCALLS, 0, INT_MAX, NULL, NULL) ); 2851 2852 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/dynamicdepth", 2853 "says if and how the recursion depth is computed at runtime", 2854 &heurdata->dynamicdepth, FALSE, DEFAULT_DYNAMICDEPTH, 0, 1, NULL, NULL) ); 2855 2856 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxequalranks", 2857 "maximal number of variables that may have maximal rank, quit if there are more, turn off by setting -1", 2858 &heurdata->maxequalranks, FALSE, DEFAULT_MAXEQUALRANKS, -1, INT_MAX, NULL, NULL) ); 2859 2860 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/mingap", 2861 "minimal gap for which we still run the heuristic, if gap is less we return without doing anything", 2862 &heurdata->mingap, FALSE, DEFAULT_MINGAP, 0.0, 100.0, NULL, NULL) ); 2863 2864 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lambdaslack", 2865 "value added to objective of slack variables, must not be zero", 2866 &heurdata->lambdaslack, FALSE, DEFAULT_LAMBDASLACK, 0.1, SCIPinfinity(scip), NULL, NULL) ); 2867 2868 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lambdaobj", 2869 "scaling factor for the objective function", 2870 &heurdata->lambdaobj, FALSE, DEFAULT_LAMBDAOBJ, 0.0, 1.0, NULL, NULL) ); 2871 2872 return SCIP_OKAY; 2873 } 2874