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 cons_components.c 26 * @ingroup DEFPLUGINS_CONS 27 * @brief constraint handler for handling independent components 28 * @author Gerald Gamrath 29 * 30 * This constraint handler looks for independent components. 31 */ 32 /*#define DETAILED_OUTPUT*/ 33 /*#define SCIP_DEBUG*/ 34 /*#define SCIP_MORE_DEBUG*/ 35 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 36 37 #include "blockmemshell/memory.h" 38 #include "scip/cons_components.h" 39 #include "scip/debug.h" 40 #include "scip/pub_cons.h" 41 #include "scip/pub_heur.h" 42 #include "scip/pub_message.h" 43 #include "scip/pub_misc.h" 44 #include "scip/pub_misc_sort.h" 45 #include "scip/pub_sol.h" 46 #include "scip/pub_tree.h" 47 #include "scip/pub_var.h" 48 #include "scip/scip_cons.h" 49 #include "scip/scip_copy.h" 50 #include "scip/scip_datastructures.h" 51 #include "scip/scip_general.h" 52 #include "scip/scip_heur.h" 53 #include "scip/scip_mem.h" 54 #include "scip/scip_message.h" 55 #include "scip/scip_numerics.h" 56 #include "scip/scip_param.h" 57 #include "scip/scip_pricer.h" 58 #include "scip/scip_prob.h" 59 #include "scip/scip_probing.h" 60 #include "scip/scip_sol.h" 61 #include "scip/scip_solve.h" 62 #include "scip/scip_solvingstats.h" 63 #include "scip/scip_timing.h" 64 #include "scip/scip_tree.h" 65 #include "scip/scip_var.h" 66 #include <string.h> 67 68 #define CONSHDLR_NAME "components" 69 #define CONSHDLR_DESC "independent components constraint handler" 70 #define CONSHDLR_ENFOPRIORITY 0 /**< priority of the constraint handler for constraint enforcing */ 71 #define CONSHDLR_CHECKPRIORITY -9999999 /**< priority of the constraint handler for checking feasibility */ 72 #define CONSHDLR_EAGERFREQ -1 /**< frequency for using all instead of only the useful constraints in separation, 73 * propagation and enforcement, -1 for no eager evaluations, 0 for first only */ 74 #define CONSHDLR_NEEDSCONS FALSE /**< should the constraint handler be skipped, if no constraints are available? */ 75 76 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */ 77 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */ 78 #define CONSHDLR_DELAYPROP TRUE /**< should propagation method be delayed, if other propagators found reductions? */ 79 80 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_FINAL /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */ 81 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP /**< propagation timing mask of the constraint handler*/ 82 83 #define DEFAULT_MAXDEPTH -1 /**< maximum depth of a node to run components detection (-1: disable component detection during solving) */ 84 #define DEFAULT_MAXINTVARS 500 /**< maximum number of integer (or binary) variables to solve a subproblem directly in presolving (-1: no solving) */ 85 #define DEFAULT_MINSIZE 50 /**< minimum absolute size (in terms of variables) to solve a component individually during branch-and-bound */ 86 #define DEFAULT_MINRELSIZE 0.1 /**< minimum relative size (in terms of variables) to solve a component individually during branch-and-bound */ 87 #define DEFAULT_NODELIMIT 10000LL /**< maximum number of nodes to be solved in subproblems during presolving */ 88 #define DEFAULT_INTFACTOR 1.0 /**< the weight of an integer variable compared to binary variables */ 89 #define DEFAULT_FEASTOLFACTOR 1.0 /**< default value for parameter to increase the feasibility tolerance in all sub-SCIPs */ 90 91 /* 92 * Data structures 93 */ 94 95 /** data related to one problem (see below) */ 96 typedef struct Problem PROBLEM; 97 98 /** data related to one component */ 99 typedef struct Component 100 { 101 PROBLEM* problem; /**< the problem this component belongs to */ 102 SCIP* subscip; /**< sub-SCIP representing the component */ 103 SCIP_SOL* workingsol; /**< working solution for transferring solutions into the sub-SCIP */ 104 SCIP_VAR** vars; /**< variables belonging to this component (in complete problem) */ 105 SCIP_VAR** subvars; /**< variables belonging to this component (in subscip) */ 106 SCIP_VAR** fixedvars; /**< variables in the original SCIP which were copied while copying the component's 107 * constraints, but do not count to the subvars, because they were locally fixed */ 108 SCIP_VAR** fixedsubvars; /**< variables in the sub-SCIP which were copied while copying the component's 109 * constraints, but do not count to the subvars, because they were locally fixed */ 110 SCIP_Real fixedvarsobjsum; /**< objective contribution of all locally fixed variables */ 111 SCIP_Real lastdualbound; /**< dual bound after last optimization call for this component */ 112 SCIP_Real lastprimalbound; /**< primal bound after last optimization call for this component */ 113 SCIP_STATUS laststatus; /**< solution status of last optimization call for the sub-SCIP of this component */ 114 SCIP_Bool solved; /**< was this component solved already? */ 115 int ncalls; /**< number of optimization calls for this component */ 116 int lastsolindex; /**< index of best solution after last optimization call for this component */ 117 int lastbestsolindex; /**< index of last best solution transferred to this component from the main problem */ 118 int nvars; /**< number of variables belonging to this component */ 119 int nfixedvars; /**< number of fixed variables copied during constraint copying */ 120 int fixedvarssize; /**< size of fixedvars and fixedsubvars arrays */ 121 int number; /**< component number */ 122 } COMPONENT; 123 124 /** data related to one problem 125 * (corresponding to one node in the branch-and-bound tree and consisting of multiple components) 126 */ 127 struct Problem 128 { 129 SCIP* scip; /**< the SCIP instance this problem belongs to */ 130 COMPONENT* components; /**< independent components into which the problem can be divided */ 131 SCIP_PQUEUE* compqueue; /**< priority queue for components */ 132 SCIP_SOL* bestsol; /**< best solution found so far for the problem */ 133 char* name; /**< name of the problem */ 134 SCIP_Real fixedvarsobjsum; /**< objective contribution of all locally fixed variables */ 135 SCIP_Real lowerbound; /**< lower bound of the problem */ 136 int ncomponents; /**< number of independent components into which the problem can be divided */ 137 int componentssize; /**< size of components array */ 138 int nfeascomps; /**< number of components for which a feasible solution was found */ 139 int nsolvedcomps; /**< number of components solved to optimality */ 140 int nlowerboundinf; /**< number of components with lower bound equal to -infinity */ 141 }; 142 143 144 /** constraint handler data */ 145 struct SCIP_ConshdlrData 146 { 147 SCIP_Longint nodelimit; /**< maximum number of nodes to be solved in subproblems */ 148 SCIP_Real intfactor; /**< the weight of an integer variable compared to binary variables */ 149 SCIP_Real feastolfactor; /**< parameter to increase the feasibility tolerance in all sub-SCIPs */ 150 int maxintvars; /**< maximum number of integer (or binary) variables to solve a subproblem 151 * directly (-1: no solving) */ 152 int maxdepth; /**< maximum depth of a node to run components detection (-1: disable 153 * component detection during solving) */ 154 int minsize; /**< minimum absolute size (in terms of variables) to solve a component 155 * individually during branch-and-bound */ 156 SCIP_Real minrelsize; /**< minimum relative size (in terms of variables) to solve a component 157 * individually during branch-and-bound */ 158 int subscipdepth; /**< depth offset of the current (sub-)problem compared to the original 159 * problem */ 160 }; 161 162 163 /** comparison method for sorting components */ 164 static 165 SCIP_DECL_SORTPTRCOMP(componentSort) 166 { 167 SCIP* scip; 168 COMPONENT* comp1; 169 COMPONENT* comp2; 170 SCIP_Real gap1; 171 SCIP_Real gap2; 172 173 assert(elem1 != NULL); 174 assert(elem2 != NULL); 175 176 comp1 = (COMPONENT*)elem1; 177 comp2 = (COMPONENT*)elem2; 178 179 if( comp1->ncalls == 0 ) 180 if( comp2->ncalls == 0 ) 181 return comp1->number - comp2->number; 182 else 183 return -1; 184 else if( comp2->ncalls == 0 ) 185 return 1; 186 187 /* the main sorting criterion is the absolute gap; however, we devide it by the number of solving calls for this 188 * component to diversify the search if one component does not improve 189 * @todo investigate other sorting criteria 190 */ 191 gap1 = SQR(comp1->lastprimalbound - comp1->lastdualbound) / comp1->ncalls; 192 gap2 = SQR(comp2->lastprimalbound - comp2->lastdualbound) / comp2->ncalls; 193 194 assert(comp1->problem != NULL); 195 assert(comp1->problem == comp2->problem); 196 assert(comp1->problem->scip == comp2->problem->scip); 197 198 scip = comp1->problem->scip; 199 assert(scip != NULL); 200 201 if( SCIPisFeasGT(scip, gap1, gap2) ) 202 return -1; 203 else if( SCIPisFeasLT(scip, gap1, gap2) ) 204 return +1; 205 else 206 return comp1->number - comp2->number; 207 } 208 209 /** returns minimum size of components to be solved individually during the branch-and-bound search */ 210 static 211 int getMinsize( 212 SCIP* scip, /**< main SCIP data structure */ 213 SCIP_CONSHDLRDATA* conshdlrdata /**< constraint handler data */ 214 ) 215 { 216 int minsize; 217 218 assert(conshdlrdata != NULL); 219 220 minsize = (int)(conshdlrdata->minrelsize * SCIPgetNVars(scip)); 221 minsize = MAX(minsize, conshdlrdata->minsize); 222 223 return minsize; 224 } 225 226 /** initialize component structure */ 227 static 228 SCIP_RETCODE initComponent( 229 PROBLEM* problem /**< subproblem structure */ 230 ) 231 { 232 COMPONENT* component; 233 SCIP* scip; 234 235 assert(problem != NULL); 236 assert(problem->ncomponents < problem->componentssize); 237 238 scip = problem->scip; 239 assert(scip != NULL); 240 241 component = &problem->components[problem->ncomponents]; 242 243 component->problem = problem; 244 component->subscip = NULL; 245 component->workingsol = NULL; 246 component->vars = NULL; 247 component->subvars = NULL; 248 component->fixedvars = NULL; 249 component->fixedsubvars = NULL; 250 component->fixedvarsobjsum = 0.0; 251 component->lastdualbound = -SCIPinfinity(scip); 252 component->lastprimalbound = SCIPinfinity(scip); 253 component->laststatus = SCIP_STATUS_UNKNOWN; 254 component->solved = FALSE; 255 component->ncalls = 0; 256 component->lastsolindex = -1; 257 component->lastbestsolindex = -1; 258 component->nvars = 0; 259 component->nfixedvars = 0; 260 component->fixedvarssize = 0; 261 component->number = problem->ncomponents; 262 263 ++problem->ncomponents; 264 265 return SCIP_OKAY; 266 } 267 268 /** free component structure */ 269 static 270 SCIP_RETCODE freeComponent( 271 COMPONENT* component /**< pointer to component structure */ 272 ) 273 { 274 PROBLEM* problem; 275 SCIP* scip; 276 277 assert(component != NULL); 278 279 problem = component->problem; 280 assert(problem != NULL); 281 282 scip = problem->scip; 283 assert(scip != NULL); 284 285 SCIPdebugMsg(scip, "freeing component %d of problem <%s>\n", component->number, component->problem->name); 286 287 assert((component->vars != NULL) == (component->subvars != NULL)); 288 if( component->vars != NULL ) 289 { 290 SCIPfreeBlockMemoryArray(scip, &component->vars, component->nvars); 291 SCIPfreeBlockMemoryArray(scip, &component->subvars, component->nvars); 292 } 293 294 assert((component->fixedvars != NULL) == (component->fixedsubvars != NULL)); 295 if( component->fixedvars != NULL ) 296 { 297 SCIPfreeBlockMemoryArray(scip, &component->fixedsubvars, component->fixedvarssize); 298 SCIPfreeBlockMemoryArray(scip, &component->fixedvars, component->fixedvarssize); 299 } 300 301 /* free sub-SCIP belonging to this component and the working solution */ 302 if( component->subscip != NULL ) 303 { 304 if( component->workingsol != NULL ) 305 { 306 SCIP_CALL( SCIPfreeSol(component->subscip, &component->workingsol) ); 307 } 308 309 SCIP_CALL( SCIPfree(&component->subscip) ); 310 } 311 312 return SCIP_OKAY; 313 } 314 315 316 /** create the working solution for a given component, store fixed variables and the corresponding objective offset */ 317 static 318 SCIP_RETCODE componentSetupWorkingSol( 319 COMPONENT* component, /**< component structure */ 320 SCIP_HASHMAP* varmap /**< variable hashmap */ 321 ) 322 { 323 SCIP* subscip; 324 325 assert(component != NULL); 326 327 subscip = component->subscip; 328 assert(subscip != NULL); 329 assert(SCIPgetStage(subscip) == SCIP_STAGE_PROBLEM); 330 331 /* the solution should live in the primal, not the origprimal, of the sub-SCIP, so we need to transform it first */ 332 SCIP_CALL( SCIPtransformProb(subscip) ); 333 SCIP_CALL( SCIPcreateOrigSol(subscip, &(component->workingsol), NULL) ); 334 335 /* the number of variables was increased by copying the constraints */ 336 if( SCIPgetNOrigVars(subscip) > component->nvars ) 337 { 338 PROBLEM* problem; 339 SCIP* scip; 340 SCIP_VAR** sourcevars; 341 SCIP_VAR* subvar; 342 int nsourcevars; 343 int nnewvars; 344 int idx = 0; 345 int nvars; 346 int v; 347 348 problem = component->problem; 349 assert(problem != NULL); 350 351 scip = problem->scip; 352 assert(scip != NULL); 353 354 sourcevars = SCIPgetVars(scip); 355 nsourcevars = SCIPgetNVars(scip); 356 nnewvars = SCIPgetNOrigVars(subscip); 357 nvars = component->nvars; 358 359 component->fixedvarssize = nnewvars - nvars; 360 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &component->fixedvars, component->fixedvarssize) ); 361 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &component->fixedsubvars, component->fixedvarssize) ); 362 363 for( v = 0; v < nsourcevars; ++v ) 364 { 365 subvar = (SCIP_VAR*)SCIPhashmapGetImage(varmap, sourcevars[v]); 366 if( subvar != NULL && SCIPvarGetIndex(subvar) >= nvars ) 367 { 368 /* the variable is either locally fixed or could be an inactive variable present in a constraint 369 * for which an aggregation constraint linking it to the active variable was created in the subscip 370 */ 371 assert(SCIPisZero(subscip, SCIPvarGetObj(subvar)) || 372 SCIPisEQ(subscip, SCIPvarGetLbGlobal(subvar), SCIPvarGetUbGlobal(subvar))); 373 374 /* variable is gloablly fixed in sub-SCIP, so it was locally fixed in the main-SCIP */ 375 if( SCIPisEQ(subscip, SCIPvarGetLbGlobal(subvar), SCIPvarGetUbGlobal(subvar)) ) 376 { 377 assert(SCIPisEQ(scip, SCIPvarGetLbLocal(sourcevars[v]), SCIPvarGetUbLocal(sourcevars[v]))); 378 379 component->fixedvarsobjsum += SCIPvarGetLbGlobal(subvar) * SCIPvarGetObj(subvar); 380 component->fixedvars[idx] = sourcevars[v]; 381 component->fixedsubvars[idx] = subvar; 382 ++idx; 383 384 SCIP_CALL( SCIPsetSolVal(subscip, component->workingsol, subvar, SCIPvarGetLbGlobal(subvar)) ); 385 } 386 /* inactive variable */ 387 else 388 { 389 assert(SCIPisZero(subscip, SCIPvarGetObj(subvar))); 390 } 391 } 392 else 393 { 394 assert(subvar == NULL || SCIPisLT(scip, SCIPvarGetLbGlobal(sourcevars[v]), SCIPvarGetUbGlobal(sourcevars[v]))); 395 assert(subvar == NULL || SCIPisLT(subscip, SCIPvarGetLbGlobal(subvar), SCIPvarGetUbGlobal(subvar))); 396 } 397 } 398 component->nfixedvars = idx; 399 assert(component->nfixedvars <= component->fixedvarssize); 400 SCIPdebugMsg(scip, "%d locally fixed variables have been copied, objective contribution: %g\n", 401 component->nfixedvars, component->fixedvarsobjsum); 402 } 403 404 /* set up debug solution */ 405 #ifdef WITH_DEBUG_SOLUTION 406 if( SCIPdebugSolIsEnabled(component->problem->scip) ) 407 { 408 PROBLEM* problem; 409 SCIP* scip; 410 SCIP_Bool isvalid = FALSE; 411 412 problem = component->problem; 413 assert(problem != NULL); 414 415 scip = problem->scip; 416 assert(scip != NULL); 417 418 SCIP_CALL( SCIPdebugSolIsValidInSubtree(scip, &isvalid) ); 419 420 if( isvalid ) 421 { 422 SCIP_Real val; 423 int i; 424 425 SCIPdebugSolEnable(component->subscip); 426 427 for( i = 0; i < component->nvars; ++i ) 428 { 429 if( component->subvars[i] != NULL ) 430 { 431 SCIP_CALL( SCIPdebugGetSolVal(scip, component->vars[i], &val) ); 432 SCIP_CALL( SCIPdebugAddSolVal(component->subscip, component->subvars[i], val) ); 433 } 434 } 435 for( i = 0; i < component->nfixedvars; ++i ) 436 { 437 if( component->fixedsubvars[i] != NULL ) 438 { 439 SCIP_CALL( SCIPdebugGetSolVal(scip, component->fixedvars[i], &val) ); 440 SCIP_CALL( SCIPdebugAddSolVal(component->subscip, component->fixedsubvars[i], val) ); 441 } 442 } 443 } 444 } 445 #endif 446 447 return SCIP_OKAY; 448 } 449 450 /** create a sub-SCIP for the given variables and constraints */ 451 static 452 SCIP_RETCODE createSubscip( 453 SCIP* scip, /**< main SCIP data structure */ 454 SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */ 455 SCIP** subscip /**< pointer to store created sub-SCIP */ 456 ) 457 { 458 SCIP_Bool success; 459 460 assert(conshdlrdata != NULL); 461 462 /* create a new SCIP instance */ 463 SCIP_CALL( SCIPcreate(subscip) ); 464 465 /* copy plugins, we omit pricers (because we do not run if there are active pricers) and dialogs */ 466 #ifdef SCIP_MORE_DEBUG /* we print statistics later, so we need to copy statistics tables */ 467 SCIP_CALL( SCIPcopyPlugins(scip, *subscip, TRUE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, 468 TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, TRUE, TRUE, TRUE, TRUE, &success) ); 469 #else 470 SCIP_CALL( SCIPcopyPlugins(scip, *subscip, TRUE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, 471 TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, TRUE, &success) ); 472 #endif 473 474 /* the plugins were successfully copied */ 475 if( success ) 476 { 477 SCIP_CONSHDLR* newconshdlr; 478 SCIP_CONSHDLRDATA* newconshdlrdata; 479 #ifdef WITH_DEBUG_SOLUTION 480 SCIP_Bool isvalid = FALSE; 481 #endif 482 483 /* copy parameter settings */ 484 SCIP_CALL( SCIPcopyParamSettings(scip, *subscip) ); 485 486 /* some general settings should not be fixed */ 487 assert(!SCIPisParamFixed(*subscip, "limits/solutions")); 488 assert(!SCIPisParamFixed(*subscip, "limits/bestsol")); 489 assert(!SCIPisParamFixed(*subscip, "misc/usevartable")); 490 assert(!SCIPisParamFixed(*subscip, "misc/useconstable")); 491 assert(!SCIPisParamFixed(*subscip, "numerics/feastol")); 492 assert(!SCIPisParamFixed(*subscip, "misc/usesmalltables")); 493 494 /* disable solution limits */ 495 SCIP_CALL( SCIPsetIntParam(*subscip, "limits/solutions", -1) ); 496 SCIP_CALL( SCIPsetIntParam(*subscip, "limits/bestsol", -1) ); 497 498 /* reduce the effort spent for hash tables; however, if the debug solution is enabled and valid in this subtree, 499 * hash tables are needed for installing the debug solution 500 */ 501 #ifdef WITH_DEBUG_SOLUTION 502 SCIP_CALL( SCIPdebugSolIsValidInSubtree(scip, &isvalid) ); 503 if( !isvalid && SCIPgetStage(scip) > SCIP_STAGE_PRESOLVING ) 504 #endif 505 { 506 SCIP_CALL( SCIPsetBoolParam(*subscip, "misc/usevartable", FALSE) ); 507 SCIP_CALL( SCIPsetBoolParam(*subscip, "misc/useconstable", FALSE) ); 508 } 509 510 /* disable presolving */ 511 SCIP_CALL( SCIPsetPresolving(*subscip, SCIP_PARAMSETTING_OFF, TRUE) ); 512 513 /* disable component presolving and fix the parameter */ 514 SCIP_CALL( SCIPsetIntParam(*subscip, "constraints/" CONSHDLR_NAME "/maxprerounds", 0) ); 515 SCIP_CALL( SCIPfixParam(*subscip, "constraints/" CONSHDLR_NAME "/maxprerounds") ); 516 517 /* find the components constraint handler in the sub-SCIP and inform it about the actual depth in the tree */ 518 newconshdlr = SCIPfindConshdlr(*subscip, CONSHDLR_NAME); 519 assert(newconshdlr != NULL); 520 521 newconshdlrdata = SCIPconshdlrGetData(newconshdlr); 522 assert(newconshdlrdata != NULL); 523 newconshdlrdata->subscipdepth = conshdlrdata->subscipdepth + SCIPgetDepth(scip); 524 525 /* disable output, unless in extended debug mode */ 526 #ifndef SCIP_MORE_DEBUG 527 SCIP_CALL( SCIPsetIntParam(*subscip, "display/verblevel", 0) ); 528 #endif 529 } 530 else 531 { 532 SCIP_CALL( SCIPfree(subscip) ); 533 *subscip = NULL; 534 } 535 536 return SCIP_OKAY; 537 } 538 539 /** copies the given variables and constraints to the given sub-SCIP */ 540 static 541 SCIP_RETCODE copyToSubscip( 542 SCIP* scip, /**< source SCIP */ 543 SCIP* subscip, /**< target SCIP */ 544 const char* name, /**< name for copied problem */ 545 SCIP_VAR** vars, /**< array of variables to copy */ 546 SCIP_VAR** subvars, /**< array to fill with copied vars */ 547 SCIP_CONS** conss, /**< constraint to copy */ 548 SCIP_HASHMAP* varmap, /**< hashmap used for the copy process of variables */ 549 SCIP_HASHMAP* consmap, /**< hashmap used for the copy process of constraints */ 550 int nvars, /**< number of variables to copy */ 551 int nconss, /**< number of constraints to copy */ 552 SCIP_Bool* success /**< pointer to store whether copying was successful */ 553 ) 554 { 555 SCIP_CONS* newcons; 556 int i; 557 558 assert(scip != NULL); 559 assert(subscip != NULL); 560 assert(vars != NULL); 561 assert(subvars != NULL); 562 assert(conss != NULL); 563 assert(varmap != NULL); 564 assert(consmap != NULL); 565 assert(success != NULL); 566 567 *success = TRUE; 568 569 /* create problem in sub-SCIP */ 570 SCIP_CALL( SCIPcopyProb(scip, subscip, varmap, consmap, FALSE, name) ); 571 572 /* copy variables */ 573 for( i = 0; i < nvars; ++i ) 574 { 575 SCIP_CALL( SCIPgetVarCopy(scip, subscip, vars[i], &subvars[i], varmap, consmap, FALSE, success) ); 576 577 /* abort if variable was not successfully copied */ 578 if( !(*success) ) 579 return SCIP_OKAY; 580 } 581 582 /* copy constraints */ 583 for( i = 0; i < nconss; ++i ) 584 { 585 assert(!SCIPconsIsModifiable(conss[i])); 586 587 /* copy the constraint */ 588 SCIP_CALL( SCIPgetConsCopy(scip, subscip, conss[i], &newcons, SCIPconsGetHdlr(conss[i]), varmap, consmap, NULL, 589 SCIPconsIsInitial(conss[i]), SCIPconsIsSeparated(conss[i]), SCIPconsIsEnforced(conss[i]), 590 SCIPconsIsChecked(conss[i]), SCIPconsIsPropagated(conss[i]), FALSE, FALSE, 591 SCIPconsIsDynamic(conss[i]), SCIPconsIsRemovable(conss[i]), FALSE, FALSE, success) ); 592 593 /* abort if constraint was not successfully copied */ 594 if( !(*success) ) 595 return SCIP_OKAY; 596 597 SCIP_CALL( SCIPaddCons(subscip, newcons) ); 598 SCIP_CALL( SCIPreleaseCons(subscip, &newcons) ); 599 } 600 601 return SCIP_OKAY; 602 } 603 604 /** create the sub-SCIP for a given component */ 605 static 606 SCIP_RETCODE componentCreateSubscip( 607 COMPONENT* component, /**< component structure */ 608 SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */ 609 SCIP_HASHMAP* varmap, /**< variable hashmap used to improve performance */ 610 SCIP_HASHMAP* consmap, /**< constraint hashmap used to improve performance */ 611 SCIP_CONS** conss, /**< constraints contained in this component */ 612 int nconss, /**< number of constraints contained in this component */ 613 SCIP_Bool* success /**< pointer to store whether the copying process was successful */ 614 ) 615 { 616 char name[SCIP_MAXSTRLEN]; 617 PROBLEM* problem; 618 SCIP* scip; 619 int minsize; 620 621 assert(component != NULL); 622 assert(consmap != NULL); 623 assert(conss != NULL); 624 assert(success != NULL); 625 assert(component->nvars > 0); 626 627 problem = component->problem; 628 assert(problem != NULL); 629 630 scip = problem->scip; 631 assert(scip != NULL); 632 633 (*success) = TRUE; 634 635 SCIP_CALL( createSubscip(scip, conshdlrdata, &component->subscip) ); 636 637 if( component->subscip != NULL ) 638 { 639 /* get minimum size of components to solve individually and set the parameter in the sub-SCIP */ 640 minsize = getMinsize(scip, conshdlrdata); 641 642 SCIP_CALL( SCIPsetIntParam(component->subscip, "constraints/" CONSHDLR_NAME "/minsize", minsize) ); 643 644 /* get name of the original problem and add "comp_nr" */ 645 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_comp_%d", problem->name, component->number); 646 647 SCIP_CALL( copyToSubscip(scip, component->subscip, name, component->vars, component->subvars, 648 conss, varmap, consmap, component->nvars, nconss, success) ); 649 650 if( !(*success) ) 651 { 652 SCIP_CALL( SCIPfree(&component->subscip) ); 653 component->subscip = NULL; 654 } 655 } 656 else 657 (*success) = FALSE; 658 659 return SCIP_OKAY; 660 } 661 662 /** solve a given sub-SCIP up to the given limits */ 663 static 664 SCIP_RETCODE solveSubscip( 665 SCIP* scip, /**< main SCIP */ 666 SCIP* subscip, /**< sub-SCIP to solve */ 667 SCIP_Longint nodelimit, /**< node limit */ 668 SCIP_Real gaplimit /**< gap limit */ 669 ) 670 { 671 SCIP_Real timelimit; 672 SCIP_Real memorylimit; 673 SCIP_Bool avoidmemout; 674 675 assert(scip != NULL); 676 assert(subscip != NULL); 677 678 /* set time limit */ 679 SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) ); 680 if( !SCIPisInfinity(scip, timelimit) ) 681 { 682 timelimit -= SCIPgetSolvingTime(scip); 683 timelimit += SCIPgetSolvingTime(subscip); 684 } 685 686 /* substract the memory already used by the main SCIP and the estimated memory usage of external software */ 687 /* @todo count memory of other components */ 688 SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) ); 689 if( !SCIPisInfinity(scip, memorylimit) ) 690 { 691 memorylimit -= SCIPgetMemUsed(scip)/1048576.0; 692 memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0; 693 } 694 695 /* check if mem limit needs to be avoided */ 696 SCIP_CALL( SCIPgetBoolParam(scip, "misc/avoidmemout", &avoidmemout) ); 697 698 /* abort if no time is left or not enough memory (we don't abort in this case if misc_avoidmemout == TRUE) 699 * to create a copy of SCIP, including external memory usage */ 700 if( avoidmemout && memorylimit <= 0.0 ) 701 { 702 SCIPdebugMessage("--> not solved (not enough memory left)\n"); 703 return SCIP_OKAY; 704 } 705 else if( timelimit <= 0.0 ) 706 { 707 SCIPdebugMessage("--> not solved (not enough time left)\n"); 708 return SCIP_OKAY; 709 } 710 711 /* SCIP copy limits will set wrong time limits since it does not take into account time spent already in the 712 * sub-SCIP; nevertheless, we call it to set the memory limit and unset all other limits, if set in the main SCIP 713 */ 714 SCIP_CALL( SCIPcopyLimits(scip, subscip) ); 715 716 /* set time and memory limit for the subproblem */ 717 SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) ); 718 719 /* only set soft time limit if it exists */ 720 if( SCIPgetParam(scip, "limits/softtime") != NULL ) 721 { 722 SCIP_Real softtimelimit; 723 724 /* set soft time limit, if specified in main SCIP and if it exists */ 725 SCIP_CALL( SCIPgetRealParam(scip, "limits/softtime", &softtimelimit) ); 726 if( softtimelimit > -0.5 ) 727 { 728 softtimelimit -= SCIPgetSolvingTime(scip); 729 softtimelimit += SCIPgetSolvingTime(subscip); 730 softtimelimit = MAX(softtimelimit, 0.0); 731 } 732 733 SCIP_CALL( SCIPsetRealParam(subscip, "limits/softtime", softtimelimit) ); 734 } 735 736 /* set gap limit */ 737 SCIP_CALL( SCIPsetRealParam(subscip, "limits/gap", gaplimit) ); 738 739 /* set node limit */ 740 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nodelimit) ); 741 742 /* solve the subproblem */ 743 SCIP_CALL( SCIPsolve(subscip) ); 744 745 #ifdef SCIP_MORE_DEBUG 746 SCIP_CALL( SCIPprintBestSol(subscip, NULL, FALSE) ); 747 SCIP_CALL( SCIPprintStatistics(subscip, NULL) ); 748 #endif 749 750 return SCIP_OKAY; 751 } 752 753 /** solve a connected component during presolving and evaluate the result */ 754 static 755 SCIP_RETCODE solveAndEvalSubscip( 756 SCIP* scip, /**< SCIP main data structure */ 757 SCIP_CONSHDLRDATA* conshdlrdata, /**< the components constraint handler data */ 758 SCIP* subscip, /**< sub-SCIP to be solved */ 759 SCIP_VAR** vars, /**< array of variables copied to this component */ 760 SCIP_VAR** subvars, /**< array of sub-SCIP variables corresponding to the vars array */ 761 SCIP_CONS** conss, /**< array of constraints copied to this component */ 762 int nvars, /**< number of variables copied to this component */ 763 int nconss, /**< number of constraints copied to this component */ 764 int* ndeletedconss, /**< pointer to store the number of deleted constraints */ 765 int* nfixedvars, /**< pointer to store the number of fixed variables */ 766 int* ntightenedbounds, /**< pointer to store the number of bound tightenings */ 767 SCIP_RESULT* result, /**< pointer to store the result of the component solving */ 768 SCIP_Bool* solved /**< pointer to store if the problem was solved to optimality */ 769 ) 770 { 771 int i; 772 773 assert(scip != NULL); 774 assert(conshdlrdata != NULL); 775 assert(subscip != NULL); 776 assert(vars != NULL); 777 assert(conss != NULL); 778 assert(ndeletedconss != NULL); 779 assert(nfixedvars != NULL); 780 assert(ntightenedbounds != NULL); 781 assert(result != NULL); 782 783 *solved = FALSE; 784 785 SCIP_CALL( solveSubscip(scip, subscip, conshdlrdata->nodelimit, 0.0) ); 786 787 if( SCIPgetStatus(subscip) == SCIP_STATUS_OPTIMAL ) 788 { 789 SCIP_SOL* sol; 790 SCIP_VAR* var; 791 SCIP_VAR* subvar; 792 SCIP_Real* fixvals; 793 SCIP_Bool feasible; 794 SCIP_Bool infeasible; 795 SCIP_Bool fixed; 796 797 sol = SCIPgetBestSol(subscip); 798 799 #ifdef SCIP_DEBUG 800 SCIP_CALL( SCIPcheckSolOrig(subscip, sol, &feasible, TRUE, TRUE) ); 801 #else 802 SCIP_CALL( SCIPcheckSolOrig(subscip, sol, &feasible, FALSE, FALSE) ); 803 #endif 804 805 SCIPdebugMessage("--> solved to optimality: time=%.2f, solution is%s feasible\n", SCIPgetSolvingTime(subscip), feasible ? "" : " not"); 806 807 SCIP_CALL( SCIPallocBufferArray(scip, &fixvals, nvars) ); 808 809 if( feasible ) 810 { 811 SCIP_Real glb; 812 SCIP_Real gub; 813 814 /* get values of variables in the optimal solution */ 815 for( i = 0; i < nvars; ++i ) 816 { 817 var = vars[i]; 818 subvar = subvars[i]; 819 820 /* get global bounds */ 821 glb = SCIPvarGetLbGlobal(var); 822 gub = SCIPvarGetUbGlobal(var); 823 824 if( subvar != NULL ) 825 { 826 /* get solution value from optimal solution of the sub-SCIP */ 827 fixvals[i] = SCIPgetSolVal(subscip, sol, subvar); 828 829 assert(SCIPisFeasLE(scip, fixvals[i], SCIPvarGetUbLocal(var))); 830 assert(SCIPisFeasGE(scip, fixvals[i], SCIPvarGetLbLocal(var))); 831 832 /* checking a solution is done with a relative tolerance of feasibility epsilon, if we really want to 833 * change the bounds of the variables by fixing them, the old bounds must not be violated by more than 834 * the absolute epsilon; therefore, we change the fixing values, if needed, and mark that the solution 835 * has to be checked again 836 */ 837 if( SCIPisGT(scip, fixvals[i], gub) ) 838 { 839 SCIPdebugMessage("variable <%s> fixval: %f violates global upperbound: %f\n", 840 SCIPvarGetName(var), fixvals[i], gub); 841 fixvals[i] = gub; 842 feasible = FALSE; 843 } 844 else if( SCIPisLT(scip, fixvals[i], glb) ) 845 { 846 SCIPdebugMessage("variable <%s> fixval: %f violates global lowerbound: %f\n", 847 SCIPvarGetName(var), fixvals[i], glb); 848 fixvals[i] = glb; 849 feasible = FALSE; 850 } 851 assert(SCIPisLE(scip, fixvals[i], SCIPvarGetUbLocal(var))); 852 assert(SCIPisGE(scip, fixvals[i], SCIPvarGetLbLocal(var))); 853 } 854 else 855 { 856 /* the variable was not copied, so it was cancelled out of constraints during copying; 857 * thus, the variable is not constrained and we fix it to its best bound 858 */ 859 if( SCIPisPositive(scip, SCIPvarGetObj(var)) ) 860 fixvals[i] = glb; 861 else if( SCIPisNegative(scip, SCIPvarGetObj(var)) ) 862 fixvals[i] = gub; 863 else 864 { 865 fixvals[i] = 0.0; 866 fixvals[i] = MIN(fixvals[i], gub); 867 fixvals[i] = MAX(fixvals[i], glb); 868 } 869 } 870 } 871 872 /* the solution value of at least one variable is feasible with a relative tolerance of feasibility epsilon, 873 * but infeasible with an absolute tolerance of epsilon; try to set the variables to the bounds and check 874 * solution again in the original space (changing the values might now introduce infeasibilities of constraints) 875 */ 876 if( !feasible ) 877 { 878 SCIP_Real origobj; 879 880 SCIPdebugMessage("solution violates bounds by more than epsilon, check the corrected solution...\n"); 881 882 origobj = SCIPgetSolOrigObj(subscip, SCIPgetBestSol(subscip)); 883 884 SCIP_CALL( SCIPfreeTransform(subscip) ); 885 886 SCIP_CALL( SCIPcreateOrigSol(subscip, &sol, NULL) ); 887 888 /* set solution values of variables */ 889 for( i = 0; i < nvars; ++i ) 890 { 891 if( subvars[i] != NULL ) 892 { 893 SCIP_CALL( SCIPsetSolVal(subscip, sol, subvars[i], fixvals[i]) ); 894 } 895 } 896 897 /* check the solution; integrality and bounds should be fulfilled and do not have to be checked */ 898 SCIP_CALL( SCIPcheckSol(subscip, sol, FALSE, FALSE, FALSE, FALSE, TRUE, &feasible) ); 899 900 #ifndef NDEBUG 901 /* in debug mode, we additionally check integrality and bounds */ 902 if( feasible ) 903 { 904 SCIP_CALL( SCIPcheckSol(subscip, sol, FALSE, FALSE, TRUE, TRUE, FALSE, &feasible) ); 905 assert(feasible); 906 } 907 #endif 908 909 SCIPdebugMessage("--> corrected solution is%s feasible\n", feasible ? "" : " not"); 910 911 if( !SCIPisFeasEQ(subscip, SCIPsolGetOrigObj(sol), origobj) ) 912 { 913 SCIPdebugMessage("--> corrected solution has a different objective value (old=%16.9g, corrected=%16.9g)\n", 914 origobj, SCIPsolGetOrigObj(sol)); 915 916 feasible = FALSE; 917 } 918 919 SCIP_CALL( SCIPfreeSol(subscip, &sol) ); 920 } 921 922 /* if the solution is feasible, fix variables and delete constraints of the component */ 923 if( feasible ) 924 { 925 /* fix variables */ 926 for( i = 0; i < nvars; ++i ) 927 { 928 assert(SCIPisLE(scip, fixvals[i], SCIPvarGetUbLocal(vars[i]))); 929 assert(SCIPisGE(scip, fixvals[i], SCIPvarGetLbLocal(vars[i]))); 930 assert(SCIPisLE(scip, fixvals[i], SCIPvarGetUbGlobal(vars[i]))); 931 assert(SCIPisGE(scip, fixvals[i], SCIPvarGetLbGlobal(vars[i]))); 932 933 SCIP_CALL( SCIPfixVar(scip, vars[i], fixvals[i], &infeasible, &fixed) ); 934 SCIPvarMarkDeleteGlobalStructures(vars[i]); 935 assert(!infeasible); 936 assert(fixed); 937 (*nfixedvars)++; 938 } 939 940 /* delete constraints */ 941 for( i = 0; i < nconss; ++i ) 942 { 943 SCIP_CALL( SCIPdelCons(scip, conss[i]) ); 944 (*ndeletedconss)++; 945 } 946 947 *result = SCIP_SUCCESS; 948 *solved = TRUE; 949 } 950 } 951 952 SCIPfreeBufferArray(scip, &fixvals); 953 } 954 else if( SCIPgetStatus(subscip) == SCIP_STATUS_INFEASIBLE ) 955 { 956 *result = SCIP_CUTOFF; 957 } 958 else if( SCIPgetStatus(subscip) == SCIP_STATUS_UNBOUNDED || SCIPgetStatus(subscip) == SCIP_STATUS_INFORUNBD ) 959 { 960 /* TODO: store unbounded ray in original SCIP data structure */ 961 *result = SCIP_UNBOUNDED; 962 } 963 else 964 { 965 SCIPdebugMessage("--> solving interrupted (status=%d, time=%.2f)\n", 966 SCIPgetStatus(subscip), SCIPgetSolvingTime(subscip)); 967 968 /* transfer global fixings to the original problem; we can only do this, if we did not find a solution in the 969 * subproblem, because otherwise, the primal bound might lead to dual reductions that cannot be transferred to 970 * the original problem without also transferring the possibly suboptimal solution (which is currently not 971 * possible) 972 */ 973 if( SCIPgetNSols(subscip) == 0 ) 974 { 975 SCIP_Bool infeasible; 976 SCIP_Bool tightened; 977 int ntightened; 978 979 ntightened = 0; 980 981 for( i = 0; i < nvars; ++i ) 982 { 983 if( subvars[i] == NULL ) 984 continue; 985 986 SCIP_CALL( SCIPtightenVarLb(scip, vars[i], SCIPvarGetLbGlobal(subvars[i]), FALSE, 987 &infeasible, &tightened) ); 988 assert(!infeasible); 989 if( tightened ) 990 ntightened++; 991 992 SCIP_CALL( SCIPtightenVarUb(scip, vars[i], SCIPvarGetUbGlobal(subvars[i]), FALSE, 993 &infeasible, &tightened) ); 994 assert(!infeasible); 995 if( tightened ) 996 ntightened++; 997 } 998 999 *result = SCIP_SUCCESS; 1000 1001 *ntightenedbounds += ntightened; 1002 1003 SCIPdebugMessage("--> tightened %d bounds of variables due to global bounds in the sub-SCIP\n", ntightened); 1004 } 1005 } 1006 1007 return SCIP_OKAY; 1008 } 1009 1010 /** (continues) solving a connected component */ 1011 static 1012 SCIP_RETCODE solveComponent( 1013 COMPONENT* component, /**< component structure */ 1014 SCIP_Bool lastcomponent, /**< is this the last component to be solved? */ 1015 SCIP_RESULT* result /**< pointer to store the result of the solving process */ 1016 ) 1017 { 1018 PROBLEM* problem; 1019 SCIP* scip; 1020 SCIP* subscip; 1021 SCIP_SOL* bestsol; 1022 SCIP_Longint nodelimit; 1023 SCIP_Longint lastnnodes; 1024 SCIP_Real gaplimit; 1025 SCIP_STATUS status; 1026 1027 assert(component != NULL); 1028 1029 problem = component->problem; 1030 assert(problem != NULL); 1031 1032 scip = problem->scip; 1033 assert(scip != NULL); 1034 1035 subscip = component->subscip; 1036 assert(subscip != NULL); 1037 1038 *result = SCIP_DIDNOTRUN; 1039 1040 SCIPdebugMessage("solve component <%s> (ncalls=%d, absgap=%.9g)\n", 1041 SCIPgetProbName(subscip), component->ncalls, component->lastprimalbound - component->lastdualbound); 1042 1043 bestsol = SCIPgetBestSol(scip); 1044 1045 /* update best solution of component */ 1046 if( bestsol != NULL && SCIPsolGetIndex(bestsol) != component->lastbestsolindex ) 1047 { 1048 SCIP_SOL* compsol = component->workingsol; 1049 SCIP_VAR** vars = component->vars; 1050 SCIP_VAR** subvars = component->subvars; 1051 int nvars = component->nvars; 1052 int v; 1053 1054 component->lastbestsolindex = SCIPsolGetIndex(bestsol); 1055 1056 /* set solution values of component variables */ 1057 for( v = 0; v < nvars; ++v ) 1058 { 1059 if( subvars[v] != NULL ) 1060 { 1061 SCIP_CALL( SCIPsetSolVal(subscip, compsol, subvars[v], SCIPgetSolVal(scip, bestsol, vars[v])) ); 1062 } 1063 } 1064 #ifndef NDEBUG 1065 for( v = 0; v < component->nfixedvars; ++v ) 1066 { 1067 if( component->fixedsubvars[v] != NULL ) 1068 assert(SCIPisEQ(scip, SCIPgetSolVal(subscip, compsol, component->fixedsubvars[v]), 1069 SCIPvarGetLbGlobal(component->fixedsubvars[v]))); 1070 } 1071 #endif 1072 1073 if( SCIPgetStage(subscip) == SCIP_STAGE_PROBLEM 1074 || SCIPisLT(subscip, SCIPgetSolOrigObj(subscip, compsol), SCIPgetPrimalbound(subscip)) ) 1075 { 1076 SCIP_Bool feasible; 1077 1078 SCIPdebugMessage("checking new solution in component <%s> inherited from problem <%s>: primal bound %.9g --> %.9g\n", 1079 SCIPgetProbName(subscip), problem->name, 1080 SCIPgetStage(subscip) == SCIP_STAGE_PROBLEM ? SCIPinfinity(subscip) : SCIPgetPrimalbound(subscip), 1081 SCIPgetSolOrigObj(subscip, compsol)); 1082 1083 SCIP_CALL( SCIPcheckSolOrig(subscip, compsol, &feasible, FALSE, FALSE) ); 1084 if( feasible ) 1085 { 1086 SCIPdebugMessage("... feasible, adding solution.\n"); 1087 1088 SCIP_CALL( SCIPaddSol(subscip, compsol, &feasible) ); 1089 } 1090 1091 /* We cannot take the value of compsol as a cutoff bound if it was not feasible; some of the fixed connecting 1092 * variables are different and might not allow for a better solution in this component, but still for far 1093 * better solutions in other components. Therefore, the only cutoffbound we can apply is the cutoffbound 1094 * of the problem reduced by the dual bounds of the other components 1095 */ 1096 if( problem->nlowerboundinf == 0 || (problem->nlowerboundinf == 1 1097 && SCIPisInfinity(scip, -component->lastdualbound)) ) 1098 { 1099 SCIP_Real newcutoffbound = SCIPgetSolTransObj(scip, bestsol); 1100 1101 assert(problem->nlowerboundinf > 0 || SCIPisGE(scip, newcutoffbound, problem->lowerbound)); 1102 1103 newcutoffbound = newcutoffbound - problem->lowerbound + component->fixedvarsobjsum; 1104 1105 if( problem->nlowerboundinf == 0 ) 1106 newcutoffbound += component->lastdualbound; 1107 1108 if( SCIPisSumLT(subscip, newcutoffbound, SCIPgetCutoffbound(subscip)) ) 1109 { 1110 SCIPdebugMessage("update cutoff bound to %16.9g\n", newcutoffbound); 1111 1112 SCIP_CALL( SCIPupdateCutoffbound(subscip, newcutoffbound) ); 1113 } 1114 } 1115 } 1116 } 1117 1118 assert(component->laststatus != SCIP_STATUS_OPTIMAL); 1119 1120 SCIPdebugMsg(scip, "solve sub-SCIP for component <%s> (ncalls=%d, absgap=%16.9g)\n", 1121 SCIPgetProbName(component->subscip), component->ncalls, component->lastprimalbound - component->lastdualbound); 1122 1123 if( component->ncalls == 0 ) 1124 { 1125 nodelimit = 1LL; 1126 gaplimit = 0.0; 1127 1128 lastnnodes = 0; 1129 } 1130 else 1131 { 1132 SCIP_Longint mainnodelimit; 1133 1134 lastnnodes = SCIPgetNNodes(component->subscip); 1135 1136 SCIP_CALL( SCIPgetLongintParam(scip, "limits/nodes", &mainnodelimit) ); 1137 1138 nodelimit = 2 * lastnnodes; 1139 nodelimit = MAX(nodelimit, 10LL); 1140 1141 if( mainnodelimit != -1 ) 1142 { 1143 assert(mainnodelimit >= lastnnodes); 1144 nodelimit = MIN(nodelimit, mainnodelimit - lastnnodes); 1145 } 1146 1147 /* set a gap limit of half the current gap (at most 10%) */ 1148 if( SCIPgetGap(component->subscip) < 0.2 ) 1149 gaplimit = 0.5 * SCIPgetGap(component->subscip); 1150 else 1151 gaplimit = 0.1; 1152 1153 if( lastcomponent ) 1154 gaplimit = 0.0; 1155 } 1156 1157 SCIP_CALL( solveSubscip(scip, subscip, nodelimit, gaplimit) ); 1158 1159 SCIPaddNNodes(scip, SCIPgetNNodes(subscip) - lastnnodes); 1160 1161 SCIP_CALL( SCIPprintDisplayLine(scip, NULL, SCIP_VERBLEVEL_NORMAL, TRUE) ); 1162 1163 status = SCIPgetStatus(subscip); 1164 1165 component->laststatus = status; 1166 ++component->ncalls; 1167 1168 SCIPdebugMsg(scip, "--> (status=%d, nodes=%lld, time=%.2f): gap: %12.5g%% absgap: %16.9g\n", 1169 status, SCIPgetNNodes(subscip), SCIPgetSolvingTime(subscip), 100.0*SCIPgetGap(subscip), 1170 SCIPgetPrimalbound(subscip) - SCIPgetDualbound(subscip)); 1171 1172 *result = SCIP_SUCCESS; 1173 1174 switch( status ) 1175 { 1176 case SCIP_STATUS_OPTIMAL: 1177 component->solved = TRUE; 1178 break; 1179 case SCIP_STATUS_INFEASIBLE: 1180 component->solved = TRUE; 1181 1182 /* the problem is really infeasible */ 1183 if( SCIPisInfinity(subscip, SCIPgetPrimalbound(subscip)) ) 1184 { 1185 *result = SCIP_CUTOFF; 1186 } 1187 /* the cutoff bound was reached; no solution better than the cutoff bound exists */ 1188 else 1189 { 1190 *result = SCIP_SUCCESS; 1191 component->laststatus = SCIP_STATUS_OPTIMAL; 1192 assert(SCIPisLE(subscip, SCIPgetDualbound(subscip), SCIPgetPrimalbound(subscip))); 1193 } 1194 break; 1195 case SCIP_STATUS_UNBOUNDED: 1196 case SCIP_STATUS_INFORUNBD: 1197 /* TODO: store unbounded ray in original SCIP data structure */ 1198 *result = SCIP_UNBOUNDED; 1199 component->solved = TRUE; 1200 break; 1201 case SCIP_STATUS_USERINTERRUPT: 1202 SCIP_CALL( SCIPinterruptSolve(scip) ); 1203 break; 1204 case SCIP_STATUS_TERMINATE: 1205 case SCIP_STATUS_UNKNOWN: 1206 case SCIP_STATUS_NODELIMIT: 1207 case SCIP_STATUS_TOTALNODELIMIT: 1208 case SCIP_STATUS_STALLNODELIMIT: 1209 case SCIP_STATUS_TIMELIMIT: 1210 case SCIP_STATUS_MEMLIMIT: 1211 case SCIP_STATUS_GAPLIMIT: 1212 case SCIP_STATUS_SOLLIMIT: 1213 case SCIP_STATUS_BESTSOLLIMIT: 1214 case SCIP_STATUS_RESTARTLIMIT: 1215 default: 1216 break; 1217 } 1218 1219 /* evaluate call */ 1220 if( *result == SCIP_SUCCESS ) 1221 { 1222 SCIP_SOL* sol = SCIPgetBestSol(subscip); 1223 SCIP_VAR* var; 1224 SCIP_VAR* subvar; 1225 SCIP_Real newdualbound; 1226 int v; 1227 1228 /* get dual bound as the minimum of SCIP dual bound and sub-problems dual bound */ 1229 newdualbound = SCIPgetDualbound(subscip) - component->fixedvarsobjsum; 1230 1231 /* update dual bound of problem */ 1232 if( !SCIPisEQ(scip, component->lastdualbound, newdualbound) ) 1233 { 1234 assert(!SCIPisInfinity(scip, -newdualbound)); 1235 1236 /* first finite dual bound: decrease inf counter and add dual bound to problem dualbound */ 1237 if( SCIPisInfinity(scip, -component->lastdualbound) ) 1238 { 1239 --problem->nlowerboundinf; 1240 problem->lowerbound += newdualbound; 1241 } 1242 /* increase problem dual bound by dual bound delta */ 1243 else 1244 { 1245 problem->lowerbound += (newdualbound - component->lastdualbound); 1246 } 1247 1248 /* update problem dual bound if all problem components have a finite dual bound */ 1249 if( problem->nlowerboundinf == 0 ) 1250 { 1251 SCIPdebugMessage("component <%s>: dual bound increased from %16.9g to %16.9g, new dual bound of problem <%s>: %16.9g (gap: %16.9g, absgap: %16.9g)\n", 1252 SCIPgetProbName(subscip), component->lastdualbound, newdualbound, problem->name, 1253 SCIPretransformObj(scip, problem->lowerbound), 1254 problem->nfeascomps == problem->ncomponents ? 1255 (SCIPgetSolOrigObj(scip, problem->bestsol) - SCIPretransformObj(scip, problem->lowerbound)) / 1256 MAX( ABS( SCIPretransformObj(scip, problem->lowerbound) ), SCIPgetSolOrigObj(scip, problem->bestsol) ) /*lint !e666*/ 1257 : SCIPinfinity(scip), 1258 problem->nfeascomps == problem->ncomponents ? 1259 SCIPgetSolOrigObj(scip, problem->bestsol) - SCIPretransformObj(scip, problem->lowerbound) : SCIPinfinity(scip)); 1260 SCIP_CALL( SCIPupdateLocalLowerbound(scip, problem->lowerbound) ); 1261 } 1262 1263 /* store dual bound of this call */ 1264 component->lastdualbound = newdualbound; 1265 } 1266 1267 /* update primal solution of problem */ 1268 if( sol != NULL && component->lastsolindex != SCIPsolGetIndex(sol) ) 1269 { 1270 component->lastsolindex = SCIPsolGetIndex(sol); 1271 1272 if( SCIPsolGetHeur(sol) != NULL ) 1273 SCIPsolSetHeur(problem->bestsol, SCIPfindHeur(scip, SCIPheurGetName(SCIPsolGetHeur(sol)))); 1274 else 1275 SCIPsolSetHeur(problem->bestsol, NULL); 1276 1277 /* increase counter for feasible problems if no solution was known before */ 1278 if( SCIPisInfinity(scip, component->lastprimalbound) ) 1279 ++(problem->nfeascomps); 1280 1281 /* update working best solution in problem */ 1282 for( v = 0; v < component->nvars; ++v ) 1283 { 1284 var = component->vars[v]; 1285 subvar = component->subvars[v]; 1286 assert(var != NULL); 1287 assert(SCIPvarIsActive(var)); 1288 1289 if( subvar == NULL ) 1290 continue; 1291 1292 SCIP_CALL( SCIPsetSolVal(scip, problem->bestsol, var, SCIPgetSolVal(subscip, sol, subvar)) ); 1293 } 1294 1295 /* if we have a feasible solution for each component, add the working solution to the main problem */ 1296 if( problem->nfeascomps == problem->ncomponents ) 1297 { 1298 SCIP_Bool feasible; 1299 #ifdef SCIP_MORE_DEBUG 1300 SCIP_CALL( SCIPcheckSol(scip, problem->bestsol, TRUE, FALSE, TRUE, TRUE, TRUE, &feasible) ); 1301 assert(feasible); 1302 #endif 1303 SCIP_CALL( SCIPaddSol(scip, problem->bestsol, &feasible) ); 1304 1305 SCIPdebugMessage("component <%s>: primal bound decreased from %16.9g to %16.9g, new primal bound of problem <%s>: %16.9g (gap: %16.9g, absgap: %16.9g)\n", 1306 SCIPgetProbName(subscip), component->lastprimalbound, SCIPgetPrimalbound(subscip), problem->name, 1307 SCIPgetSolOrigObj(scip, problem->bestsol), 1308 problem->nfeascomps == problem->ncomponents ? 1309 (SCIPgetSolOrigObj(scip, problem->bestsol) - SCIPretransformObj(scip, problem->lowerbound)) / 1310 MAX( ABS( SCIPretransformObj(scip, problem->lowerbound) ),SCIPgetSolOrigObj(scip, problem->bestsol) ) /*lint !e666*/ 1311 : SCIPinfinity(scip), 1312 problem->nfeascomps == problem->ncomponents ? 1313 SCIPgetSolOrigObj(scip, problem->bestsol) - SCIPretransformObj(scip, problem->lowerbound) : SCIPinfinity(scip)); 1314 } 1315 1316 /* store primal bound of this call */ 1317 component->lastprimalbound = SCIPgetPrimalbound(subscip) - component->fixedvarsobjsum; 1318 } 1319 1320 /* if the component was solved to optimality, we increase the respective counter and free the subscip */ 1321 if( component->laststatus == SCIP_STATUS_OPTIMAL || component->laststatus == SCIP_STATUS_INFEASIBLE || 1322 component->laststatus == SCIP_STATUS_UNBOUNDED || component->laststatus == SCIP_STATUS_INFORUNBD ) 1323 { 1324 ++(problem->nsolvedcomps); 1325 component->solved = TRUE; 1326 1327 /* free working solution and component */ 1328 SCIP_CALL( SCIPfreeSol(subscip, &component->workingsol) ); 1329 1330 SCIP_CALL( SCIPfree(&subscip) ); 1331 component->subscip = NULL; 1332 } 1333 } 1334 1335 return SCIP_OKAY; 1336 } 1337 1338 /** initialize subproblem structure */ 1339 static 1340 SCIP_RETCODE initProblem( 1341 SCIP* scip, /**< SCIP data structure */ 1342 PROBLEM** problem, /**< pointer to subproblem structure */ 1343 SCIP_Real fixedvarsobjsum, /**< objective contribution of all locally fixed variables */ 1344 int ncomponents /**< number of independent components */ 1345 ) 1346 { 1347 char name[SCIP_MAXSTRLEN]; 1348 SCIP_VAR** vars; 1349 int nvars; 1350 int v; 1351 1352 assert(scip != NULL); 1353 assert(problem != NULL); 1354 1355 vars = SCIPgetVars(scip); 1356 nvars = SCIPgetNVars(scip); 1357 1358 SCIP_CALL( SCIPallocBlockMemory(scip, problem) ); 1359 assert(*problem != NULL); 1360 1361 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*problem)->components, ncomponents) ); 1362 1363 /* create a priority queue for the components: we need exactly ncomponents slots in the queue so it should never be 1364 * resized 1365 */ 1366 SCIP_CALL( SCIPpqueueCreate(&(*problem)->compqueue, ncomponents, 1.2, componentSort, NULL) ); 1367 1368 (*problem)->scip = scip; 1369 (*problem)->lowerbound = fixedvarsobjsum; 1370 (*problem)->fixedvarsobjsum = fixedvarsobjsum; 1371 (*problem)->ncomponents = 0; 1372 (*problem)->componentssize = ncomponents; 1373 (*problem)->nlowerboundinf = ncomponents; 1374 (*problem)->nfeascomps = 0; 1375 (*problem)->nsolvedcomps = 0; 1376 1377 if( SCIPgetDepth(scip) == 0 ) 1378 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s", SCIPgetProbName(scip)); 1379 else 1380 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_node_%" SCIP_LONGINT_FORMAT, SCIPgetProbName(scip), SCIPnodeGetNumber(SCIPgetCurrentNode(scip))); 1381 1382 SCIP_CALL( SCIPduplicateMemoryArray(scip, &(*problem)->name, name, strlen(name)+1) ); 1383 1384 SCIP_CALL( SCIPcreateSol(scip, &(*problem)->bestsol, NULL) ); 1385 1386 for( v = 0; v < nvars; v++ ) 1387 { 1388 if( SCIPisFeasEQ(scip, SCIPvarGetLbLocal(vars[v]), SCIPvarGetUbLocal(vars[v])) ) 1389 { 1390 SCIP_CALL( SCIPsetSolVal(scip, (*problem)->bestsol, vars[v], 1391 (SCIPvarGetUbLocal(vars[v]) + SCIPvarGetLbLocal(vars[v]))/2) ); 1392 } 1393 } 1394 1395 SCIPdebugMessage("initialized problem <%s>\n", (*problem)->name); 1396 1397 return SCIP_OKAY; 1398 } 1399 1400 /** free subproblem structure */ 1401 static 1402 SCIP_RETCODE freeProblem( 1403 PROBLEM** problem /**< pointer to problem to free */ 1404 ) 1405 { 1406 SCIP* scip; 1407 int c; 1408 1409 assert(problem != NULL); 1410 assert(*problem != NULL); 1411 1412 scip = (*problem)->scip; 1413 assert(scip != NULL); 1414 1415 /* free best solution */ 1416 if( (*problem)->bestsol != NULL ) 1417 { 1418 SCIP_CALL( SCIPfreeSol(scip, &(*problem)->bestsol) ); 1419 } 1420 1421 /* free all components */ 1422 for( c = (*problem)->ncomponents - 1; c >= 0; --c ) 1423 { 1424 SCIP_CALL( freeComponent(&(*problem)->components[c]) ); 1425 } 1426 if( (*problem)->components != NULL ) 1427 { 1428 SCIPfreeBlockMemoryArray(scip, &(*problem)->components, (*problem)->componentssize); 1429 } 1430 1431 /* free priority queue */ 1432 SCIPpqueueFree(&(*problem)->compqueue); 1433 1434 /* free problem name */ 1435 SCIPfreeMemoryArray(scip, &(*problem)->name); 1436 1437 /* free PROBLEM struct and set the pointer to NULL */ 1438 SCIPfreeBlockMemory(scip, problem); 1439 *problem = NULL; 1440 1441 return SCIP_OKAY; 1442 } 1443 1444 /** creates and captures a components constraint */ 1445 static 1446 SCIP_RETCODE createConsComponents( 1447 SCIP* scip, /**< SCIP data structure */ 1448 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 1449 const char* name, /**< name of constraint */ 1450 PROBLEM* problem /**< problem to be stored in the constraint */ 1451 ) 1452 { 1453 SCIP_CONSHDLR* conshdlr; 1454 1455 /* find the samediff constraint handler */ 1456 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME); 1457 if( conshdlr == NULL ) 1458 { 1459 SCIPerrorMessage("components constraint handler not found\n"); 1460 return SCIP_PLUGINNOTFOUND; 1461 } 1462 1463 /* create constraint */ 1464 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, (SCIP_CONSDATA*)problem, 1465 FALSE, FALSE, FALSE, FALSE, TRUE, 1466 TRUE, FALSE, FALSE, FALSE, TRUE) ); 1467 1468 return SCIP_OKAY; 1469 } 1470 1471 1472 /** sort the components by size and sort vars and conss arrays by component numbers */ 1473 static 1474 SCIP_RETCODE sortComponents( 1475 SCIP* scip, /**< SCIP data structure */ 1476 SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */ 1477 SCIP_DIGRAPH* digraph, /**< directed graph */ 1478 SCIP_CONS** conss, /**< constraints */ 1479 SCIP_VAR** vars, /**< variables */ 1480 int* varcomponent, /**< component numbers for the variables */ 1481 int* conscomponent, /**< array to store component numbers for the constraints */ 1482 int nconss, /**< number of constraints */ 1483 int nvars, /**< number of variables */ 1484 int* firstvaridxpercons, /**< array with index of first variable in vars array for each constraint */ 1485 int* ncompsminsize, /**< pointer to store the number of components not exceeding the minimum size */ 1486 int* ncompsmaxsize /**< pointer to store the number of components not exceeding the maximum size */ 1487 ) 1488 { 1489 SCIP_Real* compsize; 1490 int* permu; 1491 int ncomponents; 1492 int nbinvars; 1493 int nintvars; 1494 int ndiscvars; 1495 int ncontvars; 1496 int minsize; 1497 int v; 1498 int c; 1499 1500 assert(scip != NULL); 1501 assert(conshdlrdata != NULL); 1502 assert(digraph != NULL); 1503 assert(conss != NULL); 1504 assert(vars != NULL); 1505 assert(firstvaridxpercons != NULL); 1506 1507 /* compute minimum size of components to solve individually */ 1508 minsize = getMinsize(scip, conshdlrdata); 1509 1510 ncomponents = SCIPdigraphGetNComponents(digraph); 1511 *ncompsminsize = 0; 1512 *ncompsmaxsize = 0; 1513 1514 /* We want to sort the components in increasing complexity (number of discrete variables, 1515 * integer weighted with factor intfactor, continuous used as tie-breaker). 1516 * Therefore, we now get the variables for each component, count the different variable types 1517 * and compute a size as described above. Then, we rename the components 1518 * such that for i < j, component i has no higher complexity than component j. 1519 */ 1520 SCIP_CALL( SCIPallocBufferArray(scip, &compsize, ncomponents) ); 1521 SCIP_CALL( SCIPallocBufferArray(scip, &permu, ncomponents) ); 1522 1523 /* get number of variables in the components */ 1524 for( c = 0; c < ncomponents; ++c ) 1525 { 1526 int* cvars; 1527 int ncvars; 1528 1529 SCIPdigraphGetComponent(digraph, c, &cvars, &ncvars); 1530 permu[c] = c; 1531 nbinvars = 0; 1532 nintvars = 0; 1533 1534 for( v = 0; v < ncvars; ++v ) 1535 { 1536 /* check whether variable is of binary or integer type */ 1537 if( SCIPvarGetType(vars[cvars[v]]) == SCIP_VARTYPE_BINARY ) 1538 nbinvars++; 1539 else if( SCIPvarGetType(vars[cvars[v]]) == SCIP_VARTYPE_INTEGER ) 1540 nintvars++; 1541 } 1542 ncontvars = ncvars - nintvars - nbinvars; 1543 ndiscvars = (int)(nbinvars + conshdlrdata->intfactor * nintvars); 1544 compsize[c] = ((1000.0 * ndiscvars + (950.0 * ncontvars)/nvars)); 1545 1546 /* component fulfills the maxsize requirement */ 1547 if( ndiscvars <= conshdlrdata->maxintvars ) 1548 ++(*ncompsmaxsize); 1549 1550 /* component fulfills the minsize requirement */ 1551 if( ncvars >= minsize ) 1552 ++(*ncompsminsize); 1553 } 1554 1555 /* get permutation of component numbers such that the size of the components is increasing */ 1556 SCIPsortRealInt(compsize, permu, ncomponents); 1557 1558 /* now, we need the reverse direction, i.e., for each component number, we store its new number 1559 * such that the components are sorted; for this, we abuse the conscomponent array 1560 */ 1561 for( c = 0; c < ncomponents; ++c ) 1562 conscomponent[permu[c]] = c; 1563 1564 /* for each variable, replace the old component number by the new one */ 1565 for( c = 0; c < nvars; ++c ) 1566 varcomponent[c] = conscomponent[varcomponent[c]]; 1567 1568 SCIPfreeBufferArray(scip, &permu); 1569 SCIPfreeBufferArray(scip, &compsize); 1570 1571 /* do the mapping from calculated components per variable to corresponding 1572 * constraints and sort the component-arrays for faster finding the 1573 * actual variables and constraints belonging to one component 1574 */ 1575 for( c = 0; c < nconss; c++ ) 1576 conscomponent[c] = (firstvaridxpercons[c] == -1 ? -1 : varcomponent[firstvaridxpercons[c]]); 1577 1578 SCIPsortIntPtr(varcomponent, (void**)vars, nvars); 1579 SCIPsortIntPtr(conscomponent, (void**)conss, nconss); 1580 1581 return SCIP_OKAY; 1582 } 1583 1584 1585 1586 /** create PROBLEM structure for the current node and split it into components */ 1587 static 1588 SCIP_RETCODE createAndSplitProblem( 1589 SCIP* scip, /**< SCIP data structure */ 1590 SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */ 1591 SCIP_Real fixedvarsobjsum, /**< objective contribution of all locally fixed variables */ 1592 SCIP_VAR** sortedvars, /**< array of unfixed variables sorted by components */ 1593 SCIP_CONS** sortedconss, /**< array of (checked) constraints sorted by components */ 1594 int* compstartsvars, /**< start points of components in sortedvars array */ 1595 int* compstartsconss, /**< start points of components in sortedconss array */ 1596 int ncomponents, /**< number of components */ 1597 PROBLEM** problem /**< pointer to store problem structure */ 1598 ) 1599 { 1600 COMPONENT* component; 1601 SCIP_HASHMAP* consmap; 1602 SCIP_HASHMAP* varmap; 1603 SCIP_VAR** compvars; 1604 SCIP_CONS** compconss; 1605 SCIP_Bool success = TRUE; 1606 int nfixedvars = SCIPgetNVars(scip) - compstartsvars[ncomponents]; 1607 int ncompconss; 1608 int comp; 1609 1610 /* init subproblem data structure */ 1611 SCIP_CALL( initProblem(scip, problem, fixedvarsobjsum, ncomponents) ); 1612 assert((*problem)->components != NULL); 1613 1614 /* hashmap mapping from original constraints to constraints in the sub-SCIPs (for performance reasons) */ 1615 SCIP_CALL( SCIPhashmapCreate(&consmap, SCIPblkmem(scip), compstartsconss[ncomponents]) ); 1616 1617 /* loop over all components */ 1618 for( comp = 0; comp < ncomponents; comp++ ) 1619 { 1620 SCIP_CALL( initComponent(*problem) ); 1621 assert((*problem)->ncomponents == comp+1); 1622 1623 component = &(*problem)->components[comp]; 1624 1625 /* get component variables and store them in component structure */ 1626 compvars = &(sortedvars[compstartsvars[comp]]); 1627 component->nvars = compstartsvars[comp + 1 ] - compstartsvars[comp]; 1628 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &component->vars, compvars, component->nvars) ); 1629 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &component->subvars, component->nvars) ); 1630 SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(scip), component->nvars + nfixedvars) ); 1631 1632 /* get component constraints */ 1633 compconss = &(sortedconss[compstartsconss[comp]]); 1634 ncompconss = compstartsconss[comp + 1] - compstartsconss[comp]; 1635 1636 #ifdef DETAILED_OUTPUT 1637 /* print details about the component including its size */ 1638 if( component->nvars > 1 && ncompconss > 1 ) 1639 { 1640 int nbinvars = 0; 1641 int nintvars = 0; 1642 int ncontvars = 0; 1643 int i; 1644 1645 for( i = 0; i < component->nvars; ++i ) 1646 { 1647 if( SCIPvarGetType(compvars[i]) == SCIP_VARTYPE_BINARY ) 1648 ++nbinvars; 1649 else if( SCIPvarGetType(compvars[i]) == SCIP_VARTYPE_INTEGER ) 1650 ++nintvars; 1651 else 1652 ++ncontvars; 1653 } 1654 SCIPdebugMsg(scip, "component %d at node %lld, depth %d (%d): %d vars (%d bin, %d int, %d cont), %d conss\n", 1655 comp, SCIPnodeGetNumber(SCIPgetCurrentNode(scip)), SCIPgetDepth(scip), SCIPgetDepth(scip) + conshdlrdata->subscipdepth, 1656 component->nvars, nbinvars, nintvars, ncontvars, ncompconss); 1657 } 1658 #endif 1659 assert(ncompconss > 0 || component->nvars == 1); 1660 1661 SCIPdebugMsg(scip, "build sub-SCIP for component %d of problem <%s>: %d vars, %d conss\n", 1662 component->number, (*problem)->name, component->nvars, ncompconss); 1663 1664 #ifndef NDEBUG 1665 { 1666 int i; 1667 for( i = 0; i < component->nvars; ++i ) 1668 assert(SCIPvarIsActive(component->vars[i])); 1669 } 1670 #endif 1671 1672 /* build subscip for component */ 1673 SCIP_CALL( componentCreateSubscip(component, conshdlrdata, varmap, consmap, compconss, ncompconss, &success) ); 1674 1675 if( success ) 1676 { 1677 SCIP_CALL( componentSetupWorkingSol(component, varmap) ); 1678 1679 /* add component to the priority queue of the problem structure */ 1680 SCIP_CALL( SCIPpqueueInsert((*problem)->compqueue, component) ); 1681 } 1682 1683 SCIPhashmapFree(&varmap); 1684 1685 if( !success ) 1686 break; 1687 } 1688 1689 SCIPhashmapFree(&consmap); 1690 1691 if( !success ) 1692 { 1693 /* free subproblem data structure since not all component could be copied */ 1694 SCIP_CALL( freeProblem(problem) ); 1695 } 1696 1697 return SCIP_OKAY; 1698 } 1699 1700 /** continue solving a problem */ 1701 static 1702 SCIP_RETCODE solveProblem( 1703 PROBLEM* problem, /**< problem structure */ 1704 SCIP_RESULT* result /**< result pointer for the problem solve */ 1705 ) 1706 { 1707 COMPONENT* component; 1708 SCIP_RESULT subscipresult; 1709 1710 assert(problem != NULL); 1711 1712 *result = SCIP_SUCCESS; 1713 1714 component = (COMPONENT*)SCIPpqueueRemove(problem->compqueue); 1715 1716 /* continue solving the component */ 1717 SCIP_CALL( solveComponent(component, SCIPpqueueNElems(problem->compqueue) == 0, &subscipresult) ); 1718 1719 /* if infeasibility or unboundedness was detected, return this */ 1720 if( subscipresult == SCIP_CUTOFF || subscipresult == SCIP_UNBOUNDED ) 1721 { 1722 *result = subscipresult; 1723 } 1724 /* the component was not solved to optimality, so we need to re-insert it in the components queue */ 1725 else if( !component->solved ) 1726 { 1727 SCIP_CALL( SCIPpqueueInsert(problem->compqueue, component) ); 1728 *result = SCIP_DELAYNODE; 1729 } 1730 /* no unsolved components are left, so this problem has be completely evaluated and the node can be pruned */ 1731 else if( SCIPpqueueNElems(problem->compqueue) == 0 ) 1732 *result = SCIP_CUTOFF; 1733 /* there are some unsolved components left, so we delay this node */ 1734 else 1735 *result = SCIP_DELAYNODE; 1736 1737 return SCIP_OKAY; 1738 } 1739 1740 /* 1741 * Local methods 1742 */ 1743 1744 /** loop over constraints, get active variables and fill directed graph */ 1745 static 1746 SCIP_RETCODE fillDigraph( 1747 SCIP* scip, /**< SCIP data structure */ 1748 SCIP_DIGRAPH* digraph, /**< directed graph */ 1749 SCIP_CONS** conss, /**< constraints */ 1750 int nconss, /**< number of constraints */ 1751 int* unfixedvarpos, /**< mapping from variable problem index to unfixed var index */ 1752 int nunfixedvars, /**< number of unfixed variables */ 1753 int* firstvaridxpercons, /**< array to store for each constraint the index in the local vars array 1754 * of the first variable of the constraint */ 1755 SCIP_Bool* success /**< flag indicating successful directed graph filling */ 1756 ) 1757 { 1758 SCIP_VAR** consvars; 1759 int requiredsize; 1760 int nconsvars; 1761 int nvars; 1762 int idx1; 1763 int idx2; 1764 int c; 1765 int v; 1766 1767 assert(scip != NULL); 1768 assert(digraph != NULL); 1769 assert(conss != NULL); 1770 assert(firstvaridxpercons != NULL); 1771 assert(success != NULL); 1772 1773 *success = TRUE; 1774 1775 nconsvars = 0; 1776 requiredsize = 0; 1777 nvars = SCIPgetNVars(scip); 1778 1779 /* allocate buffer for storing active variables per constraint; size = nvars ensures that it will be big enough */ 1780 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nvars) ); 1781 1782 for( c = 0; c < nconss; ++c ) 1783 { 1784 /* check for reached timelimit */ 1785 if( (c % 1000 == 0) && SCIPisStopped(scip) ) 1786 { 1787 *success = FALSE; 1788 break; 1789 } 1790 1791 /* get number of variables for this constraint */ 1792 SCIP_CALL( SCIPgetConsNVars(scip, conss[c], &nconsvars, success) ); 1793 1794 if( !(*success) ) 1795 break; 1796 1797 /* reallocate consvars array, if needed */ 1798 if( nconsvars > nvars ) 1799 { 1800 nvars = nconsvars; 1801 SCIP_CALL( SCIPreallocBufferArray(scip, &consvars, nvars) ); 1802 } 1803 1804 #ifndef NDEBUG 1805 /* clearing variables array to check for consistency */ 1806 if( nconsvars == nvars ) 1807 { 1808 BMSclearMemoryArray(consvars, nconsvars); 1809 } 1810 else 1811 { 1812 assert(nconsvars < nvars); 1813 BMSclearMemoryArray(consvars, nconsvars + 1); 1814 } 1815 #endif 1816 1817 /* get variables for this constraint */ 1818 SCIP_CALL( SCIPgetConsVars(scip, conss[c], consvars, nvars, success) ); 1819 1820 if( !(*success) ) 1821 { 1822 #ifndef NDEBUG 1823 /* it looks strange if returning the number of variables was successful but not returning the variables */ 1824 SCIPwarningMessage(scip, "constraint <%s> returned number of variables but returning variables failed\n", SCIPconsGetName(conss[c])); 1825 #endif 1826 break; 1827 } 1828 1829 #ifndef NDEBUG 1830 /* check if returned variables are consistent with the number of variables that were returned */ 1831 for( v = nconsvars - 1; v >= 0; --v ) 1832 assert(consvars[v] != NULL); 1833 if( nconsvars < nvars ) 1834 assert(consvars[nconsvars] == NULL); 1835 #endif 1836 1837 /* transform given variables to active variables */ 1838 SCIP_CALL( SCIPgetActiveVars(scip, consvars, &nconsvars, nvars, &requiredsize) ); 1839 assert(requiredsize <= nvars); 1840 1841 firstvaridxpercons[c] = -1; 1842 1843 /* store the index of the first unfixed variable and add edges to the directed graph */ 1844 if( nconsvars > 0 ) 1845 { 1846 v = 0; 1847 idx1 = -1; 1848 1849 /* go through variables until the first unfixed one is reached (which has unfixedvarpos >= 0) */ 1850 while( idx1 == -1 && v < nconsvars ) 1851 { 1852 idx1 = SCIPvarGetProbindex(consvars[v]); 1853 assert(idx1 >= 0); 1854 idx1 = unfixedvarpos[idx1]; 1855 assert(idx1 < nunfixedvars); 1856 ++v; 1857 } 1858 1859 if( idx1 >= 0 ) 1860 { 1861 /* save index of the first variable for later component assignment */ 1862 firstvaridxpercons[c] = idx1; 1863 1864 /* create sparse directed graph; sparse means to add only those edges necessary for component calculation, 1865 * i.e., add edges from the first variable to all others 1866 */ 1867 for(; v < nconsvars; ++v ) 1868 { 1869 idx2 = SCIPvarGetProbindex(consvars[v]); 1870 assert(idx2 >= 0); 1871 idx2 = unfixedvarpos[idx2]; 1872 assert(idx2 < nunfixedvars); 1873 1874 /* variable is fixed */ 1875 if( idx2 < 0 ) 1876 continue; 1877 1878 /* we add only one directed edge, because the other direction is automatically added for component computation */ 1879 SCIP_CALL( SCIPdigraphAddArc(digraph, idx1, idx2, NULL) ); 1880 } 1881 } 1882 } 1883 } 1884 1885 SCIPfreeBufferArray(scip, &consvars); 1886 1887 return SCIP_OKAY; 1888 } 1889 1890 /** search for components in the problem */ 1891 static 1892 SCIP_RETCODE findComponents( 1893 SCIP* scip, /**< SCIP main data structure */ 1894 SCIP_CONSHDLRDATA* conshdlrdata, /**< the components constraint handler data */ 1895 SCIP_Real* fixedvarsobjsum, /**< objective contribution of all locally fixed variables, or NULL if 1896 * fixed variables should not be disregarded */ 1897 SCIP_VAR** sortedvars, /**< array to store variables sorted by components, should have enough size 1898 * for all variables */ 1899 SCIP_CONS** sortedconss, /**< array to store (checked) constraints sorted by components, should have 1900 * enough size for all constraints */ 1901 int* compstartsvars, /**< start points of components in sortedvars array */ 1902 int* compstartsconss, /**< start points of components in sortedconss array */ 1903 int* nsortedvars, /**< pointer to store the number of variables belonging to any component */ 1904 int* nsortedconss, /**< pointer to store the number of (checked) constraints in components */ 1905 int* ncomponents, /**< pointer to store the number of components */ 1906 int* ncompsminsize, /**< pointer to store the number of components not exceeding the minimum size */ 1907 int* ncompsmaxsize /**< pointer to store the number of components not exceeding the maximum size */ 1908 1909 ) 1910 { 1911 SCIP_CONS** tmpconss; 1912 SCIP_VAR** vars; 1913 SCIP_Bool success; 1914 int ntmpconss; 1915 int nvars; 1916 int c; 1917 1918 assert(scip != NULL); 1919 assert(conshdlrdata != NULL); 1920 assert(sortedvars != NULL); 1921 assert(sortedconss != NULL); 1922 assert(compstartsvars != NULL); 1923 assert(compstartsconss != NULL); 1924 assert(nsortedvars != NULL); 1925 assert(nsortedconss != NULL); 1926 assert(ncomponents != NULL); 1927 assert(ncompsminsize != NULL); 1928 assert(ncompsmaxsize != NULL); 1929 1930 vars = SCIPgetVars(scip); 1931 nvars = SCIPgetNVars(scip); 1932 1933 if( fixedvarsobjsum != NULL ) 1934 *fixedvarsobjsum = 0.0; 1935 1936 *ncomponents = 0; 1937 *ncompsminsize = 0; 1938 *ncompsmaxsize = 0; 1939 1940 /* collect checked constraints for component detection */ 1941 ntmpconss = SCIPgetNConss(scip); 1942 tmpconss = SCIPgetConss(scip); 1943 (*nsortedconss) = 0; 1944 for( c = 0; c < ntmpconss; c++ ) 1945 { 1946 sortedconss[(*nsortedconss)] = tmpconss[c]; 1947 (*nsortedconss)++; 1948 } 1949 1950 if( nvars > 1 && *nsortedconss > 1 ) 1951 { 1952 int* unfixedvarpos; 1953 int* firstvaridxpercons; 1954 int* varlocks; 1955 int nunfixedvars = 0; 1956 int v; 1957 1958 /* arrays for storing the first variable in each constraint (for later component assignment), the number of 1959 * variable locks, and the positions in the sortedvars array for all unfixed variables 1960 */ 1961 SCIP_CALL( SCIPallocBufferArray(scip, &firstvaridxpercons, *nsortedconss) ); 1962 SCIP_CALL( SCIPallocBufferArray(scip, &varlocks, nvars) ); 1963 SCIP_CALL( SCIPallocBufferArray(scip, &unfixedvarpos, nvars) ); 1964 1965 /* count number of varlocks for each variable (up + down locks) and multiply it by 2; 1966 * that value is used as an estimate of the number of arcs incident to the variable's node in the digraph 1967 * to be safe, we double this value 1968 */ 1969 for( v = 0; v < nvars; ++v ) 1970 { 1971 /* variable is not fixed or we do not want to disregard fixed variables */ 1972 if( (fixedvarsobjsum == NULL) || SCIPisLT(scip, SCIPvarGetLbLocal(vars[v]), SCIPvarGetUbLocal(vars[v])) ) 1973 { 1974 assert(nunfixedvars <= v); 1975 sortedvars[nunfixedvars] = vars[v]; 1976 varlocks[nunfixedvars] = 4 * (SCIPvarGetNLocksDownType(vars[v], SCIP_LOCKTYPE_MODEL) 1977 + SCIPvarGetNLocksUpType(vars[v], SCIP_LOCKTYPE_MODEL)); 1978 unfixedvarpos[v] = nunfixedvars; 1979 ++nunfixedvars; 1980 } 1981 /* variable is fixed; update the objective sum of all fixed variables */ 1982 else 1983 { 1984 unfixedvarpos[v] = -1; 1985 (*fixedvarsobjsum) += SCIPvarGetObj(vars[v]) * SCIPvarGetLbLocal(vars[v]); 1986 } 1987 } 1988 *nsortedvars = nunfixedvars; 1989 1990 if( nunfixedvars > 0 ) 1991 { 1992 SCIP_DIGRAPH* digraph; 1993 1994 /* create and fill directed graph */ 1995 SCIP_CALL( SCIPcreateDigraph(scip, &digraph, nunfixedvars) ); 1996 SCIP_CALL( SCIPdigraphSetSizes(digraph, varlocks) ); 1997 SCIP_CALL( fillDigraph(scip, digraph, sortedconss, *nsortedconss, unfixedvarpos, nunfixedvars, firstvaridxpercons, &success) ); 1998 1999 if( success ) 2000 { 2001 int* varcomponent; 2002 int* conscomponent; 2003 2004 SCIP_CALL( SCIPallocBufferArray(scip, &varcomponent, nunfixedvars) ); 2005 SCIP_CALL( SCIPallocBufferArray(scip, &conscomponent, MAX(nunfixedvars,*nsortedconss)) ); 2006 2007 /* compute independent components */ 2008 SCIP_CALL( SCIPdigraphComputeUndirectedComponents(digraph, 1, varcomponent, ncomponents) ); 2009 2010 if( *ncomponents > 1 ) 2011 { 2012 int nconss = *nsortedconss; 2013 int i; 2014 2015 nvars = *nsortedvars; 2016 2017 SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, 2018 "cons components found %d undirected components at node %lld, depth %d (%d)\n", 2019 *ncomponents, SCIPnodeGetNumber(SCIPgetCurrentNode(scip)), SCIPgetDepth(scip), SCIPgetDepth(scip) + conshdlrdata->subscipdepth); 2020 2021 /* sort components by size and sort variables and constraints by component number */ 2022 SCIP_CALL( sortComponents(scip, conshdlrdata, digraph, sortedconss, sortedvars, varcomponent, conscomponent, nconss, *nsortedvars, 2023 firstvaridxpercons, ncompsminsize, ncompsmaxsize) ); 2024 2025 /* determine start indices of components in sortedvars and sortedconss array */ 2026 i = 0; 2027 2028 while( i < nconss && conscomponent[i] == -1 ) 2029 ++i; 2030 2031 for( c = 0; c < *ncomponents + 1; ++c ) 2032 { 2033 assert(i == nconss || conscomponent[i] >= c); 2034 2035 compstartsconss[c] = i; 2036 2037 while( i < nconss && conscomponent[i] == c ) 2038 ++i; 2039 } 2040 2041 for( c = 0, i = 0; c < *ncomponents + 1; ++c ) 2042 { 2043 assert(i == nvars || varcomponent[i] >= c); 2044 2045 compstartsvars[c] = i; 2046 2047 while( i < nvars && varcomponent[i] == c ) 2048 ++i; 2049 } 2050 2051 #ifndef NDEBUG 2052 for( c = 0; c < *ncomponents; ++c ) 2053 { 2054 for( i = compstartsconss[c]; i < compstartsconss[c+1]; ++i ) 2055 assert(conscomponent[i] == c); 2056 for( i = compstartsvars[c]; i < compstartsvars[c+1]; ++i ) 2057 assert(varcomponent[i] == c); 2058 } 2059 #endif 2060 } 2061 2062 SCIPfreeBufferArray(scip, &conscomponent); 2063 SCIPfreeBufferArray(scip, &varcomponent); 2064 } 2065 2066 SCIPdigraphFree(&digraph); 2067 } 2068 2069 SCIPfreeBufferArray(scip, &unfixedvarpos); 2070 SCIPfreeBufferArray(scip, &varlocks); 2071 SCIPfreeBufferArray(scip, &firstvaridxpercons); 2072 } 2073 2074 return SCIP_OKAY; 2075 } 2076 2077 2078 /* 2079 * Callback methods of constraint handler 2080 */ 2081 2082 /** copy method for constraint handler plugins (called when SCIP copies plugins) */ 2083 static 2084 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyComponents) 2085 { /*lint --e{715}*/ 2086 assert(scip != NULL); 2087 assert(conshdlr != NULL); 2088 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2089 2090 /* call inclusion method of constraint handler */ 2091 SCIP_CALL( SCIPincludeConshdlrComponents(scip) ); 2092 2093 *valid = TRUE; 2094 2095 return SCIP_OKAY; 2096 } 2097 2098 /** destructor of constraint handler to free user data (called when SCIP is exiting) */ 2099 static 2100 SCIP_DECL_CONSFREE(conshdlrFreeComponents) 2101 { /*lint --e{715}*/ 2102 SCIP_CONSHDLRDATA* conshdlrdata; 2103 2104 /* free constraint handler data */ 2105 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2106 assert(conshdlrdata != NULL); 2107 2108 SCIPfreeBlockMemory(scip, &conshdlrdata); 2109 SCIPconshdlrSetData(conshdlr, NULL); 2110 2111 return SCIP_OKAY; 2112 } 2113 2114 /** domain propagation method of constraint handler */ 2115 static 2116 SCIP_DECL_CONSPROP(consPropComponents) 2117 { /*lint --e{715}*/ 2118 PROBLEM* problem; 2119 SCIP_CONSHDLRDATA* conshdlrdata; 2120 SCIP_Longint nodelimit; 2121 2122 assert(conshdlr != NULL); 2123 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2124 assert(result != NULL); 2125 assert(SCIPconshdlrGetNActiveConss(conshdlr) >= 0); 2126 assert(SCIPconshdlrGetNActiveConss(conshdlr) <= 1); 2127 2128 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2129 assert(conshdlrdata != NULL); 2130 2131 *result = SCIP_DIDNOTRUN; 2132 2133 /* do not try to detect independent components if the depth is too high */ 2134 if( SCIPgetDepth(scip) + conshdlrdata->subscipdepth > conshdlrdata->maxdepth 2135 && SCIPconshdlrGetNActiveConss(conshdlr) == 0 ) 2136 return SCIP_OKAY; 2137 2138 /* don't run in probing or in repropagation */ 2139 if( SCIPinProbing(scip) || SCIPinRepropagation(scip) ) 2140 return SCIP_OKAY; 2141 2142 /* do not run, if not all variables are explicitly known */ 2143 if( SCIPgetNActivePricers(scip) > 0 ) 2144 return SCIP_OKAY; 2145 2146 /* we do not want to run, if there are no variables left */ 2147 if( SCIPgetNVars(scip) == 0 ) 2148 return SCIP_OKAY; 2149 2150 /* check for a reached timelimit */ 2151 if( SCIPisStopped(scip) ) 2152 return SCIP_OKAY; 2153 2154 /* the components constraint handler does kind of dual reductions */ 2155 if( !SCIPallowStrongDualReds(scip) || !SCIPallowWeakDualReds(scip) ) 2156 return SCIP_OKAY; 2157 2158 problem = NULL; 2159 *result = SCIP_DIDNOTFIND; 2160 2161 /* the current node already has a components constraint storing a problem split into individual components */ 2162 if( SCIPconshdlrGetNActiveConss(conshdlr) >= 1 ) 2163 { 2164 assert(SCIPconshdlrGetNActiveConss(conshdlr) == 1); 2165 2166 problem = (PROBLEM*)SCIPconsGetData(SCIPconshdlrGetConss(conshdlr)[0]); 2167 } 2168 /* no components constraint at the current node, search for components */ 2169 else 2170 { 2171 SCIP_Real fixedvarsobjsum; 2172 SCIP_VAR** sortedvars; 2173 SCIP_CONS** sortedconss; 2174 int* compstartsvars; 2175 int* compstartsconss; 2176 int nsortedvars; 2177 int nsortedconss; 2178 int ncomponents; 2179 int ncompsminsize; 2180 int ncompsmaxsize; 2181 2182 assert(SCIPconshdlrGetNActiveConss(conshdlr) == 0); 2183 2184 /* allocate memory for sorted components */ 2185 SCIP_CALL( SCIPallocBufferArray(scip, &sortedvars, SCIPgetNVars(scip)) ); 2186 SCIP_CALL( SCIPallocBufferArray(scip, &sortedconss, SCIPgetNConss(scip)) ); 2187 SCIP_CALL( SCIPallocBufferArray(scip, &compstartsvars, SCIPgetNVars(scip) + 1) ); 2188 SCIP_CALL( SCIPallocBufferArray(scip, &compstartsconss, SCIPgetNVars(scip) + 1) ); 2189 2190 /* search for components */ 2191 SCIP_CALL( findComponents(scip, conshdlrdata, &fixedvarsobjsum, sortedvars, sortedconss, compstartsvars, 2192 compstartsconss, &nsortedvars, &nsortedconss, &ncomponents, &ncompsminsize, &ncompsmaxsize) ); 2193 2194 if( ncompsminsize > 1 ) 2195 { 2196 SCIP_CONS* cons; 2197 2198 SCIPdebugMsg(scip, "found %d components (%d fulfulling the minsize requirement) at node %lld at depth %d (%d)\n", 2199 ncomponents, ncompsminsize, SCIPnodeGetNumber(SCIPgetCurrentNode(scip)), SCIPgetDepth(scip), 2200 SCIPgetDepth(scip) + conshdlrdata->subscipdepth); 2201 2202 /* if there are components with size smaller than the limit, we merge them with the smallest component */ 2203 if( ncomponents > ncompsminsize ) 2204 { 2205 int minsize; 2206 int size; 2207 int c; 2208 int m = 0; 2209 2210 /* compute minimum size of components to solve individually */ 2211 minsize = getMinsize(scip, conshdlrdata); 2212 2213 for( c = 0; c < ncomponents; ++c ) 2214 { 2215 size = compstartsvars[c+1] - compstartsvars[c]; 2216 2217 if( size >= minsize ) 2218 { 2219 ++m; 2220 compstartsvars[m] = compstartsvars[c+1]; 2221 compstartsconss[m] = compstartsconss[c+1]; 2222 } 2223 /* the last component is too small */ 2224 else if( c == ncomponents - 1 ) 2225 { 2226 assert(m == ncompsminsize); 2227 compstartsvars[m] = compstartsvars[c+1]; 2228 compstartsconss[m] = compstartsconss[c+1]; 2229 } 2230 } 2231 assert(m == ncompsminsize); 2232 assert(compstartsvars[m] == nsortedvars); 2233 assert(compstartsconss[m] == nsortedconss); 2234 2235 ncomponents = m; 2236 } 2237 2238 SCIP_CALL( createAndSplitProblem(scip, conshdlrdata, fixedvarsobjsum, sortedvars, sortedconss, compstartsvars, 2239 compstartsconss, ncomponents, &problem) ); 2240 2241 /* if the problem is not NULL, copying worked fine */ 2242 if( problem != NULL ) 2243 { 2244 SCIP_CALL( createConsComponents(scip, &cons, problem->name, problem) ); 2245 SCIP_CALL( SCIPaddConsNode(scip, SCIPgetCurrentNode(scip), cons, NULL) ); 2246 SCIP_CALL( SCIPreleaseCons(scip, &cons) ); 2247 } 2248 } 2249 2250 SCIPfreeBufferArray(scip, &compstartsconss); 2251 SCIPfreeBufferArray(scip, &compstartsvars); 2252 SCIPfreeBufferArray(scip, &sortedconss); 2253 SCIPfreeBufferArray(scip, &sortedvars); 2254 } 2255 2256 /* (continue to) solve the problem 2257 * 2258 * If the problem was not solved to optimality yet, the result code is set to SCIP_DELAYNODE, so that after the 2259 * propagation is finished, the node is put back into the queue of open nodes and solving the components of the 2260 * problem will be continued when the node is focused and propagated the next time. 2261 * However, if we are at the root node, we continue solving the problem until it is solved or some limit is reached 2262 * since there are no other nodes to process and we want to avoid calling other propagation methods or heuristics 2263 * again and again 2264 */ 2265 SCIP_CALL( SCIPgetLongintParam(scip, "limits/nodes", &nodelimit) ); 2266 if( nodelimit == -1 ) 2267 nodelimit = SCIP_LONGINT_MAX; 2268 2269 do 2270 { 2271 if( problem != NULL ) 2272 { 2273 SCIP_CALL( solveProblem(problem, result) ); 2274 } 2275 } while( *result == SCIP_DELAYNODE && SCIPgetDepth(scip) == 0 && !SCIPisStopped(scip) && SCIPgetNNodes(scip) < nodelimit); 2276 2277 return SCIP_OKAY; 2278 } 2279 2280 /** presolving method of constraint handler */ 2281 static 2282 SCIP_DECL_CONSPRESOL(consPresolComponents) 2283 { /*lint --e{715}*/ 2284 SCIP_CONSHDLRDATA* conshdlrdata; 2285 SCIP_VAR** sortedvars; 2286 SCIP_CONS** sortedconss; 2287 int* compstartsvars; 2288 int* compstartsconss; 2289 int nsortedvars; 2290 int nsortedconss; 2291 int ncomponents; 2292 int ncompsminsize; 2293 int ncompsmaxsize; 2294 int nvars; 2295 2296 assert(conshdlr != NULL); 2297 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2298 assert(result != NULL); 2299 assert(SCIPconshdlrGetNActiveConss(conshdlr) >= 0); 2300 assert(SCIPconshdlrGetNActiveConss(conshdlr) <= 1); 2301 2302 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2303 assert(conshdlrdata != NULL); 2304 2305 *result = SCIP_DIDNOTRUN; 2306 2307 if( SCIPgetStage(scip) != SCIP_STAGE_PRESOLVING || SCIPinProbing(scip) ) 2308 return SCIP_OKAY; 2309 2310 /* do not run, if not all variables are explicitly known */ 2311 if( SCIPgetNActivePricers(scip) > 0 ) 2312 return SCIP_OKAY; 2313 2314 nvars = SCIPgetNVars(scip); 2315 2316 /* we do not want to run, if there are no variables left */ 2317 if( nvars == 0 ) 2318 return SCIP_OKAY; 2319 2320 /* only call the components presolving, if presolving would be stopped otherwise */ 2321 if( !SCIPisPresolveFinished(scip) ) 2322 return SCIP_OKAY; 2323 2324 /* the components constraint handler does kind of dual reductions */ 2325 if( !SCIPallowStrongDualReds(scip) || !SCIPallowWeakDualReds(scip) ) 2326 return SCIP_OKAY; 2327 2328 /* check for a reached timelimit */ 2329 if( SCIPisStopped(scip) ) 2330 return SCIP_OKAY; 2331 2332 *result = SCIP_DIDNOTFIND; 2333 2334 assert(SCIPconshdlrGetNActiveConss(conshdlr) == 0); 2335 2336 /* allocate memory for sorted components */ 2337 SCIP_CALL( SCIPallocBufferArray(scip, &sortedvars, SCIPgetNVars(scip)) ); 2338 SCIP_CALL( SCIPallocBufferArray(scip, &sortedconss, SCIPgetNConss(scip)) ); 2339 SCIP_CALL( SCIPallocBufferArray(scip, &compstartsvars, SCIPgetNVars(scip) + 1) ); 2340 SCIP_CALL( SCIPallocBufferArray(scip, &compstartsconss, SCIPgetNVars(scip) + 1) ); 2341 2342 /* search for components */ 2343 SCIP_CALL( findComponents(scip, conshdlrdata, NULL, sortedvars, sortedconss, compstartsvars, 2344 compstartsconss, &nsortedvars, &nsortedconss, &ncomponents, &ncompsminsize, &ncompsmaxsize) ); 2345 2346 if( ncompsmaxsize > 0 ) 2347 { 2348 char name[SCIP_MAXSTRLEN]; 2349 SCIP* subscip; 2350 SCIP_HASHMAP* consmap; 2351 SCIP_HASHMAP* varmap; 2352 SCIP_VAR** compvars; 2353 SCIP_VAR** subvars; 2354 SCIP_CONS** compconss; 2355 SCIP_Bool success; 2356 SCIP_Bool solved; 2357 int nsolved = 0; 2358 int ncompvars; 2359 int ncompconss; 2360 int comp; 2361 2362 SCIPdebugMsg(scip, "found %d components (%d with small size) during presolving; overall problem size: %d vars (%d int, %d bin, %d cont), %d conss\n", 2363 ncomponents, ncompsmaxsize, SCIPgetNVars(scip), SCIPgetNBinVars(scip), SCIPgetNIntVars(scip), SCIPgetNContVars(scip) + SCIPgetNImplVars(scip), SCIPgetNConss(scip)); 2364 2365 /* build subscip */ 2366 SCIP_CALL( createSubscip(scip, conshdlrdata, &subscip) ); 2367 2368 if( subscip == NULL ) 2369 goto TERMINATE; 2370 2371 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/usesmalltables", TRUE) ); 2372 SCIP_CALL( SCIPsetIntParam(subscip, "constraints/" CONSHDLR_NAME "/propfreq", -1) ); 2373 2374 /* hashmap mapping from original constraints to constraints in the sub-SCIPs (for performance reasons) */ 2375 SCIP_CALL( SCIPhashmapCreate(&consmap, SCIPblkmem(scip), nsortedconss) ); 2376 2377 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nsortedvars) ); 2378 2379 /* loop over all components */ 2380 for( comp = 0; comp < ncompsmaxsize && !SCIPisStopped(scip); comp++ ) 2381 { 2382 #ifdef WITH_DEBUG_SOLUTION 2383 if( SCIPgetStage(subscip) > SCIP_STAGE_INIT ) 2384 { 2385 SCIP_CALL( SCIPfree(&subscip) ); 2386 SCIP_CALL( createSubscip(scip, conshdlrdata, &subscip) ); 2387 } 2388 #endif 2389 /* get component variables */ 2390 compvars = &(sortedvars[compstartsvars[comp]]); 2391 ncompvars = compstartsvars[comp + 1 ] - compstartsvars[comp]; 2392 2393 /* get component constraints */ 2394 compconss = &(sortedconss[compstartsconss[comp]]); 2395 ncompconss = compstartsconss[comp + 1] - compstartsconss[comp]; 2396 2397 /* if we have an unlocked variable, let duality fixing do the job! */ 2398 if( ncompconss == 0 ) 2399 { 2400 assert(ncompvars == 1); 2401 continue; 2402 } 2403 2404 SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(scip), ncompvars) ); 2405 #ifdef DETAILED_OUTPUT 2406 { 2407 int nbinvars = 0; 2408 int nintvars = 0; 2409 int ncontvars = 0; 2410 int i; 2411 2412 for( i = 0; i < ncompvars; ++i ) 2413 { 2414 if( SCIPvarGetType(compvars[i]) == SCIP_VARTYPE_BINARY ) 2415 ++nbinvars; 2416 else if( SCIPvarGetType(compvars[i]) == SCIP_VARTYPE_INTEGER ) 2417 ++nintvars; 2418 else 2419 ++ncontvars; 2420 } 2421 SCIPdebugMsg(scip, "solve component %d: %d vars (%d bin, %d int, %d cont), %d conss\n", 2422 comp, ncompvars, nbinvars, nintvars, ncontvars, ncompconss); 2423 } 2424 #endif 2425 #ifndef NDEBUG 2426 { 2427 int i; 2428 for( i = 0; i < ncompvars; ++i ) 2429 assert(SCIPvarIsActive(compvars[i])); 2430 } 2431 #endif 2432 2433 /* get name of the original problem and add "comp_nr" */ 2434 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_comp_%d", SCIPgetProbName(scip), comp); 2435 2436 SCIP_CALL( copyToSubscip(scip, subscip, name, compvars, subvars, 2437 compconss, varmap, consmap, ncompvars, ncompconss, &success) ); 2438 2439 if( !success ) 2440 { 2441 SCIPhashmapFree(&varmap); 2442 continue; 2443 } 2444 2445 /* set up debug solution */ 2446 #ifdef WITH_DEBUG_SOLUTION 2447 if( SCIPdebugSolIsEnabled(scip) ) 2448 { 2449 SCIP_SOL* debugsol; 2450 SCIP_Real val; 2451 int i; 2452 2453 SCIP_CALL( SCIPdebugGetSol(scip, &debugsol) ); 2454 2455 /* set solution values in the debug solution if it is available */ 2456 if( debugsol != NULL ) 2457 { 2458 SCIPdebugSolEnable(subscip); 2459 2460 for( i = 0; i < ncompvars; ++i ) 2461 { 2462 if( subvars[i] != NULL ) 2463 { 2464 SCIP_CALL( SCIPdebugGetSolVal(scip, compvars[i], &val) ); 2465 SCIP_CALL( SCIPdebugAddSolVal(subscip, subvars[i], val) ); 2466 } 2467 } 2468 } 2469 } 2470 #endif 2471 2472 /* solve the subproblem and evaluate the result, i.e. apply fixings of variables and remove constraints */ 2473 SCIP_CALL( solveAndEvalSubscip(scip, conshdlrdata, subscip, compvars, subvars, compconss, 2474 ncompvars, ncompconss, ndelconss, nfixedvars, nchgbds, result, &solved) ); 2475 2476 /* free variable hash map */ 2477 SCIPhashmapFree(&varmap); 2478 2479 if( solved ) 2480 ++nsolved; 2481 2482 /* if the component is unbounded or infeasible, this holds for the complete problem as well */ 2483 if( *result == SCIP_UNBOUNDED || *result == SCIP_CUTOFF ) 2484 break; 2485 /* if there is only one component left, let's solve this in the main SCIP */ 2486 else if( nsolved == ncomponents - 1 ) 2487 break; 2488 } 2489 2490 SCIPfreeBufferArray(scip, &subvars); 2491 SCIPhashmapFree(&consmap); 2492 2493 SCIP_CALL( SCIPfree(&subscip) ); 2494 } 2495 2496 TERMINATE: 2497 SCIPfreeBufferArray(scip, &compstartsconss); 2498 SCIPfreeBufferArray(scip, &compstartsvars); 2499 SCIPfreeBufferArray(scip, &sortedconss); 2500 SCIPfreeBufferArray(scip, &sortedvars); 2501 2502 return SCIP_OKAY; 2503 } 2504 2505 /** frees specific constraint data */ 2506 static 2507 SCIP_DECL_CONSDELETE(consDeleteComponents) 2508 { /*lint --e{715}*/ 2509 assert(conshdlr != NULL); 2510 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2511 assert(consdata != NULL); 2512 assert(*consdata != NULL); 2513 2514 SCIP_CALL( freeProblem((PROBLEM**) consdata) ); 2515 2516 return SCIP_OKAY; 2517 } 2518 2519 /** constraint enforcing method of constraint handler for relaxation solutions */ 2520 static 2521 SCIP_DECL_CONSENFORELAX(consEnforelaxComponents) 2522 { /*lint --e{715}*/ 2523 assert(result != NULL ); 2524 2525 /* no enforcement is performed, but the callback is needed for all constraint handlers with needscons = FALSE */ 2526 *result = SCIP_FEASIBLE; 2527 2528 return SCIP_OKAY; 2529 } 2530 2531 /** variable rounding lock method of constraint handler */ 2532 static 2533 SCIP_DECL_CONSLOCK(consLockComponents) 2534 { /*lint --e{715}*/ 2535 return SCIP_OKAY; 2536 } 2537 2538 #ifndef NDEBUG 2539 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */ 2540 static 2541 SCIP_DECL_CONSINITSOL(consInitsolComponents) 2542 { /*lint --e{715}*/ 2543 assert(nconss == 0); 2544 2545 return SCIP_OKAY; 2546 } 2547 #endif 2548 2549 #define consEnfolpComponents NULL 2550 #define consEnfopsComponents NULL 2551 #define consCheckComponents NULL 2552 2553 /** creates the components constraint handler and includes it in SCIP */ 2554 SCIP_RETCODE SCIPincludeConshdlrComponents( 2555 SCIP* scip /**< SCIP data structure */ 2556 ) 2557 { 2558 SCIP_CONSHDLRDATA* conshdlrdata; 2559 SCIP_CONSHDLR* conshdlr; 2560 2561 /* create components propagator data */ 2562 SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) ); 2563 conshdlrdata->subscipdepth = 0; 2564 2565 /* include constraint handler */ 2566 SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC, CONSHDLR_ENFOPRIORITY, 2567 CONSHDLR_CHECKPRIORITY, CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS, 2568 consEnfolpComponents, consEnfopsComponents, consCheckComponents, consLockComponents, 2569 conshdlrdata) ); 2570 assert(conshdlr != NULL); 2571 2572 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropComponents, 2573 CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP, CONSHDLR_PROP_TIMING)); 2574 SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolComponents, 2575 CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING)); 2576 2577 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, conshdlrFreeComponents) ); 2578 SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxComponents) ); 2579 #ifndef NDEBUG 2580 SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolComponents) ); 2581 #endif 2582 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyComponents, NULL) ); 2583 SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteComponents) ); 2584 2585 SCIP_CALL( SCIPaddIntParam(scip, 2586 "constraints/" CONSHDLR_NAME "/maxdepth", 2587 "maximum depth of a node to run components detection (-1: disable component detection during solving)", 2588 &conshdlrdata->maxdepth, FALSE, DEFAULT_MAXDEPTH, -1, INT_MAX, NULL, NULL) ); 2589 SCIP_CALL( SCIPaddIntParam(scip, 2590 "constraints/" CONSHDLR_NAME "/maxintvars", 2591 "maximum number of integer (or binary) variables to solve a subproblem during presolving (-1: unlimited)", 2592 &conshdlrdata->maxintvars, TRUE, DEFAULT_MAXINTVARS, -1, INT_MAX, NULL, NULL) ); 2593 SCIP_CALL( SCIPaddIntParam(scip, 2594 "constraints/" CONSHDLR_NAME "/minsize", 2595 "minimum absolute size (in terms of variables) to solve a component individually during branch-and-bound", 2596 &conshdlrdata->minsize, TRUE, DEFAULT_MINSIZE, 0, INT_MAX, NULL, NULL) ); 2597 SCIP_CALL( SCIPaddRealParam(scip, 2598 "constraints/" CONSHDLR_NAME "/minrelsize", 2599 "minimum relative size (in terms of variables) to solve a component individually during branch-and-bound", 2600 &conshdlrdata->minrelsize, TRUE, DEFAULT_MINRELSIZE, 0.0, 1.0, NULL, NULL) ); 2601 SCIP_CALL( SCIPaddLongintParam(scip, 2602 "constraints/" CONSHDLR_NAME "/nodelimit", 2603 "maximum number of nodes to be solved in subproblems during presolving", 2604 &conshdlrdata->nodelimit, FALSE, DEFAULT_NODELIMIT, -1LL, SCIP_LONGINT_MAX, NULL, NULL) ); 2605 SCIP_CALL( SCIPaddRealParam(scip, 2606 "constraints/" CONSHDLR_NAME "/intfactor", 2607 "the weight of an integer variable compared to binary variables", 2608 &conshdlrdata->intfactor, FALSE, DEFAULT_INTFACTOR, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 2609 SCIP_CALL( SCIPaddRealParam(scip, 2610 "constraints/" CONSHDLR_NAME "/feastolfactor", 2611 "factor to increase the feasibility tolerance of the main SCIP in all sub-SCIPs, default value 1.0", 2612 &conshdlrdata->feastolfactor, TRUE, DEFAULT_FEASTOLFACTOR, 0.0, 1000000.0, NULL, NULL) ); 2613 2614 return SCIP_OKAY; 2615 } 2616