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_sos2.c 26 * @ingroup DEFPLUGINS_CONS 27 * @brief constraint handler for SOS type 2 constraints 28 * @author Marc Pfetsch 29 * 30 * A specially ordered set of type 2 (SOS2) is a sequence of variables such that at most two 31 * variables are nonzero and if two variables are nonzero they must be adjacent in the specified 32 * sequence. Note that it is in principle allowed that a variable appears twice, but it then can be 33 * fixed to 0 if it is at least two apart in the sequence. 34 * 35 * This constraint is useful when considering a piecewise affine approximation of a univariate 36 * (nonlinear) function \f$: [a,b] \rightarrow R\f$: Let \f$x_1 < \ldots < x_n\f$ be points in 37 * \f$[a,b]\f$ and introduce variables \f$\lambda_1, \ldots, \lambda_n\f$. To evaluate \f$f(x')\f$ 38 * at some point \f$x' \in [a,b]\f$ one can use the following constraints: 39 * \f[ 40 * \lambda_1 + \cdots + \lambda_n = 1,\quad x' = x_1 \lambda_1 + \cdots + x_n \lambda_n. 41 * \f] 42 * The value of \f$f(x')\f$ can the be approximated as 43 * \f[ 44 * f(x_1) \lambda_1 + \cdots + f(x_n) \lambda_n. 45 * \f] 46 * To get a valid piecewise affine approximation, \f$\lambda_1, \ldots, \lambda_n\f$ have to obey an 47 * SOS constraint of type 2. 48 * 49 * This implementation of this constraint handler is based on classical ideas, see e.g.@n 50 * "Special Facilities in General Mathematical Programming System for 51 * Non-Convex Problems Using Ordered Sets of Variables"@n 52 * E. Beale and J. Tomlin, Proc. 5th IFORS Conference, 447-454 (1970) 53 * 54 * The order of the variables is determined as follows: 55 * 56 * - If the constraint is created with SCIPcreateConsSOS2() and weights are given, the weights 57 * determine the order (decreasing weights). Additional variables can be added with 58 * SCIPaddVarSOS2(), which adds a variable with given weight. 59 * 60 * - If an empty constraint is created and then variables are added with SCIPaddVarSOS2(), weights 61 * are needed and stored. 62 * 63 * - All other calls ignore the weights, i.e., if a nonempty constraint is created or variables are 64 * added with SCIPappendVarSOS2(). 65 * 66 * @todo Allow to adapt the order of the constraints, e.g. by priorities. This for instance 67 * determines the branching order. 68 * @todo Separate the following cuts for each pair of variables x, y of at least distance 2 in the 69 * SOS2 constraint: \f$ \min \{l_x, l_y\} \leq x + y \leq \max \{u_x, u_y\}\f$, where \f$l_x, u_x, 70 * l_y, u_y\f$ are the lower and upper bounds of x and y, respectively. 71 * @todo Possibly allow to generate local cuts via strengthened local cuts (would affect lhs/rhs of rows) 72 * @todo Try to compute better estimations for the child nodes in enforceSOS2 when called for a relaxation solution; 73 * currently pseudo costs are used, which are not computed for the relaxation. 74 */ 75 76 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 77 78 #include "blockmemshell/memory.h" 79 #include "scip/cons_linear.h" 80 #include "scip/cons_sos2.h" 81 #include "scip/pub_cons.h" 82 #include "scip/pub_event.h" 83 #include "scip/pub_lp.h" 84 #include "scip/pub_message.h" 85 #include "scip/pub_misc.h" 86 #include "scip/pub_misc_sort.h" 87 #include "scip/pub_var.h" 88 #include "scip/scip_branch.h" 89 #include "scip/scip_conflict.h" 90 #include "scip/scip_cons.h" 91 #include "scip/scip_copy.h" 92 #include "scip/scip_cut.h" 93 #include "scip/scip_event.h" 94 #include "scip/scip_general.h" 95 #include "scip/scip_lp.h" 96 #include "scip/scip_mem.h" 97 #include "scip/scip_message.h" 98 #include "scip/scip_numerics.h" 99 #include "scip/scip_prob.h" 100 #include "scip/scip_sol.h" 101 #include "scip/scip_var.h" 102 #include "scip/symmetry_graph.h" 103 #include "symmetry/struct_symmetry.h" 104 #include <ctype.h> 105 #include <stdlib.h> 106 #include <string.h> 107 108 109 /* constraint handler properties */ 110 #define CONSHDLR_NAME "SOS2" 111 #define CONSHDLR_DESC "SOS2 constraint handler" 112 #define CONSHDLR_SEPAPRIORITY 10 /**< priority of the constraint handler for separation */ 113 #define CONSHDLR_ENFOPRIORITY 100 /**< priority of the constraint handler for constraint enforcing */ 114 #define CONSHDLR_CHECKPRIORITY -10 /**< priority of the constraint handler for checking feasibility */ 115 #define CONSHDLR_SEPAFREQ 0 /**< frequency for separating cuts; zero means to separate only in the root node */ 116 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */ 117 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation, 118 * propagation and enforcement, -1 for no eager evaluations, 0 for first only */ 119 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */ 120 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */ 121 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */ 122 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */ 123 124 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP 125 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_FAST 126 127 /* event handler properties */ 128 #define EVENTHDLR_NAME "SOS2" 129 #define EVENTHDLR_DESC "bound change event handler for SOS2 constraints" 130 131 #define EVENTHDLR_EVENT_TYPE (SCIP_EVENTTYPE_BOUNDCHANGED | SCIP_EVENTTYPE_GBDCHANGED) 132 133 134 /** constraint data for SOS2 constraints */ 135 struct SCIP_ConsData 136 { 137 int nvars; /**< number of variables in the constraint */ 138 int maxvars; /**< maximal number of variables (= size of storage) */ 139 int nfixednonzeros; /**< number of variables fixed to be nonzero */ 140 SCIP_VAR** vars; /**< variables in constraint */ 141 SCIP_ROW* row; /**< row corresponding to upper and lower bound inequalities, or NULL if not yet created */ 142 SCIP_Real* weights; /**< weights determining the order (ascending), or NULL if not used */ 143 }; 144 145 /** SOS2 constraint handler data */ 146 struct SCIP_ConshdlrData 147 { 148 SCIP_EVENTHDLR* eventhdlr; /**< event handler for bound change events */ 149 }; 150 151 152 /** fix variable in given node to 0 or add constraint if variable is multi-aggregated */ 153 static 154 SCIP_RETCODE fixVariableZeroNode( 155 SCIP* scip, /**< SCIP pointer */ 156 SCIP_VAR* var, /**< variable to be fixed to 0*/ 157 SCIP_NODE* node, /**< node */ 158 SCIP_Bool* infeasible /**< if fixing is infeasible */ 159 ) 160 { 161 /* if variable cannot be nonzero */ 162 *infeasible = FALSE; 163 if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var)) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(var)) ) 164 { 165 *infeasible = TRUE; 166 return SCIP_OKAY; 167 } 168 169 /* if variable is multi-aggregated */ 170 if ( SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR ) 171 { 172 SCIP_CONS* cons; 173 SCIP_Real val; 174 175 val = 1.0; 176 177 if ( ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) || ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) ) 178 { 179 SCIPdebugMsg(scip, "creating constraint to force multi-aggregated variable <%s> to 0.\n", SCIPvarGetName(var)); 180 /* we have to insert a local constraint var = 0 */ 181 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, "branch", 1, &var, &val, 0.0, 0.0, TRUE, TRUE, TRUE, TRUE, TRUE, 182 TRUE, FALSE, FALSE, FALSE, FALSE) ); 183 SCIP_CALL( SCIPaddConsNode(scip, node, cons, NULL) ); 184 SCIP_CALL( SCIPreleaseCons(scip, &cons) ); 185 } 186 } 187 else 188 { 189 if ( ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) ) 190 SCIP_CALL( SCIPchgVarLbNode(scip, node, var, 0.0) ); 191 if ( ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) ) 192 SCIP_CALL( SCIPchgVarUbNode(scip, node, var, 0.0) ); 193 } 194 195 return SCIP_OKAY; 196 } 197 198 199 /** fix variable in local node to 0, and return whether the operation was feasible 200 * 201 * @note We do not add a linear constraint if the variable is multi-aggregated as in 202 * fixVariableZeroNode(), since this would be too time consuming. 203 */ 204 static 205 SCIP_RETCODE inferVariableZero( 206 SCIP* scip, /**< SCIP pointer */ 207 SCIP_VAR* var, /**< variable to be fixed to 0*/ 208 SCIP_CONS* cons, /**< constraint */ 209 int inferinfo, /**< info for reverse prop. */ 210 SCIP_Bool* infeasible, /**< if fixing is infeasible */ 211 SCIP_Bool* tightened, /**< if fixing was performed */ 212 SCIP_Bool* success /**< whether fixing was successful, i.e., variable is not multi-aggregated */ 213 ) 214 { 215 *infeasible = FALSE; 216 *tightened = FALSE; 217 *success = FALSE; 218 219 /* if variable cannot be nonzero */ 220 if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var)) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(var)) ) 221 { 222 *infeasible = TRUE; 223 return SCIP_OKAY; 224 } 225 226 /* directly fix variable if it is not multi-aggregated, do nothing otherwise */ 227 if ( SCIPvarGetStatus(var) != SCIP_VARSTATUS_MULTAGGR ) 228 { 229 SCIP_Bool tighten; 230 231 /* fix lower bound */ 232 SCIP_CALL( SCIPinferVarLbCons(scip, var, 0.0, cons, inferinfo, FALSE, infeasible, &tighten) ); 233 *tightened = *tightened || tighten; 234 235 /* fix upper bound */ 236 SCIP_CALL( SCIPinferVarUbCons(scip, var, 0.0, cons, inferinfo, FALSE, infeasible, &tighten) ); 237 *tightened = *tightened || tighten; 238 239 *success = TRUE; 240 } 241 242 return SCIP_OKAY; 243 } 244 245 246 /** add lock on variable */ 247 static 248 SCIP_RETCODE lockVariableSOS2( 249 SCIP* scip, /**< SCIP data structure */ 250 SCIP_CONS* cons, /**< constraint */ 251 SCIP_VAR* var /**< variable */ 252 ) 253 { 254 assert( scip != NULL ); 255 assert( cons != NULL ); 256 assert( var != NULL ); 257 258 /* rounding down == bad if lb < 0, rounding up == bad if ub > 0 */ 259 SCIP_CALL( SCIPlockVarCons(scip, var, cons, SCIPisFeasNegative(scip, SCIPvarGetLbGlobal(var)), 260 SCIPisFeasPositive(scip, SCIPvarGetUbGlobal(var))) ); 261 262 return SCIP_OKAY; 263 } 264 265 266 /** remove lock on variable */ 267 static 268 SCIP_RETCODE unlockVariableSOS2( 269 SCIP* scip, /**< SCIP data structure */ 270 SCIP_CONS* cons, /**< constraint */ 271 SCIP_VAR* var /**< variable */ 272 ) 273 { 274 assert( scip != NULL ); 275 assert( cons != NULL ); 276 assert( var != NULL ); 277 278 /* rounding down == bad if lb < 0, rounding up == bad if ub > 0 */ 279 SCIP_CALL( SCIPunlockVarCons(scip, var, cons, SCIPisFeasNegative(scip, SCIPvarGetLbGlobal(var)), 280 SCIPisFeasPositive(scip, SCIPvarGetUbGlobal(var))) ); 281 282 return SCIP_OKAY; 283 } 284 285 286 /** ensures that the vars and weights array can store at least num entries */ 287 static 288 SCIP_RETCODE consdataEnsurevarsSizeSOS2( 289 SCIP* scip, /**< SCIP data structure */ 290 SCIP_CONSDATA* consdata, /**< constraint data */ 291 int num, /**< minimum number of entries to store */ 292 SCIP_Bool reserveWeights /**< whether the weights array is handled */ 293 ) 294 { 295 assert( consdata != NULL ); 296 assert( consdata->nvars <= consdata->maxvars ); 297 298 if ( num > consdata->maxvars ) 299 { 300 int newsize; 301 302 newsize = SCIPcalcMemGrowSize(scip, num); 303 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->vars, consdata->maxvars, newsize) ); 304 if ( reserveWeights ) 305 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->weights, consdata->maxvars, newsize) ); 306 consdata->maxvars = newsize; 307 } 308 assert( num <= consdata->maxvars ); 309 310 return SCIP_OKAY; 311 } 312 313 314 /** handle new variable */ 315 static 316 SCIP_RETCODE handleNewVariableSOS2( 317 SCIP* scip, /**< SCIP data structure */ 318 SCIP_CONS* cons, /**< constraint */ 319 SCIP_CONSDATA* consdata, /**< constraint data */ 320 SCIP_VAR* var, /**< variable */ 321 SCIP_Bool transformed /**< whether original variable was transformed */ 322 ) 323 { 324 assert( scip != NULL ); 325 assert( cons != NULL ); 326 assert( consdata != NULL ); 327 assert( var != NULL ); 328 329 /* if we are in transformed problem, catch the variable's events */ 330 if ( transformed ) 331 { 332 SCIP_CONSHDLR* conshdlr; 333 SCIP_CONSHDLRDATA* conshdlrdata; 334 335 /* get event handler */ 336 conshdlr = SCIPconsGetHdlr(cons); 337 conshdlrdata = SCIPconshdlrGetData(conshdlr); 338 assert( conshdlrdata != NULL ); 339 assert( conshdlrdata->eventhdlr != NULL ); 340 341 /* catch bound change events of variable */ 342 SCIP_CALL( SCIPcatchVarEvent(scip, var, EVENTHDLR_EVENT_TYPE, conshdlrdata->eventhdlr, 343 (SCIP_EVENTDATA*)cons, NULL) ); 344 345 /* if the variable if fixed to nonzero */ 346 assert( consdata->nfixednonzeros >= 0 ); 347 if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var)) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(var)) ) 348 ++consdata->nfixednonzeros; 349 } 350 351 /* install the rounding locks for the new variable */ 352 SCIP_CALL( lockVariableSOS2(scip, cons, var) ); 353 354 /* add the new coefficient to the LP row, if necessary */ 355 if ( consdata->row != NULL ) 356 { 357 /* this is currently dead code, since the constraint is not modifiable */ 358 SCIP_CALL( SCIPaddVarToRow(scip, consdata->row, var, 1.0) ); 359 360 /* update lhs and rhs if necessary */ 361 if ( SCIPisFeasGT(scip, SCIPvarGetUbLocal(var), SCIProwGetRhs(consdata->row)) ) 362 SCIP_CALL( SCIPchgRowRhs(scip, consdata->row, SCIPvarGetUbLocal(var) ) ); 363 if ( SCIPisFeasLT(scip, SCIPvarGetLbLocal(var), SCIProwGetLhs(consdata->row)) ) 364 SCIP_CALL( SCIPchgRowLhs(scip, consdata->row, SCIPvarGetLbLocal(var) ) ); 365 } 366 367 return SCIP_OKAY; 368 } 369 370 371 /** adds a variable to an SOS2 constraint, a position given by weight - ascending order */ 372 static 373 SCIP_RETCODE addVarSOS2( 374 SCIP* scip, /**< SCIP data structure */ 375 SCIP_CONS* cons, /**< constraint */ 376 SCIP_VAR* var, /**< variable to add to the constraint */ 377 SCIP_Real weight /**< weight to determine position */ 378 ) 379 { 380 SCIP_CONSDATA* consdata; 381 SCIP_Bool transformed; 382 int j; 383 int pos; 384 385 assert( var != NULL ); 386 assert( cons != NULL ); 387 388 consdata = SCIPconsGetData(cons); 389 assert( consdata != NULL ); 390 391 if ( consdata->weights == NULL && consdata->maxvars > 0 ) 392 { 393 SCIPerrorMessage("cannot add variable to SOS2 constraint <%s> that does not contain weights.\n", SCIPconsGetName(cons)); 394 return SCIP_INVALIDCALL; 395 } 396 397 /* are we in the transformed problem? */ 398 transformed = SCIPconsIsTransformed(cons); 399 400 /* always use transformed variables in transformed constraints */ 401 if ( transformed ) 402 { 403 SCIP_CALL( SCIPgetTransformedVar(scip, var, &var) ); 404 } 405 assert( var != NULL ); 406 assert( transformed == SCIPvarIsTransformed(var) ); 407 408 SCIP_CALL( consdataEnsurevarsSizeSOS2(scip, consdata, consdata->nvars + 1, TRUE) ); 409 assert( consdata->weights != NULL ); 410 assert( consdata->maxvars >= consdata->nvars+1 ); 411 412 /* find variable position */ 413 for (pos = 0; pos < consdata->nvars; ++pos) 414 { 415 if ( consdata->weights[pos] > weight ) 416 break; 417 } 418 assert( 0 <= pos && pos <= consdata->nvars ); 419 420 /* move other variables, if necessary */ 421 for (j = consdata->nvars; j > pos; --j) 422 { 423 consdata->vars[j] = consdata->vars[j-1]; 424 consdata->weights[j] = consdata->weights[j-1]; 425 } 426 427 /* insert variable */ 428 consdata->vars[pos] = var; 429 consdata->weights[pos] = weight; 430 ++consdata->nvars; 431 432 /* handle the new variable */ 433 SCIP_CALL( handleNewVariableSOS2(scip, cons, consdata, var, transformed) ); 434 435 return SCIP_OKAY; 436 } 437 438 439 /** appends a variable to an SOS2 constraint */ 440 static 441 SCIP_RETCODE appendVarSOS2( 442 SCIP* scip, /**< SCIP data structure */ 443 SCIP_CONS* cons, /**< constraint */ 444 SCIP_VAR* var /**< variable to add to the constraint */ 445 ) 446 { 447 SCIP_CONSDATA* consdata; 448 SCIP_Bool transformed; 449 450 assert( var != NULL ); 451 assert( cons != NULL ); 452 453 consdata = SCIPconsGetData(cons); 454 assert( consdata != NULL ); 455 assert( consdata->nvars >= 0 ); 456 457 /* are we in the transformed problem? */ 458 transformed = SCIPconsIsTransformed(cons); 459 460 /* always use transformed variables in transformed constraints */ 461 if ( transformed ) 462 { 463 SCIP_CALL( SCIPgetTransformedVar(scip, var, &var) ); 464 } 465 assert( var != NULL ); 466 assert( transformed == SCIPvarIsTransformed(var) ); 467 468 if ( consdata->weights != NULL ) 469 { 470 SCIP_CALL( consdataEnsurevarsSizeSOS2(scip, consdata, consdata->nvars + 1, TRUE) ); 471 } 472 else 473 { 474 SCIP_CALL( consdataEnsurevarsSizeSOS2(scip, consdata, consdata->nvars + 1, FALSE) ); 475 } 476 477 /* insert variable */ 478 consdata->vars[consdata->nvars] = var; 479 if ( consdata->weights != NULL ) 480 { 481 if ( consdata->nvars > 0 ) 482 consdata->weights[consdata->nvars] = consdata->weights[consdata->nvars-1] + 1.0; 483 else 484 consdata->weights[consdata->nvars] = 0.0; 485 } 486 ++consdata->nvars; 487 488 /* handle the new variable */ 489 SCIP_CALL( handleNewVariableSOS2(scip, cons, consdata, var, transformed) ); 490 491 return SCIP_OKAY; 492 } 493 494 495 /** deletes a variable of an SOS2 constraint */ 496 static 497 SCIP_RETCODE deleteVarSOS2( 498 SCIP* scip, /**< SCIP data structure */ 499 SCIP_CONS* cons, /**< constraint */ 500 SCIP_CONSDATA* consdata, /**< constraint data */ 501 SCIP_EVENTHDLR* eventhdlr, /**< corresponding event handler */ 502 int pos /**< position of variable in array */ 503 ) 504 { 505 int j; 506 507 assert( 0 <= pos && pos < consdata->nvars ); 508 509 /* remove lock of variable */ 510 SCIP_CALL( unlockVariableSOS2(scip, cons, consdata->vars[pos]) ); 511 512 /* drop events on variable */ 513 SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[pos], EVENTHDLR_EVENT_TYPE, eventhdlr, (SCIP_EVENTDATA*)cons, -1) ); 514 515 /* delete variable - need to copy since order is important */ 516 for (j = pos; j < consdata->nvars-1; ++j) 517 { 518 consdata->vars[j] = consdata->vars[j+1]; /*lint !e679*/ 519 if ( consdata->weights != NULL ) 520 consdata->weights[j] = consdata->weights[j+1]; /*lint !e679*/ 521 } 522 --consdata->nvars; 523 524 return SCIP_OKAY; 525 } 526 527 528 /** perform one presolving round 529 * 530 * We perform the following presolving steps. 531 * 532 * - If the bounds of one variable force it to be nonzero, we can fix all other variables with distance at least two to 533 * zero. If two variables are certain to be nonzero, we can fix all other variables to 0 and remove the constraint. 534 * - All variables fixed to zero, that are at the beginning or end of the constraint can be removed. 535 * - We substitute appregated variables. 536 * - If a constraint has at most two variables, we delete it. 537 * 538 * We currently do not handle the following: 539 * 540 * - If we have at least two variables fixed to zero next to each-other, that are positioned in the inner part of this 541 * constraint, we can delete all but one of these variables. 542 * - If a variable appears twice not next to each-other, it can be fixed to 0. If one variable appears next to 543 * each-other and is already certain to be nonzero, we can fix all variables. 544 * - If a binary variable and its negation appear in the constraint, we might fix variables to zero or can forbid a zero 545 * value for them. 546 * - When, after removing all zero "border" variables, a constraint with more than two variables has at most two 547 * variables that are not fixed to 0, only one of these can take a nonzero value, because these variables need to be 548 * the "border" variables of this constraint. The same holds if we have exactly three variables in one constraint and 549 * the middle variable is certain to be not zero. In both cases we can upgrade this constraint constraint to an sos1 550 * consisting only of the "border" variables. If these "border" variables are negations of each other, we can delete 551 * this constraint. 552 * - When, after removing all variables fixed to 0, that are possible, in a constraint each even positioned variable is 553 * fixed to 0, we can upgrade this constraint to an sos1 that holds all non-fixed variables. 554 * - Extract cliques for all odd and also for all even positioned binary variables 555 */ 556 static 557 SCIP_RETCODE presolRoundSOS2( 558 SCIP* scip, /**< SCIP pointer */ 559 SCIP_CONS* cons, /**< constraint */ 560 SCIP_CONSDATA* consdata, /**< constraint data */ 561 SCIP_EVENTHDLR* eventhdlr, /**< event handler */ 562 SCIP_Bool* cutoff, /**< whether a cutoff happened */ 563 SCIP_Bool* success, /**< whether we performed a successful reduction */ 564 int* ndelconss, /**< number of deleted constraints */ 565 int* nfixedvars, /**< number of fixed variables */ 566 int* nremovedvars /**< number of variables removed */ 567 ) 568 { 569 SCIP_VAR** vars; 570 SCIP_Bool infeasible; 571 SCIP_Bool fixed; 572 int nfixednonzeros; 573 int lastFixedNonzero; 574 int lastzero; 575 int localnremovedvars; 576 int oldnfixedvars; 577 int j; 578 579 assert( scip != NULL ); 580 assert( cons != NULL ); 581 assert( consdata != NULL ); 582 assert( eventhdlr != NULL ); 583 assert( cutoff != NULL ); 584 assert( success != NULL ); 585 assert( ndelconss != NULL ); 586 assert( nfixedvars != NULL ); 587 assert( nremovedvars != NULL ); 588 589 *cutoff = FALSE; 590 *success = FALSE; 591 592 SCIPdebugMsg(scip, "Presolving SOS2 constraint <%s>.\n", SCIPconsGetName(cons) ); 593 594 /* if the number of variables is at most 2 */ 595 if( consdata->nvars <= 2 ) 596 { 597 SCIPdebugMsg(scip, "Deleting constraint with <= 2 variables.\n"); 598 599 /* delete constraint */ 600 assert( ! SCIPconsIsModifiable(cons) ); 601 SCIP_CALL( SCIPdelCons(scip, cons) ); 602 ++(*ndelconss); 603 *success = TRUE; 604 605 return SCIP_OKAY; 606 } 607 608 nfixednonzeros = 0; 609 lastFixedNonzero = -1; 610 vars = consdata->vars; 611 lastzero = consdata->nvars; 612 localnremovedvars = 0; 613 614 /* check for variables fixed to 0 and bounds that guarantee a variable to be nonzero; downward loop is important */ 615 for( j = consdata->nvars - 1; j >= 0; --j ) 616 { 617 SCIP_VAR* var; 618 SCIP_Real lb; 619 SCIP_Real ub; 620 SCIP_Real scalar; 621 SCIP_Real constant; 622 623 /* check that our vars array is still correct */ 624 assert(vars == consdata->vars); 625 626 scalar = 1.0; 627 constant = 0.0; 628 629 /* check aggregation: if the constant is zero, the variable is zero iff the aggregated variable is 0 */ 630 var = vars[j]; 631 SCIP_CALL( SCIPgetProbvarSum(scip, &var, &scalar, &constant) ); 632 633 /* if constant is zero and we get a different variable, substitute variable */ 634 if ( SCIPisZero(scip, constant) && ! SCIPisZero(scip, scalar) && var != vars[j] ) 635 { 636 SCIPdebugMsg(scip, "substituted variable <%s> by <%s>.\n", SCIPvarGetName(vars[j]), SCIPvarGetName(var)); 637 SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[j], EVENTHDLR_EVENT_TYPE, eventhdlr, (SCIP_EVENTDATA*)cons, -1) ); 638 SCIP_CALL( SCIPcatchVarEvent(scip, var, EVENTHDLR_EVENT_TYPE, eventhdlr, (SCIP_EVENTDATA*)cons, NULL) ); 639 640 /* change the rounding locks */ 641 SCIP_CALL( unlockVariableSOS2(scip, cons, consdata->vars[j]) ); 642 SCIP_CALL( lockVariableSOS2(scip, cons, var) ); 643 644 vars[j] = var; 645 } 646 647 /* get bounds */ 648 lb = SCIPvarGetLbLocal(vars[j]); 649 ub = SCIPvarGetUbLocal(vars[j]); 650 651 /* if the variable if fixed to nonzero */ 652 if ( SCIPisFeasPositive(scip, lb) || SCIPisFeasNegative(scip, ub) ) 653 { 654 ++nfixednonzeros; 655 656 /* two variables certain to be nonzero which are not next to each other, so we are infeasible */ 657 if( lastFixedNonzero != -1 && lastFixedNonzero != j + 1 ) 658 { 659 SCIPdebugMsg(scip, "The problem is infeasible: two non-consecutive variables have bounds that keep them from being 0.\n"); 660 *cutoff = TRUE; 661 return SCIP_OKAY; 662 } 663 664 /* if more than two variables are fixed to be nonzero, we are infeasible */ 665 if( nfixednonzeros > 2 ) 666 { 667 SCIPdebugMsg(scip, "The problem is infeasible: more than two variables have bounds that keep them from being 0.\n"); 668 *cutoff = TRUE; 669 return SCIP_OKAY; 670 } 671 672 if( lastFixedNonzero == -1) 673 lastFixedNonzero = j; 674 } 675 676 /* if the variable is fixed to 0 we may delete it from our constraint */ 677 if( SCIPisFeasZero(scip, lb) && SCIPisFeasZero(scip, ub) ) 678 { 679 /* all rear variables fixed to 0 can be deleted */ 680 if( j == consdata->nvars - 1 ) 681 { 682 ++(*nremovedvars); 683 684 SCIPdebugMsg(scip, "deleting variable <%s> fixed to 0.\n", SCIPvarGetName(vars[j])); 685 SCIP_CALL( deleteVarSOS2(scip, cons, consdata, eventhdlr, j) ); 686 687 *success = TRUE; 688 } 689 /* remember position of last variable for which all up front and this one are fixed to 0 */ 690 else if( lastzero > j + 1 ) 691 lastzero = j; 692 } 693 else 694 lastzero = consdata->nvars; 695 } 696 697 /* check that our vars array is still correct */ 698 assert(vars == consdata->vars); 699 700 /* remove first "lastzero" many variables, that are already fixed to 0 */ 701 if( lastzero < consdata->nvars ) 702 { 703 assert(lastzero >= 0); 704 705 for( j = lastzero; j >= 0; --j ) 706 { 707 /* the variables should all be fixed to zero */ 708 assert(SCIPisFeasZero(scip, SCIPvarGetLbGlobal(vars[j])) && SCIPisFeasZero(scip, SCIPvarGetUbGlobal(vars[j]))); 709 710 SCIPdebugMsg(scip, "deleting variable <%s> fixed to 0.\n", SCIPvarGetName(vars[j])); 711 SCIP_CALL( deleteVarSOS2(scip, cons, consdata, eventhdlr, j) ); 712 } 713 localnremovedvars += (lastzero + 1); 714 *success = TRUE; 715 } 716 717 /* check that our variable array is still correct */ 718 assert(vars == consdata->vars); 719 720 *nremovedvars += localnremovedvars; 721 722 /* we might need to correct the position of the first variable which is certain to be not zero */ 723 if( lastFixedNonzero >= 0 ) 724 { 725 lastFixedNonzero -= localnremovedvars; 726 assert(0 <= lastFixedNonzero && lastFixedNonzero < consdata->nvars); 727 assert(SCIPisFeasPositive(scip, SCIPvarGetLbGlobal(vars[lastFixedNonzero])) || SCIPisFeasNegative(scip, SCIPvarGetUbGlobal(vars[lastFixedNonzero]))); 728 } 729 730 /* if the number of variables is at most 2 */ 731 if( consdata->nvars <= 2 ) 732 { 733 SCIPdebugMsg(scip, "Deleting constraint with <= 2 variables.\n"); 734 735 /* delete constraint */ 736 assert( ! SCIPconsIsModifiable(cons) ); 737 SCIP_CALL( SCIPdelCons(scip, cons) ); 738 ++(*ndelconss); 739 *success = TRUE; 740 741 return SCIP_OKAY; 742 } 743 744 oldnfixedvars = *nfixedvars; 745 746 /* if there is exactly one fixed nonzero variable */ 747 if ( nfixednonzeros == 1 ) 748 { 749 assert(0 <= lastFixedNonzero && lastFixedNonzero < consdata->nvars); 750 assert(SCIPisFeasPositive(scip, SCIPvarGetLbGlobal(vars[lastFixedNonzero])) || 751 SCIPisFeasNegative(scip, SCIPvarGetUbGlobal(vars[lastFixedNonzero]))); 752 753 /* fix all other variables with distance two to zero */ 754 for( j = 0; j < lastFixedNonzero - 1; ++j ) 755 { 756 SCIPdebugMsg(scip, "fixing variable <%s> to 0.\n", SCIPvarGetName(vars[j])); 757 SCIP_CALL( SCIPfixVar(scip, vars[j], 0.0, &infeasible, &fixed) ); 758 759 if( infeasible ) 760 { 761 *cutoff = TRUE; 762 return SCIP_OKAY; 763 } 764 765 if ( fixed ) 766 ++(*nfixedvars); 767 } 768 for( j = lastFixedNonzero + 2; j < consdata->nvars; ++j ) 769 { 770 SCIPdebugMsg(scip, "fixing variable <%s> to 0.\n", SCIPvarGetName(vars[j])); 771 SCIP_CALL( SCIPfixVar(scip, vars[j], 0.0, &infeasible, &fixed) ); 772 773 if( infeasible ) 774 { 775 *cutoff = TRUE; 776 return SCIP_OKAY; 777 } 778 779 if ( fixed ) 780 ++(*nfixedvars); 781 } 782 783 if( *nfixedvars > oldnfixedvars ) 784 *success = TRUE; 785 } 786 /* if there are exactly two fixed nonzero variables */ 787 else if ( nfixednonzeros == 2 ) 788 { 789 assert(0 < lastFixedNonzero && lastFixedNonzero < consdata->nvars); 790 assert(SCIPisFeasPositive(scip, SCIPvarGetLbGlobal(vars[lastFixedNonzero])) || 791 SCIPisFeasNegative(scip, SCIPvarGetUbGlobal(vars[lastFixedNonzero]))); 792 /* the previous variable need also to be nonzero, otherwise the infeasibility should have been detected earlier */ 793 assert(SCIPisFeasPositive(scip, SCIPvarGetLbGlobal(vars[lastFixedNonzero - 1])) || 794 SCIPisFeasNegative(scip, SCIPvarGetUbGlobal(vars[lastFixedNonzero - 1]))); 795 796 /* fix all variables before lastFixedNonzero to zero */ 797 for( j = 0; j < lastFixedNonzero - 1; ++j ) 798 { 799 SCIPdebugMsg(scip, "fixing variable <%s> to 0.\n", SCIPvarGetName(vars[j])); 800 SCIP_CALL( SCIPfixVar(scip, vars[j], 0.0, &infeasible, &fixed) ); 801 802 if( infeasible ) 803 { 804 *cutoff = TRUE; 805 return SCIP_OKAY; 806 } 807 if ( fixed ) 808 ++(*nfixedvars); 809 } 810 /* fix all variables after lastFixedNonzero + 1 to zero */ 811 for( j = lastFixedNonzero + 1; j < consdata->nvars; ++j ) 812 { 813 SCIPdebugMsg(scip, "fixing variable <%s> to 0.\n", SCIPvarGetName(vars[j])); 814 SCIP_CALL( SCIPfixVar(scip, vars[j], 0.0, &infeasible, &fixed) ); 815 816 if( infeasible ) 817 { 818 *cutoff = TRUE; 819 return SCIP_OKAY; 820 } 821 if ( fixed ) 822 ++(*nfixedvars); 823 } 824 825 /* delete constraint */ 826 assert( ! SCIPconsIsModifiable(cons) ); 827 SCIP_CALL( SCIPdelCons(scip, cons) ); 828 ++(*ndelconss); 829 *success = TRUE; 830 } 831 832 return SCIP_OKAY; 833 } 834 835 836 /** propagate variables */ 837 static 838 SCIP_RETCODE propSOS2( 839 SCIP* scip, /**< SCIP pointer */ 840 SCIP_CONS* cons, /**< constraint */ 841 SCIP_CONSDATA* consdata, /**< constraint data */ 842 SCIP_Bool* cutoff, /**< whether a cutoff happened */ 843 int* ngen /**< pointer to incremental counter for domain changes */ 844 ) 845 { 846 int ngenold; 847 848 assert( scip != NULL ); 849 assert( cons != NULL ); 850 assert( consdata != NULL ); 851 assert( cutoff != NULL ); 852 assert( ngen != NULL ); 853 854 *cutoff = FALSE; 855 ngenold = *ngen; 856 857 /* if more than two variables are fixed to be nonzero */ 858 if ( consdata->nfixednonzeros > 2 ) 859 { 860 SCIPdebugMsg(scip, "the node is infeasible, more than 2 variables are fixed to be nonzero.\n"); 861 SCIP_CALL( SCIPresetConsAge(scip, cons) ); 862 *cutoff = TRUE; 863 return SCIP_OKAY; 864 } 865 866 /* if exactly one variable is fixed to be nonzero */ 867 if ( consdata->nfixednonzeros == 1 ) 868 { 869 SCIP_VAR** vars; 870 SCIP_Bool infeasible; 871 SCIP_Bool tightened; 872 SCIP_Bool success; 873 int firstFixedNonzero; 874 int nvars; 875 int j; 876 877 firstFixedNonzero = -1; 878 nvars = consdata->nvars; 879 vars = consdata->vars; 880 assert( vars != NULL ); 881 882 /* search nonzero variable */ 883 for (j = 0; j < nvars; ++j) 884 { 885 if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(vars[j])) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(vars[j])) ) 886 { 887 firstFixedNonzero = j; 888 break; 889 } 890 } 891 assert( firstFixedNonzero >= 0 ); 892 893 SCIPdebugMsg(scip, "variable <%s> is nonzero, fixing variables with distance at least 2 to 0.\n", SCIPvarGetName(vars[firstFixedNonzero])); 894 895 /* fix variables before firstFixedNonzero-1 to 0 */ 896 for (j = 0; j < firstFixedNonzero-1; ++j) 897 { 898 /* fix variable */ 899 SCIP_CALL( inferVariableZero(scip, vars[j], cons, firstFixedNonzero, &infeasible, &tightened, &success) ); 900 assert( ! infeasible ); 901 902 if ( tightened ) 903 ++(*ngen); 904 } 905 906 /* fix variables after firstFixedNonzero+1 to 0 */ 907 for (j = firstFixedNonzero+2; j < nvars; ++j) 908 { 909 /* fix variable */ 910 SCIP_CALL( inferVariableZero(scip, vars[j], cons, firstFixedNonzero, &infeasible, &tightened, &success) ); 911 912 /* no variable after firstFixedNonzero+1 should be fixed to be nonzero */ 913 if ( infeasible ) 914 { 915 assert( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(vars[j])) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(vars[j])) ); 916 SCIPdebugMsg(scip, "the node is infeasible: variable <%s> is fixed nonzero and variable <%s> with distance at least 2 as well.\n", 917 SCIPvarGetName(vars[firstFixedNonzero]), SCIPvarGetName(vars[j])); 918 *cutoff = TRUE; 919 return SCIP_OKAY; 920 } 921 922 if ( tightened ) 923 ++(*ngen); 924 } 925 /* cannot locally delete constraint, since position of second entry is not fixed! */ 926 } /*lint !e438*/ 927 /* if exactly two variables are fixed to be nonzero */ 928 else if ( consdata->nfixednonzeros == 2 ) 929 { 930 SCIP_VAR** vars; 931 SCIP_Bool infeasible; 932 SCIP_Bool tightened; 933 SCIP_Bool success; 934 SCIP_Bool allVarFixed; 935 int firstFixedNonzero; 936 int nvars; 937 int j; 938 939 firstFixedNonzero = -1; 940 nvars = consdata->nvars; 941 vars = consdata->vars; 942 assert( vars != NULL ); 943 944 /* search nonzero variable */ 945 for (j = 0; j < nvars; ++j) 946 { 947 if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(vars[j])) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(vars[j])) ) 948 { 949 firstFixedNonzero = j; 950 break; 951 } 952 } 953 assert( 0 <= firstFixedNonzero && firstFixedNonzero < nvars-1 ); 954 955 SCIPdebugMsg(scip, "variable <%s> is fixed to be nonzero, fixing variables to 0.\n", SCIPvarGetName(vars[firstFixedNonzero])); 956 957 /* fix variables before firstFixedNonzero to 0 */ 958 allVarFixed = TRUE; 959 for (j = 0; j < firstFixedNonzero; ++j) 960 { 961 /* fix variable */ 962 SCIP_CALL( inferVariableZero(scip, vars[j], cons, firstFixedNonzero+1, &infeasible, &tightened, &success) ); 963 assert( ! infeasible ); 964 allVarFixed = allVarFixed && success; 965 if ( tightened ) 966 ++(*ngen); 967 } 968 969 /* fix variables after firstFixedNonzero+1 to 0 */ 970 for (j = firstFixedNonzero+2; j < nvars; ++j) 971 { 972 /* fix variable */ 973 SCIP_CALL( inferVariableZero(scip, vars[j], cons, firstFixedNonzero, &infeasible, &tightened, &success) ); 974 975 /* no variable after firstFixedNonzero+1 should be fixed to be nonzero */ 976 if ( infeasible ) 977 { 978 assert( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(vars[j])) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(vars[j])) ); 979 SCIPdebugMsg(scip, "the node is infeasible: variable <%s> is fixed nonzero and variable <%s> with distance at least 2 as well.\n", 980 SCIPvarGetName(vars[firstFixedNonzero]), SCIPvarGetName(vars[j])); 981 *cutoff = TRUE; 982 return SCIP_OKAY; 983 } 984 allVarFixed = allVarFixed && success; 985 986 if ( tightened ) 987 ++(*ngen); 988 } 989 990 /* delete constraint locally, since the nonzero positions are fixed */ 991 if ( allVarFixed ) 992 { 993 SCIPdebugMsg(scip, "locally deleting constraint <%s>.\n", SCIPconsGetName(cons)); 994 assert( !SCIPconsIsModifiable(cons) ); 995 SCIP_CALL( SCIPdelConsLocal(scip, cons) ); 996 } 997 } 998 999 /* reset constraint age counter */ 1000 if ( *ngen > ngenold ) 1001 SCIP_CALL( SCIPresetConsAge(scip, cons) ); 1002 1003 return SCIP_OKAY; 1004 } 1005 1006 1007 /** enforcement method 1008 * 1009 * We check whether the current solution is feasible, i.e., contains 1010 * at most one nonzero variable. If not, we branch along the lines 1011 * indicated by Beale and Tomlin: 1012 * 1013 * We first compute \f$W = \sum_{j=1}^n |x_i|\f$ and \f$w = 1014 * \sum_{j=1}^n j\, |x_i|\f$. Then we search for the index \f$k\f$ that 1015 * satisfies 1016 * \f[ 1017 * k \leq \frac{w}{W} < k+1. 1018 * \f] 1019 * The branches are then 1020 * \f[ 1021 * x_1 = 0, \ldots, x_{k-1} = 0 \qquad \mbox{and}\qquad 1022 * x_{k+1} = 0, \ldots, x_n = 0. 1023 * \f] 1024 * 1025 * There is one special case that we have to consider: It can happen 1026 * that \f$k\f$ is one too small. Example: \f$x_1 = 1 - \epsilon, x_2 1027 * = 0, x_3 = \epsilon\f$. Then \f$w = 1 - \epsilon + 3 \epsilon = 1 1028 * + 2 \epsilon\f$. This yields \f$k = 1\f$ and hence the first 1029 * branch does not change the solution. We therefore increase \f$k\f$ 1030 * by one if \f$x_k \neq 0\f$. This is valid, since we know that 1031 * \f$x_{k+1} \neq 0\f$ (with respect to the original \f$k\f$); the 1032 * corresponding branch will cut off the current solution, since 1033 * \f$x_k \neq 0\f$. 1034 */ 1035 static 1036 SCIP_RETCODE enforceSOS2( 1037 SCIP* scip, /**< SCIP pointer */ 1038 SCIP_CONSHDLR* conshdlr, /**< constraint handler */ 1039 int nconss, /**< number of constraints */ 1040 SCIP_CONS** conss, /**< indicator constraints */ 1041 SCIP_SOL* sol, /**< solution to be enforced (NULL for LP solution) */ 1042 SCIP_RESULT* result /**< result */ 1043 ) 1044 { 1045 SCIP_CONSDATA* consdata; 1046 SCIP_Bool infeasible; 1047 SCIP_NODE* node1; 1048 SCIP_NODE* node2; 1049 SCIP_CONS* branchCons = NULL; 1050 SCIP_VAR** vars; 1051 SCIP_Real nodeselest; 1052 SCIP_Real objest; 1053 int nvars; 1054 int maxNonzeros; 1055 int maxInd; 1056 int j; 1057 int c; 1058 1059 assert( scip != NULL ); 1060 assert( conshdlr != NULL ); 1061 assert( conss != NULL ); 1062 assert( result != NULL ); 1063 1064 maxNonzeros = 0; 1065 maxInd = -1; 1066 1067 SCIPdebugMsg(scip, "Enforcing SOS2 constraints <%s>.\n", SCIPconshdlrGetName(conshdlr) ); 1068 *result = SCIP_FEASIBLE; 1069 1070 /* check each constraint */ 1071 for (c = 0; c < nconss; ++c) 1072 { 1073 SCIP_CONS* cons; 1074 SCIP_Bool cutoff; 1075 SCIP_Real weight1; 1076 SCIP_Real weight2; 1077 SCIP_Real w; 1078 int lastNonzero; 1079 int ngen; 1080 int cnt; 1081 int ind; 1082 1083 cons = conss[c]; 1084 assert( cons != NULL ); 1085 1086 consdata = SCIPconsGetData(cons); 1087 assert( consdata != NULL ); 1088 1089 nvars = consdata->nvars; 1090 vars = consdata->vars; 1091 1092 /* do nothing if there are not enough variables - this is usually eliminated by preprocessing */ 1093 if ( nvars <= 2 ) 1094 return SCIP_OKAY; 1095 1096 ngen = 0; 1097 1098 /* first perform propagation (it might happen that standard propagation is turned off) */ 1099 SCIP_CALL( propSOS2(scip, cons, consdata, &cutoff, &ngen) ); 1100 SCIPdebugMsg(scip, "propagating <%s> in enforcing (cutoff: %u, domain reductions: %d).\n", SCIPconsGetName(cons), cutoff, ngen); 1101 if ( cutoff ) 1102 { 1103 *result = SCIP_CUTOFF; 1104 return SCIP_OKAY; 1105 } 1106 if ( ngen > 0 ) 1107 { 1108 *result = SCIP_REDUCEDDOM; 1109 return SCIP_OKAY; 1110 } 1111 1112 cnt = 0; 1113 weight1 = 0.0; 1114 weight2 = 0.0; 1115 lastNonzero = -1; 1116 1117 /* compute weight */ 1118 for (j = 0; j < nvars; ++j) 1119 { 1120 SCIP_Real val; 1121 1122 val = REALABS(SCIPgetSolVal(scip, sol, vars[j])); 1123 weight1 += val * (SCIP_Real) j; 1124 weight2 += val; 1125 1126 if ( ! SCIPisFeasZero(scip, val) ) 1127 { 1128 lastNonzero = j; 1129 ++cnt; 1130 } 1131 } 1132 1133 /* if at most one variable is nonzero, the constraint is feasible */ 1134 if ( cnt < 2 ) 1135 continue; 1136 1137 /* if two adjacent variables are nonzero */ 1138 assert( 0 < lastNonzero && lastNonzero < nvars ); 1139 if ( cnt == 2 && ! SCIPisFeasZero(scip, SCIPgetSolVal(scip, sol, vars[lastNonzero-1])) ) 1140 continue; 1141 1142 assert( !SCIPisFeasZero(scip, weight2) ); 1143 w = weight1/weight2; /*lint !e795*/ 1144 1145 ind = (int) SCIPfeasFloor(scip, w); 1146 assert( 0 <= ind && ind < nvars-1 ); 1147 1148 /* correct index if necessary - see above for an explanation */ 1149 if ( ! SCIPisFeasZero(scip, SCIPgetSolVal(scip, sol, vars[ind])) && ind < lastNonzero-1 ) 1150 ++ind; 1151 1152 /* check if the constraint has more nonzeros */ 1153 if ( cnt > maxNonzeros ) 1154 { 1155 maxNonzeros = cnt; 1156 branchCons = cons; 1157 maxInd = ind; 1158 } 1159 } 1160 1161 /* if all constraints are feasible */ 1162 if ( branchCons == NULL ) 1163 { 1164 SCIPdebugMsg(scip, "All SOS2 constraints are feasible.\n"); 1165 return SCIP_OKAY; 1166 } 1167 1168 /* create branches */ 1169 consdata = SCIPconsGetData(branchCons); 1170 assert( consdata != NULL ); 1171 nvars = consdata->nvars; 1172 vars = consdata->vars; 1173 1174 assert( 0 < maxInd && maxInd < nvars-1 ); 1175 1176 /* branch on variable ind: either all variables before ind or all variables after ind are zero */ 1177 SCIPdebugMsg(scip, "Branching on variable <%s> in constraint <%s> (nonzeros: %d).\n", SCIPvarGetName(vars[maxInd]), 1178 SCIPconsGetName(branchCons), maxNonzeros); 1179 1180 /* calculate node selection and objective estimate for node 1 */ 1181 nodeselest = 0.0; 1182 objest = SCIPgetLocalTransEstimate(scip); 1183 for (j = 0; j < maxInd; ++j) 1184 { 1185 objest += SCIPcalcChildEstimateIncrease(scip, vars[j], SCIPgetSolVal(scip, sol, vars[j]), 0.0); 1186 nodeselest += SCIPcalcNodeselPriority(scip, vars[j], SCIP_BRANCHDIR_DOWNWARDS, 0.0); 1187 } 1188 assert( objest >= SCIPgetLocalTransEstimate(scip) ); 1189 1190 /* create node 1 */ 1191 SCIP_CALL( SCIPcreateChild(scip, &node1, nodeselest, objest) ); 1192 1193 for (j = 0; j < maxInd; ++j) 1194 { 1195 SCIP_CALL( fixVariableZeroNode(scip, vars[j], node1, &infeasible) ); 1196 assert( ! infeasible ); 1197 } 1198 1199 /* calculate node selection and objective estimate for node 2 */ 1200 nodeselest = 0.0; 1201 objest = SCIPgetLocalTransEstimate(scip); 1202 for (j = maxInd+1; j < nvars; ++j) 1203 { 1204 objest += SCIPcalcChildEstimateIncrease(scip, vars[j], SCIPgetSolVal(scip, sol, vars[j]), 0.0); 1205 nodeselest += SCIPcalcNodeselPriority(scip, vars[j], SCIP_BRANCHDIR_DOWNWARDS, 0.0); 1206 } 1207 assert( objest >= SCIPgetLocalTransEstimate(scip) ); 1208 1209 /* create node 2 */ 1210 SCIP_CALL( SCIPcreateChild(scip, &node2, nodeselest, objest) ); 1211 for (j = maxInd+1; j < nvars; ++j) 1212 { 1213 SCIP_CALL( fixVariableZeroNode(scip, vars[j], node2, &infeasible) ); 1214 assert( ! infeasible ); 1215 } 1216 SCIP_CALL( SCIPresetConsAge(scip, branchCons) ); 1217 *result = SCIP_BRANCHED; 1218 1219 return SCIP_OKAY; 1220 } 1221 1222 1223 /** Generate basic row 1224 * 1225 * We generate the row corresponding to the following simple valid 1226 * inequalities. Let \f$U\f$ and \f$U'\f$ be the largest and second 1227 * largest upper bound of variables appearing in the 1228 * constraint. Similarly let \f$L\f$ and \f$L'\f$ be the smallest and 1229 * second smallest lower bound. The inequalities are: 1230 * \f[ 1231 * x_1 + \ldots + x_n \leq U + U' \qquad\mbox{and}\qquad 1232 * x_1 + \ldots + x_n \geq L + L'. 1233 * \f] 1234 * Of course, these inequalities are only added if the upper and 1235 * lower bounds are all finite and \f$L+L' < 0\f$ or \f$U+U' > 0\f$. 1236 */ 1237 static 1238 SCIP_RETCODE generateRowSOS2( 1239 SCIP* scip, /**< SCIP pointer */ 1240 SCIP_CONSHDLR* conshdlr, /**< constraint handler */ 1241 SCIP_CONS* cons, /**< constraint */ 1242 SCIP_Bool local /**< produce local cut? */ 1243 ) 1244 { 1245 char name[SCIP_MAXSTRLEN]; 1246 SCIP_CONSDATA* consdata; 1247 SCIP_VAR** vars; 1248 SCIP_Real minLb = SCIPinfinity(scip); 1249 SCIP_Real minLb2 = SCIPinfinity(scip); 1250 SCIP_Real maxUb = -SCIPinfinity(scip); 1251 SCIP_Real maxUb2 = -SCIPinfinity(scip); 1252 SCIP_Real lhs; 1253 SCIP_Real rhs; 1254 SCIP_ROW* row; 1255 int nvars; 1256 int j; 1257 1258 assert( scip != NULL ); 1259 assert( conshdlr != NULL ); 1260 assert( cons != NULL ); 1261 1262 consdata = SCIPconsGetData(cons); 1263 assert( consdata != NULL ); 1264 assert( consdata->row == NULL ); 1265 1266 nvars = consdata->nvars; 1267 vars = consdata->vars; 1268 assert( vars != NULL ); 1269 1270 /* find minimum and maximum lower and upper bounds */ 1271 for (j = 0; j < nvars; ++j) 1272 { 1273 SCIP_Real val; 1274 1275 if ( local ) 1276 val = SCIPvarGetLbLocal(vars[j]); 1277 else 1278 val = SCIPvarGetLbGlobal(vars[j]); 1279 1280 if ( val < minLb ) 1281 { 1282 minLb2 = minLb; 1283 minLb = val; 1284 } 1285 else 1286 { 1287 if ( val < minLb2 ) 1288 minLb2 = val; 1289 } 1290 1291 if ( local ) 1292 val = SCIPvarGetUbLocal(vars[j]); 1293 else 1294 val = SCIPvarGetUbGlobal(vars[j]); 1295 1296 if ( val > maxUb ) 1297 { 1298 maxUb2 = maxUb; 1299 maxUb = val; 1300 } 1301 else 1302 { 1303 if ( val > maxUb2 ) 1304 maxUb2 = val; 1305 } 1306 } 1307 lhs = minLb + minLb2; 1308 rhs = maxUb + maxUb2; 1309 1310 /* ignore trivial inequality if left hand side would be 0 */ 1311 if ( SCIPisFeasZero(scip, lhs) ) 1312 lhs = -SCIPinfinity(scip); 1313 1314 /* ignore trivial inequality if right hand side would be 0 */ 1315 if ( SCIPisFeasZero(scip, rhs) ) 1316 rhs = SCIPinfinity(scip); 1317 1318 /* create upper and lower bound inequality if one of the bounds is finite */ 1319 if ( ! SCIPisInfinity(scip, REALABS(lhs)) || ! SCIPisInfinity(scip, REALABS(rhs)) ) 1320 { 1321 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "sos2bnd#%s", SCIPconsGetName(cons)); 1322 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, lhs, rhs, local, FALSE, FALSE) ); 1323 SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, row, nvars, vars, 1.0) ); 1324 consdata->row = row; 1325 1326 SCIPdebug( SCIP_CALL( SCIPprintRow(scip, row, NULL) ) ); 1327 } 1328 1329 return SCIP_OKAY; 1330 } 1331 1332 1333 /* ---------------------------- constraint handler callback methods ----------------------*/ 1334 1335 /** copy method for constraint handler plugins (called when SCIP copies plugins) */ 1336 static 1337 SCIP_DECL_CONSHDLRCOPY(conshdlrCopySOS2) 1338 { /*lint --e{715}*/ 1339 assert( scip != NULL ); 1340 assert( conshdlr != NULL ); 1341 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1342 1343 /* call inclusion method of constraint handler */ 1344 SCIP_CALL( SCIPincludeConshdlrSOS2(scip) ); 1345 1346 *valid = TRUE; 1347 1348 return SCIP_OKAY; 1349 } 1350 1351 1352 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */ 1353 static 1354 SCIP_DECL_CONSFREE(consFreeSOS2) 1355 { 1356 SCIP_CONSHDLRDATA* conshdlrdata; 1357 1358 assert( scip != NULL ); 1359 assert( conshdlr != NULL ); 1360 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1361 1362 conshdlrdata = SCIPconshdlrGetData(conshdlr); 1363 assert(conshdlrdata != NULL); 1364 1365 SCIPfreeBlockMemory(scip, &conshdlrdata); 1366 1367 return SCIP_OKAY; 1368 } 1369 1370 1371 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */ 1372 static 1373 SCIP_DECL_CONSEXITSOL(consExitsolSOS2) 1374 { /*lint --e{715}*/ 1375 int c; 1376 1377 assert( scip != NULL ); 1378 assert( conshdlr != NULL ); 1379 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1380 1381 /* check each constraint */ 1382 for (c = 0; c < nconss; ++c) 1383 { 1384 SCIP_CONSDATA* consdata; 1385 1386 assert( conss != NULL ); 1387 assert( conss[c] != NULL ); 1388 consdata = SCIPconsGetData(conss[c]); 1389 assert( consdata != NULL ); 1390 1391 SCIPdebugMsg(scip, "Exiting SOS2 constraint <%s>.\n", SCIPconsGetName(conss[c]) ); 1392 1393 /* free row */ 1394 if ( consdata->row != NULL ) 1395 { 1396 SCIP_CALL( SCIPreleaseRow(scip, &consdata->row) ); 1397 } 1398 } 1399 return SCIP_OKAY; 1400 } 1401 1402 1403 /** frees specific constraint data */ 1404 static 1405 SCIP_DECL_CONSDELETE(consDeleteSOS2) 1406 { 1407 assert( scip != NULL ); 1408 assert( conshdlr != NULL ); 1409 assert( cons != NULL ); 1410 assert( consdata != NULL ); 1411 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1412 1413 SCIPdebugMsg(scip, "Deleting SOS2 constraint <%s>.\n", SCIPconsGetName(cons) ); 1414 1415 /* drop events on transformed variables */ 1416 if ( SCIPconsIsTransformed(cons) ) 1417 { 1418 SCIP_CONSHDLRDATA* conshdlrdata; 1419 int j; 1420 1421 /* get constraint handler data */ 1422 conshdlrdata = SCIPconshdlrGetData(conshdlr); 1423 assert( conshdlrdata != NULL ); 1424 assert( conshdlrdata->eventhdlr != NULL ); 1425 1426 for (j = 0; j < (*consdata)->nvars; ++j) 1427 { 1428 SCIP_CALL( SCIPdropVarEvent(scip, (*consdata)->vars[j], EVENTHDLR_EVENT_TYPE, conshdlrdata->eventhdlr, 1429 (SCIP_EVENTDATA*)cons, -1) ); 1430 } 1431 } 1432 1433 SCIPfreeBlockMemoryArray(scip, &(*consdata)->vars, (*consdata)->maxvars); 1434 if ( (*consdata)->weights != NULL ) 1435 { 1436 SCIPfreeBlockMemoryArray(scip, &(*consdata)->weights, (*consdata)->maxvars); 1437 } 1438 1439 /* free row */ 1440 if ( (*consdata)->row != NULL ) 1441 { 1442 SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->row) ); 1443 } 1444 assert( (*consdata)->row == NULL ); 1445 1446 SCIPfreeBlockMemory(scip, consdata); 1447 1448 return SCIP_OKAY; 1449 } 1450 1451 1452 /** transforms constraint data into data belonging to the transformed problem */ 1453 static 1454 SCIP_DECL_CONSTRANS(consTransSOS2) 1455 { 1456 SCIP_CONSDATA* consdata; 1457 SCIP_CONSHDLRDATA* conshdlrdata; 1458 SCIP_CONSDATA* sourcedata; 1459 char s[SCIP_MAXSTRLEN]; 1460 int j; 1461 1462 assert( scip != NULL ); 1463 assert( conshdlr != NULL ); 1464 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1465 assert( sourcecons != NULL ); 1466 assert( targetcons != NULL ); 1467 1468 /* get constraint handler data */ 1469 conshdlrdata = SCIPconshdlrGetData(conshdlr); 1470 assert( conshdlrdata != NULL ); 1471 assert( conshdlrdata->eventhdlr != NULL ); 1472 1473 SCIPdebugMsg(scip, "Transforming SOS2 constraint: <%s>.\n", SCIPconsGetName(sourcecons) ); 1474 1475 /* get data of original constraint */ 1476 sourcedata = SCIPconsGetData(sourcecons); 1477 assert( sourcedata != NULL ); 1478 assert( sourcedata->nvars > 0 ); 1479 assert( sourcedata->nvars <= sourcedata->maxvars ); 1480 1481 /* create constraint data */ 1482 SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) ); 1483 1484 consdata->nvars = sourcedata->nvars; 1485 consdata->maxvars = sourcedata->nvars; 1486 consdata->row = NULL; 1487 consdata->nfixednonzeros = 0; 1488 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->vars, consdata->nvars) ); 1489 1490 /* if weights were used */ 1491 if ( sourcedata->weights != NULL ) 1492 { 1493 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->weights, sourcedata->weights, consdata->nvars) ); 1494 } 1495 else 1496 consdata->weights = NULL; 1497 1498 for (j = 0; j < sourcedata->nvars; ++j) 1499 { 1500 assert( sourcedata->vars[j] != 0 ); 1501 SCIP_CALL( SCIPgetTransformedVar(scip, sourcedata->vars[j], &(consdata->vars[j])) ); 1502 1503 /* if variable is fixed to be nonzero */ 1504 if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(consdata->vars[j])) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(consdata->vars[j])) ) 1505 ++(consdata->nfixednonzeros); 1506 } 1507 1508 /* create transformed constraint with the same flags */ 1509 (void) SCIPsnprintf(s, SCIP_MAXSTRLEN, "t_%s", SCIPconsGetName(sourcecons)); 1510 SCIP_CALL( SCIPcreateCons(scip, targetcons, s, conshdlr, consdata, 1511 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), 1512 SCIPconsIsEnforced(sourcecons), SCIPconsIsChecked(sourcecons), 1513 SCIPconsIsPropagated(sourcecons), SCIPconsIsLocal(sourcecons), 1514 SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons), 1515 SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) ); 1516 1517 /* catch bound change events on variable */ 1518 for (j = 0; j < consdata->nvars; ++j) 1519 { 1520 SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[j], EVENTHDLR_EVENT_TYPE, conshdlrdata->eventhdlr, 1521 (SCIP_EVENTDATA*)*targetcons, NULL) ); 1522 } 1523 1524 #ifdef SCIP_DEBUG 1525 if ( consdata->nfixednonzeros > 0 ) 1526 { 1527 SCIPdebugMsg(scip, "constraint <%s> has %d variables fixed to be nonzero.\n", SCIPconsGetName(*targetcons), consdata->nfixednonzeros ); 1528 } 1529 #endif 1530 1531 return SCIP_OKAY; 1532 } 1533 1534 1535 /** presolving method of constraint handler */ 1536 static 1537 SCIP_DECL_CONSPRESOL(consPresolSOS2) 1538 { /*lint --e{715}*/ 1539 SCIPdebug( int oldnfixedvars = *nfixedvars; ) 1540 SCIPdebug( int oldndelconss = *ndelconss; ) 1541 int nremovedvars; 1542 SCIP_EVENTHDLR* eventhdlr; 1543 int c; 1544 1545 assert( scip != NULL ); 1546 assert( conshdlr != NULL ); 1547 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1548 assert( result != NULL ); 1549 1550 *result = SCIP_DIDNOTRUN; 1551 nremovedvars = 0; 1552 1553 /* only run if success is possible */ 1554 if( nrounds == 0 || nnewfixedvars > 0 || nnewaggrvars > 0 || nnewchgcoefs > 0 ) 1555 { 1556 /* get constraint handler data */ 1557 assert( SCIPconshdlrGetData(conshdlr) != NULL ); 1558 eventhdlr = SCIPconshdlrGetData(conshdlr)->eventhdlr; 1559 assert( eventhdlr != NULL ); 1560 1561 *result = SCIP_DIDNOTFIND; 1562 1563 /* check each constraint */ 1564 for (c = 0; c < nconss; ++c) 1565 { 1566 SCIP_CONSDATA* consdata; 1567 SCIP_CONS* cons; 1568 SCIP_Bool cutoff; 1569 SCIP_Bool success; 1570 1571 assert( conss != NULL ); 1572 assert( conss[c] != NULL ); 1573 1574 cons = conss[c]; 1575 consdata = SCIPconsGetData(cons); 1576 1577 assert( consdata != NULL ); 1578 assert( consdata->nvars >= 0 ); 1579 assert( consdata->nvars <= consdata->maxvars ); 1580 assert( ! SCIPconsIsModifiable(cons) ); 1581 1582 /* perform one presolving round */ 1583 SCIP_CALL( presolRoundSOS2(scip, cons, consdata, eventhdlr, &cutoff, &success, ndelconss, nfixedvars, &nremovedvars) ); 1584 1585 if ( cutoff ) 1586 { 1587 *result = SCIP_CUTOFF; 1588 return SCIP_OKAY; 1589 } 1590 1591 if ( success ) 1592 *result = SCIP_SUCCESS; 1593 } 1594 } 1595 (*nchgcoefs) += nremovedvars; 1596 1597 SCIPdebug( SCIPdebugMsg(scip, "presolving fixed %d variables, removed %d variables, and deleted %d constraints.\n", 1598 *nfixedvars - oldnfixedvars, nremovedvars, *ndelconss - oldndelconss); ) 1599 1600 return SCIP_OKAY; 1601 } 1602 1603 1604 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */ 1605 static 1606 SCIP_DECL_CONSINITLP(consInitlpSOS2) 1607 { 1608 int c; 1609 1610 assert( scip != NULL ); 1611 assert( conshdlr != NULL ); 1612 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1613 1614 *infeasible = FALSE; 1615 1616 /* check each constraint */ 1617 for (c = 0; c < nconss && !(*infeasible); ++c) 1618 { 1619 SCIP_CONSDATA* consdata; 1620 1621 assert( conss != NULL ); 1622 assert( conss[c] != NULL ); 1623 consdata = SCIPconsGetData(conss[c]); 1624 assert( consdata != NULL ); 1625 1626 SCIPdebugMsg(scip, "Checking for initial rows for SOS2 constraint <%s>.\n", SCIPconsGetName(conss[c]) ); 1627 1628 /* possibly generate row if not yet done */ 1629 if ( consdata->row == NULL ) 1630 { 1631 SCIP_CALL( generateRowSOS2(scip, conshdlr, conss[c], FALSE) ); 1632 } 1633 1634 /* put corresponding rows into LP */ 1635 if ( consdata->row != NULL && ! SCIProwIsInLP(consdata->row) ) 1636 { 1637 assert( ! SCIPisInfinity(scip, REALABS(SCIProwGetLhs(consdata->row))) || ! SCIPisInfinity(scip, REALABS(SCIProwGetRhs(consdata->row))) ); 1638 1639 SCIP_CALL( SCIPaddRow(scip, consdata->row, FALSE, infeasible) ); 1640 SCIPdebug( SCIP_CALL( SCIPprintRow(scip, consdata->row, NULL) ) ); 1641 } 1642 } 1643 1644 return SCIP_OKAY; 1645 } 1646 1647 1648 /** separation method of constraint handler for LP solutions */ 1649 static 1650 SCIP_DECL_CONSSEPALP(consSepalpSOS2) 1651 { /*lint --e{715}*/ 1652 SCIP_Bool cutoff = FALSE; 1653 int c; 1654 int ngen = 0; 1655 1656 assert( scip != NULL ); 1657 assert( conshdlr != NULL ); 1658 assert( conss != NULL ); 1659 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1660 assert( result != NULL ); 1661 1662 *result = SCIP_DIDNOTRUN; 1663 1664 /* check each constraint */ 1665 for (c = 0; c < nconss && ! cutoff; ++c) 1666 { 1667 SCIP_CONSDATA* consdata; 1668 SCIP_ROW* row; 1669 1670 *result = SCIP_DIDNOTFIND; 1671 assert( conss[c] != NULL ); 1672 consdata = SCIPconsGetData(conss[c]); 1673 assert( consdata != NULL ); 1674 SCIPdebugMsg(scip, "Separating inequalities for SOS2 constraint <%s>.\n", SCIPconsGetName(conss[c]) ); 1675 1676 /* possibly generate row if not yet done */ 1677 if ( consdata->row == NULL ) 1678 { 1679 SCIP_CALL( generateRowSOS2(scip, conshdlr, conss[c], FALSE) ); 1680 } 1681 1682 /* put corresponding rows into LP if they are useful */ 1683 row = consdata->row; 1684 1685 /* possibly add row to LP if it is useful */ 1686 if ( row != NULL && ! SCIProwIsInLP(row) && SCIPisCutEfficacious(scip, NULL, row) ) 1687 { 1688 SCIP_CALL( SCIPaddRow(scip, row, FALSE, &cutoff) ); 1689 SCIPdebug( SCIP_CALL( SCIPprintRow(scip, row, NULL) ) ); 1690 SCIP_CALL( SCIPresetConsAge(scip, conss[c]) ); 1691 ++ngen; 1692 } 1693 } 1694 SCIPdebugMsg(scip, "Separated %d SOS2 constraints.\n", ngen); 1695 if ( cutoff ) 1696 *result = SCIP_CUTOFF; 1697 else if ( ngen > 0 ) 1698 *result = SCIP_SEPARATED; 1699 1700 return SCIP_OKAY; 1701 } 1702 1703 1704 /** separation method of constraint handler for arbitrary primal solutions */ 1705 static 1706 SCIP_DECL_CONSSEPASOL(consSepasolSOS2) 1707 { /*lint --e{715}*/ 1708 SCIP_Bool cutoff = FALSE; 1709 int c; 1710 int ngen = 0; 1711 1712 assert( scip != NULL ); 1713 assert( conshdlr != NULL ); 1714 assert( conss != NULL ); 1715 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1716 assert( result != NULL ); 1717 1718 *result = SCIP_DIDNOTRUN; 1719 1720 /* check each constraint */ 1721 for (c = 0; c < nconss && ! cutoff; ++c) 1722 { 1723 SCIP_CONSDATA* consdata; 1724 SCIP_ROW* row; 1725 1726 *result = SCIP_DIDNOTFIND; 1727 assert( conss[c] != NULL ); 1728 consdata = SCIPconsGetData(conss[c]); 1729 assert( consdata != NULL ); 1730 SCIPdebugMsg(scip, "Separating solution for SOS2 constraint <%s>.\n", SCIPconsGetName(conss[c]) ); 1731 1732 /* put corresponding row into LP if it is useful */ 1733 row = consdata->row; 1734 1735 /* possibly generate row if not yet done */ 1736 if ( row == NULL ) 1737 { 1738 SCIP_CALL( generateRowSOS2(scip, conshdlr, conss[c], FALSE) ); 1739 } 1740 1741 /* possibly add row to LP if it is useful */ 1742 if ( row != NULL && ! SCIProwIsInLP(row) && SCIPisCutEfficacious(scip, sol, row) ) 1743 { 1744 SCIP_CALL( SCIPaddRow(scip, row, FALSE, &cutoff) ); 1745 SCIPdebug( SCIP_CALL( SCIPprintRow(scip, row, NULL) ) ); 1746 SCIP_CALL( SCIPresetConsAge(scip, conss[c]) ); 1747 ++ngen; 1748 } 1749 } 1750 SCIPdebugMsg(scip, "Separated %d SOS2 constraints.\n", ngen); 1751 if ( cutoff ) 1752 *result = SCIP_CUTOFF; 1753 else if ( ngen > 0 ) 1754 *result = SCIP_SEPARATED; 1755 1756 return SCIP_OKAY; 1757 } 1758 1759 1760 /** constraint enforcing method of constraint handler for LP solutions */ 1761 static 1762 SCIP_DECL_CONSENFOLP(consEnfolpSOS2) 1763 { /*lint --e{715}*/ 1764 assert( scip != NULL ); 1765 assert( conshdlr != NULL ); 1766 assert( conss != NULL ); 1767 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1768 assert( result != NULL ); 1769 1770 SCIP_CALL( enforceSOS2(scip, conshdlr, nconss, conss, NULL, result) ); 1771 1772 return SCIP_OKAY; 1773 } 1774 1775 1776 /** constraint enforcing method of constraint handler for relaxation solutions */ 1777 static 1778 SCIP_DECL_CONSENFORELAX(consEnforelaxSOS2) 1779 { /*lint --e{715}*/ 1780 assert( scip != NULL ); 1781 assert( conshdlr != NULL ); 1782 assert( conss != NULL ); 1783 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1784 assert( result != NULL ); 1785 1786 SCIP_CALL( enforceSOS2(scip, conshdlr, nconss, conss, sol, result) ); 1787 1788 return SCIP_OKAY; 1789 } 1790 1791 1792 /** constraint enforcing method of constraint handler for pseudo solutions */ 1793 static 1794 SCIP_DECL_CONSENFOPS(consEnfopsSOS2) 1795 { /*lint --e{715}*/ 1796 assert( scip != NULL ); 1797 assert( conshdlr != NULL ); 1798 assert( conss != NULL ); 1799 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1800 assert( result != NULL ); 1801 1802 SCIP_CALL( enforceSOS2(scip, conshdlr, nconss, conss, NULL, result) ); 1803 1804 return SCIP_OKAY; 1805 } 1806 1807 1808 /** feasibility check method of constraint handler for integral solutions 1809 * 1810 * We simply check whether at most two variable are nonzero and in the 1811 * case there are exactly two nonzero, then they have to be direct 1812 * neighbors in the given solution. 1813 */ 1814 static 1815 SCIP_DECL_CONSCHECK(consCheckSOS2) 1816 { /*lint --e{715}*/ 1817 int c; 1818 1819 assert( scip != NULL ); 1820 assert( conshdlr != NULL ); 1821 assert( conss != NULL ); 1822 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1823 assert( result != NULL ); 1824 1825 *result = SCIP_FEASIBLE; 1826 1827 /* check each constraint */ 1828 for (c = 0; c < nconss && (*result == SCIP_FEASIBLE || completely); ++c) 1829 { 1830 SCIP_CONSDATA* consdata; 1831 int firstNonzero; 1832 int j; 1833 1834 firstNonzero = -1; 1835 assert( conss[c] != NULL ); 1836 consdata = SCIPconsGetData(conss[c]); 1837 assert( consdata != NULL ); 1838 SCIPdebugMsg(scip, "Checking SOS2 constraint <%s>.\n", SCIPconsGetName(conss[c])); 1839 1840 /* check all variables */ 1841 for (j = 0; j < consdata->nvars; ++j) 1842 { 1843 /* if variable is nonzero */ 1844 if ( ! SCIPisFeasZero(scip, SCIPgetSolVal(scip, sol, consdata->vars[j])) ) 1845 { 1846 if ( firstNonzero < 0 ) 1847 firstNonzero = j; 1848 else 1849 { 1850 /* if we are more than one position away from the firstNonzero variable */ 1851 if ( j > firstNonzero+1 ) 1852 { 1853 SCIP_CALL( SCIPresetConsAge(scip, conss[c]) ); 1854 *result = SCIP_INFEASIBLE; 1855 1856 /* update constraint violation in solution */ 1857 if ( sol != NULL ) 1858 SCIPupdateSolConsViolation(scip, sol, 1.0, 1.0); 1859 1860 if ( printreason ) 1861 { 1862 SCIP_CALL( SCIPprintCons(scip, conss[c], NULL) ); 1863 1864 SCIPinfoMessage(scip, NULL, ";\nviolation: <%s> = %.15g and <%s> = %.15g\n", 1865 SCIPvarGetName(consdata->vars[firstNonzero]), 1866 SCIPgetSolVal(scip, sol, consdata->vars[firstNonzero]), 1867 SCIPvarGetName(consdata->vars[j]), 1868 SCIPgetSolVal(scip, sol, consdata->vars[j])); 1869 } 1870 1871 SCIPdebugMsg(scip, "SOS2 constraint <%s> infeasible.\n", SCIPconsGetName(conss[c])); 1872 } 1873 } 1874 } 1875 } 1876 } 1877 1878 return SCIP_OKAY; 1879 } 1880 1881 1882 /** domain propagation method of constraint handler */ 1883 static 1884 SCIP_DECL_CONSPROP(consPropSOS2) 1885 { /*lint --e{715}*/ 1886 int c; 1887 int ngen = 0; 1888 1889 assert( scip != NULL ); 1890 assert( conshdlr != NULL ); 1891 assert( conss != NULL ); 1892 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1893 assert( result != NULL ); 1894 *result = SCIP_DIDNOTRUN; 1895 1896 assert( SCIPisTransformed(scip) ); 1897 1898 /* check each constraint */ 1899 for (c = 0; c < nconss; ++c) 1900 { 1901 SCIP_CONS* cons; 1902 SCIP_CONSDATA* consdata; 1903 SCIP_Bool cutoff; 1904 1905 assert( conss[c] != NULL ); 1906 cons = conss[c]; 1907 consdata = SCIPconsGetData(cons); 1908 assert( consdata != NULL ); 1909 SCIPdebugMsg(scip, "Propagating SOS2 constraint <%s>.\n", SCIPconsGetName(cons) ); 1910 1911 *result = SCIP_DIDNOTFIND; 1912 SCIP_CALL( propSOS2(scip, cons, consdata, &cutoff, &ngen) ); 1913 if ( cutoff ) 1914 { 1915 *result = SCIP_CUTOFF; 1916 return SCIP_OKAY; 1917 } 1918 } 1919 SCIPdebugMsg(scip, "Propagated %d domains.\n", ngen); 1920 if ( ngen > 0 ) 1921 *result = SCIP_REDUCEDDOM; 1922 1923 return SCIP_OKAY; 1924 } 1925 1926 1927 /** propagation conflict resolving method of constraint handler 1928 * 1929 * We check which bound changes were the reason for infeasibility. We 1930 * use that @a inferinfo stores the index of the variable that has 1931 * bounds that fix it to be nonzero (these bounds are the reason). */ 1932 static 1933 SCIP_DECL_CONSRESPROP(consRespropSOS2) 1934 { /*lint --e{715}*/ 1935 SCIP_CONSDATA* consdata; 1936 SCIP_VAR* var; 1937 1938 assert( scip != NULL ); 1939 assert( cons != NULL ); 1940 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1941 assert( infervar != NULL ); 1942 assert( bdchgidx != NULL ); 1943 assert( result != NULL ); 1944 1945 *result = SCIP_DIDNOTFIND; 1946 SCIPdebugMsg(scip, "Propagation resolution method of SOS2 constraint <%s>.\n", SCIPconsGetName(cons)); 1947 1948 consdata = SCIPconsGetData(cons); 1949 assert( consdata != NULL ); 1950 assert( 0 <= inferinfo && inferinfo < consdata->nvars ); 1951 var = consdata->vars[inferinfo]; 1952 assert( var != infervar ); 1953 1954 /* check if lower bound of var was the reason */ 1955 if ( SCIPisFeasPositive(scip, SCIPgetVarLbAtIndex(scip, var, bdchgidx, FALSE)) ) 1956 { 1957 SCIP_CALL( SCIPaddConflictLb(scip, var, bdchgidx) ); 1958 *result = SCIP_SUCCESS; 1959 } 1960 1961 /* check if upper bound of var was the reason */ 1962 if ( SCIPisFeasNegative(scip, SCIPgetVarUbAtIndex(scip, var, bdchgidx, FALSE)) ) 1963 { 1964 SCIP_CALL( SCIPaddConflictUb(scip, var, bdchgidx) ); 1965 *result = SCIP_SUCCESS; 1966 } 1967 1968 return SCIP_OKAY; 1969 } 1970 1971 1972 /** variable rounding lock method of constraint handler 1973 * 1974 * Let lb and ub be the lower and upper bounds of a 1975 * variable. Preprocessing usually makes sure that lb <= 0 <= ub. 1976 * 1977 * - If lb < 0 then rounding down may violate the constraint. 1978 * - If ub > 0 then rounding up may violated the constraint. 1979 * - If lb > 0 or ub < 0 then the constraint is infeasible and we do 1980 * not have to deal with it here. 1981 * - If lb == 0 then rounding down does not violate the constraint. 1982 * - If ub == 0 then rounding up does not violate the constraint. 1983 */ 1984 static 1985 SCIP_DECL_CONSLOCK(consLockSOS2) 1986 { 1987 SCIP_CONSDATA* consdata; 1988 SCIP_VAR** vars; 1989 int nvars; 1990 int j; 1991 1992 assert( scip != NULL ); 1993 assert( conshdlr != NULL ); 1994 assert( cons != NULL ); 1995 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1996 assert(locktype == SCIP_LOCKTYPE_MODEL); 1997 1998 consdata = SCIPconsGetData(cons); 1999 assert( consdata != NULL ); 2000 2001 SCIPdebugMsg(scip, "Locking constraint <%s>.\n", SCIPconsGetName(cons)); 2002 2003 vars = consdata->vars; 2004 nvars = consdata->nvars; 2005 assert( vars != NULL ); 2006 2007 for (j = 0; j < nvars; ++j) 2008 { 2009 SCIP_VAR* var; 2010 var = vars[j]; 2011 2012 /* if lower bound is negative, rounding down may violate constraint */ 2013 if ( SCIPisFeasNegative(scip, SCIPvarGetLbGlobal(var)) ) 2014 SCIP_CALL( SCIPaddVarLocksType(scip, var, locktype, nlockspos, nlocksneg) ); 2015 2016 /* additionally: if upper bound is positive, rounding up may violate constraint */ 2017 if ( SCIPisFeasPositive(scip, SCIPvarGetUbGlobal(var)) ) 2018 SCIP_CALL( SCIPaddVarLocksType(scip, var, locktype, nlocksneg, nlockspos) ); 2019 } 2020 2021 return SCIP_OKAY; 2022 } 2023 2024 2025 /** constraint display method of constraint handler */ 2026 static 2027 SCIP_DECL_CONSPRINT(consPrintSOS2) 2028 { /*lint --e{715}*/ 2029 SCIP_CONSDATA* consdata; 2030 int j; 2031 2032 assert( scip != NULL ); 2033 assert( conshdlr != NULL ); 2034 assert( cons != NULL ); 2035 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 2036 2037 consdata = SCIPconsGetData(cons); 2038 assert( consdata != NULL ); 2039 2040 for (j = 0; j < consdata->nvars; ++j) 2041 { 2042 if ( j > 0 ) 2043 SCIPinfoMessage(scip, file, ", "); 2044 SCIP_CALL( SCIPwriteVarName(scip, file, consdata->vars[j], FALSE) ); 2045 if ( consdata->weights == NULL ) 2046 SCIPinfoMessage(scip, file, " (%d)", j+1); 2047 else 2048 SCIPinfoMessage(scip, file, " (%3.2f)", consdata->weights[j]); 2049 } 2050 2051 return SCIP_OKAY; 2052 } 2053 2054 2055 /** constraint copying method of constraint handler */ 2056 static 2057 SCIP_DECL_CONSCOPY(consCopySOS2) 2058 { /*lint --e{715}*/ 2059 SCIP_CONSDATA* sourceconsdata; 2060 SCIP_VAR** sourcevars; 2061 SCIP_VAR** targetvars; 2062 SCIP_Real* targetweights = NULL; 2063 const char* consname; 2064 int nvars; 2065 int v; 2066 2067 assert( scip != NULL ); 2068 assert( sourcescip != NULL ); 2069 assert( sourcecons != NULL ); 2070 assert( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(sourcecons)), CONSHDLR_NAME) == 0 ); 2071 assert( valid != NULL ); 2072 2073 *valid = TRUE; 2074 2075 if ( name != NULL ) 2076 consname = name; 2077 else 2078 consname = SCIPconsGetName(sourcecons); 2079 2080 SCIPdebugMsg(scip, "Copying SOS2 constraint <%s> ...\n", consname); 2081 2082 sourceconsdata = SCIPconsGetData(sourcecons); 2083 assert( sourceconsdata != NULL ); 2084 2085 /* get variables and weights of the source constraint */ 2086 nvars = sourceconsdata->nvars; 2087 assert( nvars >= 0 ); 2088 2089 /* duplicate weights array */ 2090 if ( sourceconsdata->weights != NULL ) 2091 { 2092 SCIP_CALL( SCIPduplicateBufferArray(sourcescip, &targetweights, sourceconsdata->weights, nvars) ); 2093 } 2094 2095 /* get copied variables in target SCIP */ 2096 sourcevars = sourceconsdata->vars; 2097 SCIP_CALL( SCIPallocBufferArray(sourcescip, &targetvars, nvars) ); 2098 for (v = 0; v < nvars && *valid; ++v) 2099 { 2100 assert( sourcevars != NULL ); 2101 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &(targetvars[v]), varmap, consmap, global, valid) ); 2102 } 2103 2104 /* only create the target constraint, if all variables could be copied */ 2105 if( *valid ) 2106 { 2107 SCIP_CALL( SCIPcreateConsSOS2(scip, cons, consname, nvars, targetvars, targetweights, 2108 initial, separate, enforce, check, propagate, local, dynamic, removable, stickingatnode) ); 2109 } 2110 2111 /* free buffer array */ 2112 SCIPfreeBufferArray(sourcescip, &targetvars); 2113 SCIPfreeBufferArrayNull(sourcescip, &targetweights); 2114 2115 return SCIP_OKAY; 2116 } 2117 2118 2119 /** constraint parsing method of constraint handler */ 2120 static 2121 SCIP_DECL_CONSPARSE(consParseSOS2) 2122 { /*lint --e{715}*/ 2123 SCIP_VAR* var; 2124 SCIP_Real weight; 2125 const char* s; 2126 char* t; 2127 2128 *success = TRUE; 2129 s = str; 2130 2131 /* create empty SOS2 constraint */ 2132 SCIP_CALL( SCIPcreateConsSOS2(scip, cons, name, 0, NULL, NULL, initial, separate, enforce, check, propagate, local, dynamic, removable, stickingatnode) ); 2133 2134 /* loop through string */ 2135 while( *s != '\0' ) 2136 { 2137 /* parse variable name */ 2138 SCIP_CALL( SCIPparseVarName(scip, s, &var, &t) ); 2139 2140 if( var == NULL ) 2141 break; 2142 2143 /* skip until beginning of weight */ 2144 t = strchr(t, '('); 2145 2146 if( t == NULL ) 2147 { 2148 SCIPerrorMessage("Syntax error: expected opening '(' at input: %s\n", s); 2149 *success = FALSE; 2150 break; 2151 } 2152 2153 s = t; 2154 2155 /* skip '(' */ 2156 ++s; 2157 2158 /* find weight */ 2159 weight = strtod(s, &t); 2160 2161 if( t == NULL ) 2162 { 2163 SCIPerrorMessage("Syntax error during parsing of the weight: %s\n", s); 2164 *success = FALSE; 2165 break; 2166 } 2167 2168 s = t; 2169 2170 /* skip until ending of weight */ 2171 t = strchr(t, ')'); 2172 2173 if( t == NULL ) 2174 { 2175 SCIPerrorMessage("Syntax error: expected closing ')' at input %s\n", s); 2176 *success = FALSE; 2177 break; 2178 } 2179 2180 s = t; 2181 2182 /* skip ')' */ 2183 ++s; 2184 2185 /* skip white space */ 2186 SCIP_CALL( SCIPskipSpace((char**)&s) ); 2187 2188 /* skip ',' */ 2189 if( *s == ',' ) 2190 ++s; 2191 2192 /* add variable */ 2193 SCIP_CALL( SCIPaddVarSOS2(scip, *cons, var, weight) ); 2194 } 2195 2196 if( !*success ) 2197 SCIP_CALL( SCIPreleaseCons(scip, cons) ); 2198 2199 return SCIP_OKAY; 2200 } 2201 2202 2203 /** constraint method of constraint handler which returns the variables (if possible) */ 2204 static 2205 SCIP_DECL_CONSGETVARS(consGetVarsSOS2) 2206 { /*lint --e{715}*/ 2207 SCIP_CONSDATA* consdata; 2208 2209 consdata = SCIPconsGetData(cons); 2210 assert(consdata != NULL); 2211 2212 if( varssize < consdata->nvars ) 2213 (*success) = FALSE; 2214 else 2215 { 2216 assert(vars != NULL); 2217 2218 BMScopyMemoryArray(vars, consdata->vars, consdata->nvars); 2219 (*success) = TRUE; 2220 } 2221 2222 return SCIP_OKAY; 2223 } 2224 2225 2226 /** constraint method of constraint handler which returns the number of variables (if possible) */ 2227 static 2228 SCIP_DECL_CONSGETNVARS(consGetNVarsSOS2) 2229 { /*lint --e{715}*/ 2230 SCIP_CONSDATA* consdata; 2231 2232 consdata = SCIPconsGetData(cons); 2233 assert(consdata != NULL); 2234 2235 (*nvars) = consdata->nvars; 2236 (*success) = TRUE; 2237 2238 return SCIP_OKAY; 2239 } 2240 2241 2242 /** constraint handler method which returns the permutation symmetry detection graph of a constraint */ 2243 static 2244 SCIP_DECL_CONSGETPERMSYMGRAPH(consGetPermsymGraphSOS2) 2245 { /*lint --e{715}*/ 2246 SCIP_CONSDATA* consdata; 2247 SCIP_VAR** consvars; 2248 SCIP_VAR** locvars; 2249 SCIP_Real* locvals; 2250 SCIP_Real constant = 0.0; 2251 int consnodeidx; 2252 int opnodeidx; 2253 int nodeidx; 2254 int nconsvars; 2255 int nlocvars; 2256 int nvars; 2257 int i; 2258 int j; 2259 2260 consdata = SCIPconsGetData(cons); 2261 assert(consdata != NULL); 2262 2263 /* get active variables of the constraint */ 2264 nvars = SCIPgetNVars(scip); 2265 nconsvars = consdata->nvars; 2266 consvars = SCIPgetVarsSOS2(scip, cons); 2267 assert(consvars != NULL); 2268 2269 SCIP_CALL( SCIPallocBufferArray(scip, &locvars, nvars) ); 2270 SCIP_CALL( SCIPallocBufferArray(scip, &locvals, nvars) ); 2271 2272 /* add node initializing constraint (with artificial rhs) */ 2273 SCIP_CALL( SCIPaddSymgraphConsnode(scip, graph, cons, 0.0, 0.0, &consnodeidx) ); 2274 2275 /* for all pairs of variables, add a node indicating a tuple and add nodes for (aggregated) variables */ 2276 for( i = 0; i < nconsvars - 1; ++i ) 2277 { 2278 SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, (int) SYM_CONSOPTYPE_SOS2_TUPLE, &opnodeidx) ); /*lint !e641*/ 2279 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, consnodeidx, opnodeidx, FALSE, 0.0) ); 2280 2281 for( j = i; j < i + 2; ++j ) 2282 { 2283 locvars[0] = consvars[j]; 2284 locvals[0] = 1.0; 2285 constant = 0.0; 2286 nlocvars = 1; 2287 2288 /* ignore weights of SOS2 constraint (variables are sorted according to these weights) */ 2289 SCIP_CALL( SCIPgetActiveVariables(scip, SYM_SYMTYPE_PERM, &locvars, &locvals, 2290 &nlocvars, &constant, SCIPisTransformed(scip)) ); 2291 2292 if( nlocvars == 1 && SCIPisZero(scip, constant) && SCIPisEQ(scip, locvals[0], 1.0) ) 2293 { 2294 nodeidx = SCIPgetSymgraphVarnodeidx(scip, graph, locvars[0]); 2295 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, opnodeidx, nodeidx, FALSE, 0.0) ); 2296 } 2297 else 2298 { 2299 SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, (int) SYM_CONSOPTYPE_SUM, &nodeidx) ); /*lint !e641*/ 2300 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, opnodeidx, nodeidx, FALSE, 0.0) ); 2301 SCIP_CALL( SCIPaddSymgraphVarAggegration(scip, graph, nodeidx, locvars, locvals, nlocvars, constant) ); 2302 } 2303 } 2304 } 2305 2306 SCIPfreeBufferArray(scip, &locvals); 2307 SCIPfreeBufferArray(scip, &locvars); 2308 2309 return SCIP_OKAY; 2310 } 2311 2312 2313 /** constraint handler method which returns the signed permutation symmetry detection graph of a constraint */ 2314 static 2315 SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(consGetSignedPermsymGraphSOS2) 2316 { /*lint --e{715}*/ 2317 SCIP_CONSDATA* consdata; 2318 SCIP_VAR** consvars; 2319 SCIP_VAR** locvars; 2320 SCIP_Real* locvals; 2321 SCIP_Real constant = 0.0; 2322 int consnodeidx; 2323 int opnodeidx; 2324 int nodeidx; 2325 int nconsvars; 2326 int nlocvars; 2327 int nvars; 2328 int i; 2329 int j; 2330 2331 consdata = SCIPconsGetData(cons); 2332 assert(consdata != NULL); 2333 2334 /* get active variables of the constraint */ 2335 nvars = SCIPgetNVars(scip); 2336 nconsvars = consdata->nvars; 2337 consvars = SCIPgetVarsSOS2(scip, cons); 2338 assert(consvars != NULL); 2339 2340 SCIP_CALL( SCIPallocBufferArray(scip, &locvars, nvars) ); 2341 SCIP_CALL( SCIPallocBufferArray(scip, &locvals, nvars) ); 2342 2343 /* add node initializing constraint (with artificial rhs) */ 2344 SCIP_CALL( SCIPaddSymgraphConsnode(scip, graph, cons, 0.0, 0.0, &consnodeidx) ); 2345 2346 /* for all pairs of variables, add a node indicating a tuple and add nodes for (aggregated) variables */ 2347 for( i = 0; i < nconsvars - 1; ++i ) 2348 { 2349 SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, (int) SYM_CONSOPTYPE_SOS2_TUPLE, &opnodeidx) ); /*lint !e641*/ 2350 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, consnodeidx, opnodeidx, FALSE, 0.0) ); 2351 2352 for( j = i; j < i + 2; ++j ) 2353 { 2354 locvars[0] = consvars[j]; 2355 locvals[0] = 1.0; 2356 constant = 0.0; 2357 nlocvars = 1; 2358 2359 /* ignore weights of SOS2 constraint (variables are sorted according to these weights) */ 2360 2361 /* use SYM_SYMTYPE_PERM here to NOT center variable domains at 0, as the latter might not preserve 2362 * SOS1 constraints */ 2363 SCIP_CALL( SCIPgetActiveVariables(scip, SYM_SYMTYPE_PERM, &locvars, &locvals, 2364 &nlocvars, &constant, SCIPisTransformed(scip)) ); 2365 2366 if( nlocvars == 1 && SCIPisZero(scip, constant) && SCIPisEQ(scip, locvals[0], 1.0) ) 2367 { 2368 SCIP_Bool allownegation = FALSE; 2369 2370 /* a negation is allowed if it is centered around 0 */ 2371 if ( SCIPisInfinity(scip, -SCIPvarGetLbGlobal(locvars[0])) == SCIPisInfinity(scip, SCIPvarGetUbGlobal(locvars[0])) 2372 && (SCIPisInfinity(scip, SCIPvarGetUbGlobal(locvars[0])) 2373 || SCIPisZero(scip, (SCIPvarGetLbGlobal(locvars[0]) + SCIPvarGetUbGlobal(locvars[0]))/2)) ) 2374 allownegation = TRUE; 2375 2376 nodeidx = SCIPgetSymgraphVarnodeidx(scip, graph, locvars[0]); 2377 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, opnodeidx, nodeidx, TRUE, 1.0) ); 2378 2379 nodeidx = SCIPgetSymgraphNegatedVarnodeidx(scip, graph, locvars[0]); 2380 if( allownegation ) 2381 { 2382 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, opnodeidx, nodeidx, TRUE, 1.0) ); 2383 } 2384 else 2385 { 2386 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, opnodeidx, nodeidx, TRUE, -1.0) ); 2387 } 2388 } 2389 else 2390 { 2391 int sumnodeidx; 2392 int k; 2393 2394 SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, (int) SYM_CONSOPTYPE_SUM, &sumnodeidx) ); /*lint !e641*/ 2395 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, consnodeidx, sumnodeidx, FALSE, 0.0) ); 2396 2397 /* add nodes and edges for variables in aggregation, do not add edges to negated variables 2398 * since this might not necessarily be a symmetry of the SOS1 constraint; therefore, 2399 * do not use SCIPaddSymgraphVarAggegration() */ 2400 for( k = 0; k < nlocvars; ++k ) 2401 { 2402 nodeidx = SCIPgetSymgraphVarnodeidx(scip, graph, locvars[k]); 2403 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, sumnodeidx, nodeidx, TRUE, locvals[k]) ); 2404 } 2405 2406 /* possibly add node for constant */ 2407 if( ! SCIPisZero(scip, constant) ) 2408 { 2409 SCIP_CALL( SCIPaddSymgraphValnode(scip, graph, constant, &nodeidx) ); 2410 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, sumnodeidx, nodeidx, FALSE, 0.0) ); 2411 } 2412 } 2413 } 2414 } 2415 2416 SCIPfreeBufferArray(scip, &locvals); 2417 SCIPfreeBufferArray(scip, &locvars); 2418 2419 return SCIP_OKAY; 2420 } 2421 2422 2423 /* ---------------- Callback methods of event handler ---------------- */ 2424 2425 /** exec the event handler 2426 * 2427 * We update the number of variables fixed to be nonzero 2428 */ 2429 static 2430 SCIP_DECL_EVENTEXEC(eventExecSOS2) 2431 { 2432 SCIP_EVENTTYPE eventtype; 2433 SCIP_CONS* cons; 2434 SCIP_CONSDATA* consdata; 2435 SCIP_VAR* var; 2436 SCIP_Real oldbound, newbound; 2437 2438 assert( eventhdlr != NULL ); 2439 assert( eventdata != NULL ); 2440 assert( strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0 ); 2441 assert( event != NULL ); 2442 2443 cons = (SCIP_CONS*)eventdata; 2444 assert( cons != NULL ); 2445 consdata = SCIPconsGetData(cons); 2446 assert( consdata != NULL ); 2447 assert( 0 <= consdata->nfixednonzeros && consdata->nfixednonzeros <= consdata->nvars ); 2448 2449 oldbound = SCIPeventGetOldbound(event); 2450 newbound = SCIPeventGetNewbound(event); 2451 2452 eventtype = SCIPeventGetType(event); 2453 switch ( eventtype ) 2454 { 2455 case SCIP_EVENTTYPE_LBTIGHTENED: 2456 /* if variable is now fixed to be nonzero */ 2457 if ( ! SCIPisFeasPositive(scip, oldbound) && SCIPisFeasPositive(scip, newbound) ) 2458 ++(consdata->nfixednonzeros); 2459 break; 2460 case SCIP_EVENTTYPE_UBTIGHTENED: 2461 /* if variable is now fixed to be nonzero */ 2462 if ( ! SCIPisFeasNegative(scip, oldbound) && SCIPisFeasNegative(scip, newbound) ) 2463 ++(consdata->nfixednonzeros); 2464 break; 2465 case SCIP_EVENTTYPE_LBRELAXED: 2466 /* if variable is not fixed to be nonzero anymore */ 2467 if ( SCIPisFeasPositive(scip, oldbound) && ! SCIPisFeasPositive(scip, newbound) ) 2468 --(consdata->nfixednonzeros); 2469 break; 2470 case SCIP_EVENTTYPE_UBRELAXED: 2471 /* if variable is not fixed to be nonzero anymore */ 2472 if ( SCIPisFeasNegative(scip, oldbound) && ! SCIPisFeasNegative(scip, newbound) ) 2473 --(consdata->nfixednonzeros); 2474 break; 2475 case SCIP_EVENTTYPE_GLBCHANGED: 2476 var = SCIPeventGetVar(event); 2477 assert(var != NULL); 2478 2479 /* global lower bound is not negative anymore -> remove down lock */ 2480 if ( SCIPisFeasNegative(scip, oldbound) && ! SCIPisFeasNegative(scip, newbound) ) 2481 SCIP_CALL( SCIPunlockVarCons(scip, var, cons, TRUE, FALSE) ); 2482 /* global lower bound turned negative -> add down lock */ 2483 else if ( ! SCIPisFeasNegative(scip, oldbound) && SCIPisFeasNegative(scip, newbound) ) 2484 SCIP_CALL( SCIPlockVarCons(scip, var, cons, TRUE, FALSE) ); 2485 break; 2486 case SCIP_EVENTTYPE_GUBCHANGED: 2487 var = SCIPeventGetVar(event); 2488 assert(var != NULL); 2489 2490 /* global upper bound is not positive anymore -> remove up lock */ 2491 if ( SCIPisFeasPositive(scip, oldbound) && ! SCIPisFeasPositive(scip, newbound) ) 2492 SCIP_CALL( SCIPunlockVarCons(scip, var, cons, FALSE, TRUE) ); 2493 /* global upper bound turned positive -> add up lock */ 2494 else if ( ! SCIPisFeasPositive(scip, oldbound) && SCIPisFeasPositive(scip, newbound) ) 2495 SCIP_CALL( SCIPlockVarCons(scip, var, cons, FALSE, TRUE) ); 2496 break; 2497 default: 2498 SCIPerrorMessage("invalid event type.\n"); 2499 return SCIP_INVALIDDATA; 2500 } 2501 assert( 0 <= consdata->nfixednonzeros && consdata->nfixednonzeros <= consdata->nvars ); 2502 2503 SCIPdebugMsg(scip, "changed bound of variable <%s> from %f to %f (nfixednonzeros: %d).\n", SCIPvarGetName(SCIPeventGetVar(event)), 2504 oldbound, newbound, consdata->nfixednonzeros); 2505 2506 return SCIP_OKAY; 2507 } 2508 2509 2510 /* ---------------- Constraint specific interface methods ---------------- */ 2511 2512 /** creates the handler for SOS2 constraints and includes it in SCIP */ 2513 SCIP_RETCODE SCIPincludeConshdlrSOS2( 2514 SCIP* scip /**< SCIP data structure */ 2515 ) 2516 { 2517 SCIP_CONSHDLRDATA* conshdlrdata; 2518 SCIP_CONSHDLR* conshdlr; 2519 2520 /* create constraint handler data */ 2521 SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) ); 2522 2523 conshdlrdata->eventhdlr = NULL; 2524 /* create event handler for bound change events */ 2525 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &(conshdlrdata->eventhdlr), EVENTHDLR_NAME, EVENTHDLR_DESC, 2526 eventExecSOS2, NULL) ); 2527 if ( conshdlrdata->eventhdlr == NULL ) 2528 { 2529 SCIPerrorMessage("event handler for SOS2 constraints not found.\n"); 2530 return SCIP_PLUGINNOTFOUND; 2531 } 2532 2533 /* include constraint handler */ 2534 SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC, 2535 CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY, CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS, 2536 consEnfolpSOS2, consEnfopsSOS2, consCheckSOS2, consLockSOS2, conshdlrdata) ); 2537 assert(conshdlr != NULL); 2538 2539 /* set non-fundamental callbacks via specific setter functions */ 2540 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopySOS2, consCopySOS2) ); 2541 SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteSOS2) ); 2542 SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolSOS2) ); 2543 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeSOS2) ); 2544 SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsSOS2) ); 2545 SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsSOS2) ); 2546 SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpSOS2) ); 2547 SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseSOS2) ); 2548 SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolSOS2, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) ); 2549 SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintSOS2) ); 2550 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropSOS2, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP, CONSHDLR_PROP_TIMING) ); 2551 SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropSOS2) ); 2552 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpSOS2, consSepasolSOS2, CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, CONSHDLR_DELAYSEPA) ); 2553 SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransSOS2) ); 2554 SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxSOS2) ); 2555 SCIP_CALL( SCIPsetConshdlrGetPermsymGraph(scip, conshdlr, consGetPermsymGraphSOS2) ); 2556 SCIP_CALL( SCIPsetConshdlrGetSignedPermsymGraph(scip, conshdlr, consGetSignedPermsymGraphSOS2) ); 2557 2558 return SCIP_OKAY; 2559 } 2560 2561 2562 /** creates and captures a SOS2 constraint 2563 * 2564 * We set the constraint to not be modifable. If the weights are non 2565 * NULL, the variables are ordered according to these weights (in 2566 * ascending order). 2567 * 2568 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 2569 */ 2570 SCIP_RETCODE SCIPcreateConsSOS2( 2571 SCIP* scip, /**< SCIP data structure */ 2572 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 2573 const char* name, /**< name of constraint */ 2574 int nvars, /**< number of variables in the constraint */ 2575 SCIP_VAR** vars, /**< array with variables of constraint entries */ 2576 SCIP_Real* weights, /**< weights determining the variable order, or NULL if natural order should be used */ 2577 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? 2578 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */ 2579 SCIP_Bool separate, /**< should the constraint be separated during LP processing? 2580 * Usually set to TRUE. */ 2581 SCIP_Bool enforce, /**< should the constraint be enforced during node processing? 2582 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 2583 SCIP_Bool check, /**< should the constraint be checked for feasibility? 2584 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 2585 SCIP_Bool propagate, /**< should the constraint be propagated during node processing? 2586 * Usually set to TRUE. */ 2587 SCIP_Bool local, /**< is constraint only valid locally? 2588 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */ 2589 SCIP_Bool dynamic, /**< is constraint subject to aging? 2590 * Usually set to FALSE. Set to TRUE for own cuts which 2591 * are separated as constraints. */ 2592 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? 2593 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */ 2594 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even 2595 * if it may be moved to a more global node? 2596 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */ 2597 ) 2598 { 2599 SCIP_CONSHDLR* conshdlr; 2600 SCIP_CONSDATA* consdata; 2601 SCIP_Bool modifiable; 2602 2603 modifiable = FALSE; 2604 2605 /* find the SOS2 constraint handler */ 2606 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME); 2607 if ( conshdlr == NULL ) 2608 { 2609 SCIPerrorMessage("<%s> constraint handler not found\n", CONSHDLR_NAME); 2610 return SCIP_PLUGINNOTFOUND; 2611 } 2612 2613 /* create constraint data */ 2614 SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) ); 2615 consdata->vars = NULL; 2616 consdata->nvars = nvars; 2617 consdata->maxvars = nvars; 2618 consdata->row = NULL; 2619 consdata->nfixednonzeros = -1; 2620 consdata->weights = NULL; 2621 if ( nvars > 0 ) 2622 { 2623 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->vars, vars, nvars) ); 2624 2625 /* check weights */ 2626 if ( weights != NULL ) 2627 { 2628 /* store weights */ 2629 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->weights, weights, nvars) ); 2630 2631 /* sort variables - ascending order */ 2632 SCIPsortRealPtr(consdata->weights, (void**)consdata->vars, nvars); 2633 } 2634 } 2635 else 2636 assert( weights == NULL ); 2637 2638 /* create constraint */ 2639 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate, 2640 local, modifiable, dynamic, removable, stickingatnode) ); 2641 2642 return SCIP_OKAY; 2643 } 2644 2645 2646 /** creates and captures a SOS2 constraint with all constraint flags set to their default values. 2647 * 2648 * @warning Do NOT set the constraint to be modifiable manually, because this might lead 2649 * to wrong results as the variable array will not be resorted 2650 * 2651 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 2652 */ 2653 SCIP_RETCODE SCIPcreateConsBasicSOS2( 2654 SCIP* scip, /**< SCIP data structure */ 2655 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 2656 const char* name, /**< name of constraint */ 2657 int nvars, /**< number of variables in the constraint */ 2658 SCIP_VAR** vars, /**< array with variables of constraint entries */ 2659 SCIP_Real* weights /**< weights determining the variable order, or NULL if natural order should be used */ 2660 ) 2661 { 2662 SCIP_CALL( SCIPcreateConsSOS2( scip, cons, name, nvars, vars, weights, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 2663 2664 return SCIP_OKAY; 2665 } 2666 2667 2668 /** adds variable to SOS2 constraint, the position is determined by the given weight */ 2669 SCIP_RETCODE SCIPaddVarSOS2( 2670 SCIP* scip, /**< SCIP data structure */ 2671 SCIP_CONS* cons, /**< constraint */ 2672 SCIP_VAR* var, /**< variable to add to the constraint */ 2673 SCIP_Real weight /**< weight determining position of variable */ 2674 ) 2675 { 2676 assert( scip != NULL ); 2677 assert( var != NULL ); 2678 assert( cons != NULL ); 2679 2680 SCIPdebugMsg(scip, "adding variable <%s> to constraint <%s> with weight %g\n", SCIPvarGetName(var), SCIPconsGetName(cons), weight); 2681 2682 if ( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 ) 2683 { 2684 SCIPerrorMessage("constraint is not an SOS2 constraint.\n"); 2685 return SCIP_INVALIDDATA; 2686 } 2687 2688 SCIP_CALL( addVarSOS2(scip, cons, var, weight) ); 2689 2690 return SCIP_OKAY; 2691 } 2692 2693 2694 /** appends variable to SOS2 constraint */ 2695 SCIP_RETCODE SCIPappendVarSOS2( 2696 SCIP* scip, /**< SCIP data structure */ 2697 SCIP_CONS* cons, /**< constraint */ 2698 SCIP_VAR* var /**< variable to add to the constraint */ 2699 ) 2700 { 2701 assert( scip != NULL ); 2702 assert( var != NULL ); 2703 assert( cons != NULL ); 2704 2705 SCIPdebugMsg(scip, "appending variable <%s> to constraint <%s>\n", SCIPvarGetName(var), SCIPconsGetName(cons)); 2706 2707 if ( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 ) 2708 { 2709 SCIPerrorMessage("constraint is not an SOS2 constraint.\n"); 2710 return SCIP_INVALIDDATA; 2711 } 2712 2713 SCIP_CALL( appendVarSOS2(scip, cons, var) ); 2714 2715 return SCIP_OKAY; 2716 } 2717 2718 2719 /** gets number of variables in SOS2 constraint */ 2720 int SCIPgetNVarsSOS2( 2721 SCIP* scip, /**< SCIP data structure */ 2722 SCIP_CONS* cons /**< constraint */ 2723 ) 2724 { 2725 SCIP_CONSDATA* consdata; 2726 2727 assert( scip != NULL ); 2728 assert( cons != NULL ); 2729 2730 if ( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 ) 2731 { 2732 SCIPerrorMessage("constraint is not an SOS2 constraint.\n"); 2733 SCIPABORT(); 2734 return -1; /*lint !e527*/ 2735 } 2736 2737 consdata = SCIPconsGetData(cons); 2738 assert( consdata != NULL ); 2739 2740 return consdata->nvars; 2741 } 2742 2743 2744 /** gets array of variables in SOS2 constraint */ 2745 SCIP_VAR** SCIPgetVarsSOS2( 2746 SCIP* scip, /**< SCIP data structure */ 2747 SCIP_CONS* cons /**< constraint data */ 2748 ) 2749 { 2750 SCIP_CONSDATA* consdata; 2751 2752 assert( scip != NULL ); 2753 assert( cons != NULL ); 2754 2755 if ( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 ) 2756 { 2757 SCIPerrorMessage("constraint is not an SOS2 constraint.\n"); 2758 SCIPABORT(); 2759 return NULL; /*lint !e527*/ 2760 } 2761 2762 consdata = SCIPconsGetData(cons); 2763 assert( consdata != NULL ); 2764 2765 return consdata->vars; 2766 } 2767 2768 2769 /** gets array of weights in SOS2 constraint (or NULL if not existent) */ 2770 SCIP_Real* SCIPgetWeightsSOS2( 2771 SCIP* scip, /**< SCIP data structure */ 2772 SCIP_CONS* cons /**< constraint data */ 2773 ) 2774 { 2775 SCIP_CONSDATA* consdata; 2776 2777 assert( scip != NULL ); 2778 assert( cons != NULL ); 2779 2780 if ( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 ) 2781 { 2782 SCIPerrorMessage("constraint is not an SOS2 constraint.\n"); 2783 SCIPABORT(); 2784 return NULL; /*lint !e527*/ 2785 } 2786 2787 consdata = SCIPconsGetData(cons); 2788 assert( consdata != NULL ); 2789 2790 return consdata->weights; 2791 } 2792