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_cardinality.c 26 * @ingroup DEFPLUGINS_CONS 27 * @brief constraint handler for cardinality constraints 28 * @author Tobias Fischer 29 * 30 * This constraint handler handles cardinality constraints of the form 31 * \f[ 32 * |\mbox{supp}(x)| \leq b 33 * \f] 34 * with integer right-hand side \f$b\f$. Here, \f$|\mbox{supp}(x)|\f$ denotes the number of nonzero entries of the 35 * vector \f$x\f$. 36 * 37 * Note that cardinality constraints generalize special ordered set of type one (SOS1) constraints in which \f$b = 1\f$. 38 * 39 * The implementation of this constraint handler is based on@n 40 * "On the Structure of Linear Programs with Overlapping Cardinality Constraints"@n 41 * T. Fischer and M. E. Pfetsch, Tech. rep., 2016 42 */ 43 44 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 45 46 #include "blockmemshell/memory.h" 47 #include "scip/cons_cardinality.h" 48 #include "scip/cons_knapsack.h" 49 #include "scip/cons_linear.h" 50 #include "scip/pub_cons.h" 51 #include "scip/pub_event.h" 52 #include "scip/pub_lp.h" 53 #include "scip/pub_message.h" 54 #include "scip/pub_misc.h" 55 #include "scip/pub_misc_sort.h" 56 #include "scip/pub_var.h" 57 #include "scip/scip_branch.h" 58 #include "scip/scip_cons.h" 59 #include "scip/scip_copy.h" 60 #include "scip/scip_cut.h" 61 #include "scip/scip_event.h" 62 #include "scip/scip_general.h" 63 #include "scip/scip_lp.h" 64 #include "scip/scip_mem.h" 65 #include "scip/scip_message.h" 66 #include "scip/scip_numerics.h" 67 #include "scip/scip_param.h" 68 #include "scip/scip_prob.h" 69 #include "scip/scip_sol.h" 70 #include "scip/scip_solvingstats.h" 71 #include "scip/scip_tree.h" 72 #include "scip/scip_var.h" 73 #include "scip/symmetry_graph.h" 74 #include "symmetry/struct_symmetry.h" 75 #include <ctype.h> 76 #include <stdlib.h> 77 #include <string.h> 78 79 /* constraint handler properties */ 80 #define CONSHDLR_NAME "cardinality" 81 #define CONSHDLR_DESC "cardinality constraint handler" 82 #define CONSHDLR_SEPAPRIORITY 10 /**< priority of the constraint handler for separation */ 83 #define CONSHDLR_ENFOPRIORITY 100 /**< priority of the constraint handler for constraint enforcing */ 84 #define CONSHDLR_CHECKPRIORITY -10 /**< priority of the constraint handler for checking feasibility */ 85 #define CONSHDLR_SEPAFREQ 10 /**< frequency for separating cuts; zero means to separate only in the root node */ 86 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */ 87 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation, 88 * propagation and enforcement, -1 for no eager evaluations, 0 for first only */ 89 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in 90 * (-1: no limit) */ 91 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */ 92 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */ 93 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */ 94 95 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP 96 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_FAST 97 98 /* branching rules */ 99 #define DEFAULT_BRANCHBALANCED FALSE /**< whether to use balanced instead of unbalanced branching */ 100 #define DEFAULT_BALANCEDDEPTH 20 /**< maximum depth for using balanced branching (-1: no limit) */ 101 #define DEFAULT_BALANCEDCUTOFF 2.0 /**< determines that balanced branching is only used if the branching cut off value 102 * w.r.t. the current LP solution is greater than a given value */ 103 104 /* event handler properties */ 105 #define EVENTHDLR_NAME "cardinality" 106 #define EVENTHDLR_DESC "bound change event handler for cardinality constraints" 107 108 #define EVENTHDLR_EVENT_TYPE (SCIP_EVENTTYPE_BOUNDCHANGED | SCIP_EVENTTYPE_GBDCHANGED) 109 110 111 /** constraint data for cardinality constraints */ 112 struct SCIP_ConsData 113 { 114 SCIP_CONS* cons; /**< cardinality constraint */ 115 int cardval; /**< number of variables that the constraint allows to be nonzero */ 116 int nvars; /**< number of variables in the constraint */ 117 int maxvars; /**< maximal number of variables (= size of storage) */ 118 int ntreatnonzeros; /**< number of variables in constraint that are either known to be nonzero 119 * (because zero is not in variable domain) or may be treated as nonzero */ 120 SCIP_EVENTDATA** eventdatascurrent; /**< event datas for current bound change events */ 121 SCIP_VAR** eventvarscurrent; /**< event variables for current bound change events */ 122 int neventdatascurrent; /**< number of current bound change events */ 123 SCIP_EVENTDATA** eventdatas; /**< event data array for bound change events */ 124 SCIP_VAR** vars; /**< variables in constraint */ 125 SCIP_VAR** indvars; /**< indicator variables that indicate which variables may be treated as 126 * nonzero in cardinality constraint */ 127 SCIP_Real* weights; /**< weights determining the order (ascending), or NULL if not used */ 128 SCIP_ROW* rowlb; /**< row corresponding to lower bounds, or NULL if not yet created */ 129 SCIP_ROW* rowub; /**< row corresponding to upper bounds, or NULL if not yet created */ 130 }; 131 132 /** cardinality constraint handler data */ 133 struct SCIP_ConshdlrData 134 { 135 SCIP_HASHMAP* varhash; /**< hash map from implied variable to (binary) indicator variable */ 136 SCIP_Bool branchbalanced; /**< whether to use balanced instead of unbalanced branching */ 137 int balanceddepth; /**< maximum depth for using balanced branching (-1: no limit) */ 138 SCIP_Real balancedcutoff; /**< determines that balanced branching is only used if the branching cut off 139 * value w.r.t. the current LP solution is greater than a given value */ 140 SCIP_EVENTHDLR* eventhdlr; /**< event handler for bound change events */ 141 }; 142 143 /** event data for bound changes events */ 144 struct SCIP_EventData 145 { 146 SCIP_CONSDATA* consdata; /**< cardinality constraint data to process the bound change for */ 147 SCIP_VAR* var; /**< implied variable */ 148 SCIP_VAR* indvar; /**< indicator variable */ 149 unsigned int pos:30; /**< position in constraint */ 150 unsigned int varmarked:1; /**< whether implied variable is marked for propagation */ 151 unsigned int indvarmarked:1; /**< whether indicator variable is marked for propagation */ 152 }; 153 154 /** catches bound change events for a variable and its indicator variable */ 155 static 156 SCIP_RETCODE catchVarEventCardinality( 157 SCIP* scip, /**< SCIP data structure */ 158 SCIP_EVENTHDLR* eventhdlr, /**< event handler for bound change events */ 159 SCIP_CONSDATA* consdata, /**< constraint data */ 160 SCIP_VAR* var, /**< implied variable */ 161 SCIP_VAR* indvar, /**< indicator variable */ 162 int pos, /**< position in constraint */ 163 SCIP_EVENTDATA** eventdata /**< pointer to store event data for bound change events */ 164 ) 165 { 166 assert(eventhdlr != NULL); 167 assert(consdata != NULL); 168 assert(var != NULL); 169 assert(indvar != NULL); 170 assert(pos >= 0); 171 172 /* create event data of indicator variable */ 173 SCIP_CALL( SCIPallocBlockMemory(scip, eventdata) ); 174 175 (*eventdata)->consdata = consdata; 176 (*eventdata)->var = var; 177 (*eventdata)->indvar = indvar; 178 (*eventdata)->varmarked = FALSE; 179 (*eventdata)->indvarmarked = FALSE; 180 (*eventdata)->pos = (unsigned int)pos; 181 182 /* catch bound change events of each variable */ 183 SCIP_CALL( SCIPcatchVarEvent(scip, var, EVENTHDLR_EVENT_TYPE, eventhdlr, *eventdata, NULL) ); 184 SCIP_CALL( SCIPcatchVarEvent(scip, indvar, SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr, *eventdata, NULL) ); 185 186 return SCIP_OKAY; 187 } 188 189 /** drops bound change events for a variable and its indicator variable */ 190 static 191 SCIP_RETCODE dropVarEventCardinality( 192 SCIP* scip, /**< SCIP data structure */ 193 SCIP_EVENTHDLR* eventhdlr, /**< event handler for bound change events */ 194 SCIP_CONSDATA* consdata, /**< constraint data */ 195 SCIP_VAR* var, /**< implied variable */ 196 SCIP_VAR* indvar, /**< indicator variable */ 197 SCIP_EVENTDATA** eventdata /**< pointer of event data for bound change events */ 198 ) 199 { 200 assert(eventhdlr != NULL); 201 assert(consdata != NULL); 202 assert(var != NULL); 203 assert(indvar != NULL); 204 assert(eventdata != NULL); 205 206 /* drop bound change events of each variable */ 207 SCIP_CALL( SCIPdropVarEvent(scip, var, EVENTHDLR_EVENT_TYPE, eventhdlr, *eventdata, -1) ); 208 SCIP_CALL( SCIPdropVarEvent(scip, indvar, SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr, *eventdata, -1) ); 209 210 /* free event data of indicator variable */ 211 SCIPfreeBlockMemory(scip, eventdata); 212 *eventdata = NULL; 213 214 return SCIP_OKAY; 215 } 216 217 /** fix variable in given node to 0 or add constraint if variable is multi-aggregated 218 * 219 * @todo Try to handle multi-aggregated variables as in \ref fixVariableZero() below. 220 */ 221 static 222 SCIP_RETCODE fixVariableZeroNode( 223 SCIP* scip, /**< SCIP pointer */ 224 SCIP_VAR* var, /**< variable to be fixed to 0 */ 225 SCIP_NODE* node, /**< node */ 226 SCIP_Bool* infeasible /**< pointer to store if fixing is infeasible */ 227 ) 228 { 229 /* if variable cannot be nonzero */ 230 *infeasible = FALSE; 231 if( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var)) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(var)) ) 232 { 233 *infeasible = TRUE; 234 return SCIP_OKAY; 235 } 236 237 /* if variable is multi-aggregated */ 238 if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR ) 239 { 240 SCIP_CONS* cons; 241 SCIP_Real val; 242 243 val = 1.0; 244 245 if( !SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) || !SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) ) 246 { 247 SCIPdebugMsg(scip, "creating constraint to force multi-aggregated variable <%s> to 0.\n", SCIPvarGetName(var)); 248 249 /* we have to insert a local constraint var = 0 */ 250 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, "branch", 1, &var, &val, 0.0, 0.0, TRUE, TRUE, TRUE, TRUE, TRUE, 251 TRUE, FALSE, FALSE, FALSE, FALSE) ); 252 SCIP_CALL( SCIPaddConsNode(scip, node, cons, NULL) ); 253 SCIP_CALL( SCIPreleaseCons(scip, &cons) ); 254 } 255 } 256 else 257 { 258 if ( ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) ) 259 { 260 SCIP_CALL( SCIPchgVarLbNode(scip, node, var, 0.0) ); 261 } 262 if ( ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) ) 263 { 264 SCIP_CALL( SCIPchgVarUbNode(scip, node, var, 0.0) ); 265 } 266 } 267 268 return SCIP_OKAY; 269 } 270 271 /** try to fix variable to 0 272 * 273 * Try to treat fixing by special consideration of multiaggregated variables. For a multi-aggregation 274 * \f[ 275 * x = \sum_{i=1}^n \alpha_i x_i + c, 276 * \f] 277 * we can express the fixing \f$x = 0\f$ by fixing all \f$x_i\f$ to 0 if \f$c = 0\f$ and the lower bounds of \f$x_i\f$ 278 * are nonnegative if \f$\alpha_i > 0\f$ or the upper bounds are nonpositive if \f$\alpha_i < 0\f$. 279 */ 280 static 281 SCIP_RETCODE fixVariableZero( 282 SCIP* scip, /**< SCIP pointer */ 283 SCIP_VAR* var, /**< variable to be fixed to 0*/ 284 SCIP_Bool* infeasible, /**< if fixing is infeasible */ 285 SCIP_Bool* tightened /**< if fixing was performed */ 286 ) 287 { 288 assert(scip != NULL); 289 assert(var != NULL); 290 assert(infeasible != NULL); 291 assert(tightened != NULL); 292 293 *infeasible = FALSE; 294 *tightened = FALSE; 295 296 if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR ) 297 { 298 SCIP_Real aggrconst; 299 300 /* if constant is 0 */ 301 aggrconst = SCIPvarGetMultaggrConstant(var); 302 if( SCIPisZero(scip, aggrconst) ) 303 { 304 SCIP_VAR** aggrvars; 305 SCIP_Real* aggrvals; 306 SCIP_Bool allnonnegative = TRUE; 307 int naggrvars; 308 int i; 309 310 SCIP_CALL( SCIPflattenVarAggregationGraph(scip, var) ); 311 312 /* check whether all variables are "nonnegative" */ 313 naggrvars = SCIPvarGetMultaggrNVars(var); 314 aggrvars = SCIPvarGetMultaggrVars(var); 315 aggrvals = SCIPvarGetMultaggrScalars(var); 316 for( i = 0; i < naggrvars; ++i ) 317 { 318 if( (SCIPisPositive(scip, aggrvals[i]) && SCIPisNegative(scip, SCIPvarGetLbLocal(aggrvars[i]))) || 319 (SCIPisNegative(scip, aggrvals[i]) && SCIPisPositive(scip, SCIPvarGetUbLocal(aggrvars[i]))) ) 320 { 321 allnonnegative = FALSE; 322 break; 323 } 324 } 325 326 if( allnonnegative ) 327 { 328 /* all variables are nonnegative -> fix variables */ 329 for( i = 0; i < naggrvars; ++i ) 330 { 331 SCIP_Bool fixed; 332 SCIP_CALL( SCIPfixVar(scip, aggrvars[i], 0.0, infeasible, &fixed) ); 333 if( *infeasible ) 334 return SCIP_OKAY; 335 *tightened = *tightened || fixed; 336 } 337 } 338 } 339 } 340 else 341 { 342 SCIP_CALL( SCIPfixVar(scip, var, 0.0, infeasible, tightened) ); 343 } 344 345 return SCIP_OKAY; 346 } 347 348 /** add lock on variable */ 349 static 350 SCIP_RETCODE lockVariableCardinality( 351 SCIP* scip, /**< SCIP data structure */ 352 SCIP_CONS* cons, /**< constraint */ 353 SCIP_VAR* var, /**< variable */ 354 SCIP_VAR* indvar /**< indicator variable */ 355 ) 356 { 357 assert(scip != NULL); 358 assert(cons != NULL); 359 assert(var != NULL); 360 361 /* rounding down == bad if lb < 0, rounding up == bad if ub > 0 */ 362 SCIP_CALL( SCIPlockVarCons(scip, var, cons, SCIPisFeasNegative(scip, SCIPvarGetLbGlobal(var)), 363 SCIPisFeasPositive(scip, SCIPvarGetUbGlobal(var))) ); 364 SCIP_CALL( SCIPlockVarCons(scip, indvar, cons, TRUE, TRUE) ); 365 366 return SCIP_OKAY; 367 } 368 369 /* remove lock on variable */ 370 static 371 SCIP_RETCODE unlockVariableCardinality( 372 SCIP* scip, /**< SCIP data structure */ 373 SCIP_CONS* cons, /**< constraint */ 374 SCIP_VAR* var, /**< variable */ 375 SCIP_VAR* indvar /**< indicator variable */ 376 ) 377 { 378 assert(scip != NULL); 379 assert(cons != NULL); 380 assert(var != NULL); 381 382 /* rounding down == bad if lb < 0, rounding up == bad if ub > 0 */ 383 SCIP_CALL( SCIPunlockVarCons(scip, var, cons, SCIPisFeasNegative(scip, SCIPvarGetLbGlobal(var)), 384 SCIPisFeasPositive(scip, SCIPvarGetUbGlobal(var))) ); 385 SCIP_CALL( SCIPunlockVarCons(scip, indvar, cons, TRUE, TRUE) ); 386 387 return SCIP_OKAY; 388 } 389 390 /** ensures that the vars and weights array can store at least num entries */ 391 static 392 SCIP_RETCODE consdataEnsurevarsSizeCardinality( 393 SCIP* scip, /**< SCIP data structure */ 394 SCIP_CONSDATA* consdata, /**< constraint data */ 395 int num, /**< minimum number of entries to store */ 396 SCIP_Bool reserveweights /**< whether the weights array is handled */ 397 ) 398 { 399 assert(consdata != NULL); 400 assert(consdata->nvars <= consdata->maxvars); 401 402 if( num > consdata->maxvars ) 403 { 404 int newsize; 405 406 newsize = SCIPcalcMemGrowSize(scip, num); 407 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->vars, consdata->maxvars, newsize) ); 408 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->indvars, consdata->maxvars, newsize) ); 409 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->eventdatas, consdata->maxvars, newsize) ); 410 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->eventdatascurrent, 4*consdata->maxvars, 4*newsize) );/*lint !e647*/ 411 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->eventvarscurrent, 4*consdata->maxvars, 4*newsize) );/*lint !e647*/ 412 413 if ( reserveweights ) 414 { 415 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->weights, consdata->maxvars, newsize) ); 416 } 417 consdata->maxvars = newsize; 418 } 419 assert(num <= consdata->maxvars); 420 421 return SCIP_OKAY; 422 } 423 424 /** handle new variable that was added to the constraint 425 * 426 * We perform the following steps: 427 * 428 * - catch bound change events of variable. 429 * - update rounding locks of variable. 430 * - don't allow multiaggregation of variable, since this cannot be handled by branching in the current implementation 431 * - update lower and upper bound row, i.e., the linear representations of the cardinality constraints 432 */ 433 static 434 SCIP_RETCODE handleNewVariableCardinality( 435 SCIP* scip, /**< SCIP data structure */ 436 SCIP_CONS* cons, /**< constraint */ 437 SCIP_CONSDATA* consdata, /**< constraint data */ 438 SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */ 439 SCIP_VAR* var, /**< variable */ 440 SCIP_VAR* indvar, /**< indicator variable to indicate whether variable may be treated as 441 * nonzero in cardinality constraint */ 442 int pos, /**< position in constraint */ 443 SCIP_Bool transformed, /**< whether original variable was transformed */ 444 SCIP_EVENTDATA** eventdata /**< pointer to store event data for bound change events */ 445 ) 446 { 447 assert(scip != NULL); 448 assert(cons != NULL); 449 assert(consdata != NULL); 450 assert(conshdlrdata != NULL); 451 assert(var != NULL); 452 453 /* if we are in transformed problem, catch the variable's events */ 454 if( transformed ) 455 { 456 /* catch bound change events of variable */ 457 SCIP_CALL( catchVarEventCardinality(scip, conshdlrdata->eventhdlr, consdata, var, indvar, pos, eventdata) ); 458 assert(eventdata != NULL ); 459 460 /* if the variable is fixed to nonzero */ 461 assert(consdata->ntreatnonzeros >= 0 ); 462 if( SCIPisFeasEQ(scip, SCIPvarGetLbLocal(indvar), 1.0) ) 463 ++consdata->ntreatnonzeros; 464 } 465 466 /* branching on multiaggregated variables does not seem to work well, so avoid it */ 467 SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, indvar) ); 468 469 /* install the rounding locks for the new variable */ 470 SCIP_CALL( lockVariableCardinality(scip, cons, var, indvar) ); 471 472 /* add the new coefficient to the upper bound LP row, if necessary */ 473 if( consdata->rowub != NULL && !SCIPisInfinity(scip, SCIPvarGetUbGlobal(var)) 474 && !SCIPisZero(scip, SCIPvarGetUbGlobal(var)) ) 475 { 476 SCIP_CALL( SCIPaddVarToRow(scip, consdata->rowub, var, 1.0/SCIPvarGetUbGlobal(var)) ); 477 } 478 479 /* add the new coefficient to the lower bound LP row, if necessary */ 480 if( consdata->rowlb != NULL && !SCIPisInfinity(scip, SCIPvarGetLbGlobal(var)) 481 && !SCIPisZero(scip, SCIPvarGetLbGlobal(var)) ) 482 { 483 SCIP_CALL( SCIPaddVarToRow(scip, consdata->rowlb, var, 1.0/SCIPvarGetLbGlobal(var)) ); 484 } 485 486 return SCIP_OKAY; 487 } 488 489 /** adds a variable to a cardinality constraint, at position given by weight - ascending order */ 490 static 491 SCIP_RETCODE addVarCardinality( 492 SCIP* scip, /**< SCIP data structure */ 493 SCIP_CONS* cons, /**< constraint */ 494 SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */ 495 SCIP_VAR* var, /**< variable to add to the constraint */ 496 SCIP_VAR* indvar, /**< indicator variable to indicate whether variable may be treated as nonzero 497 * in cardinality constraint (or NULL) */ 498 SCIP_Real weight /**< weight to determine position */ 499 ) 500 { 501 SCIP_EVENTDATA* eventdata = NULL; 502 SCIP_CONSDATA* consdata; 503 SCIP_Bool transformed; 504 int pos; 505 506 assert(var != NULL); 507 assert(cons != NULL); 508 assert(conshdlrdata != NULL); 509 510 consdata = SCIPconsGetData(cons); 511 assert(consdata != NULL ); 512 513 if( consdata->weights == NULL && consdata->maxvars > 0 ) 514 { 515 SCIPerrorMessage("cannot add variable to cardinality constraint <%s> that does not contain weights.\n", 516 SCIPconsGetName(cons)); 517 return SCIP_INVALIDCALL; 518 } 519 520 /* check indicator variable */ 521 if( indvar == NULL ) 522 { 523 if( conshdlrdata->varhash == NULL ) 524 { 525 /* set up hash map */ 526 SCIP_CALL( SCIPhashmapCreate(&conshdlrdata->varhash, SCIPblkmem(scip), SCIPgetNTotalVars(scip)) ); 527 } 528 529 /* check whether an indicator variable already exists for implied variable */ 530 if( SCIPhashmapExists(conshdlrdata->varhash, var) ) 531 { 532 assert((SCIP_VAR*) SCIPhashmapGetImage(conshdlrdata->varhash, var) != NULL); 533 indvar = (SCIP_VAR*) SCIPhashmapGetImage(conshdlrdata->varhash, var); 534 assert(indvar != NULL); 535 } 536 else 537 { 538 /* if implied variable is binary, then it is also not necessary to create an indicator variable */ 539 if( SCIPvarIsBinary(var) ) 540 indvar = var; 541 else 542 { 543 char varname[SCIP_MAXSTRLEN]; 544 SCIP_VAR* newvar; 545 546 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "ind_%s", SCIPvarGetName(var)); 547 SCIP_CALL( SCIPcreateVar(scip, &newvar, varname, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY, FALSE, FALSE, 548 NULL, NULL, NULL, NULL, NULL) ); 549 SCIP_CALL( SCIPaddVar(scip, newvar) ); 550 indvar = newvar; 551 552 SCIP_CALL( SCIPreleaseVar(scip, &newvar) ); 553 } 554 assert(indvar != NULL); 555 556 /* insert implied variable to hash map */ 557 SCIP_CALL( SCIPhashmapInsert(conshdlrdata->varhash, var, (void*) indvar) );/*lint !e571*/ 558 assert(indvar == (SCIP_VAR*) SCIPhashmapGetImage(conshdlrdata->varhash, var)); 559 assert(SCIPhashmapExists(conshdlrdata->varhash, var)); 560 } 561 } 562 563 /* are we in the transformed problem? */ 564 transformed = SCIPconsIsTransformed(cons); 565 566 /* always use transformed variables in transformed constraints */ 567 if( transformed ) 568 { 569 SCIP_CALL( SCIPgetTransformedVar(scip, var, &var) ); 570 SCIP_CALL( SCIPgetTransformedVar(scip, indvar, &indvar) ); 571 } 572 assert(var != NULL); 573 assert(indvar != NULL); 574 assert(transformed == SCIPvarIsTransformed(var)); 575 assert(transformed == SCIPvarIsTransformed(indvar)); 576 577 /* ensure that the new information can be storend in the constraint data */ 578 SCIP_CALL( consdataEnsurevarsSizeCardinality(scip, consdata, consdata->nvars + 1, TRUE) ); 579 assert(consdata->weights != NULL); 580 assert(consdata->maxvars >= consdata->nvars+1); 581 582 /* move other variables, if necessary */ 583 for( pos = consdata->nvars; pos >= 1; --pos ) 584 { 585 /* coverity[var_deref_model] */ 586 if( consdata->weights[pos-1] > weight ) 587 { 588 consdata->vars[pos] = consdata->vars[pos-1]; 589 consdata->indvars[pos] = consdata->indvars[pos-1]; 590 consdata->eventdatas[pos] = consdata->eventdatas[pos-1]; 591 consdata->weights[pos] = consdata->weights[pos-1]; 592 593 if( consdata->eventdatas[pos] != NULL ) 594 { 595 consdata->eventdatas[pos]->pos = (unsigned int)pos; 596 } 597 } 598 else 599 break; 600 } 601 assert(0 <= pos && pos <= consdata->nvars); 602 603 /* handle the new variable */ 604 SCIP_CALL( handleNewVariableCardinality(scip, cons, consdata, conshdlrdata, var, indvar, pos, transformed, &eventdata) ); 605 assert(! transformed || eventdata != NULL); 606 607 /* insert variable */ 608 consdata->vars[pos] = var; 609 consdata->indvars[pos] = indvar; 610 consdata->eventdatas[pos] = eventdata; 611 consdata->weights[pos] = weight; 612 ++consdata->nvars; 613 614 return SCIP_OKAY; 615 } 616 617 /** appends a variable to a cardinality constraint */ 618 static 619 SCIP_RETCODE appendVarCardinality( 620 SCIP* scip, /**< SCIP data structure */ 621 SCIP_CONS* cons, /**< constraint */ 622 SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */ 623 SCIP_VAR* var, /**< variable to add to the constraint */ 624 SCIP_VAR* indvar /**< indicator variable to indicate whether variable may be treated as nonzero 625 * in cardinality constraint */ 626 ) 627 { 628 SCIP_EVENTDATA* eventdata = NULL; 629 SCIP_CONSDATA* consdata; 630 SCIP_Bool transformed; 631 632 assert(var != NULL); 633 assert(cons != NULL); 634 assert(conshdlrdata != NULL); 635 636 consdata = SCIPconsGetData(cons); 637 assert(consdata != NULL); 638 639 /* check indicator variable */ 640 if( indvar == NULL ) 641 { 642 if( conshdlrdata->varhash == NULL ) 643 { 644 /* set up hash map */ 645 SCIP_CALL( SCIPhashmapCreate(&conshdlrdata->varhash, SCIPblkmem(scip), SCIPgetNTotalVars(scip)) ); 646 } 647 648 /* check whether an indicator variable already exists for implied variable */ 649 if( SCIPhashmapExists(conshdlrdata->varhash, var) ) 650 { 651 assert((SCIP_VAR*) SCIPhashmapGetImage(conshdlrdata->varhash, var) != NULL); 652 indvar = (SCIP_VAR*) SCIPhashmapGetImage(conshdlrdata->varhash, var); 653 assert(indvar != NULL); 654 } 655 else 656 { 657 /* if implied variable is binary, then it is also not necessary to create an indicator variable */ 658 if( SCIPvarIsBinary(var) ) 659 indvar = var; 660 else 661 { 662 char varname[SCIP_MAXSTRLEN]; 663 SCIP_VAR* newvar; 664 665 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "ind_%s", SCIPvarGetName(var)); 666 SCIP_CALL( SCIPcreateVar(scip, &newvar, varname, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY, FALSE, FALSE, 667 NULL, NULL, NULL, NULL, NULL) ); 668 SCIP_CALL( SCIPaddVar(scip, newvar) ); 669 indvar = newvar; 670 671 SCIP_CALL( SCIPreleaseVar(scip, &newvar) ); 672 } 673 assert(indvar != NULL); 674 675 /* insert implied variable to hash map */ 676 SCIP_CALL( SCIPhashmapInsert(conshdlrdata->varhash, var, (void*) indvar) );/*lint !e571*/ 677 assert(indvar == (SCIP_VAR*) SCIPhashmapGetImage(conshdlrdata->varhash, var)); 678 assert(SCIPhashmapExists(conshdlrdata->varhash, var)); 679 } 680 } 681 682 /* are we in the transformed problem? */ 683 transformed = SCIPconsIsTransformed(cons); 684 685 /* always use transformed variables in transformed constraints */ 686 if( transformed ) 687 { 688 SCIP_CALL( SCIPgetTransformedVar(scip, var, &var) ); 689 SCIP_CALL( SCIPgetTransformedVar(scip, indvar, &indvar) ); 690 } 691 assert(var != NULL); 692 assert(indvar != NULL); 693 assert(transformed == SCIPvarIsTransformed(var)); 694 assert(transformed == SCIPvarIsTransformed(indvar)); 695 696 /* ensure that the new information can be stored in the constraint data */ 697 SCIP_CALL( consdataEnsurevarsSizeCardinality(scip, consdata, consdata->nvars + 1, FALSE) ); 698 699 /* handle the new variable */ 700 SCIP_CALL( handleNewVariableCardinality(scip, cons, consdata, conshdlrdata, var, indvar, consdata->nvars, transformed, 701 &eventdata) ); 702 assert(!transformed || eventdata != NULL); 703 704 /* insert variable */ 705 consdata->vars[consdata->nvars] = var; 706 consdata->indvars[consdata->nvars] = indvar; 707 consdata->eventdatas[consdata->nvars] = eventdata; 708 709 if( consdata->weights != NULL && consdata->nvars > 0 ) 710 consdata->weights[consdata->nvars] = consdata->weights[consdata->nvars-1] + 1.0; 711 ++consdata->nvars; 712 713 assert(consdata->weights != NULL || consdata->nvars > 0); 714 715 return SCIP_OKAY; 716 } 717 718 /** deletes a variable from a cardinality constraint */ 719 static 720 SCIP_RETCODE deleteVarCardinality( 721 SCIP* scip, /**< SCIP data structure */ 722 SCIP_CONS* cons, /**< constraint */ 723 SCIP_CONSDATA* consdata, /**< constraint data */ 724 SCIP_EVENTHDLR* eventhdlr, /**< corresponding event handler */ 725 int pos /**< position of variable in array */ 726 ) 727 { /*lint --e{679}*/ 728 int j; 729 730 assert(0 <= pos && pos < consdata->nvars); 731 732 /* remove lock of variable */ 733 SCIP_CALL( unlockVariableCardinality(scip, cons, consdata->vars[pos], consdata->indvars[pos]) ); 734 735 /* drop events on indicator variable and implied variable */ 736 SCIP_CALL( dropVarEventCardinality(scip, eventhdlr, consdata, consdata->vars[pos], consdata->indvars[pos], 737 &consdata->eventdatas[pos]) ); 738 739 /* update number of variables that may be treated as nonzero */ 740 if( SCIPisFeasEQ(scip, SCIPvarGetLbLocal(consdata->indvars[pos]), 1.0) ) 741 --(consdata->ntreatnonzeros); 742 743 /* delete variable - need to copy since order is important */ 744 for( j = pos; j < consdata->nvars-1; ++j ) 745 { 746 consdata->vars[j] = consdata->vars[j+1]; 747 consdata->indvars[j] = consdata->indvars[j+1]; 748 consdata->eventdatas[j] = consdata->eventdatas[j+1]; 749 if( consdata->weights != NULL ) 750 consdata->weights[j] = consdata->weights[j+1]; 751 752 consdata->eventdatas[j]->pos = (unsigned int)j; 753 } 754 --consdata->nvars; 755 756 return SCIP_OKAY; 757 } 758 759 /** for each indicator variable sets solution to 1.0 if the solution value of the implied variable is nonzero */ 760 static 761 SCIP_RETCODE polishPrimalSolution( 762 SCIP* scip, /**< SCIP pointer */ 763 SCIP_CONS** conss, /**< constraints */ 764 int nconss, /**< number of constraints */ 765 SCIP_SOL* sol, /**< solution to be enforced (or NULL) */ 766 SCIP_SOL* primsol /**< primal solution */ 767 ) 768 { 769 SCIP_CONSDATA* consdata; 770 SCIP_VAR** indvars; 771 SCIP_VAR** vars; 772 int nvars; 773 int c; 774 775 /* check each constraint */ 776 for( c = 0; c < nconss; ++c ) 777 { 778 SCIP_CONS* cons; 779 int j; 780 781 cons = conss[c]; 782 assert(cons != NULL); 783 consdata = SCIPconsGetData(cons); 784 assert(consdata != NULL); 785 786 nvars = consdata->nvars; 787 vars = consdata->vars; 788 indvars = consdata->indvars; 789 790 for( j = 0; j < nvars; ++j ) 791 { 792 if( SCIPisFeasZero(scip, SCIPgetSolVal(scip, sol, vars[j])) ) 793 { 794 SCIP_CALL( SCIPsetSolVal(scip, primsol, indvars[j], 0.0) ); 795 } 796 else 797 { 798 SCIP_CALL( SCIPsetSolVal(scip, primsol, indvars[j], 1.0) ); 799 } 800 } 801 } 802 803 return SCIP_OKAY; 804 } 805 806 /** unmark variables that are marked for propagation */ 807 static 808 void consdataUnmarkEventdataVars( 809 SCIP_CONSDATA* consdata /**< constraint data */ 810 ) 811 { 812 SCIP_EVENTDATA** eventdatas; 813 int nvars; 814 int j; 815 816 eventdatas = consdata->eventdatas; 817 nvars = consdata->nvars; 818 assert(eventdatas != NULL); 819 820 for( j = 0; j < nvars; ++j ) 821 { 822 SCIP_EVENTDATA* eventdata; 823 824 eventdata = eventdatas[j]; 825 eventdata->varmarked = FALSE; 826 eventdata->indvarmarked = FALSE; 827 } 828 } 829 830 /** perform one presolving round 831 * 832 * We perform the following presolving steps: 833 * 834 * - If the bounds of some variable force it to be nonzero, we can 835 * fix all other variables to zero and remove the cardinality constraints 836 * that contain it. 837 * - If a variable is fixed to zero, we can remove the variable. 838 * - If a variable appears twice, it can be fixed to 0. 839 * - We substitute appregated variables. 840 */ 841 static 842 SCIP_RETCODE presolRoundCardinality( 843 SCIP* scip, /**< SCIP pointer */ 844 SCIP_CONS* cons, /**< constraint */ 845 SCIP_CONSDATA* consdata, /**< constraint data */ 846 SCIP_EVENTHDLR* eventhdlr, /**< event handler */ 847 SCIP_Bool* cutoff, /**< whether a cutoff happened */ 848 SCIP_Bool* success, /**< whether we performed a successful reduction */ 849 int* ndelconss, /**< number of deleted constraints */ 850 int* nupgdconss, /**< number of upgraded constraints */ 851 int* nfixedvars, /**< number of fixed variables */ 852 int* nremovedvars /**< number of variables removed */ 853 ) 854 { 855 SCIP_VAR** indvars; 856 SCIP_VAR** vars; 857 SCIP_Bool allvarsbinary; 858 SCIP_Bool infeasible; 859 SCIP_Bool fixed; 860 int j; 861 862 assert(scip != NULL); 863 assert(cons != NULL); 864 assert(consdata != NULL); 865 assert(eventhdlr != NULL); 866 assert(cutoff != NULL); 867 assert(success != NULL); 868 assert(ndelconss != NULL); 869 assert(nfixedvars != NULL); 870 assert(nremovedvars != NULL); 871 872 *cutoff = FALSE; 873 *success = FALSE; 874 875 SCIPdebugMsg(scip, "Presolving cardinality constraint <%s>.\n", SCIPconsGetName(cons) ); 876 877 /* reset number of events stored for propagation, since presolving already performs a 878 * complete propagation of all variables */ 879 consdata->neventdatascurrent = 0; 880 consdataUnmarkEventdataVars(consdata); 881 882 j = 0; 883 allvarsbinary = TRUE; 884 vars = consdata->vars; 885 indvars = consdata->indvars; 886 887 /* check for variables fixed to 0 and bounds that fix a variable to be nonzero */ 888 while ( j < consdata->nvars ) 889 { 890 int l; 891 SCIP_VAR* var; 892 SCIP_VAR* oldvar; 893 SCIP_VAR* indvar; 894 SCIP_Real lb; 895 SCIP_Real ub; 896 SCIP_Real indlb; 897 SCIP_Real indub; 898 SCIP_Real scalar; 899 SCIP_Real constant; 900 901 scalar = 1.0; 902 constant = 0.0; 903 904 /* check for aggregation: if the constant is zero the variable is zero iff the aggregated 905 * variable is 0 */ 906 var = vars[j]; 907 indvar = indvars[j]; 908 oldvar = var; 909 SCIP_CALL( SCIPgetProbvarSum(scip, &var, &scalar, &constant) ); 910 911 /* if constant is zero and we get a different variable, substitute variable */ 912 if( SCIPisZero(scip, constant) && !SCIPisZero(scip, scalar) && var != vars[j] ) 913 { 914 SCIPdebugMsg(scip, "substituted variable <%s> by <%s>.\n", SCIPvarGetName(vars[j]), SCIPvarGetName(var)); 915 916 /* we reuse the same indicator variable for the new variable */ 917 SCIP_CALL( dropVarEventCardinality(scip, eventhdlr, consdata, consdata->vars[j], consdata->indvars[j], 918 &consdata->eventdatas[j]) ); 919 SCIP_CALL( catchVarEventCardinality(scip, eventhdlr, consdata, var, consdata->indvars[j], j, 920 &consdata->eventdatas[j]) ); 921 assert(consdata->eventdatas[j] != NULL); 922 923 /* change the rounding locks */ 924 SCIP_CALL( unlockVariableCardinality(scip, cons, consdata->vars[j], consdata->indvars[j]) ); 925 SCIP_CALL( lockVariableCardinality(scip, cons, var, consdata->indvars[j]) ); 926 927 /* update event data */ 928 consdata->eventdatas[j]->var = var; 929 930 vars[j] = var; 931 } 932 assert(var == vars[j]); 933 934 /* check whether the variable appears again later */ 935 for( l = j+1; l < consdata->nvars; ++l ) 936 { 937 if( var == vars[l] || oldvar == vars[l] ) 938 { 939 SCIPdebugMsg(scip, "variable <%s> appears twice in constraint <%s>.\n", SCIPvarGetName(vars[j]), 940 SCIPconsGetName(cons)); 941 return SCIP_INVALIDDATA; 942 } 943 } 944 945 /* get bounds of variable */ 946 lb = SCIPvarGetLbLocal(var); 947 ub = SCIPvarGetUbLocal(var); 948 949 /* if the variable is fixed to nonzero */ 950 if( SCIPisFeasPositive(scip, lb) || SCIPisFeasNegative(scip, ub) ) 951 { 952 assert(SCIPvarIsBinary(indvar)); 953 954 /* fix (binary) indicator variable to 1.0 (the cardinality constraint will then be modified below) */ 955 SCIP_CALL( SCIPfixVar(scip, indvar, 1.0, &infeasible, &fixed) ); 956 if( infeasible ) 957 { 958 *cutoff = TRUE; 959 return SCIP_OKAY; 960 } 961 962 if( fixed ) 963 { 964 SCIPdebugMsg(scip, "fixed binary variable <%s> to 1.0.\n", SCIPvarGetName(indvar)); 965 ++(*nfixedvars); 966 } 967 } 968 969 /* if the variable is fixed to 0 */ 970 if( SCIPisFeasZero(scip, lb) && SCIPisFeasZero(scip, ub) ) 971 { 972 assert(SCIPvarIsBinary(indvar)); 973 974 /* fix (binary) indicator variable to 0.0, if possible (the cardinality constraint will then be modified below) 975 * note that an infeasibility implies no cut off */ 976 SCIP_CALL( SCIPfixVar(scip, indvar, 0.0, &infeasible, &fixed) ); 977 if( fixed ) 978 { 979 SCIPdebugMsg(scip, "fixed binary variable <%s> to 0.0.\n", SCIPvarGetName(indvar)); 980 ++(*nfixedvars); 981 } 982 } 983 984 /* get bounds of indicator variable */ 985 indlb = SCIPvarGetLbLocal(indvar); 986 indub = SCIPvarGetUbLocal(indvar); 987 988 /* if the variable may be treated as nonzero */ 989 if( SCIPisFeasEQ(scip, indlb, 1.0) ) 990 { 991 assert(indub == 1.0); 992 993 /* modify row and delete variable */ 994 SCIP_CALL( deleteVarCardinality(scip, cons, consdata, eventhdlr, j) ); 995 SCIPdebugMsg(scip, "deleting variable <%s> from constraint <%s>, since it may be treated as nonzero.\n", 996 SCIPvarGetName(var), SCIPconsGetName(cons)); 997 --(consdata->cardval); 998 ++(*nremovedvars); 999 } 1000 /* if the indicator variable is fixed to 0 */ 1001 else if( SCIPisFeasEQ(scip, indub, 0.0) ) 1002 { 1003 assert(indlb == 0.0); 1004 1005 /* fix variable to 0.0 */ 1006 SCIP_CALL( SCIPfixVar(scip, var, 0.0, &infeasible, &fixed) ); 1007 if( infeasible ) 1008 { 1009 *cutoff = TRUE; 1010 return SCIP_OKAY; 1011 } 1012 if( fixed ) 1013 { 1014 SCIPdebugMsg(scip, "fixed variable <%s> to 0.0.\n", SCIPvarGetName(var)); 1015 ++(*nfixedvars); 1016 } 1017 1018 /* delete variable */ 1019 SCIP_CALL( deleteVarCardinality(scip, cons, consdata, eventhdlr, j) ); 1020 SCIPdebugMsg(scip, "deleting variable <%s> from constraint <%s>, since it is fixed to 0.\n", SCIPvarGetName(var), 1021 SCIPconsGetName(cons)); 1022 ++(*nremovedvars); 1023 } 1024 else 1025 { 1026 /* check whether all variables are binary */ 1027 if( !SCIPvarIsBinary(var) ) 1028 allvarsbinary = FALSE; 1029 1030 ++j; 1031 } 1032 } 1033 1034 /* if the cardinality value is smaller than 0, then the problem is infeasible */ 1035 if( consdata->cardval < 0 ) 1036 { 1037 SCIPdebugMsg(scip, "The problem is infeasible: more variables have bounds that keep them from being 0 than allowed.\n"); 1038 1039 *cutoff = TRUE; 1040 return SCIP_OKAY; 1041 } 1042 /* else if the cardinality value is 0 */ 1043 else if( consdata->cardval == 0 ) 1044 { 1045 /* fix all variables of the constraint to 0 */ 1046 for( j = 0; j < consdata->nvars; ++j ) 1047 { 1048 SCIP_CALL( SCIPfixVar(scip, consdata->vars[j], 0.0, &infeasible, &fixed) ); 1049 if( infeasible ) 1050 { 1051 *cutoff = TRUE; 1052 return SCIP_OKAY; 1053 } 1054 if( fixed ) 1055 { 1056 SCIPdebugMsg(scip, "fixed variable <%s> to 0.0.\n", SCIPvarGetName(consdata->vars[j])); 1057 ++(*nfixedvars); 1058 } 1059 } 1060 } 1061 1062 /* if the cardinality constraint is redundant */ 1063 if( consdata->nvars <= consdata->cardval ) 1064 { 1065 SCIPdebugMsg(scip, "Deleting cardinality constraint <%s> with <%d> variables and cardinality value <%d>.\n", 1066 SCIPconsGetName(cons), consdata->nvars, consdata->cardval); 1067 1068 /* delete constraint */ 1069 assert(!SCIPconsIsModifiable(cons)); 1070 SCIP_CALL( SCIPdelCons(scip, cons) ); 1071 ++(*ndelconss); 1072 *success = TRUE; 1073 return SCIP_OKAY; 1074 } 1075 else 1076 { 1077 /* if all variables are binary create a knapsack constraint */ 1078 if( allvarsbinary ) 1079 { 1080 SCIP_CONS* knapsackcons; 1081 SCIP_Longint* vals; 1082 1083 SCIP_CALL( SCIPallocBufferArray(scip, &vals, consdata->nvars) ); 1084 for( j = 0; j < consdata->nvars; ++j ) 1085 vals[j] = 1; 1086 1087 /* create, add, and release the knapsack constraint */ 1088 SCIP_CALL( SCIPcreateConsKnapsack(scip, &knapsackcons, SCIPconsGetName(cons), consdata->nvars, consdata->vars, 1089 vals, (SCIP_Longint) consdata->cardval, SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), 1090 SCIPconsIsEnforced(cons), SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons), 1091 SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), 1092 SCIPconsIsStickingAtNode(cons)) );/*lint !e524*/ 1093 SCIP_CALL( SCIPaddCons(scip, knapsackcons) ); 1094 SCIP_CALL( SCIPreleaseCons(scip, &knapsackcons) ); 1095 1096 SCIPfreeBufferArray(scip, &vals); 1097 1098 SCIPdebugMsg(scip, "Upgrading cardinality constraint <%s> to knapsack constraint.\n", SCIPconsGetName(cons)); 1099 1100 /* remove the cardinality constraint globally */ 1101 assert(!SCIPconsIsModifiable(cons)); 1102 SCIP_CALL( SCIPdelCons(scip, cons) ); 1103 ++(*nupgdconss); 1104 *success = TRUE; 1105 } 1106 } 1107 1108 return SCIP_OKAY; 1109 } 1110 1111 /** propagates a cardinality constraint and its variables 1112 * 1113 * The number 'ntreatnonzeros' that is assigned to the constraint data returns the number of variables that are either 1114 * known to be nonzero or can be treated as nonzero. We say that a variable is known to be nonzero, if zero is outside 1115 * the domain of this variable. A variable can be treated as nonzero, if its corresponding indicator variable 'indvar' is 1116 * fixed to 1.0, e.g., by branching. 1117 * 1118 * We perform the following propagation steps: 1119 * 1120 * - if the number 'ntreatnonzeros' is greater than the cardinality value of the constraint, then the current subproblem 1121 * is marked as infeasible. 1122 * - if the cardinality constraint is saturated, i.e., the number 'ntreatnonzeros' is equal to the cardinality value of 1123 * the constraint, then fix all the other variables of the constraint to zero. 1124 * - remove the cardinality constraint locally if all variables are either fixed to zero or can be treated as nonzero. 1125 * - if a (binary) indicator variable is fixed to zero, then fix the corresponding implied variable to zero. 1126 * - if zero is outside of the domain of an implied variable, then fix the corresponding indicator variable to one. 1127 */ 1128 static 1129 SCIP_RETCODE propCardinality( 1130 SCIP* scip, /**< SCIP pointer */ 1131 SCIP_CONS* cons, /**< constraint */ 1132 SCIP_CONSDATA* consdata, /**< constraint data */ 1133 SCIP_Bool* cutoff, /**< whether a cutoff happened */ 1134 int* nchgdomain /**< number of domain changes */ 1135 ) 1136 { 1137 assert(scip != NULL); 1138 assert(cons != NULL); 1139 assert(consdata != NULL); 1140 assert(cutoff != NULL); 1141 assert(nchgdomain != NULL); 1142 1143 *cutoff = FALSE; 1144 1145 /* if more variables may be treated as nonzero than allowed */ 1146 if( consdata->ntreatnonzeros > consdata->cardval ) 1147 { 1148 SCIPdebugMsg(scip, "the node is infeasible, more than %d variables are fixed to be nonzero.\n", consdata->cardval); 1149 SCIP_CALL( SCIPresetConsAge(scip, cons) ); 1150 *cutoff = TRUE; 1151 1152 return SCIP_OKAY; 1153 } 1154 1155 /* if number of nonzeros is saturated */ 1156 if( consdata->ntreatnonzeros == consdata->cardval ) 1157 { 1158 SCIP_VAR** vars; 1159 SCIP_VAR** indvars; 1160 SCIP_Bool infeasible; 1161 SCIP_Bool tightened; 1162 SCIP_Bool allvarfixed; 1163 int nvars; 1164 #ifndef NDEBUG 1165 int cnt = 0; 1166 #endif 1167 int j; 1168 1169 nvars = consdata->nvars; 1170 vars = consdata->vars; 1171 indvars = consdata->indvars; 1172 assert(vars != NULL); 1173 assert(indvars != NULL); 1174 1175 /* fix free variables to zero */ 1176 allvarfixed = TRUE; 1177 for( j = 0; j < nvars; ++j ) 1178 { 1179 /* if variable is implied to be treated as nonzero */ 1180 if( SCIPisFeasEQ(scip, SCIPvarGetLbLocal(indvars[j]), 1.0) ) 1181 #ifndef NDEBUG 1182 ++cnt; 1183 #else 1184 ; 1185 #endif 1186 /* else fix variable to zero if not done already */ 1187 else 1188 { 1189 SCIP_VAR* var; 1190 1191 var = vars[j]; 1192 1193 /* fix variable */ 1194 if( SCIPisFeasNegative(scip, SCIPvarGetLbLocal(var)) || SCIPisFeasPositive(scip, SCIPvarGetUbLocal(var)) ) 1195 { 1196 SCIP_CALL( fixVariableZero(scip, var, &infeasible, &tightened) ); 1197 if( infeasible ) 1198 { 1199 SCIPdebugMsg(scip, "the node is infeasible, more than %d variables are fixed to be nonzero.\n", 1200 consdata->cardval); 1201 SCIP_CALL( SCIPresetConsAge(scip, cons) ); 1202 *cutoff = TRUE; 1203 1204 return SCIP_OKAY; 1205 } 1206 1207 if( tightened ) 1208 { 1209 SCIPdebugMsg(scip, "fixed variable <%s> to 0, since constraint <%s> with cardinality value %d is \ 1210 saturated.\n", SCIPvarGetName(var), SCIPconsGetName(cons), consdata->cardval); 1211 ++(*nchgdomain); 1212 } 1213 else 1214 allvarfixed = FALSE; 1215 } 1216 } 1217 } 1218 assert(cnt == consdata->ntreatnonzeros); 1219 1220 /* reset constraint age counter */ 1221 if( *nchgdomain > 0 ) 1222 { 1223 SCIP_CALL( SCIPresetConsAge(scip, cons) ); 1224 } 1225 1226 /* delete constraint locally */ 1227 if( allvarfixed ) 1228 { 1229 assert(!SCIPconsIsModifiable(cons)); 1230 SCIP_CALL( SCIPdelConsLocal(scip, cons) ); 1231 1232 return SCIP_OKAY; 1233 } 1234 } 1235 1236 /* if relevant bound change events happened */ 1237 if( consdata->neventdatascurrent > 0 ) 1238 { 1239 SCIP_EVENTDATA** eventdatas; 1240 SCIP_VAR** eventvars; 1241 int neventdatas; 1242 int j; 1243 1244 neventdatas = consdata->neventdatascurrent; 1245 eventvars = consdata->eventvarscurrent; 1246 eventdatas = consdata->eventdatascurrent; 1247 assert(eventdatas != NULL && eventvars != NULL); 1248 1249 for( j = 0; j < neventdatas; ++j ) 1250 { 1251 SCIP_EVENTDATA* eventdata; 1252 SCIP_Bool infeasible; 1253 SCIP_Bool tightened; 1254 SCIP_VAR* var; 1255 1256 eventdata = eventdatas[j]; 1257 var = eventvars[j]; 1258 assert(var != NULL && eventdata != NULL); 1259 assert(eventdata->var != NULL); 1260 assert(eventdata->indvar != NULL); 1261 assert(var == eventdata->var || var == eventdata->indvar); 1262 assert(SCIPvarIsBinary(eventdata->indvar)); 1263 1264 /* if variable is an indicator variable */ 1265 if( eventdata->indvar == var ) 1266 { 1267 assert(eventdata->indvarmarked); 1268 1269 /* if variable is fixed to zero */ 1270 if( SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) ) 1271 { 1272 SCIP_VAR* implvar; 1273 1274 implvar = eventdata->var; 1275 1276 /* fix implied variable to zero if not done already */ 1277 if( SCIPisFeasNegative(scip, SCIPvarGetLbLocal(implvar)) || 1278 SCIPisFeasPositive(scip, SCIPvarGetUbLocal(implvar)) ) 1279 { 1280 SCIP_CALL( fixVariableZero(scip, implvar, &infeasible, &tightened) ); 1281 1282 if( infeasible ) 1283 { 1284 SCIPdebugMsg(scip, "the node is infeasible, indicator variable %s is fixed to zero although implied " 1285 "variable %s is nonzero.\n", SCIPvarGetName(var), SCIPvarGetName(implvar)); 1286 SCIP_CALL( SCIPresetConsAge(scip, cons) ); 1287 *cutoff = TRUE; 1288 1289 return SCIP_OKAY; 1290 } 1291 1292 if( tightened ) 1293 { 1294 SCIPdebugMsg(scip, "fixed variable <%s> to 0, since indicator variable %s is 0.\n", 1295 SCIPvarGetName(implvar), SCIPvarGetName(var)); 1296 ++(*nchgdomain); 1297 } 1298 } 1299 } 1300 eventdata->indvarmarked = FALSE; 1301 } 1302 /* else if variable is an implied variable */ 1303 else 1304 { 1305 assert(eventdata->var == var); 1306 assert(eventdata->varmarked); 1307 1308 /* if variable is is nonzero */ 1309 if( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var)) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(var)) ) 1310 { 1311 SCIP_VAR* indvar; 1312 1313 indvar = eventdata->indvar; 1314 assert(SCIPvarIsBinary(indvar)); 1315 1316 /* fix indicator variable to 1.0 if not done already */ 1317 if( !SCIPisFeasEQ(scip, SCIPvarGetLbLocal(indvar), 1.0) ) 1318 { 1319 /* if fixing is infeasible */ 1320 if( SCIPvarGetUbLocal(indvar) != 1.0 ) 1321 { 1322 SCIPdebugMsg(scip, "the node is infeasible, implied variable %s is fixed to nonzero " 1323 "although indicator variable %s is 0.\n", SCIPvarGetName(var), SCIPvarGetName(indvar)); 1324 SCIP_CALL( SCIPresetConsAge(scip, cons) ); 1325 *cutoff = TRUE; 1326 1327 return SCIP_OKAY; 1328 } 1329 SCIP_CALL( SCIPchgVarLb(scip, indvar, 1.0) ); 1330 SCIPdebugMsg(scip, "fixed variable <%s> to 1.0, since implied variable %s is nonzero.\n", 1331 SCIPvarGetName(indvar), SCIPvarGetName(var)); 1332 ++(*nchgdomain); 1333 } 1334 } 1335 eventdata->varmarked = FALSE; 1336 } 1337 } 1338 } 1339 consdata->neventdatascurrent = 0; 1340 1341 return SCIP_OKAY; 1342 } 1343 1344 /** apply unbalanced branching (see the function \ref enforceCardinality() for further information) */ 1345 static 1346 SCIP_RETCODE branchUnbalancedCardinality( 1347 SCIP* scip, /**< SCIP pointer */ 1348 SCIP_SOL* sol, /**< solution to be enforced (or NULL) */ 1349 SCIP_CONS* branchcons, /**< cardinality constraint */ 1350 SCIP_VAR** vars, /**< variables of constraint */ 1351 SCIP_VAR** indvars, /**< indicator variables */ 1352 int nvars, /**< number of variables of constraint */ 1353 int cardval, /**< cardinality value of constraint */ 1354 int branchnnonzero, /**< number of variables that are fixed to be nonzero */ 1355 int branchpos /**< position in array 'vars' */ 1356 ) 1357 { 1358 SCIP_Bool infeasible; 1359 SCIP_NODE* node1; 1360 SCIP_NODE* node2; 1361 1362 /* check whether the variable selected for branching has a nonzero LP solution */ 1363 assert(!SCIPisFeasZero(scip, SCIPgetSolVal(scip, sol, vars[branchpos]))); 1364 assert(SCIPisFeasZero(scip, SCIPvarGetLbLocal(indvars[branchpos]))); 1365 assert(SCIPisFeasEQ(scip, SCIPvarGetUbLocal(indvars[branchpos]), 1.0)); 1366 1367 /* create branches */ 1368 SCIPdebugMsg(scip, "apply unbalanced branching on variable <%s> of constraint <%s>.\n", 1369 SCIPvarGetName(indvars[branchpos]), SCIPconsGetName(branchcons)); 1370 1371 /* create node 1 */ 1372 1373 /* calculate node selection and objective estimate for node 1 */ 1374 SCIP_CALL( SCIPcreateChild(scip, &node1, SCIPcalcNodeselPriority(scip, vars[branchpos], SCIP_BRANCHDIR_DOWNWARDS, 0.0), 1375 SCIPcalcChildEstimate(scip, vars[branchpos], 0.0) ) ); 1376 1377 /* fix branching variable to zero */ 1378 SCIP_CALL( fixVariableZeroNode(scip, vars[branchpos], node1, &infeasible) ); 1379 assert(! infeasible); 1380 1381 /* create node 2 */ 1382 1383 /* if the new number of nonzero variables is equal to the number of allowed nonzero variables; 1384 * i.e. cardinality constraint is saturated */ 1385 assert(branchnnonzero + 1 <= cardval); 1386 if( branchnnonzero + 1 == cardval ) 1387 { 1388 SCIP_Real nodeselest; 1389 SCIP_Real objest; 1390 #ifndef NDEBUG 1391 int cnt = 0; 1392 #endif 1393 int j; 1394 1395 /* calculate node selection and objective estimate for node 2 */ 1396 nodeselest = 0.0; 1397 objest = SCIPgetLocalTransEstimate(scip); 1398 for( j = 0; j < nvars; ++j ) 1399 { 1400 /* we only consider variables in constraint that are not the branching variable and are not fixed to nonzero */ 1401 if( j != branchpos && SCIPvarGetLbLocal(indvars[j]) != 1.0 && !SCIPisFeasPositive(scip, SCIPvarGetLbLocal(vars[j])) 1402 && !SCIPisFeasNegative(scip, SCIPvarGetUbLocal(vars[j])) 1403 ) 1404 { 1405 objest += SCIPcalcChildEstimateIncrease(scip, vars[j], SCIPgetSolVal(scip, sol, vars[j]), 0.0); 1406 nodeselest += SCIPcalcNodeselPriority(scip, vars[j], SCIP_BRANCHDIR_DOWNWARDS, 0.0); 1407 #ifndef NDEBUG 1408 ++cnt; 1409 #endif 1410 } 1411 } 1412 assert(objest >= SCIPgetLocalTransEstimate(scip)); 1413 assert(cnt == nvars - (1 + branchnnonzero)); 1414 assert(cnt > 0); 1415 1416 /* create node 2 */ 1417 SCIP_CALL( SCIPcreateChild(scip, &node2, nodeselest, objest) ); 1418 1419 /* indicate that branching variable may be treated as nonzero */ 1420 SCIP_CALL( SCIPchgVarLbNode(scip, node2, indvars[branchpos], 1.0) ); 1421 1422 /* fix variables to zero since cardinality constraint is now saturated */ 1423 for( j = 0; j < nvars; ++j ) 1424 { 1425 /* we only consider variables in constraint that are not the branching variable and are not fixed to nonzero */ 1426 if( j != branchpos && SCIPvarGetLbLocal(indvars[j]) != 1.0 1427 && !SCIPisFeasPositive(scip, SCIPvarGetLbLocal(vars[j])) 1428 && !SCIPisFeasNegative(scip, SCIPvarGetUbLocal(vars[j])) 1429 ) 1430 { 1431 SCIP_CALL( fixVariableZeroNode(scip, vars[j], node2, &infeasible) ); 1432 assert(!infeasible); 1433 } 1434 } 1435 } 1436 else 1437 { 1438 /* calculate node selection estimate for node 2 */ 1439 SCIP_CALL( SCIPcreateChild(scip, &node2, 0.0, SCIPgetLocalTransEstimate(scip)) ); 1440 1441 /* indicate that branching variable may be treated as nonzero */ 1442 SCIP_CALL( SCIPchgVarLbNode(scip, node2, indvars[branchpos], 1.0) ); 1443 } 1444 1445 return SCIP_OKAY; 1446 } 1447 1448 /** apply balanced branching (see the function enforceCardinality() for further information) */ 1449 static 1450 SCIP_RETCODE branchBalancedCardinality( 1451 SCIP* scip, /**< SCIP pointer */ 1452 SCIP_CONSHDLR* conshdlr, /**< constraint handler */ 1453 SCIP_SOL* sol, /**< solution to be enforced (or NULL) */ 1454 SCIP_CONS* branchcons, /**< cardinality constraint */ 1455 SCIP_VAR** vars, /**< variables of constraint */ 1456 SCIP_VAR** indvars, /**< indicator variables */ 1457 int nvars, /**< number of variables of constraint */ 1458 int cardval, /**< cardinality value of constraint */ 1459 int branchnnonzero, /**< number of variables that are fixed to be nonzero */ 1460 int branchpos, /**< position in array 'vars' */ 1461 SCIP_Real balancedcutoff /**< cut off value for deciding whether to apply balanced branching */ 1462 ) 1463 { 1464 SCIP_VAR** branchvars; 1465 SCIP_VAR** branchindvars; 1466 int nbranchvars; 1467 SCIP_Real splitval1; 1468 SCIP_Real splitval2; 1469 SCIP_Real weight1; 1470 SCIP_Real weight2; 1471 SCIP_Real sum1; 1472 SCIP_Real sum2; 1473 SCIP_Real w; 1474 int newcardval; 1475 int nnonzero; 1476 int nzero; 1477 int nbuffer; 1478 int ind; 1479 int cnt; 1480 int j; 1481 1482 /* check parameters */ 1483 if( SCIPconshdlrGetSepaFreq(conshdlr) != 1 ) 1484 { 1485 SCIPerrorMessage("balanced branching is only possible if separation frequency of constraint handler is 1.\n"); 1486 return SCIP_PARAMETERWRONGVAL; 1487 } 1488 1489 cnt = 0; 1490 nzero = 0; 1491 nnonzero = 0; 1492 nbranchvars = 0; 1493 1494 weight1 = 0.0; 1495 weight2 = 0.0; 1496 sum1 = 0.0; 1497 sum2 = 0.0; 1498 1499 /* allocate buffer arrays */ 1500 nbuffer = nvars-branchnnonzero; 1501 SCIP_CALL( SCIPallocBufferArray(scip, &branchvars, nbuffer) ); 1502 SCIP_CALL( SCIPallocBufferArray(scip, &branchindvars, nbuffer) ); 1503 1504 /* compute weight */ 1505 for( j = 0; j < nvars; ++j ) 1506 { 1507 SCIP_VAR* var; 1508 1509 var = vars[j]; 1510 1511 /* if(binary) indicator variable is not fixed to 1.0 */ 1512 if( SCIPvarGetLbLocal(indvars[j]) != 1.0 && !SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var)) 1513 && !SCIPisFeasNegative(scip, SCIPvarGetUbLocal(var)) ) 1514 { 1515 /* if implied variable is not already fixed to zero */ 1516 if( !SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) || !SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) ) 1517 { 1518 SCIP_Real val = REALABS(SCIPgetSolVal(scip, sol, var)); 1519 1520 weight1 += val * (SCIP_Real) (j - (nnonzero + nzero)); 1521 weight2 += val; 1522 branchindvars[nbranchvars] = indvars[j]; 1523 branchvars[nbranchvars++] = var; 1524 1525 if( !SCIPisFeasZero(scip, val) ) 1526 ++cnt; 1527 } 1528 else 1529 ++nzero; 1530 } 1531 else 1532 ++nnonzero; 1533 } 1534 assert(nnonzero == branchnnonzero); 1535 assert(nbranchvars <= nvars - branchnnonzero); 1536 1537 assert(cnt >= cardval-nnonzero); 1538 assert(!SCIPisFeasZero(scip, weight2)); 1539 w = weight1/weight2; /*lint !e414*/ 1540 1541 ind = (int)SCIPfloor(scip, w); 1542 assert(0 <= ind && ind < nbranchvars-1); 1543 1544 /* compute LP sums */ 1545 for( j = 0; j <= ind; ++j ) 1546 { 1547 SCIP_Real val; 1548 1549 val = SCIPgetSolVal(scip, sol, branchvars[j]); 1550 1551 if( SCIPisFeasPositive(scip, val) ) 1552 { 1553 assert(SCIPisFeasPositive(scip, SCIPvarGetUbLocal(branchvars[j]))); 1554 sum1 += val / SCIPvarGetUbLocal(branchvars[j]); 1555 } 1556 else if( SCIPisFeasNegative(scip, val) ) 1557 { 1558 assert(SCIPisFeasNegative(scip, SCIPvarGetLbLocal(branchvars[j]))); 1559 sum1 += val / SCIPvarGetLbLocal(branchvars[j]); 1560 } 1561 } 1562 for( j = ind+1; j < nbranchvars; ++j ) 1563 { 1564 SCIP_Real val; 1565 1566 val = SCIPgetSolVal(scip, sol, branchvars[j]); 1567 1568 if( SCIPisFeasPositive(scip, val) ) 1569 { 1570 assert(SCIPisFeasPositive(scip, SCIPvarGetUbLocal(branchvars[j]))); 1571 sum2 += val/SCIPvarGetUbLocal(branchvars[j]); 1572 } 1573 else if( SCIPisFeasNegative(scip, val) ) 1574 { 1575 assert(SCIPisFeasNegative(scip, SCIPvarGetLbLocal(branchvars[j]))); 1576 sum2 += val/SCIPvarGetLbLocal(branchvars[j]); 1577 } 1578 } 1579 1580 /* compute cardinality values of branching constraints */ 1581 newcardval = cardval - nnonzero; 1582 splitval1 = sum1 + (SCIP_Real)newcardval - sum2 - 1.0;/*lint !e834*/ 1583 splitval1 = SCIPfloor(scip, splitval1/2); 1584 splitval1 = MAX(splitval1, 0); 1585 assert((int)splitval1 >= 0); 1586 assert((int)splitval1 <= MIN(newcardval-1, ind)); 1587 splitval2 = (SCIP_Real)(newcardval-1); 1588 splitval2 -= splitval1; 1589 1590 /* the lower or upper LP row of each branching constraint should cut off the current LP solution 1591 * if this is not the case, then use unbalanced branching */ 1592 if ( !SCIPisFeasLT(scip, (SCIP_Real) splitval1 + balancedcutoff, sum1) || 1593 !SCIPisFeasLT(scip, (SCIP_Real) splitval2 + balancedcutoff, sum2) ) 1594 { 1595 SCIP_CALL( branchUnbalancedCardinality(scip, sol, branchcons, vars, indvars, nvars, cardval, 1596 branchnnonzero, branchpos) ); 1597 } 1598 else 1599 { 1600 char name[SCIP_MAXSTRLEN]; 1601 SCIP_NODE* node1; 1602 SCIP_NODE* node2; 1603 SCIP_CONS* cons1; 1604 SCIP_CONS* cons2; 1605 1606 SCIPdebugMsg(scip, "apply balanced branching on constraint <%s>.\n", SCIPconsGetName(branchcons)); 1607 1608 if( SCIPisFeasZero(scip, splitval1) ) 1609 { 1610 SCIP_Bool infeasible; 1611 SCIP_Real nodeselest; 1612 SCIP_Real objest; 1613 1614 nodeselest = 0.0; 1615 objest = SCIPgetLocalTransEstimate(scip); 1616 1617 /* calculate node selection and objective estimate for node */ 1618 for( j = 0; j <= ind; ++j ) 1619 { 1620 objest += SCIPcalcChildEstimateIncrease(scip, branchvars[j], SCIPgetSolVal(scip, sol, branchvars[j]), 0.0); 1621 nodeselest += SCIPcalcNodeselPriority(scip, branchvars[j], SCIP_BRANCHDIR_DOWNWARDS, 0.0); 1622 } 1623 assert( objest >= SCIPgetLocalTransEstimate(scip) ); 1624 1625 /* create node 1 */ 1626 SCIP_CALL( SCIPcreateChild(scip, &node1, nodeselest, objest) ); 1627 1628 for( j = 0; j <= ind; ++j ) 1629 { 1630 SCIP_CALL( fixVariableZeroNode(scip, branchvars[j], node1, &infeasible) ); 1631 assert(!infeasible); 1632 } 1633 } 1634 else 1635 { 1636 /* calculate node selection and objective estimate for node */ 1637 SCIP_CALL( SCIPcreateChild(scip, &node1, 0.0, SCIPgetLocalTransEstimate(scip)) ); 1638 1639 /* create branching constraint for node 1 */ 1640 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "brleft_#%" SCIP_LONGINT_FORMAT, SCIPgetNNodes(scip)); 1641 SCIP_CALL( SCIPcreateConsCardinality(scip, &cons1, name, ind+1, branchvars, (int)splitval1, branchindvars, NULL, 1642 FALSE, TRUE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, TRUE) ); 1643 1644 /* add constraint to node */ 1645 SCIP_CALL( SCIPaddConsNode(scip, node1, cons1, NULL) ); 1646 1647 /* release constraint */ 1648 SCIP_CALL( SCIPreleaseCons(scip, &cons1) ); 1649 } 1650 1651 if( SCIPisFeasZero(scip, splitval2) ) 1652 { 1653 SCIP_Bool infeasible; 1654 SCIP_Real nodeselest; 1655 SCIP_Real objest; 1656 1657 nodeselest = 0.0; 1658 objest = SCIPgetLocalTransEstimate(scip); 1659 1660 /* calculate node selection and objective estimate for node */ 1661 for( j = ind+1; j < nbranchvars; ++j ) 1662 { 1663 objest += SCIPcalcChildEstimateIncrease(scip, branchvars[j], SCIPgetSolVal(scip, sol, branchvars[j]), 0.0); 1664 nodeselest += SCIPcalcNodeselPriority(scip, branchvars[j], SCIP_BRANCHDIR_DOWNWARDS, 0.0); 1665 } 1666 assert(nbranchvars - (ind + 1) > 0); 1667 assert(objest >= SCIPgetLocalTransEstimate(scip)); 1668 1669 /* create node 1 */ 1670 SCIP_CALL( SCIPcreateChild(scip, &node2, nodeselest, objest) ); 1671 1672 for( j = ind+1; j < nbranchvars; ++j ) 1673 { 1674 SCIP_CALL( fixVariableZeroNode(scip, branchvars[j], node2, &infeasible) ); 1675 assert(!infeasible); 1676 } 1677 } 1678 else 1679 { 1680 /* calculate node selection and objective estimate for node */ 1681 SCIP_CALL( SCIPcreateChild(scip, &node2, 0.0, SCIPgetLocalTransEstimate(scip)) ); 1682 1683 /* shift the second half of variables */ 1684 cnt = 0; 1685 for( j = ind+1; j < nbranchvars; ++j ) 1686 { 1687 branchvars[cnt] = branchvars[j]; 1688 branchindvars[cnt++] = branchindvars[j]; 1689 } 1690 assert(cnt == nbranchvars - (ind + 1)); 1691 1692 /* create branching constraint for node 2 */ 1693 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "brright_#% " SCIP_LONGINT_FORMAT , SCIPgetNNodes(scip)); 1694 SCIP_CALL( SCIPcreateConsCardinality(scip, &cons2, name, cnt, branchvars, (int)splitval2, branchindvars, NULL, 1695 FALSE, TRUE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, TRUE) ); 1696 1697 /* add constraint to node */ 1698 SCIP_CALL( SCIPaddConsNode(scip, node2, cons2, NULL) ); 1699 1700 /* release constraint */ 1701 SCIP_CALL( SCIPreleaseCons(scip, &cons2) ); 1702 } 1703 } 1704 1705 /* free buffer arrays */ 1706 SCIPfreeBufferArray(scip, &branchindvars); 1707 SCIPfreeBufferArray(scip, &branchvars); 1708 1709 return SCIP_OKAY; 1710 } 1711 1712 /** enforcement method 1713 * 1714 * We check whether the current solution is feasible. If not, the cardinality constraints can be enforced by different 1715 * branching rules: 1716 * 1717 * - Unbalanced branching: Branch on the neighborhood of a single variable \f$i\f$, i.e., in one branch \f$x_i\f$ is 1718 * fixed to zero and in the other we modify cardinality constraints \f$|\mbox{supp}(x)| \leq k\f$ with \f$i\in D\f$ to 1719 * \f$|\mbox{supp}(x_{D\setminus i}) \leq k-1\f$ 1720 * 1721 * - Balanced branching: First, choose a cardinality constraint \f$|\mbox{supp}(x_D) \leq k\f$ that is violated by the 1722 * current LP solution. Then, we compute \f$W = \sum_{j=1}^n |x_i|\f$ and \f$w = \sum_{j=1}^n j\, |x_i|\f$. Next, 1723 * search for the index \f$r\f$ that satisfies 1724 * \f[ 1725 * r \leq \frac{w}{W} < r+1. 1726 * \f] 1727 * Choose a number \f$s\f$ with \f$0\leq s < \min\{k, r\}\f$. The branches are then 1728 * \f[ 1729 * |\mbox{supp}(x_{d_1}, \ldots, x_{d_r})| \leq s \qquad \mbox{and}\qquad 1730 * |\mbox{supp}(x_{d_{r+1}}, \ldots, x_{d_{n}})| \leq k-s-1, 1731 * \f] 1732 * where \f$d_1, \ldots, d_n\f$ are the elements of the set \f$D\f$. 1733 * 1734 * The branching constraint is chosen by the largest sum of variable values. 1735 */ 1736 static 1737 SCIP_RETCODE enforceCardinality( 1738 SCIP* scip, /**< SCIP pointer */ 1739 SCIP_CONSHDLR* conshdlr, /**< constraint handler */ 1740 SCIP_SOL* sol, /**< solution to be enforced (or NULL) */ 1741 int nconss, /**< number of constraints */ 1742 SCIP_CONS** conss, /**< indicator constraints */ 1743 SCIP_RESULT* result /**< result */ 1744 ) 1745 { 1746 SCIP_CONSHDLRDATA* conshdlrdata; 1747 SCIP_CONSDATA* consdata; 1748 SCIP_CONS* branchcons; 1749 SCIP_Real maxweight; 1750 SCIP_VAR** indvars; 1751 SCIP_VAR** vars; 1752 int nvars; 1753 int cardval; 1754 1755 SCIP_Bool branchbalanced = FALSE; 1756 SCIP_Bool branchallpos = TRUE; 1757 SCIP_Bool branchallneg = TRUE; 1758 int branchnnonzero; 1759 int branchpos; 1760 int c; 1761 1762 assert(scip != NULL); 1763 assert(conshdlr != NULL); 1764 assert(conss != NULL); 1765 assert(result != NULL); 1766 1767 maxweight = -SCIP_REAL_MAX; 1768 branchcons = NULL; 1769 branchnnonzero = -1; 1770 branchpos = -1; 1771 1772 SCIPdebugMsg(scip, "Enforcing cardinality constraints <%s>.\n", SCIPconshdlrGetName(conshdlr) ); 1773 *result = SCIP_FEASIBLE; 1774 1775 /* get constraint handler data */ 1776 conshdlrdata = SCIPconshdlrGetData(conshdlr); 1777 assert(conshdlrdata != NULL); 1778 1779 /* search for a constraint with largest violation; from this constraint, we select the variable with largest LP value */ 1780 for( c = 0; c < nconss; ++c ) 1781 { 1782 SCIP_CONS* cons; 1783 SCIP_Bool cutoff; 1784 SCIP_Real weight; 1785 SCIP_Real maxval; 1786 SCIP_Bool allpos = TRUE; 1787 SCIP_Bool allneg = TRUE; 1788 int nnonzero; /* number of variables that are currently deactivated in constraint */ 1789 int pos; /* position of variable with largest LP solution value */ 1790 int nchgdomain; 1791 int cnt; 1792 int j; 1793 1794 cons = conss[c]; 1795 assert(cons != NULL); 1796 consdata = SCIPconsGetData(cons); 1797 assert(consdata != NULL); 1798 1799 nchgdomain = 0; 1800 cnt = 0; 1801 nnonzero = 0; 1802 pos = -1; 1803 nvars = consdata->nvars; 1804 vars = consdata->vars; 1805 indvars = consdata->indvars; 1806 cardval = consdata->cardval; 1807 1808 /* do nothing if there are not enough variables - this is usually eliminated by preprocessing */ 1809 if( nvars < 2 ) 1810 continue; 1811 1812 /* first perform propagation (it might happen that standard propagation is turned off) */ 1813 SCIP_CALL( propCardinality(scip, cons, consdata, &cutoff, &nchgdomain) ); 1814 1815 SCIPdebugMsg(scip, "propagating <%s> in enforcing (cutoff: %u, domain reductions: %d).\n", 1816 SCIPconsGetName(cons), cutoff, nchgdomain); 1817 if( cutoff ) 1818 { 1819 *result = SCIP_CUTOFF; 1820 return SCIP_OKAY; 1821 } 1822 if( nchgdomain > 0 ) 1823 { 1824 *result = SCIP_REDUCEDDOM; 1825 return SCIP_OKAY; 1826 } 1827 assert(nchgdomain == 0); 1828 1829 /* check constraint */ 1830 weight = 0.0; 1831 maxval = -SCIPinfinity(scip); 1832 1833 for( j = 0; j < nvars; ++j ) 1834 { 1835 SCIP_VAR* var; 1836 1837 /* check whether indicator variable is zero, but variable in cardinality constraint is not fixed to zero; 1838 * if the variable is not multiaggregated this case should already be handled in propagation */ 1839 if( SCIPvarGetUbLocal(indvars[j]) == 0.0 && 1840 ( 1841 !SCIPisFeasZero(scip, SCIPvarGetLbLocal(vars[j])) || !SCIPisFeasZero(scip, SCIPvarGetUbLocal(vars[j])) 1842 ) 1843 ) 1844 { 1845 *result = SCIP_CUTOFF; 1846 return SCIP_OKAY; 1847 } 1848 1849 assert(SCIPvarGetStatus(indvars[j]) != SCIP_VARSTATUS_MULTAGGR); 1850 1851 var = vars[j]; 1852 1853 /* variable is not fixed to nonzero */ 1854 if( SCIPvarGetLbLocal(indvars[j]) != 1.0 1855 && !SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var)) 1856 && !SCIPisFeasNegative(scip, SCIPvarGetUbLocal(var)) 1857 ) 1858 { 1859 SCIP_Real val; 1860 1861 val = SCIPgetSolVal(scip, sol, var); 1862 if( SCIPisFeasPositive(scip, val)) 1863 allneg = FALSE; 1864 else if( SCIPisFeasNegative(scip, val)) 1865 allpos = FALSE; 1866 val = REALABS(val); 1867 1868 if( !SCIPisFeasZero(scip, val) ) 1869 { 1870 /* determine maximum nonzero-variable solution value */ 1871 if( SCIPisFeasGT(scip, val, maxval) ) 1872 { 1873 pos = j; 1874 maxval = val; 1875 } 1876 1877 weight += val; 1878 ++cnt; 1879 } 1880 } 1881 else 1882 ++nnonzero; 1883 } 1884 weight -= cardval; 1885 weight += nnonzero; 1886 1887 /* if we detected a cut off */ 1888 if( nnonzero > cardval ) 1889 { 1890 SCIPdebugMsg(scip, "Detected cut off: constraint <%s> has %d many variables that can be treated as nonzero, \ 1891 although only %d many are feasible.\n", SCIPconsGetName(cons), nnonzero, cardval); 1892 *result = SCIP_CUTOFF; 1893 return SCIP_OKAY; 1894 } 1895 /* else if domain can be reduced (since node 2 created in branchUnbalancedCardinality() would be infeasible) */ 1896 else if( cnt > 0 && nnonzero + 1 > cardval ) 1897 { 1898 SCIP_Bool infeasible; 1899 int v; 1900 1901 for( v = 0; v < nvars; ++v ) 1902 { 1903 SCIP_VAR* var; 1904 1905 var = vars[v]; 1906 1907 /* variable is not fixed to nonzero */ 1908 if( !SCIPisFeasEQ(scip, SCIPvarGetLbLocal(indvars[v]), 1.0) 1909 && !SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var)) 1910 && !SCIPisFeasNegative(scip, SCIPvarGetUbLocal(var)) 1911 ) 1912 { 1913 SCIP_CALL( fixVariableZeroNode(scip, var, SCIPgetCurrentNode(scip), &infeasible) ); 1914 assert(!infeasible); 1915 SCIPdebugMsg(scip, "detected domain reduction in enforcing: fixed variable <%s> to zero.\n", SCIPvarGetName(var)); 1916 } 1917 } 1918 1919 *result = SCIP_REDUCEDDOM; 1920 return SCIP_OKAY; 1921 } 1922 1923 /* if constraint is violated */ 1924 if( cnt > cardval - nnonzero && weight > maxweight ) 1925 { 1926 maxweight = weight; 1927 branchcons = cons; 1928 branchnnonzero = nnonzero; 1929 branchpos = pos; 1930 branchallneg = allneg; 1931 branchallpos = allpos; 1932 } 1933 } 1934 1935 /* if all constraints are feasible */ 1936 if( branchcons == NULL ) 1937 { 1938 SCIP_SOL* primsol; 1939 SCIP_Bool success; 1940 1941 /* polish primal solution */ 1942 SCIP_CALL( SCIPcreateSolCopy(scip, &primsol, sol) ); 1943 SCIP_CALL( polishPrimalSolution(scip, conss, nconss, sol, primsol) ); 1944 SCIP_CALL( SCIPtrySol(scip, primsol, FALSE, TRUE, FALSE, TRUE, FALSE, &success) ); 1945 SCIP_CALL( SCIPfreeSol(scip, &primsol) ); 1946 1947 SCIPdebugMsg(scip, "All cardinality constraints are feasible.\n"); 1948 return SCIP_OKAY; 1949 } 1950 assert(branchnnonzero >= 0); 1951 assert(branchpos >= 0); 1952 1953 /* get data for branching or domain reduction */ 1954 consdata = SCIPconsGetData(branchcons); 1955 assert(consdata != NULL); 1956 nvars = consdata->nvars; 1957 vars = consdata->vars; 1958 indvars = consdata->indvars; 1959 cardval = consdata->cardval; 1960 1961 /* we only use balanced branching if either the lower or the upper bound row of the branching constraint is known 1962 * to be tight or violated */ 1963 if( conshdlrdata->branchbalanced && !SCIPisFeasNegative(scip, maxweight) && ( branchallneg || branchallpos ) 1964 && (conshdlrdata->balanceddepth == -1 || SCIPgetDepth(scip) <= conshdlrdata->balanceddepth) 1965 ) 1966 { 1967 branchbalanced = TRUE; 1968 } 1969 1970 /* apply branching rule */ 1971 if( branchbalanced ) 1972 { 1973 SCIP_CALL( branchBalancedCardinality(scip, conshdlr, sol, branchcons, vars, indvars, nvars, cardval, branchnnonzero, branchpos, 1974 conshdlrdata->balancedcutoff) ); 1975 } 1976 else 1977 { 1978 SCIP_CALL( branchUnbalancedCardinality(scip, sol, branchcons, vars, indvars, nvars, cardval, branchnnonzero, 1979 branchpos) ); 1980 } 1981 1982 SCIP_CALL( SCIPresetConsAge(scip, branchcons) ); 1983 *result = SCIP_BRANCHED; 1984 1985 return SCIP_OKAY; 1986 } 1987 1988 /** Generate row 1989 * 1990 * We generate the row corresponding to the following simple valid inequalities: 1991 * \f[ 1992 * \frac{x_1}{u_1} + \ldots + \frac{x_n}{u_n} \leq k\qquad\mbox{and}\qquad 1993 * \frac{x_1}{\ell_1} + \ldots + \frac{x_n}{\ell_1} \leq k, 1994 * \f] 1995 * where \f$\ell_1, \ldots, \ell_n\f$ and \f$u_1, \ldots, u_n\f$ are the nonzero and finite lower and upper bounds of 1996 * the variables \f$x_1, \ldots, x_n\f$ and k is the right hand side of the cardinality constraint. If at least k upper 1997 * bounds < 0 or a lower bounds > 0, the constraint itself is redundant, so the cut is not applied (lower bounds > 0 1998 * and upper bounds < 0 are usually detected in presolving or propagation). Infinite bounds and zero are skipped. Thus 1999 * \f$\ell_1, \ldots, \ell_n\f$ are all negative, which results in the \f$\leq\f$ inequality. 2000 * 2001 * Note that in fact, any mixture of nonzero finite lower and upper bounds would lead to a valid inequality as 2002 * above. However, usually either the lower or upper bound is nonzero. Thus, the above inequalities are the most 2003 * interesting. 2004 */ 2005 static 2006 SCIP_RETCODE generateRowCardinality( 2007 SCIP* scip, /**< SCIP pointer */ 2008 SCIP_CONSHDLR* conshdlr, /**< constraint handler */ 2009 SCIP_CONS* cons, /**< constraint */ 2010 SCIP_Bool local, /**< produce local cut? */ 2011 SCIP_ROW** rowlb, /**< output: row for lower bounds (or NULL if not needed) */ 2012 SCIP_ROW** rowub /**< output: row for upper bounds (or NULL if not needed) */ 2013 ) 2014 { 2015 char name[SCIP_MAXSTRLEN]; 2016 SCIP_CONSDATA* consdata; 2017 SCIP_VAR** vars; 2018 SCIP_Real* vals; 2019 SCIP_Real val; 2020 int nvars; 2021 int cnt; 2022 int j; 2023 2024 assert(scip != NULL); 2025 assert(conshdlr != NULL); 2026 assert(cons != NULL); 2027 2028 consdata = SCIPconsGetData(cons); 2029 assert(consdata != NULL); 2030 assert(consdata->vars != NULL); 2031 assert(consdata->indvars != NULL); 2032 2033 nvars = consdata->nvars; 2034 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) ); 2035 SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars) ); 2036 2037 /* take care of upper bounds */ 2038 if( rowub != NULL ) 2039 { 2040 int cardval; 2041 2042 cnt = 0; 2043 cardval = consdata->cardval; 2044 for( j = 0; j < nvars; ++j ) 2045 { 2046 if( local ) 2047 val = SCIPvarGetLbLocal(consdata->vars[j]); 2048 else 2049 val = SCIPvarGetUbGlobal(consdata->vars[j]); 2050 2051 /* if a variable may be treated as nonzero, then update cardinality value */ 2052 if( SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(consdata->indvars[j]), 1.0) ) 2053 { 2054 --cardval; 2055 continue; 2056 } 2057 2058 if( !SCIPisInfinity(scip, val) && !SCIPisZero(scip, val) && !SCIPisNegative(scip, val) ) 2059 { 2060 assert(consdata->vars[j] != NULL); 2061 vars[cnt] = consdata->vars[j]; 2062 vals[cnt++] = 1.0/val; 2063 } 2064 } 2065 assert(cardval >= 0); 2066 2067 /* if cut is meaningful */ 2068 if( cnt > cardval ) 2069 { 2070 /* create upper bound inequality if at least two of the bounds are finite and nonzero */ 2071 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cardub#%s", SCIPconsGetName(cons)); 2072 SCIP_CALL( SCIPcreateEmptyRowCons(scip, rowub, cons, name, -SCIPinfinity(scip), (SCIP_Real)cardval, 2073 local, TRUE, FALSE) ); 2074 SCIP_CALL( SCIPaddVarsToRow(scip, *rowub, cnt, vars, vals) ); 2075 SCIPdebug( SCIP_CALL( SCIPprintRow(scip, *rowub, NULL) ) ); 2076 } 2077 } 2078 2079 /* take care of lower bounds */ 2080 if( rowlb != NULL ) 2081 { 2082 int cardval; 2083 2084 cnt = 0; 2085 cardval = consdata->cardval; 2086 for( j = 0; j < nvars; ++j ) 2087 { 2088 if( local ) 2089 val = SCIPvarGetLbLocal(consdata->vars[j]); 2090 else 2091 val = SCIPvarGetLbGlobal(consdata->vars[j]); 2092 2093 /* if a variable may be treated as nonzero, then update cardinality value */ 2094 if( SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(consdata->indvars[j]), 1.0) ) 2095 { 2096 --cardval; 2097 continue; 2098 } 2099 2100 if( !SCIPisInfinity(scip, -val) && !SCIPisZero(scip, val) && !SCIPisPositive(scip, val) ) 2101 { 2102 assert(consdata->vars[j] != NULL); 2103 vars[cnt] = consdata->vars[j]; 2104 vals[cnt++] = 1.0/val; 2105 } 2106 } 2107 assert(cardval >= 0); 2108 2109 /* if cut is meaningful */ 2110 /* coverity[copy_paste_error] */ 2111 if( cnt > cardval ) 2112 { 2113 /* create lower bound inequality if at least two of the bounds are finite and nonzero */ 2114 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cardlb#%s", SCIPconsGetName(cons)); 2115 SCIP_CALL( SCIPcreateEmptyRowCons(scip, rowlb, cons, name, -SCIPinfinity(scip), (SCIP_Real)cardval, 2116 local, TRUE, FALSE) ); 2117 SCIP_CALL( SCIPaddVarsToRow(scip, *rowlb, nvars, vars, vals) ); 2118 SCIPdebug( SCIP_CALL( SCIPprintRow(scip, *rowlb, NULL) ) ); 2119 } 2120 } 2121 2122 SCIPfreeBufferArray(scip, &vals); 2123 SCIPfreeBufferArray(scip, &vars); 2124 2125 return SCIP_OKAY; 2126 } 2127 2128 /** initialize or separate bound inequalities from cardinality constraints 2129 * (see the function \ref generateRowCardinality() for an explanation of bound inequalities) 2130 */ 2131 static 2132 SCIP_RETCODE initsepaBoundInequalityFromCardinality( 2133 SCIP* scip, /**< SCIP pointer */ 2134 SCIP_CONSHDLR* conshdlr, /**< constraint handler */ 2135 SCIP_CONS** conss, /**< cardinality constraints */ 2136 int nconss, /**< number of cardinality constraints */ 2137 SCIP_SOL* sol, /**< LP solution to be separated (or NULL) */ 2138 SCIP_Bool solvedinitlp, /**< TRUE if initial LP relaxation at a node is solved */ 2139 int* ngen, /**< pointer to store number of cuts generated (or NULL) */ 2140 SCIP_Bool* cutoff /**< pointer to store whether a cutoff occurred */ 2141 ) 2142 { 2143 int cnt = 0; 2144 int c; 2145 2146 assert(scip != NULL); 2147 assert(conss != NULL); 2148 2149 *cutoff = FALSE; 2150 2151 for( c = nconss-1; c >= 0; --c ) 2152 { 2153 SCIP_CONSDATA* consdata; 2154 SCIP_ROW* rowub = NULL; 2155 SCIP_ROW* rowlb = NULL; 2156 SCIP_Bool release = FALSE; 2157 2158 assert(conss != NULL); 2159 assert(conss[c] != NULL); 2160 consdata = SCIPconsGetData(conss[c]); 2161 assert(consdata != NULL); 2162 2163 if( solvedinitlp ) 2164 SCIPdebugMsg(scip, "Separating inequalities for cardinality constraint <%s>.\n", SCIPconsGetName(conss[c]) ); 2165 else 2166 SCIPdebugMsg(scip, "Checking for initial rows for cardinality constraint <%s>.\n", SCIPconsGetName(conss[c]) ); 2167 2168 /* generate rows associated to cardinality constraint; the rows are stored in the constraint data 2169 * if they are globally valid */ 2170 if( SCIPconsIsLocal(conss[c]) ) 2171 { 2172 SCIP_CALL( generateRowCardinality(scip, conshdlr, conss[c], TRUE, &rowlb, &rowub) ); 2173 release = TRUE; 2174 } 2175 else 2176 { 2177 if( consdata->rowub == NULL || consdata->rowlb == NULL ) 2178 { 2179 SCIP_CALL( generateRowCardinality(scip, conshdlr, conss[c], FALSE, 2180 (consdata->rowlb == NULL) ? &consdata->rowlb : NULL, 2181 (consdata->rowub == NULL) ? &consdata->rowub : NULL) );/*lint !e826*/ 2182 } 2183 rowub = consdata->rowub; 2184 rowlb = consdata->rowlb; 2185 } 2186 2187 /* put corresponding rows into LP */ 2188 if( rowub != NULL && !SCIProwIsInLP(rowub) && ( solvedinitlp || SCIPisCutEfficacious(scip, sol, rowub) ) ) 2189 { 2190 assert(SCIPisInfinity(scip, -SCIProwGetLhs(rowub))); 2191 assert(SCIPisLE(scip, SCIProwGetRhs(rowub), (SCIP_Real)consdata->cardval)); 2192 2193 SCIP_CALL( SCIPaddRow(scip, rowub, FALSE, cutoff) ); 2194 SCIPdebug( SCIP_CALL( SCIPprintRow(scip, rowub, NULL) ) ); 2195 2196 if( solvedinitlp ) 2197 { 2198 SCIP_CALL( SCIPresetConsAge(scip, conss[c]) ); 2199 } 2200 ++cnt; 2201 } 2202 2203 if( ! (*cutoff) && rowlb != NULL && !SCIProwIsInLP(rowlb) 2204 && ( solvedinitlp || SCIPisCutEfficacious(scip, sol, rowlb) ) 2205 ) 2206 { 2207 assert(SCIPisInfinity(scip, -SCIProwGetLhs(rowlb))); 2208 assert(SCIPisLE(scip, SCIProwGetRhs(rowlb), (SCIP_Real)consdata->cardval)); 2209 2210 SCIP_CALL( SCIPaddRow(scip, rowlb, FALSE, cutoff) ); 2211 SCIPdebug( SCIP_CALL( SCIPprintRow(scip, rowlb, NULL) ) ); 2212 2213 if( solvedinitlp ) 2214 { 2215 SCIP_CALL( SCIPresetConsAge(scip, conss[c]) ); 2216 } 2217 ++cnt; 2218 } 2219 2220 if( release ) 2221 { 2222 if( rowlb != NULL ) 2223 { 2224 SCIP_CALL( SCIPreleaseRow(scip, &rowlb) ); 2225 } 2226 if( rowub != NULL ) 2227 { 2228 SCIP_CALL( SCIPreleaseRow(scip, &rowub) ); 2229 } 2230 } 2231 2232 if( *cutoff ) 2233 break; 2234 } 2235 2236 /* store number of generated cuts */ 2237 if( ngen != NULL ) 2238 *ngen = cnt; 2239 2240 return SCIP_OKAY; 2241 } 2242 2243 /** separates cardinality constraints for arbitrary solutions */ 2244 static 2245 SCIP_RETCODE separateCardinality( 2246 SCIP* scip, /**< SCIP pointer */ 2247 SCIP_CONSHDLR* conshdlr, /**< constraint handler */ 2248 SCIP_SOL* sol, /**< solution to be separated (or NULL) */ 2249 int nconss, /**< number of constraints */ 2250 SCIP_CONS** conss, /**< cardinality constraints */ 2251 SCIP_RESULT* result /**< result */ 2252 ) 2253 { 2254 SCIP_Bool cutoff; 2255 int ngen = 0; 2256 2257 assert(scip != NULL); 2258 assert(conshdlr != NULL); 2259 assert(conss != NULL); 2260 assert(result != NULL); 2261 2262 *result = SCIP_DIDNOTRUN; 2263 2264 if( nconss == 0 ) 2265 return SCIP_OKAY; 2266 2267 /* only separate cuts if we are not close to terminating */ 2268 if( SCIPisStopped(scip) ) 2269 return SCIP_OKAY; 2270 2271 *result = SCIP_DIDNOTFIND; 2272 2273 /* separate bound inequalities from cardinality constraints */ 2274 SCIP_CALL( initsepaBoundInequalityFromCardinality(scip, conshdlr, conss, nconss, sol, TRUE, &ngen, &cutoff) ); 2275 if( cutoff ) 2276 { 2277 *result = SCIP_CUTOFF; 2278 return SCIP_OKAY; 2279 } 2280 2281 /* evaluate results */ 2282 if( ngen > 0 ) 2283 *result = SCIP_SEPARATED; 2284 SCIPdebugMsg(scip, "Separated %d bound inequalities.\n", ngen); 2285 2286 return SCIP_OKAY; 2287 } 2288 2289 /* ---------------------------- constraint handler callback methods ----------------------*/ 2290 2291 /** copy method for constraint handler plugins (called when SCIP copies plugins) */ 2292 static 2293 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyCardinality) 2294 { /*lint --e{715}*/ 2295 assert(scip != NULL); 2296 assert(conshdlr != NULL); 2297 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2298 2299 /* call inclusion method of constraint handler */ 2300 SCIP_CALL( SCIPincludeConshdlrCardinality(scip) ); 2301 2302 *valid = TRUE; 2303 2304 return SCIP_OKAY; 2305 } 2306 2307 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */ 2308 static 2309 SCIP_DECL_CONSFREE(consFreeCardinality) 2310 { 2311 SCIP_CONSHDLRDATA* conshdlrdata; 2312 2313 assert(scip != NULL); 2314 assert(conshdlr != NULL); 2315 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2316 2317 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2318 assert(conshdlrdata != NULL); 2319 2320 /* free hash map */ 2321 if( conshdlrdata->varhash != NULL ) 2322 { 2323 SCIPhashmapFree(&conshdlrdata->varhash); 2324 } 2325 2326 SCIPfreeBlockMemory(scip, &conshdlrdata); 2327 2328 return SCIP_OKAY; 2329 } 2330 2331 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */ 2332 static 2333 SCIP_DECL_CONSEXITSOL(consExitsolCardinality) 2334 { /*lint --e{715}*/ 2335 SCIP_CONSHDLRDATA* conshdlrdata; 2336 int c; 2337 2338 assert(scip != NULL); 2339 assert(conshdlr != NULL); 2340 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2341 2342 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2343 assert(conshdlrdata != NULL); 2344 2345 /* check each constraint */ 2346 for( c = 0; c < nconss; ++c ) 2347 { 2348 SCIP_CONSDATA* consdata; 2349 2350 assert(conss != NULL); 2351 assert(conss[c] != NULL); 2352 consdata = SCIPconsGetData(conss[c]); 2353 assert(consdata != NULL); 2354 2355 SCIPdebugMsg(scip, "Exiting cardinality constraint <%s>.\n", SCIPconsGetName(conss[c]) ); 2356 2357 /* free rows */ 2358 if( consdata->rowub != NULL ) 2359 { 2360 SCIP_CALL( SCIPreleaseRow(scip, &consdata->rowub) ); 2361 } 2362 if( consdata->rowlb != NULL ) 2363 { 2364 SCIP_CALL( SCIPreleaseRow(scip, &consdata->rowlb) ); 2365 } 2366 } 2367 2368 /* free hash map */ 2369 if( conshdlrdata->varhash != NULL ) 2370 { 2371 SCIPhashmapFree(&conshdlrdata->varhash); 2372 } 2373 2374 return SCIP_OKAY; 2375 } 2376 2377 /** frees specific constraint data */ 2378 static 2379 SCIP_DECL_CONSDELETE(consDeleteCardinality) 2380 { /*lint --e{737, 647}*/ 2381 assert(scip != NULL); 2382 assert(conshdlr != NULL); 2383 assert(cons != NULL); 2384 assert(consdata != NULL); 2385 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2386 2387 SCIPdebugMsg(scip, "Deleting cardinality constraint <%s>.\n", SCIPconsGetName(cons) ); 2388 2389 /* drop events on transformed variables */ 2390 if( SCIPconsIsTransformed(cons) ) 2391 { 2392 SCIP_CONSHDLRDATA* conshdlrdata; 2393 int j; 2394 2395 /* get constraint handler data */ 2396 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2397 assert(conshdlrdata != NULL); 2398 assert(conshdlrdata->eventhdlr != NULL); 2399 2400 for( j = 0; j < (*consdata)->nvars; ++j ) 2401 { 2402 SCIP_CALL( dropVarEventCardinality(scip, conshdlrdata->eventhdlr, *consdata, (*consdata)->vars[j], 2403 (*consdata)->indvars[j], &(*consdata)->eventdatas[j]) ); 2404 assert((*consdata)->eventdatas[j] == NULL); 2405 } 2406 } 2407 2408 if( (*consdata)->weights != NULL ) 2409 { 2410 SCIPfreeBlockMemoryArray(scip, &(*consdata)->weights, (*consdata)->maxvars); 2411 } 2412 SCIPfreeBlockMemoryArray(scip, &(*consdata)->eventdatas, (*consdata)->maxvars); 2413 SCIPfreeBlockMemoryArray(scip, &(*consdata)->eventvarscurrent, 4 * (*consdata)->maxvars);/*lint !e647*/ 2414 SCIPfreeBlockMemoryArray(scip, &(*consdata)->eventdatascurrent, 4 * (*consdata)->maxvars);/*lint !e647*/ 2415 SCIPfreeBlockMemoryArray(scip, &(*consdata)->indvars, (*consdata)->maxvars); 2416 SCIPfreeBlockMemoryArray(scip, &(*consdata)->vars, (*consdata)->maxvars); 2417 2418 /* free rows */ 2419 if( (*consdata)->rowub != NULL ) 2420 { 2421 SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->rowub) ); 2422 } 2423 if( (*consdata)->rowlb != NULL ) 2424 { 2425 SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->rowlb) ); 2426 } 2427 assert((*consdata)->rowub == NULL); 2428 assert((*consdata)->rowlb == NULL); 2429 2430 SCIPfreeBlockMemory(scip, consdata); 2431 2432 return SCIP_OKAY; 2433 } 2434 2435 /** transforms constraint data into data belonging to the transformed problem */ 2436 static 2437 SCIP_DECL_CONSTRANS(consTransCardinality) 2438 { 2439 SCIP_CONSDATA* consdata; 2440 SCIP_CONSHDLRDATA* conshdlrdata; 2441 SCIP_CONSDATA* sourcedata; 2442 char s[SCIP_MAXSTRLEN]; 2443 int j; 2444 2445 assert(scip != NULL); 2446 assert(conshdlr != NULL); 2447 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2448 assert(sourcecons != NULL); 2449 assert(targetcons != NULL); 2450 2451 /* get constraint handler data */ 2452 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2453 assert(conshdlrdata != NULL); 2454 assert(conshdlrdata->eventhdlr != NULL); 2455 2456 SCIPdebugMsg(scip, "Transforming cardinality constraint: <%s>.\n", SCIPconsGetName(sourcecons) ); 2457 2458 /* get data of original constraint */ 2459 sourcedata = SCIPconsGetData(sourcecons); 2460 assert(sourcedata != NULL); 2461 assert(sourcedata->nvars > 0); 2462 assert(sourcedata->nvars <= sourcedata->maxvars); 2463 2464 /* create constraint data */ 2465 SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) ); 2466 2467 consdata->cons = NULL; 2468 consdata->nvars = sourcedata->nvars; 2469 consdata->maxvars = sourcedata->nvars; 2470 consdata->cardval = sourcedata->cardval; 2471 consdata->rowub = NULL; 2472 consdata->rowlb = NULL; 2473 consdata->eventdatascurrent = NULL; 2474 consdata->neventdatascurrent = 0; 2475 consdata->ntreatnonzeros = 0; 2476 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->vars, consdata->nvars) ); 2477 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->indvars, consdata->nvars) ); 2478 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->eventdatas, consdata->nvars) ); 2479 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->eventdatascurrent, 4*consdata->nvars) );/*lint !e647*/ 2480 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->eventvarscurrent, 4*consdata->nvars) );/*lint !e647*/ 2481 2482 /* if weights were used */ 2483 if( sourcedata->weights != NULL ) 2484 { 2485 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->weights, sourcedata->weights, consdata->nvars) ); 2486 } 2487 else 2488 consdata->weights = NULL; 2489 2490 for( j = 0; j < sourcedata->nvars; ++j ) 2491 { 2492 assert(sourcedata->vars[j] != 0); 2493 assert(sourcedata->indvars[j] != 0); 2494 SCIP_CALL( SCIPgetTransformedVar(scip, sourcedata->vars[j], &(consdata->vars[j])) ); 2495 SCIP_CALL( SCIPgetTransformedVar(scip, sourcedata->indvars[j], &(consdata->indvars[j])) ); 2496 2497 /* if variable is fixed to be nonzero */ 2498 if( SCIPisFeasEQ(scip, SCIPvarGetLbLocal(consdata->indvars[j]), 1.0) ) 2499 ++(consdata->ntreatnonzeros); 2500 } 2501 2502 /* create transformed constraint with the same flags */ 2503 (void) SCIPsnprintf(s, SCIP_MAXSTRLEN, "t_%s", SCIPconsGetName(sourcecons)); 2504 SCIP_CALL( SCIPcreateCons(scip, targetcons, s, conshdlr, consdata, 2505 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), 2506 SCIPconsIsEnforced(sourcecons), SCIPconsIsChecked(sourcecons), 2507 SCIPconsIsPropagated(sourcecons), SCIPconsIsLocal(sourcecons), 2508 SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons), 2509 SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) ); 2510 2511 consdata->cons = *targetcons; 2512 assert(consdata->cons != NULL); 2513 2514 /* catch bound change events on variable */ 2515 for( j = 0; j < consdata->nvars; ++j ) 2516 { 2517 SCIP_CALL( catchVarEventCardinality(scip, conshdlrdata->eventhdlr, consdata, 2518 consdata->vars[j], consdata->indvars[j], j, &consdata->eventdatas[j]) ); 2519 assert(consdata->eventdatas[j] != NULL); 2520 } 2521 2522 #ifdef SCIP_DEBUG 2523 if( SCIPisGT(scip, (SCIP_Real)consdata->ntreatnonzeros, consdata->cardval) ) 2524 { 2525 SCIPdebugMsg(scip, "constraint <%s> has %d variables fixed to be nonzero, allthough the constraint allows \ 2526 only %d nonzero variables\n", SCIPconsGetName(*targetcons), consdata->ntreatnonzeros, consdata->cardval); 2527 } 2528 #endif 2529 2530 return SCIP_OKAY; 2531 } 2532 2533 /** presolving method of constraint handler */ 2534 static 2535 SCIP_DECL_CONSPRESOL(consPresolCardinality) 2536 { /*lint --e{715}*/ 2537 SCIPdebug( int oldnfixedvars; ) 2538 SCIPdebug( int oldndelconss; ) 2539 SCIPdebug( int oldnupgdconss; ) 2540 int nremovedvars; 2541 SCIP_EVENTHDLR* eventhdlr; 2542 int c; 2543 2544 assert(scip != NULL); 2545 assert(conshdlr != NULL); 2546 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2547 assert(result != NULL); 2548 2549 SCIPdebugMsg(scip, "Presolving cardinality constraints.\n"); 2550 2551 *result = SCIP_DIDNOTRUN; 2552 SCIPdebug( oldnfixedvars = *nfixedvars; ) 2553 SCIPdebug( oldndelconss = *ndelconss; ) 2554 SCIPdebug( oldnupgdconss = *nupgdconss; ) 2555 nremovedvars = 0; 2556 2557 /* only run if success if possible */ 2558 if( nrounds == 0 || nnewfixedvars > 0 || nnewaggrvars > 0 ) 2559 { 2560 /* get constraint handler data */ 2561 assert(SCIPconshdlrGetData(conshdlr) != NULL); 2562 eventhdlr = SCIPconshdlrGetData(conshdlr)->eventhdlr; 2563 assert(eventhdlr != NULL); 2564 2565 *result = SCIP_DIDNOTFIND; 2566 2567 /* check each constraint */ 2568 for( c = 0; c < nconss; ++c ) 2569 { 2570 SCIP_CONSDATA* consdata; 2571 SCIP_CONS* cons; 2572 SCIP_Bool cutoff; 2573 SCIP_Bool success; 2574 2575 assert(conss != NULL); 2576 assert(conss[c] != NULL); 2577 cons = conss[c]; 2578 consdata = SCIPconsGetData(cons); 2579 2580 assert(consdata != NULL); 2581 assert(consdata->nvars >= 0); 2582 assert(consdata->nvars <= consdata->maxvars); 2583 assert(!SCIPconsIsModifiable(cons)); 2584 2585 /* perform one presolving round */ 2586 SCIP_CALL( presolRoundCardinality(scip, cons, consdata, eventhdlr, &cutoff, &success, 2587 ndelconss, nupgdconss, nfixedvars, &nremovedvars) ); 2588 2589 if( cutoff ) 2590 { 2591 SCIPdebugMsg(scip, "presolving detected cutoff.\n"); 2592 *result = SCIP_CUTOFF; 2593 return SCIP_OKAY; 2594 } 2595 2596 if( success ) 2597 *result = SCIP_SUCCESS; 2598 } 2599 } 2600 (*nchgcoefs) += nremovedvars; 2601 2602 SCIPdebug( SCIPdebugMsg(scip, "presolving fixed %d variables, removed %d variables, deleted %d constraints, \ 2603 and upgraded %d constraints.\n", *nfixedvars - oldnfixedvars, nremovedvars, *ndelconss - oldndelconss, 2604 *nupgdconss - oldnupgdconss); ) 2605 2606 return SCIP_OKAY; 2607 } 2608 2609 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */ 2610 static 2611 SCIP_DECL_CONSINITLP(consInitlpCardinality) 2612 { /*lint --e{715}*/ 2613 SCIP_Bool cutoff; 2614 2615 assert(scip != NULL); 2616 assert(conshdlr != NULL); 2617 2618 /* checking for initial rows for cardinality constraints */ 2619 SCIP_CALL( initsepaBoundInequalityFromCardinality(scip, conshdlr, conss, nconss, NULL, FALSE, NULL, &cutoff) ); 2620 assert(!cutoff); 2621 2622 return SCIP_OKAY; 2623 } 2624 2625 /** separation method of constraint handler for LP solutions */ 2626 static 2627 SCIP_DECL_CONSSEPALP(consSepalpCardinality) 2628 { /*lint --e{715}*/ 2629 assert(scip != NULL); 2630 assert(conshdlr != NULL); 2631 assert(conss != NULL); 2632 assert(result != NULL); 2633 2634 SCIP_CALL( separateCardinality(scip, conshdlr, NULL, nconss, conss, result) ); 2635 2636 return SCIP_OKAY; 2637 } 2638 2639 /** separation method of constraint handler for arbitrary primal solutions */ 2640 static 2641 SCIP_DECL_CONSSEPASOL(consSepasolCardinality) 2642 { /*lint --e{715}*/ 2643 assert(scip != NULL); 2644 assert(conshdlr != NULL); 2645 assert(conss != NULL); 2646 assert(result != NULL); 2647 2648 SCIP_CALL( separateCardinality(scip, conshdlr, sol, nconss, conss, result) ); 2649 2650 return SCIP_OKAY; 2651 } 2652 2653 /** constraint enforcing method of constraint handler for LP solutions */ 2654 static 2655 SCIP_DECL_CONSENFOLP(consEnfolpCardinality) 2656 { /*lint --e{715}*/ 2657 assert(scip != NULL); 2658 assert(conshdlr != NULL); 2659 assert(conss != NULL); 2660 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2661 assert(result != NULL); 2662 2663 SCIP_CALL( enforceCardinality(scip, conshdlr, NULL, nconss, conss, result) ); 2664 2665 return SCIP_OKAY; 2666 } 2667 2668 /** constraint enforcing method of constraint handler for relaxation solutions */ 2669 static 2670 SCIP_DECL_CONSENFORELAX(consEnforelaxCardinality) 2671 { /*lint --e{715}*/ 2672 assert( scip != NULL ); 2673 assert( conshdlr != NULL ); 2674 assert( conss != NULL ); 2675 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 2676 assert( result != NULL ); 2677 2678 SCIP_CALL( enforceCardinality(scip, conshdlr, sol, nconss, conss, result) ); 2679 2680 return SCIP_OKAY; 2681 } 2682 2683 /** constraint enforcing method of constraint handler for pseudo solutions */ 2684 static 2685 SCIP_DECL_CONSENFOPS(consEnfopsCardinality) 2686 { /*lint --e{715}*/ 2687 assert(scip != NULL); 2688 assert(conshdlr != NULL); 2689 assert(conss != NULL); 2690 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2691 assert(result != NULL); 2692 2693 SCIP_CALL( enforceCardinality(scip, conshdlr, NULL, nconss, conss, result) ); 2694 2695 return SCIP_OKAY; 2696 } 2697 2698 /** feasibility check method of constraint handler for integral solutions 2699 * 2700 * We simply check whether more variables than allowed are nonzero in the given solution. 2701 */ 2702 static 2703 SCIP_DECL_CONSCHECK(consCheckCardinality) 2704 { /*lint --e{715}*/ 2705 int c; 2706 2707 assert(scip != NULL); 2708 assert(conshdlr != NULL); 2709 assert(conss != NULL); 2710 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2711 assert(result != NULL); 2712 2713 /* check each constraint */ 2714 for( c = 0; c < nconss; ++c ) 2715 { 2716 SCIP_CONSDATA* consdata; 2717 int cardval; 2718 int j; 2719 int cnt; 2720 2721 cnt = 0; 2722 assert(conss[c] != NULL); 2723 consdata = SCIPconsGetData(conss[c]); 2724 assert(consdata != NULL); 2725 cardval = consdata->cardval; 2726 SCIPdebugMsg(scip, "Checking cardinality constraint <%s>.\n", SCIPconsGetName(conss[c])); 2727 2728 /* check all variables */ 2729 for( j = 0; j < consdata->nvars; ++j ) 2730 { 2731 /* if variable is nonzero */ 2732 if( !SCIPisFeasZero(scip, SCIPgetSolVal(scip, sol, consdata->vars[j])) ) 2733 { 2734 ++cnt; 2735 2736 /* if more variables than allowed are nonzero */ 2737 if( cnt > cardval ) 2738 { 2739 SCIP_CALL( SCIPresetConsAge(scip, conss[c]) ); 2740 *result = SCIP_INFEASIBLE; 2741 2742 if( printreason ) 2743 { 2744 int l; 2745 2746 SCIP_CALL( SCIPprintCons(scip, conss[c], NULL) ); 2747 SCIPinfoMessage(scip, NULL, ";\nviolation: "); 2748 2749 for( l = 0; l < consdata->nvars; ++l ) 2750 { 2751 /* if variable is nonzero */ 2752 if( !SCIPisFeasZero(scip, SCIPgetSolVal(scip, sol, consdata->vars[l])) ) 2753 { 2754 SCIPinfoMessage(scip, NULL, "<%s> = %.15g ", 2755 SCIPvarGetName(consdata->vars[l]), SCIPgetSolVal(scip, sol, consdata->vars[l])); 2756 } 2757 } 2758 SCIPinfoMessage(scip, NULL, "\n"); 2759 } 2760 if( sol != NULL ) 2761 SCIPupdateSolConsViolation(scip, sol, 1.0, 1.0); 2762 return SCIP_OKAY; 2763 } 2764 } 2765 } 2766 } 2767 *result = SCIP_FEASIBLE; 2768 2769 return SCIP_OKAY; 2770 } 2771 2772 /** domain propagation method of constraint handler */ 2773 static 2774 SCIP_DECL_CONSPROP(consPropCardinality) 2775 { /*lint --e{715}*/ 2776 int nchgdomain = 0; 2777 int c; 2778 2779 assert(scip != NULL); 2780 assert(conshdlr != NULL); 2781 assert(conss != NULL); 2782 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2783 assert(result != NULL); 2784 *result = SCIP_DIDNOTRUN; 2785 2786 assert(SCIPisTransformed(scip)); 2787 2788 /* check each constraint */ 2789 for( c = 0; c < nconss; ++c ) 2790 { 2791 SCIP_CONS* cons; 2792 SCIP_CONSDATA* consdata; 2793 SCIP_Bool cutoff; 2794 2795 *result = SCIP_DIDNOTFIND; 2796 assert(conss[c] != NULL); 2797 cons = conss[c]; 2798 consdata = SCIPconsGetData(cons); 2799 assert(consdata != NULL); 2800 SCIPdebugMsg(scip, "Propagating cardinality constraint <%s>.\n", SCIPconsGetName(cons) ); 2801 2802 *result = SCIP_DIDNOTFIND; 2803 SCIP_CALL( propCardinality(scip, cons, consdata, &cutoff, &nchgdomain) ); 2804 if( cutoff ) 2805 { 2806 *result = SCIP_CUTOFF; 2807 return SCIP_OKAY; 2808 } 2809 } 2810 SCIPdebugMsg(scip, "Propagated %d domains.\n", nchgdomain); 2811 if( nchgdomain > 0 ) 2812 *result = SCIP_REDUCEDDOM; 2813 2814 return SCIP_OKAY; 2815 } 2816 2817 /** variable rounding lock method of constraint handler 2818 * 2819 * Let lb and ub be the lower and upper bounds of a 2820 * variable. Preprocessing usually makes sure that lb <= 0 <= ub. 2821 * 2822 * - If lb < 0 then rounding down may violate the constraint. 2823 * - If ub > 0 then rounding up may violated the constraint. 2824 * - If lb > 0 or ub < 0 then the rhs of the constraint can be updated and the variable 2825 * can be removed from the constraint. Thus, we do not have to deal with it here. 2826 * - If lb == 0 then rounding down does not violate the constraint. 2827 * - If ub == 0 then rounding up does not violate the constraint. 2828 */ 2829 static 2830 SCIP_DECL_CONSLOCK(consLockCardinality) 2831 { 2832 SCIP_CONSDATA* consdata; 2833 SCIP_VAR** vars; 2834 int nvars; 2835 SCIP_VAR** indvars; 2836 int j; 2837 2838 assert(scip != NULL); 2839 assert(conshdlr != NULL); 2840 assert(cons != NULL); 2841 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2842 assert(locktype == SCIP_LOCKTYPE_MODEL); 2843 2844 consdata = SCIPconsGetData(cons); 2845 assert(consdata != NULL); 2846 2847 SCIPdebugMsg(scip, "Locking constraint <%s>.\n", SCIPconsGetName(cons)); 2848 2849 vars = consdata->vars; 2850 indvars = consdata->indvars; 2851 nvars = consdata->nvars; 2852 assert(vars != NULL); 2853 2854 for( j = 0; j < nvars; ++j ) 2855 { 2856 SCIP_VAR* var; 2857 SCIP_VAR* indvar; 2858 var = vars[j]; 2859 indvar = indvars[j]; 2860 2861 /* if lower bound is negative, rounding down may violate constraint */ 2862 if( SCIPisFeasNegative(scip, SCIPvarGetLbGlobal(var)) ) 2863 { 2864 SCIP_CALL( SCIPaddVarLocksType(scip, var, locktype, nlockspos, nlocksneg) ); 2865 } 2866 2867 /* additionally: if upper bound is positive, rounding up may violate constraint */ 2868 if( SCIPisFeasPositive(scip, SCIPvarGetUbGlobal(var)) ) 2869 { 2870 SCIP_CALL( SCIPaddVarLocksType(scip, var, locktype, nlocksneg, nlockspos) ); 2871 } 2872 2873 /* add lock on indicator variable; @todo write constraint handler to handle down locks */ 2874 SCIP_CALL( SCIPaddVarLocksType(scip, indvar, locktype, nlockspos, nlockspos) ); 2875 } 2876 2877 return SCIP_OKAY; 2878 } 2879 2880 /** constraint display method of constraint handler */ 2881 static 2882 SCIP_DECL_CONSPRINT(consPrintCardinality) 2883 { /*lint --e{715}*/ 2884 SCIP_CONSDATA* consdata; 2885 int j; 2886 2887 assert(scip != NULL); 2888 assert(conshdlr != NULL); 2889 assert(cons != NULL); 2890 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 2891 2892 consdata = SCIPconsGetData(cons); 2893 assert(consdata != NULL); 2894 2895 for( j = 0; j < consdata->nvars; ++j ) 2896 { 2897 if( j > 0 ) 2898 SCIPinfoMessage(scip, file, ", "); 2899 SCIP_CALL( SCIPwriteVarName(scip, file, consdata->vars[j], FALSE) ); 2900 if( consdata->weights == NULL ) 2901 SCIPinfoMessage(scip, file, " (%d)", j+1); 2902 else 2903 SCIPinfoMessage(scip, file, " (%3.2f)", consdata->weights[j]); 2904 } 2905 SCIPinfoMessage(scip, file, " <= %d", consdata->cardval); 2906 2907 return SCIP_OKAY; 2908 } 2909 2910 /** constraint copying method of constraint handler */ 2911 static 2912 SCIP_DECL_CONSCOPY(consCopyCardinality) 2913 { /*lint --e{715}*/ 2914 SCIP_CONSDATA* sourceconsdata; 2915 SCIP_VAR** sourcevars; 2916 SCIP_VAR** targetvars; 2917 SCIP_VAR** sourceindvars; 2918 SCIP_VAR** targetindvars; 2919 SCIP_Real* sourceweights; 2920 SCIP_Real* targetweights; 2921 const char* consname; 2922 int nvars; 2923 int v; 2924 2925 assert(scip != NULL); 2926 assert(sourcescip != NULL); 2927 assert(sourcecons != NULL); 2928 assert(SCIPisTransformed(sourcescip)); 2929 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(sourcecons)), CONSHDLR_NAME) == 0); 2930 2931 *valid = TRUE; 2932 2933 if( name != NULL ) 2934 consname = name; 2935 else 2936 consname = SCIPconsGetName(sourcecons); 2937 2938 SCIPdebugMsg(scip, "Copying cardinality constraint <%s> ...\n", consname); 2939 2940 sourceconsdata = SCIPconsGetData(sourcecons); 2941 assert(sourceconsdata != NULL); 2942 2943 /* get variables and weights of the source constraint */ 2944 nvars = sourceconsdata->nvars; 2945 2946 if( nvars == 0 ) 2947 return SCIP_OKAY; 2948 2949 sourcevars = sourceconsdata->vars; 2950 assert(sourcevars != NULL); 2951 sourceindvars = sourceconsdata->indvars; 2952 assert(sourceindvars != NULL); 2953 sourceweights = sourceconsdata->weights; 2954 assert(sourceweights != NULL); 2955 2956 /* duplicate variable array */ 2957 SCIP_CALL( SCIPallocBufferArray(sourcescip, &targetvars, nvars) ); 2958 SCIP_CALL( SCIPallocBufferArray(sourcescip, &targetindvars, nvars) ); 2959 SCIP_CALL( SCIPduplicateBufferArray(sourcescip, &targetweights, sourceweights, nvars) ); 2960 2961 /* get copied variables in target SCIP */ 2962 for( v = 0; v < nvars && *valid; ++v ) 2963 { 2964 assert(sourcevars[v] != NULL); 2965 assert(sourceindvars[v] != NULL); 2966 2967 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &(targetvars[v]), varmap, consmap, global, valid) ); 2968 if( *valid ) 2969 { 2970 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourceindvars[v], &(targetindvars[v]), varmap, consmap, global, valid) ); 2971 } 2972 } 2973 2974 /* only create the target constraint, if all variables could be copied */ 2975 if( *valid ) 2976 { 2977 SCIP_CALL( SCIPcreateConsCardinality(scip, cons, consname, nvars, targetvars, sourceconsdata->cardval, targetindvars, 2978 targetweights, initial, separate, enforce, check, propagate, local, dynamic, removable, stickingatnode) ); 2979 } 2980 2981 /* free buffer array */ 2982 SCIPfreeBufferArray(sourcescip, &targetweights); 2983 SCIPfreeBufferArray(sourcescip, &targetindvars); 2984 SCIPfreeBufferArray(sourcescip, &targetvars); 2985 2986 return SCIP_OKAY; 2987 } 2988 2989 /** constraint parsing method of constraint handler */ 2990 static 2991 SCIP_DECL_CONSPARSE(consParseCardinality) 2992 { /*lint --e{715}*/ 2993 SCIP_VAR* var; 2994 SCIP_Real weight; 2995 int cardval; 2996 const char* s; 2997 char* t; 2998 2999 assert(scip != NULL); 3000 assert(conshdlr != NULL); 3001 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 3002 assert(cons != NULL); 3003 assert(success != NULL); 3004 3005 *success = TRUE; 3006 s = str; 3007 3008 /* create empty cardinality constraint */ 3009 SCIP_CALL( SCIPcreateConsCardinality(scip, cons, name, 0, NULL, 0, NULL, NULL, initial, separate, enforce, check, propagate, local, dynamic, removable, stickingatnode) ); 3010 3011 /* loop through string */ 3012 while( *s != '\0' ) 3013 { 3014 /* parse variable name */ 3015 SCIP_CALL( SCIPparseVarName(scip, s, &var, &t) ); 3016 3017 if( var == NULL ) 3018 { 3019 t = strchr(t, '<'); 3020 3021 if( t != NULL ) 3022 s = t; 3023 3024 break; 3025 } 3026 3027 /* skip until beginning of weight */ 3028 t = strchr(t, '('); 3029 3030 if( t == NULL ) 3031 { 3032 SCIPerrorMessage("Syntax error: expected opening '(' at input: %s\n", s); 3033 *success = FALSE; 3034 break; 3035 } 3036 3037 s = t; 3038 3039 /* skip '(' */ 3040 ++s; 3041 3042 /* find weight */ 3043 weight = strtod(s, &t); 3044 3045 if( t == NULL ) 3046 { 3047 SCIPerrorMessage("Syntax error during parsing of the weight: %s\n", s); 3048 *success = FALSE; 3049 break; 3050 } 3051 3052 s = t; 3053 3054 /* skip until ending of weight */ 3055 t = strchr(t, ')'); 3056 3057 if( t == NULL ) 3058 { 3059 SCIPerrorMessage("Syntax error: expected closing ')' at input %s\n", s); 3060 *success = FALSE; 3061 break; 3062 } 3063 3064 s = t; 3065 3066 /* skip ')' */ 3067 ++s; 3068 3069 /* skip white space */ 3070 SCIP_CALL( SCIPskipSpace((char**)&s) ); 3071 3072 /* skip ',' */ 3073 if( *s == ',' ) 3074 ++s; 3075 3076 /* add variable */ 3077 SCIP_CALL( SCIPaddVarCardinality(scip, *cons, var, NULL, weight) ); 3078 } 3079 3080 /* check if there is a '<=' */ 3081 if( *success && *s == '<' && *(s+1) == '=' ) 3082 { 3083 s = s + 2; 3084 3085 /* skip white space */ 3086 SCIP_CALL( SCIPskipSpace((char**)&s) ); 3087 3088 cardval = (int)strtod(s, &t); 3089 3090 if( t == NULL ) 3091 { 3092 SCIPerrorMessage("Syntax error during parsing of the cardinality restriction value: %s\n", s); 3093 *success = FALSE; 3094 } 3095 else 3096 SCIP_CALL( SCIPchgCardvalCardinality(scip, *cons, cardval) ); 3097 } 3098 3099 if( !*success ) 3100 SCIP_CALL( SCIPreleaseCons(scip, cons) ); 3101 3102 return SCIP_OKAY; 3103 } 3104 3105 /** constraint method of constraint handler which returns the variables (if possible) */ 3106 static 3107 SCIP_DECL_CONSGETVARS(consGetVarsCardinality) 3108 { /*lint --e{715}*/ 3109 SCIP_CONSDATA* consdata; 3110 3111 consdata = SCIPconsGetData(cons); 3112 assert(consdata != NULL); 3113 3114 if( varssize < consdata->nvars ) 3115 (*success) = FALSE; 3116 else 3117 { 3118 assert(vars != NULL); 3119 3120 BMScopyMemoryArray(vars, consdata->vars, consdata->nvars); 3121 (*success) = TRUE; 3122 } 3123 3124 return SCIP_OKAY; 3125 } 3126 3127 /** constraint method of constraint handler which returns the number of variables (if possible) */ 3128 static 3129 SCIP_DECL_CONSGETNVARS(consGetNVarsCardinality) 3130 { /*lint --e{715}*/ 3131 SCIP_CONSDATA* consdata; 3132 3133 consdata = SCIPconsGetData(cons); 3134 assert(consdata != NULL); 3135 3136 (*nvars) = consdata->nvars; 3137 (*success) = TRUE; 3138 3139 return SCIP_OKAY; 3140 } 3141 3142 /** constraint handler method which returns the permutation symmetry detection graph of a constraint */ 3143 static 3144 SCIP_DECL_CONSGETPERMSYMGRAPH(consGetPermsymGraphCardinality) 3145 { /*lint --e{715}*/ 3146 SCIP_CONSDATA* consdata; 3147 SCIP_VAR** vars; 3148 SCIP_Real* vals; 3149 SCIP_Real constant; 3150 SCIP_Real rhs; 3151 int consnodeidx; 3152 int pairnodeidx; 3153 int nodeidx; 3154 int nconsvars; 3155 int nlocvars; 3156 int nvars; 3157 int i; 3158 3159 consdata = SCIPconsGetData(cons); 3160 assert(consdata != NULL); 3161 assert(graph != NULL); 3162 3163 nconsvars = consdata->nvars; 3164 rhs = (SCIP_Real) consdata->cardval; 3165 3166 /* add node for constraint */ 3167 SCIP_CALL( SCIPaddSymgraphConsnode(scip, graph, cons, -SCIPinfinity(scip), rhs, &consnodeidx) ); 3168 3169 /* create nodes and edges for each variable */ 3170 nvars = SCIPgetNVars(scip); 3171 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) ); 3172 SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars) ); 3173 3174 for( i = 0; i < nconsvars; ++i ) 3175 { 3176 /* connect each variable and its indicator variable with an intermediate node, which is connected with consnode */ 3177 SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, (int) SYM_CONSOPTYPE_CARD_TUPLE , &pairnodeidx) ); 3178 3179 /* connect variable with pair node*/ 3180 vars[0] = consdata->vars[i]; 3181 vals[0] = 1.0; 3182 nlocvars = 1; 3183 constant = 0.0; 3184 3185 SCIP_CALL( SCIPgetActiveVariables(scip, SYM_SYMTYPE_PERM, &vars, &vals, 3186 &nlocvars, &constant, SCIPisTransformed(scip)) ); 3187 3188 /* check whether variable is (multi-)aggregated or negated */ 3189 if( nlocvars > 1 || !SCIPisEQ(scip, vals[0], 1.0) || !SCIPisZero(scip, constant) ) 3190 { 3191 /* encode aggregation by a sum-expression */ 3192 SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, (int) SYM_CONSOPTYPE_SUM, &nodeidx) ); /*lint !e641*/ 3193 3194 /* we do not need to take weights of variables into account; 3195 * they are only used to sort variables within the constraint */ 3196 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, pairnodeidx, nodeidx, FALSE, 0.0) ); 3197 3198 /* add nodes and edges for variables in aggregation */ 3199 SCIP_CALL( SCIPaddSymgraphVarAggegration(scip, graph, nodeidx, vars, vals, nlocvars, constant) ); 3200 } 3201 else if( nlocvars == 1 ) 3202 { 3203 nodeidx = SCIPgetSymgraphVarnodeidx(scip, graph, vars[0]); 3204 3205 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, pairnodeidx, nodeidx, FALSE, 0.0) ); 3206 } 3207 3208 /* connect indicator variable with pair node*/ 3209 vars[0] = consdata->indvars[i]; 3210 vals[0] = 1.0; 3211 nlocvars = 1; 3212 constant = 0.0; 3213 3214 SCIP_CALL( SCIPgetActiveVariables(scip, SYM_SYMTYPE_PERM, &vars, &vals, 3215 &nlocvars, &constant, SCIPisTransformed(scip)) ); 3216 3217 /* check whether variable is (multi-)aggregated or negated */ 3218 if( nlocvars > 1 || !SCIPisEQ(scip, vals[0], 1.0) || !SCIPisZero(scip, constant) ) 3219 { 3220 /* encode aggregation by a sum-expression */ 3221 SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, (int) SYM_CONSOPTYPE_SUM, &nodeidx) ); /*lint !e641*/ 3222 3223 /* we do not need to take weights of variables into account; 3224 * they are only used to sort variables within the constraint */ 3225 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, pairnodeidx, nodeidx, FALSE, 0.0) ); 3226 3227 /* add nodes and edges for variables in aggregation */ 3228 SCIP_CALL( SCIPaddSymgraphVarAggegration(scip, graph, nodeidx, vars, vals, nlocvars, constant) ); 3229 } 3230 else if( nlocvars == 1 ) 3231 { 3232 nodeidx = SCIPgetSymgraphVarnodeidx(scip, graph, vars[0]); 3233 3234 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, pairnodeidx, nodeidx, FALSE, 0.0) ); 3235 } 3236 } 3237 3238 SCIPfreeBufferArray(scip, &vals); 3239 SCIPfreeBufferArray(scip, &vars); 3240 3241 return SCIP_OKAY; 3242 } 3243 3244 /** constraint handler method which returns the signed permutation symmetry detection graph of a constraint */ 3245 static 3246 SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(consGetSignedPermsymGraphCardinality) 3247 { /*lint --e{715}*/ 3248 SCIP_CONSDATA* consdata; 3249 SCIP_VAR** vars; 3250 SCIP_Real* vals; 3251 SCIP_Real constant; 3252 SCIP_Real rhs; 3253 int consnodeidx; 3254 int pairnodeidx; 3255 int nodeidx; 3256 int nconsvars; 3257 int nlocvars; 3258 int nvars; 3259 int i; 3260 3261 consdata = SCIPconsGetData(cons); 3262 assert(consdata != NULL); 3263 assert(graph != NULL); 3264 3265 nconsvars = consdata->nvars; 3266 rhs = (SCIP_Real) consdata->cardval; 3267 3268 /* add node for constraint */ 3269 SCIP_CALL( SCIPaddSymgraphConsnode(scip, graph, cons, -SCIPinfinity(scip), rhs, &consnodeidx) ); 3270 3271 /* create nodes and edges for each variable */ 3272 nvars = SCIPgetNVars(scip); 3273 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) ); 3274 SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars) ); 3275 3276 for( i = 0; i < nconsvars; ++i ) 3277 { 3278 /* connect each variable and its indicator variable with an intermediate node, which is connected with consnode */ 3279 SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, (int) SYM_CONSOPTYPE_CARD_TUPLE , &pairnodeidx) ); 3280 3281 vars[0] = consdata->vars[i]; 3282 vals[0] = 1.0; 3283 nlocvars = 1; 3284 constant = 0.0; 3285 3286 /* use SYM_SYMTYPE_PERM here to NOT center variable domains at 0, as the latter might not preserve 3287 * cardinality constraints */ 3288 SCIP_CALL( SCIPgetActiveVariables(scip, SYM_SYMTYPE_PERM, &vars, &vals, 3289 &nlocvars, &constant, SCIPisTransformed(scip)) ); 3290 3291 /* check whether variable is (multi-) aggregated or negated */ 3292 if( nlocvars > 1 || !SCIPisEQ(scip, vals[0], 1.0) || !SCIPisZero(scip, constant) ) 3293 { 3294 int sumnodeidx; 3295 int j; 3296 3297 /* encode aggregation by a sum-expression */ 3298 SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, (int) SYM_CONSOPTYPE_SUM, &sumnodeidx) ); /*lint !e641*/ 3299 3300 /* we do not need to take weights of variables into account; 3301 * they are only used to sort variables within the constraint */ 3302 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, pairnodeidx, sumnodeidx, FALSE, 0.0) ); 3303 3304 /* add nodes and edges for variables in aggregation, do not add edges to negated variables 3305 * since this might not necessarily be a symmetry of the cardinality constraint; therefore, 3306 * do not use SCIPaddSymgraphVarAggegration() */ 3307 for( j = 0; j < nlocvars; ++j ) 3308 { 3309 nodeidx = SCIPgetSymgraphVarnodeidx(scip, graph, vars[j]); 3310 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, sumnodeidx, nodeidx, TRUE, vals[j]) ); 3311 } 3312 3313 /* possibly add node for constant */ 3314 if( ! SCIPisZero(scip, constant) ) 3315 { 3316 SCIP_CALL( SCIPaddSymgraphValnode(scip, graph, constant, &nodeidx) ); 3317 3318 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, sumnodeidx, nodeidx, FALSE, 0.0) ); 3319 } 3320 } 3321 else if( nlocvars == 1 ) 3322 { 3323 SCIP_Bool allownegation = FALSE; 3324 3325 /* a negation is allowed if it is centered around 0 */ 3326 if ( SCIPisInfinity(scip, -SCIPvarGetLbGlobal(vars[0])) == SCIPisInfinity(scip, SCIPvarGetUbGlobal(vars[0])) 3327 && (SCIPisInfinity(scip, SCIPvarGetUbGlobal(vars[0])) 3328 || SCIPisZero(scip, (SCIPvarGetLbGlobal(vars[0]) + SCIPvarGetUbGlobal(vars[0]))/2)) ) 3329 allownegation = TRUE; 3330 3331 nodeidx = SCIPgetSymgraphVarnodeidx(scip, graph, vars[0]); 3332 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, pairnodeidx, nodeidx, TRUE, 1.0) ); 3333 3334 nodeidx = SCIPgetSymgraphNegatedVarnodeidx(scip, graph, vars[0]); 3335 if( allownegation ) 3336 { 3337 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, pairnodeidx, nodeidx, TRUE, 1.0) ); 3338 } 3339 else 3340 { 3341 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, pairnodeidx, nodeidx, FALSE, 0.0) ); 3342 } 3343 } 3344 3345 /* connect indicator variable with pair node, do not add edges to negated variables since negating 3346 * might not preserve the cardinality requirement 3347 */ 3348 vars[0] = consdata->indvars[i]; 3349 vals[0] = 1.0; 3350 nlocvars = 1; 3351 constant = 0.0; 3352 3353 SCIP_CALL( SCIPgetActiveVariables(scip, SYM_SYMTYPE_PERM, &vars, &vals, 3354 &nlocvars, &constant, SCIPisTransformed(scip)) ); 3355 3356 /* check whether variable is (multi-)aggregated or negated */ 3357 if( nlocvars > 1 || !SCIPisEQ(scip, vals[0], 1.0) || !SCIPisZero(scip, constant) ) 3358 { 3359 /* encode aggregation by a sum-expression */ 3360 SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, (int) SYM_CONSOPTYPE_SUM, &nodeidx) ); /*lint !e641*/ 3361 3362 /* we do not need to take weights of variables into account; 3363 * they are only used to sort variables within the constraint */ 3364 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, pairnodeidx, nodeidx, FALSE, 0.0) ); 3365 3366 /* add nodes and edges for variables in aggregation */ 3367 SCIP_CALL( SCIPaddSymgraphVarAggegration(scip, graph, nodeidx, vars, vals, nlocvars, constant) ); 3368 } 3369 else if( nlocvars == 1 ) 3370 { 3371 nodeidx = SCIPgetSymgraphVarnodeidx(scip, graph, vars[0]); 3372 3373 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, pairnodeidx, nodeidx, FALSE, 0.0) ); 3374 } 3375 } 3376 3377 SCIPfreeBufferArray(scip, &vals); 3378 SCIPfreeBufferArray(scip, &vars); 3379 3380 return SCIP_OKAY; 3381 } 3382 3383 /* ---------------- Callback methods of event handler ---------------- */ 3384 3385 /* exec the event handler 3386 * 3387 * update the number of variables fixed to be nonzero 3388 * update the bound constraints 3389 */ 3390 static 3391 SCIP_DECL_EVENTEXEC(eventExecCardinality) 3392 { 3393 SCIP_EVENTTYPE eventtype; 3394 SCIP_CONSDATA* consdata; 3395 SCIP_Real oldbound; 3396 SCIP_Real newbound; 3397 SCIP_VAR* var; 3398 3399 assert(eventhdlr != NULL); 3400 assert(eventdata != NULL); 3401 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0); 3402 assert(event != NULL); 3403 3404 consdata = eventdata->consdata; 3405 assert(consdata != NULL); 3406 assert(0 <= consdata->ntreatnonzeros && consdata->ntreatnonzeros <= consdata->nvars); 3407 assert(consdata->eventdatascurrent != NULL); 3408 assert(consdata->eventvarscurrent != NULL); 3409 3410 var = SCIPeventGetVar(event); 3411 assert(var != NULL); 3412 oldbound = SCIPeventGetOldbound(event); 3413 newbound = SCIPeventGetNewbound(event); 3414 eventtype = SCIPeventGetType(event); 3415 3416 #ifdef SCIP_DEBUG 3417 if( ( eventdata->varmarked && var == eventdata->var) || ( eventdata->indvarmarked && var == eventdata->indvar) ) 3418 { 3419 int i; 3420 3421 for( i = 0; i < consdata->neventdatascurrent; ++i ) 3422 { 3423 if( var == consdata->eventvarscurrent[i] ) 3424 { 3425 break; 3426 } 3427 } 3428 assert(i < consdata->neventdatascurrent); 3429 } 3430 #endif 3431 3432 if( eventtype & SCIP_EVENTTYPE_GBDCHANGED ) 3433 { 3434 if( eventtype == SCIP_EVENTTYPE_GLBCHANGED ) 3435 { 3436 /* global lower bound is not negative anymore -> remove down lock */ 3437 if ( SCIPisFeasNegative(scip, oldbound) && ! SCIPisFeasNegative(scip, newbound) ) 3438 SCIP_CALL( SCIPunlockVarCons(scip, var, consdata->cons, TRUE, FALSE) ); 3439 /* global lower bound turned negative -> add down lock */ 3440 else if ( ! SCIPisFeasNegative(scip, oldbound) && SCIPisFeasNegative(scip, newbound) ) 3441 SCIP_CALL( SCIPlockVarCons(scip, var, consdata->cons, TRUE, FALSE) ); 3442 3443 return SCIP_OKAY; 3444 } 3445 if( eventtype == SCIP_EVENTTYPE_GUBCHANGED ) 3446 { 3447 /* global upper bound is not positive anymore -> remove up lock */ 3448 if ( SCIPisFeasPositive(scip, oldbound) && ! SCIPisFeasPositive(scip, newbound) ) 3449 SCIP_CALL( SCIPunlockVarCons(scip, var, consdata->cons, FALSE, TRUE) ); 3450 /* global upper bound turned positive -> add up lock */ 3451 else if ( ! SCIPisFeasPositive(scip, oldbound) && SCIPisFeasPositive(scip, newbound) ) 3452 SCIP_CALL( SCIPlockVarCons(scip, var, consdata->cons, FALSE, TRUE) ); 3453 3454 return SCIP_OKAY; 3455 } 3456 } 3457 3458 /* if variable is an indicator variable */ 3459 if( var == eventdata->indvar ) 3460 { 3461 assert(SCIPvarIsBinary(var)); 3462 assert(consdata->cons != NULL); 3463 3464 if( eventtype == SCIP_EVENTTYPE_LBTIGHTENED ) 3465 ++(consdata->ntreatnonzeros); 3466 else if( eventtype == SCIP_EVENTTYPE_LBRELAXED ) 3467 --(consdata->ntreatnonzeros); 3468 else if( eventtype == SCIP_EVENTTYPE_UBTIGHTENED && ! eventdata->indvarmarked ) 3469 { 3470 assert(oldbound == 1.0 && newbound == 0.0 ); 3471 3472 /* save event data for propagation */ 3473 consdata->eventdatascurrent[consdata->neventdatascurrent] = eventdata; 3474 consdata->eventvarscurrent[consdata->neventdatascurrent] = var; 3475 ++consdata->neventdatascurrent; 3476 eventdata->indvarmarked = TRUE; 3477 assert(consdata->neventdatascurrent <= 4 * consdata->maxvars); 3478 assert(var == eventdata->indvar ); 3479 } 3480 assert(0 <= consdata->ntreatnonzeros && consdata->ntreatnonzeros <= consdata->nvars); 3481 } 3482 3483 /* if variable is an implied variable, 3484 * notice that the case consdata->var = consdata->indvar is possible */ 3485 if( var == eventdata->var && ! eventdata->varmarked ) 3486 { 3487 if( eventtype == SCIP_EVENTTYPE_LBTIGHTENED ) 3488 { 3489 /* if variable is now fixed to be nonzero */ 3490 if( !SCIPisFeasPositive(scip, oldbound) && SCIPisFeasPositive(scip, newbound) ) 3491 { 3492 /* save event data for propagation */ 3493 consdata->eventdatascurrent[consdata->neventdatascurrent] = eventdata; 3494 consdata->eventvarscurrent[consdata->neventdatascurrent] = var; 3495 ++consdata->neventdatascurrent; 3496 eventdata->varmarked = TRUE; 3497 assert(consdata->neventdatascurrent <= 4 * consdata->maxvars ); 3498 assert(var == eventdata->var ); 3499 } 3500 } 3501 else if( eventtype == SCIP_EVENTTYPE_UBTIGHTENED ) 3502 { 3503 /* if variable is now fixed to be nonzero */ 3504 if( !SCIPisFeasNegative(scip, oldbound) && SCIPisFeasNegative(scip, newbound) ) 3505 { 3506 /* save event data for propagation */ 3507 consdata->eventdatascurrent[consdata->neventdatascurrent] = eventdata; 3508 consdata->eventvarscurrent[consdata->neventdatascurrent] = var; 3509 ++consdata->neventdatascurrent; 3510 eventdata->varmarked = TRUE; 3511 assert(consdata->neventdatascurrent <= 4 * consdata->maxvars ); 3512 assert(var == eventdata->var); 3513 } 3514 } 3515 } 3516 assert(0 <= consdata->ntreatnonzeros && consdata->ntreatnonzeros <= consdata->nvars); 3517 3518 SCIPdebugMsg(scip, "event exec cons <%s>: changed bound of variable <%s> from %f to %f (ntreatnonzeros: %d).\n", 3519 SCIPconsGetName(consdata->cons), SCIPvarGetName(SCIPeventGetVar(event)), 3520 oldbound, newbound, consdata->ntreatnonzeros); 3521 3522 return SCIP_OKAY; 3523 } 3524 3525 /* ---------------- Constraint specific interface methods ---------------- */ 3526 3527 /** creates the handler for cardinality constraints and includes it in SCIP */ 3528 SCIP_RETCODE SCIPincludeConshdlrCardinality( 3529 SCIP* scip /**< SCIP data structure */ 3530 ) 3531 { 3532 SCIP_CONSHDLRDATA* conshdlrdata; 3533 SCIP_CONSHDLR* conshdlr; 3534 3535 /* create constraint handler data */ 3536 SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) ); 3537 conshdlrdata->eventhdlr = NULL; 3538 conshdlrdata->varhash = NULL; 3539 3540 /* create event handler for bound change events */ 3541 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &conshdlrdata->eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, 3542 eventExecCardinality, NULL) ); 3543 if( conshdlrdata->eventhdlr == NULL ) 3544 { 3545 SCIPerrorMessage("event handler for cardinality constraints not found.\n"); 3546 return SCIP_PLUGINNOTFOUND; 3547 } 3548 3549 /* include constraint handler */ 3550 SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC, 3551 CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY, CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS, 3552 consEnfolpCardinality, consEnfopsCardinality, consCheckCardinality, consLockCardinality, conshdlrdata) ); 3553 assert(conshdlr != NULL); 3554 3555 /* set non-fundamental callbacks via specific setter functions */ 3556 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyCardinality, consCopyCardinality) ); 3557 SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteCardinality) ); 3558 SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolCardinality) ); 3559 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeCardinality) ); 3560 SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsCardinality) ); 3561 SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsCardinality) ); 3562 SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpCardinality) ); 3563 SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseCardinality) ); 3564 SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolCardinality, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) ); 3565 SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintCardinality) ); 3566 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropCardinality, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP, 3567 CONSHDLR_PROP_TIMING) ); 3568 /*SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropCardinality) ); @todo: implement repropagation */ 3569 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpCardinality, consSepasolCardinality, CONSHDLR_SEPAFREQ, 3570 CONSHDLR_SEPAPRIORITY, CONSHDLR_DELAYSEPA) ); 3571 SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransCardinality) ); 3572 SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxCardinality) ); 3573 SCIP_CALL( SCIPsetConshdlrGetPermsymGraph(scip, conshdlr, consGetPermsymGraphCardinality) ); 3574 SCIP_CALL( SCIPsetConshdlrGetSignedPermsymGraph(scip, conshdlr, consGetSignedPermsymGraphCardinality) ); 3575 3576 /* add cardinality constraint handler parameters */ 3577 SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/branchbalanced", 3578 "whether to use balanced instead of unbalanced branching", 3579 &conshdlrdata->branchbalanced, TRUE, DEFAULT_BRANCHBALANCED, NULL, NULL) ); 3580 3581 SCIP_CALL( SCIPaddIntParam(scip, "constraints/" CONSHDLR_NAME "/balanceddepth", 3582 "maximum depth for using balanced branching (-1: no limit)", 3583 &conshdlrdata->balanceddepth, TRUE, DEFAULT_BALANCEDDEPTH, -1, INT_MAX, NULL, NULL) ); 3584 3585 SCIP_CALL( SCIPaddRealParam(scip, "constraints/" CONSHDLR_NAME "/balancedcutoff", 3586 "determines that balanced branching is only used if the branching cut off value " 3587 "w.r.t. the current LP solution is greater than a given value", 3588 &conshdlrdata->balancedcutoff, TRUE, DEFAULT_BALANCEDCUTOFF, 0.01, SCIP_REAL_MAX, NULL, NULL) ); 3589 3590 return SCIP_OKAY; 3591 } 3592 3593 /** creates and captures a cardinality constraint 3594 * 3595 * We set the constraint to not be modifable. If the weights are non 3596 * NULL, the variables are ordered according to these weights (in 3597 * ascending order). 3598 * 3599 * @note the constraint gets captured, hence at one point you have to release it using the method \ref SCIPreleaseCons() 3600 */ 3601 SCIP_RETCODE SCIPcreateConsCardinality( 3602 SCIP* scip, /**< SCIP data structure */ 3603 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 3604 const char* name, /**< name of constraint */ 3605 int nvars, /**< number of variables in the constraint */ 3606 SCIP_VAR** vars, /**< array with variables of constraint entries */ 3607 int cardval, /**< number of variables allowed to be nonzero */ 3608 SCIP_VAR** indvars, /**< indicator variables indicating which variables may be treated as nonzero 3609 * in cardinality constraint, or NULL if new indicator variables should be 3610 * introduced automatically */ 3611 SCIP_Real* weights, /**< weights determining the variable order, or NULL if variables should be 3612 * ordered in the same way they were added to the constraint */ 3613 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? 3614 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */ 3615 SCIP_Bool separate, /**< should the constraint be separated during LP processing? 3616 * Usually set to TRUE. */ 3617 SCIP_Bool enforce, /**< should the constraint be enforced during node processing? 3618 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 3619 SCIP_Bool check, /**< should the constraint be checked for feasibility? 3620 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 3621 SCIP_Bool propagate, /**< should the constraint be propagated during node processing? 3622 * Usually set to TRUE. */ 3623 SCIP_Bool local, /**< is constraint only valid locally? 3624 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */ 3625 SCIP_Bool dynamic, /**< is constraint subject to aging? 3626 * Usually set to FALSE. Set to TRUE for own cuts which 3627 * are separated as constraints. */ 3628 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? 3629 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */ 3630 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even 3631 * if it may be moved to a more global node? 3632 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */ 3633 ) 3634 { 3635 SCIP_CONSHDLRDATA* conshdlrdata; 3636 SCIP_CONSHDLR* conshdlr; 3637 SCIP_CONSDATA* consdata; 3638 SCIP_Bool modifiable; 3639 SCIP_Bool transformed; 3640 int v; 3641 3642 modifiable = FALSE; 3643 3644 /* find the cardinality constraint handler */ 3645 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME); 3646 if( conshdlr == NULL ) 3647 { 3648 SCIPerrorMessage("<%s> constraint handler not found\n", CONSHDLR_NAME); 3649 return SCIP_PLUGINNOTFOUND; 3650 } 3651 3652 /* get constraint handler data */ 3653 conshdlrdata = SCIPconshdlrGetData(conshdlr); 3654 assert(conshdlrdata != NULL); 3655 3656 /* are we in the transformed problem? */ 3657 transformed = SCIPgetStage(scip) >= SCIP_STAGE_TRANSFORMED; 3658 3659 /* create constraint data */ 3660 SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) ); 3661 consdata->cons = NULL; 3662 consdata->vars = NULL; 3663 consdata->indvars = NULL; 3664 consdata->eventdatas = NULL; 3665 consdata->nvars = nvars; 3666 consdata->cardval = cardval; 3667 consdata->maxvars = nvars; 3668 consdata->rowub = NULL; 3669 consdata->rowlb = NULL; 3670 consdata->eventdatascurrent = NULL; 3671 consdata->eventvarscurrent = NULL; 3672 consdata->neventdatascurrent = 0; 3673 consdata->ntreatnonzeros = transformed ? 0 : -1; 3674 consdata->weights = NULL; 3675 3676 if( nvars > 0 ) 3677 { 3678 /* duplicate memory for implied variables */ 3679 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->vars, vars, nvars) ); 3680 3681 /* create indicator variables if not present */ 3682 if( indvars != NULL ) 3683 { 3684 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->indvars, indvars, nvars) ); 3685 } 3686 else 3687 { 3688 if( conshdlrdata->varhash == NULL ) 3689 { 3690 /* set up hash map */ 3691 SCIP_CALL( SCIPhashmapCreate(&conshdlrdata->varhash, SCIPblkmem(scip), SCIPgetNTotalVars(scip)) ); 3692 } 3693 3694 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->indvars, nvars) ); 3695 for( v = 0; v < nvars; ++v ) 3696 { 3697 SCIP_VAR* implvar; 3698 3699 implvar = vars[v]; 3700 assert(implvar != NULL); 3701 3702 /* check whether an indicator variable already exists for implied variable */ 3703 if( SCIPhashmapExists(conshdlrdata->varhash, implvar) ) 3704 { 3705 assert((SCIP_VAR*) SCIPhashmapGetImage(conshdlrdata->varhash, implvar) != NULL); 3706 consdata->indvars[v] = (SCIP_VAR*) SCIPhashmapGetImage(conshdlrdata->varhash, implvar); 3707 } 3708 else 3709 { 3710 /* if implied variable is binary, then it is not necessary to create an indicator variable */ 3711 if( SCIPvarIsBinary(implvar) ) 3712 consdata->indvars[v] = implvar; 3713 else 3714 { 3715 char varname[SCIP_MAXSTRLEN]; 3716 SCIP_VAR* var; 3717 3718 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "ind_%s", SCIPvarGetName(vars[v])); 3719 SCIP_CALL( SCIPcreateVar(scip, &var, varname, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY, FALSE, FALSE, 3720 NULL, NULL, NULL, NULL, NULL) ); 3721 SCIP_CALL( SCIPaddVar(scip, var) ); 3722 consdata->indvars[v] = var; 3723 SCIP_CALL( SCIPreleaseVar(scip, &var) ); 3724 } 3725 3726 /* insert implied variable to hash map */ 3727 SCIP_CALL( SCIPhashmapInsert(conshdlrdata->varhash, implvar, (void*) consdata->indvars[v]) );/*lint !e571*/ 3728 assert(consdata->indvars[v] == (SCIP_VAR*) SCIPhashmapGetImage(conshdlrdata->varhash, implvar)); 3729 assert(SCIPhashmapExists(conshdlrdata->varhash, implvar)); 3730 } 3731 } 3732 } 3733 3734 /* allocate block memory */ 3735 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->eventdatascurrent, 4*nvars) );/*lint !e647*/ 3736 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->eventvarscurrent, 4*nvars) );/*lint !e647*/ 3737 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->eventdatas, nvars) ); 3738 3739 /* check weights */ 3740 if( weights != NULL ) 3741 { 3742 int* dummy; 3743 3744 /* store weights */ 3745 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->weights, weights, nvars) ); 3746 3747 /* create dummy array to make code compatible with SCIP 3.2.0 3748 * (the function SCIPsortRealPtrPtr() is not available) */ 3749 SCIP_CALL( SCIPallocBufferArray(scip, &dummy, nvars) ); 3750 for( v = 0; v < nvars; ++v ) 3751 dummy[v] = 0; 3752 3753 /* sort variables - ascending order */ 3754 SCIPsortRealPtrPtrInt(consdata->weights, (void**)consdata->vars, (void**)consdata->indvars, dummy, nvars); 3755 3756 SCIPfreeBufferArray(scip, &dummy); 3757 } 3758 } 3759 else 3760 { 3761 assert(weights == NULL); 3762 } 3763 3764 /* create cardinality constraint */ 3765 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate, 3766 local, modifiable, dynamic, removable, stickingatnode) ); 3767 3768 consdata->cons = *cons; 3769 assert(consdata->cons != NULL); 3770 3771 /* replace original variables by transformed variables in transformed constraint, add locks, and catch events */ 3772 for( v = nvars - 1; v >= 0; --v ) 3773 { 3774 /* always use transformed variables in transformed constraints */ 3775 if( transformed ) 3776 { 3777 SCIP_CALL( SCIPgetTransformedVar(scip, consdata->vars[v], &(consdata->vars[v])) ); 3778 SCIP_CALL( SCIPgetTransformedVar(scip, consdata->indvars[v], &(consdata->indvars[v])) ); 3779 } 3780 assert(consdata->vars[v] != NULL); 3781 assert(consdata->indvars[v] != NULL); 3782 assert(transformed == SCIPvarIsTransformed(consdata->vars[v])); 3783 assert(transformed == SCIPvarIsTransformed(consdata->indvars[v])); 3784 3785 /* handle the new variable */ 3786 SCIP_CALL( handleNewVariableCardinality(scip, *cons, consdata, conshdlrdata, consdata->vars[v], 3787 consdata->indvars[v], v, transformed, &consdata->eventdatas[v]) ); 3788 assert(! transformed || consdata->eventdatas[v] != NULL); 3789 } 3790 3791 return SCIP_OKAY; 3792 } 3793 3794 /** creates and captures a cardinality constraint with all constraint flags set to their default values. 3795 * 3796 * @warning Do NOT set the constraint to be modifiable manually, because this might lead 3797 * to wrong results as the variable array will not be resorted 3798 * 3799 * @note the constraint gets captured, hence at one point you have to release it using the method \ref SCIPreleaseCons() 3800 */ 3801 SCIP_RETCODE SCIPcreateConsBasicCardinality( 3802 SCIP* scip, /**< SCIP data structure */ 3803 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 3804 const char* name, /**< name of constraint */ 3805 int nvars, /**< number of variables in the constraint */ 3806 SCIP_VAR** vars, /**< array with variables of constraint entries */ 3807 int cardval, /**< number of variables allowed to be nonzero */ 3808 SCIP_VAR** indvars, /**< indicator variables indicating which variables may be treated as nonzero 3809 * in cardinality constraint, or NULL if new indicator variables should be 3810 * introduced automatically */ 3811 SCIP_Real* weights /**< weights determining the variable order, or NULL if variables should be 3812 * ordered in the same way they were added to the constraint */ 3813 ) 3814 { 3815 SCIP_CALL( SCIPcreateConsCardinality(scip, cons, name, nvars, vars, cardval, indvars, weights, TRUE, TRUE, TRUE, TRUE, 3816 TRUE, FALSE, FALSE, FALSE, FALSE) ); 3817 3818 return SCIP_OKAY; 3819 } 3820 3821 /** changes cardinality value of cardinality constraint (i.e., right hand side of cardinality constraint) */ 3822 SCIP_RETCODE SCIPchgCardvalCardinality( 3823 SCIP* scip, /**< SCIP data structure */ 3824 SCIP_CONS* cons, /**< pointer to hold the created constraint */ 3825 int cardval /**< number of variables allowed to be nonzero */ 3826 ) 3827 { 3828 SCIP_CONSDATA* consdata; 3829 3830 assert(scip != NULL); 3831 assert(cons != NULL); 3832 3833 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 ) 3834 { 3835 SCIPerrorMessage("constraint is not a cardinality constraint.\n"); 3836 return SCIP_INVALIDDATA; 3837 } 3838 3839 consdata = SCIPconsGetData(cons); 3840 assert(consdata != NULL); 3841 3842 SCIPdebugMsg(scip, "modify right hand side of cardinality constraint from <%i> to <%i>\n", consdata->cardval, cardval); 3843 3844 /* create constraint data */ 3845 consdata->cardval = cardval; 3846 3847 return SCIP_OKAY; 3848 } 3849 3850 /** adds variable to cardinality constraint, the position is determined by the given weight */ 3851 SCIP_RETCODE SCIPaddVarCardinality( 3852 SCIP* scip, /**< SCIP data structure */ 3853 SCIP_CONS* cons, /**< constraint */ 3854 SCIP_VAR* var, /**< variable to add to the constraint */ 3855 SCIP_VAR* indvar, /**< indicator variable indicating whether variable may be treated as nonzero 3856 * in cardinality constraint (or NULL if this variable should be created 3857 * automatically) */ 3858 SCIP_Real weight /**< weight determining position of variable */ 3859 ) 3860 { 3861 SCIP_CONSHDLRDATA* conshdlrdata; 3862 SCIP_CONSHDLR* conshdlr; 3863 3864 assert(scip != NULL); 3865 assert(var != NULL); 3866 assert(cons != NULL); 3867 3868 SCIPdebugMsg(scip, "adding variable <%s> to constraint <%s> with weight %g\n", SCIPvarGetName(var), 3869 SCIPconsGetName(cons), weight); 3870 3871 conshdlr = SCIPconsGetHdlr(cons); 3872 assert(conshdlr != NULL); 3873 if( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) != 0 ) 3874 { 3875 SCIPerrorMessage("constraint is not a cardinality constraint.\n"); 3876 return SCIP_INVALIDDATA; 3877 } 3878 3879 conshdlrdata = SCIPconshdlrGetData(conshdlr); 3880 assert(conshdlrdata != NULL); 3881 3882 SCIP_CALL( addVarCardinality(scip, cons, conshdlrdata, var, indvar, weight) ); 3883 3884 return SCIP_OKAY; 3885 } 3886 3887 /** appends variable to cardinality constraint */ 3888 SCIP_RETCODE SCIPappendVarCardinality( 3889 SCIP* scip, /**< SCIP data structure */ 3890 SCIP_CONS* cons, /**< constraint */ 3891 SCIP_VAR* var, /**< variable to add to the constraint */ 3892 SCIP_VAR* indvar /**< indicator variable indicating whether variable may be treated as nonzero 3893 * in cardinality constraint (or NULL if this variable should be created 3894 * automatically) */ 3895 ) 3896 { 3897 SCIP_CONSHDLRDATA* conshdlrdata; 3898 SCIP_CONSHDLR* conshdlr; 3899 3900 assert(scip != NULL); 3901 assert(var != NULL); 3902 assert(cons != NULL); 3903 3904 SCIPdebugMsg(scip, "appending variable <%s> to constraint <%s>\n", SCIPvarGetName(var), SCIPconsGetName(cons)); 3905 3906 conshdlr = SCIPconsGetHdlr(cons); 3907 assert(conshdlr != NULL); 3908 if( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) != 0 ) 3909 { 3910 SCIPerrorMessage("constraint is not a cardinality constraint.\n"); 3911 return SCIP_INVALIDDATA; 3912 } 3913 3914 conshdlrdata = SCIPconshdlrGetData(conshdlr); 3915 assert(conshdlrdata != NULL); 3916 3917 SCIP_CALL( appendVarCardinality(scip, cons, conshdlrdata, var, indvar) ); 3918 3919 return SCIP_OKAY; 3920 } 3921 3922 /** gets number of variables in cardinality constraint */ 3923 int SCIPgetNVarsCardinality( 3924 SCIP* scip, /**< SCIP data structure */ 3925 SCIP_CONS* cons /**< constraint */ 3926 ) 3927 { 3928 SCIP_CONSDATA* consdata; 3929 3930 assert(scip != NULL); 3931 assert(cons != NULL); 3932 3933 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 ) 3934 { 3935 SCIPerrorMessage("constraint is not a cardinality constraint.\n"); 3936 SCIPABORT(); 3937 return -1; /*lint !e527*/ 3938 } 3939 3940 consdata = SCIPconsGetData(cons); 3941 assert(consdata != NULL); 3942 3943 return consdata->nvars; 3944 } 3945 3946 /** gets array of variables in cardinality constraint */ 3947 SCIP_VAR** SCIPgetVarsCardinality( 3948 SCIP* scip, /**< SCIP data structure */ 3949 SCIP_CONS* cons /**< constraint data */ 3950 ) 3951 { 3952 SCIP_CONSDATA* consdata; 3953 3954 assert(scip != NULL); 3955 assert(cons != NULL); 3956 3957 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 ) 3958 { 3959 SCIPerrorMessage("constraint is not a cardinality constraint.\n"); 3960 SCIPABORT(); 3961 return NULL; /*lint !e527*/ 3962 } 3963 3964 consdata = SCIPconsGetData(cons); 3965 assert(consdata != NULL); 3966 3967 return consdata->vars; 3968 } 3969 3970 /** gets cardinality value of cardinality constraint (i.e., right hand side of cardinality constraint) */ 3971 int SCIPgetCardvalCardinality( 3972 SCIP* scip, /**< SCIP data structure */ 3973 SCIP_CONS* cons /**< constraint data */ 3974 ) 3975 { 3976 SCIP_CONSDATA* consdata; 3977 3978 assert(scip != NULL); 3979 assert(cons != NULL); 3980 3981 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 ) 3982 { 3983 SCIPerrorMessage("constraint is not a cardinality constraint.\n"); 3984 return -1; /*lint !e527*/ 3985 } 3986 3987 consdata = SCIPconsGetData(cons); 3988 assert(consdata != NULL); 3989 3990 return consdata->cardval; 3991 } 3992 3993 /** gets array of weights in cardinality constraint (or NULL if not existent) */ 3994 SCIP_Real* SCIPgetWeightsCardinality( 3995 SCIP* scip, /**< SCIP data structure */ 3996 SCIP_CONS* cons /**< constraint data */ 3997 ) 3998 { 3999 SCIP_CONSDATA* consdata; 4000 4001 assert(scip != NULL); 4002 assert(cons != NULL); 4003 4004 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 ) 4005 { 4006 SCIPerrorMessage("constraint is not a cardinality constraint.\n"); 4007 SCIPABORT(); 4008 return NULL; /*lint !e527*/ 4009 } 4010 4011 consdata = SCIPconsGetData(cons); 4012 assert(consdata != NULL); 4013 4014 return consdata->weights; 4015 } 4016