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_mixing.c 26 * @ingroup DEFPLUGINS_SEPA 27 * @brief mixing/star inequality separator 28 * @author Weikun Chen 29 * @author Marc Pfetsch 30 * 31 * This separator generates cuts based on the mixing set 32 * \f[ 33 * X = \{ (x,y) \in \{0,1\}^{N \cup M} \times \mathbb{R} \, : \, y \geq a_i x_i, \, \textrm{for} \, i \in N, \, 34 * y \leq u - a_i x_i, \, \textrm{for} \, i \in M, \, 0 \leq y \leq u \}, 35 * \f] 36 * where \f$0 \leq a_i \leq u\f$ for all \f$i\f$. This information can be obtained directly from the variable bounds data 37 * structure. The separator will generate three classes of cuts. 38 * 39 * VLB: Let \f$T\f$ be a subset of \f$N\f$, wlog, \f$T = \{1,\ldots,r\}\f$ with \f$a_1 \leq a_2 \leq \ldots \leq a_r\f$. 40 * Let \f$a_0 = 0\f$. The mixing/star VLB cut is of the form \f$ y \geq \sum_{i=1}^r (a_i - a_{i-1})x_i \f$. 41 * 42 * VUB: Let \f$T\f$ be a subset of \f$M\f$, wlog, \f$T = \{1,\ldots,r\}\f$ with \f$a_1 \leq a_2 \leq \ldots \leq a_r\f$. 43 * Let \f$a_0 = 0\f$. The mixing/star VUB cut is of the form \f$ y \leq u - \sum_{i=1}^r (a_i - a_{i-1})x_i \f$. 44 * 45 * CONFLICT: Consider \f$i \in N\f$ and \f$j \in M\f$ with \f$a_i + a_j > u\f$. The conflict cut is 46 * \f$x_i + x_j \leq 1\f$. 47 * 48 * A small example is described in the following to see the generated cuts. 49 * \f[ 50 * Y = \{ (x,y) \in \{0,1\}^{4} \times \mathbb{R} \, : \, y \geq 2x_1, \, y \geq 3x_2, \, y \leq 4 - x_3, \, 51 * y \leq 4 - 2 x_4, \, 0 \leq y \leq 4 \}. 52 * \f] 53 * In this small example, the mixing/star cuts \f$y \geq 2x_1 + x_2\f$ (VLB) and \f$y \leq 4 - x_3 - x_4\f$ (VUB) will be 54 * considered to be generated. Besides the mixing cuts, we also consider the conflict cut \f$x_1 + x_3 \leq 1\f$ (CONFLICT). 55 * 56 * 57 * For an overview see: 58 * Atamturk, A., Nemhauser, G.L. and Savelsbergh, M.W.,@n 59 * The mixed vertex packing problem.@n 60 * Mathematical Programming, 89(1), 35-53, 2000. 61 * 62 * Some remarks: 63 * - Besides the mixing inequality, we also add the conflict inequality. 64 * - Currently, the performance is bad on the neos-565672 instance. 65 * The reason is that, after adding the separator, SCIP spends a lot of time at the stage of cutting plane generation. 66 * - We do not consider sparsity of the cuts as we aim to find a most violated cut. 67 * - Besides the most violated cut we consider, we also add an additional variable to make the cut be the strongest one, 68 * even the additional variable does not contribute any to the violation. 69 * 70 */ 71 72 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 73 74 #include "blockmemshell/memory.h" 75 #include "scip/pub_implics.h" 76 #include "scip/pub_lp.h" 77 #include "scip/pub_message.h" 78 #include "scip/pub_misc.h" 79 #include "scip/pub_sepa.h" 80 #include "scip/pub_var.h" 81 #include "scip/scip_branch.h" 82 #include "scip/scip_cut.h" 83 #include "scip/scip_lp.h" 84 #include "scip/scip_mem.h" 85 #include "scip/scip_message.h" 86 #include "scip/scip_numerics.h" 87 #include "scip/scip_param.h" 88 #include "scip/scip_prob.h" 89 #include "scip/scip_sepa.h" 90 #include "scip/scip_sol.h" 91 #include "scip/scip_solvingstats.h" 92 #include "scip/scip_var.h" 93 #include "scip/sepa_mixing.h" 94 #include "scip/scip_tree.h" 95 #include "scip/sepa_mixing.h" 96 #include <string.h> 97 98 99 #define SEPA_NAME "mixing" 100 #define SEPA_DESC "mixing inequality separator" 101 #define DEFAULT_MAXROUNDS -1 /**< maximal number of mixing separation rounds per node (-1: unlimited) */ 102 #define DEFAULT_MAXROUNDSROOT -1 /**< maximal number of mixing separation rounds in the root node (-1: unlimited) */ 103 #define SEPA_PRIORITY -50 104 #define SEPA_FREQ 10 105 #define SEPA_MAXBOUNDDIST 1.0 106 #define SEPA_USESSUBSCIP FALSE /**< does the separator use a secondary SCIP instance? */ 107 #define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */ 108 109 #define DEFAULT_USELOCALBOUNDS FALSE /**< should local bounds be used? */ 110 #define DEFAULT_ISCUTSONINTS FALSE /**< should general/implicit integer variables be used to generate cuts? */ 111 #define DEFAULT_MAXNUNSUCCESSFUL 10 /**< maximal number of consecutive unsuccessful iterations */ 112 113 /** separator-specific data for the mixing separator */ 114 struct SCIP_SepaData 115 { 116 SCIP_Bool uselocalbounds; /**< should local bounds be used? */ 117 SCIP_Bool iscutsonints; /**< should general/implicit integer variables be used to generate cuts? */ 118 int maxrounds; /**< maximal number of mixing separation rounds per node (-1: unlimited) */ 119 int maxroundsroot; /**< maximal number of mixing separation rounds in the root node (-1: unlimited) */ 120 int nunsuccessful; /**< number of consecutive unsuccessful iterations */ 121 int maxnunsuccessful; /**< maximal number of consecutive unsuccessful iterations */ 122 }; 123 124 /* 125 * local methods 126 */ 127 128 /** adds the given cut */ 129 static 130 SCIP_RETCODE addCut( 131 SCIP* scip, /**< SCIP data structure */ 132 SCIP_SEPA* sepa, /**< separator */ 133 SCIP_SOL* sol, /**< the solution that should be separated, or NULL for LP solution */ 134 SCIP_Real* cutcoefs, /**< coefficients of active variables in cut */ 135 int* cutinds, /**< problem indices of variables in cut */ 136 int cutnnz, /**< number of non-zeros in cut */ 137 SCIP_Real cutrhs, /**< right hand side of cut */ 138 SCIP_Bool cutislocal, /**< Is the cut only locally valid? */ 139 SCIP_Bool* cutoff, /**< pointer to store whether a cutoff has been detected */ 140 int* ncuts /**< pointer to update number of cuts added */ 141 ) 142 { 143 char cutname[SCIP_MAXSTRLEN]; 144 SCIP_VAR** vars; 145 SCIP_ROW* cut; 146 int v; 147 148 assert(cutcoefs != NULL); 149 assert(cutinds != NULL); 150 assert(ncuts != NULL); 151 assert(cutoff != NULL); 152 153 *cutoff = FALSE; 154 155 /* get active problem variables */ 156 vars = SCIPgetVars(scip); 157 158 /* construct cut name */ 159 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "mix%" SCIP_LONGINT_FORMAT "_x%d", SCIPgetNLPs(scip), *ncuts); 160 161 /* create empty cut */ 162 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), cutrhs, 163 cutislocal, FALSE, TRUE) ); 164 165 /* cache the row extension and only flush them if the cut gets added */ 166 SCIP_CALL( SCIPcacheRowExtensions(scip, cut) ); 167 168 /* collect all non-zero coefficients */ 169 for( v = 0; v < cutnnz; ++v ) 170 { 171 SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cutinds[v]], cutcoefs[v]) ); 172 } 173 174 /* flush all changes before adding the cut */ 175 SCIP_CALL( SCIPflushRowExtensions(scip, cut) ); 176 177 if( SCIPisCutEfficacious(scip, sol, cut) ) 178 { 179 /* set cut rank */ 180 SCIProwChgRank(cut, 1); 181 182 #ifdef SCIP_DEBUG 183 SCIPdebugMsg(scip, "-> found cut (eff: %f): ", SCIPgetCutEfficacy(scip, sol, cut)); 184 SCIP_CALL( SCIPprintRow(scip, cut, NULL) ); 185 #endif 186 187 if( cutislocal ) 188 { 189 /* local cuts are added to the sepastore */ 190 SCIP_CALL( SCIPaddRow(scip, cut, FALSE, cutoff) ); 191 } 192 else 193 { 194 SCIP_CALL( SCIPaddPoolCut(scip, cut) ); 195 } 196 (*ncuts)++; 197 } 198 199 /* release the row */ 200 SCIP_CALL( SCIPreleaseRow(scip, &cut) ); 201 202 return SCIP_OKAY; 203 } 204 205 /** searches and adds mixing cuts that are violated by the given solution value array 206 * 207 * This function implements a separation heuristic that runs in linear time in comparison to the quadratic exact 208 * algorithm in Atamturk et al.: 209 * - Lower and upper bounds are considered separately. Then possible conflict cuts. 210 * - Variable lower/upper bounds data are collected, i.e., the corresponding binary variables and coefficients. 211 * - These lists are sorted non-increasingly according to the solution values. 212 * - Then binary variables are added in turn as long as their coefficients increase in order to make the coefficients 213 * nonnegative. This clearly makes the cuts heuristic, since it is order dependent, but also sparser. 214 * - The procedure stops as soon as it reaches 0 solution values. 215 * - If the cut is efficious it is added. 216 * 217 * @todo Check whether one wants to sort according to the quotient of solution values and coefficients to increase the 218 * chance of having smaller coefficients in the front. 219 */ 220 static 221 SCIP_RETCODE separateCuts( 222 SCIP* scip, /**< SCIP data structure */ 223 SCIP_SEPA* sepa, /**< separator */ 224 SCIP_SOL* sol, /**< the solution that should be separated, or NULL for LP solution */ 225 SCIP_Bool* cutoff, /**< whether a cutoff has been detected */ 226 int* ncuts /**< pointer to store the number of generated cuts */ 227 ) 228 { 229 SCIP_SEPADATA* sepadata; 230 SCIP_VAR* var; 231 SCIP_VAR** vars; 232 SCIP_Real* vlbmixcoefs; 233 SCIP_Real* vlbmixsols; 234 SCIP_Real* vubmixcoefs; 235 SCIP_Real* vubmixsols; 236 SCIP_Real* cutcoefs; 237 SCIP_Real cutrhs; 238 int* vlbmixinds; 239 int* vubmixinds; 240 int* cutinds; 241 int* vlbmixsigns; 242 int* vubmixsigns; 243 int firstvar; 244 int nmaxvars; 245 int nvars; 246 int i; 247 int k; 248 249 assert(sepa != NULL); 250 assert(cutoff != NULL); 251 assert(ncuts != NULL); 252 253 *cutoff = FALSE; 254 *ncuts = 0; 255 256 /* exit if there are no binary variables - ignore integer variables that have 0/1 bounds */ 257 nmaxvars = SCIPgetNBinVars(scip); 258 if( nmaxvars <= 0 ) 259 return SCIP_OKAY; 260 261 sepadata = SCIPsepaGetData(sepa); 262 assert(sepadata != NULL); 263 264 /* get the index of the first considered variable */ 265 if( sepadata->iscutsonints ) 266 { 267 /* generate cuts based on all nonbinary variabels */ 268 firstvar = SCIPgetNBinVars(scip); 269 } 270 else 271 { 272 /* only generate cuts based on continuous variables */ 273 firstvar = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) + SCIPgetNImplVars(scip); 274 } 275 nvars = SCIPgetNVars(scip); 276 if( firstvar == nvars ) 277 return SCIP_OKAY; 278 279 vars = SCIPgetVars(scip); 280 281 /* allocate temporary memory */ 282 SCIP_CALL( SCIPallocBufferArray(scip, &vlbmixcoefs, nmaxvars) ); 283 SCIP_CALL( SCIPallocBufferArray(scip, &vlbmixsols, nmaxvars) ); 284 SCIP_CALL( SCIPallocBufferArray(scip, &vlbmixinds, nmaxvars) ); 285 SCIP_CALL( SCIPallocBufferArray(scip, &vlbmixsigns, nmaxvars) ); 286 SCIP_CALL( SCIPallocBufferArray(scip, &vubmixcoefs, nmaxvars) ); 287 SCIP_CALL( SCIPallocBufferArray(scip, &vubmixsols, nmaxvars) ); 288 SCIP_CALL( SCIPallocBufferArray(scip, &vubmixinds, nmaxvars) ); 289 SCIP_CALL( SCIPallocBufferArray(scip, &vubmixsigns, nmaxvars) ); 290 SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, nmaxvars + 1) ); 291 SCIP_CALL( SCIPallocBufferArray(scip, &cutinds, nmaxvars + 1) ); 292 293 for( i = firstvar; i < nvars; i++ ) 294 { 295 SCIP_VAR** vlbvars; 296 SCIP_Real* vlbcoefs; 297 SCIP_Real* vlbconsts; 298 SCIP_VAR** vubvars; 299 SCIP_Real* vubcoefs; 300 SCIP_Real* vubconsts; 301 SCIP_Real maxabscoef; 302 SCIP_Real activity; 303 SCIP_Real lastcoef; 304 SCIP_Real varsolval; 305 SCIP_Real lb = SCIP_INVALID; 306 SCIP_Real ub = SCIP_INVALID; 307 SCIP_Bool islocallb = FALSE; /* Is it a local lower bound or global lower bound? */ 308 SCIP_Bool islocalub = FALSE; /* Is it a local upper bound or global upper bound? */ 309 SCIP_Bool cutislocal; /* Is it a local cut or global cut? */ 310 int vlbmixsize = 0; 311 int vubmixsize = 0; 312 int cutnnz = 0; 313 int maxabsind; 314 int maxabssign; 315 int nvlb; 316 int nvub; 317 int j; 318 319 var = vars[i]; 320 assert( SCIPvarGetType(var) != SCIP_VARTYPE_BINARY ); 321 322 if( SCIPvarGetProbindex(var) < 0 ) 323 continue; 324 325 nvlb = SCIPvarGetNVlbs(var); 326 nvub = SCIPvarGetNVubs(var); 327 328 if( nvlb == 0 && nvub == 0 ) 329 continue; 330 331 /* skip lower bound if the LP solution value is equal to the upper bound of the continuous variable */ 332 varsolval = SCIPgetSolVal(scip, sol, var); 333 if( SCIPisFeasEQ(scip, SCIPvarGetUbLocal(var), varsolval) ) 334 goto VUB; 335 336 if( nvlb == 0 ) 337 goto VUB; 338 339 /* get variable lower variable bounds information */ 340 vlbvars = SCIPvarGetVlbVars(var); 341 vlbcoefs = SCIPvarGetVlbCoefs(var); 342 vlbconsts = SCIPvarGetVlbConstants(var); 343 344 maxabscoef = 0.0; 345 maxabsind = -1; 346 maxabssign = 0; 347 348 lb = SCIPvarGetLbGlobal(var); 349 if( sepadata->uselocalbounds && SCIPisLT(scip, lb, SCIPvarGetLbLocal(var)) ) 350 { 351 /* this is a lcoal cut */ 352 islocallb = TRUE; 353 lb = SCIPvarGetLbLocal(var); 354 } 355 356 #ifdef SCIP_DEBUG 357 for( j = 0; j < nvlb; j++ ) 358 { 359 SCIP_Real tmplb; 360 361 if( SCIPvarIsBinary(vlbvars[j]) && SCIPvarGetProbindex(vlbvars[j]) >= 0 ) 362 { 363 tmplb = (vlbcoefs[j] > 0) ? vlbconsts[j] : (vlbconsts[j] + vlbcoefs[j]); 364 assert( SCIPisFeasLE(scip, tmplb, lb) ); 365 } 366 } 367 #endif 368 369 assert( SCIPisFeasLE(scip, lb, SCIPvarGetUbLocal(var)) ); 370 371 /* extract the useful variable bounds information (binary and nonredundant) */ 372 for( j = 0; j < nvlb; j++ ) 373 { 374 /* consider only active and binary variables */ 375 if( SCIPvarIsBinary(vlbvars[j]) && SCIPvarGetProbindex(vlbvars[j]) >= 0 ) 376 { 377 SCIP_Real maxactivity; 378 SCIP_Real coef; 379 380 maxactivity = (vlbcoefs[j] > 0) ? (vlbconsts[j] + vlbcoefs[j]) : vlbconsts[j]; 381 382 /* skip redundant variable bound constraints */ 383 if( SCIPisFeasLE(scip, maxactivity, lb) ) 384 continue; 385 386 if( vlbcoefs[j] > 0 ) 387 { 388 coef = maxactivity - lb; 389 vlbmixsigns[vlbmixsize] = 0; 390 } 391 else 392 { 393 coef = lb - maxactivity; 394 vlbmixsigns[vlbmixsize] = 1; 395 } 396 assert(vlbmixsize <= nvars); 397 398 vlbmixcoefs[vlbmixsize] = REALABS(coef); 399 vlbmixinds[vlbmixsize] = SCIPvarGetProbindex(vlbvars[j]); 400 vlbmixsols[vlbmixsize] = (! vlbmixsigns[vlbmixsize]) ? SCIPgetSolVal(scip, sol, vlbvars[j]) : (1.0 - SCIPgetSolVal(scip, sol, vlbvars[j])); 401 402 /* update the maximal coefficient if needed */ 403 if( maxabscoef < vlbmixcoefs[vlbmixsize] ) 404 { 405 maxabscoef = vlbmixcoefs[vlbmixsize]; 406 maxabsind = vlbmixinds[vlbmixsize]; 407 maxabssign = vlbmixsigns[vlbmixsize]; 408 } 409 410 ++vlbmixsize; 411 412 /* stop if size is exceeded; possibly ignore redundant variable bounds */ 413 if( vlbmixsize >= nmaxvars ) 414 break; 415 } 416 } 417 assert( vlbmixsize <= nmaxvars ); 418 419 /* stop if no variable lower bounds information exists */ 420 if( vlbmixsize == 0 ) 421 goto VUB; 422 423 /* stop if the current solution value of the transformed continuous variable is larger than the maximal coefficient */ 424 if( SCIPisFeasGT(scip, varsolval - lb, maxabscoef) ) 425 goto VUB; 426 427 /* sort the solution values in non-increasing order */ 428 SCIPsortDownRealRealIntInt(vlbmixsols, vlbmixcoefs, vlbmixinds, vlbmixsigns, vlbmixsize); 429 430 /* add the continuous variable */ 431 cutcoefs[cutnnz] = -1; 432 cutinds[cutnnz] = SCIPvarGetProbindex(var); 433 cutrhs = -lb; 434 cutnnz++; 435 436 activity = -(varsolval - lb); 437 lastcoef = 0.0; 438 439 /* loop over the variables and add the variable to the cut if its coefficient is larger than that of the last variable */ 440 for( j = 0; j < vlbmixsize; j++ ) 441 { 442 SCIP_Real solval; 443 444 solval = vlbmixsols[j]; 445 446 /* stop if we can not find a violated cut or we reached 0 solution values */ 447 if( activity + solval * (maxabscoef - lastcoef) < 0.0 || SCIPisFeasZero(scip, solval) ) 448 break; 449 else 450 { 451 /* skip if we have already added a variable with bigger coefficient */ 452 if( SCIPisLE(scip, vlbmixcoefs[j], lastcoef) ) 453 continue; 454 else 455 { 456 activity += (vlbmixcoefs[j] - lastcoef) * solval; 457 if( vlbmixsigns[j] ) 458 { 459 cutcoefs[cutnnz] = lastcoef - vlbmixcoefs[j]; 460 cutrhs -= vlbmixcoefs[j] - lastcoef; 461 } 462 else 463 cutcoefs[cutnnz] = vlbmixcoefs[j] - lastcoef; 464 cutinds[cutnnz++] = vlbmixinds[j]; 465 lastcoef = vlbmixcoefs[j]; 466 } 467 } 468 } 469 470 /* add the variable with maximal coefficient to make sure the cut is strong enough */ 471 if( SCIPisGT(scip, maxabscoef, lastcoef) ) 472 { 473 /* do not update activity: either the corresponding solval is 0.0 or the cut will not become efficious */ 474 if( maxabssign ) 475 { 476 cutcoefs[cutnnz] = lastcoef - maxabscoef; 477 cutrhs -= maxabscoef - lastcoef; 478 } 479 else 480 cutcoefs[cutnnz] = maxabscoef - lastcoef; 481 cutinds[cutnnz++] = maxabsind; 482 } 483 assert( cutnnz <= nmaxvars + 1 ); 484 485 /* add the cut if the violtion is good enough and the number of nonzero coefficients is larger than 2 */ 486 if( SCIPisEfficacious(scip, activity) && cutnnz > 2 ) 487 { 488 SCIP_CALL( addCut(scip, sepa, sol, cutcoefs, cutinds, cutnnz, cutrhs, islocallb, cutoff, ncuts) ); 489 } 490 491 VUB: 492 if( nvub == 0 ) 493 goto CONFLICT; 494 495 /* get variable upper bounds information */ 496 vubvars = SCIPvarGetVubVars(var); 497 vubcoefs = SCIPvarGetVubCoefs(var); 498 vubconsts = SCIPvarGetVubConstants(var); 499 500 maxabscoef = 0.0; 501 maxabsind = -1; 502 maxabssign = 0; 503 504 /* stop if the lower bound is equal to the solution value of the continuous variable */ 505 if( SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), varsolval) ) 506 goto CONFLICT; 507 508 ub = SCIPvarGetUbGlobal(var); 509 if( sepadata->uselocalbounds && SCIPisGT(scip, ub, SCIPvarGetUbLocal(var)) ) 510 { 511 /* this is a lcoal cut */ 512 islocalub = TRUE; 513 ub = SCIPvarGetUbLocal(var); 514 } 515 516 #ifdef SCIP_DEBUG 517 for( j = 0; j < nvub; j++ ) 518 { 519 SCIP_Real tmpub; 520 521 if( SCIPvarIsBinary(vubvars[j]) && SCIPvarGetProbindex(vubvars[j]) >= 0 ) 522 { 523 tmpub = (vubcoefs[j] < 0) ? vubconsts[j] : (vubconsts[j] + vubcoefs[j]); 524 assert( SCIPisFeasGE(scip, tmpub, ub) ); 525 } 526 } 527 #endif 528 529 assert( SCIPisFeasLE(scip, SCIPvarGetLbLocal(var), ub) ); 530 531 /* extract the useful variable bounds information (binary and nonredundant) */ 532 for( j = 0; j < nvub; j++ ) 533 { 534 /* consider only active and binary variables */ 535 if( SCIPvarIsBinary(vubvars[j]) && SCIPvarGetProbindex(vubvars[j]) >= 0 ) 536 { 537 SCIP_Real minactivity; 538 SCIP_Real coef; 539 540 minactivity = (vubcoefs[j] < 0) ? (vubconsts[j] + vubcoefs[j]) : vubconsts[j]; 541 542 /* skip redundant variable bound constraints */ 543 if( SCIPisFeasLE(scip, ub, minactivity) ) 544 continue; 545 546 if( vubcoefs[j] > 0 ) 547 { 548 coef = ub - minactivity; 549 vubmixsigns[vubmixsize] = 1; 550 } 551 else 552 { 553 coef = minactivity - ub; 554 vubmixsigns[vubmixsize] = 0; 555 } 556 557 vubmixcoefs[vubmixsize] = REALABS(coef); 558 vubmixinds[vubmixsize] = SCIPvarGetProbindex(vubvars[j]); 559 vubmixsols[vubmixsize] = (! vubmixsigns[vubmixsize]) ? SCIPgetSolVal(scip, sol, vubvars[j]): (1.0 - SCIPgetSolVal(scip, sol, vubvars[j])); 560 561 /* update the maximal coefficient if needed */ 562 if( maxabscoef < vubmixcoefs[vubmixsize] ) 563 { 564 maxabscoef = vubmixcoefs[vubmixsize]; 565 maxabsind = vubmixinds[vubmixsize]; 566 maxabssign = vubmixsigns[vubmixsize]; 567 } 568 569 ++vubmixsize; 570 571 /* stop if size is exceeded; possibly ignore redundant variable bounds */ 572 if( vubmixsize >= nmaxvars ) 573 break; 574 } 575 } 576 assert( vubmixsize <= nmaxvars ); 577 578 /* stop if no variable upper bounds information exists */ 579 if( vubmixsize == 0 ) 580 goto CONFLICT; 581 582 /* stop if the current solution value of transformed continuous variable is larger than the maximal coefficient */ 583 if( SCIPisFeasGT(scip, ub - varsolval, maxabscoef) ) 584 goto CONFLICT; 585 586 /* sort the solution values in non-increasing order */ 587 SCIPsortDownRealRealIntInt(vubmixsols, vubmixcoefs, vubmixinds, vubmixsigns, vubmixsize); 588 589 /* add the continuous variables */ 590 cutnnz = 0; 591 cutcoefs[cutnnz] = 1; 592 cutinds[cutnnz] = SCIPvarGetProbindex(var); 593 cutrhs = ub; 594 cutnnz++; 595 596 activity = varsolval - ub; 597 lastcoef = 0.0; 598 599 for( j = 0; j < vubmixsize; j++ ) 600 { 601 SCIP_Real solval; 602 603 solval = vubmixsols[j]; 604 605 /* stop if we can not find a violated cut or we reached 0 solution values */ 606 if( activity + solval * (maxabscoef - lastcoef) < 0.0 || SCIPisFeasZero(scip, solval) ) 607 break; 608 else 609 { 610 /* skip if we have already added a variable with bigger coefficient */ 611 if( SCIPisLE(scip, vubmixcoefs[j], lastcoef) ) 612 continue; 613 else 614 { 615 activity += (vubmixcoefs[j] - lastcoef) * solval; 616 if( vubmixsigns[j] ) 617 { 618 cutcoefs[cutnnz] = lastcoef - vubmixcoefs[j]; 619 cutrhs -= vubmixcoefs[j] - lastcoef; 620 } 621 else 622 cutcoefs[cutnnz] = vubmixcoefs[j] - lastcoef; 623 cutinds[cutnnz++] = vubmixinds[j]; 624 lastcoef = vubmixcoefs[j]; 625 } 626 } 627 } 628 629 /* add the variable with maximal coefficient if needed */ 630 if( SCIPisGT(scip, maxabscoef, lastcoef) ) 631 { 632 /* do not update activity: either the corresponding solval is 0.0 or the cut will not become efficious */ 633 if( maxabssign ) 634 { 635 cutcoefs[cutnnz] = lastcoef - maxabscoef; 636 cutrhs -= maxabscoef - lastcoef; 637 } 638 else 639 cutcoefs[cutnnz] = maxabscoef - lastcoef; 640 cutinds[cutnnz++] = maxabsind; 641 } 642 assert( cutnnz <= nmaxvars + 1 ); 643 644 /* add the cut if the violtion is good enough and the number of nonzero coefficients is larger than 2 */ 645 if( SCIPisEfficacious(scip, activity) && cutnnz > 2 ) 646 { 647 SCIP_CALL( addCut(scip, sepa, sol, cutcoefs, cutinds, cutnnz, cutrhs, islocalub, cutoff, ncuts) ); 648 } 649 650 CONFLICT: 651 /* combine the variable lower bounds information and upper bounds information together to generate cuts */ 652 /* stop if no useful variable lower (or upper) bounds information exists */ 653 if( vlbmixsize == 0 || vubmixsize == 0 ) 654 continue; 655 656 assert( lb != SCIP_INVALID ); /*lint !e777*/ 657 assert( ub != SCIP_INVALID ); /*lint !e777*/ 658 659 cutislocal = islocallb || islocalub; 660 for( j = 0; j < vlbmixsize; j++ ) 661 { 662 SCIP_Real solval; 663 664 solval = vlbmixsols[j]; 665 666 /* stop if no violated cut exists */ 667 if( ! SCIPisEfficacious(scip, solval + vubmixsols[0] - 1.0) ) 668 break; 669 670 for( k = 0; k < vubmixsize; k++ ) 671 { 672 /* only consider the inequality if its violation is good enough */ 673 if( SCIPisEfficacious(scip, solval + vubmixsols[k] - 1.0) ) 674 { 675 SCIP_Real tmp; 676 677 tmp = lb + vlbmixcoefs[j] + vubmixcoefs[k] - ub; 678 679 /* add the cut if it is valid */ 680 if( SCIPisEfficacious(scip, tmp) ) 681 { 682 cutnnz = 2; 683 cutrhs = 1.0; 684 cutcoefs[0] = vlbmixsigns[j] ? -1.0 : 1.0; 685 cutcoefs[1] = vubmixsigns[k] ? -1.0 : 1.0; 686 cutinds[0] = vlbmixinds[j]; 687 cutinds[1] = vubmixinds[k]; 688 cutrhs = vlbmixsigns[j] ? (cutrhs - 1.0) : cutrhs; 689 cutrhs = vubmixsigns[k] ? (cutrhs - 1.0) : cutrhs; 690 SCIP_CALL( addCut(scip, sepa, sol, cutcoefs, cutinds, cutnnz, cutrhs, cutislocal, cutoff, ncuts) ); 691 } 692 } 693 else 694 break; 695 } 696 } 697 } 698 699 /* free temporary memory */ 700 SCIPfreeBufferArray(scip, &cutinds); 701 SCIPfreeBufferArray(scip, &cutcoefs); 702 SCIPfreeBufferArray(scip, &vubmixsigns); 703 SCIPfreeBufferArray(scip, &vubmixinds); 704 SCIPfreeBufferArray(scip, &vubmixsols); 705 SCIPfreeBufferArray(scip, &vubmixcoefs); 706 SCIPfreeBufferArray(scip, &vlbmixsigns); 707 SCIPfreeBufferArray(scip, &vlbmixinds); 708 SCIPfreeBufferArray(scip, &vlbmixsols); 709 SCIPfreeBufferArray(scip, &vlbmixcoefs); 710 711 return SCIP_OKAY; 712 } 713 714 715 /* 716 * Callback methods of separator 717 */ 718 719 /** copy method for separator plugins (called when SCIP copies plugins) */ 720 static 721 SCIP_DECL_SEPACOPY(sepaCopyMixing) 722 { /*lint --e{715}*/ 723 assert(scip != NULL); 724 assert(sepa != NULL); 725 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0); 726 727 /* call inclusion method of separator */ 728 SCIP_CALL( SCIPincludeSepaMixing(scip) ); 729 730 return SCIP_OKAY; 731 } 732 733 /** destructor of separator to free user data (called when SCIP is exiting) */ 734 static 735 SCIP_DECL_SEPAFREE(sepaFreeMixing) 736 { /*lint --e{715}*/ 737 SCIP_SEPADATA* sepadata; 738 739 assert(scip != NULL); 740 assert(sepa != NULL); 741 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0); 742 743 /* get separation data and free it */ 744 sepadata = SCIPsepaGetData(sepa); 745 assert(sepadata != NULL); 746 SCIPfreeBlockMemory(scip, &sepadata); 747 748 /* reset data pointer to NULL */ 749 SCIPsepaSetData(sepa, NULL); 750 751 return SCIP_OKAY; 752 } 753 754 755 /** LP solution separation method of separator */ 756 static 757 SCIP_DECL_SEPAEXECLP(sepaExeclpMixing) 758 { /*lint --e{715}*/ 759 SCIP_SEPADATA* sepadata; 760 SCIP_Bool cutoff; 761 int nbinvars; 762 int nvars; 763 int ncuts; 764 int ncalls; 765 766 assert(sepa != NULL); 767 assert(scip != NULL); 768 assert(result != NULL); 769 770 *result = SCIP_DIDNOTRUN; 771 ncalls = SCIPsepaGetNCallsAtNode(sepa); 772 sepadata = SCIPsepaGetData(sepa); 773 assert(sepadata != NULL); 774 775 /* only call the mixing cut separator a given number of times at each node */ 776 if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot) 777 || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) ) 778 return SCIP_OKAY; 779 780 /* gets numver of active problem variables and number of binary variables */ 781 SCIP_CALL( SCIPgetVarsData(scip, NULL, &nvars, &nbinvars, NULL, NULL, NULL) ); 782 783 /* if all the active problem variables are binary, stop */ 784 if( nvars == nbinvars ) 785 return SCIP_OKAY; 786 787 /* call the cut separation */ 788 SCIP_CALL( separateCuts(scip, sepa, NULL, &cutoff, &ncuts) ); 789 790 /* adjust result code */ 791 if( cutoff ) 792 *result = SCIP_CUTOFF; 793 else if( ncuts > 0 ) 794 { 795 SCIPdebugMsg(scip, "mixing separator generated %d cuts.\n", ncuts); 796 *result = SCIP_SEPARATED; 797 } 798 else 799 *result = SCIP_DIDNOTFIND; 800 801 return SCIP_OKAY; 802 } 803 804 /** arbitrary primal solution separation method of separator */ 805 static 806 SCIP_DECL_SEPAEXECSOL(sepaExecSolMixing) 807 { /*lint --e{715}*/ 808 SCIP_SEPADATA* sepadata; 809 SCIP_Bool cutoff; 810 int nbinvars; 811 int nvars; 812 int ncuts; 813 int ncalls; 814 815 assert(sepa != NULL); 816 assert(scip != NULL); 817 assert(result != NULL); 818 819 *result = SCIP_DIDNOTRUN; 820 sepadata = SCIPsepaGetData(sepa); 821 assert(sepadata != NULL); 822 823 /* do not run if we have reached the maximal number of consecutive unsuccessful calls */ 824 if( sepadata->nunsuccessful >= sepadata->maxnunsuccessful ) 825 return SCIP_OKAY; 826 827 /* only call the mixing cut separator a given number of times at each node */ 828 ncalls = SCIPsepaGetNCallsAtNode(sepa); 829 if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot) 830 || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) ) 831 return SCIP_OKAY; 832 833 /* gets numver of active problem variables and number of binary variables */ 834 nvars = SCIPgetNVars(scip); 835 nbinvars = SCIPgetNBinVars(scip); 836 837 /* if all the active problem variables are binary, stop */ 838 if( nvars == nbinvars ) 839 return SCIP_OKAY; 840 841 /* call the cut separation */ 842 SCIP_CALL( separateCuts(scip, sepa, sol, &cutoff, &ncuts) ); 843 844 /* adjust result code */ 845 if( cutoff ) 846 { 847 sepadata->nunsuccessful = 0; 848 *result = SCIP_CUTOFF; 849 } 850 else if( ncuts > 0 ) 851 { 852 SCIPdebugMsg(scip, "mixing separator generated %d cuts.\n", ncuts); 853 sepadata->nunsuccessful = 0; 854 *result = SCIP_SEPARATED; 855 } 856 else 857 { 858 ++sepadata->nunsuccessful; 859 *result = SCIP_DIDNOTFIND; 860 } 861 862 return SCIP_OKAY; 863 } 864 865 866 /* 867 * separator specific interface methods 868 */ 869 870 /** creates the mixing separator and includes it in SCIP */ 871 SCIP_RETCODE SCIPincludeSepaMixing( 872 SCIP* scip /**< SCIP data structure */ 873 ) 874 { 875 SCIP_SEPADATA* sepadata; 876 SCIP_SEPA* sepa; 877 878 /* create mixing separator data */ 879 SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) ); 880 assert(sepadata != NULL); 881 sepadata->nunsuccessful = 0; 882 883 /* include separator */ 884 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST, 885 SEPA_USESSUBSCIP, SEPA_DELAY, 886 sepaExeclpMixing, sepaExecSolMixing, 887 sepadata) ); 888 assert(sepa != NULL); 889 890 /* set non-NULL pointers to callback methods */ 891 SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyMixing) ); 892 SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeMixing) ); 893 894 /* add separator parameters */ 895 SCIP_CALL( SCIPaddBoolParam(scip, "separating/mixing/uselocalbounds", 896 "Should local bounds be used?", 897 &sepadata->uselocalbounds, TRUE, DEFAULT_USELOCALBOUNDS, NULL, NULL) ); 898 899 SCIP_CALL( SCIPaddBoolParam(scip, "separating/mixing/iscutsonints", 900 "Should general integer variables be used to generate cuts?", 901 &sepadata->iscutsonints, TRUE, DEFAULT_ISCUTSONINTS, NULL, NULL) ); 902 903 SCIP_CALL( SCIPaddIntParam(scip, "separating/mixing/maxrounds", 904 "maximal number of mixing separation rounds per node (-1: unlimited)", 905 &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) ); 906 907 SCIP_CALL( SCIPaddIntParam(scip, "separating/mixing/maxroundsroot", 908 "maximal number of mixing separation rounds in the root node (-1: unlimited)", 909 &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) ); 910 911 SCIP_CALL( SCIPaddIntParam(scip, "separating/mixing/maxnunsuccessful", 912 "maximal number of consecutive unsuccessful iterations", 913 &sepadata->maxnunsuccessful, FALSE, DEFAULT_MAXNUNSUCCESSFUL, -1, INT_MAX, NULL, NULL) ); 914 915 return SCIP_OKAY; 916 } 917