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 sepa_impliedbounds.c 26 * @ingroup DEFPLUGINS_SEPA 27 * @brief implied bounds separator 28 * @author Kati Wolter 29 * @author Tobias Achterberg 30 */ 31 32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 33 34 #include "blockmemshell/memory.h" 35 #include "scip/pub_implics.h" 36 #include "scip/pub_lp.h" 37 #include "scip/pub_message.h" 38 #include "scip/pub_misc.h" 39 #include "scip/pub_sepa.h" 40 #include "scip/pub_var.h" 41 #include "scip/scip_branch.h" 42 #include "scip/scip_cut.h" 43 #include "scip/scip_lp.h" 44 #include "scip/scip_mem.h" 45 #include "scip/scip_message.h" 46 #include "scip/scip_numerics.h" 47 #include "scip/scip_param.h" 48 #include "scip/scip_prob.h" 49 #include "scip/scip_sepa.h" 50 #include "scip/scip_sol.h" 51 #include "scip/scip_solvingstats.h" 52 #include "scip/scip_var.h" 53 #include "scip/sepa_impliedbounds.h" 54 #include <string.h> 55 56 57 #define SEPA_NAME "impliedbounds" 58 #define SEPA_DESC "implied bounds separator" 59 #define SEPA_PRIORITY -50 60 #define SEPA_FREQ 10 61 #define SEPA_MAXBOUNDDIST 1.0 62 #define SEPA_USESSUBSCIP FALSE /**< does the separator use a secondary SCIP instance? */ 63 #define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */ 64 65 #define RELCUTCOEFMAXRANGE 1.0 /**< maximal allowed range of cut coefficients, relative to 1/feastol */ 66 #define DEFAULT_USETWOSIZECLIQUES TRUE /**< should violated inequalities for cliques with 2 variables be separated? */ 67 68 /** separator-specific data for the implied bounds separator */ 69 struct SCIP_SepaData 70 { 71 SCIP_Bool usetwosizecliques; /**< should violated inequalities for cliques with 2 variables be separated? */ 72 }; 73 74 /* 75 * Local methods 76 */ 77 78 /** adds given cut with two variables, if it is violated */ 79 static 80 SCIP_RETCODE addCut( 81 SCIP* scip, /**< SCIP data structure */ 82 SCIP_SEPA* sepa, /**< separator */ 83 SCIP_Real val1, /**< given coefficient of first variable */ 84 SCIP_VAR* var1, /**< given first variable */ 85 SCIP_Real solval1, /**< current LP solution value of first variable */ 86 SCIP_Real val2, /**< given coefficient of second variable */ 87 SCIP_VAR* var2, /**< given second variable */ 88 SCIP_Real solval2, /**< current LP solution value of second variable */ 89 SCIP_Real rhs, /**< given right hand side of the cut to add */ 90 SCIP_Bool* cutoff, /**< whether a cutoff has been detected */ 91 int* ncuts /**< pointer to update number of cuts added */ 92 ) 93 { 94 SCIP_Real activity; 95 96 assert(ncuts != NULL); 97 assert(cutoff != NULL); 98 *cutoff = FALSE; 99 100 /* calculate activity of cut */ 101 activity = val1 * solval1 + val2 * solval2; 102 /*SCIPdebugMsg(scip, " -> %g<%s>[%g] + %g<%s>[%g] <= %g (act: %g)\n", 103 val1, SCIPvarGetName(var1), solval1, val2, SCIPvarGetName(var2), solval2, rhs, activity);*/ 104 105 /* check, if cut is violated */ 106 if( SCIPisEfficacious(scip, activity - rhs) ) 107 { 108 SCIP_ROW* cut; 109 char cutname[SCIP_MAXSTRLEN]; 110 111 /* create cut */ 112 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "implbd%" SCIP_LONGINT_FORMAT "_%d", SCIPgetNLPs(scip), *ncuts); 113 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), rhs, FALSE, FALSE, TRUE) ); 114 SCIP_CALL( SCIPcacheRowExtensions(scip, cut) ); 115 SCIP_CALL( SCIPaddVarToRow(scip, cut, var1, val1) ); 116 SCIP_CALL( SCIPaddVarToRow(scip, cut, var2, val2) ); 117 SCIP_CALL( SCIPflushRowExtensions(scip, cut) ); 118 /* set cut rank: for implied bounds we always set to 1 */ 119 SCIProwChgRank(cut, 1); 120 121 #ifdef SCIP_DEBUG 122 SCIPdebugMsg(scip, " -> found cut (activity = %g): ", activity); 123 SCIP_CALL( SCIPprintRow(scip, cut, NULL) ); 124 #endif 125 126 SCIP_CALL( SCIPaddPoolCut(scip, cut) ); 127 (*ncuts)++; 128 129 /* release cut */ 130 SCIP_CALL( SCIPreleaseRow(scip, &cut) ); 131 } 132 133 return SCIP_OKAY; 134 } 135 136 /** searches and adds implied bound cuts that are violated by the given solution value array */ 137 static 138 SCIP_RETCODE separateCuts( 139 SCIP* scip, /**< SCIP data structure */ 140 SCIP_SEPA* sepa, /**< separator */ 141 SCIP_SOL* sol, /**< the solution that should be separated, or NULL for LP solution */ 142 SCIP_Real* solvals, /**< array with solution values of all problem variables */ 143 SCIP_VAR** fracvars, /**< array of fractional variables */ 144 SCIP_Real* fracvals, /**< solution values of fractional variables */ 145 int nfracs, /**< number of fractional variables */ 146 SCIP_Bool* cutoff, /**< whether a cutoff has been detected */ 147 int* ncuts /**< pointer to store the number of generated cuts */ 148 ) 149 { 150 SCIP_CLIQUE** cliques; 151 SCIP_SEPADATA* sepadata; 152 int ncliques; 153 int i; 154 155 assert(solvals != NULL); 156 assert(fracvars != NULL || nfracs == 0); 157 assert(fracvals != NULL || nfracs == 0); 158 assert(cutoff != NULL); 159 assert(ncuts != NULL); 160 161 *cutoff = FALSE; 162 *ncuts = 0; 163 sepadata = SCIPsepaGetData(sepa); 164 assert(sepadata != NULL); 165 166 SCIPdebugMsg(scip, "searching for implied bound cuts\n"); 167 168 /* search binary variables for violated implications */ 169 for( i = 0; i < nfracs; i++ ) 170 { 171 SCIP_BOUNDTYPE* impltypes; 172 SCIP_Real* implbounds; 173 SCIP_VAR** implvars; 174 int nimpl; 175 int j; 176 177 assert(fracvars != NULL); 178 assert(fracvals != NULL); 179 180 /* only process binary variables */ 181 if( SCIPvarGetType(fracvars[i]) != SCIP_VARTYPE_BINARY ) 182 continue; 183 184 /* get implications of x == 1 */ 185 nimpl = SCIPvarGetNImpls(fracvars[i], TRUE); 186 implvars = SCIPvarGetImplVars(fracvars[i], TRUE); 187 impltypes = SCIPvarGetImplTypes(fracvars[i], TRUE); 188 implbounds = SCIPvarGetImplBounds(fracvars[i], TRUE); 189 190 /*SCIPdebugMsg(scip, "%d implications for <%s>[%g] == 1\n", nimpl, SCIPvarGetName(fracvars[i]), fracvals[i]);*/ 191 192 /* try to add cuts for implications of x == 1 193 * x == 1 -> y <= p: y <= ub + x * (p - ub) <==> y + (ub - p) * x <= ub 194 * x == 1 -> y >= p: y >= lb + x * (p - lb) <==> -y + (p - lb) * x <= -lb 195 * with lb (ub) global lower (upper) bound of y 196 */ 197 for( j = 0; j < nimpl; j++ ) 198 { 199 SCIP_Real solval; 200 201 assert(implvars != NULL); 202 assert(impltypes != NULL); 203 assert(implbounds != NULL); 204 205 /* consider only implications with active implvar */ 206 if( SCIPvarGetProbindex(implvars[j]) < 0 ) 207 continue; 208 209 solval = solvals[SCIPvarGetProbindex(implvars[j])]; 210 if( impltypes[j] == SCIP_BOUNDTYPE_UPPER ) 211 { 212 SCIP_Real ub; 213 214 /* implication x == 1 -> y <= p */ 215 ub = SCIPvarGetUbGlobal(implvars[j]); 216 217 /* consider only nonredundant and numerical harmless implications */ 218 if( SCIPisLE(scip, implbounds[j], ub) && (ub - implbounds[j]) * SCIPfeastol(scip) <= RELCUTCOEFMAXRANGE ) 219 { 220 /* add cut if violated */ 221 SCIP_CALL( addCut(scip, sepa, 1.0, implvars[j], solval, (ub - implbounds[j]), fracvars[i], fracvals[i], 222 ub, cutoff, ncuts) ); 223 if ( *cutoff ) 224 return SCIP_OKAY; 225 } 226 } 227 else 228 { 229 SCIP_Real lb; 230 231 /* implication x == 1 -> y >= p */ 232 lb = SCIPvarGetLbGlobal(implvars[j]); 233 assert(impltypes[j] == SCIP_BOUNDTYPE_LOWER); 234 235 /* consider only nonredundant and numerical harmless implications */ 236 if( SCIPisGE(scip, implbounds[j], lb) && (implbounds[j] - lb) * SCIPfeastol(scip) <= RELCUTCOEFMAXRANGE ) 237 { 238 /* add cut if violated */ 239 SCIP_CALL( addCut(scip, sepa, -1.0, implvars[j], solval, (implbounds[j] - lb), fracvars[i], fracvals[i], 240 -lb, cutoff, ncuts) ); 241 if ( *cutoff ) 242 return SCIP_OKAY; 243 } 244 } 245 } 246 247 /* get implications of x == 0 */ 248 nimpl = SCIPvarGetNImpls(fracvars[i], FALSE); 249 implvars = SCIPvarGetImplVars(fracvars[i], FALSE); 250 impltypes = SCIPvarGetImplTypes(fracvars[i], FALSE); 251 implbounds = SCIPvarGetImplBounds(fracvars[i], FALSE); 252 253 /*SCIPdebugMsg(scip, "%d implications for <%s>[%g] == 0\n", nimpl, SCIPvarGetName(fracvars[i]), fracvals[i]);*/ 254 255 /* try to add cuts for implications of x == 0 256 * x == 0 -> y <= p: y <= p + x * (ub - p) <==> y + (p - ub) * x <= p 257 * x == 0 -> y >= p: y >= p + x * (lb - p) <==> -y + (lb - p) * x <= -p 258 * with lb (ub) global lower (upper) bound of y 259 */ 260 for( j = 0; j < nimpl; j++ ) 261 { 262 SCIP_Real solval; 263 264 /* consider only implications with active implvar */ 265 if( SCIPvarGetProbindex(implvars[j]) < 0 ) 266 continue; 267 268 solval = solvals[SCIPvarGetProbindex(implvars[j])]; 269 if( impltypes[j] == SCIP_BOUNDTYPE_UPPER ) 270 { 271 SCIP_Real ub; 272 273 /* implication x == 0 -> y <= p */ 274 ub = SCIPvarGetUbGlobal(implvars[j]); 275 276 /* consider only nonredundant and numerical harmless implications */ 277 if( SCIPisLE(scip, implbounds[j], ub) && (ub - implbounds[j]) * SCIPfeastol(scip) < RELCUTCOEFMAXRANGE ) 278 { 279 /* add cut if violated */ 280 SCIP_CALL( addCut(scip, sepa, 1.0, implvars[j], solval, (implbounds[j] - ub), fracvars[i], fracvals[i], 281 implbounds[j], cutoff, ncuts) ); 282 if ( *cutoff ) 283 return SCIP_OKAY; 284 } 285 } 286 else 287 { 288 SCIP_Real lb; 289 290 /* implication x == 0 -> y >= p */ 291 lb = SCIPvarGetLbGlobal(implvars[j]); 292 assert(impltypes[j] == SCIP_BOUNDTYPE_LOWER); 293 294 /* consider only nonredundant and numerical harmless implications */ 295 if( SCIPisGE(scip, implbounds[j], lb) && (implbounds[j] - lb) * SCIPfeastol(scip) < RELCUTCOEFMAXRANGE ) 296 { 297 /* add cut if violated */ 298 SCIP_CALL( addCut(scip, sepa, -1.0, implvars[j], solval, (lb - implbounds[j]), fracvars[i], fracvals[i], 299 -implbounds[j], cutoff, ncuts) ); 300 if ( *cutoff ) 301 return SCIP_OKAY; 302 } 303 } 304 } 305 } 306 307 /* stop separation here if cliques should not be separated */ 308 if( ! sepadata->usetwosizecliques ) 309 return SCIP_OKAY; 310 311 /* prepare clean clique data */ 312 SCIP_CALL( SCIPcleanupCliques(scip, cutoff) ); 313 314 if( *cutoff ) 315 return SCIP_OKAY; 316 317 cliques = SCIPgetCliques(scip); 318 ncliques = SCIPgetNCliques(scip); 319 320 /* loop over cliques of size 2 which are essentially implications and add cuts if they are violated */ 321 for( i = 0; i < ncliques; ++i ) 322 { 323 SCIP_CLIQUE* clique; 324 SCIP_VAR** clqvars; 325 SCIP_Bool* clqvals; 326 SCIP_Real rhs; 327 328 clique = cliques[i]; 329 /* only consider inequality cliques of size 2 */ 330 if( SCIPcliqueGetNVars(clique) != 2 || SCIPcliqueIsEquation(clique) ) 331 continue; 332 333 /* get variables and values of the clique */ 334 clqvars = SCIPcliqueGetVars(clique); 335 clqvals = SCIPcliqueGetValues(clique); 336 337 /* clique variables should never be equal after clean up */ 338 assert(clqvars[0] != clqvars[1]); 339 340 /* calculate right hand side of clique inequality, which is initially 1 and decreased by 1 for every occurence of 341 * a negated variable in the clique 342 */ 343 rhs = 1.0; 344 if( ! clqvals[0] ) 345 rhs -= 1.0; 346 if( ! clqvals[1] ) 347 rhs -= 1.0; 348 349 /* Basic clique inequality is 350 * 351 * cx * x + (1-cx) (1-x) + cy * y + (1-cy) * (1-y) <= 1, 352 * 353 * where x and y are the two binary variables in the clique and cx and cy are their clique values, where a 354 * clique value of 0 means that the negation of the variable should be part of the inequality. 355 * Hence, exactly one of the two possible terms for x and y has a nonzero coefficient 356 */ 357 SCIP_CALL( addCut(scip, sepa, 358 clqvals[0] ? 1.0 : -1.0, clqvars[0], SCIPgetSolVal(scip, sol, clqvars[0]), 359 clqvals[1] ? 1.0 : -1.0, clqvars[1], SCIPgetSolVal(scip, sol, clqvars[1]), 360 rhs, cutoff, ncuts) ); 361 362 /* terminate if cutoff was found */ 363 if( *cutoff ) 364 return SCIP_OKAY; 365 } 366 367 return SCIP_OKAY; 368 } 369 370 371 /* 372 * Callback methods of separator 373 */ 374 375 /** copy method for separator plugins (called when SCIP copies plugins) */ 376 static 377 SCIP_DECL_SEPACOPY(sepaCopyImpliedbounds) 378 { /*lint --e{715}*/ 379 assert(scip != NULL); 380 assert(sepa != NULL); 381 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0); 382 383 /* call inclusion method of constraint handler */ 384 SCIP_CALL( SCIPincludeSepaImpliedbounds(scip) ); 385 386 return SCIP_OKAY; 387 } 388 389 /** destructor of separator to free user data (called when SCIP is exiting) */ 390 static 391 SCIP_DECL_SEPAFREE(sepaFreeImpliedbounds) 392 { /*lint --e{715}*/ 393 SCIP_SEPADATA* sepadata; 394 395 assert(scip != NULL); 396 assert(sepa != NULL); 397 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0); 398 399 /* get separation data and free it */ 400 sepadata = SCIPsepaGetData(sepa); 401 assert(sepadata != NULL); 402 SCIPfreeBlockMemory(scip, &sepadata); 403 404 /* reset data pointer to NULL */ 405 SCIPsepaSetData(sepa, NULL); 406 407 return SCIP_OKAY; 408 } 409 410 411 /** LP solution separation method of separator */ 412 static 413 SCIP_DECL_SEPAEXECLP(sepaExeclpImpliedbounds) 414 { /*lint --e{715}*/ 415 SCIP_VAR** vars; 416 SCIP_VAR** fracvars; 417 SCIP_Real* solvals; 418 SCIP_Real* fracvals; 419 SCIP_Bool cutoff; 420 int nvars; 421 int nbinvars; 422 int nfracs; 423 int ncuts; 424 425 assert(sepa != NULL); 426 assert(scip != NULL); 427 428 *result = SCIP_DIDNOTRUN; 429 430 /* gets active problem variables */ 431 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, NULL, NULL, NULL) ); 432 if( nbinvars == 0 ) 433 return SCIP_OKAY; 434 435 /* get fractional problem variables */ 436 /* todo try out also separating fractional implicit integer variables */ 437 SCIP_CALL( SCIPgetLPBranchCands(scip, &fracvars, &fracvals, NULL, &nfracs, NULL, NULL) ); 438 if( nfracs == 0 ) 439 return SCIP_OKAY; 440 441 /* get solution values for all variables */ 442 SCIP_CALL( SCIPallocBufferArray(scip, &solvals, nvars) ); 443 SCIP_CALL( SCIPgetVarSols(scip, nvars, vars, solvals) ); 444 445 /* call the cut separation */ 446 SCIP_CALL( separateCuts(scip, sepa, NULL, solvals, fracvars, fracvals, nfracs, &cutoff, &ncuts) ); 447 448 /* adjust result code */ 449 if ( cutoff ) 450 *result = SCIP_CUTOFF; 451 else if ( ncuts > 0 ) 452 *result = SCIP_SEPARATED; 453 else 454 *result = SCIP_DIDNOTFIND; 455 456 /* free temporary memory */ 457 SCIPfreeBufferArray(scip, &solvals); 458 459 return SCIP_OKAY; 460 } 461 462 463 /** arbitrary primal solution separation method of separator */ 464 static 465 SCIP_DECL_SEPAEXECSOL(sepaExecsolImpliedbounds) 466 { /*lint --e{715}*/ 467 SCIP_VAR** vars; 468 SCIP_VAR** fracvars; 469 SCIP_Real* solvals; 470 SCIP_Real* fracvals; 471 SCIP_Bool cutoff; 472 int nvars; 473 int nbinvars; 474 int nfracs; 475 int ncuts; 476 int i; 477 478 assert(sepa != NULL); 479 assert(scip != NULL); 480 481 *result = SCIP_DIDNOTRUN; 482 483 /* gets active problem variables */ 484 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, NULL, NULL, NULL) ); 485 if( nbinvars == 0 ) 486 return SCIP_OKAY; 487 488 /* get solution values for all variables */ 489 SCIP_CALL( SCIPallocBufferArray(scip, &solvals, nvars) ); 490 SCIP_CALL( SCIPgetSolVals(scip, sol, nvars, vars, solvals) ); 491 492 /* get binary problem variables that are fractional in given solution */ 493 SCIP_CALL( SCIPallocBufferArray(scip, &fracvars, nbinvars) ); 494 SCIP_CALL( SCIPallocBufferArray(scip, &fracvals, nbinvars) ); 495 nfracs = 0; 496 for( i = 0; i < nbinvars; ++i ) 497 { 498 if( !SCIPisFeasIntegral(scip, solvals[i]) ) 499 { 500 fracvars[nfracs] = vars[i]; 501 fracvals[nfracs] = solvals[i]; 502 nfracs++; 503 } 504 } 505 506 /* call the cut separation */ 507 ncuts = 0; 508 cutoff = FALSE; 509 510 if( nfracs > 0 ) 511 { 512 SCIP_CALL( separateCuts(scip, sepa, sol, solvals, fracvars, fracvals, nfracs, &cutoff, &ncuts) ); 513 } 514 515 /* adjust result code */ 516 if ( cutoff ) 517 *result = SCIP_CUTOFF; 518 else if ( ncuts > 0 ) 519 *result = SCIP_SEPARATED; 520 else 521 *result = SCIP_DIDNOTFIND; 522 523 /* free temporary memory */ 524 SCIPfreeBufferArray(scip, &fracvals); 525 SCIPfreeBufferArray(scip, &fracvars); 526 SCIPfreeBufferArray(scip, &solvals); 527 528 return SCIP_OKAY; 529 } 530 531 532 /* 533 * separator specific interface methods 534 */ 535 536 /** creates the impliedbounds separator and includes it in SCIP */ 537 SCIP_RETCODE SCIPincludeSepaImpliedbounds( 538 SCIP* scip /**< SCIP data structure */ 539 ) 540 { 541 SCIP_SEPADATA* sepadata; 542 SCIP_SEPA* sepa; 543 544 /* create impliedbounds separator data */ 545 SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) ); 546 assert(sepadata != NULL); 547 548 /* include separator */ 549 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST, 550 SEPA_USESSUBSCIP, SEPA_DELAY, 551 sepaExeclpImpliedbounds, sepaExecsolImpliedbounds, 552 sepadata) ); 553 assert(sepa != NULL); 554 555 /* set non-NULL pointers to callback methods */ 556 SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyImpliedbounds) ); 557 SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeImpliedbounds) ); 558 559 /* add separator parameters */ 560 SCIP_CALL( SCIPaddBoolParam(scip, "separating/impliedbounds/usetwosizecliques", 561 "should violated inequalities for cliques with 2 variables be separated?", 562 &sepadata->usetwosizecliques, TRUE, DEFAULT_USETWOSIZECLIQUES, NULL, NULL) ); 563 564 return SCIP_OKAY; 565 } 566