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_linking.c 26 * @ingroup DEFPLUGINS_CONS 27 * @brief constraint handler for linking constraints 28 * @author Stefan Heinz 29 * @author Jens Schulz 30 * 31 * The constraints handler stores linking constraints between a linking variable (integer or continuous) and an array of binary variables. Such 32 * a linking constraint has the form: 33 * 34 * linkvar = sum_{i=1}^n {vals[i] * binvars[i]} 35 * 36 * with the additional side condition that exactly one binary variable has to be one (set partitioning condition). 37 * 38 * This constraint can be created only with the linking variable if it is an integer variable. In this case the binary variables are only created on 39 * demand. That is, whenever someone asks for the binary variables. Therefore, such constraints can be used to get a 40 * "binary representation" of the domain of the linking variable which will be dynamically created. 41 * 42 * 43 * @todo add pairwise comparison of constraints in presolving (fast hash table version and complete pairwise comparison) 44 * @todo in case the integer variable is set to lower or upper bound it follows that only the corresponding binary 45 * variable has a positive value which is one, this can be used to fasten the checking routine 46 */ 47 48 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 49 50 #include "blockmemshell/memory.h" 51 #include "scip/cons_linear.h" 52 #include "scip/cons_linking.h" 53 #include "scip/cons_setppc.h" 54 #include "scip/pub_cons.h" 55 #include "scip/pub_event.h" 56 #include "scip/pub_lp.h" 57 #include "scip/pub_message.h" 58 #include "scip/pub_misc.h" 59 #include "scip/pub_misc_sort.h" 60 #include "scip/pub_var.h" 61 #include "scip/scip_conflict.h" 62 #include "scip/scip_cons.h" 63 #include "scip/scip_copy.h" 64 #include "scip/scip_cut.h" 65 #include "scip/scip_event.h" 66 #include "scip/scip_general.h" 67 #include "scip/scip_lp.h" 68 #include "scip/scip_mem.h" 69 #include "scip/scip_message.h" 70 #include "scip/scip_nlp.h" 71 #include "scip/scip_numerics.h" 72 #include "scip/scip_param.h" 73 #include "scip/scip_prob.h" 74 #include "scip/scip_probing.h" 75 #include "scip/scip_sol.h" 76 #include "scip/scip_tree.h" 77 #include "scip/scip_var.h" 78 #include "scip/symmetry_graph.h" 79 #include "symmetry/struct_symmetry.h" 80 #include <ctype.h> 81 #include <string.h> 82 83 /* constraint handler properties */ 84 #define CONSHDLR_NAME "linking" 85 #define CONSHDLR_DESC "linking constraint x = sum_{i=1}^{n} c_i*y_i, y1+...+yn = 1, x real, y's binary" 86 87 #define EVENTHDLR_NAME "linking" 88 #define EVENTHDLR_DESC "event handler for linking constraints" 89 90 #define CONSHDLR_SEPAPRIORITY 750000 /**< priority of the constraint handler for separation */ 91 #define CONSHDLR_ENFOPRIORITY -2050000 /**< priority of the constraint handler for constraint enforcing */ 92 #define CONSHDLR_CHECKPRIORITY -750000 /**< priority of the constraint handler for checking feasibility */ 93 #define CONSHDLR_SEPAFREQ 1 /**< frequency for separating cuts; zero means to separate only in the root node */ 94 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */ 95 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation, propagation and enforcement, -1 for no eager evaluations, 0 for first only */ 96 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */ 97 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */ 98 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */ 99 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */ 100 101 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP /**< propagation timing mask of the constraint handler */ 102 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */ 103 104 105 #define HASHSIZE_BINVARSCONS 500 /**< minimal size of hash table in linking constraint handler */ 106 #define DEFAULT_LINEARIZE FALSE /**< should the linking constraint be linearize after the binary variable are created */ 107 108 /* 109 * Data structures 110 */ 111 112 /** constraint data for linking constraints */ 113 struct SCIP_ConsData 114 { 115 SCIP_VAR* linkvar; /**< continuous variable which is linked */ 116 SCIP_VAR** binvars; /**< binary variables */ 117 SCIP_Real* vals; /**< coefficients */ 118 SCIP_ROW* row1; /**< LP row for the linking itself */ 119 SCIP_ROW* row2; /**< LP row ensuring the set partitioning condition of the binary variables */ 120 SCIP_NLROW* nlrow1; /**< NLP row for the linking itself */ 121 SCIP_NLROW* nlrow2; /**< NLP row ensuring the set partitioning condition of the binary variables */ 122 int nbinvars; /**< number of binary variables */ 123 int sizebinvars; /**< size of the binary variable array */ 124 int nfixedzeros; /**< current number of variables fixed to zero in the constraint */ 125 int nfixedones; /**< current number of variables fixed to one in the constraint */ 126 int firstnonfixed; /**< index of first locally non-fixed binary variable in binvars array */ 127 int lastnonfixed; /**< index of last locally non-fixed binary variable in binvars array */ 128 unsigned int cliqueadded:1; /**< was the set partitioning condition already added as clique? */ 129 unsigned int sorted:1; /**< are the coefficients of the binary variables are sorted in non-decreasing order */ 130 }; 131 132 /** constraint handler data */ 133 struct SCIP_ConshdlrData 134 { 135 SCIP_EVENTHDLR* eventhdlr; /**< event handler for bound change events on binary variables */ 136 SCIP_HASHMAP* varmap; /**< hash map mapping a linking variable to its linking constraint */ 137 SCIP_Bool linearize; /**< should the linking constraint be linearize after the binary variable are created */ 138 }; 139 140 /* 141 * Local methods 142 */ 143 144 /** returns for a given linking variable the corresponding hash map key */ 145 static 146 void* getHashmapKey( 147 SCIP_VAR* var /**< variable to get the hash map key for */ 148 ) 149 { 150 /* return the unique variable index + 1 */ 151 return (void*)(size_t)(SCIPvarGetIndex(var) + 1); /*lint !e571 !e776*/ 152 } 153 154 /* sort binary variable in non-decreasing order w.r.t. coefficients */ 155 static 156 void consdataSort( 157 SCIP_CONSDATA* consdata /**< linking constraint data */ 158 ) 159 { 160 if( consdata->sorted ) 161 return; 162 163 /* sort binary variable in non-decreasing order w.r.t. coefficients */ 164 SCIPsortRealPtr(consdata->vals, (void**)consdata->binvars, consdata->nbinvars); 165 166 consdata->sorted = TRUE; 167 } 168 169 170 /** installs rounding locks for the binary variables in the given linking constraint */ 171 static 172 SCIP_RETCODE lockRounding( 173 SCIP* scip, /**< SCIP data structure */ 174 SCIP_CONS* cons, /**< linking constraint */ 175 SCIP_VAR** binvars, /**< binary variables */ 176 int nbinvars /**< number of binary variables */ 177 ) 178 { 179 int b; 180 181 for( b = 0; b < nbinvars; ++b ) 182 { 183 SCIP_CALL( SCIPlockVarCons(scip, binvars[b], cons, TRUE, TRUE) ); 184 } 185 186 return SCIP_OKAY; 187 } 188 189 /** creates constraint handler data for the linking constraint handler */ 190 static 191 SCIP_RETCODE conshdlrdataCreate( 192 SCIP* scip, /**< SCIP data structure */ 193 SCIP_CONSHDLRDATA** conshdlrdata, /**< pointer to store the constraint handler data */ 194 SCIP_EVENTHDLR* eventhdlr /**< event handler */ 195 ) 196 { 197 assert(scip != NULL); 198 assert(conshdlrdata != NULL); 199 assert(eventhdlr != NULL); 200 201 SCIP_CALL( SCIPallocBlockMemory(scip, conshdlrdata) ); 202 203 /* create hash map */ 204 (*conshdlrdata)->varmap = NULL; 205 206 /* set event handler for bound change events on binary variables */ 207 (*conshdlrdata)->eventhdlr = eventhdlr; 208 209 return SCIP_OKAY; 210 } 211 212 /** frees constraint handler data for linking constraint handler */ 213 static 214 void conshdlrdataFree( 215 SCIP* scip, /**< SCIP data structure */ 216 SCIP_CONSHDLRDATA** conshdlrdata /**< pointer to the constraint handler data */ 217 ) 218 { 219 assert(conshdlrdata != NULL); 220 assert(*conshdlrdata != NULL); 221 222 /* free hash map */ 223 if( (*conshdlrdata)->varmap != NULL ) 224 SCIPhashmapFree(&(*conshdlrdata)->varmap); 225 226 /* free memory of constraint handler data */ 227 SCIPfreeBlockMemory(scip, conshdlrdata); 228 } 229 230 /** prints linking constraint to file stream */ 231 static 232 SCIP_RETCODE consdataPrint( 233 SCIP* scip, /**< SCIP data structure */ 234 SCIP_CONSDATA* consdata, /**< linking constraint data */ 235 FILE* file /**< output file (or NULL for standard output) */ 236 ) 237 { 238 SCIP_VAR** binvars; 239 SCIP_VAR* linkvar; 240 int nbinvars; 241 242 assert(scip != NULL); 243 assert(consdata != NULL); 244 245 linkvar = consdata->linkvar; 246 binvars = consdata->binvars; 247 nbinvars = consdata->nbinvars; 248 249 assert(linkvar != NULL); 250 assert(binvars != NULL || nbinvars == 0); 251 252 /* print linking variable */ 253 SCIP_CALL( SCIPwriteVarName(scip, file, linkvar, FALSE) ); 254 255 SCIPinfoMessage(scip, file, " = "); 256 257 if( nbinvars == 0 ) 258 { 259 SCIPinfoMessage(scip, file, " no binary variables yet"); 260 } 261 else 262 { 263 assert(binvars != NULL); 264 265 SCIP_CALL( SCIPwriteVarsLinearsum(scip, file, binvars, consdata->vals, nbinvars, FALSE) ); 266 } 267 268 return SCIP_OKAY; 269 } 270 271 /** catches events for variable at given position */ 272 static 273 SCIP_RETCODE catchEvent( 274 SCIP* scip, /**< SCIP data structure */ 275 SCIP_CONSDATA* consdata, /**< linking constraint data */ 276 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */ 277 int pos /**< array position of variable to catch bound change events for */ 278 ) 279 { 280 SCIP_VAR* var; 281 282 assert(consdata != NULL); 283 assert(eventhdlr != NULL); 284 assert(0 <= pos && pos < consdata->nbinvars); 285 assert(consdata->binvars != NULL); 286 287 var = consdata->binvars[pos]; 288 assert(var != NULL); 289 290 /* catch bound change events on variable */ 291 /**@todo do we have to add the event SCIP_EVENTTYPE_VARFIXED? */ 292 SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr, (SCIP_EVENTDATA*)consdata, NULL) ); 293 294 /* update the fixed variables counters for this variable */ 295 if( SCIPisEQ(scip, SCIPvarGetUbLocal(var), 0.0) ) 296 consdata->nfixedzeros++; 297 else if( SCIPisEQ(scip, SCIPvarGetLbLocal(var), 1.0) ) 298 consdata->nfixedones++; 299 300 return SCIP_OKAY; 301 } 302 303 /** drops events for variable at given position */ 304 static 305 SCIP_RETCODE dropEvent( 306 SCIP* scip, /**< SCIP data structure */ 307 SCIP_CONSDATA* consdata, /**< linking constraint data */ 308 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */ 309 int pos /**< array position of variable to catch bound change events for */ 310 ) 311 { 312 SCIP_VAR* var; 313 314 assert(consdata != NULL); 315 assert(eventhdlr != NULL); 316 assert(0 <= pos && pos < consdata->nbinvars); 317 assert(consdata->binvars != NULL); 318 319 var = consdata->binvars[pos]; 320 assert(var != NULL); 321 322 /* drop events on variable */ 323 SCIP_CALL( SCIPdropVarEvent(scip, var, SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr, (SCIP_EVENTDATA*)consdata, -1) ); 324 325 /* update the fixed variables counters for this variable */ 326 if( SCIPisEQ(scip, SCIPvarGetUbLocal(var), 0.0) ) 327 consdata->nfixedzeros--; 328 else if( SCIPisEQ(scip, SCIPvarGetLbLocal(var), 1.0) ) 329 consdata->nfixedones--; 330 331 return SCIP_OKAY; 332 } 333 334 /** catches bound change events for all variables in transformed linking constraint */ 335 static 336 SCIP_RETCODE catchAllEvents( 337 SCIP* scip, /**< SCIP data structure */ 338 SCIP_CONSDATA* consdata, /**< linking constraint data */ 339 SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */ 340 ) 341 { 342 int i; 343 344 assert(consdata != NULL); 345 346 /* author bzfhende 347 * 348 * TODO should we catch events even in the trivial case of only 1 binary variable 349 */ 350 351 /* catch event for every single variable */ 352 for( i = 0; i < consdata->nbinvars; ++i ) 353 { 354 SCIP_CALL( catchEvent(scip, consdata, eventhdlr, i) ); 355 } 356 357 return SCIP_OKAY; 358 } 359 360 /** drops bound change events for all variables in transformed linking constraint */ 361 static 362 SCIP_RETCODE dropAllEvents( 363 SCIP* scip, /**< SCIP data structure */ 364 SCIP_CONSDATA* consdata, /**< linking constraint data */ 365 SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */ 366 ) 367 { 368 int i; 369 370 assert(consdata != NULL); 371 372 /* author bzfhende 373 * 374 * TODO drop the events even in the trivial case nbinvars == 1? 375 */ 376 377 /* drop event of every single variable */ 378 for( i = 0; i < consdata->nbinvars; ++i ) 379 { 380 SCIP_CALL( dropEvent(scip, consdata, eventhdlr, i) ); 381 } 382 383 return SCIP_OKAY; 384 } 385 386 /** linearize the given linking constraint into a set partitioning constraint for the binary variables and a linear 387 * constraint for the linking between the linking variable and the binary variables */ 388 static 389 SCIP_RETCODE consdataLinearize( 390 SCIP* scip, /**< SCIP data structure */ 391 SCIP_CONS* cons, /**< linking constraint */ 392 SCIP_CONSDATA* consdata /**< linking constraint data */ 393 ) 394 { 395 SCIP_CONS* lincons; 396 int b; 397 398 SCIPdebugMsg(scip, "linearized linking constraint <%s>\n", SCIPconsGetName(cons)); 399 400 /* create set partitioning constraint for the binary variables */ 401 SCIP_CALL( SCIPcreateConsSetpart(scip, &lincons, SCIPconsGetName(cons), consdata->nbinvars, consdata->binvars, 402 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons), SCIPconsIsChecked(cons), 403 SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), 404 SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) ); 405 SCIP_CALL( SCIPaddCons(scip, lincons) ); 406 SCIP_CALL( SCIPreleaseCons(scip, &lincons) ); 407 408 /* create linear constraint for the linking between the binary variables and the linking variable */ 409 SCIP_CALL( SCIPcreateConsLinear(scip, &lincons, SCIPconsGetName(cons), 0, NULL, NULL, 0.0, 0.0, 410 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons), SCIPconsIsChecked(cons), 411 SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), 412 SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) ); 413 414 for( b = 0; b < consdata->nbinvars; ++b ) 415 { 416 SCIP_CALL( SCIPaddCoefLinear(scip, lincons, consdata->binvars[b], consdata->vals[b]) ); 417 } 418 SCIP_CALL( SCIPaddCoefLinear(scip, lincons, consdata->linkvar, -1.0) ); 419 420 SCIP_CALL( SCIPaddCons(scip, lincons) ); 421 SCIP_CALL( SCIPreleaseCons(scip, &lincons) ); 422 423 return SCIP_OKAY; 424 } 425 426 /** creates the binary variables */ 427 static 428 SCIP_RETCODE consdataCreateBinvars( 429 SCIP* scip, /**< SCIP data structure */ 430 SCIP_CONS* cons, /**< linking constraint */ 431 SCIP_CONSDATA* consdata, /**< linking constraint data */ 432 SCIP_EVENTHDLR* eventhdlr, /**< event handler for bound change events on binary variables */ 433 SCIP_Bool linearize /**< should the linking constraint be linearized */ 434 ) 435 { 436 SCIP_VAR* linkvar; 437 SCIP_VAR* binvar; 438 int lb; 439 int ub; 440 char name[SCIP_MAXSTRLEN]; 441 int nbinvars; 442 int b; 443 444 assert(scip != NULL); 445 assert(consdata != NULL); 446 assert(consdata->nbinvars == 0); 447 assert(consdata->binvars == NULL); 448 449 SCIPdebugMsg(scip, "create binary variables for linking variable <%s>\n", SCIPvarGetName(consdata->linkvar)); 450 451 /* author bzfhende 452 * 453 * TODO ensure that this method is only called for integer linking variables, because it does not make sense for continuous linking variables. 454 */ 455 456 linkvar = consdata->linkvar; 457 lb = SCIPconvertRealToInt(scip, SCIPvarGetLbGlobal(linkvar)); 458 ub = SCIPconvertRealToInt(scip, SCIPvarGetUbGlobal(linkvar)); 459 460 nbinvars = ub - lb + 1; 461 assert(nbinvars > 0); 462 463 /* allocate block memory for the binary variables */ 464 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->binvars, nbinvars) ); 465 /* allocate block memory for the binary variables */ 466 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->vals, nbinvars) ); 467 consdata->sizebinvars = nbinvars; 468 469 /* check if the linking variable is fixed */ 470 if( nbinvars == 1 ) 471 { 472 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s[%d]", SCIPvarGetName(linkvar), lb); 473 474 /* creates and captures a fixed binary variables */ 475 SCIP_CALL( SCIPcreateVar(scip, &binvar, name, 1.0, 1.0, 0.0, SCIP_VARTYPE_BINARY, 476 FALSE, TRUE, NULL, NULL, NULL, NULL, NULL) ); 477 SCIP_CALL( SCIPaddVar(scip, binvar) ); 478 479 consdata->binvars[0] = binvar; 480 consdata->vals[0] = lb; 481 } 482 else 483 { 484 for( b = 0; b < nbinvars; ++b) 485 { 486 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s[%d]", SCIPvarGetName(linkvar), lb + b); 487 488 /* creates and captures variables */ 489 SCIP_CALL( SCIPcreateVar(scip, &binvar, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY, 490 TRUE, TRUE, NULL, NULL, NULL, NULL, NULL) ); 491 492 /* add variable to the problem */ 493 SCIP_CALL( SCIPaddVar(scip, binvar) ); 494 consdata->binvars[b] = binvar; 495 consdata->vals[b] = lb + b; 496 } 497 } 498 499 consdata->nbinvars = nbinvars; 500 501 assert(consdata->nfixedzeros == 0); 502 assert(consdata->nfixedones == 0); 503 504 if( SCIPisTransformed(scip) ) 505 { 506 /* (rounding) lock binary variable */ 507 SCIP_CALL( lockRounding(scip, cons, consdata->binvars, consdata->nbinvars) ); 508 509 /* catch bound change events of variables */ 510 SCIP_CALL( catchAllEvents(scip, consdata, eventhdlr) ); 511 512 if( nbinvars > 1 ) 513 { 514 if( linearize ) 515 { 516 SCIP_CALL( consdataLinearize(scip, cons, consdata) ); 517 } 518 else 519 { 520 /* enable constraint */ 521 SCIP_CALL( SCIPenableCons(scip, cons) ); 522 } 523 } 524 } 525 526 return SCIP_OKAY; 527 } 528 529 /** creates consdata */ 530 static 531 SCIP_RETCODE consdataCreate( 532 SCIP* scip, /**< SCIP data structure */ 533 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */ 534 SCIP_CONSDATA** consdata, /**< pointer to constraint data */ 535 SCIP_VAR* linkvar, /**< linking variable which is linked */ 536 SCIP_VAR** binvars, /**< binary variables */ 537 SCIP_Real* vals, /**< coefficients of the binary variables */ 538 int nbinvars /**< number of binary starting variables */ 539 ) 540 { 541 int v; 542 543 assert(scip!= NULL); 544 assert(consdata != NULL); 545 assert(linkvar != NULL); 546 assert(binvars != NULL || nbinvars == 0); 547 assert(SCIPvarGetType(linkvar) != SCIP_VARTYPE_CONTINUOUS || nbinvars > 0); 548 549 /* allocate memory for consdata */ 550 SCIP_CALL( SCIPallocBlockMemory(scip, consdata) ); 551 552 (*consdata)->linkvar = linkvar; 553 (*consdata)->nbinvars = nbinvars; 554 (*consdata)->sizebinvars = nbinvars; 555 (*consdata)->row1 = NULL; 556 (*consdata)->row2 = NULL; 557 (*consdata)->nlrow1 = NULL; 558 (*consdata)->nlrow2 = NULL; 559 (*consdata)->cliqueadded = FALSE; 560 561 /* initialize constraint state */ 562 (*consdata)->sorted = FALSE; 563 (*consdata)->firstnonfixed = 0; 564 (*consdata)->lastnonfixed = nbinvars - 1; 565 (*consdata)->nfixedzeros = 0; 566 (*consdata)->nfixedones = 0; 567 568 if( nbinvars == 0 ) 569 { 570 (*consdata)->binvars = NULL; 571 (*consdata)->vals = NULL; 572 } 573 else 574 { 575 /* copy binary variable array */ 576 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->binvars, binvars, nbinvars) ); 577 578 /* copy coefficients */ 579 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vals, vals, nbinvars) ); 580 } 581 582 /* get transformed variable, if we are in the transformed problem */ 583 if( SCIPisTransformed(scip) ) 584 { 585 if( nbinvars > 0 ) 586 { 587 SCIP_CALL( SCIPgetTransformedVars(scip, nbinvars, (*consdata)->binvars, (*consdata)->binvars) ); 588 589 /* catch bound change events of variables */ 590 SCIP_CALL( catchAllEvents(scip, *consdata, eventhdlr) ); 591 } 592 593 SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->linkvar, &(*consdata)->linkvar) ); 594 } 595 596 /* author bzfhende 597 * 598 * TODO do we need to forbid multi-aggregations? This was only needed if we substitute and resubstitute linking 599 * variables into linear constraints. 600 */ 601 602 /* capture variables */ 603 for( v = 0; v < nbinvars; ++v ) 604 { 605 assert((*consdata)->binvars[v] != NULL); 606 SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->binvars[v]) ); 607 } 608 SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->linkvar) ); 609 610 return SCIP_OKAY; 611 } 612 613 614 /** free consdata */ 615 static 616 SCIP_RETCODE consdataFree( 617 SCIP* scip, /**< SCIP data structure */ 618 SCIP_CONSDATA** consdata /**< pointer to consdata */ 619 ) 620 { 621 int v; 622 623 assert(consdata != NULL); 624 assert(*consdata != NULL); 625 assert((*consdata)->nbinvars == 0 || (*consdata)->binvars != NULL); 626 627 /* release the rows */ 628 if( (*consdata)->row1 != NULL ) 629 { 630 assert((*consdata)->row2 != NULL); 631 632 SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->row1) ); 633 SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->row2) ); 634 } 635 636 /* release the nlrows */ 637 if( (*consdata)->nlrow1 != NULL ) 638 { 639 assert((*consdata)->nlrow2 != NULL); 640 641 SCIP_CALL( SCIPreleaseNlRow(scip, &(*consdata)->nlrow1) ); 642 SCIP_CALL( SCIPreleaseNlRow(scip, &(*consdata)->nlrow2) ); 643 } 644 645 /* capture variables */ 646 for( v = 0; v < (*consdata)->nbinvars; ++v ) 647 { 648 assert((*consdata)->binvars[v] != NULL); 649 SCIP_CALL( SCIPreleaseVar(scip, &(*consdata)->binvars[v]) ); 650 } 651 SCIP_CALL( SCIPreleaseVar(scip, &(*consdata)->linkvar) ); 652 653 /* free binary variable array */ 654 if( (*consdata)->sizebinvars > 0 ) 655 { 656 /* if constraint belongs to transformed problem space, drop bound change events on variables */ 657 SCIPfreeBlockMemoryArray(scip, &(*consdata)->vals, (*consdata)->sizebinvars); 658 SCIPfreeBlockMemoryArray(scip, &(*consdata)->binvars, (*consdata)->sizebinvars); 659 } 660 661 /* check if the fixed counters are reset */ 662 assert((*consdata)->nfixedzeros == 0); 663 assert((*consdata)->nfixedones == 0); 664 665 /* free constraint data */ 666 SCIPfreeBlockMemory(scip, consdata); 667 668 return SCIP_OKAY; 669 } 670 671 672 /** analyzes conflicting assignment on given constraint where reason comes from the linking variable lower or upper 673 * bound 674 */ 675 static 676 SCIP_RETCODE analyzeConflict( 677 SCIP* scip, /**< SCIP data structure */ 678 SCIP_CONS* cons, /**< linking constraint to be processed */ 679 SCIP_VAR* linkvar, /**< linking variable */ 680 SCIP_VAR* binvar, /**< binary variable is the reason */ 681 SCIP_Bool lblinkvar, /**< lower bound of linking variable is the reason */ 682 SCIP_Bool ublinkvar /**< upper bound of linking variable is the reason */ 683 ) 684 { 685 assert(scip != NULL); 686 687 /* conflict analysis can only be applied in solving stage and if it is turned on */ 688 if( (SCIPgetStage(scip) != SCIP_STAGE_SOLVING && !SCIPinProbing(scip)) || !SCIPisConflictAnalysisApplicable(scip) ) 689 return SCIP_OKAY; 690 691 /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */ 692 SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) ); 693 694 if( lblinkvar ) 695 { 696 assert(linkvar != NULL); 697 SCIP_CALL( SCIPaddConflictLb(scip, linkvar, NULL) ); 698 } 699 700 if( ublinkvar ) 701 { 702 assert(linkvar != NULL); 703 SCIP_CALL( SCIPaddConflictUb(scip, linkvar, NULL) ); 704 } 705 706 if( binvar != NULL ) 707 { 708 SCIP_CALL( SCIPaddConflictBinvar(scip, binvar) ); 709 } 710 711 /* analyze the conflict */ 712 SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) ); 713 714 return SCIP_OKAY; 715 } 716 717 /* author bzfhende 718 * 719 * TODO check if the method below produces valid results even if the variable is continuous 720 */ 721 722 /** fix linking variable to the value of the binary variable at pos */ 723 static 724 SCIP_RETCODE consFixLinkvar( 725 SCIP* scip, /**< SCIP data structure */ 726 SCIP_CONS* cons, /**< linking constraint to be processed */ 727 int pos, /**< position of binary variable */ 728 SCIP_Bool* cutoff /**< pointer to store TRUE, if the node can be cut off */ 729 ) 730 { 731 SCIP_CONSDATA* consdata; 732 SCIP_VAR* linkvar; 733 SCIP_Bool infeasible; 734 SCIP_Bool tightened; 735 SCIP_Real coef; 736 737 consdata = SCIPconsGetData(cons); 738 assert(consdata != NULL); 739 740 linkvar = consdata->linkvar; 741 coef = consdata->vals[pos]; 742 743 /* change lower bound of the linking variable */ 744 SCIP_CALL( SCIPinferVarLbCons(scip, linkvar, coef, cons, pos, TRUE, &infeasible, &tightened) ); 745 746 if( infeasible ) 747 { 748 assert(coef > SCIPvarGetUbLocal(linkvar)); 749 assert(coef >= SCIPvarGetLbLocal(linkvar)); 750 751 SCIP_CALL( analyzeConflict(scip, cons, linkvar, consdata->binvars[pos], FALSE, TRUE) ); 752 753 *cutoff = TRUE; 754 return SCIP_OKAY; 755 } 756 assert(SCIPisFeasLE(scip, coef, SCIPvarGetUbLocal(linkvar))); 757 758 /* change upper bound of the integer variable */ 759 SCIP_CALL( SCIPinferVarUbCons(scip, linkvar, coef, cons, pos, TRUE, &infeasible, &tightened) ); 760 761 if( infeasible ) 762 { 763 assert(coef < SCIPvarGetLbLocal(linkvar)); 764 assert(coef <= SCIPvarGetUbLocal(linkvar)); 765 766 SCIP_CALL( analyzeConflict(scip, cons, linkvar, consdata->binvars[pos], TRUE, FALSE) ); 767 768 *cutoff = TRUE; 769 return SCIP_OKAY; 770 } 771 772 assert(SCIPisFeasEQ(scip, SCIPvarGetUbLocal(linkvar), SCIPvarGetLbLocal(linkvar))); 773 774 return SCIP_OKAY; 775 } 776 777 /** checks constraint for violation from the local bound of the linking variable, applies fixings to the binary 778 * variables if possible 779 */ 780 static 781 SCIP_RETCODE processRealBoundChg( 782 SCIP* scip, /**< SCIP data structure */ 783 SCIP_CONS* cons, /**< linking constraint to be processed */ 784 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */ 785 int* nchgbds, /**< pointer to store the number of changes (foxed) variable bounds */ 786 SCIP_Bool* mustcheck /**< pointer to store whether this constraint must be checked for feasibility */ 787 ) 788 { 789 SCIP_CONSDATA* consdata; 790 SCIP_VAR** binvars; 791 SCIP_VAR* linkvar; 792 SCIP_Real* vals; 793 SCIP_Real lb; 794 SCIP_Real ub; 795 int nbinvars; 796 int b; 797 SCIP_Bool infeasible; 798 SCIP_Bool tightened; 799 800 assert(cons != NULL); 801 assert(SCIPconsGetHdlr(cons) != NULL); 802 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0); 803 assert(cutoff != NULL); 804 assert(nchgbds != NULL); 805 assert(mustcheck != NULL); 806 807 consdata = SCIPconsGetData(cons); 808 assert(consdata != NULL); 809 810 /* ensure that the binary variables are sorted in non-decreasing order w.r.t. their coefficients */ 811 consdataSort(consdata); 812 813 nbinvars = consdata->nbinvars; 814 815 /* in case there is only at most one binary variables, the constraints should already be disabled */ 816 assert(nbinvars > 1); 817 818 /* if more than one binary variable is fixed to one or at least nbinvars minus one variable are fixed to zero */ 819 if( consdata->nfixedones > 0 || consdata->nfixedzeros >= nbinvars-1 ) 820 return SCIP_OKAY; 821 822 linkvar = consdata->linkvar; 823 assert(linkvar != NULL); 824 825 binvars = consdata->binvars; 826 vals = consdata->vals; 827 828 lb = SCIPvarGetLbLocal(linkvar); 829 ub = SCIPvarGetUbLocal(linkvar); 830 831 assert(lb <= ub); 832 833 #ifndef NDEBUG 834 /* check that the first variable are locally fixed to zero */ 835 for( b = 0; b < consdata->firstnonfixed; ++b ) 836 assert(SCIPvarGetUbLocal(binvars[b]) < 0.5); 837 838 /* check that the last variable are locally fixed to zero */ 839 for( b = consdata->lastnonfixed + 1; b < nbinvars; ++b ) 840 assert(SCIPvarGetUbLocal(binvars[b]) < 0.5); 841 #endif 842 843 for( b = consdata->firstnonfixed; b < nbinvars; ++b ) 844 { 845 if( SCIPisLT(scip, vals[b], lb) ) 846 { 847 SCIP_VAR* var; 848 849 var = binvars[b]; 850 assert(var != NULL); 851 852 SCIPdebugMsg(scip, "fix variable <%s> to zero due to the lower bound of the linking variable <%s> [%g,%g]\n", 853 SCIPvarGetName(var), SCIPvarGetName(linkvar), lb, ub); 854 855 SCIP_CALL( SCIPinferBinvarCons(scip, var, FALSE, cons, -2, &infeasible, &tightened) ); 856 857 if( infeasible ) 858 { 859 SCIP_CALL( analyzeConflict(scip, cons, linkvar, var, TRUE, FALSE) ); 860 *cutoff = TRUE; 861 return SCIP_OKAY; 862 } 863 864 if( tightened ) 865 (*nchgbds)++; 866 867 /* adjust constraint state */ 868 consdata->firstnonfixed++; 869 } 870 else 871 break; 872 } 873 874 /* fix binary variables to zero if not yet fixed, from local upper bound + 1*/ 875 for( b = consdata->lastnonfixed; b >= 0; --b ) 876 { 877 if( SCIPisGT(scip, vals[b], ub) ) 878 { 879 SCIP_VAR* var; 880 881 var = binvars[b]; 882 assert(var != NULL); 883 884 SCIPdebugMsg(scip, "fix variable <%s> to zero due to the upper bound of the linking variable <%s> [%g,%g]\n", 885 SCIPvarGetName(var), SCIPvarGetName(linkvar), lb, ub); 886 887 SCIP_CALL( SCIPinferBinvarCons(scip, var, FALSE, cons, -3, &infeasible, &tightened) ); 888 889 if( infeasible ) 890 { 891 SCIP_CALL( analyzeConflict(scip, cons, linkvar, var, FALSE, TRUE) ); 892 *cutoff = TRUE; 893 return SCIP_OKAY; 894 } 895 896 if( tightened ) 897 (*nchgbds)++; 898 899 /* adjust constraint state */ 900 consdata->lastnonfixed--; 901 } 902 else 903 break; 904 } 905 906 if( consdata->firstnonfixed > consdata->lastnonfixed ) 907 { 908 *cutoff = TRUE; 909 return SCIP_OKAY; 910 } 911 912 *mustcheck = (*nchgbds) == 0; 913 914 /* if linking variable is fixed, create for the binary variables which have a coefficient equal to the fixed value a 915 * set partitioning constraint 916 */ 917 if( SCIPisEQ(scip, lb, ub) ) 918 { 919 if( consdata->firstnonfixed == consdata->lastnonfixed ) 920 { 921 SCIP_VAR* var; 922 923 var = binvars[consdata->firstnonfixed]; 924 925 SCIPdebugMsg(scip, "fix variable <%s> to one due to the fixed linking variable <%s> [%g,%g]\n", 926 SCIPvarGetName(var), SCIPvarGetName(linkvar), lb, ub); 927 928 /* TODO can the forbidden cases be covered more elegantly? */ 929 if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR ) 930 return SCIP_OKAY; 931 932 if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_AGGREGATED ) 933 if( SCIPvarGetStatus(SCIPvarGetAggrVar(var)) == SCIP_VARSTATUS_MULTAGGR || 934 SCIPvarGetStatus(SCIPvarGetAggrVar(var)) == SCIP_VARSTATUS_AGGREGATED ) 935 return SCIP_OKAY; 936 937 SCIP_CALL( SCIPinferBinvarCons(scip, var, TRUE, cons, -6, &infeasible, &tightened) ); 938 939 if( infeasible ) 940 { 941 SCIP_CALL( analyzeConflict(scip, cons, linkvar, var, TRUE, TRUE) ); 942 *cutoff = TRUE; 943 return SCIP_OKAY; 944 } 945 946 if( tightened ) 947 (*nchgbds)++; 948 949 SCIPdebugMsg(scip, " -> disabling linking constraint <%s>\n", SCIPconsGetName(cons)); 950 SCIP_CALL( SCIPdelConsLocal(scip, cons) ); 951 952 *mustcheck = FALSE; 953 } 954 else if( SCIPgetDepth(scip) <= 0 ) 955 { 956 SCIP_CONS* setppc; 957 SCIP_VAR** vars; 958 int nvars; 959 960 /* get sub array of variables which have the same coefficient */ 961 vars = &consdata->binvars[consdata->firstnonfixed]; 962 nvars = consdata->lastnonfixed - consdata->firstnonfixed + 1; 963 964 SCIP_CALL( SCIPcreateConsSetpart(scip, &setppc, SCIPconsGetName(cons), nvars, vars, 965 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons), SCIPconsIsChecked(cons), 966 SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), 967 SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) ); 968 969 SCIP_CALL( SCIPaddCons(scip, setppc) ); 970 SCIP_CALL( SCIPreleaseCons(scip, &setppc) ); 971 972 SCIP_CALL( SCIPdelConsLocal(scip, cons) ); 973 } 974 } 975 976 return SCIP_OKAY; 977 } 978 979 /** deletes coefficient at given position from the binary variable array */ 980 static 981 SCIP_RETCODE delCoefPos( 982 SCIP* scip, /**< SCIP data structure */ 983 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */ 984 SCIP_CONS* cons, /**< linking constraint */ 985 int pos /**< position of coefficient to delete */ 986 ) 987 { 988 SCIP_CONSDATA* consdata; 989 SCIP_VAR* var; 990 991 assert(scip != NULL); 992 assert(eventhdlr != NULL); 993 994 consdata = SCIPconsGetData(cons); 995 assert(consdata != NULL); 996 assert(0 <= pos && pos < consdata->nbinvars); 997 998 var = consdata->binvars[pos]; 999 assert(var != NULL); 1000 assert(SCIPconsIsTransformed(cons) == SCIPvarIsTransformed(var)); 1001 1002 /* remove the rounding locks for the deleted variable */ 1003 SCIP_CALL( SCIPunlockVarCons(scip, var, cons, TRUE, TRUE) ); 1004 1005 /* if we are in transformed problem, delete the event data of the variable */ 1006 if( SCIPconsIsTransformed(cons) ) 1007 { 1008 SCIP_CONSHDLR* conshdlr; 1009 SCIP_CONSHDLRDATA* conshdlrdata; 1010 1011 /* get event handler */ 1012 conshdlr = SCIPconsGetHdlr(cons); 1013 conshdlrdata = SCIPconshdlrGetData(conshdlr); 1014 assert(conshdlrdata != NULL); 1015 assert(conshdlrdata->eventhdlr != NULL); 1016 1017 /* drop bound change events of variable */ 1018 SCIP_CALL( dropEvent(scip, consdata, conshdlrdata->eventhdlr, pos) ); 1019 } 1020 1021 /* move the last variable to the free slot */ 1022 if( pos != consdata->nbinvars - 1 ) 1023 { 1024 consdata->binvars[pos] = consdata->binvars[consdata->nbinvars-1]; 1025 consdata->vals[pos] = consdata->vals[consdata->nbinvars-1]; 1026 consdata->sorted = FALSE; 1027 } 1028 1029 consdata->nbinvars--; 1030 1031 /* release variable */ 1032 SCIP_CALL( SCIPreleaseVar(scip, &var) ); 1033 1034 return SCIP_OKAY; 1035 } 1036 1037 /** remove the trailing and leading binary variables that are fixed to zero */ 1038 static 1039 SCIP_RETCODE removeFixedBinvars( 1040 SCIP* scip, /**< SCIP data structure */ 1041 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */ 1042 SCIP_CONS* cons /**< linking constraint */ 1043 ) 1044 { 1045 SCIP_CONSDATA* consdata; 1046 int nbinvars; 1047 int b; 1048 1049 consdata = SCIPconsGetData(cons); 1050 assert(consdata != NULL); 1051 assert(consdata->sorted); 1052 1053 assert(SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING || SCIPgetDepth(scip) <= 0); 1054 assert(!SCIPinProbing(scip)); 1055 assert(!SCIPinRepropagation(scip)); 1056 1057 nbinvars = consdata->nbinvars; 1058 1059 for( b = nbinvars - 1; b > consdata->lastnonfixed; --b ) 1060 { 1061 SCIP_CALL( delCoefPos(scip, eventhdlr, cons, b) ); 1062 } 1063 1064 for( b = consdata->firstnonfixed - 1; b >= 0; --b ) 1065 { 1066 SCIP_CALL( delCoefPos(scip, eventhdlr, cons, b) ); 1067 } 1068 1069 for( b = consdata->nbinvars - 1; b >= 0; --b ) 1070 { 1071 if( SCIPvarGetUbLocal(consdata->binvars[b]) < 0.5 ) 1072 { 1073 SCIP_CALL( delCoefPos(scip, eventhdlr, cons, b) ); 1074 } 1075 } 1076 1077 /* set the constraint state */ 1078 consdata->firstnonfixed = 0; 1079 consdata->lastnonfixed = consdata->nbinvars - 1; 1080 1081 return SCIP_OKAY; 1082 } 1083 1084 /** tightened the linking variable due to binary variables which are fixed to zero */ 1085 static 1086 SCIP_RETCODE tightenedLinkvar( 1087 SCIP* scip, /**< SCIP data structure */ 1088 SCIP_CONS* cons, /**< linking constraint to be processed */ 1089 SCIP_CONSDATA* consdata, /**< linking constraint to be processed */ 1090 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */ 1091 int* nchgbds /**< pointer to store the number of changed variable bounds */ 1092 ) 1093 { 1094 SCIP_VAR** binvars; 1095 SCIP_VAR* linkvar; 1096 SCIP_Real* vals; 1097 1098 SCIP_Bool infeasible; 1099 SCIP_Bool tightened; 1100 int nbinvars; 1101 int b; 1102 1103 /* if more than one binary variable is fixed to one or at least nbinvars minus one variable are fixed to zero return */ 1104 if( consdata->nfixedones > 1 || consdata->nfixedzeros >= consdata->nbinvars-1 ) 1105 return SCIP_OKAY; 1106 1107 if( *cutoff ) 1108 return SCIP_OKAY; 1109 1110 assert(consdata->sorted); 1111 1112 linkvar = consdata->linkvar; 1113 binvars = consdata->binvars; 1114 vals = consdata->vals; 1115 nbinvars = consdata->nbinvars; 1116 1117 #ifndef NDEBUG 1118 /* check that the first variable are locally fixed to zero */ 1119 for( b = 0; b < consdata->firstnonfixed; ++b ) 1120 assert(SCIPvarGetUbLocal(binvars[b]) < 0.5); 1121 #endif 1122 1123 assert(consdata->firstnonfixed < nbinvars); 1124 assert(consdata->lastnonfixed < nbinvars); 1125 1126 /* find first non fixed binary variable */ 1127 for( b = consdata->firstnonfixed; b < nbinvars; ++b ) 1128 { 1129 if( SCIPvarGetUbLocal(binvars[b]) > 0.5 ) 1130 break; 1131 1132 consdata->firstnonfixed++; 1133 } 1134 1135 SCIP_CALL( SCIPinferVarLbCons(scip, linkvar, vals[b], cons, -4, TRUE, &infeasible, &tightened) ); 1136 1137 /* start conflict analysis if infeasible */ 1138 if( infeasible ) 1139 { 1140 /* analyze the cutoff if if SOLVING stage and conflict analysis is turned on */ 1141 if( (SCIPgetStage(scip) == SCIP_STAGE_SOLVING && !SCIPinProbing(scip)) && SCIPisConflictAnalysisApplicable(scip) ) 1142 { 1143 SCIPdebugMsg(scip, "conflict at <%s> due to bounds and fixed binvars: [lb,ub] = [%g,%g]; b= %d; coef = %g \n", 1144 SCIPvarGetName(linkvar), SCIPvarGetLbLocal(linkvar), SCIPvarGetUbLocal(linkvar), b, vals[b]); 1145 1146 SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) ); 1147 1148 /* ??????????? use resolve method and only add binvars which are needed to exceed the upper bound */ 1149 1150 /* add conflicting variables */ 1151 SCIP_CALL( SCIPaddConflictUb(scip, linkvar, NULL) ); 1152 1153 for( b = 0; b < consdata->firstnonfixed; ++b ) 1154 { 1155 SCIP_CALL( SCIPaddConflictBinvar(scip, binvars[b]) ); 1156 } 1157 1158 /* analyze the conflict */ 1159 SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) ); 1160 } 1161 1162 *cutoff = TRUE; 1163 return SCIP_OKAY; 1164 } 1165 1166 if( tightened ) 1167 (*nchgbds)++; 1168 1169 #ifndef NDEBUG 1170 /* check that the last variable are locally fixed to zero */ 1171 for( b = consdata->lastnonfixed + 1; b < nbinvars; ++b ) 1172 assert(SCIPvarGetUbLocal(binvars[b]) < 0.5); 1173 #endif 1174 1175 /* find last non fixed variable */ 1176 for( b = consdata->lastnonfixed; b >= 0; --b ) 1177 { 1178 if( SCIPvarGetUbLocal(binvars[b]) > 0.5 ) 1179 break; 1180 1181 consdata->lastnonfixed--; 1182 } 1183 1184 if( SCIPvarGetStatus(SCIPvarGetProbvar(linkvar)) != SCIP_VARSTATUS_MULTAGGR ) 1185 SCIP_CALL( SCIPinferVarUbCons(scip, linkvar, (SCIP_Real)vals[b], cons, -5, TRUE, &infeasible, &tightened) ); 1186 1187 if( infeasible ) 1188 { 1189 /* conflict analysis can only be applied in solving stage and if conflict analysis is turned on */ 1190 if( (SCIPgetStage(scip) == SCIP_STAGE_SOLVING && !SCIPinProbing(scip)) && SCIPisConflictAnalysisApplicable(scip) ) 1191 { 1192 SCIPdebugMsg(scip, "conflict at <%s> due to bounds and fixed binvars: [lb,ub] = [%g,%g]; b = %d; coef = %g,\n", 1193 SCIPvarGetName(linkvar), SCIPvarGetLbLocal(linkvar), SCIPvarGetUbLocal(linkvar), b, vals[b]); 1194 1195 SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) ); 1196 1197 /* ??????????? use resolve method and only add binvars which are needed to fall below the lower bound */ 1198 1199 /* add conflicting variables */ 1200 SCIP_CALL( SCIPaddConflictLb(scip, linkvar, NULL) ); 1201 1202 for( b = consdata->lastnonfixed + 1; b < nbinvars; ++b ) 1203 { 1204 SCIP_CALL( SCIPaddConflictBinvar(scip, binvars[b]) ); 1205 } 1206 1207 /* analyze the conflict */ 1208 SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) ); 1209 } 1210 1211 *cutoff = TRUE; 1212 return SCIP_OKAY; 1213 } 1214 1215 if( tightened ) 1216 (*nchgbds)++; 1217 1218 return SCIP_OKAY; 1219 } 1220 1221 /** checks constraint for violation only looking at the fixed binary variables, applies further fixings if possible */ 1222 static 1223 SCIP_RETCODE processBinvarFixings( 1224 SCIP* scip, /**< SCIP data structure */ 1225 SCIP_CONS* cons, /**< linking constraint to be processed */ 1226 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */ 1227 int* nchgbds, /**< pointer to store the number of changed variable bounds */ 1228 SCIP_Bool* addcut, /**< pointer to store whether this constraint must be added as a cut */ 1229 SCIP_Bool* mustcheck /**< pointer to store whether this constraint must be checked for feasibility */ 1230 ) 1231 { 1232 SCIP_CONSDATA* consdata; 1233 SCIP_Bool infeasible; 1234 SCIP_Bool tightened; 1235 1236 assert(cons != NULL); 1237 assert(SCIPconsGetHdlr(cons) != NULL); 1238 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0); 1239 assert(cutoff != NULL); 1240 assert(nchgbds != NULL); 1241 assert(addcut != NULL); 1242 assert(mustcheck != NULL); 1243 1244 consdata = SCIPconsGetData(cons); 1245 assert(consdata != NULL); 1246 assert(consdata->nbinvars == 0 || consdata->binvars != NULL); 1247 assert(0 <= consdata->nfixedzeros && consdata->nfixedzeros <= consdata->nbinvars); 1248 assert(0 <= consdata->nfixedones && consdata->nfixedones <= consdata->nbinvars); 1249 1250 /* ensure that the binary variables are sorted in non-decreasing order w.r.t. their coefficients */ 1251 consdataSort(consdata); 1252 1253 /* in case there is only at most one binary variables, the constraints should already be disabled */ 1254 assert(consdata->nbinvars > 1); 1255 1256 if( *cutoff ) 1257 return SCIP_OKAY; 1258 1259 if( consdata->nfixedones == 1 ) 1260 { 1261 /* exactly one variable is fixed to 1: 1262 * - all other binary variables in a set partitioning must be zero 1263 * - linking variable is fixed to that binary variable 1264 */ 1265 if( consdata->nfixedzeros < consdata->nbinvars - 1 || 1266 SCIPisLT(scip, SCIPvarGetLbLocal(consdata->linkvar), SCIPvarGetUbLocal(consdata->linkvar)) ) 1267 { 1268 SCIP_VAR** vars; 1269 SCIP_VAR* var; 1270 #ifndef NDEBUG 1271 SCIP_Bool fixedonefound; 1272 #endif 1273 int nvars; 1274 int v; 1275 1276 SCIPdebugMsg(scip, " -> fixing all other variables to zero due to the set partitioning condition <%s>\n", 1277 SCIPconsGetName(cons)); 1278 1279 /* unfixed variables exist: fix them to zero; 1280 * this could result in additional variables fixed to one due to aggregations; in this case, the 1281 * constraint is infeasible in local bounds 1282 */ 1283 vars = consdata->binvars; 1284 nvars = consdata->nbinvars; 1285 #ifndef NDEBUG 1286 fixedonefound = FALSE; 1287 #endif 1288 1289 for( v = 0; v < nvars && consdata->nfixedones == 1 && !(*cutoff); ++v ) 1290 { 1291 var = vars[v]; 1292 assert(SCIPvarIsBinary(var)); 1293 /* TODO can this be handled more elegantly? */ 1294 if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR ) 1295 continue; 1296 1297 if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_AGGREGATED ) 1298 if( SCIPvarGetStatus(SCIPvarGetAggrVar(var)) == SCIP_VARSTATUS_MULTAGGR || 1299 SCIPvarGetStatus(SCIPvarGetAggrVar(var)) == SCIP_VARSTATUS_AGGREGATED ) 1300 continue; 1301 1302 if( SCIPvarGetLbLocal(var) < 0.5 ) 1303 { 1304 SCIP_CALL( SCIPinferBinvarCons(scip, var, FALSE, cons, -1, &infeasible, &tightened) ); 1305 assert(!infeasible); 1306 SCIPdebugMsg(scip, " -> fixed <%s> to zero (tightened=%u)\n", SCIPvarGetName(var), tightened); 1307 } 1308 else 1309 { 1310 #ifndef NDEBUG 1311 fixedonefound = TRUE; 1312 #endif 1313 /* fix linking variable */ 1314 /* TODO check if variable status allows fixing (probably in consFixLinkvar) */ 1315 SCIP_CALL( consFixLinkvar(scip, cons, v, cutoff) ); 1316 } 1317 } 1318 if( !(*cutoff) ) 1319 { 1320 /* the fixed to one variable must have been found, and at least one variable must have been fixed */ 1321 assert(consdata->nfixedones >= 1 || fixedonefound); 1322 1323 SCIP_CALL( SCIPresetConsAge(scip, cons) ); 1324 (*nchgbds)++; 1325 } 1326 } 1327 1328 /* now all other variables are fixed to zero: 1329 * the constraint is feasible, and if it's not modifiable, it is redundant 1330 */ 1331 if( !SCIPconsIsModifiable(cons) && consdata->nfixedones == 1 ) 1332 { 1333 SCIPdebugMsg(scip, " -> disabling set linking constraint <%s>\n", SCIPconsGetName(cons)); 1334 SCIP_CALL( SCIPdelConsLocal(scip, cons) ); 1335 } 1336 } 1337 else if( consdata->nfixedones >= 2 ) 1338 { 1339 /* at least two variables are fixed to 1: 1340 * - the set partitioning condition is violated 1341 */ 1342 SCIPdebugMsg(scip, " -> conflict on " CONSHDLR_NAME " constraint <%s> due to the set partitioning condition\n", SCIPconsGetName(cons)); 1343 1344 SCIP_CALL( SCIPresetConsAge(scip, cons) ); 1345 1346 /* conflict analysis can only be applied in solving stage and if it is applicable */ 1347 if( (SCIPgetStage(scip) == SCIP_STAGE_SOLVING && !SCIPinProbing(scip)) && SCIPisConflictAnalysisApplicable(scip) ) 1348 { 1349 SCIP_VAR** vars; 1350 int nvars; 1351 int n; 1352 int v; 1353 1354 vars = consdata->binvars; 1355 nvars = consdata->nbinvars; 1356 1357 /* initialize conflict analysis, and add the two variables assigned to one to conflict candidate queue */ 1358 SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) ); 1359 1360 n = 0; 1361 1362 for( v = 0; v < nvars && n < 2; ++v ) 1363 { 1364 if( SCIPvarGetLbLocal(vars[v]) > 0.5 ) 1365 { 1366 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[v]) ); 1367 n++; 1368 } 1369 } 1370 assert(n == 2); 1371 1372 /* analyze the conflict */ 1373 SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) ); 1374 } 1375 1376 *cutoff = TRUE; 1377 } 1378 else if( consdata->nfixedzeros == consdata->nbinvars ) 1379 { 1380 /* all variables are fixed to zero: 1381 * - the set partitioning condition is violated, and if it's unmodifiable, the node 1382 * can be cut off -- otherwise, the constraint must be added as a cut and further pricing must 1383 * be performed 1384 */ 1385 assert(consdata->nfixedones == 0); 1386 1387 SCIPdebugMsg(scip, " -> " CONSHDLR_NAME " constraint <%s> is infeasible due to the set partitioning condition\n", 1388 SCIPconsGetName(cons)); 1389 1390 SCIP_CALL( SCIPresetConsAge(scip, cons) ); 1391 if( SCIPconsIsModifiable(cons) ) 1392 *addcut = TRUE; 1393 else 1394 { 1395 /* conflict analysis can only be applied in solving stage and if it is applicable */ 1396 if( (SCIPgetStage(scip) == SCIP_STAGE_SOLVING && !SCIPinProbing(scip)) && SCIPisConflictAnalysisApplicable(scip) ) 1397 { 1398 SCIP_VAR** vars; 1399 int nvars; 1400 int v; 1401 1402 vars = consdata->binvars; 1403 nvars = consdata->nbinvars; 1404 1405 /* initialize conflict analysis, add all variables of infeasible constraint to conflict candidate queue */ 1406 SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) ); 1407 1408 for( v = 0; v < nvars; ++v ) 1409 { 1410 assert(SCIPvarGetUbLocal(vars[v]) < 0.5); 1411 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[v]) ); 1412 } 1413 1414 /* analyze the conflict */ 1415 SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) ); 1416 } 1417 *cutoff = TRUE; 1418 } 1419 } 1420 else if( consdata->nfixedzeros == consdata->nbinvars - 1 ) 1421 { 1422 /* all variables except one are fixed to zero: 1423 * - an unmodifiable set partitioning constraint is feasible and can be disabled after the 1424 * remaining variable is fixed to one 1425 * - a modifiable set partitioning constraint must be checked manually 1426 */ 1427 assert(consdata->nfixedones == 0); 1428 1429 if( !SCIPconsIsModifiable(cons) ) 1430 { 1431 SCIP_VAR** vars; 1432 SCIP_VAR* var; 1433 int nvars; 1434 int v; 1435 1436 /* search the single variable that can be fixed */ 1437 vars = consdata->binvars; 1438 nvars = consdata->nbinvars; 1439 for( v = 0; v < nvars && !(*cutoff); ++v ) 1440 { 1441 var = vars[v]; 1442 assert(SCIPisFeasZero(scip, SCIPvarGetLbLocal(var))); 1443 assert(SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) || SCIPisFeasEQ(scip, SCIPvarGetUbLocal(var), 1.0)); 1444 1445 if( SCIPvarGetUbLocal(var) > 0.5 ) 1446 { 1447 assert(SCIPvarGetLbLocal(var) < 0.5); 1448 SCIPdebugMsg(scip, " -> fixing remaining binary variable <%s> to one in " CONSHDLR_NAME " constraint <%s>\n", 1449 SCIPvarGetName(var), SCIPconsGetName(cons)); 1450 1451 if( SCIPvarGetStatus(SCIPvarGetProbvar(var)) != SCIP_VARSTATUS_MULTAGGR ) 1452 { 1453 SCIP_CALL( SCIPinferBinvarCons(scip, var, TRUE, cons, -1, &infeasible, &tightened) ); 1454 assert(!infeasible); 1455 assert(tightened); 1456 } 1457 1458 /* fix linking variable */ 1459 /* TODO check if variable status allows fixing (probably in consFixLinkvar)*/ 1460 SCIP_CALL( consFixLinkvar(scip, cons, v, cutoff) ); 1461 break; 1462 } 1463 } 1464 assert(v < nvars); 1465 assert(consdata->nfixedzeros == consdata->nbinvars - 1); 1466 assert(consdata->nfixedones == 1); 1467 1468 SCIP_CALL( SCIPdelConsLocal(scip, cons) ); 1469 (*nchgbds)++; 1470 } 1471 } 1472 else 1473 { 1474 SCIP_CALL( tightenedLinkvar(scip, cons, consdata, cutoff, nchgbds) ); 1475 } 1476 1477 *mustcheck = (*nchgbds) == 0; 1478 1479 assert(consdata->nfixedzeros + consdata->nfixedones <= consdata->nbinvars); 1480 1481 return SCIP_OKAY; 1482 } 1483 1484 /** returns whether the given solution is feasible for the given linking constraint */ 1485 static 1486 SCIP_Bool checkCons( 1487 SCIP* scip, /**< SCIP data structure */ 1488 SCIP_CONS* cons, /**< linking constraint to be checked */ 1489 SCIP_SOL* sol /**< primal solution, or NULL for current LP/pseudo solution */ 1490 ) 1491 { 1492 SCIP_CONSDATA* consdata; 1493 SCIP_VAR** binvars; 1494 SCIP_Real* vals; 1495 SCIP_Real solval; 1496 SCIP_Real linksum; 1497 SCIP_Real linkvarval; 1498 SCIP_Real setpartsum; 1499 SCIP_Real setpartsumbound; 1500 SCIP_Real absviol; 1501 SCIP_Real relviol; 1502 int nbinvars; 1503 int b; 1504 1505 assert(scip != NULL); 1506 assert(cons != NULL); 1507 1508 SCIPdebugMsg(scip, "checking linking constraint <%s> for feasibility of solution %p\n", SCIPconsGetName(cons), (void*)sol); 1509 1510 consdata = SCIPconsGetData(cons); 1511 assert(consdata != NULL); 1512 assert(consdata->binvars != NULL || consdata->nbinvars == 0); 1513 1514 /* in case there is only at most one binary variables, the constraints should already be disabled */ 1515 assert(consdata->nbinvars > 1); 1516 1517 /* calculate the constraint's activity for the linking part and the set partitioning part */ 1518 binvars = consdata->binvars; 1519 vals = consdata->vals; 1520 nbinvars = consdata->nbinvars; 1521 1522 linksum = 0.0; 1523 setpartsum = 0.0; 1524 setpartsumbound = 1.0 + 2*SCIPfeastol(scip); 1525 1526 for( b = 0; b < nbinvars && setpartsum < setpartsumbound; ++b ) /* if sum >= sumbound, the feasibility is clearly decided */ 1527 { 1528 assert(SCIPvarIsBinary(binvars[b])); 1529 1530 solval = SCIPgetSolVal(scip, sol, binvars[b]); 1531 assert(SCIPisFeasGE(scip, solval, 0.0) && SCIPisFeasLE(scip, solval, 1.0)); 1532 1533 linksum += vals[b] * solval; 1534 setpartsum += solval; 1535 } 1536 1537 /* calculate and update absolute and relative violation of the equality constraint */ 1538 linkvarval = SCIPgetSolVal(scip, sol, consdata->linkvar); 1539 absviol = REALABS(linksum - linkvarval); 1540 relviol = REALABS(SCIPrelDiff(linksum, linkvarval)); 1541 if( sol != NULL ) 1542 SCIPupdateSolLPConsViolation(scip, sol, absviol, relviol); 1543 1544 /* calculate and update absolute and relative violation of the set partitioning constraint */ 1545 absviol = REALABS(setpartsum - 1.0); 1546 relviol = REALABS(SCIPrelDiff(setpartsum, 1.0)); 1547 if( sol != NULL ) 1548 SCIPupdateSolLPConsViolation(scip, sol, absviol, relviol); 1549 1550 /* check if the fixed binary variable match with the linking variable */ 1551 return SCIPisFeasEQ(scip, linksum, linkvarval) && SCIPisFeasEQ(scip, setpartsum, 1.0); 1552 } 1553 1554 #if 0 1555 /** transfer aggregated integer variables to the corresponding binary variables */ 1556 static 1557 SCIP_RETCODE aggregateVariables( 1558 SCIP* scip, /**< SCIP data structure */ 1559 SCIP_HASHMAP* varmap, /**< hash map mapping a integer variables to its linking constraint */ 1560 SCIP_CONS** conss, /**< array of linking constraint */ 1561 int nconss, /**< number of linking constraints */ 1562 int* naggrvars, /**< pointer to store the number of aggregate variables */ 1563 SCIP_Bool* cutoff /**< pointer to store if a cutoff was detected */ 1564 ) 1565 { 1566 SCIP_CONS* aggrcons; 1567 SCIP_CONSDATA* aggrconsdata; 1568 SCIP_CONSDATA* consdata; 1569 SCIP_VAR** binvars; 1570 SCIP_VAR** aggrbinvars; 1571 SCIP_VAR* linkvar; 1572 SCIP_VAR* aggrvar; 1573 SCIP_Real aggrconst; 1574 SCIP_Real aggrscalar; 1575 SCIP_Bool infeasible; 1576 SCIP_Bool redundant; 1577 SCIP_Bool aggregated; 1578 int offset; 1579 int aggroffset; 1580 int nbinvars; 1581 int shift; 1582 int b; 1583 int c; 1584 1585 assert(varmap != NULL); 1586 1587 for( c = 0; c < nconss; ++c ) 1588 { 1589 consdata = SCIPconsGetData(conss[c]); 1590 assert(consdata != NULL); 1591 1592 linkvar = consdata->linkvar; 1593 assert(linkvar != NULL); 1594 1595 if( SCIPvarGetStatus(linkvar) == SCIP_VARSTATUS_AGGREGATED ) 1596 { 1597 aggrvar = SCIPvarGetAggrVar(linkvar); 1598 aggrcons = (SCIP_CONS*) SCIPhashmapGetImage(varmap, getHashmapKey(aggrvar)); 1599 1600 /* check if the aggregate variable belongs to a linking constraint */ 1601 if( aggrcons != NULL ) 1602 { 1603 aggrconsdata = SCIPconsGetData(aggrcons); 1604 assert(aggrconsdata != NULL); 1605 1606 aggrconst = SCIPvarGetAggrConstant(linkvar); 1607 aggrscalar = SCIPvarGetAggrScalar(linkvar); 1608 1609 /**@todo extend the aggregation for those cases were the aggrscalar is not equal to 1.0 */ 1610 if( SCIPisEQ(scip, aggrscalar, 1.0 ) ) 1611 { 1612 /* since both variables are integer variable and the aggrscalar is 1.0 the aggrconst should 1613 * integral 1614 */ 1615 assert(SCIPisIntegral(scip, aggrconst)); 1616 shift = SCIPconvertRealToInt(scip, aggrconst); 1617 1618 offset = consdata->offset; 1619 binvars = consdata->binvars; 1620 aggroffset = aggrconsdata->offset; 1621 aggrbinvars = aggrconsdata->binvars; 1622 1623 nbinvars = MIN(consdata->nbinvars + offset, aggrconsdata->nbinvars + shift + aggroffset); 1624 1625 for( b = MAX(offset, aggroffset-shift); b < nbinvars; ++b ) 1626 { 1627 assert(b - offset >= 0); 1628 assert(b + shift - aggroffset >= 0); 1629 assert(b < consdata->nbinvars); 1630 assert(b < aggrconsdata->nbinvars - shift); 1631 1632 /* add aggregation x - y = 0.0 */ 1633 SCIP_CALL( SCIPaggregateVars(scip, binvars[b-offset], aggrbinvars[b+shift-aggroffset], 1.0, -1.0, 0.0, 1634 &infeasible, &redundant, &aggregated) ); 1635 1636 if( infeasible ) 1637 { 1638 (*cutoff) = TRUE; 1639 return SCIP_OKAY; 1640 } 1641 1642 if( aggregated ) 1643 (*naggrvars)++; 1644 } 1645 } 1646 } 1647 } 1648 } 1649 return SCIP_OKAY; 1650 } 1651 #endif 1652 1653 /** create two rows for the linking constraint 1654 * 1655 * - row1: {sum_{b=1}^n-1 vals[b] * binvars[b]} - linkvar = 0 1656 * - row2: {sum_{b=0}^n-1 binvars[b]} = 1.0 1657 */ 1658 static 1659 SCIP_RETCODE createRows( 1660 SCIP* scip, /**< SCIP data structure */ 1661 SCIP_CONS* cons /**< linking constraint */ 1662 ) 1663 { 1664 SCIP_CONSDATA* consdata; 1665 char rowname[SCIP_MAXSTRLEN]; 1666 int b; 1667 1668 assert( cons != NULL); 1669 1670 /* get constraint data */ 1671 consdata = SCIPconsGetData(cons); 1672 assert(consdata != NULL); 1673 assert(consdata->row1 == NULL); 1674 assert(consdata->row2 == NULL); 1675 assert(consdata->nbinvars > 1); 1676 1677 /* create the LP row which captures the linking between the real and binary variables */ 1678 (void)SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s[link]", SCIPconsGetName(cons)); 1679 1680 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->row1, cons, rowname, 0.0, 0.0, 1681 SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons), SCIPconsIsRemovable(cons)) ); 1682 1683 /* add linking variable to the row */ 1684 assert(consdata->linkvar != NULL); 1685 SCIP_CALL( SCIPaddVarToRow(scip, consdata->row1, consdata->linkvar, -1.0) ); 1686 1687 /* adding binary variables to the row */ 1688 assert(consdata->binvars != NULL); 1689 for( b = 0; b < consdata->nbinvars; ++b ) 1690 { 1691 SCIP_CALL( SCIPaddVarToRow(scip, consdata->row1, consdata->binvars[b], consdata->vals[b]) ); 1692 } 1693 1694 /* create the LP row which captures the set partitioning condition of the binary variables */ 1695 (void)SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s[setppc]", SCIPconsGetName(cons)); 1696 assert( consdata->nbinvars > 0 ); 1697 1698 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->row2, cons, rowname, 1.0, 1.0, 1699 SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons), SCIPconsIsRemovable(cons)) ); 1700 1701 SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->row2, consdata->nbinvars, consdata->binvars, 1.0) ); 1702 1703 return SCIP_OKAY; 1704 } 1705 1706 1707 /** adds linking constraint as cut to the LP */ 1708 static 1709 SCIP_RETCODE addCuts( 1710 SCIP* scip, /**< SCIP data structure */ 1711 SCIP_CONS* cons, /**< linking constraint */ 1712 SCIP_Bool* cutoff /**< whether a cutoff has been detected */ 1713 ) 1714 { 1715 SCIP_CONSDATA* consdata; 1716 1717 assert( cutoff != NULL ); 1718 *cutoff = FALSE; 1719 1720 consdata = SCIPconsGetData(cons); 1721 assert(consdata != NULL); 1722 1723 /* in case there is only at most one binary variables, the constraints should already be disabled */ 1724 assert(consdata->nbinvars > 1); 1725 1726 if( consdata->row1 == NULL ) 1727 { 1728 assert(consdata->row2 == NULL); 1729 1730 /* convert linking data into LP rows */ 1731 SCIP_CALL( createRows(scip, cons) ); 1732 } 1733 assert(consdata->row1 != NULL); 1734 assert(consdata->row2 != NULL); 1735 1736 /* insert LP linking row as cut */ 1737 if( !SCIProwIsInLP(consdata->row1) ) 1738 { 1739 SCIPdebugMsg(scip, "adding linking row of constraint <%s> as cut to the LP\n", SCIPconsGetName(cons)); 1740 SCIP_CALL( SCIPaddRow(scip, consdata->row1, TRUE/*FALSE*/, cutoff) ); 1741 } 1742 1743 /* insert LP set partitioning row as cut */ 1744 if( !SCIProwIsInLP(consdata->row2) ) 1745 { 1746 SCIPdebugMsg(scip, "adding set partitioning row of constraint <%s> as cut to the LP\n", SCIPconsGetName(cons)); 1747 SCIP_CALL( SCIPaddRow(scip, consdata->row2, TRUE/*FALSE*/, cutoff) ); 1748 } 1749 1750 return SCIP_OKAY; 1751 } 1752 1753 /** adds linking constraint as rows to the NLP, if not added yet */ 1754 static 1755 SCIP_RETCODE addNlrow( 1756 SCIP* scip, /**< SCIP data structure */ 1757 SCIP_CONS* cons /**< linking constraint */ 1758 ) 1759 { 1760 SCIP_CONSDATA* consdata; 1761 1762 assert(SCIPisNLPConstructed(scip)); 1763 1764 /* skip deactivated, redundant, or local constraints (the NLP does not allow for local rows at the moment) */ 1765 if( !SCIPconsIsActive(cons) || !SCIPconsIsChecked(cons) || SCIPconsIsLocal(cons) ) 1766 return SCIP_OKAY; 1767 1768 consdata = SCIPconsGetData(cons); 1769 assert(consdata != NULL); 1770 1771 if( consdata->nlrow1 == NULL ) 1772 { 1773 char rowname[SCIP_MAXSTRLEN]; 1774 SCIP_Real* coefs; 1775 int i; 1776 1777 assert(consdata->nlrow2 == NULL); 1778 1779 /* create the NLP row which captures the linking between the real and binary variables */ 1780 (void)SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s[link]", SCIPconsGetName(cons)); 1781 1782 /* create nlrow1 with binary variables */ 1783 SCIP_CALL( SCIPcreateNlRow(scip, &consdata->nlrow1, rowname, 1784 0.0, consdata->nbinvars, consdata->binvars, consdata->vals, NULL, 0.0, 0.0, SCIP_EXPRCURV_LINEAR) ); 1785 /* add linking variable to the row */ 1786 SCIP_CALL( SCIPaddLinearCoefToNlRow(scip, consdata->nlrow1, consdata->linkvar, -1.0) ); 1787 1788 /* create the NLP row which captures the set partitioning condition of the binary variables */ 1789 (void)SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s[setppc]", SCIPconsGetName(cons)); 1790 1791 SCIP_CALL( SCIPallocBufferArray(scip, &coefs, consdata->nbinvars) ); 1792 for( i = 0; i < consdata->nbinvars; ++i ) 1793 coefs[i] = 1.0; 1794 1795 SCIP_CALL( SCIPcreateNlRow(scip, &consdata->nlrow2, rowname, 1796 0.0, consdata->nbinvars, consdata->binvars, coefs, NULL, 1.0, 1.0, SCIP_EXPRCURV_LINEAR) ); 1797 1798 SCIPfreeBufferArray(scip, &coefs); 1799 } 1800 1801 assert(SCIPnlrowIsInNLP(consdata->nlrow1) == SCIPnlrowIsInNLP(consdata->nlrow2)); 1802 if( !SCIPnlrowIsInNLP(consdata->nlrow1) ) 1803 { 1804 SCIP_CALL( SCIPaddNlRow(scip, consdata->nlrow1) ); 1805 SCIP_CALL( SCIPaddNlRow(scip, consdata->nlrow2) ); 1806 } 1807 1808 return SCIP_OKAY; 1809 } 1810 1811 /** checks constraint for violation, and adds it as a cuts if possible */ 1812 static 1813 SCIP_RETCODE separateCons( 1814 SCIP* scip, /**< SCIP data structure */ 1815 SCIP_CONS* cons, /**< linking constraint to be separated */ 1816 SCIP_SOL* sol, /**< primal CIP solution, NULL for current LP solution */ 1817 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */ 1818 SCIP_Bool* separated, /**< pointer to store TRUE, if a cut was found */ 1819 int* nchgbds /**< pointer to store the number of changed variables bounds */ 1820 ) 1821 { 1822 SCIP_CONSDATA* consdata; 1823 SCIP_Bool addcut; 1824 SCIP_Bool mustcheck; 1825 1826 assert(cons != NULL); 1827 assert(SCIPconsGetHdlr(cons) != NULL); 1828 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0); 1829 assert(cutoff != NULL); 1830 assert(separated != NULL); 1831 assert(nchgbds != NULL); 1832 1833 consdata = SCIPconsGetData(cons); 1834 assert(consdata != NULL); 1835 1836 /* in case there is only at most one binary variables, the constraints should already be disabled */ 1837 assert(consdata->nbinvars > 1); 1838 1839 SCIPdebugMsg(scip, "separating constraint <%s>\n", SCIPconsGetName(cons)); 1840 1841 *cutoff = FALSE; 1842 addcut = FALSE; 1843 mustcheck = TRUE; 1844 1845 /* check constraint for violation only looking at the fixed variables, apply further fixings if possible */ 1846 if( sol == NULL ) 1847 { 1848 SCIP_CALL( processRealBoundChg(scip, cons, cutoff, nchgbds, &mustcheck) ); 1849 } 1850 1851 if( mustcheck && !(*cutoff) ) 1852 { 1853 /* variable's fixings didn't give us any information -> we have to check the constraint */ 1854 if( sol == NULL && consdata->row1 != NULL ) 1855 { 1856 SCIP_Real feasibility; 1857 SCIP_Real tmp; 1858 1859 assert(consdata->row2 != NULL); 1860 1861 /* skip constraints already in the LP */ 1862 if( SCIProwIsInLP(consdata->row1) && SCIProwIsInLP(consdata->row2)) 1863 return SCIP_OKAY; 1864 1865 feasibility = 1.0; 1866 1867 /* check first row (linking) for feasibility */ 1868 if( !SCIProwIsInLP(consdata->row1) ) 1869 { 1870 tmp = SCIPgetRowLPFeasibility(scip, consdata->row1); 1871 feasibility = MIN(feasibility, tmp); 1872 } 1873 1874 /* check second row (setppc) for feasibility */ 1875 if( !SCIProwIsInLP(consdata->row2) ) 1876 { 1877 tmp = SCIPgetRowLPFeasibility(scip, consdata->row2); 1878 feasibility = MIN(feasibility, tmp); 1879 } 1880 addcut = SCIPisFeasNegative(scip, feasibility); 1881 } 1882 else 1883 addcut = !checkCons(scip, cons, sol); 1884 1885 if( !addcut ) 1886 { 1887 /* constraint was feasible -> increase age */ 1888 SCIP_CALL( SCIPincConsAge(scip, cons) ); 1889 } 1890 } 1891 1892 if( addcut ) 1893 { 1894 /* insert LP row as cut */ 1895 assert(!(*cutoff)); 1896 SCIP_CALL( addCuts(scip, cons, cutoff) ); 1897 SCIP_CALL( SCIPresetConsAge(scip, cons) ); 1898 *separated = TRUE; 1899 } 1900 1901 return SCIP_OKAY; 1902 } 1903 1904 /** enforces the pseudo solution on the given constraint */ 1905 static 1906 SCIP_RETCODE enforcePseudo( 1907 SCIP* scip, /**< SCIP data structure */ 1908 SCIP_CONS* cons, /**< linking constraint to be separated */ 1909 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */ 1910 SCIP_Bool* infeasible, /**< pointer to store TRUE, if the constraint was infeasible */ 1911 int* nchgbds, /**< pointer to store the number of changed variable bounds */ 1912 SCIP_Bool* solvelp /**< pointer to store TRUE, if the LP has to be solved */ 1913 ) 1914 { 1915 SCIP_Bool addcut; 1916 SCIP_Bool mustcheck; 1917 1918 assert(!SCIPhasCurrentNodeLP(scip)); 1919 assert(cons != NULL); 1920 assert(SCIPconsGetHdlr(cons) != NULL); 1921 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0); 1922 assert(cutoff != NULL); 1923 assert(infeasible != NULL); 1924 assert(nchgbds != NULL); 1925 assert(solvelp != NULL); 1926 1927 addcut = FALSE; 1928 mustcheck = TRUE; 1929 1930 /* check constraint for violation only looking at the fixed variables, apply further fixings if possible */ 1931 SCIP_CALL( processRealBoundChg(scip, cons, cutoff, nchgbds, &mustcheck) ); 1932 SCIP_CALL( processBinvarFixings(scip, cons, cutoff, nchgbds, &addcut, &mustcheck) ); 1933 1934 if( mustcheck ) 1935 { 1936 assert(!addcut); 1937 1938 if( checkCons(scip, cons, NULL) ) 1939 { 1940 /* constraint was feasible -> increase age */ 1941 SCIP_CALL( SCIPincConsAge(scip, cons) ); 1942 } 1943 else 1944 { 1945 /* constraint was infeasible -> reset age */ 1946 SCIP_CALL( SCIPresetConsAge(scip, cons) ); 1947 *infeasible = TRUE; 1948 } 1949 } 1950 1951 if( addcut ) 1952 { 1953 assert(!(*cutoff)); 1954 /* a cut must be added to the LP -> we have to solve the LP immediately */ 1955 SCIP_CALL( SCIPresetConsAge(scip, cons) ); 1956 *solvelp = TRUE; 1957 } 1958 1959 return SCIP_OKAY; 1960 } 1961 1962 /** helper function to enforce constraints */ 1963 static 1964 SCIP_RETCODE enforceConstraint( 1965 SCIP* scip, /**< SCIP data structure */ 1966 SCIP_CONSHDLR* conshdlr, /**< constraint handler */ 1967 SCIP_CONS** conss, /**< constraints to process */ 1968 int nconss, /**< number of constraints */ 1969 int nusefulconss, /**< number of useful (non-obsolete) constraints to process */ 1970 SCIP_SOL* sol, /**< solution to enforce (NULL for the LP solution) */ 1971 SCIP_RESULT* result /**< pointer to store the result of the enforcing call */ 1972 ) 1973 { 1974 SCIP_Bool cutoff; 1975 SCIP_Bool separated; 1976 int nchgbds; 1977 int c; 1978 1979 assert(conshdlr != NULL); 1980 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 1981 assert(nconss == 0 || conss != NULL); 1982 assert(result != NULL); 1983 1984 SCIPdebugMsg(scip, "Enforcing %d linking constraints for %s solution\n", nconss, sol == NULL ? "LP" : "relaxation"); 1985 1986 cutoff = FALSE; 1987 separated = FALSE; 1988 nchgbds = 0; 1989 1990 /* check all useful linking constraints for feasibility */ 1991 for( c = 0; c < nusefulconss && !cutoff && nchgbds == 0; ++c ) 1992 { 1993 SCIP_CALL( separateCons(scip, conss[c], sol, &cutoff, &separated, &nchgbds) ); 1994 } 1995 1996 /* check all obsolete linking constraints for feasibility */ 1997 for( c = nusefulconss; c < nconss && !cutoff && !separated && nchgbds == 0; ++c ) 1998 { 1999 SCIP_CALL( separateCons(scip, conss[c], sol, &cutoff, &separated, &nchgbds) ); 2000 } 2001 2002 /* return the correct result */ 2003 if( cutoff ) 2004 *result = SCIP_CUTOFF; 2005 else if( nchgbds > 0 ) 2006 *result = SCIP_REDUCEDDOM; 2007 else if( separated ) 2008 *result = SCIP_SEPARATED; 2009 else 2010 *result = SCIP_FEASIBLE; 2011 2012 return SCIP_OKAY; 2013 } 2014 2015 /** adds symmetry information of constraint to a symmetry detection graph */ 2016 static 2017 SCIP_RETCODE addSymmetryInformation( 2018 SCIP* scip, /**< SCIP pointer */ 2019 SYM_SYMTYPE symtype, /**< type of symmetries that need to be added */ 2020 SCIP_CONS* cons, /**< constraint */ 2021 SYM_GRAPH* graph, /**< symmetry detection graph */ 2022 SCIP_Bool* success /**< pointer to store whether symmetry information could be added */ 2023 ) 2024 { 2025 SCIP_CONSDATA* consdata; 2026 SCIP_VAR** vars; 2027 SCIP_Real* vals; 2028 SCIP_Real constant = 0.0; 2029 int nlocvars; 2030 int nvars; 2031 int i; 2032 2033 assert(scip != NULL); 2034 assert(cons != NULL); 2035 assert(graph != NULL); 2036 assert(success != NULL); 2037 2038 consdata = SCIPconsGetData(cons); 2039 assert(consdata != NULL); 2040 2041 /* get active variables of the constraint */ 2042 nvars = SCIPgetNVars(scip); 2043 nlocvars = consdata->nbinvars + 1; 2044 2045 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) ); 2046 SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars) ); 2047 2048 /* get binary variables */ 2049 for( i = 0; i < consdata->nbinvars; ++i ) 2050 { 2051 vars[i] = consdata->binvars[i]; 2052 vals[i] = consdata->vals[i]; 2053 } 2054 2055 /* get linking variable */ 2056 vars[consdata->nbinvars] = consdata->linkvar; 2057 vals[consdata->nbinvars] = -1.0; 2058 2059 SCIP_CALL( SCIPgetActiveVariables(scip, symtype, &vars, &vals, &nlocvars, &constant, SCIPisTransformed(scip)) ); 2060 2061 SCIP_CALL( SCIPextendPermsymDetectionGraphLinear(scip, graph, vars, vals, nlocvars, 2062 cons, -constant, -constant, success) ); 2063 2064 SCIPfreeBufferArray(scip, &vals); 2065 SCIPfreeBufferArray(scip, &vars); 2066 2067 return SCIP_OKAY; 2068 } 2069 2070 /* 2071 * Callback methods of constraint handler 2072 */ 2073 2074 /** copy method for constraint handler plugins (called when SCIP copies plugins) */ 2075 static 2076 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyLinking) 2077 { /*lint --e{715}*/ 2078 assert(scip != NULL); 2079 assert(conshdlr != NULL); 2080 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2081 2082 /* call inclusion method of constraint handler */ 2083 SCIP_CALL( SCIPincludeConshdlrLinking(scip) ); 2084 2085 *valid = TRUE; 2086 2087 return SCIP_OKAY; 2088 } 2089 2090 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */ 2091 static 2092 SCIP_DECL_CONSFREE(consFreeLinking) 2093 { 2094 SCIP_CONSHDLRDATA* conshdlrdata; 2095 2096 assert(conshdlr != NULL); 2097 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2098 assert(scip != NULL); 2099 2100 /* free constraint handler data */ 2101 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2102 assert(conshdlrdata != NULL); 2103 2104 conshdlrdataFree(scip, &conshdlrdata); 2105 2106 return SCIP_OKAY; 2107 } 2108 2109 2110 /** presolving initialization method of constraint handler (called when presolving is about to begin) */ 2111 static 2112 SCIP_DECL_CONSINITPRE(consInitpreLinking) 2113 { /*lint --e{715}*/ 2114 SCIP_CONSHDLRDATA* conshdlrdata; 2115 SCIP_CONSDATA* consdata; 2116 int c; 2117 2118 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2119 assert(conshdlrdata != NULL); 2120 2121 /* disable all linking constraints which contain at most one binary variable */ 2122 for( c = 0; c < nconss; ++c ) 2123 { 2124 consdata = SCIPconsGetData(conss[c]); 2125 assert(consdata != NULL); 2126 2127 /* skip constraints which are not added */ 2128 if( !SCIPconsIsAdded(conss[c]) ) 2129 continue; 2130 2131 if( consdata->nbinvars <= 1 ) 2132 { 2133 SCIP_CALL( SCIPdisableCons(scip, conss[c]) ); 2134 assert(consdata->nbinvars == 0 || SCIPvarGetLbGlobal(consdata->binvars[0]) > 0.5); 2135 } 2136 else if( conshdlrdata->linearize ) 2137 { 2138 SCIP_CALL( consdataLinearize(scip, conss[c], consdata) ); 2139 SCIP_CALL( SCIPdelCons(scip, conss[c]) ); 2140 } 2141 } 2142 2143 return SCIP_OKAY; 2144 } 2145 2146 /** solving process initialization method of constraint handler */ 2147 static 2148 SCIP_DECL_CONSINITSOL(consInitsolLinking) 2149 { /*lint --e{715}*/ 2150 /* add nlrow representations to NLP, if NLP had been constructed */ 2151 if( SCIPisNLPConstructed(scip) ) 2152 { 2153 int c; 2154 for( c = 0; c < nconss; ++c ) 2155 { 2156 SCIP_CALL( addNlrow(scip, conss[c]) ); 2157 } 2158 } 2159 2160 return SCIP_OKAY; 2161 } 2162 2163 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */ 2164 static 2165 SCIP_DECL_CONSEXITSOL(consExitsolLinking) 2166 { /*lint --e{715}*/ 2167 SCIP_CONSDATA* consdata; 2168 int c; 2169 2170 for( c = 0; c < nconss; ++c ) 2171 { 2172 consdata = SCIPconsGetData(conss[c]); 2173 assert(consdata != NULL); 2174 2175 /* release the rows and nlrows of all constraints */ 2176 if( consdata->row1 != NULL ) 2177 { 2178 assert(consdata->row2 != NULL); 2179 2180 SCIP_CALL( SCIPreleaseRow(scip, &consdata->row1) ); 2181 SCIP_CALL( SCIPreleaseRow(scip, &consdata->row2) ); 2182 } 2183 2184 if( consdata->nlrow1 != NULL ) 2185 { 2186 assert(consdata->nlrow2 != NULL); 2187 2188 SCIP_CALL( SCIPreleaseNlRow(scip, &consdata->nlrow1) ); 2189 SCIP_CALL( SCIPreleaseNlRow(scip, &consdata->nlrow2) ); 2190 } 2191 } 2192 2193 return SCIP_OKAY; 2194 } 2195 2196 2197 /** frees specific constraint data */ 2198 static 2199 SCIP_DECL_CONSDELETE(consDeleteLinking) 2200 { /*lint --e{715}*/ 2201 SCIP_CONSHDLRDATA* conshdlrdata; 2202 2203 assert(conshdlr != NULL); 2204 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2205 assert(consdata != NULL); 2206 assert(*consdata != NULL); 2207 2208 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2209 assert(conshdlrdata != NULL); 2210 assert(conshdlrdata->eventhdlr != NULL); 2211 2212 /* remove linking constraint form variable hash map */ 2213 assert(conshdlrdata->varmap != NULL); 2214 assert(SCIPhashmapExists(conshdlrdata->varmap, getHashmapKey((*consdata)->linkvar))); 2215 SCIP_CALL( SCIPhashmapRemove(conshdlrdata->varmap, getHashmapKey((*consdata)->linkvar)) ); 2216 2217 if( (*consdata)->nbinvars > 0 && SCIPisTransformed(scip) ) 2218 { 2219 SCIP_CALL( dropAllEvents(scip, *consdata, conshdlrdata->eventhdlr) ); 2220 } 2221 2222 /* free consdata */ 2223 SCIP_CALL( consdataFree(scip, consdata) ); 2224 2225 return SCIP_OKAY; 2226 } 2227 2228 2229 /** transforms constraint data into data belonging to the transformed problem */ 2230 static 2231 SCIP_DECL_CONSTRANS(consTransLinking) 2232 { /*lint --e{715}*/ 2233 SCIP_CONSDATA* sourcedata; 2234 SCIP_CONSDATA* targetdata; 2235 SCIP_CONSHDLRDATA* conshdlrdata; 2236 2237 assert(conshdlr != NULL); 2238 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2239 assert(SCIPgetStage(scip) == SCIP_STAGE_TRANSFORMING); 2240 assert(sourcecons != NULL); 2241 assert(targetcons != NULL); 2242 2243 /* free constraint handler data */ 2244 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2245 assert(conshdlrdata != NULL); 2246 assert(conshdlrdata->eventhdlr != NULL); 2247 2248 sourcedata = SCIPconsGetData(sourcecons); 2249 assert(sourcedata != NULL); 2250 assert(sourcedata->row1 == NULL); /* in original problem, there cannot be LP rows */ 2251 assert(sourcedata->row2 == NULL); /* in original problem, there cannot be LP rows */ 2252 2253 SCIPdebugMsg(scip, "transform linking constraint for variable <%s>\n", SCIPvarGetName(sourcedata->linkvar)); 2254 2255 /* create constraint data for target constraint */ 2256 SCIP_CALL( consdataCreate(scip, conshdlrdata->eventhdlr, &targetdata, 2257 sourcedata->linkvar, sourcedata->binvars, sourcedata->vals, sourcedata->nbinvars) ); 2258 2259 /* create target constraint */ 2260 SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata, 2261 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons), 2262 SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons), 2263 SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons), 2264 SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) ); 2265 2266 /* insert (transformed) linking constraint into the hash map */ 2267 assert(conshdlrdata->varmap != NULL); 2268 SCIP_CALL( SCIPhashmapInsert(conshdlrdata->varmap, getHashmapKey(targetdata->linkvar), *targetcons) ); 2269 2270 return SCIP_OKAY; 2271 } 2272 2273 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */ 2274 static 2275 SCIP_DECL_CONSINITLP(consInitlpLinking) 2276 { /*lint --e{715}*/ 2277 SCIP_CONSDATA* consdata; 2278 int c; 2279 2280 *infeasible = FALSE; 2281 2282 for( c = 0; c < nconss && !(*infeasible); ++c ) 2283 { 2284 assert(SCIPconsIsInitial(conss[c])); 2285 2286 consdata = SCIPconsGetData(conss[c]); 2287 assert(consdata != NULL); 2288 2289 if( consdata->nbinvars <= 1 ) 2290 continue; 2291 2292 SCIP_CALL( addCuts(scip, conss[c], infeasible) ); 2293 } 2294 2295 return SCIP_OKAY; 2296 } 2297 2298 2299 /** separation method of constraint handler for LP solutions */ 2300 static 2301 SCIP_DECL_CONSSEPALP(consSepalpLinking) 2302 { /*lint --e{715}*/ 2303 SCIP_Bool cutoff; 2304 SCIP_Bool separated; 2305 int nchgbds; 2306 int c; 2307 2308 assert(conshdlr != NULL); 2309 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2310 assert(nconss == 0 || conss != NULL); 2311 assert(result != NULL); 2312 2313 SCIPdebugMsg(scip, "separating %d/%d linking constraints\n", nusefulconss, nconss); 2314 2315 cutoff = FALSE; 2316 separated = FALSE; 2317 nchgbds = 0; 2318 2319 /* check all useful linking constraints for feasibility */ 2320 for( c = 0; c < nusefulconss && !cutoff; ++c ) 2321 { 2322 SCIP_CALL( separateCons(scip, conss[c], NULL, &cutoff, &separated, &nchgbds) ); 2323 } 2324 2325 /* return the correct result */ 2326 if( cutoff ) 2327 *result = SCIP_CUTOFF; 2328 else if( nchgbds > 0 ) 2329 *result = SCIP_REDUCEDDOM; 2330 else if( separated ) 2331 *result = SCIP_SEPARATED; 2332 else 2333 *result = SCIP_DIDNOTFIND; 2334 2335 return SCIP_OKAY; 2336 } 2337 2338 2339 /** separation method of constraint handler for arbitrary primal solutions */ 2340 static 2341 SCIP_DECL_CONSSEPASOL(consSepasolLinking) 2342 { /*lint --e{715}*/ 2343 SCIP_Bool cutoff; 2344 SCIP_Bool separated; 2345 int nchgbds; 2346 int c; 2347 2348 assert(conshdlr != NULL); 2349 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2350 assert(nconss == 0 || conss != NULL); 2351 assert(result != NULL); 2352 2353 SCIPdebugMsg(scip, "separating %d/%d " CONSHDLR_NAME " constraints\n", nusefulconss, nconss); 2354 2355 cutoff = FALSE; 2356 separated = FALSE; 2357 nchgbds = 0; 2358 2359 /* check all useful set partitioning / packing / covering constraints for feasibility */ 2360 for( c = 0; c < nusefulconss && !cutoff; ++c ) 2361 { 2362 SCIP_CALL( separateCons(scip, conss[c], sol, &cutoff, &separated, &nchgbds) ); 2363 } 2364 2365 /* return the correct result */ 2366 if( cutoff ) 2367 *result = SCIP_CUTOFF; 2368 else if( nchgbds > 0 ) 2369 *result = SCIP_REDUCEDDOM; 2370 else if( separated ) 2371 *result = SCIP_SEPARATED; 2372 else 2373 *result = SCIP_DIDNOTFIND; 2374 2375 return SCIP_OKAY; 2376 } 2377 2378 2379 /** constraint enforcing method of constraint handler for LP solutions */ 2380 static 2381 SCIP_DECL_CONSENFOLP(consEnfolpLinking) 2382 { /*lint --e{715}*/ 2383 SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, nusefulconss, NULL, result) ); 2384 2385 return SCIP_OKAY; 2386 } 2387 2388 2389 /** constraint enforcing method of constraint handler for relaxation solutions */ 2390 static 2391 SCIP_DECL_CONSENFORELAX(consEnforelaxLinking) 2392 { /*lint --e{715}*/ 2393 SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, nusefulconss, sol, result) ); 2394 2395 return SCIP_OKAY; 2396 } 2397 2398 2399 /** constraint enforcing method of constraint handler for pseudo solutions */ 2400 static 2401 SCIP_DECL_CONSENFOPS(consEnfopsLinking) 2402 { /*lint --e{715}*/ 2403 SCIP_Bool cutoff; 2404 SCIP_Bool infeasible; 2405 int nchgbds; 2406 SCIP_Bool solvelp; 2407 int c; 2408 2409 assert(conshdlr != NULL); 2410 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2411 assert(nconss == 0 || conss != NULL); 2412 assert(result != NULL); 2413 2414 SCIPdebugMsg(scip, "pseudo enforcing %d " CONSHDLR_NAME " constraints\n", nconss); 2415 2416 if( objinfeasible ) 2417 { 2418 *result = SCIP_DIDNOTRUN; 2419 return SCIP_OKAY; 2420 } 2421 2422 cutoff = FALSE; 2423 infeasible = FALSE; 2424 nchgbds = 0; 2425 solvelp = FALSE; 2426 2427 /* check all linking constraint for domain reductions and feasibility */ 2428 for( c = 0; c < nconss && !cutoff && !solvelp; ++c ) 2429 { 2430 SCIP_CALL( enforcePseudo(scip, conss[c], &cutoff, &infeasible, &nchgbds, &solvelp) ); 2431 } 2432 2433 if( cutoff ) 2434 *result = SCIP_CUTOFF; 2435 else if( nchgbds > 0 ) 2436 *result = SCIP_REDUCEDDOM; 2437 else if( solvelp ) 2438 *result = SCIP_SOLVELP; 2439 else if( infeasible ) 2440 *result = SCIP_INFEASIBLE; 2441 else 2442 *result = SCIP_FEASIBLE; 2443 2444 return SCIP_OKAY; 2445 } 2446 2447 2448 /** feasibility check method of constraint handler for integral solutions */ 2449 static 2450 SCIP_DECL_CONSCHECK(consCheckLinking) 2451 { /*lint --e{715}*/ 2452 SCIP_CONS* cons; 2453 SCIP_CONSDATA* consdata; 2454 int c; 2455 2456 assert(conshdlr != NULL); 2457 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2458 assert(nconss == 0 || conss != NULL); 2459 assert(result != NULL); 2460 2461 *result = SCIP_FEASIBLE; 2462 2463 /* check all linking constraints for feasibility */ 2464 for( c = 0; c < nconss && (*result == SCIP_FEASIBLE || completely); ++c ) 2465 { 2466 cons = conss[c]; 2467 consdata = SCIPconsGetData(cons); 2468 assert(consdata != NULL); 2469 2470 if( consdata->nbinvars > 1 && (checklprows || consdata->row1 == NULL || !SCIProwIsInLP(consdata->row1)) ) 2471 { 2472 if( !checkCons(scip, cons, sol) ) 2473 { 2474 /* constraint is violated */ 2475 *result = SCIP_INFEASIBLE; 2476 2477 if( printreason ) 2478 { 2479 int pos; 2480 int b; 2481 2482 pos = -1; 2483 2484 #ifndef NDEBUG 2485 for( b = 0; b < consdata->nbinvars; ++b ) 2486 { 2487 assert(consdata->binvars[b] != NULL); 2488 assert(SCIPvarIsBinary(consdata->binvars[b])); 2489 } 2490 #endif 2491 2492 SCIP_CALL( SCIPprintCons(scip, cons, NULL) ); 2493 SCIPinfoMessage(scip, NULL, ";\n"); 2494 2495 /* check that at most one binary variable is fixed */ 2496 for( b = 0; b < consdata->nbinvars; ++b ) 2497 { 2498 assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, consdata->binvars[b])) ); 2499 2500 /* check if binary variable is fixed */ 2501 if( SCIPgetSolVal(scip, sol, consdata->binvars[b]) > 0.5 ) 2502 { 2503 if( pos != -1 ) 2504 { 2505 SCIPinfoMessage(scip, NULL, "violation: more than one binary variable is set to one"); 2506 break; 2507 } 2508 pos = b ; 2509 } 2510 } 2511 2512 /* check that at least one binary variable is fixed */ 2513 if( pos == -1 ) 2514 { 2515 SCIPinfoMessage(scip, NULL, "violation: none of the binary variables is set to one\n"); 2516 } 2517 else if( !SCIPisFeasEQ(scip, consdata->vals[pos], SCIPgetSolVal(scip, sol, consdata->linkvar)) ) 2518 { 2519 /* check if the fixed binary variable match with the linking variable */ 2520 SCIPinfoMessage(scip, NULL, "violation: <%s> = <%g> and <%s> is one\n", 2521 SCIPvarGetName(consdata->linkvar), SCIPgetSolVal(scip, sol, consdata->linkvar), 2522 SCIPvarGetName(consdata->binvars[pos]) ); 2523 } 2524 } 2525 } 2526 } 2527 } 2528 2529 return SCIP_OKAY; 2530 } 2531 2532 /** domain propagation method of constraint handler */ 2533 static 2534 SCIP_DECL_CONSPROP(consPropLinking) 2535 { /*lint --e{715}*/ 2536 SCIP_Bool cutoff = FALSE; 2537 int nchgbds = 0; 2538 int c; 2539 2540 assert(conshdlr != NULL); 2541 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2542 assert(nconss == 0 || conss != NULL); 2543 assert(result != NULL); 2544 2545 SCIPdebugMsg(scip, "propagating %d/%d " CONSHDLR_NAME " constraints\n", nusefulconss, nconss); 2546 2547 /* propagate all useful set partitioning / packing / covering constraints */ 2548 for( c = 0; c < nusefulconss && !cutoff; ++c ) 2549 { 2550 SCIP_Bool addcut; 2551 SCIP_Bool mustcheck; 2552 2553 SCIP_CALL( processRealBoundChg(scip, conss[c], &cutoff, &nchgbds, &mustcheck) ); 2554 SCIP_CALL( processBinvarFixings(scip, conss[c], &cutoff, &nchgbds, &addcut, &mustcheck) ); 2555 } /*lint !e438*/ 2556 2557 /* return the correct result */ 2558 if( cutoff ) 2559 *result = SCIP_CUTOFF; 2560 else if( nchgbds > 0 ) 2561 *result = SCIP_REDUCEDDOM; 2562 else 2563 *result = SCIP_DIDNOTFIND; 2564 2565 return SCIP_OKAY; 2566 } 2567 2568 2569 /** presolving method of constraint handler */ 2570 static 2571 SCIP_DECL_CONSPRESOL(consPresolLinking) 2572 { /*lint --e{715}*/ 2573 SCIP_CONSHDLRDATA* conshdlrdata; 2574 int oldnfixedvars; 2575 int oldnchgbds; 2576 int oldnaggrvars; 2577 int oldndelconss; 2578 int firstchange; 2579 int firstclique; 2580 int lastclique; 2581 int c; 2582 SCIP_Bool fixed; 2583 SCIP_Bool cutoff; 2584 SCIP_Bool infeasible; 2585 SCIP_Bool mustcheck; 2586 2587 assert(conshdlr != NULL); 2588 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2589 assert(scip != NULL); 2590 assert(result != NULL); 2591 2592 SCIPdebugMsg(scip, "presolve %d linking constraints\n", nconss); 2593 2594 (*result) = SCIP_DIDNOTFIND; 2595 2596 oldnchgbds = *nchgbds; 2597 oldnaggrvars = *naggrvars; 2598 oldnfixedvars = *nfixedvars; 2599 oldndelconss = *ndelconss; 2600 cutoff = FALSE; 2601 2602 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2603 assert(conshdlrdata != NULL); 2604 2605 /* process constraints */ 2606 firstchange = INT_MAX; 2607 firstclique = INT_MAX; 2608 lastclique = -1; 2609 2610 /* check for each linking constraint the set partitioning condition */ 2611 for( c = 0; c < nconss && !SCIPisStopped(scip); ++c ) 2612 { 2613 SCIP_CONS* cons; 2614 SCIP_CONSDATA* consdata; 2615 2616 assert(*result != SCIP_CUTOFF); 2617 2618 cons = conss[c]; 2619 assert(cons != NULL); 2620 assert(!SCIPconsIsModifiable(cons)); 2621 2622 SCIPdebugMsg(scip, "presolve linking constraints <%s>\n", SCIPconsGetName(cons)); 2623 2624 consdata = SCIPconsGetData(cons); 2625 assert(consdata != NULL); 2626 2627 if( !SCIPconsIsEnabled(cons) /* || consdata->nbinvars <= 1 */ ) 2628 continue; 2629 2630 /* in case there is only at most one binary variables, the constraints should already be disabled */ 2631 assert(consdata->nbinvars > 1); 2632 2633 /*SCIPdebugMsg(scip, "presolving set partitioning / packing / covering constraint <%s>\n", SCIPconsGetName(cons));*/ 2634 if( consdata->nfixedones >= 2 ) 2635 { 2636 /* at least two variables are fixed to 1: 2637 * - a linking constraint is infeasible due to the set partitioning condition 2638 */ 2639 SCIPdebugMsg(scip, "" CONSHDLR_NAME " constraint <%s> is infeasible\n", SCIPconsGetName(cons)); 2640 *result = SCIP_CUTOFF; 2641 return SCIP_OKAY; 2642 } 2643 2644 if( consdata->nfixedones == 1 ) 2645 { 2646 /* exactly one variable is fixed to 1: 2647 * - all other binary variables must be zero due to the set partitioning condition 2648 * - linking variable has to be fixed to corresponding binary variable which is fixed to one 2649 * - if constraint is not modifiable it can be removed 2650 */ 2651 SCIP_VAR* var; 2652 int v; 2653 2654 SCIPdebugMsg(scip, "" CONSHDLR_NAME " constraint <%s> has a binary variable fixed to 1.0\n", SCIPconsGetName(cons)); 2655 2656 for( v = 0; v < consdata->nbinvars; ++v ) 2657 { 2658 var = consdata->binvars[v]; 2659 assert(var != NULL); 2660 2661 if( SCIPvarGetLbGlobal(var) < 0.5 && SCIPvarGetUbGlobal(var) > 0.5 ) 2662 { 2663 SCIP_CALL( SCIPfixVar(scip, var, 0.0, &infeasible, &fixed) ); 2664 2665 if( infeasible ) 2666 { 2667 SCIPdebugMsg(scip, "" CONSHDLR_NAME " constraint <%s>: infeasible fixing <%s> == 0\n", 2668 SCIPconsGetName(cons), SCIPvarGetName(var)); 2669 2670 *result = SCIP_CUTOFF; 2671 return SCIP_OKAY; 2672 } 2673 assert(fixed); 2674 (*nfixedvars)++; 2675 } 2676 else if( SCIPvarGetLbGlobal(var) > 0.5 ) 2677 { 2678 /* fix linking variable */ 2679 assert(SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_LOOSE 2680 || SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_AGGREGATED 2681 || SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_COLUMN 2682 || SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_FIXED 2683 || SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_NEGATED); 2684 SCIP_CALL( SCIPfixVar(scip, consdata->linkvar, consdata->vals[v], &infeasible, &fixed) ); 2685 2686 if( infeasible ) 2687 { 2688 SCIPdebugMsg(scip, "" CONSHDLR_NAME " constraint <%s>: infeasible fixing <%s> == %g\n", 2689 SCIPconsGetName(cons), SCIPvarGetName(consdata->linkvar), consdata->vals[v]); 2690 2691 *result = SCIP_CUTOFF; 2692 return SCIP_OKAY; 2693 } 2694 2695 if( fixed ) 2696 (*nfixedvars)++; 2697 } 2698 } 2699 2700 /* now all other variables are fixed to zero: 2701 * the constraint is feasible, and if it's not modifiable, it is redundant 2702 */ 2703 SCIPdebugMsg(scip, "" CONSHDLR_NAME " constraint <%s> is redundant\n", SCIPconsGetName(cons)); 2704 SCIP_CALL( SCIPdelCons(scip, cons) ); 2705 (*ndelconss)++; 2706 continue; 2707 } 2708 2709 if( consdata->nfixedzeros == consdata->nbinvars ) 2710 { 2711 /* all variables are fixed to zero: 2712 * - a linking constraint is infeasible due the set partitioning condition 2713 */ 2714 assert(consdata->nfixedones == 0); 2715 2716 SCIPdebugMsg(scip, "linking constraint <%s> is infeasible due to set partitioning condition\n", SCIPconsGetName(cons)); 2717 *result = SCIP_CUTOFF; 2718 return SCIP_OKAY; 2719 } 2720 2721 if( consdata->nfixedzeros == consdata->nbinvars - 1 ) 2722 { 2723 /* all variables except one are fixed to zero: 2724 * - a linking constraint is feasible due the set partitioning condition 2725 * - the remaining binary variable can be fixed to one 2726 * - linking variable has to be fixed to corresponding binary variable which is fixed to one 2727 * - constraint can be deleted since it is not modifiable 2728 */ 2729 SCIP_VAR* var; 2730 int v; 2731 2732 assert(consdata->nfixedones == 0); 2733 2734 SCIPdebugMsg(scip, "" CONSHDLR_NAME " constraint <%s> has only one binary variable not fixed to zero\n", 2735 SCIPconsGetName(cons)); 2736 2737 /* search unfixed variable */ 2738 /* intentional empty for loop to increment counter to proper position */ 2739 /* TODO speed up loop by considering only variables between firstnonfixed and lastnonfixed */ 2740 for( v = 0; v < consdata->nbinvars && SCIPvarGetUbGlobal(consdata->binvars[v]) < 0.5; ++v ); /*lint !e722*/ 2741 assert(v < consdata->nbinvars); 2742 var = consdata->binvars[v]; 2743 2744 /* fix remaining binary variable */ 2745 SCIP_CALL( SCIPfixVar(scip, var, 1.0, &infeasible, &fixed) ); 2746 if( infeasible ) 2747 { 2748 SCIPdebugMsg(scip, "" CONSHDLR_NAME " constraint <%s>: infeasible fixing <%s> == 1\n", 2749 SCIPconsGetName(cons), SCIPvarGetName(var)); 2750 *result = SCIP_CUTOFF; 2751 return SCIP_OKAY; 2752 } 2753 assert(fixed); 2754 (*nfixedvars)++; 2755 2756 /* fix linking variable */ 2757 assert(SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_LOOSE 2758 || SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_AGGREGATED 2759 || SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_COLUMN 2760 || SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_FIXED 2761 || SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_NEGATED); 2762 SCIP_CALL( SCIPfixVar(scip, consdata->linkvar, consdata->vals[v], &infeasible, &fixed) ); 2763 2764 if( infeasible ) 2765 { 2766 SCIPdebugMsg(scip, CONSHDLR_NAME " constraint <%s>: infeasible fixing <%s> == %g\n", 2767 SCIPconsGetName(cons), SCIPvarGetName(consdata->linkvar), consdata->vals[v]); 2768 2769 *result = SCIP_CUTOFF; 2770 return SCIP_OKAY; 2771 } 2772 assert(!SCIPvarIsActive(consdata->linkvar) || fixed); 2773 if( fixed ) 2774 (*nfixedvars)++; 2775 2776 /* delete constraint from problem */ 2777 SCIP_CALL( SCIPdelCons(scip, cons) ); 2778 (*ndelconss)++; 2779 continue; 2780 } 2781 2782 if( consdata->nfixedzeros == consdata->nbinvars - 2 ) /*lint !e641*/ 2783 { 2784 SCIP_VAR* var; 2785 SCIP_VAR* var1; 2786 SCIP_VAR* var2; 2787 SCIP_Bool redundant; 2788 SCIP_Bool aggregated; 2789 int v; 2790 2791 /* aggregate variable, if set partitioning condition consists only of two 2792 * non-fixed variables 2793 */ 2794 2795 /* search unfixed variable */ 2796 var1 = NULL; 2797 var2 = NULL; 2798 for( v = 0; v < consdata->nbinvars && var2 == NULL; ++v ) 2799 { 2800 var = consdata->binvars[v]; 2801 if( SCIPvarGetUbGlobal(var) > 0.5 ) 2802 { 2803 if( var1 == NULL ) 2804 var1 = var; 2805 else 2806 var2 = var; 2807 } 2808 } 2809 assert(var1 != NULL && var2 != NULL); 2810 2811 /* aggregate binary equality var1 + var2 == 1 */ 2812 SCIPdebugMsg(scip, "" CONSHDLR_NAME " constraint <%s>: aggregate <%s> + <%s> == 1\n", 2813 SCIPconsGetName(cons), SCIPvarGetName(var1), SCIPvarGetName(var2)); 2814 SCIP_CALL( SCIPaggregateVars(scip, var1, var2, 1.0, 1.0, 1.0, &infeasible, &redundant, &aggregated) ); 2815 2816 /* evaluate aggregation result */ 2817 if( infeasible ) 2818 { 2819 SCIPdebugMsg(scip, "linking constraint <%s>: infeasible aggregation <%s> + <%s> == 1\n", 2820 SCIPconsGetName(cons), SCIPvarGetName(var1), SCIPvarGetName(var2)); 2821 *result = SCIP_CUTOFF; 2822 return SCIP_OKAY; 2823 } 2824 if( aggregated ) 2825 (*naggrvars)++; 2826 } 2827 2828 /* apply real bound to binary variables */ 2829 SCIP_CALL( processRealBoundChg(scip, cons, &cutoff, nchgbds, &mustcheck) ); 2830 2831 /* tightened linking variable */ 2832 SCIP_CALL( tightenedLinkvar(scip, cons, consdata, &cutoff, nchgbds) ); 2833 2834 /* remove the trailing and leeading binary variable which are fixed to zero */ 2835 SCIP_CALL( removeFixedBinvars(scip, conshdlrdata->eventhdlr, cons) ); 2836 2837 /* fix the linking variable to the only remaining value and the corresponding binary variable to 1.0 */ 2838 if( ! cutoff && consdata->nbinvars == 1 ) 2839 { 2840 SCIP_VAR* linkvar; 2841 SCIP_VAR* binvar; 2842 SCIP_Real val; 2843 2844 linkvar = consdata->linkvar; 2845 binvar = consdata->binvars[0]; 2846 val = consdata->vals[0]; 2847 2848 SCIPdebugMsg(scip, "linking constraint <%s>: fix <%s> to %16.9g as only one binary variable remains", 2849 SCIPconsGetName(cons), SCIPvarGetName(linkvar), val); 2850 2851 SCIP_CALL( SCIPfixVar(scip, binvar, 1.0, &infeasible, &fixed) ); 2852 assert(fixed); 2853 ++(*nfixedvars); 2854 2855 if( ! infeasible ) 2856 { 2857 SCIP_CALL( SCIPfixVar(scip, linkvar, val, &infeasible, &fixed) ); 2858 assert(fixed); 2859 ++(*nfixedvars); 2860 } 2861 cutoff = infeasible; 2862 2863 SCIP_CALL(SCIPdelCons(scip, cons)); 2864 ++(*ndelconss); 2865 } 2866 2867 if( cutoff ) 2868 { 2869 *result = SCIP_CUTOFF; 2870 return SCIP_OKAY; 2871 } 2872 2873 /* remember the first changed constraint to begin the next redundancy round with */ 2874 if( firstchange == INT_MAX ) 2875 firstchange = c; 2876 2877 /* remember the first and last constraints for which we have to add the clique information */ 2878 if( !consdata->cliqueadded && consdata->nbinvars >= 2 ) 2879 { 2880 if( firstclique == INT_MAX ) 2881 firstclique = c; 2882 lastclique = c; 2883 } 2884 } 2885 2886 /* add clique and implication information */ 2887 for( c = firstclique; c < lastclique && !SCIPisStopped(scip); ++c ) 2888 { 2889 SCIP_CONS* cons; 2890 SCIP_CONSDATA* consdata; 2891 2892 assert(*result != SCIP_CUTOFF); 2893 2894 cons = conss[c]; 2895 assert(cons != NULL); 2896 2897 /* ignore deleted constraints */ 2898 if( !SCIPconsIsActive(cons) ) 2899 continue; 2900 2901 consdata = SCIPconsGetData(cons); 2902 assert(consdata != NULL); 2903 2904 if( !consdata->cliqueadded && consdata->nbinvars >= 3 ) 2905 { 2906 /* add set partitioning condition as clique */ 2907 int ncliquebdchgs; 2908 2909 SCIP_CALL( SCIPaddClique(scip, consdata->binvars, NULL, consdata->nbinvars, TRUE, &infeasible, &ncliquebdchgs) ); 2910 *nchgbds += ncliquebdchgs; 2911 2912 if( infeasible ) 2913 { 2914 *result = SCIP_CUTOFF; 2915 return SCIP_OKAY; 2916 } 2917 2918 consdata->cliqueadded = TRUE; 2919 } 2920 } 2921 2922 #if 0 2923 /* transfer aggregated linking variables to the corresponding binary variables */ 2924 assert(conshdlrdata->varmap != NULL); 2925 SCIP_CALL( aggregateVariables(scip, conshdlrdata->varmap, conss, nconss, naggrvars, &cutoff) ); 2926 #endif 2927 2928 if( cutoff ) 2929 *result = SCIP_CUTOFF; 2930 else if( oldndelconss < *ndelconss || oldnfixedvars < *nfixedvars || oldnchgbds < *nchgbds || oldnaggrvars < *naggrvars) 2931 *result = SCIP_SUCCESS; 2932 2933 return SCIP_OKAY; /*lint !e438*/ 2934 } 2935 2936 2937 /** propagation conflict resolving method of constraint handler */ 2938 static 2939 SCIP_DECL_CONSRESPROP(consRespropLinking) 2940 { /*lint --e{715}*/ 2941 SCIP_CONSDATA* consdata; 2942 SCIP_VAR* linkvar; 2943 int v; 2944 2945 SCIPdebugMsg(scip, "conflict resolving method of " CONSHDLR_NAME " constraint handler\n"); 2946 2947 consdata = SCIPconsGetData(cons); 2948 assert(consdata != NULL); 2949 2950 linkvar = consdata->linkvar; 2951 assert(linkvar != NULL); 2952 2953 *result = SCIP_DIDNOTFIND; 2954 2955 if( inferinfo == -1 ) 2956 { 2957 /* we have to resolve a fixing of a binary variable which was done due to fixed binary variables */ 2958 assert(SCIPvarIsBinary(infervar)); 2959 assert(SCIPisFeasEQ(scip, SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, FALSE))); 2960 assert(SCIPisFeasEQ(scip, SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, FALSE))); 2961 2962 if( boundtype == SCIP_BOUNDTYPE_UPPER ) 2963 { 2964 /* we fixed the binary variable to zero since one of the other binary variable was fixed to one (set 2965 * partitioning condition) 2966 */ 2967 assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE) < 0.5); 2968 2969 for( v = 0; v < consdata->nbinvars; ++v ) 2970 { 2971 if( SCIPgetVarLbAtIndex(scip, consdata->binvars[v], bdchgidx, FALSE) > 0.5 ) 2972 { 2973 SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->binvars[v]) ); 2974 break; 2975 } 2976 } 2977 assert(v < consdata->nbinvars); 2978 } 2979 else 2980 { 2981 /* we fixed the binary variable to one since all other binary variable were fixed to zero */ 2982 assert(boundtype == SCIP_BOUNDTYPE_LOWER); 2983 assert(SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE) > 0.5); 2984 2985 for( v = 0; v < consdata->nbinvars; ++v ) 2986 { 2987 if( consdata->binvars[v] != infervar ) 2988 { 2989 /* the reason variable must be assigned to zero */ 2990 assert(SCIPgetVarUbAtIndex(scip, consdata->binvars[v], bdchgidx, FALSE) < 0.5); 2991 SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->binvars[v]) ); 2992 } 2993 } 2994 } 2995 } 2996 else if( inferinfo == -2 ) 2997 { 2998 /* we have to resolve a fixing of a binary variable which was done due to the linking variable lower bound */ 2999 assert(SCIPvarIsBinary(infervar)); 3000 assert(SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE) < 0.5); 3001 assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE) < 0.5); /*@repair: neu*/ 3002 assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, FALSE) > 0.5); /*@repair: neu*/ 3003 assert( SCIPisFeasEQ(scip, SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, FALSE)) ); 3004 assert( SCIPisFeasEQ(scip, SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, FALSE)) ); 3005 3006 SCIP_CALL( SCIPaddConflictLb(scip, linkvar, bdchgidx) ); 3007 } 3008 else if( inferinfo == -3 ) 3009 { 3010 /* we have to resolve a fixing of a binary variable which was done due to the linking variable upper bound */ 3011 assert(SCIPvarIsBinary(infervar)); 3012 assert(SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE) < 0.5); 3013 assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE) < 0.5); 3014 assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, FALSE) > 0.5); 3015 assert( SCIPisFeasEQ(scip, SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, FALSE)) ); 3016 assert( SCIPisFeasEQ(scip, SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, FALSE)) ); 3017 3018 SCIP_CALL( SCIPaddConflictUb(scip, linkvar, bdchgidx) ); 3019 } 3020 else if( inferinfo == -4 ) 3021 { 3022 SCIP_VAR** binvars; 3023 SCIP_Real* vals; 3024 SCIP_Real lb; 3025 int nbinvars; 3026 int b; 3027 3028 /* we tightened the lower bound of the linking variable due the fixing of the corresponding binary variable to zero */ 3029 assert(infervar == linkvar); 3030 assert(boundtype == SCIP_BOUNDTYPE_LOWER); 3031 3032 binvars = consdata->binvars; 3033 nbinvars = consdata->nbinvars; 3034 vals = consdata->vals; 3035 3036 /* get propagated lower bound */ 3037 lb = SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, TRUE); 3038 3039 for( b = 0; b < nbinvars; ++b ) 3040 { 3041 if( vals[b] >= lb ) 3042 break; 3043 3044 assert(SCIPvarGetUbLocal(binvars[b]) < 0.5); 3045 SCIP_CALL( SCIPaddConflictBinvar(scip, binvars[b]) ); 3046 } 3047 } 3048 else if( inferinfo == -5 ) 3049 { 3050 SCIP_VAR** binvars; 3051 SCIP_Real* vals; 3052 SCIP_Real ub; 3053 int nbinvars; 3054 int b; 3055 3056 /* we tightened the upper bound of the linking variable due the fixing of the corresponding binary variable two zero */ 3057 3058 assert(infervar == linkvar); 3059 assert(boundtype == SCIP_BOUNDTYPE_UPPER); 3060 3061 binvars = consdata->binvars; 3062 nbinvars = consdata->nbinvars; 3063 vals = consdata->vals; 3064 3065 /* get old and new upper bound */ 3066 ub = SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, TRUE); 3067 3068 /* resolve tightening of upper bound of the linking variable by binary variables */ 3069 for( b = nbinvars - 1; b >= 0; --b ) 3070 { 3071 if( vals[b] <= ub ) 3072 break; 3073 3074 SCIP_CALL( SCIPaddConflictBinvar(scip, binvars[b]) ); 3075 } 3076 } 3077 else if( inferinfo == -6 ) 3078 { 3079 /* we fixed a binary variable to one since the linking variable was fixed */ 3080 assert(SCIPvarIsBinary(infervar)); 3081 assert(boundtype == SCIP_BOUNDTYPE_LOWER); 3082 assert( SCIPisFeasEQ(scip, SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, FALSE)) ); 3083 assert( SCIPisFeasEQ(scip, SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, FALSE)) ); 3084 assert( SCIPisFeasEQ(scip, SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, FALSE)) ); 3085 assert( SCIPisFeasEQ(scip, SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, FALSE)) ); 3086 3087 assert( !SCIPisFeasEQ(scip, SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, FALSE)) ); 3088 3089 SCIP_CALL( SCIPaddConflictLb(scip, linkvar, bdchgidx) ); 3090 SCIP_CALL( SCIPaddConflictUb(scip, linkvar, bdchgidx) ); 3091 } 3092 else 3093 { 3094 /* we fixed the linking variable to (vals[inferinfo]) since the corresponding binary variable was fixed to one */ 3095 assert(infervar == linkvar); 3096 assert(inferinfo >= 0); 3097 assert(inferinfo < consdata->nbinvars); 3098 assert(SCIPisEQ(scip, consdata->vals[inferinfo], SCIPgetVarUbAtIndex(scip, consdata->linkvar, bdchgidx, TRUE)) 3099 || SCIPisEQ(scip, consdata->vals[inferinfo], SCIPgetVarLbAtIndex(scip, consdata->linkvar, bdchgidx, TRUE))); 3100 3101 assert(SCIPgetVarLbAtIndex(scip, consdata->binvars[inferinfo], bdchgidx, FALSE) > 0.5); 3102 SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->binvars[inferinfo]) ); 3103 } 3104 3105 *result = SCIP_SUCCESS; 3106 3107 return SCIP_OKAY; 3108 } 3109 3110 /** variable rounding lock method of constraint handler */ 3111 static 3112 SCIP_DECL_CONSLOCK(consLockLinking) 3113 { /*lint --e{715}*/ 3114 SCIP_CONSDATA* consdata; 3115 int b; 3116 3117 assert(locktype == SCIP_LOCKTYPE_MODEL); 3118 3119 consdata = SCIPconsGetData(cons); 3120 assert(consdata != NULL); 3121 3122 /* lock linking variable in both directions */ 3123 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->linkvar, locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) ); 3124 3125 /* look binary variables in both directions */ 3126 for( b = 0; b < consdata->nbinvars; ++b ) 3127 { 3128 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->binvars[b], locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) ); 3129 } 3130 3131 return SCIP_OKAY; 3132 } 3133 3134 /** constraint activation notification method of constraint handler */ 3135 static 3136 SCIP_DECL_CONSACTIVE(consActiveLinking) 3137 { /*lint --e{715}*/ 3138 assert(cons != NULL); 3139 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 3140 assert(SCIPconsIsTransformed(cons)); 3141 3142 if( SCIPgetStage(scip) == SCIP_STAGE_SOLVING && SCIPisNLPConstructed(scip) ) 3143 { 3144 SCIP_CALL( addNlrow(scip, cons) ); 3145 } 3146 3147 return SCIP_OKAY; 3148 } 3149 3150 3151 /** constraint deactivation notification method of constraint handler */ 3152 static 3153 SCIP_DECL_CONSDEACTIVE(consDeactiveLinking) 3154 { /*lint --e{715}*/ 3155 SCIP_CONSDATA* consdata; 3156 3157 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 3158 assert(SCIPconsIsTransformed(cons)); 3159 3160 /* get constraint data */ 3161 consdata = SCIPconsGetData(cons); 3162 assert(consdata != NULL); 3163 3164 /* remove row from NLP, if still in solving 3165 * if we are in exitsolve, the whole NLP will be freed anyway 3166 */ 3167 if( SCIPgetStage(scip) == SCIP_STAGE_SOLVING && consdata->nlrow1 != NULL ) 3168 { 3169 assert(consdata->nlrow2 != NULL); 3170 SCIP_CALL( SCIPdelNlRow(scip, consdata->nlrow1) ); 3171 SCIP_CALL( SCIPdelNlRow(scip, consdata->nlrow2) ); 3172 } 3173 3174 return SCIP_OKAY; 3175 } 3176 3177 /** constraint enabling notification method of constraint handler */ 3178 static 3179 SCIP_DECL_CONSENABLE(consEnableLinking) 3180 { /*lint --e{715}*/ 3181 #if 0 3182 SCIP_CONSHDLRDATA* conshdlrdata; 3183 SCIP_CONSDATA* consdata; 3184 3185 conshdlrdata = SCIPconshdlrGetData(conshdlr); 3186 assert(conshdlrdata != NULL); 3187 3188 consdata = SCIPconsGetData(cons); 3189 assert(consdata != NULL); 3190 3191 if( consdata->nbinvars <= 1 ) 3192 { 3193 SCIP_CALL( SCIPdisableCons(scip, cons) ); 3194 assert(consdata->nbinvars == 0 || SCIPvarGetLbGlobal(consdata->binvars[0]) > 0.5); 3195 } 3196 else if( conshdlrdata->linearize ) 3197 { 3198 SCIP_CALL( consdataLinearize(scip, cons, consdata) ); 3199 SCIP_CALL( SCIPdelCons(scip, cons) ); 3200 } 3201 #endif 3202 return SCIP_OKAY; 3203 } 3204 3205 /** constraint display method of constraint handler */ 3206 static 3207 SCIP_DECL_CONSPRINT(consPrintLinking) 3208 { /*lint --e{715}*/ 3209 assert(scip != NULL); 3210 assert(conshdlr != NULL); 3211 assert(cons != NULL); 3212 3213 SCIP_CALL( consdataPrint(scip, SCIPconsGetData(cons), file) ); 3214 3215 return SCIP_OKAY; 3216 } 3217 3218 3219 /** constraint copying method of constraint handler */ 3220 static 3221 SCIP_DECL_CONSCOPY(consCopyLinking) 3222 { /*lint --e{715}*/ 3223 SCIP_CONSDATA* sourceconsdata; 3224 SCIP_VAR** binvars; 3225 SCIP_VAR* linkvar; 3226 SCIP_Real* vals; 3227 const char* consname; 3228 int nbinvars; 3229 int v; 3230 3231 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(sourcecons)), CONSHDLR_NAME) != 0 ) 3232 { 3233 SCIPerrorMessage("constraint is not a linking constraint\n"); 3234 SCIPABORT(); 3235 return SCIP_INVALIDDATA; /*lint !e527*/ 3236 } 3237 3238 (*valid) = TRUE; 3239 3240 sourceconsdata = SCIPconsGetData(sourcecons); 3241 assert(sourceconsdata != NULL); 3242 3243 /* get number of binary variables, linking variables */ 3244 nbinvars = sourceconsdata->nbinvars; 3245 linkvar = sourceconsdata->linkvar; 3246 3247 /* duplicate variable array */ 3248 if( nbinvars > 0 ) 3249 { 3250 SCIP_CALL( SCIPduplicateBufferArray(scip, &binvars, sourceconsdata->binvars, nbinvars) ); 3251 SCIP_CALL( SCIPduplicateBufferArray(scip, &vals, sourceconsdata->vals, nbinvars) ); 3252 } 3253 else 3254 { 3255 binvars = NULL; 3256 vals = NULL; 3257 } 3258 3259 /* get copy for the binary variables */ 3260 for( v = 0; v < nbinvars && *valid; ++v ) 3261 { 3262 assert(binvars != NULL); /* for flexelint */ 3263 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, binvars[v], &binvars[v], varmap, consmap, global, valid) ); 3264 assert(!(*valid) || binvars[v] != NULL); 3265 } 3266 3267 /* copy the linking variable */ 3268 if( *valid ) 3269 { 3270 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, linkvar, &linkvar, varmap, consmap, global, valid) ); 3271 assert(!(*valid) || linkvar != NULL); 3272 } 3273 3274 /* only create the target constraint, if all variables could be copied */ 3275 if( *valid ) 3276 { 3277 if( name != NULL ) 3278 consname = name; 3279 else 3280 consname = SCIPconsGetName(sourcecons); 3281 3282 SCIP_CALL( SCIPcreateConsLinking(scip, cons, consname, linkvar, binvars, vals, nbinvars, 3283 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) ); 3284 } 3285 3286 /* free buffer array */ 3287 if( nbinvars > 0 ) 3288 { 3289 SCIPfreeBufferArrayNull(scip, &vals); 3290 SCIPfreeBufferArrayNull(scip, &binvars); 3291 } 3292 3293 return SCIP_OKAY; 3294 } 3295 3296 /** constraint parsing method of constraint handler */ 3297 static 3298 SCIP_DECL_CONSPARSE(consParseLinking) 3299 { /*lint --e{715}*/ 3300 SCIP_VAR** binvars; 3301 SCIP_VAR* linkvar; 3302 SCIP_Real* vals; 3303 char* endptr; 3304 int varssize; 3305 int nbinvars; 3306 3307 assert(scip != NULL); 3308 assert(success != NULL); 3309 assert(str != NULL); 3310 assert(name != NULL); 3311 assert(cons != NULL); 3312 3313 *success = TRUE; 3314 3315 /* parse linking variable */ 3316 SCIP_CALL( SCIPparseVarName(scip, str, &linkvar, &endptr) ); 3317 3318 if( linkvar == NULL ) 3319 { 3320 SCIPerrorMessage("unknown variable name at '%s'\n", str); 3321 *success = FALSE; 3322 return SCIP_OKAY; 3323 } 3324 3325 /* find "==" */ 3326 endptr = strchr(endptr, '='); 3327 3328 /* if the string end has been reached without finding the "==" */ 3329 if( endptr == NULL ) 3330 { 3331 SCIPerrorMessage("Could not find initializing '='.\n"); 3332 *success = FALSE; 3333 return SCIP_OKAY; 3334 } 3335 3336 str = endptr; 3337 3338 /* skip "==" */ 3339 str += *(str+1) == '=' ? 2 : 1; 3340 3341 /* skip whitespace */ 3342 SCIP_CALL( SCIPskipSpace((char**)&str) ); 3343 3344 nbinvars = 0; 3345 varssize = 16; 3346 SCIP_CALL( SCIPallocBufferArray(scip, &binvars, varssize) ); 3347 SCIP_CALL( SCIPallocBufferArray(scip, &vals, varssize) ); 3348 3349 /* check for the string "no binary variables yet" */ 3350 if( strncmp(str, "no binary variables yet", 24) != 0 ) 3351 { 3352 int requsize; 3353 int v; 3354 3355 /* parse linear sum to get variables and coefficients */ 3356 SCIP_CALL( SCIPparseVarsLinearsum(scip, str, binvars, vals, &nbinvars, varssize, &requsize, &endptr, success) ); 3357 3358 if( *success && requsize > varssize ) 3359 { 3360 /* realloc buffers and try again */ 3361 varssize = requsize; 3362 SCIP_CALL( SCIPreallocBufferArray(scip, &binvars, varssize) ); 3363 SCIP_CALL( SCIPreallocBufferArray(scip, &vals, varssize) ); 3364 3365 SCIP_CALL( SCIPparseVarsLinearsum(scip, str, binvars, vals, &nbinvars, varssize, &requsize, &endptr, success) ); 3366 assert(!*success || requsize <= varssize); /* if successful, then should have had enough space now */ 3367 } 3368 3369 /* check coefficients */ 3370 if( *success ) 3371 { 3372 /* convert SCIP_Real to integer */ 3373 for( v = 0; v < nbinvars; ++v ) 3374 { 3375 if( SCIPisIntegral(scip, vals[v]) ) 3376 vals[v] = SCIPconvertRealToInt(scip, vals[v]); 3377 } 3378 } 3379 } 3380 3381 if( *success ) 3382 { 3383 SCIP_CALL( SCIPcreateConsLinking(scip, cons, name, linkvar, binvars, vals, nbinvars, 3384 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) ); 3385 } 3386 3387 SCIPfreeBufferArray(scip, &vals); 3388 SCIPfreeBufferArray(scip, &binvars); 3389 3390 return SCIP_OKAY; 3391 } 3392 3393 /** constraint method of constraint handler which returns the variables (if possible) */ 3394 static 3395 SCIP_DECL_CONSGETVARS(consGetVarsLinking) 3396 { /*lint --e{715}*/ 3397 SCIP_CONSDATA* consdata; 3398 3399 consdata = SCIPconsGetData(cons); 3400 assert(consdata != NULL); 3401 3402 if( varssize < consdata->nbinvars + 1) 3403 (*success) = FALSE; 3404 else 3405 { 3406 assert(vars != NULL); 3407 3408 BMScopyMemoryArray(vars, consdata->binvars, consdata->nbinvars); 3409 vars[consdata->nbinvars] = consdata->linkvar; 3410 (*success) = TRUE; 3411 } 3412 3413 return SCIP_OKAY; 3414 } 3415 3416 /** constraint method of constraint handler which returns the number of variables (if possible) */ 3417 static 3418 SCIP_DECL_CONSGETNVARS(consGetNVarsLinking) 3419 { /*lint --e{715}*/ 3420 SCIP_CONSDATA* consdata; 3421 3422 consdata = SCIPconsGetData(cons); 3423 assert(consdata != NULL); 3424 3425 (*nvars) = consdata->nbinvars + 1; 3426 (*success) = TRUE; 3427 3428 return SCIP_OKAY; 3429 } 3430 3431 /** constraint handler method which returns the permutation symmetry detection graph of a constraint */ 3432 static 3433 SCIP_DECL_CONSGETPERMSYMGRAPH(consGetPermsymGraphLinking) 3434 { /*lint --e{715}*/ 3435 SCIP_CALL( addSymmetryInformation(scip, SYM_SYMTYPE_PERM, cons, graph, success) ); 3436 3437 return SCIP_OKAY; 3438 } 3439 3440 /** constraint handler method which returns the signed permutation symmetry detection graph of a constraint */ 3441 static 3442 SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(consGetSignedPermsymGraphLinking) 3443 { /*lint --e{715}*/ 3444 SCIP_CALL( addSymmetryInformation(scip, SYM_SYMTYPE_SIGNPERM, cons, graph, success) ); 3445 3446 return SCIP_OKAY; 3447 } 3448 3449 /* 3450 * Callback methods of event handler 3451 */ 3452 3453 /** execution method of event handler */ 3454 static 3455 SCIP_DECL_EVENTEXEC(eventExecBinvar) 3456 { /*lint --e{715}*/ 3457 SCIP_CONSDATA* consdata; 3458 SCIP_EVENTTYPE eventtype; 3459 3460 assert(eventhdlr != NULL); 3461 assert(eventdata != NULL); 3462 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0); 3463 assert(event != NULL); 3464 3465 consdata = (SCIP_CONSDATA*)eventdata; 3466 assert(consdata != NULL); 3467 3468 eventtype = SCIPeventGetType(event); 3469 switch( eventtype ) 3470 { 3471 case SCIP_EVENTTYPE_LBTIGHTENED: 3472 consdata->nfixedones++; 3473 break; 3474 case SCIP_EVENTTYPE_LBRELAXED: 3475 consdata->nfixedones--; 3476 consdata->firstnonfixed = 0; 3477 consdata->lastnonfixed = consdata->nbinvars - 1; 3478 break; 3479 case SCIP_EVENTTYPE_UBTIGHTENED: 3480 consdata->nfixedzeros++; 3481 break; 3482 case SCIP_EVENTTYPE_UBRELAXED: 3483 consdata->firstnonfixed = 0; 3484 consdata->lastnonfixed = consdata->nbinvars - 1; 3485 consdata->nfixedzeros--; 3486 break; 3487 default: 3488 SCIPerrorMessage("invalid event type\n"); 3489 return SCIP_INVALIDDATA; 3490 } 3491 assert(0 <= consdata->nfixedzeros && consdata->nfixedzeros <= consdata->nbinvars); 3492 assert(0 <= consdata->nfixedones && consdata->nfixedones <= consdata->nbinvars); 3493 3494 /*debugMsg(scip, " -> constraint has %d zero-fixed and %d one-fixed of %d variables\n", 3495 consdata->nfixedzeros, consdata->nfixedones, consdata->nvars);*/ 3496 3497 return SCIP_OKAY; 3498 } 3499 3500 /* 3501 * constraint specific interface methods 3502 */ 3503 3504 /** creates the handler for linking constraints and includes it in SCIP */ 3505 SCIP_RETCODE SCIPincludeConshdlrLinking( 3506 SCIP* scip /**< SCIP data structure */ 3507 ) 3508 { 3509 SCIP_CONSHDLRDATA* conshdlrdata; 3510 SCIP_CONSHDLR* conshdlr; 3511 SCIP_EVENTHDLR* eventhdlr; 3512 3513 /* create event handler for bound change events */ 3514 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, 3515 eventExecBinvar, NULL) ); 3516 3517 /* create linking constraint handler data */ 3518 SCIP_CALL( conshdlrdataCreate(scip, &conshdlrdata, eventhdlr) ); 3519 3520 /* include constraint handler */ 3521 SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC, 3522 CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY, CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS, 3523 consEnfolpLinking, consEnfopsLinking, consCheckLinking, consLockLinking, 3524 conshdlrdata) ); 3525 3526 assert(conshdlr != NULL); 3527 3528 /* set non-fundamental callbacks via specific setter functions */ 3529 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyLinking, consCopyLinking) ); 3530 SCIP_CALL( SCIPsetConshdlrActive(scip, conshdlr, consActiveLinking) ); 3531 SCIP_CALL( SCIPsetConshdlrDeactive(scip, conshdlr, consDeactiveLinking) ); 3532 SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteLinking) ); 3533 SCIP_CALL( SCIPsetConshdlrEnable(scip, conshdlr, consEnableLinking) ); 3534 SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolLinking) ); 3535 SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolLinking) ); 3536 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeLinking) ); 3537 SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsLinking) ); 3538 SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsLinking) ); 3539 SCIP_CALL( SCIPsetConshdlrInitpre(scip, conshdlr, consInitpreLinking) ); 3540 SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpLinking) ); 3541 SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseLinking) ); 3542 SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolLinking, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) ); 3543 SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintLinking) ); 3544 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropLinking, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP, 3545 CONSHDLR_PROP_TIMING) ); 3546 SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropLinking) ); 3547 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpLinking, consSepasolLinking, CONSHDLR_SEPAFREQ, 3548 CONSHDLR_SEPAPRIORITY, CONSHDLR_DELAYSEPA) ); 3549 SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransLinking) ); 3550 SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxLinking) ); 3551 SCIP_CALL( SCIPsetConshdlrGetPermsymGraph(scip, conshdlr, consGetPermsymGraphLinking) ); 3552 SCIP_CALL( SCIPsetConshdlrGetSignedPermsymGraph(scip, conshdlr, consGetSignedPermsymGraphLinking) ); 3553 3554 /* include the linear constraint to linking constraint upgrade in the linear constraint handler */ 3555 /* SCIP_CALL( SCIPincludeLinconsUpgrade(scip, linconsUpgdLinking, LINCONSUPGD_PRIORITY, CONSHDLR_NAME) ); */ 3556 3557 /* add linking constraint handler parameters */ 3558 SCIP_CALL( SCIPaddBoolParam(scip, 3559 "constraints/" CONSHDLR_NAME "/linearize", "this constraint will not propagate or separate, linear and setppc are used?", 3560 &conshdlrdata->linearize, FALSE, DEFAULT_LINEARIZE, NULL, NULL) ); 3561 3562 return SCIP_OKAY; 3563 } 3564 3565 /** creates and captures a linking constraint 3566 * 3567 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 3568 */ 3569 SCIP_RETCODE SCIPcreateConsLinking( 3570 SCIP* scip, /**< SCIP data structure */ 3571 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 3572 const char* name, /**< name of constraint */ 3573 SCIP_VAR* linkvar, /**< linking variable (continuous or integer) which should be linked */ 3574 SCIP_VAR** binvars, /**< binary variables */ 3575 SCIP_Real* vals, /**< coefficients of the binary variables */ 3576 int nbinvars, /**< number of binary starting variables */ 3577 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? 3578 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */ 3579 SCIP_Bool separate, /**< should the constraint be separated during LP processing? 3580 * Usually set to TRUE. */ 3581 SCIP_Bool enforce, /**< should the constraint be enforced during node processing? 3582 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 3583 SCIP_Bool check, /**< should the constraint be checked for feasibility? 3584 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 3585 SCIP_Bool propagate, /**< should the constraint be propagated during node processing? 3586 * Usually set to TRUE. */ 3587 SCIP_Bool local, /**< is constraint only valid locally? 3588 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */ 3589 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)? 3590 * Usually set to FALSE. In column generation applications, set to TRUE if pricing 3591 * adds coefficients to this constraint. */ 3592 SCIP_Bool dynamic, /**< is constraint subject to aging? 3593 * Usually set to FALSE. Set to TRUE for own cuts which 3594 * are separated as constraints. */ 3595 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? 3596 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */ 3597 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even 3598 * if it may be moved to a more global node? 3599 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */ 3600 ) 3601 { 3602 SCIP_CONSHDLR* conshdlr; 3603 SCIP_CONSDATA* consdata; 3604 SCIP_CONSHDLRDATA* conshdlrdata; 3605 int k; 3606 3607 assert(scip != NULL); 3608 assert(!SCIPisInfinity(scip, -SCIPvarGetLbGlobal(linkvar))); 3609 assert(!SCIPisInfinity(scip, SCIPvarGetUbGlobal(linkvar))); 3610 3611 /* find the linking constraint handler */ 3612 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME); 3613 if( conshdlr == NULL ) 3614 { 3615 SCIPerrorMessage("linking constraint handler not found\n"); 3616 return SCIP_PLUGINNOTFOUND; 3617 } 3618 3619 SCIPdebugMsg(scip, "create linking constraint for variable <%s> with %d binary variables (SCIP stage %d)\n", 3620 SCIPvarGetName(linkvar), nbinvars, SCIPgetStage(scip)); 3621 for( k = 0; k < nbinvars; k++ ) 3622 { 3623 SCIPdebugMsg(scip, "Var %d : <%s>\n", k, SCIPvarGetName(binvars[k])); 3624 } 3625 3626 /* get constraint handler data */ 3627 conshdlrdata = SCIPconshdlrGetData(conshdlr); 3628 assert(conshdlrdata != NULL); 3629 3630 if( conshdlrdata->varmap == NULL ) 3631 { 3632 SCIP_CALL( SCIPhashmapCreate(&conshdlrdata->varmap, SCIPblkmem(scip), HASHSIZE_BINVARSCONS) ); 3633 } 3634 assert(conshdlrdata->varmap != NULL); 3635 3636 /* check if the linking for the requests linking variable already exists */ 3637 assert(!SCIPhashmapExists(conshdlrdata->varmap, getHashmapKey(linkvar))); 3638 3639 /* create the constraint specific data */ 3640 SCIP_CALL( consdataCreate(scip, conshdlrdata->eventhdlr, &consdata, linkvar, binvars, vals, nbinvars) ); 3641 3642 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, 3643 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) ); 3644 3645 /* create binary variables for the real domain */ 3646 if( nbinvars == 0 ) 3647 { 3648 SCIP_CALL( consdataCreateBinvars(scip, *cons, consdata, conshdlrdata->eventhdlr, conshdlrdata->linearize) ); 3649 } 3650 3651 /* insert linking constraint into the hash map */ 3652 SCIP_CALL( SCIPhashmapInsert(conshdlrdata->varmap, getHashmapKey(linkvar), *cons) ); 3653 assert(SCIPhashmapExists(conshdlrdata->varmap, getHashmapKey(linkvar))); 3654 3655 return SCIP_OKAY; 3656 } 3657 3658 /** creates and captures a linking constraint 3659 * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the 3660 * method SCIPcreateConsLinking(); all flags can be set via SCIPsetCons<Flagname>-methods in scip.h 3661 * 3662 * @see SCIPcreateConsLinking() for information about the basic constraint flag configuration 3663 * 3664 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 3665 */ 3666 SCIP_RETCODE SCIPcreateConsBasicLinking( 3667 SCIP* scip, /**< SCIP data structure */ 3668 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 3669 const char* name, /**< name of constraint */ 3670 SCIP_VAR* linkvar, /**< linking variable (continuous or integer) which should be linked */ 3671 SCIP_VAR** binvars, /**< binary variables, or NULL */ 3672 SCIP_Real* vals, /**< coefficients of the binary variables */ 3673 int nbinvars /**< number of binary variables */ 3674 ) 3675 { 3676 assert(scip != NULL); 3677 3678 SCIP_CALL( SCIPcreateConsLinking(scip, cons, name, linkvar, binvars, vals, nbinvars, 3679 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 3680 3681 return SCIP_OKAY; 3682 } 3683 3684 /** checks if for the given linking variable (continuous or integer) a linking constraint exists */ 3685 SCIP_Bool SCIPexistsConsLinking( 3686 SCIP* scip, /**< SCIP data structure */ 3687 SCIP_VAR* linkvar /**< linking variable (continuous or integer) which should be linked */ 3688 ) 3689 { 3690 SCIP_CONSHDLR* conshdlr; 3691 SCIP_CONSHDLRDATA* conshdlrdata; 3692 3693 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME); 3694 assert(conshdlr != NULL); 3695 3696 conshdlrdata = SCIPconshdlrGetData(conshdlr); 3697 assert(conshdlrdata != NULL); 3698 3699 return (conshdlrdata->varmap != NULL) && SCIPhashmapExists(conshdlrdata->varmap, getHashmapKey(linkvar)); 3700 } 3701 3702 /** returns the linking constraint belonging the given linking variable (continuous or integer) or NULL if it does not exist yet */ 3703 SCIP_CONS* SCIPgetConsLinking( 3704 SCIP* scip, /**< SCIP data structure */ 3705 SCIP_VAR* linkvar /**< linking variable (continuous or integer) which should be linked */ 3706 ) 3707 { 3708 SCIP_CONSHDLR* conshdlr; 3709 SCIP_CONSHDLRDATA* conshdlrdata; 3710 3711 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME); 3712 assert(conshdlr != NULL); 3713 3714 conshdlrdata = SCIPconshdlrGetData(conshdlr); 3715 assert(conshdlrdata != NULL); 3716 3717 if( conshdlrdata->varmap != NULL ) 3718 return (SCIP_CONS*) SCIPhashmapGetImage(conshdlrdata->varmap, getHashmapKey(linkvar)); 3719 else 3720 return NULL; 3721 } 3722 3723 /** returns the linking variable (continuous or integer) of the linking constraint */ 3724 SCIP_VAR* SCIPgetLinkvarLinking( 3725 SCIP* scip, /**< SCIP data structure */ 3726 SCIP_CONS* cons /**< linking constraint */ 3727 ) 3728 { 3729 SCIP_CONSDATA* consdata; 3730 3731 assert(scip != NULL); 3732 3733 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 ) 3734 { 3735 SCIPerrorMessage("constraint is not a " CONSHDLR_NAME " constraint\n"); 3736 SCIPABORT(); 3737 return NULL; /*lint !e527*/ 3738 } 3739 3740 consdata = SCIPconsGetData(cons); 3741 assert(consdata != NULL); 3742 3743 return consdata->linkvar; 3744 } 3745 3746 /** returns the binary variables of the linking constraint */ 3747 SCIP_RETCODE SCIPgetBinvarsLinking( 3748 SCIP* scip, /**< SCIP data structure */ 3749 SCIP_CONS* cons, /**< linking constraint */ 3750 SCIP_VAR*** binvars, /**< pointer to store the binary variables array pointer */ 3751 int* nbinvars /**< pointer to store the number of returned binary variables */ 3752 ) 3753 { 3754 SCIP_CONSDATA* consdata; 3755 3756 assert(scip != NULL); 3757 3758 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 ) 3759 { 3760 SCIPerrorMessage("constraint is not a " CONSHDLR_NAME " constraint\n"); 3761 SCIPABORT(); 3762 return SCIP_INVALIDDATA; /*lint !e527*/ 3763 } 3764 3765 consdata = SCIPconsGetData(cons); 3766 assert(consdata != NULL); 3767 3768 if( consdata->binvars == NULL ) 3769 { 3770 SCIP_CONSHDLR* conshdlr; 3771 SCIP_CONSHDLRDATA* conshdlrdata; 3772 3773 conshdlr = SCIPconsGetHdlr(cons); 3774 assert(conshdlr != NULL); 3775 3776 conshdlrdata = SCIPconshdlrGetData(conshdlr); 3777 assert(conshdlrdata != NULL); 3778 3779 SCIP_CALL( consdataCreateBinvars(scip, cons, consdata, conshdlrdata->eventhdlr, conshdlrdata->linearize) ); 3780 } 3781 3782 assert(consdata->binvars != NULL); 3783 3784 if( binvars != NULL ) 3785 (*binvars) = consdata->binvars; 3786 if( nbinvars != NULL ) 3787 (*nbinvars) = consdata->nbinvars; 3788 3789 return SCIP_OKAY; 3790 } 3791 3792 /** returns the number of binary variables of the linking constraint */ 3793 int SCIPgetNBinvarsLinking( 3794 SCIP* scip, /**< SCIP data structure */ 3795 SCIP_CONS* cons /**< linking constraint */ 3796 ) 3797 { 3798 SCIP_CONSDATA* consdata; 3799 3800 assert(scip != NULL); 3801 3802 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 ) 3803 { 3804 SCIPerrorMessage("constraint is not a " CONSHDLR_NAME " constraint\n"); 3805 SCIPABORT(); 3806 return -1; /*lint !e527*/ 3807 } 3808 3809 consdata = SCIPconsGetData(cons); 3810 assert(consdata != NULL); 3811 3812 return consdata->nbinvars; 3813 } 3814 3815 /** returns the coefficients of the binary variables */ 3816 SCIP_Real* SCIPgetValsLinking( 3817 SCIP* scip, /**< SCIP data structure */ 3818 SCIP_CONS* cons /**< linking constraint */ 3819 ) 3820 { 3821 SCIP_CONSDATA* consdata; 3822 3823 assert(scip != NULL); 3824 3825 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 ) 3826 { 3827 SCIPerrorMessage("constraint is not a " CONSHDLR_NAME " constraint\n"); 3828 SCIPABORT(); 3829 return NULL; /*lint !e527*/ 3830 } 3831 3832 consdata = SCIPconsGetData(cons); 3833 assert(consdata != NULL); 3834 consdataSort(consdata); 3835 3836 return consdata->vals; 3837 } 3838 3839 /** return all binary variable information of the linking constraint */ 3840 SCIP_RETCODE SCIPgetBinvarsDataLinking( 3841 SCIP_CONS* cons, /**< linking constraint */ 3842 SCIP_VAR*** binvars, /**< pointer to store binary variables, or NULL */ 3843 SCIP_Real** vals, /**< pointer to store the binary coefficients, or NULL */ 3844 int* nbinvars /**< pointer to store the number of binary variables, or NULL */ 3845 ) 3846 { 3847 SCIP_CONSDATA* consdata; 3848 3849 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 ) 3850 { 3851 SCIPerrorMessage("constraint is not a " CONSHDLR_NAME " constraint\n"); 3852 SCIPABORT(); 3853 return SCIP_ERROR; 3854 } 3855 3856 consdata = SCIPconsGetData(cons); 3857 assert(consdata != NULL); 3858 3859 consdataSort(consdata); 3860 3861 if( binvars != NULL ) 3862 *binvars = consdata->binvars; 3863 if( vals != NULL ) 3864 *vals = consdata->vals; 3865 if( nbinvars != NULL ) 3866 *nbinvars = consdata->nbinvars; 3867 3868 return SCIP_OKAY; 3869 } 3870