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 concsolver_scip.c 26 * @ingroup PARALLEL 27 * @brief implementation of concurrent solver interface for SCIP 28 * @author Leona Gottwald 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include "blockmemshell/memory.h" 34 #include "scip/boundstore.h" 35 #include "scip/concsolver.h" 36 #include "scip/concsolver_scip.h" 37 #include "scip/concurrent.h" 38 #include "scip/pub_event.h" 39 #include "scip/pub_heur.h" 40 #include "scip/pub_message.h" 41 #include "scip/pub_misc.h" 42 #include "scip/pub_paramset.h" 43 #include "scip/pub_sol.h" 44 #include "scip/pub_var.h" 45 #include "scip/scip_concurrent.h" 46 #include "scip/scip_copy.h" 47 #include "scip/scip_event.h" 48 #include "scip/scip_general.h" 49 #include "scip/scip_heur.h" 50 #include "scip/scip_mem.h" 51 #include "scip/scip_message.h" 52 #include "scip/scip_numerics.h" 53 #include "scip/scip_param.h" 54 #include "scip/scip_prob.h" 55 #include "scip/scip_sol.h" 56 #include "scip/scip_solve.h" 57 #include "scip/scip_solvingstats.h" 58 #include "scip/scip_timing.h" 59 #include "scip/syncstore.h" 60 #include <string.h> 61 62 /* event handler for synchronization */ 63 #define EVENTHDLR_NAME "sync" 64 #define EVENTHDLR_DESC "event handler for synchronization of concurrent scip sovlers" 65 66 /* 67 * Data structures 68 */ 69 70 /** event handler data */ 71 struct SCIP_EventhdlrData 72 { 73 int filterpos; 74 }; 75 76 /* 77 * Callback methods of event handler 78 */ 79 80 /** destructor of event handler to free user data (called when SCIP is exiting) */ 81 static 82 SCIP_DECL_EVENTFREE(eventFreeSync) 83 { /*lint --e{715}*/ 84 SCIP_EVENTHDLRDATA* eventhdlrdata; 85 86 assert(scip != NULL); 87 assert(eventhdlr != NULL); 88 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0); 89 90 eventhdlrdata = SCIPeventhdlrGetData(eventhdlr); 91 assert(eventhdlrdata != NULL); 92 93 SCIPfreeBlockMemory(scip, &eventhdlrdata); 94 95 SCIPeventhdlrSetData(eventhdlr, NULL); 96 97 return SCIP_OKAY; 98 } 99 100 /** initialization method of event handler (called after problem was transformed) */ 101 static 102 SCIP_DECL_EVENTINIT(eventInitSync) 103 { /*lint --e{715}*/ 104 SCIP_EVENTHDLRDATA* eventhdlrdata; 105 SCIP_SYNCSTORE* syncstore; 106 107 assert(scip != NULL); 108 assert(eventhdlr != NULL); 109 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0); 110 111 eventhdlrdata = SCIPeventhdlrGetData(eventhdlr); 112 assert(eventhdlrdata != NULL); 113 114 syncstore = SCIPgetSyncstore(scip); 115 assert(syncstore != NULL); 116 117 if( eventhdlrdata->filterpos < 0 && SCIPsyncstoreIsInitialized(syncstore) ) 118 { 119 /* notify SCIP that your event handler wants to react on synchronization events */ 120 SCIP_CALL( SCIPcatchEvent(scip, SCIP_EVENTTYPE_SYNC, eventhdlr, NULL, &eventhdlrdata->filterpos) ); 121 } 122 123 return SCIP_OKAY; 124 } 125 126 /** deinitialization method of event handler (called before transformed problem is freed) */ 127 static 128 SCIP_DECL_EVENTEXIT(eventExitSync) 129 { /*lint --e{715}*/ 130 SCIP_EVENTHDLRDATA* eventhdlrdata; 131 132 assert(scip != NULL); 133 assert(eventhdlr != NULL); 134 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0); 135 136 eventhdlrdata = SCIPeventhdlrGetData(eventhdlr); 137 assert(eventhdlrdata != NULL); 138 139 /* notify SCIP that your event handler wants to drop the event type synchronization found */ 140 if( eventhdlrdata->filterpos >= 0 ) 141 { 142 SCIP_CALL( SCIPdropEvent(scip, SCIP_EVENTTYPE_SYNC, eventhdlr, NULL, eventhdlrdata->filterpos) ); 143 eventhdlrdata->filterpos = -1; 144 } 145 146 return SCIP_OKAY; 147 } 148 149 /** execution method of event handler */ 150 static 151 SCIP_DECL_EVENTEXEC(eventExecSync) 152 { /*lint --e{715}*/ 153 assert(eventhdlr != NULL); 154 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0); 155 assert(event != NULL); 156 assert(scip != NULL); 157 158 SCIP_CALL( SCIPsynchronize(scip) ); 159 160 return SCIP_OKAY; 161 } 162 163 164 /** includes event handler for synchronization found */ 165 static 166 SCIP_RETCODE includeEventHdlrSync( 167 SCIP* scip /**< SCIP data structure */ 168 ) 169 { 170 SCIP_EVENTHDLR* eventhdlr; 171 SCIP_EVENTHDLRDATA* eventhdlrdata; 172 173 SCIP_CALL( SCIPallocBlockMemory(scip, &eventhdlrdata) ); 174 eventhdlrdata->filterpos = -1; 175 176 /* create event handler for events on watched variables */ 177 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecSync, eventhdlrdata) ); 178 assert(eventhdlr != NULL); 179 180 SCIP_CALL( SCIPsetEventhdlrFree(scip, eventhdlr, eventFreeSync) ); 181 SCIP_CALL( SCIPsetEventhdlrInit(scip, eventhdlr, eventInitSync) ); 182 SCIP_CALL( SCIPsetEventhdlrExit(scip, eventhdlr, eventExitSync) ); 183 184 return SCIP_OKAY; 185 } 186 187 /** data for a concurrent solver type */ 188 struct SCIP_ConcSolverTypeData 189 { 190 SCIP_Bool loademphasis; /**< should emphasis settings be loaded when creating an instance of this concurrent solver */ 191 SCIP_PARAMEMPHASIS emphasis; /**< parameter emphasis that will be loaded if loademphasis is true */ 192 }; 193 194 /** data for a concurrent solver */ 195 struct SCIP_ConcSolverData 196 { 197 SCIP* solverscip; /**< the concurrent solvers private SCIP datastructure */ 198 SCIP_VAR** vars; /**< array of variables in the order of the main SCIP's variable array */ 199 int nvars; /**< number of variables in the above arrays */ 200 }; 201 202 /** Disable dual reductions that might cut off optimal solutions. Although they keep at least 203 * one optimal solution intact, communicating these bounds may cut off all optimal solutions, 204 * if different optimal solutions were kept in different concurrent solvers. */ 205 static 206 SCIP_RETCODE disableConflictingDualReductions( 207 SCIP* scip /**< SCIP datastructure */ 208 ) 209 { 210 SCIP_Bool commvarbnds; 211 212 SCIP_CALL( SCIPgetBoolParam(scip, "concurrent/commvarbnds", &commvarbnds) ); 213 214 if( !commvarbnds ) 215 return SCIP_OKAY; 216 217 SCIP_CALL( SCIPsetBoolParam(scip, "misc/allowstrongdualreds", FALSE) ); 218 return SCIP_OKAY; 219 } 220 221 /** sets the child selection rule based on the index of the concurrent solver */ 222 static 223 SCIP_RETCODE setChildSelRule( 224 SCIP_CONCSOLVER* concsolver /**< the concurrent solver */ 225 ) 226 { 227 SCIP_CONCSOLVERDATA* data; 228 static char childsel[] = { 'h', 'i', 'p', 'r', 'l', 'd', 'u' }; 229 230 assert(concsolver != NULL); 231 232 data = SCIPconcsolverGetData(concsolver); 233 assert(data != NULL); 234 235 SCIP_CALL( SCIPsetCharParam(data->solverscip, "nodeselection/childsel", childsel[SCIPconcsolverGetIdx(concsolver) % 7]) ); 236 237 return SCIP_OKAY; 238 } 239 240 /** initialize the concurrent SCIP solver, i.e. setup the copy of the problem and the 241 * mapping of the variables */ 242 static 243 SCIP_RETCODE initConcsolver( 244 SCIP* scip, /**< the main SCIP instance */ 245 SCIP_CONCSOLVER* concsolver /**< the concurrent solver to set up */ 246 ) 247 { 248 int i; 249 SCIP_VAR** vars; 250 SCIP_Bool valid; 251 SCIP_HASHMAP* varmapfw; 252 SCIP_CONCSOLVERDATA* data; 253 int* varperm; 254 255 assert(scip != NULL); 256 assert(concsolver != NULL); 257 258 data = SCIPconcsolverGetData(concsolver); 259 assert(data != NULL); 260 261 data->nvars = SCIPgetNVars(scip); 262 vars = SCIPgetVars(scip); 263 264 /* we force the copying of symmetry constraints that may have been detected during a central presolving step; 265 * otherwise, the copy may become invalid */ 266 if( SCIPsetBoolParam(scip, "constraints/orbitope/forceconscopy", TRUE) != SCIP_OKAY 267 || SCIPsetBoolParam(scip, "constraints/orbisack/forceconscopy", TRUE) != SCIP_OKAY 268 || SCIPsetBoolParam(scip, "constraints/symresack/forceconscopy", TRUE) != SCIP_OKAY ) 269 { 270 SCIPdebugMessage("Could not force copying of symmetry constraints\n"); 271 } 272 273 /* create the concurrent solver's SCIP instance and set up the problem */ 274 SCIP_CALL( SCIPcreate(&data->solverscip) ); 275 SCIPsetMessagehdlrQuiet(data->solverscip, SCIPmessagehdlrIsQuiet(SCIPgetMessagehdlr(scip))); 276 SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(data->solverscip), data->nvars) ); 277 SCIP_CALL( SCIPcopy(scip, data->solverscip, varmapfw, NULL, SCIPconcsolverGetName(concsolver), TRUE, FALSE, FALSE, 278 FALSE, &valid) ); 279 assert(valid); 280 281 /* allocate memory for the arrays to store the variable mapping */ 282 SCIP_CALL( SCIPallocBlockMemoryArray(data->solverscip, &data->vars, data->nvars) ); 283 SCIP_CALL( SCIPallocBufferArray(data->solverscip, &varperm, data->nvars) ); 284 285 /* set up the arrays for the variable mapping */ 286 for( i = 0; i < data->nvars; i++ ) 287 { 288 SCIP_VAR* var; 289 var = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]); 290 assert(var != NULL); 291 varperm[SCIPvarGetIndex(var)] = i; 292 data->vars[i] = var; 293 } 294 295 if( SCIPgetNSols(scip) != 0 ) 296 { 297 SCIP_Bool stored; 298 SCIP_Real* solvals; 299 SCIP_SOL* sol = SCIPgetBestSol(scip); 300 SCIP_SOL* solversol; 301 302 SCIP_CALL( SCIPallocBufferArray(data->solverscip, &solvals, data->nvars) ); 303 304 SCIP_CALL( SCIPgetSolVals(scip, sol, data->nvars, vars, solvals) ); 305 SCIP_CALL( SCIPcreateSol(data->solverscip, &solversol, NULL) ); 306 SCIP_CALL( SCIPsetSolVals(data->solverscip, solversol, data->nvars, data->vars, solvals) ); 307 308 SCIPfreeBufferArray(data->solverscip, &solvals); 309 310 SCIP_CALL( SCIPaddSolFree(data->solverscip, &solversol, &stored) ); 311 312 assert(stored); 313 } 314 315 /* create the concurrent data structure for the concurrent solver's SCIP */ 316 /* this assert fails on check/instances/Symmetry/packorb_1-FullIns_3.cip 317 * assert(SCIPgetNOrigVars(data->solverscip) == data->nvars); 318 * also fails on check/instances/Symmetry/partorb_1-FullIns_3.cip 319 * TODO: test if this leads to any problems 320 */ 321 SCIP_CALL( SCIPcreateConcurrent(data->solverscip, concsolver, varperm) ); 322 SCIPfreeBufferArray(data->solverscip, &varperm); 323 324 /* free the hashmap */ 325 SCIPhashmapFree(&varmapfw); 326 327 return SCIP_OKAY; 328 } 329 330 /** creates an instance of a concurrent SCIP solver */ 331 static 332 SCIP_DECL_CONCSOLVERCREATEINST(concsolverScipCreateInstance) 333 { 334 SCIP_CONCSOLVERDATA* data; 335 SCIP_CONCSOLVERTYPEDATA* typedata; 336 char* prefix; 337 char filename[SCIP_MAXSTRLEN]; 338 SCIP_Bool changechildsel; 339 340 assert(scip != NULL); 341 assert(concsolvertype != NULL); 342 assert(concsolver != NULL); 343 344 typedata = SCIPconcsolverTypeGetData(concsolvertype); 345 346 SCIP_ALLOC( BMSallocMemory(&data) ); 347 SCIPconcsolverSetData(concsolver, data); 348 349 SCIP_CALL( initConcsolver(scip, concsolver) ); 350 351 /* check if emphasis setting should be loaded */ 352 if( typedata->loademphasis ) 353 { 354 SCIP_PARAM** params; 355 SCIP_PARAM** fixedparams; 356 int nparams; 357 int nfixedparams; 358 int i; 359 360 params = SCIPgetParams(data->solverscip); 361 nparams = SCIPgetNParams(data->solverscip); 362 SCIP_CALL( SCIPallocBufferArray(data->solverscip, &fixedparams, nparams) ); 363 nfixedparams = 0; 364 365 /* fix certain parameters before loading emphasis to avoid setting them to default values */ 366 for( i = 0; i < nparams; ++i ) 367 { 368 const char* paramname; 369 370 paramname = SCIPparamGetName(params[i]); 371 372 if( strncmp(paramname, "limits/", 7) == 0 || 373 strncmp(paramname, "numerics/", 9) == 0 || 374 strncmp(paramname, "memory/", 7) == 0 || 375 strncmp(paramname, "concurrent/sync/", 16) == 0 || 376 strncmp(paramname, "heuristics/sync/", 16) == 0 || 377 strncmp(paramname, "propagating/sync/", 17) == 0 ) 378 { 379 fixedparams[nfixedparams++] = params[i]; 380 SCIP_CALL( SCIPfixParam(data->solverscip, paramname) ); 381 } 382 } 383 384 SCIP_CALL( SCIPsetEmphasis(data->solverscip, typedata->emphasis, TRUE) ); 385 386 for( i = 0; i < nfixedparams; ++i ) 387 SCIP_CALL( SCIPunfixParam(data->solverscip, SCIPparamGetName(fixedparams[i])) ); 388 389 SCIPfreeBufferArray(data->solverscip, &fixedparams); 390 } 391 392 /* load settings file if it exists */ 393 SCIP_CALL( SCIPgetStringParam(scip, "concurrent/paramsetprefix", &prefix) ); 394 (void) SCIPsnprintf(filename, SCIP_MAXSTRLEN, "%s%s.set", prefix, SCIPconcsolverGetName(concsolver)); 395 396 if( SCIPfileExists(filename) ) 397 { 398 /* load settings file and print info message */ 399 SCIPinfoMessage(scip, NULL, "reading parameter file <%s> for concurrent solver <%s>\n", filename, SCIPconcsolverGetName(concsolver)); 400 SCIP_CALL( SCIPreadParams(data->solverscip, filename) ); 401 } 402 else 403 { 404 /* print message about missing setting files only in verblevel full */ 405 SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "skipping non existent parameter file <%s> for concurrent solver <%s>\n", 406 filename, SCIPconcsolverGetName(concsolver)); 407 } 408 409 /* include eventhandler for synchronization */ 410 SCIP_CALL( includeEventHdlrSync(data->solverscip) ); 411 412 /* disable output for subscip */ 413 SCIP_CALL( SCIPsetIntParam(data->solverscip, "display/verblevel", 0) ); 414 415 /* use wall clock time in subscips */ 416 SCIP_CALL( SCIPsetIntParam(data->solverscip, "timing/clocktype", (int)SCIP_CLOCKTYPE_WALL) ); 417 418 /* don't catch ctrlc since already caught in main SCIP */ 419 SCIP_CALL( SCIPsetBoolParam(data->solverscip, "misc/catchctrlc", FALSE) ); 420 421 /* one solver can do all dual reductions and share them with the other solvers */ 422 if( SCIPconcsolverGetIdx(concsolver) != 0 ) 423 { 424 SCIP_CALL( disableConflictingDualReductions(data->solverscip) ); 425 } 426 427 /* set different child selection rules if corresponding parameter is TRUE */ 428 SCIP_CALL( SCIPgetBoolParam(scip, "concurrent/changechildsel", &changechildsel) ); 429 if( changechildsel ) 430 { 431 SCIP_CALL( setChildSelRule(concsolver) ); 432 } 433 434 return SCIP_OKAY; 435 } 436 437 /** destroys an instance of a concurrent SCIP solver */ 438 static 439 SCIP_DECL_CONCSOLVERDESTROYINST(concsolverScipDestroyInstance) 440 { 441 SCIP_CONCSOLVERDATA* data; 442 443 assert(concsolver != NULL); 444 445 data = SCIPconcsolverGetData(concsolver); 446 assert(data != NULL); 447 assert(data->solverscip != NULL); 448 449 /* free the array with the variable mapping */ 450 SCIPfreeBlockMemoryArray(data->solverscip, &data->vars, data->nvars); 451 452 /* free subscip */ 453 SCIP_CALL( SCIPfree(&data->solverscip) ); 454 BMSfreeMemory(&data); 455 SCIPconcsolverSetData(concsolver, NULL); 456 457 return SCIP_OKAY; 458 } 459 460 /** frees the data of a concurrent solver type */ 461 static 462 SCIP_DECL_CONCSOLVERTYPEFREEDATA(concsolverTypeScipFreeData) 463 { 464 BMSfreeMemory(data); 465 } 466 467 /** initializes the random and permutation seeds with the given one 468 * and enables permutation of constraints and variables 469 */ 470 static 471 SCIP_DECL_CONCSOLVERINITSEEDS(concsolverScipInitSeeds) 472 { 473 SCIP_CONCSOLVERDATA* data; 474 475 assert(concsolver != NULL); 476 477 data = SCIPconcsolverGetData(concsolver); 478 assert(data != NULL); 479 480 SCIPinfoMessage(data->solverscip, NULL, "initializing seeds to %d in concurrent solver '%s'\n", (int) seed, SCIPconcsolverGetName(concsolver)); 481 482 SCIP_CALL( SCIPsetIntParam(data->solverscip, "randomization/randomseedshift", (int) seed) ); 483 SCIP_CALL( SCIPsetIntParam(data->solverscip, "randomization/permutationseed", (int) seed) ); 484 SCIP_CALL( SCIPsetBoolParam(data->solverscip, "randomization/permutevars", TRUE) ); 485 SCIP_CALL( SCIPsetBoolParam(data->solverscip, "randomization/permuteconss", TRUE) ); 486 487 return SCIP_OKAY; 488 } 489 490 /** installs the solving status of this concurrent solver and the solving statistics 491 * into the given SCIP instance 492 */ 493 static 494 SCIP_DECL_CONCSOLVERCOPYSOLVINGDATA(concsolverGetSolvingData) 495 { 496 SCIP_CONCSOLVERDATA* data; 497 SCIP_VAR** vars; 498 int nvars; 499 int nsols; 500 SCIP_SOL** sols; 501 SCIP_Real* solvals; 502 SCIP_HEUR* heur; 503 int i; 504 505 assert(concsolver != NULL); 506 507 data = SCIPconcsolverGetData(concsolver); 508 assert(data != NULL); 509 assert(data->solverscip != NULL); 510 511 assert(scip != NULL); 512 vars = SCIPgetVars(scip); 513 nvars = SCIPgetNVars(scip); 514 515 nsols = SCIPgetNSols(data->solverscip); 516 sols = SCIPgetSols(data->solverscip); 517 518 assert(nvars == data->nvars); 519 520 /* allocate buffer array used for translating the solution to the given SCIP */ 521 SCIP_CALL( SCIPallocBufferArray(scip, &solvals, nvars) ); 522 523 /* add the solutions to the given SCIP */ 524 for( i = 0; i < nsols; ++i ) 525 { 526 SCIP_SOL* sol; 527 SCIP_Bool stored; 528 SCIP_CALL( SCIPgetSolVals(data->solverscip, sols[i], nvars, data->vars, solvals) ); 529 530 heur = SCIPsolGetHeur(sols[i]); 531 532 if( heur != NULL ) 533 heur = SCIPfindHeur(scip, SCIPheurGetName(heur)); 534 535 SCIP_CALL( SCIPcreateSol(scip, &sol, heur) ); 536 SCIP_CALL( SCIPsetSolVals(scip, sol, nvars, vars, solvals) ); 537 538 SCIP_CALL( SCIPcopySolStats(sols[i], sol) ); 539 540 SCIP_CALL( SCIPaddSolFree(scip, &sol, &stored) ); 541 } 542 543 /* free the buffer array */ 544 SCIPfreeBufferArray(scip, &solvals); 545 546 /* copy solving statistics and status from the solver SCIP to the given SCIP */ 547 SCIP_CALL( SCIPcopyConcurrentSolvingStats(data->solverscip, scip) ); 548 549 return SCIP_OKAY; 550 } 551 552 /** start solving the problem until the solving reaches a limit, gets interrupted, or 553 * just finished successfully 554 */ 555 static 556 SCIP_DECL_CONCSOLVEREXEC(concsolverScipExec) 557 { 558 SCIP_CONCSOLVERDATA* data; 559 560 assert(concsolver != NULL); 561 562 data = SCIPconcsolverGetData(concsolver); 563 assert(data != NULL); 564 565 /* print info message that solving has started */ 566 SCIPinfoMessage(data->solverscip, NULL, "starting solve in concurrent solver '%s'\n", SCIPconcsolverGetName(concsolver)); 567 568 /* solve */ 569 SCIP_CALL( SCIPsolve(data->solverscip) ); 570 571 /* print info message with status */ 572 SCIPinfoMessage(data->solverscip, NULL, "concurrent solver '%s' stopped with status ", SCIPconcsolverGetName(concsolver)); 573 SCIP_CALL( SCIPprintStatus(data->solverscip, NULL) ); 574 SCIPinfoMessage(data->solverscip, NULL, "\n"); 575 576 /* set solving statistics */ 577 *solvingtime = SCIPgetSolvingTime(data->solverscip); 578 *nlpiterations = SCIPgetNLPIterations(data->solverscip); 579 *nnodes = SCIPgetNNodes(data->solverscip); 580 581 return SCIP_OKAY; 582 } 583 584 /** stops the concurrent solver as soon as possible */ 585 static 586 SCIP_DECL_CONCSOLVERSTOP(concsolverScipStop) 587 { 588 SCIP_CONCSOLVERDATA* data; 589 assert(concsolver != NULL); 590 591 data = SCIPconcsolverGetData(concsolver); 592 assert(data != NULL); 593 594 SCIP_CALL( SCIPinterruptSolve(data->solverscip) ); 595 596 return SCIP_OKAY; 597 } 598 599 /** writes new solutions and global boundchanges to the given synchronization data */ 600 static 601 SCIP_DECL_CONCSOLVERSYNCWRITE(concsolverScipSyncWrite) 602 { 603 int i; 604 int nsols; 605 SCIP_SOL** sols; 606 SCIP_CONCSOLVERDATA* data; 607 SCIP_BOUNDSTORE* boundstore; 608 int concsolverid; 609 SCIP_STATUS solverstatus; 610 611 data = SCIPconcsolverGetData(concsolver); 612 assert(data != NULL); 613 concsolverid = SCIPconcsolverGetIdx(concsolver); 614 solverstatus = SCIPgetStatus(data->solverscip); 615 616 SCIPsyncdataSetStatus(syncdata, solverstatus, concsolverid); 617 SCIPsyncdataSetLowerbound(syncdata, SCIPgetDualbound(data->solverscip)); 618 SCIPsyncdataSetUpperbound(syncdata, SCIPgetPrimalbound(data->solverscip)); 619 620 *nsolsshared = 0; 621 622 if( SCIPsyncdataGetStatus(syncdata) != SCIP_STATUS_UNKNOWN ) 623 return SCIP_OKAY; 624 625 SCIPdebugMessage("syncing in concurrent solver %s\n", SCIPconcsolverGetName(concsolver)); 626 627 /* consider at most maxcandsols many solutions, and since the solution array is sorted, we will cosider the best 628 * solutions 629 */ 630 nsols = SCIPgetNSols(data->solverscip); 631 nsols = MIN(nsols, maxcandsols); 632 sols = SCIPgetSols(data->solverscip); 633 634 for( i = 0; i < nsols; ++i ) 635 { 636 if( SCIPIsConcurrentSolNew(data->solverscip, sols[i]) ) 637 { 638 SCIP_Real solobj; 639 SCIP_Real* solvals; 640 641 solobj = SCIPgetSolOrigObj(data->solverscip, sols[i]); 642 643 SCIPdebugMessage("adding sol in concurrent solver %s\n", SCIPconcsolverGetName(concsolver)); 644 SCIPsyncdataGetSolutionBuffer(syncstore, syncdata, solobj, concsolverid, &solvals); 645 646 /* if syncstore has no place for this solution we can stop since the next solution will have 647 * a worse objective value and thus won't be accepted either 648 */ 649 if( solvals == NULL ) 650 break; 651 652 ++(*nsolsshared); 653 SCIP_CALL( SCIPgetSolVals(data->solverscip, sols[i], data->nvars, data->vars, solvals) ); 654 655 /* if we have added the maximum number of solutions we can also stop */ 656 if( *nsolsshared == maxsharedsols ) 657 break; 658 } 659 } 660 661 boundstore = SCIPgetConcurrentGlobalBoundChanges(data->solverscip); 662 663 if( boundstore != NULL ) 664 SCIP_CALL( SCIPsyncdataAddBoundChanges(syncstore, syncdata, boundstore) ); 665 666 SCIPsyncdataAddMemTotal(syncdata, SCIPgetMemTotal(data->solverscip)); 667 668 return SCIP_OKAY; 669 } 670 671 /** reads the solutions and bounds from the given synchronization data */ 672 static 673 SCIP_DECL_CONCSOLVERSYNCREAD(concsolverScipSyncRead) 674 { /*lint --e{715}*/ 675 int i; 676 int nsols; 677 SCIP_Real** solvals; 678 SCIP_CONCSOLVERDATA* data; 679 SCIP_BOUNDSTORE* boundstore; 680 int* concsolverids; 681 int concsolverid; 682 int nbndchgs; 683 684 data = SCIPconcsolverGetData(concsolver); 685 assert(data != NULL); 686 687 concsolverid = SCIPconcsolverGetIdx(concsolver); 688 689 /* get solutions from synchronization data */ 690 SCIPsyncdataGetSolutions(syncdata, &solvals, &concsolverids, &nsols); 691 *nsolsrecvd = 0; 692 693 for( i = 0; i < nsols; ++i ) 694 { 695 SCIP_SOL* newsol; 696 697 /* do not add own solutions */ 698 if( concsolverids[i] == concsolverid ) 699 continue; 700 701 /* solution is from other solver so translate to this solvers variable space and add it to SCIP */ 702 ++(*nsolsrecvd); 703 SCIP_CALL( SCIPcreateOrigSol(data->solverscip, &newsol, NULL) ); 704 705 SCIP_CALL( SCIPsetSolVals(data->solverscip, newsol, data->nvars, data->vars, solvals[i]) ); 706 SCIPdebugMessage("adding solution in concurrent solver %s\n", SCIPconcsolverGetName(concsolver)); 707 SCIP_CALL( SCIPaddConcurrentSol(data->solverscip, newsol) ); 708 } 709 710 /* get bound changes from the synchronization data and add it to this concurrent solvers SCIP */ 711 *ntighterbnds = 0; 712 *ntighterintbnds = 0; 713 boundstore = SCIPsyncdataGetBoundChgs(syncdata); 714 nbndchgs = SCIPboundstoreGetNChgs(boundstore); 715 716 for( i = 0; i < nbndchgs; ++i ) 717 { 718 SCIP_VAR* var; 719 SCIP_BOUNDTYPE boundtype; 720 SCIP_Real newbound; 721 722 var = data->vars[SCIPboundstoreGetChgVaridx(boundstore, i)]; 723 boundtype = SCIPboundstoreGetChgType(boundstore, i); 724 newbound = SCIPboundstoreGetChgVal(boundstore, i); 725 726 SCIP_CALL( SCIPvarGetProbvarBound(&var, &newbound, &boundtype) ); 727 728 /* cannot change bounds of multi-aggregated variables so dont pass this bound-change to the propagator */ 729 if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR ) 730 return SCIP_OKAY; 731 732 /* if bound is not better than also don't pass this bound to the propagator and 733 * don't waste memory for storing this boundchange 734 */ 735 if( boundtype == SCIP_BOUNDTYPE_LOWER && SCIPisGE(data->solverscip, SCIPvarGetLbGlobal(var), newbound) ) 736 return SCIP_OKAY; 737 738 if( boundtype == SCIP_BOUNDTYPE_UPPER && SCIPisLE(data->solverscip, SCIPvarGetUbGlobal(var), newbound) ) 739 return SCIP_OKAY; 740 741 /* bound is better so incremented counters for statistics and pass it to the sync propagator */ 742 ++(*ntighterbnds); 743 744 if( SCIPvarGetType(var) <= SCIP_VARTYPE_INTEGER ) 745 ++(*ntighterintbnds); 746 747 SCIP_CALL( SCIPaddConcurrentBndchg(data->solverscip, var, newbound, boundtype) ); 748 } 749 750 return SCIP_OKAY; 751 } 752 753 754 /** creates the concurrent SCIP solver plugins and includes them in SCIP */ 755 SCIP_RETCODE SCIPincludeConcurrentScipSolvers( 756 SCIP* scip /**< SCIP datastructure */ 757 ) 758 { 759 SCIP_CONCSOLVERTYPEDATA* data; 760 761 assert(scip != NULL); 762 763 /* Include concurrent solvers for SCIP for all emphasis settings and without an emphasis setting. 764 * For the SCIP without an emphasis setting we set the default preferred priority to 1 and for the other types to 0 765 * so that the default concurent solve will use multiple SCIP's using settings as specified by the user in the main SCIP. 766 */ 767 SCIP_CALL( SCIPallocMemory(scip, &data) ); 768 data->loademphasis = FALSE; 769 SCIP_CALL( SCIPincludeConcsolverType(scip, "scip", 1.0, concsolverScipCreateInstance, concsolverScipDestroyInstance, concsolverScipInitSeeds, 770 concsolverScipExec, concsolverGetSolvingData, concsolverScipStop, concsolverScipSyncWrite, 771 concsolverScipSyncRead, concsolverTypeScipFreeData, data) ); 772 773 SCIP_CALL( SCIPallocMemory(scip, &data) ); 774 data->loademphasis = TRUE; 775 data->emphasis = SCIP_PARAMEMPHASIS_DEFAULT; 776 SCIP_CALL( SCIPincludeConcsolverType(scip, "scip-default", 0.0, concsolverScipCreateInstance, concsolverScipDestroyInstance, concsolverScipInitSeeds, 777 concsolverScipExec, concsolverGetSolvingData, concsolverScipStop, concsolverScipSyncWrite, 778 concsolverScipSyncRead, concsolverTypeScipFreeData, data) ); 779 780 SCIP_CALL( SCIPallocMemory(scip, &data) ); 781 data->loademphasis = TRUE; 782 data->emphasis = SCIP_PARAMEMPHASIS_CPSOLVER; 783 SCIP_CALL( SCIPincludeConcsolverType(scip, "scip-cpsolver", 0.0, concsolverScipCreateInstance, concsolverScipDestroyInstance, concsolverScipInitSeeds, 784 concsolverScipExec, concsolverGetSolvingData, concsolverScipStop, concsolverScipSyncWrite, 785 concsolverScipSyncRead, concsolverTypeScipFreeData, data) ); 786 787 SCIP_CALL( SCIPallocMemory(scip, &data) ); 788 data->loademphasis = TRUE; 789 data->emphasis = SCIP_PARAMEMPHASIS_EASYCIP; 790 SCIP_CALL( SCIPincludeConcsolverType(scip, "scip-easycip", 0.0, concsolverScipCreateInstance, concsolverScipDestroyInstance, concsolverScipInitSeeds, 791 concsolverScipExec, concsolverGetSolvingData, concsolverScipStop, concsolverScipSyncWrite, 792 concsolverScipSyncRead, concsolverTypeScipFreeData, data) ); 793 794 SCIP_CALL( SCIPallocMemory(scip, &data) ); 795 data->loademphasis = TRUE; 796 data->emphasis = SCIP_PARAMEMPHASIS_FEASIBILITY; 797 SCIP_CALL( SCIPincludeConcsolverType(scip, "scip-feas", 0.0, concsolverScipCreateInstance, concsolverScipDestroyInstance, concsolverScipInitSeeds, 798 concsolverScipExec, concsolverGetSolvingData, concsolverScipStop, concsolverScipSyncWrite, 799 concsolverScipSyncRead, concsolverTypeScipFreeData, data) ); 800 801 SCIP_CALL( SCIPallocMemory(scip, &data) ); 802 data->loademphasis = TRUE; 803 data->emphasis = SCIP_PARAMEMPHASIS_HARDLP; 804 SCIP_CALL( SCIPincludeConcsolverType(scip, "scip-hardlp", 0.0, concsolverScipCreateInstance, concsolverScipDestroyInstance, concsolverScipInitSeeds, 805 concsolverScipExec, concsolverGetSolvingData, concsolverScipStop, concsolverScipSyncWrite, 806 concsolverScipSyncRead, concsolverTypeScipFreeData, data) ); 807 808 SCIP_CALL( SCIPallocMemory(scip, &data) ); 809 data->loademphasis = TRUE; 810 data->emphasis = SCIP_PARAMEMPHASIS_OPTIMALITY; 811 SCIP_CALL( SCIPincludeConcsolverType(scip, "scip-opti", 0.0, concsolverScipCreateInstance, concsolverScipDestroyInstance, concsolverScipInitSeeds, 812 concsolverScipExec, concsolverGetSolvingData, concsolverScipStop, concsolverScipSyncWrite, 813 concsolverScipSyncRead, concsolverTypeScipFreeData, data) ); 814 815 SCIP_CALL( SCIPallocMemory(scip, &data) ); 816 data->loademphasis = TRUE; 817 data->emphasis = SCIP_PARAMEMPHASIS_COUNTER; 818 SCIP_CALL( SCIPincludeConcsolverType(scip, "scip-counter", 0.0, concsolverScipCreateInstance, concsolverScipDestroyInstance, concsolverScipInitSeeds, 819 concsolverScipExec, concsolverGetSolvingData, concsolverScipStop, concsolverScipSyncWrite, 820 concsolverScipSyncRead, concsolverTypeScipFreeData, data) ); 821 822 return SCIP_OKAY; 823 } 824