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_repair.c 26 * @ingroup DEFPLUGINS_HEUR 27 * @brief repair primal heuristic 28 * @author Gregor Hendel 29 * @author Thomas Nagel 30 * 31 */ 32 33 /* This heuristic takes an infeasible solution and tries to repair it. 34 * This can happen by variable fixing as long as the sum of all potential possible shiftings 35 * is higher than alpha*slack or slack variables with a strong penalty on the objective function. 36 * This heuristic cannot run if variable fixing and slack variables are turned off. 37 */ 38 39 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 40 41 #include "blockmemshell/memory.h" 42 #include "scip/cons_linear.h" 43 #include "scip/cons_varbound.h" 44 #include "scip/heur_repair.h" 45 #include "scip/pub_heur.h" 46 #include "scip/pub_lp.h" 47 #include "scip/pub_message.h" 48 #include "scip/pub_misc.h" 49 #include "scip/pub_misc_sort.h" 50 #include "scip/pub_var.h" 51 #include "scip/scip_branch.h" 52 #include "scip/scip_cons.h" 53 #include "scip/scip_copy.h" 54 #include "scip/scip_general.h" 55 #include "scip/scip_heur.h" 56 #include "scip/scip_lp.h" 57 #include "scip/scip_mem.h" 58 #include "scip/scip_message.h" 59 #include "scip/scip_numerics.h" 60 #include "scip/scip_param.h" 61 #include "scip/scip_prob.h" 62 #include "scip/scip_sol.h" 63 #include "scip/scip_solve.h" 64 #include "scip/scip_solvingstats.h" 65 #include "scip/scip_timing.h" 66 #include "scip/scip_tree.h" 67 #include "scip/scip_var.h" 68 #include "scip/scipdefplugins.h" 69 #include <string.h> 70 71 #define HEUR_NAME "repair" 72 #define HEUR_DESC "tries to repair a primal infeasible solution" 73 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS 74 #define HEUR_PRIORITY -20 75 #define HEUR_FREQ -1 76 #define HEUR_FREQOFS 0 77 #define HEUR_MAXDEPTH -1 78 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE 79 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */ 80 #define DEFAULT_MINFIXINGRATE 0.3 /* minimum percentage of integer variables that have to be fixed */ 81 82 #define DEFAULT_NODESOFS 500 /* number of nodes added to the contingent of the total nodes */ 83 #define DEFAULT_MAXNODES 5000 /* maximum number of nodes to regard in the subproblem */ 84 #define DEFAULT_MINNODES 50 /* minimum number of nodes to regard in the subproblem */ 85 #define DEFAULT_NODESQUOT 0.1 /* subproblem nodes in relation to nodes of the original problem */ 86 87 #define DEFAULT_FILENAME "-" /**< file name of a solution to be used as infeasible starting point */ 88 #define DEFAULT_ROUNDIT TRUE /**< if it is TRUE : fractional variables which are not fractional in the given 89 * solution are rounded, if it is FALSE : solving process of this heuristic 90 * is stopped 91 */ 92 #define DEFAULT_USEOBJFACTOR FALSE /**< should a scaled objective function for original variables be used in repair 93 * subproblem? 94 */ 95 #define DEFAULT_USEVARFIX TRUE /**< should variable fixings be used in repair subproblem? */ 96 #define DEFAULT_USESLACKVARS FALSE /**< should slack variables be used in repair subproblem? */ 97 #define DEFAULT_ALPHA 2.0 /**< how many times the potential should be bigger than the slack? */ 98 99 /* 100 * Data structures 101 */ 102 103 104 /** primal heuristic data */ 105 struct SCIP_HeurData 106 { 107 SCIP_SOL* infsol; /**< infeasible solution to start with */ 108 char* filename; /**< file name of a solution to be used as infeasible starting point */ 109 SCIP_Longint usednodes; /**< number of already used nodes by repair */ 110 SCIP_Longint subnodes; /**< number of nodes which were necessary to solve the sub-SCIP */ 111 SCIP_Longint subiters; /**< contains total number of iterations used in primal and dual simplex 112 * and barrier algorithm to solve the sub-SCIP 113 */ 114 SCIP_Real relvarfixed; /**< relative number of fixed variables */ 115 SCIP_Real alpha; /**< how many times the potential should be bigger than the slack? */ 116 SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */ 117 SCIP_Real minfixingrate; /**< minimum percentage of integer variables that have to be fixed */ 118 #ifdef SCIP_STATISTIC 119 SCIP_Real relviolatedvars; /**< relative number of violated variables */ 120 SCIP_Real subpresoltime; /**< time for presolving the sub-SCIP */ 121 SCIP_Real relviolatedcons; /**< relative number of violated cons */ 122 SCIP_Real originalsolval; /**< value of the solution find by repair, in the original Problem*/ 123 SCIP_Real improvedoldsol; /**< value of the given solution after being improved by SCIP */ 124 int nviolatedvars; /**< number of violated variables in the given solution */ 125 int norigvars; /**< number of all variables in the given problem */ 126 int nviolatedcons; /**< number of violated cons in the given solution */ 127 int norcons; /**< number of all cons in the given problem */ 128 #endif 129 int nvarfixed; /**< number of all variables fixed in the sub problem */ 130 int runs; /**< number of branch and bound runs performed to solve the sub-SCIP */ 131 int nodesofs; /**< number of nodes added to the contingent of the total nodes */ 132 int maxnodes; /**< maximum number of nodes to regard in the subproblem */ 133 int minnodes; /**< minimum number of nodes to regard in the subproblem */ 134 SCIP_Bool roundit; /**< if it is TRUE : fractional variables which are not fractional in the 135 * given solution are rounded, if it is FALSE : solving process of this 136 * heuristic is stopped. 137 */ 138 SCIP_Bool useobjfactor; /**< should a scaled objective function for original variables be used in 139 * repair subproblem? 140 */ 141 SCIP_Bool usevarfix; /**< should variable fixings be used in repair subproblem? */ 142 SCIP_Bool useslackvars; /**< should slack variables be used in repair subproblem? */ 143 }; 144 145 146 /* 147 * Local methods 148 */ 149 150 /** computes a factor, so that (factor) * (original objective upper bound) <= 1.*/ 151 static 152 SCIP_RETCODE getObjectiveFactor( 153 SCIP* scip, /**< SCIP data structure */ 154 SCIP* subscip, /**< SCIP data structure */ 155 SCIP_Real* factor, /**< SCIP_Real to save the factor for the old objective function*/ 156 SCIP_Bool* success /**< SCIP_Bool: Is the factor real?*/ 157 ) 158 { 159 SCIP_VAR** vars; 160 SCIP_Real lprelaxobj; 161 SCIP_Real upperbound; 162 SCIP_Real objoffset; 163 int nvars; 164 int i; 165 166 *success = TRUE; 167 *factor = 0.0; 168 upperbound = 0.0; 169 170 lprelaxobj = SCIPgetLowerbound(scip); 171 172 if( SCIPisInfinity(scip, -lprelaxobj) ) 173 { 174 return SCIP_OKAY; 175 } 176 177 if( !SCIPisInfinity(scip, SCIPgetUpperbound(scip)) ) 178 { 179 upperbound = SCIPgetUpperbound(scip); 180 } 181 else 182 { 183 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) ); 184 185 /* tries to find an upper bound for the original objective function, by compute the worst objective value of the 186 * LP-relaxation, which holds all variable bounds 187 */ 188 for (i = 0; i < nvars; ++i) 189 { 190 upperbound = SCIPvarGetObj(vars[i]); 191 if( SCIPisInfinity(scip, upperbound) || SCIPisInfinity(scip, -upperbound) ) 192 { 193 /* TODO fancy diving function to find a solution for the max problem */ 194 *factor = 1 / SCIPinfinity(scip); 195 return SCIP_OKAY; 196 } 197 else if( SCIPisZero(scip, upperbound) ) 198 { 199 continue; 200 } 201 else if( SCIPisGT(scip, 0.0, upperbound) ) 202 { 203 *factor += upperbound * SCIPvarGetLbGlobal(vars[i]); 204 } 205 else 206 { 207 *factor += upperbound * SCIPvarGetUbGlobal(vars[i]); 208 } 209 } 210 } 211 212 /* Ending-sequence */ 213 *factor = upperbound - lprelaxobj; 214 if( !SCIPisZero(scip, *factor) ) 215 { 216 *factor = 1.0 / *factor; 217 } 218 219 /* set an offset which guarantees positive objective values */ 220 objoffset = -lprelaxobj * (*factor); 221 SCIP_CALL( SCIPaddOrigObjoffset(subscip, -objoffset) ); 222 223 return SCIP_OKAY; 224 } 225 226 /** returns the contributed potential for a variable */ 227 static 228 SCIP_Real getPotentialContributed( 229 SCIP* scip, /**< SCIP data structure */ 230 SCIP_SOL* sol, /**< infeasible solution */ 231 SCIP_VAR* var, /**< variable, which potential should be returned */ 232 SCIP_Real coefficient, /**< variables coefficient in corresponding row */ 233 int sgn /**< sign of the slack */ 234 ) 235 { 236 SCIP_Real potential; 237 238 assert(NULL != scip); 239 assert(NULL != var); 240 241 if( 0 > sgn * coefficient ) 242 { 243 if( SCIPisInfinity(scip, -SCIPvarGetLbGlobal(var)) ) 244 { 245 potential = SCIPinfinity(scip); 246 } 247 else 248 { 249 potential = coefficient * (SCIPgetSolVal(scip, sol, var) - SCIPvarGetLbGlobal(var)); 250 } 251 } 252 else 253 { 254 if( SCIPisInfinity(scip, SCIPvarGetUbGlobal(var)) ) 255 { 256 potential = -SCIPinfinity(scip); 257 } 258 else 259 { 260 potential = coefficient * (SCIPgetSolVal(scip, sol, var) - SCIPvarGetUbGlobal(var)); 261 } 262 } 263 264 if( SCIPisZero(scip, potential) ) 265 { 266 potential = 0.0; 267 } 268 return potential; 269 } 270 271 /** finds out if a variable can be fixed with respect to the potentials of all rows, if it is possible, the potentials 272 * of rows are adapted and TRUE is returned. 273 */ 274 static 275 SCIP_RETCODE tryFixVar( 276 SCIP* scip, /**< SCIP data structure */ 277 SCIP* subscip, /**< sub-SCIP data structure */ 278 SCIP_SOL* sol, /**< solution data structure */ 279 SCIP_Real* potential, /**< array with all potential values */ 280 SCIP_Real* slack, /**< array with all slack values */ 281 SCIP_VAR* var, /**< variable to be fixed? */ 282 SCIP_VAR* subvar, /**< representative variable for var in the sub-SCIP */ 283 int* inftycounter, /**< counters how many variables have an infinity potential in a row */ 284 SCIP_HEURDATA* heurdata, /**< repairs heuristic data */ 285 SCIP_Bool* fixed /**< pointer to store whether the fixing was performed (variable was unfixed) */ 286 ) 287 { 288 SCIP_ROW** rows; 289 SCIP_COL* col; 290 SCIP_Real* vals; 291 SCIP_Real alpha; 292 SCIP_Real solval; 293 SCIP_Bool infeasible; 294 int nrows; 295 int i; 296 int sgn; 297 int rowindex; 298 299 assert(NULL != scip); 300 assert(NULL != potential); 301 assert(NULL != slack); 302 assert(NULL != var); 303 assert(NULL != inftycounter); 304 assert(NULL != heurdata); 305 306 alpha = heurdata->alpha; 307 infeasible = TRUE; 308 *fixed = FALSE; 309 310 solval = SCIPgetSolVal(scip, sol, var); 311 312 if( SCIPisFeasLT(scip, solval, SCIPvarGetLbGlobal(var)) ) 313 { 314 return SCIP_OKAY; 315 } 316 if( SCIPisFeasGT(scip, solval, SCIPvarGetUbGlobal(var)) ) 317 { 318 return SCIP_OKAY; 319 } 320 321 col = SCIPvarGetCol(var); 322 rows = SCIPcolGetRows(col); 323 nrows = SCIPcolGetNLPNonz(col); 324 vals = SCIPcolGetVals(col); 325 326 if( NULL == rows ) 327 { 328 SCIP_CALL( SCIPfixVar(subscip, subvar, solval, 329 &infeasible, fixed) ); 330 assert(!infeasible && *fixed); 331 heurdata->nvarfixed++; 332 SCIPdebugMsg(scip,"Variable %s is fixed to %g\n",SCIPvarGetName(var), solval); 333 return SCIP_OKAY; 334 } 335 assert(NULL != rows); 336 337 /* iterate over rows, where the variable coefficient is nonzero */ 338 for( i = 0; i < nrows; ++i ) 339 { 340 SCIP_Real contribution; 341 rowindex = SCIProwGetLPPos(rows[i]); 342 assert(rowindex >= 0); 343 344 sgn = 1; 345 346 if( SCIPisFeasZero(scip, slack[rowindex]) ) 347 { 348 continue; 349 } 350 else if( SCIPisFeasGT(scip, 0.0 , slack[rowindex]) ) 351 { 352 sgn = -1; 353 } 354 355 contribution = getPotentialContributed(scip, sol, var, vals[i], sgn); 356 357 if( !SCIPisInfinity(scip, REALABS(contribution)) ) 358 { 359 potential[rowindex] -= contribution; 360 } 361 else 362 { 363 inftycounter[rowindex]--; 364 } 365 366 assert(0 <= inftycounter[rowindex]); 367 if( 0 == inftycounter[rowindex] && REALABS(potential[rowindex]) < alpha * REALABS(slack[rowindex]) ) 368 { 369 /* revert the changes before */ 370 int j = i; 371 for( ; j >= 0; --j ) 372 { 373 sgn = 1; 374 if( 0 == slack[rowindex] ) 375 { 376 continue; 377 } 378 rowindex = SCIProwGetLPPos(rows[j]); 379 if( 0 > slack[rowindex]) 380 { 381 sgn = -1; 382 } 383 contribution = getPotentialContributed(scip, sol, var, vals[j], sgn); 384 if( !SCIPisInfinity(scip, REALABS(contribution)) ) 385 { 386 potential[rowindex] += contribution; 387 } 388 else 389 { 390 inftycounter[rowindex]++; 391 } 392 } 393 return SCIP_OKAY; 394 } 395 } 396 397 SCIP_CALL( SCIPfixVar(subscip, subvar, solval, &infeasible, fixed) ); 398 assert(!infeasible && *fixed); 399 heurdata->nvarfixed++; 400 SCIPdebugMsg(scip,"Variable %s is fixed to %g\n",SCIPvarGetName(var), 401 SCIPgetSolVal(scip, sol, var)); 402 403 return SCIP_OKAY; 404 } 405 406 /** checks if all integral variables in the given solution are integral. */ 407 static 408 SCIP_RETCODE checkCands( 409 SCIP* scip, /**< SCIP data structure */ 410 SCIP_SOL* sol, /**< solution pointer to the to be checked solution */ 411 SCIP_Bool roundit, /**< round fractional solution values of integer variables */ 412 SCIP_Bool* success /**< pointer to store if all integral variables are integral or could 413 * be rounded 414 */ 415 ) 416 { 417 SCIP_VAR** vars; 418 int nvars; 419 int nfracvars; 420 int nbinvars; 421 int nintvars; 422 int i; 423 424 assert(NULL != success); 425 assert(NULL != sol); 426 427 *success = TRUE; 428 429 /* get variable data */ 430 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) ); 431 432 /* check if the candidates are fractional and round them if necessary */ 433 nfracvars = nbinvars + nintvars; 434 for( i = 0; i < nfracvars; ++i) 435 { 436 SCIP_Real value = SCIPgetSolVal(scip, sol, vars[i]); 437 438 if( SCIPisInfinity(scip, REALABS(value)) ) 439 { 440 *success = FALSE; 441 SCIPdebugMsg(scip, "Variable with infinite solution value"); 442 443 return SCIP_OKAY; 444 } 445 if( !SCIPisFeasIntegral(scip, value) ) 446 { 447 if( roundit ) 448 { 449 SCIP_Real roundedvalue; 450 451 if( SCIPvarGetNLocksUpType(vars[i], SCIP_LOCKTYPE_MODEL) > SCIPvarGetNLocksDownType(vars[i], SCIP_LOCKTYPE_MODEL) ) 452 { 453 roundedvalue = SCIPceil(scip, value - 1.0); 454 } 455 else 456 { 457 roundedvalue = SCIPfloor(scip, value + 1.0); 458 } 459 460 SCIP_CALL( SCIPsetSolVal(scip, sol, vars[i], roundedvalue) ); 461 } 462 else 463 { 464 *success = FALSE; 465 SCIPdebugMsg(scip, "Repair: All variables are integral.\n"); 466 return SCIP_OKAY; 467 } 468 } 469 } 470 471 /* ensure that no other variables have infinite LP solution values */ 472 for( ; i < nvars; ++i ) 473 { 474 if( SCIPisInfinity(scip, REALABS(SCIPgetSolVal(scip, sol, vars[i]))) ) 475 { 476 *success = FALSE; 477 SCIPdebugMsg(scip, "Variable with infinite solution value"); 478 479 return SCIP_OKAY; 480 } 481 } 482 483 SCIPdebugMsg(scip, "All variables rounded.\n"); 484 return SCIP_OKAY; 485 } 486 487 /** creates a new solution for the original problem by copying the solution of the subproblem */ 488 static 489 SCIP_RETCODE createNewSol( 490 SCIP* scip, /**< original SCIP data structure */ 491 SCIP* subscip, /**< SCIP structure of the subproblem */ 492 SCIP_VAR** subvars, /**< the variables of the subproblem */ 493 SCIP_HEUR* heur, /**< Repair heuristic structure */ 494 SCIP_SOL* subsol, /**< solution of the subproblem */ 495 SCIP_Bool* success /**< used to store whether new solution was found or not */ 496 ) 497 { 498 SCIP_SOL* newsol; /* solution to be created for the original problem */ 499 500 assert(scip != NULL); 501 assert(subscip != NULL); 502 assert(subvars != NULL); 503 assert(subsol != NULL); 504 505 SCIP_CALL( SCIPtranslateSubSol(scip, subscip, subsol, heur, subvars, &newsol) ); 506 507 /* try to add new solution to SCIP and free it immediately */ 508 SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, success) ); 509 510 #ifdef SCIP_STATISTIC 511 { 512 SCIP_HEURDATA* heurdata; 513 heurdata = SCIPheurGetData(heur); 514 515 if( *success ) 516 { 517 heurdata->originalsolval = SCIPgetSolOrigObj(scip, newsol); 518 } 519 } 520 #endif 521 522 return SCIP_OKAY; 523 } 524 525 /** tries to fix variables as an approach to repair a solution. */ 526 static 527 SCIP_RETCODE applyRepair( 528 SCIP* scip, /**< SCIP data structure of the problem */ 529 SCIP_HEUR* heur, /**< pointer to this heuristic instance */ 530 SCIP_RESULT* result, /**< pointer to return the result status */ 531 SCIP_Longint nnodes /**< nodelimit for sub-SCIP */ 532 ) 533 { 534 SCIP* subscip = NULL; 535 SCIP_VAR** vars = NULL; 536 SCIP_VAR** subvars = NULL; 537 SCIP_ROW** rows; 538 SCIP_CONS** subcons = NULL; 539 int* nviolatedrows = NULL; 540 int* permutation = NULL; 541 int* inftycounter = NULL; 542 SCIP_SOL* sol; 543 SCIP_SOL* subsol = NULL; 544 SCIP_HEURDATA* heurdata; 545 SCIP_Real* potential = NULL; 546 SCIP_Real* slacks = NULL; 547 SCIP_RETCODE retcode = SCIP_OKAY; 548 SCIP_Real timelimit; 549 SCIP_Real memorylimit; 550 SCIP_Real factor; 551 char probname[SCIP_MAXSTRLEN]; 552 int i; 553 int nbinvars; 554 int nintvars; 555 int nvars; 556 int nrows; 557 int ndiscvars; 558 int nfixeddiscvars; 559 SCIP_Bool success; 560 SCIP_Bool avoidmemout; 561 562 heurdata = SCIPheurGetData(heur); 563 sol = heurdata->infsol; 564 565 /* initializes the sub-SCIP */ 566 SCIP_CALL( SCIPcreate(&subscip) ); 567 SCIP_CALL( SCIPincludeDefaultPlugins(subscip) ); 568 SCIP_CALL( SCIPcopyParamSettings(scip, subscip) ); 569 570 /* use inference branching */ 571 if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") ) 572 { 573 SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) ); 574 } 575 576 /* get name of the original problem and add the string "_repairsub" */ 577 (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN, "%s_repairsub", SCIPgetProbName(scip)); 578 579 SCIP_CALL( SCIPcreateProb(subscip, probname, NULL, NULL, NULL, NULL, NULL, NULL, NULL) ); 580 581 /* a trivial feasible solution can be constructed if violations are modeled with slack variables */ 582 if( heurdata->useslackvars ) 583 { 584 SCIP_CALL( SCIPcreateSol(subscip, &subsol, heur) ); 585 } 586 587 /* gets all original variables */ 588 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) ); 589 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) ); 590 SCIP_CALL( SCIPallocBufferArray(scip, &nviolatedrows, nvars) ); 591 SCIP_CALL( SCIPallocBufferArray(scip, &permutation, nvars) ); 592 593 SCIPdebugMsg(scip,"\n\n Calling objective factor calculation \n\n"); 594 if( heurdata->useobjfactor ) 595 { 596 SCIP_CALL( getObjectiveFactor(scip, subscip, &factor, &success) ); 597 } 598 else 599 { 600 factor = 0.0; 601 } 602 603 /* adds all original variables */ 604 ndiscvars = 0; 605 for( i = 0; i < nvars; ++i ) 606 { 607 SCIP_CONS* cons; 608 SCIP_Real lb; 609 SCIP_Real ub; 610 SCIP_Real lborig; 611 SCIP_Real uborig; 612 SCIP_Real varslack; 613 SCIP_Real objval; 614 SCIP_Real value; 615 SCIP_VARTYPE vartype; 616 char varname[SCIP_MAXSTRLEN]; 617 char slackvarname[SCIP_MAXSTRLEN]; 618 char consvarname[SCIP_MAXSTRLEN]; 619 620 #ifdef SCIP_STATISTIC 621 heurdata->norigvars++; 622 #endif 623 624 varslack = 0.0; 625 lborig = SCIPvarGetLbGlobal(vars[i]); 626 uborig = SCIPvarGetUbGlobal(vars[i]); 627 value = SCIPgetSolVal(scip, sol, vars[i]); 628 vartype = SCIPvarGetType(vars[i]); 629 630 nviolatedrows[i] = 0; 631 632 /* if the value of x is lower than the variables lower bound, sets the slack to a correcting value */ 633 if( heurdata->useslackvars && SCIPisFeasLT(scip, value, lborig) ) 634 { 635 lb = value; 636 varslack = lborig - value; 637 } 638 else 639 { 640 lb = lborig; 641 } 642 643 /* if the value of x is bigger than the variables upper bound, sets the slack to a correcting value */ 644 if( heurdata->useslackvars && SCIPisFeasGT(scip, value, uborig) ) 645 { 646 ub = value; 647 varslack = uborig - value; 648 } 649 else 650 { 651 ub = uborig; 652 } 653 654 if( heurdata->useobjfactor ) 655 { 656 objval = SCIPvarGetObj(vars[i])*factor; 657 658 if( SCIPisZero(scip, objval) ) 659 { 660 objval = 0.0; 661 } 662 } 663 else 664 { 665 objval = SCIPvarGetObj(vars[i]); 666 } 667 668 /* if a binary variable is out of bound, generalize it to an integer variable */ 669 if( !SCIPisFeasZero(scip, varslack) && SCIP_VARTYPE_BINARY == vartype ) 670 { 671 vartype = SCIP_VARTYPE_INTEGER; 672 } 673 674 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "sub_%s", SCIPvarGetName(vars[i])); 675 676 /* Adds the sub representing variable to the sub-SCIP. */ 677 SCIP_CALL( SCIPcreateVarBasic(subscip, &subvars[i], varname, lb, ub, objval, vartype) ); 678 SCIP_CALL( SCIPaddVar(subscip, subvars[i]) ); 679 680 /* a trivial feasible solution can be constructed if violations are modeled with slack variables */ 681 if( heurdata->useslackvars ) 682 { 683 SCIP_CALL( SCIPsetSolVal(subscip, subsol, subvars[i], value) ); 684 } 685 686 /* if necessary adds a constraint to represent the original bounds of x.*/ 687 if( !SCIPisFeasEQ(scip, varslack, 0.0) ) 688 { 689 SCIP_VAR* newvar; 690 (void) SCIPsnprintf(slackvarname, SCIP_MAXSTRLEN, "artificialslack_%s", SCIPvarGetName(vars[i])); 691 (void) SCIPsnprintf(consvarname, SCIP_MAXSTRLEN, "boundcons_%s", SCIPvarGetName(vars[i])); 692 693 /* initialize and add an artificial slack variable */ 694 if( heurdata->useobjfactor ) 695 { 696 SCIP_CALL( SCIPcreateVarBasic(subscip, &newvar, slackvarname, 0.0, 1.0, 1.0, SCIP_VARTYPE_CONTINUOUS)); 697 } 698 else 699 { 700 SCIP_CALL( SCIPcreateVarBasic(subscip, &newvar, slackvarname, 0.0, 1.0, 1.0, SCIP_VARTYPE_BINARY)); 701 } 702 SCIP_CALL( SCIPaddVar(subscip, newvar) ); 703 704 /* set the value of the slack variable to 1 to punish the use of it. 705 * note that a trivial feasible solution can be only constructed if violations are modeled with slack variables 706 */ 707 if( heurdata->useslackvars ) 708 { 709 SCIP_CALL( SCIPsetSolVal(subscip, subsol, newvar, 1.0) ); 710 } 711 712 /* adds a linear constraint to represent the old bounds */ 713 SCIP_CALL( SCIPcreateConsBasicVarbound(subscip, &cons, consvarname, subvars[i], newvar, varslack, lb, ub) ); 714 SCIP_CALL( SCIPaddCons(subscip, cons) ); 715 SCIP_CALL( SCIPreleaseVar(subscip, &newvar) ); 716 SCIP_CALL( SCIPreleaseCons(subscip, &cons) ); 717 718 /* increases the counter for violated vars */ 719 #ifdef SCIP_STATISTIC 720 heurdata->nviolatedvars++; 721 #endif 722 } 723 724 #ifdef SCIP_STATISTIC 725 if( SCIPisFeasLT(scip, value, lb) || SCIPisFeasGT(scip, value, ub) ) 726 { 727 heurdata->nviolatedvars++; 728 } 729 #endif 730 if( SCIP_VARTYPE_BINARY == vartype || SCIP_VARTYPE_INTEGER == vartype ) 731 { 732 ndiscvars++; 733 } 734 } 735 736 /* check solution for feasibility regarding the LP rows (SCIPgetRowSolActivity()) */ 737 rows = SCIPgetLPRows(scip); 738 nrows = SCIPgetNLPRows(scip); 739 740 SCIP_CALL( SCIPallocBufferArray(scip, &potential, nrows) ); 741 SCIP_CALL( SCIPallocBufferArray(scip, &slacks, nrows) ); 742 SCIP_CALL( SCIPallocBufferArray(scip, &subcons, nrows) ); 743 SCIP_CALL( SCIPallocBufferArray(scip, &inftycounter, nrows) ); 744 745 /* Adds all original constraints and computes potentials and slacks */ 746 for (i = 0; i < nrows; ++i) 747 { 748 SCIP_COL** cols; 749 SCIP_VAR** consvars; 750 SCIP_Real* vals; 751 SCIP_Real constant; 752 SCIP_Real lhs; 753 SCIP_Real rhs; 754 SCIP_Real rowsolact; 755 int nnonz; 756 int j; 757 758 #ifdef SCIP_STATISTIC 759 heurdata->norcons++; 760 #endif 761 762 /* gets the values to check the constraint */ 763 constant = SCIProwGetConstant(rows[i]); 764 lhs = SCIPisInfinity(scip, -SCIProwGetLhs(rows[i])) ? SCIProwGetLhs(rows[i]) : SCIProwGetLhs(rows[i]) - constant; 765 rhs = SCIPisInfinity(scip, SCIProwGetRhs(rows[i])) ? SCIProwGetRhs(rows[i]) : SCIProwGetRhs(rows[i]) - constant; 766 rowsolact = SCIPgetRowSolActivity(scip, rows[i], sol) - constant; 767 vals = SCIProwGetVals(rows[i]); 768 potential[i] = 0.0; 769 inftycounter[i] = 0; 770 771 assert(SCIPisFeasLE(scip, lhs, rhs)); 772 773 nnonz = SCIProwGetNNonz(rows[i]); 774 cols = SCIProwGetCols(rows[i]); 775 SCIP_CALL( SCIPallocBufferArray(subscip, &consvars, nnonz) ); 776 777 /* sets the slack if its necessary */ 778 if( SCIPisFeasLT(scip, rowsolact, lhs) ) 779 { 780 slacks[i] = lhs - rowsolact; 781 #ifdef SCIP_STATISTIC 782 heurdata->nviolatedcons++; 783 #endif 784 } 785 else if( SCIPisFeasGT(scip, rowsolact, rhs) ) 786 { 787 slacks[i] = rhs - rowsolact; 788 #ifdef SCIP_STATISTIC 789 heurdata->nviolatedcons++; 790 #endif 791 } 792 else 793 { 794 slacks[i] = 0.0; 795 } 796 797 /* translate all variables from the original SCIP to the sub-SCIP with sub-SCIP variables. */ 798 for( j = 0; j < nnonz; ++j ) 799 { 800 SCIP_Real contribution; 801 int pos; 802 int sgn = 1; 803 804 /* negative slack represents a right hand side violation */ 805 if( SCIPisFeasGT(scip, 0.0, slacks[i]) ) 806 { 807 assert(!SCIPisInfinity(scip, rhs)); 808 sgn = -1; 809 } 810 #ifndef NDEBUG 811 else 812 assert(!SCIPisInfinity(scip, lhs)); 813 #endif 814 815 pos = SCIPvarGetProbindex(SCIPcolGetVar(cols[j])); 816 consvars[j] = subvars[pos]; 817 assert(pos >= 0); 818 819 /* compute potentials */ 820 contribution = getPotentialContributed(scip, sol, vars[pos], vals[j], sgn); 821 if( !SCIPisInfinity(scip, REALABS(contribution)) ) 822 { 823 potential[i] += contribution; 824 } 825 else 826 { 827 inftycounter[i]++; 828 } 829 830 if( !SCIPisZero(scip, slacks[i]) ) 831 { 832 nviolatedrows[pos]++; 833 } 834 } 835 836 /* create a new linear constraint, representing the old one */ 837 SCIP_CALL( SCIPcreateConsBasicLinear(subscip, &subcons[i], SCIProwGetName(rows[i]), 838 nnonz, consvars, vals, lhs, rhs) ); 839 840 if( heurdata->useslackvars ) 841 { 842 SCIP_VAR* newvar; 843 char varname[SCIP_MAXSTRLEN]; 844 845 /*if necessary adds a new artificial slack variable*/ 846 if( !SCIPisFeasEQ(subscip, slacks[i], 0.0) ) 847 { 848 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "artificialslack_%s", SCIProwGetName(rows[i])); 849 SCIP_CALL( SCIPcreateVarBasic(subscip, &newvar, varname, 0.0, 1.0, 1.0, SCIP_VARTYPE_CONTINUOUS) ); 850 SCIP_CALL( SCIPaddVar(subscip, newvar) ); 851 852 /* a trivial feasible solution can be constructed if violations are modeled with slack variables */ 853 SCIP_CALL( SCIPsetSolVal(subscip, subsol, newvar, 1.0) ); 854 SCIP_CALL( SCIPaddCoefLinear(subscip, subcons[i], newvar, slacks[i]) ); 855 SCIP_CALL( SCIPreleaseVar(subscip, &newvar) ); 856 } 857 } 858 859 /*Adds the Constraint and release it.*/ 860 SCIP_CALL( SCIPaddCons(subscip, subcons[i]) ); 861 SCIP_CALL( SCIPreleaseCons(subscip, &subcons[i]) ); 862 SCIPfreeBufferArray(subscip, &consvars); 863 } 864 865 if( heurdata->usevarfix ) 866 { 867 /* get the greedy order */ 868 for( i = 0; i < nvars; ++i ) 869 { 870 permutation[i] = i; 871 } 872 SCIPsortIntInt(nviolatedrows, permutation, nvars); 873 874 /* loops over variables and greedily fix variables, but preserve the cover property that enough slack is given to 875 * violated rows 876 */ 877 nfixeddiscvars = 0; 878 heurdata->nvarfixed = 0; 879 for( i = 0; i < nvars; ++i ) 880 { 881 SCIP_Bool fixed; 882 883 /* continue if we have a loose variable */ 884 if( SCIPvarGetStatus(vars[permutation[i]]) != SCIP_VARSTATUS_COLUMN ) 885 continue; 886 887 SCIP_CALL( tryFixVar(scip, subscip, sol, potential, slacks, vars[permutation[i]], subvars[permutation[i]], inftycounter, heurdata, &fixed) ); 888 889 if( fixed && (SCIP_VARTYPE_BINARY == SCIPvarGetType(subvars[permutation[i]]) 890 || SCIP_VARTYPE_INTEGER == SCIPvarGetType(subvars[permutation[i]])) ) 891 { 892 nfixeddiscvars++; 893 } 894 } 895 SCIPdebugMsg(scip,"fixings finished\n\n"); 896 if( heurdata->minfixingrate > ((SCIP_Real)nfixeddiscvars/MAX((SCIP_Real)ndiscvars,1.0)) ) 897 { 898 goto TERMINATE; 899 } 900 } 901 902 /* a trivial feasible solution can be constructed if violations are modeled with slack variables */ 903 if( heurdata->useslackvars ) 904 { 905 SCIP_CALL( SCIPaddSolFree(subscip, &subsol, &success) ); 906 907 if( !success ) 908 { 909 SCIPdebugMsg(scip, "Initial repair solution was not accepted.\n"); 910 } 911 } 912 913 #ifdef SCIP_STATISTIC 914 if( heurdata->useslackvars ) 915 heurdata->improvedoldsol = SCIPgetSolOrigObj(subscip, subsol); 916 #endif 917 918 /* check whether there is enough time and memory left */ 919 SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) ); 920 if( !SCIPisInfinity(scip, timelimit) ) 921 timelimit -= SCIPgetSolvingTime(scip); 922 SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) ); 923 SCIP_CALL( SCIPgetBoolParam(scip, "misc/avoidmemout", &avoidmemout) ); 924 925 /* subtract the memory already used by the main SCIP and the estimated memory usage of external software */ 926 if( !SCIPisInfinity(scip, memorylimit) ) 927 { 928 memorylimit -= SCIPgetMemUsed(scip) / 1048576.0; 929 memorylimit -= SCIPgetMemExternEstim(scip) / 1048576.0; 930 } 931 932 /* abort if no time is left or not enough memory (we don't abort in this case if misc_avoidmemout == FALSE) 933 * to create a copy of SCIP, including external memory usage */ 934 if( timelimit <= 0.0 || (avoidmemout && memorylimit <= 2.0 * SCIPgetMemExternEstim(scip) / 1048576.0) ) 935 goto TERMINATE; 936 937 /* set limits for the subproblem */ 938 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nnodes) ); 939 SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) ); 940 SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) ); 941 SCIP_CALL( SCIPsetObjlimit(subscip,1.0) ); 942 943 /* forbid recursive call of heuristics and separators solving sub-SCIPs */ 944 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) ); 945 946 /* disable output to console */ 947 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", (int)SCIP_VERBLEVEL_NONE) ); 948 949 #ifdef SCIP_DEBUG 950 /* for debugging Repair, enable MIP output */ 951 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", (int)SCIP_VERBLEVEL_FULL) ); 952 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", -1) ); 953 #endif 954 955 /* solve the subproblem */ 956 retcode = SCIPsolve(subscip); 957 958 /* errors in sub-SCIPs should not kill the overall solving process. Hence, we print a warning message. Only 959 * in debug mode, SCIP will stop 960 */ 961 if( retcode != SCIP_OKAY ) 962 { 963 SCIPwarningMessage(scip, "Error while solving subproblem in REPAIR heuristic; sub-SCIP terminated with code <%d>\n", retcode); 964 SCIPABORT(); /*lint --e{527}*/ 965 goto TERMINATE; 966 } 967 968 success = FALSE; 969 970 /* if a solution is found, save its value and create a new solution instance for the original SCIP */ 971 if( SCIPgetBestSol(subscip) != NULL ) 972 { 973 #ifdef SCIP_STATISTIC 974 heurdata->improvedoldsol = SCIPgetSolOrigObj(subscip, SCIPgetBestSol(subscip)); 975 #endif 976 /* print solving statistics of subproblem if we are in SCIP's debug mode */ 977 SCIPdebug( SCIP_CALL( SCIPprintStatistics(subscip, NULL) ) ); 978 979 assert(SCIPgetNSols(subscip) > 0); 980 SCIP_CALL( createNewSol(scip, subscip, subvars, heur, SCIPgetBestSol(subscip), &success) ); 981 982 if( success ) 983 { 984 *result = SCIP_FOUNDSOL; 985 } 986 } 987 else 988 { 989 SCIPdebugMsg(scip,"No solution found!\n"); 990 } 991 992 if( SCIPgetStage(subscip) >= SCIP_STAGE_SOLVED ) 993 { 994 heurdata->subiters = SCIPgetNLPIterations(subscip); 995 heurdata->subnodes = SCIPgetNTotalNodes(subscip); 996 #ifdef SCIP_STATISTIC 997 heurdata->subpresoltime = SCIPgetPresolvingTime(subscip); 998 #endif 999 heurdata->runs = SCIPgetNRuns(subscip); 1000 } 1001 1002 /* terminates the solving process */ 1003 TERMINATE: 1004 if( NULL != sol ) 1005 { 1006 SCIP_CALL( SCIPfreeSol(scip, &sol) ); 1007 } 1008 SCIPfreeBufferArrayNull(scip, &nviolatedrows); 1009 for( i = 0; i < nvars; ++i ) 1010 { 1011 SCIP_CALL( SCIPreleaseVar(subscip, &subvars[i]) ); 1012 } 1013 SCIPfreeBufferArrayNull(scip, &inftycounter); 1014 SCIPfreeBufferArrayNull(scip, &subcons); 1015 SCIPfreeBufferArrayNull(scip, &slacks); 1016 SCIPfreeBufferArrayNull(scip, &potential); 1017 SCIPfreeBufferArrayNull(scip, &permutation); 1018 SCIPfreeBufferArrayNull(scip, &subvars); 1019 1020 if( NULL != subsol ) 1021 { 1022 SCIP_CALL( SCIPfreeSol(subscip, &subsol) ); 1023 } 1024 1025 SCIP_CALL( SCIPfree(&subscip) ); 1026 1027 SCIPdebugMsg(scip, "repair finished\n"); 1028 return SCIP_OKAY; 1029 } 1030 1031 1032 /* 1033 * Callback methods of primal heuristic 1034 */ 1035 1036 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */ 1037 static 1038 SCIP_DECL_HEURFREE(heurFreeRepair) 1039 { /*lint --e{715}*/ 1040 SCIP_HEURDATA* heurdata; 1041 1042 heurdata = SCIPheurGetData(heur); 1043 1044 assert(heurdata != NULL); 1045 SCIPfreeMemory(scip, &heurdata); 1046 1047 SCIPheurSetData(heur, NULL); 1048 1049 return SCIP_OKAY; 1050 } 1051 1052 1053 /** initialization method of primal heuristic (called after problem was transformed) */ 1054 static 1055 SCIP_DECL_HEURINIT(heurInitRepair) 1056 { /*lint --e{715}*/ 1057 SCIP_HEURDATA* heurdata; 1058 1059 heurdata = SCIPheurGetData(heur); 1060 1061 heurdata->subiters = -1; 1062 heurdata->subnodes = -1; 1063 heurdata->runs = 0; 1064 1065 heurdata->nvarfixed = 0; 1066 heurdata->relvarfixed = -1; 1067 1068 #ifdef SCIP_STATISTIC 1069 heurdata->subpresoltime = 0; 1070 1071 heurdata->nviolatedvars = 0; 1072 heurdata->norigvars = 0; 1073 heurdata->relviolatedvars = 0; 1074 heurdata->nviolatedcons = 0; 1075 heurdata->norcons = 0; 1076 heurdata->relviolatedcons = 0; 1077 1078 heurdata->originalsolval = SCIP_INVALID; 1079 1080 heurdata->improvedoldsol = SCIP_UNKNOWN; 1081 #endif 1082 1083 heurdata->usednodes = 0; 1084 1085 return SCIP_OKAY; 1086 } 1087 1088 1089 /** deinitialization method of primal heuristic (called before transformed problem is freed) */ 1090 static 1091 SCIP_DECL_HEUREXIT(heurExitRepair) 1092 { /*lint --e{715}*/ 1093 #ifdef SCIP_STATISTIC 1094 SCIP_HEURDATA* heurdata; 1095 SCIP_Real time; 1096 SCIP_Real relvars; 1097 SCIP_Real relcons; 1098 SCIP_Real relfixed; 1099 char solval[SCIP_MAXSTRLEN]; 1100 int violateds; 1101 int ninvars; 1102 int ninvcons; 1103 int nvars; 1104 int ncons; 1105 int iterations; 1106 int nodes; 1107 int runs; 1108 1109 heurdata = SCIPheurGetData(heur); 1110 violateds = heurdata->nviolatedvars+heurdata->nviolatedcons; 1111 ninvars = heurdata->nviolatedvars; 1112 ninvcons = heurdata->nviolatedcons; 1113 nvars = heurdata->norigvars; 1114 ncons = heurdata->norcons; 1115 iterations = heurdata->subiters; 1116 nodes = heurdata->subnodes; 1117 time = heurdata->subpresoltime; 1118 runs = heurdata->runs; 1119 1120 if( SCIP_INVALID == heurdata->originalsolval ) 1121 { 1122 (void) SCIPsnprintf(solval, SCIP_MAXSTRLEN ,"--"); 1123 } 1124 else 1125 { 1126 (void) SCIPsnprintf(solval, SCIP_MAXSTRLEN, "%15.9g", heurdata->originalsolval); 1127 } 1128 1129 heurdata->relviolatedvars = MAX((SCIP_Real)heurdata->norigvars, 1.0); 1130 heurdata->relviolatedvars = heurdata->nviolatedvars/heurdata->relviolatedvars; 1131 heurdata->relviolatedcons = MAX((SCIP_Real)heurdata->norcons, 1.0); 1132 heurdata->relviolatedcons = heurdata->nviolatedcons/heurdata->relviolatedcons; 1133 1134 heurdata->relvarfixed = MAX((SCIP_Real)heurdata->norigvars, 1.0); 1135 heurdata->relvarfixed = heurdata->nvarfixed/heurdata->relvarfixed; 1136 relvars = heurdata->relviolatedvars; 1137 relcons = heurdata->relviolatedcons; 1138 relfixed = heurdata->relvarfixed; 1139 1140 /* prints all statistic data for a user*/ 1141 SCIPstatistic( 1142 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "<repair> \n total violations : %10d\n", violateds); 1143 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " violated variables : %10d\n", ninvars); 1144 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " total variables : %10d\n", nvars); 1145 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " relative violated variables : %10.2f%%\n", 100 * relvars); 1146 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " violated constraints : %10d\n", ninvcons); 1147 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " total constraints : %10d\n", ncons); 1148 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " relative violated constraints: %10.2f%%\n", 100* relcons); 1149 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " fixed variables : %10d\n", heurdata->nvarfixed); 1150 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " relative fixed variables : %10.2f%%\n\n", 100* relfixed); 1151 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " iterations : %10d\n", iterations); 1152 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " nodes : %10d\n", nodes); 1153 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " number of runs : %10d\n", runs); 1154 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " presolve time : %10.2f\n", time); 1155 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "</repair>\n\n"); 1156 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " value of best solution : %10g\n", solval); 1157 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " improved orig. solval : %10g\n", heurdata->improvedoldsol); 1158 ) 1159 1160 #endif 1161 return SCIP_OKAY; 1162 } 1163 1164 /** execution method of primal heuristic. Repair needs an incorrect solution, in which all variables are in their bound. */ 1165 static 1166 SCIP_DECL_HEUREXEC(heurExecRepair) 1167 { /*lint --e{715}*/ 1168 SCIP_HEURDATA* heurdata; 1169 SCIP_RETCODE retcode; 1170 SCIP_Bool success; 1171 SCIP_Bool error; 1172 SCIP_Longint nnodes; 1173 1174 heurdata = SCIPheurGetData(heur); 1175 SCIPdebugMsg(scip, "%s\n", heurdata->filename); 1176 1177 /* checks the result pointer */ 1178 assert(result != NULL); 1179 *result = SCIP_DIDNOTRUN; 1180 1181 /* if repair already ran or neither variable fixing nor slack variables are enabled, stop */ 1182 if( 0 < SCIPheurGetNCalls(heur) || !(heurdata->usevarfix || heurdata->useslackvars) ) 1183 return SCIP_OKAY; 1184 1185 /* do not run if the neither the LP is constructed nor a user given solution exists */ 1186 if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL && strcmp(heurdata->filename, DEFAULT_FILENAME) == 0 ) 1187 return SCIP_OKAY; 1188 1189 /* calculate the maximal number of branching nodes until heuristic is aborted */ 1190 nnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip)); 1191 1192 /* reward REPAIR if it succeeded often */ 1193 nnodes = (SCIP_Longint)(nnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0)); 1194 nnodes -= (SCIP_Longint)(100.0 * SCIPheurGetNCalls(heur)); /* count the setup costs for the sub-MIP as 100 nodes */ 1195 nnodes += heurdata->nodesofs; 1196 1197 /* determine the node limit for the current process */ 1198 nnodes -= heurdata->usednodes; 1199 nnodes = MIN(nnodes, heurdata->maxnodes); 1200 1201 /* check whether we have enough nodes left to call subproblem solving */ 1202 if( nnodes < heurdata->minnodes ) 1203 return SCIP_OKAY; 1204 1205 if( !SCIPhasCurrentNodeLP(scip) ) 1206 return SCIP_OKAY; 1207 1208 if( !SCIPisLPConstructed(scip) ) 1209 { 1210 SCIP_Bool cutoff; 1211 1212 SCIP_CALL( SCIPconstructLP(scip, &cutoff) ); 1213 1214 /* manually cut off the node if the LP construction detected infeasibility (heuristics cannot return such a result) */ 1215 if( cutoff ) 1216 { 1217 SCIP_CALL( SCIPcutoffNode(scip, SCIPgetCurrentNode(scip)) ); 1218 return SCIP_OKAY; 1219 } 1220 } 1221 1222 /* create original solution */ 1223 SCIP_CALL( SCIPcreateOrigSol(scip, &(heurdata->infsol), heur) ); 1224 1225 /* use read method to enter solution from a file */ 1226 if( strcmp(heurdata->filename, DEFAULT_FILENAME) == 0 ) 1227 { 1228 retcode = SCIPlinkLPSol(scip, heurdata->infsol); 1229 } 1230 else 1231 { 1232 error = FALSE; 1233 retcode = SCIPreadSolFile(scip, heurdata->filename, heurdata->infsol, FALSE, NULL, &error); 1234 } 1235 1236 if( SCIP_NOFILE == retcode ) 1237 { 1238 assert(strcmp(heurdata->filename, DEFAULT_FILENAME) != 0); 1239 SCIPwarningMessage(scip, "cannot open file <%s> for reading\n", heurdata->filename); 1240 1241 SCIP_CALL( SCIPfreeSol(scip, &(heurdata->infsol)) ); 1242 return SCIP_OKAY; 1243 } 1244 else if( retcode != SCIP_OKAY ) 1245 { 1246 SCIPwarningMessage(scip, "cannot run repair, unknown return status <%d>\n", retcode); 1247 SCIP_CALL( SCIPfreeSol(scip, &(heurdata->infsol)) ); 1248 return SCIP_OKAY; 1249 } 1250 SCIPdebugMsg(scip, "Repair: Solution file read.\n"); 1251 1252 /* checks the integrality of all discrete variable */ 1253 SCIP_CALL( checkCands(scip, heurdata->infsol, heurdata->roundit, &success) ); 1254 if( !success ) 1255 { 1256 SCIPdebugMsg(scip,"Given solution is not integral, repair terminates.\n"); 1257 SCIP_CALL( SCIPfreeSol(scip, &(heurdata->infsol)) ); 1258 return SCIP_OKAY; 1259 } 1260 1261 *result = SCIP_DIDNOTFIND; 1262 1263 SCIP_CALL( SCIPtrySol(scip, heurdata->infsol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) ); 1264 1265 /* the solution is not feasible for the original problem; we will try to repair it */ 1266 if( !success ) 1267 { 1268 assert(NULL != heurdata->infsol); 1269 assert(heurdata->usevarfix || heurdata->useslackvars); 1270 SCIP_CALL( applyRepair(scip, heur, result, nnodes) ); 1271 } 1272 else 1273 { 1274 SCIP_CALL( SCIPfreeSol(scip, &(heurdata->infsol)) ); 1275 } 1276 1277 return SCIP_OKAY; 1278 } 1279 1280 /* primal heuristic specific interface methods */ 1281 1282 /** creates the repair primal heuristic and includes it in SCIP */ 1283 SCIP_RETCODE SCIPincludeHeurRepair( 1284 SCIP* scip /**< SCIP data structure */ 1285 ) 1286 { 1287 SCIP_HEURDATA* heurdata; 1288 SCIP_HEUR* heur; 1289 1290 /* create repair primal heuristic data */ 1291 heurdata = NULL; 1292 1293 SCIP_CALL( SCIPallocMemory(scip ,&heurdata) ); 1294 1295 heur = NULL; 1296 1297 /* include primal heuristic */ 1298 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, 1299 HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS, 1300 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecRepair, heurdata) ); 1301 1302 assert(heur != NULL); 1303 assert(heurdata != NULL); 1304 1305 /* set non fundamental callbacks via setter functions */ 1306 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeRepair) ); 1307 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitRepair) ); 1308 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitRepair) ); 1309 1310 /* add repair primal heuristic parameters */ 1311 1312 heurdata->filename = NULL; 1313 /* add string parameter for filename containing a solution */ 1314 SCIP_CALL( SCIPaddStringParam(scip, "heuristics/" HEUR_NAME "/filename", 1315 "file name of a solution to be used as infeasible starting point, [-] if not available", 1316 &heurdata->filename, FALSE, DEFAULT_FILENAME, NULL, NULL) ); 1317 1318 /* add bool parameter for decision how to deal with unfractional cands */ 1319 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/roundit", 1320 "True : fractional variables which are not fractional in the given solution are rounded, " 1321 "FALSE : solving process of this heuristic is stopped. ", 1322 &heurdata->roundit, FALSE, DEFAULT_ROUNDIT, NULL, NULL)); 1323 1324 /* add bool parameter for decision how the objective function should be */ 1325 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useobjfactor", 1326 "should a scaled objective function for original variables be used in repair subproblem?", 1327 &heurdata->useobjfactor, FALSE, DEFAULT_USEOBJFACTOR, NULL, NULL)); 1328 1329 /* add bool parameter for decision if variable fixings should be used */ 1330 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/usevarfix", 1331 "should variable fixings be used in repair subproblem?", 1332 &heurdata->usevarfix, FALSE, DEFAULT_USEVARFIX, NULL, NULL)); 1333 1334 /* add bool parameter for decision how the objective function should be */ 1335 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/useslackvars", 1336 "should slack variables be used in repair subproblem?", 1337 &heurdata->useslackvars, FALSE, DEFAULT_USESLACKVARS, NULL, NULL)); 1338 1339 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/alpha", "factor for the potential of var fixings", 1340 &heurdata->alpha, TRUE, DEFAULT_ALPHA, 0.0, 100.00, NULL, NULL) ); 1341 1342 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nodesofs", 1343 "number of nodes added to the contingent of the total nodes", 1344 &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0, INT_MAX, NULL, NULL) ); 1345 1346 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxnodes", 1347 "maximum number of nodes to regard in the subproblem", 1348 &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0, INT_MAX, NULL, NULL) ); 1349 1350 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/minnodes", 1351 "minimum number of nodes required to start the subproblem", 1352 &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0, INT_MAX, NULL, NULL) ); 1353 1354 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot", 1355 "contingent of sub problem nodes in relation to the number of nodes of the original problem", 1356 &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) ); 1357 1358 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minfixingrate", 1359 "minimum percentage of integer variables that have to be fixed", 1360 &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, 0.0, 1.0, NULL, NULL) ); 1361 1362 return SCIP_OKAY; 1363 } 1364