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_superindicator.c 26 * @ingroup DEFPLUGINS_CONS 27 * @brief constraint handler for indicator constraints over arbitrary constraint types 28 * @author Ambros Gleixner 29 * @author Frederic Pythoud 30 */ 31 32 /**@todo allow more types for slack constraint */ 33 /**@todo implement more upgrades, e.g., for nonlinear, quadratic, logicor slack constraints; upgrades could also help to 34 * handle difficult slack constraints such as pseudoboolean or indicator 35 */ 36 /**@todo unify enfolp and enfops, sepalp and sepaps callbacks */ 37 /**@todo enforce by branching on binary variable if slack constraint only returns SCIP_INFEASIBLE */ 38 /**@todo consider enforcing by adding slack constraint (or copy of it) locally if binary variable is fixed to 1 39 * (some constraint handler cannot enforce constraints that are not active) 40 */ 41 42 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 43 44 #include "blockmemshell/memory.h" 45 #include "scip/cons_indicator.h" 46 #include "scip/cons_linear.h" 47 #include "scip/cons_superindicator.h" 48 #include "scip/dialog_default.h" 49 #include "scip/pub_cons.h" 50 #include "scip/pub_dialog.h" 51 #include "scip/pub_heur.h" 52 #include "scip/pub_message.h" 53 #include "scip/pub_misc.h" 54 #include "scip/pub_sol.h" 55 #include "scip/pub_var.h" 56 #include "scip/scip_conflict.h" 57 #include "scip/scip_cons.h" 58 #include "scip/scip_copy.h" 59 #include "scip/scip_dialog.h" 60 #include "scip/scip_general.h" 61 #include "scip/scip_mem.h" 62 #include "scip/scip_message.h" 63 #include "scip/scip_numerics.h" 64 #include "scip/scip_param.h" 65 #include "scip/scip_prob.h" 66 #include "scip/scip_sol.h" 67 #include "scip/scip_var.h" 68 #include <string.h> 69 70 /* constraint handler properties */ 71 #define CONSHDLR_NAME "superindicator" 72 #define CONSHDLR_DESC "constraint handler for indicator constraints over arbitrary constraint types" 73 #define CONSHDLR_SEPAPRIORITY 0 /**< priority of the constraint handler for separation */ 74 #define CONSHDLR_ENFOPRIORITY -5000000 /**< priority of the constraint handler for constraint enforcing */ 75 #define CONSHDLR_CHECKPRIORITY -5000000 /**< priority of the constraint handler for checking feasibility */ 76 #define CONSHDLR_SEPAFREQ -1 /**< frequency for separating cuts; zero means to separate only in the root node */ 77 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */ 78 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation, 79 * propagation and enforcement, -1 for no eager evaluations, 0 for first only */ 80 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler 81 * participates in (-1: no limit) */ 82 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */ 83 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */ 84 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */ 85 86 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP /**< propagation timing mask of the constraint handler */ 87 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */ 88 89 #define DEFAULT_CHECKSLACKTYPE TRUE /**< should type of slack constraint be checked when creating superindicator constraint? */ 90 #define DEFAULT_UPGDPRIOINDICATOR 1 /**< priority for upgrading to an indicator constraint (-1: never) */ 91 #define DEFAULT_UPGDPRIOLINEAR 2 /**< priority for upgrading to a linear constraint (-1: never) */ 92 #define DEFAULT_MAXUPGDCOEFLINEAR 1e4 /**< maximum big-M coefficient of binary variable in upgrade to a linear constraint 93 * (relative to smallest coefficient) */ 94 95 96 /* 97 * Data structures 98 */ 99 100 /** constraint data for superindicator constraints */ 101 struct SCIP_ConsData 102 { 103 SCIP_CONS* slackcons; /**< constraint corresponding to the handled constraint */ 104 SCIP_VAR* binvar; /**< binary variable for indicator constraint */ 105 }; 106 107 /** constraint handler data */ 108 struct SCIP_ConshdlrData 109 { 110 SCIP_Bool checkslacktype; /**< should type of slack constraint be checked when creating superindicator constraint? */ 111 SCIP_Real maxupgdcoeflinear; /**< maximum big-M coefficient of binary variable in upgrade to a linear constraint 112 * (relative to smallest coefficient) */ 113 int upgdprioindicator; /**< priority for upgrading to an indicator constraint (-1: never) */ 114 int upgdpriolinear; /**< priority for upgrading to a linear constraint (-1: never) */ 115 int nrejects; /**< number of rejected calls to create method */ 116 }; 117 118 /* 119 * Local methods 120 */ 121 122 /** creates superindicator constraint data */ 123 static 124 SCIP_RETCODE consdataCreateSuperindicator( 125 SCIP* scip, /**< SCIP data structure */ 126 SCIP_CONSDATA** consdata, /**< pointer to constraint data */ 127 SCIP_VAR* binvar, /**< binary variable */ 128 SCIP_CONS* slackcons /**< slack constraint */ 129 ) 130 { 131 assert(scip != NULL); 132 133 SCIP_CALL( SCIPallocBlockMemory(scip, consdata) ); 134 135 (*consdata)->binvar = binvar; 136 (*consdata)->slackcons = slackcons; 137 138 if( SCIPisTransformed(scip) ) 139 { 140 SCIPdebugMsg(scip, "creating the transformed data\n"); 141 142 /* do not capture the slack constraint when scip is in transformed mode; this automatically happens in 143 * SCIPtransformCons() if necessary 144 */ 145 SCIP_CALL( SCIPtransformCons(scip, (*consdata)->slackcons, &(*consdata)->slackcons) ); 146 147 /* get transformed binary variable */ 148 SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->binvar, &(*consdata)->binvar) ); 149 } 150 else 151 { 152 /* we need to capture the constraint to avoid that SCIP deletes them since they are not (yet) added to the problem */ 153 SCIP_CALL( SCIPcaptureCons(scip, slackcons) ); 154 } 155 156 assert((*consdata)->slackcons != NULL); 157 158 return SCIP_OKAY; 159 } 160 161 /** checks the feasibility of a superindicator constraint */ 162 static 163 SCIP_RETCODE consdataCheckSuperindicator( 164 SCIP* scip, /**< SCIP data structure */ 165 SCIP_CONSDATA* consdata, /**< pointer to superindicator constraint data */ 166 SCIP_SOL* sol, /**< pointer to the solution to be checked */ 167 SCIP_Bool checkintegrality, /**< Has integrality to be checked? */ 168 SCIP_Bool checklprows, /**< Do constraints represented by rows in the current LP have to be checked? */ 169 SCIP_Bool printreason, /**< Should the reason for the violation be printed? */ 170 SCIP_RESULT* result /**< pointer to store the result of the test */ 171 ) 172 { 173 SCIP_Real binval; 174 175 /* not to be called if infeasibility is already detected */ 176 assert(*result == SCIP_FEASIBLE || *result == SCIP_DIDNOTRUN); 177 178 binval = SCIPgetSolVal(scip, sol, consdata->binvar); 179 180 /* check integrality of binary variable */ 181 if( checkintegrality && !SCIPisIntegral(scip, binval) ) 182 { 183 if( printreason ) 184 { 185 SCIPinfoMessage(scip, NULL, "violation: binvar takes fractional value %.15g\n", binval); 186 } 187 188 *result = SCIP_INFEASIBLE; 189 } 190 /* if binvar is one, call SCIPcheckCons() for the slack constraint */ 191 else if( binval > 0.5 ) 192 { 193 assert(SCIPisFeasEQ(scip, binval, 1.0)); 194 195 SCIP_CALL( SCIPcheckCons(scip, consdata->slackcons, sol, checkintegrality, checklprows, printreason, result) ); 196 197 if( printreason && *result != SCIP_FEASIBLE ) 198 { 199 SCIPinfoMessage(scip, NULL, "violation: SCIPcheckCons() for slack constraint <%s> returns infeasible while binvar <%s> == 1\n", 200 SCIPconsGetName(consdata->slackcons), SCIPvarGetName(consdata->binvar)); 201 } 202 203 #ifdef SCIP_DEBUG 204 { 205 /* checking in debug mode that different flags don't give us different results */ 206 SCIP_RESULT testresultnotintegrality; 207 SCIP_RESULT testresultnotlprows; 208 209 SCIP_CALL( SCIPcheckCons(scip, consdata->slackcons, sol, checkintegrality, TRUE, TRUE, &testresultnotintegrality) ); 210 SCIP_CALL( SCIPcheckCons(scip, consdata->slackcons, sol, TRUE, checklprows, TRUE, &testresultnotlprows) ); 211 212 assert(*result == testresultnotintegrality); 213 assert(*result == testresultnotlprows); 214 } 215 #endif 216 217 SCIPdebugMsg(scip, "binvar <%s> == 1, sol=%p --> SCIPcheckCons() on constraint <%s> --> %s\n", 218 SCIPvarGetName(consdata->binvar), (void*)sol, SCIPconsGetName(consdata->slackcons), 219 *result == SCIP_FEASIBLE ? "satisfied" : "violated"); 220 } 221 /* if binval is zero, the superindicator constraint is feasible */ 222 else 223 { 224 *result = SCIP_FEASIBLE; 225 } 226 227 return SCIP_OKAY; 228 } 229 230 /** computes the minactivity, maxactivity, and minimal absolute value of nonzero coefficients of a linear constraint 231 * with respect to its global bounds 232 */ 233 static 234 void extractLinearValues( 235 SCIP* scip, /**< SCIP data structure */ 236 SCIP_CONS* cons, /**< pointer to linear constraint */ 237 SCIP_Real* minactivity, /**< pointer to return the minimal activity */ 238 SCIP_Real* maxactivity, /**< pointer to return the maximal activity */ 239 SCIP_Real* minabscoef /**< pointer to return the minimal absolute value of the coefficients */ 240 ) 241 { 242 SCIP_VAR** vars; 243 SCIP_Real* vals; 244 SCIP_Bool ismininfinity; 245 SCIP_Bool ismaxinfinity; 246 int nvars; 247 int i; 248 249 assert(scip != NULL); 250 assert(cons != NULL); 251 assert(minactivity != NULL); 252 assert(maxactivity != NULL); 253 assert(minabscoef != NULL); 254 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), "linear") == 0); 255 256 /* get nonzero elements */ 257 vars = SCIPgetVarsLinear(scip, cons); 258 vals = SCIPgetValsLinear(scip, cons); 259 nvars = SCIPgetNVarsLinear(scip, cons); 260 261 /* initialize values */ 262 *minactivity = 0.0; 263 *maxactivity = 0.0; 264 *minabscoef = SCIPinfinity(scip); 265 ismininfinity = FALSE; 266 ismaxinfinity = FALSE; 267 268 /* we loop over all the coefficients of the constraint and we cannot end if the minactivity is infinite as we 269 * still need to compute the minimum absolute coefficient value 270 */ 271 for( i = nvars-1; i >= 0; i-- ) 272 { 273 SCIP_Real val; 274 SCIP_Real lb; 275 SCIP_Real ub; 276 277 val = vals[i]; 278 lb = SCIPvarGetLbGlobal(vars[i]); 279 ub = SCIPvarGetUbGlobal(vars[i]); 280 281 /* update flags for infinite bounds */ 282 ismininfinity = ismininfinity || (val > 0.0 && (SCIPisInfinity(scip, lb) || SCIPisInfinity(scip, -lb))) 283 || (val < 0.0 && (SCIPisInfinity(scip, ub) || SCIPisInfinity(scip, -ub))); 284 285 ismaxinfinity = ismaxinfinity || (val > 0.0 && (SCIPisInfinity(scip, ub) || SCIPisInfinity(scip, -ub))) 286 || (val < 0.0 && (SCIPisInfinity(scip, lb) || SCIPisInfinity(scip, -lb))); 287 288 /* update activities if not infinite */ 289 if( !ismininfinity ) 290 *minactivity += (val > 0.0) ? val * lb : val * ub; 291 292 if( !ismaxinfinity ) 293 *maxactivity += (val > 0.0) ? val * ub : val * lb; 294 295 /* update minimal absolute coefficient value */ 296 if( val > 0.0 && val < *minabscoef ) 297 *minabscoef = val; 298 else if( val < 0.0 && -val < *minabscoef ) 299 *minabscoef = -vals[i]; 300 } 301 302 if( ismininfinity ) 303 *minactivity = -SCIPinfinity(scip); 304 305 if( ismaxinfinity ) 306 *maxactivity = SCIPinfinity(scip); 307 } 308 309 /** tries to upgrade superindicator constraint to an indicator constraint */ 310 static 311 SCIP_RETCODE upgradeIndicatorSuperindicator( 312 SCIP* scip, /**< SCIP data structure */ 313 SCIP_CONS* cons, /**< superindicator constraint to be upgraded */ 314 SCIP_Bool* success, /**< pointer to store if the upgrading was successful */ 315 SCIP_Bool* deleted /**< pointer to store if the constraint was deleted */ 316 ) 317 { 318 SCIP_CONSHDLR* conshdlr; 319 SCIP_CONSDATA* consdata; 320 SCIP_CONS* indcons; 321 322 SCIP_Real lhs; 323 SCIP_Real rhs; 324 char name[SCIP_MAXSTRLEN]; 325 int i; 326 327 #ifdef SCIP_DEBUG 328 int nnewconss; 329 #endif 330 331 assert(scip != NULL); 332 assert(cons != NULL); 333 assert(success != NULL); 334 assert(deleted != NULL); 335 336 *success = FALSE; 337 *deleted = FALSE; 338 339 SCIPdebug( nnewconss = 0 ); 340 341 /* get data of superindicator constraint */ 342 consdata = SCIPconsGetData(cons); 343 assert(consdata != NULL); 344 345 /* upgrade only for linear slack constraint */ 346 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(consdata->slackcons)), "linear") != 0 ) 347 return SCIP_OKAY; 348 349 /* upgrade only if indicator constraint handler found */ 350 conshdlr = SCIPfindConshdlr(scip, "indicator"); 351 if( conshdlr == NULL ) 352 return SCIP_OKAY; 353 354 /* if linear slack constraint is free we can delete the superindicator constraint */ 355 lhs = SCIPgetLhsLinear(scip, consdata->slackcons); 356 rhs = SCIPgetRhsLinear(scip, consdata->slackcons); 357 if( SCIPisInfinity(scip, -lhs) && SCIPisInfinity(scip, rhs) ) 358 { 359 SCIP_CALL( SCIPdelCons(scip, cons) ); 360 *deleted = TRUE; 361 362 SCIPdebugMsg(scip, "constraint <%s> deleted because of free slack constraint\n", SCIPconsGetName(cons)); 363 364 return SCIP_OKAY; 365 } 366 367 /* upgrade rhs inequality */ 368 if( !SCIPisInfinity(scip, rhs) ) 369 { 370 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_upgd_indrhs", SCIPconsGetName(cons)); 371 372 SCIP_CALL( SCIPcreateConsIndicator(scip, &indcons, name, consdata->binvar, SCIPgetNVarsLinear(scip, consdata->slackcons), 373 SCIPgetVarsLinear(scip, consdata->slackcons), SCIPgetValsLinear(scip, consdata->slackcons), rhs, 374 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons), SCIPconsIsChecked(cons), 375 SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), 376 SCIPconsIsStickingAtNode(cons)) ); 377 378 SCIP_CALL( SCIPaddCons(scip, indcons) ); 379 SCIP_CALL( SCIPreleaseCons(scip, &indcons) ); 380 381 SCIPdebug( nnewconss++ ); 382 } 383 384 /* upgrade lhs inequality */ 385 if( !SCIPisInfinity(scip, -lhs) ) 386 { 387 SCIP_Real* negvals; 388 SCIP_Real* vals; 389 int nvars; 390 391 vals = SCIPgetValsLinear(scip, consdata->slackcons); 392 nvars = SCIPgetNVarsLinear(scip, consdata->slackcons); 393 394 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_upgd_indlhs", SCIPconsGetName(cons)); 395 396 /* create array of negated coefficient values */ 397 SCIP_CALL( SCIPallocBufferArray(scip, &negvals, nvars) ); 398 for( i = nvars-1; i >= 0; i-- ) 399 negvals[i] = -vals[i]; 400 401 SCIP_CALL( SCIPcreateConsIndicator(scip, &indcons, name, consdata->binvar, nvars, 402 SCIPgetVarsLinear(scip, consdata->slackcons), negvals, -lhs, 403 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons), SCIPconsIsChecked(cons), 404 SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), 405 SCIPconsIsStickingAtNode(cons)) ); 406 407 SCIP_CALL( SCIPaddCons(scip, indcons) ); 408 SCIP_CALL( SCIPreleaseCons(scip, &indcons) ); 409 410 SCIPfreeBufferArray(scip, &negvals); 411 412 SCIPdebug( nnewconss++ ); 413 } 414 415 SCIPdebug( SCIPdebugMsg(scip, "constraint <%s> upgraded to %d indicator constraint%s\n", 416 SCIPconsGetName(cons), nnewconss, nnewconss == 1 ? "" : "s") ); 417 418 /* delete the superindicator constraint */ 419 SCIP_CALL( SCIPdelCons(scip, cons) ); 420 *success = TRUE; 421 422 return SCIP_OKAY; 423 } 424 425 /** upgrades a superindicator constraint to a linear constraint if possible */ 426 static 427 SCIP_RETCODE upgradeLinearSuperindicator( 428 SCIP* scip, /**< SCIP data structure */ 429 SCIP_CONS* cons, /**< superindicator constraint to be upgraded */ 430 SCIP_Bool* success, /**< pointer to store if the upgrading was successful */ 431 SCIP_Bool* deleted /**< pointer to store if the constraint was deleted */ 432 ) 433 { 434 SCIP_CONSHDLR* conshdlr; 435 SCIP_CONSDATA* consdata; 436 SCIP_CONS* slackcons; 437 SCIP_VAR** slackvars; 438 SCIP_VAR** newvars; 439 SCIP_Real* slackvals; 440 SCIP_Real* newvals; 441 442 SCIP_Real maxcoef; 443 SCIP_Real minabscoef; 444 SCIP_Real minact; 445 SCIP_Real maxact; 446 SCIP_Real lhs; 447 SCIP_Real rhs; 448 449 int nvars; 450 int i; 451 452 #ifdef SCIP_DEBUG 453 int nnewconss; 454 #endif 455 456 assert(scip != NULL); 457 assert(cons != NULL); 458 assert(success != NULL); 459 assert(deleted != NULL); 460 461 *success = FALSE; 462 *deleted = FALSE; 463 464 SCIPdebug( nnewconss = 0 ); 465 466 /* get data of superindicator constraint */ 467 consdata = SCIPconsGetData(cons); 468 assert(consdata != NULL); 469 470 slackcons = consdata->slackcons; 471 assert(slackcons != NULL); 472 473 /* upgrade only for linear slack constraint */ 474 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(slackcons)), "linear") != 0 ) 475 return SCIP_OKAY; 476 477 /**@todo store in conshdlrdata */ 478 479 /* upgrade only if linear constraint handler found */ 480 conshdlr = SCIPfindConshdlr(scip, "linear"); 481 if( conshdlr == NULL ) 482 return SCIP_OKAY; 483 484 /* if linear slack constraint is free we can delete the superindicator constraint */ 485 rhs = SCIPgetRhsLinear(scip, slackcons); 486 lhs = SCIPgetLhsLinear(scip, slackcons); 487 488 if( SCIPisInfinity(scip, rhs) && SCIPisInfinity(scip, -lhs) ) 489 { 490 SCIP_CALL( SCIPdelCons(scip, cons) ); 491 *deleted = TRUE; 492 493 SCIPdebugMsg(scip, "constraint <%s> deleted because of free slack constraint\n", SCIPconsGetName(cons)); 494 495 return SCIP_OKAY; 496 } 497 498 /* if linear slack constraint is redundant due to bounded activities we can delete the superindicator constraint */ 499 extractLinearValues(scip, slackcons, &minact, &maxact, &minabscoef); 500 assert(!SCIPisInfinity(scip, minact)); 501 assert(!SCIPisInfinity(scip, -maxact)); 502 503 if( (SCIPisInfinity(scip, -lhs) || SCIPisLE(scip, lhs, minact)) && (SCIPisInfinity(scip, rhs) || SCIPisGE(scip, rhs, maxact)) ) 504 { 505 SCIP_CALL( SCIPdelCons(scip, cons) ); 506 *deleted = TRUE; 507 508 SCIPdebugMsg(scip, "constraint <%s> deleted because of redundant slack constraint\n", SCIPconsGetName(cons)); 509 510 return SCIP_OKAY; 511 } 512 513 /* if the big-M coefficient is too large compared to the coefficients of the slack constraint, we do not upgrade to 514 * avoid numerical problems 515 */ 516 maxcoef = minabscoef * SCIPconshdlrGetData(SCIPconsGetHdlr(cons))->maxupgdcoeflinear; 517 518 if( (!SCIPisInfinity(scip, rhs) && (SCIPisInfinity(scip, maxact) || SCIPisInfinity(scip, maxact - rhs) || 519 maxact - rhs > maxcoef)) || 520 (!SCIPisInfinity(scip, -lhs) && (SCIPisInfinity(scip, -minact) || SCIPisInfinity(scip, lhs - minact) || 521 lhs - minact > maxcoef)) ) 522 { 523 SCIPdebugMsg(scip, "constraint <%s> not upgraded to a linear constraint due to large big-M coefficient\n", 524 SCIPconsGetName(cons)); 525 return SCIP_OKAY; 526 } 527 528 /* allocating memory for new constraint */ 529 nvars = SCIPgetNVarsLinear(scip, slackcons); 530 SCIP_CALL( SCIPallocBufferArray(scip, &newvars, nvars+1) ); 531 SCIP_CALL( SCIPallocBufferArray(scip, &newvals, nvars+1) ); 532 533 /* copy the vars and the vals array */ 534 slackvars = SCIPgetVarsLinear(scip, slackcons); 535 slackvals = SCIPgetValsLinear(scip, slackcons); 536 537 assert(slackvars != NULL); 538 assert(slackvals != NULL); 539 540 for( i = nvars-1; i >= 0; i-- ) 541 { 542 newvars[i] = slackvars[i]; 543 newvals[i] = slackvals[i]; 544 } 545 546 /* add binary variable */ 547 newvars[nvars] = consdata->binvar; 548 assert(newvars[nvars] != NULL); 549 550 assert(!SCIPisInfinity(scip, -lhs) || !SCIPisInfinity(scip, rhs)); 551 552 /* create the upgraded constraint for rhs inequality */ 553 if( !SCIPisInfinity(scip, rhs) ) 554 { 555 SCIP_CONS* newcons; 556 char name[SCIP_MAXSTRLEN]; 557 558 assert(!SCIPisInfinity(scip, -maxact) ); 559 assert(!SCIPisInfinity(scip, maxact)); 560 561 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_upgd_linrhs", SCIPconsGetName(cons)); 562 563 /* compute big-M */ 564 newvals[nvars] = maxact - rhs; 565 assert(!SCIPisInfinity(scip, newvals[nvars])); 566 assert(!SCIPisInfinity(scip, -newvals[nvars])); 567 568 /* rhs inequality is redundant if maxact is less equal rhs */ 569 if( SCIPisPositive(scip, newvals[nvars]) ) 570 { 571 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, name, nvars+1, newvars, newvals, -SCIPinfinity(scip), maxact, 572 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons), SCIPconsIsChecked(cons), 573 SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), 574 SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) ); 575 576 SCIP_CALL( SCIPaddCons(scip, newcons) ); 577 SCIP_CALL( SCIPreleaseCons(scip, &newcons) ); 578 579 SCIPdebug( nnewconss++ ); 580 } 581 } 582 583 /* create the upgraded constraint for rhs inequality */ 584 if( !SCIPisInfinity(scip, -lhs) ) 585 { 586 SCIP_CONS* newcons; 587 char name[SCIP_MAXSTRLEN]; 588 589 assert(!SCIPisInfinity(scip, minact)); 590 assert(!SCIPisInfinity(scip, -minact)); 591 592 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_upgd_linlhs", SCIPconsGetName(cons)); 593 594 /* compute big-M */ 595 newvals[nvars] = minact - lhs; 596 assert(!SCIPisInfinity(scip, newvals[nvars])); 597 assert(!SCIPisInfinity(scip, -newvals[nvars])); 598 599 /* lhs inequality is redundant if minact is greater equal lhs */ 600 if( SCIPisNegative(scip, newvals[nvars]) ) 601 { 602 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, name, nvars+1, newvars, newvals, minact, SCIPinfinity(scip), 603 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons), SCIPconsIsChecked(cons), 604 SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), 605 SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) ); 606 607 SCIP_CALL( SCIPaddCons(scip, newcons) ); 608 SCIP_CALL( SCIPreleaseCons(scip, &newcons) ); 609 610 SCIPdebug( nnewconss++ ); 611 } 612 } 613 614 /* free memory */ 615 SCIPfreeBufferArray(scip, &newvals); 616 SCIPfreeBufferArray(scip, &newvars); 617 618 SCIPdebug( SCIPdebugMsg(scip, "constraint <%s> upgraded to %d indicator constraint%s\n", 619 SCIPconsGetName(cons), nnewconss, nnewconss == 1 ? "" : "s") ); 620 621 /* delete the superindicator constraint */ 622 SCIP_CALL( SCIPdelCons(scip, cons) ); 623 *success = TRUE; 624 625 return SCIP_OKAY; 626 } 627 628 /** tries to upgrade a superindicator constraint in order of the upgrade priority parameters */ 629 static 630 SCIP_RETCODE upgradeSuperindicator( 631 SCIP* scip, /**< SCIP data structure */ 632 SCIP_CONS* cons, /**< superindicator constraint to be updated */ 633 SCIP_Bool* success, /**< pointer to store if the constraint was upgraded */ 634 SCIP_Bool* deleted /**< pointer to store if the constraint was deleted */ 635 ) 636 { 637 SCIP_CONSHDLRDATA* conshdlrdata; 638 639 assert(scip != NULL); 640 assert(cons != NULL); 641 assert(success != NULL); 642 assert(deleted != NULL); 643 644 *success = FALSE; 645 *deleted = FALSE; 646 647 conshdlrdata = SCIPconshdlrGetData(SCIPconsGetHdlr(cons)); 648 649 /* indicator upgrade before linear upgrade */ 650 if( conshdlrdata->upgdprioindicator > conshdlrdata->upgdpriolinear ) 651 { 652 assert(conshdlrdata->upgdprioindicator >= 0); 653 654 SCIP_CALL( upgradeIndicatorSuperindicator(scip, cons, success, deleted) ); 655 656 if( !*deleted && !*success && conshdlrdata->upgdpriolinear >= 0 ) 657 { 658 SCIP_CALL( upgradeLinearSuperindicator(scip, cons, success, deleted) ); 659 } 660 } 661 /* linear upgrade before indicator upgrade */ 662 else if( conshdlrdata->upgdpriolinear >= 0 ) 663 { 664 SCIP_CALL( upgradeLinearSuperindicator(scip, cons, success, deleted) ); 665 666 if( !*deleted && !*success && conshdlrdata->upgdprioindicator >= 0 ) 667 { 668 SCIP_CALL( upgradeIndicatorSuperindicator(scip, cons, success, deleted) ); 669 } 670 } 671 672 return SCIP_OKAY; 673 } 674 675 /** helper function to enforce constraints */ /*lint -e{715}*/ 676 static 677 SCIP_RETCODE enforceConstraint( 678 SCIP* scip, /**< SCIP data structure */ 679 SCIP_CONSHDLR* conshdlr, /**< constraint handler */ 680 SCIP_CONS** conss, /**< constraints to process */ 681 int nconss, /**< number of constraints */ 682 int nusefulconss, /**< number of useful (non-obsolete) constraints to process */ 683 SCIP_SOL* sol, /**< solution to enforce (NULL for the LP solution) */ 684 SCIP_Bool solinfeasible, /**< was the solution already declared infeasible by a constraint handler? */ 685 SCIP_RESULT* result /**< pointer to store the result of the enforcing call */ 686 ) 687 { /*lint --e{715}*/ 688 SCIP_Bool cont; 689 int i; 690 691 assert(scip != NULL); 692 assert(conshdlr != NULL); 693 assert(result != NULL); 694 695 /* if the solution is infeasible anyway, skip the enforcement */ 696 if( solinfeasible ) 697 { 698 *result = SCIP_FEASIBLE; 699 return SCIP_OKAY; 700 } 701 702 SCIPdebugMsg(scip, "executing enforcement callback for %s solution\n", sol == NULL ? "LP" : "relaxation"); 703 704 cont = TRUE; 705 *result = SCIP_FEASIBLE; 706 707 #ifdef SCIP_OUTPUT 708 SCIP_CALL( SCIPprintSol(scip, sol, NULL, FALSE) ); 709 #endif 710 711 /* check all constraints */ 712 for( i = nconss-1; i >= 0 && cont; i-- ) 713 { 714 SCIP_CONSDATA* consdata; 715 SCIP_RESULT locresult; 716 717 consdata = SCIPconsGetData(conss[i]); 718 assert(consdata != NULL); 719 720 locresult = SCIP_FEASIBLE; 721 722 /* enforce only if binvar is fixed to one */ 723 if( SCIPvarGetLbLocal(consdata->binvar) > 0.5 ) 724 { 725 assert(SCIPisFeasEQ(scip, SCIPvarGetLbLocal(consdata->binvar), 1.0)); 726 727 if( sol == NULL ) 728 { 729 SCIPdebugMsg(scip, "binvar <%s> == 1 locally --> SCIPenfolpCons() on constraint <%s>\n", 730 SCIPvarGetName(consdata->binvar), SCIPconsGetName(consdata->slackcons)); 731 732 SCIP_CALL( SCIPenfolpCons(scip, consdata->slackcons, solinfeasible, &locresult) ); 733 } 734 else 735 { 736 SCIPdebugMsg(scip, "binvar <%s> == 1 locally --> SCIPenforelaxCons() on constraint <%s>\n", 737 SCIPvarGetName(consdata->binvar), SCIPconsGetName(consdata->slackcons)); 738 739 SCIP_CALL( SCIPenforelaxCons(scip, consdata->slackcons, sol, solinfeasible, &locresult) ); 740 } 741 742 SCIPdebugPrintf(" --> %slocresult=%d\n", locresult == SCIP_FEASIBLE ? "satisfied, " : "", locresult); 743 } 744 /* otherwise check if we have not yet detected infeasibility */ 745 else if( *result == SCIP_FEASIBLE ) 746 { 747 SCIP_CALL( consdataCheckSuperindicator(scip, consdata, sol, TRUE, FALSE, FALSE, &locresult) ); 748 } 749 750 /* evaluate result */ 751 switch( locresult ) 752 { 753 case SCIP_CUTOFF: 754 case SCIP_BRANCHED: 755 assert(*result != SCIP_CUTOFF); 756 assert(*result != SCIP_BRANCHED); 757 *result = locresult; 758 cont = FALSE; 759 break; 760 case SCIP_CONSADDED: 761 assert(*result != SCIP_CUTOFF); 762 assert(*result != SCIP_BRANCHED); 763 if( *result != SCIP_CUTOFF ) 764 *result = locresult; 765 break; 766 case SCIP_REDUCEDDOM: 767 assert(*result != SCIP_CUTOFF); 768 assert(*result != SCIP_BRANCHED); 769 if( *result != SCIP_CUTOFF 770 && *result != SCIP_CONSADDED ) 771 *result = locresult; 772 break; 773 case SCIP_SEPARATED: 774 assert(*result != SCIP_CUTOFF); 775 assert(*result != SCIP_BRANCHED); 776 if( *result != SCIP_CUTOFF 777 && *result != SCIP_CONSADDED 778 && *result != SCIP_REDUCEDDOM ) 779 *result = locresult; 780 break; 781 case SCIP_INFEASIBLE: 782 assert(*result != SCIP_CUTOFF); 783 assert(*result != SCIP_BRANCHED); 784 if( *result != SCIP_CUTOFF 785 && *result != SCIP_CONSADDED 786 && *result != SCIP_REDUCEDDOM 787 && *result != SCIP_SEPARATED 788 && *result != SCIP_BRANCHED ) 789 *result = locresult; 790 break; 791 case SCIP_FEASIBLE: 792 break; 793 default: 794 SCIPerrorMessage("invalid SCIP result %d\n", locresult); 795 return SCIP_INVALIDRESULT; 796 } /*lint !e788*/ 797 } 798 799 SCIPdebugMsg(scip, "enforcement result=%d\n", *result); 800 801 return SCIP_OKAY; 802 } 803 804 805 /* 806 * Callback methods of constraint handler 807 */ 808 809 /** copy method for constraint handler plugins (called when SCIP copies plugins) */ 810 static 811 SCIP_DECL_CONSHDLRCOPY(conshdlrCopySuperindicator) 812 { /*lint --e{715}*/ 813 assert(scip != NULL); 814 assert(conshdlr != NULL); 815 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 816 817 /* call inclusion method of constraint handler */ 818 SCIP_CALL( SCIPincludeConshdlrSuperindicator(scip) ); 819 820 *valid = TRUE; 821 822 return SCIP_OKAY; 823 } 824 825 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */ 826 static 827 SCIP_DECL_CONSFREE(consFreeSuperindicator) 828 { /*lint --e{715}*/ 829 SCIP_CONSHDLRDATA* conshdlrdata; 830 831 assert(conshdlr != NULL); 832 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 833 assert(scip != NULL); 834 835 SCIPdebugMsg(scip, "freeing superindicator constraint handler data\n"); 836 837 /* free constraint handler data */ 838 conshdlrdata = SCIPconshdlrGetData(conshdlr); 839 assert(conshdlrdata != NULL); 840 841 SCIPfreeBlockMemory(scip, &conshdlrdata); 842 843 SCIPconshdlrSetData(conshdlr, NULL); 844 845 return SCIP_OKAY; 846 } 847 848 /** presolving initialization method of constraint handler (called when presolving is about to begin) */ 849 static 850 SCIP_DECL_CONSINITPRE(consInitpreSuperindicator) 851 { /*lint --e{715}*/ 852 SCIP_CONSDATA* consdata; 853 int i; 854 855 SCIPdebugMsg(scip, "initializing presolving\n"); 856 857 for( i = nconss-1; i >= 0; i-- ) 858 { 859 consdata = SCIPconsGetData(conss[i]); 860 assert(consdata != NULL); 861 862 /* make the constraint local to avoid wrong propagation */ 863 SCIP_CALL( SCIPsetConsLocal(scip, consdata->slackcons, TRUE) ); 864 } 865 866 return SCIP_OKAY; 867 } 868 869 /** frees specific constraint data */ 870 static 871 SCIP_DECL_CONSDELETE(consDeleteSuperindicator) 872 { /*lint --e{715}*/ 873 assert(conshdlr != NULL); 874 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 875 assert(consdata != NULL); 876 assert(*consdata != NULL); 877 assert((*consdata)->slackcons != NULL); 878 879 SCIPdebugMsg(scip, "deleting constraint <%s>\n", SCIPconsGetName(cons)); 880 881 /* we have to release the slack constraint also in case we transformed it manually since it is captured automatically 882 * in SCIPtransformCons() 883 */ 884 SCIP_CALL( SCIPreleaseCons(scip, &((*consdata)->slackcons)) ); 885 886 /* free memory */ 887 SCIPfreeBlockMemory(scip, consdata); 888 889 return SCIP_OKAY; 890 } 891 892 /** transforms constraint data into data belonging to the transformed problem */ 893 static 894 SCIP_DECL_CONSTRANS(consTransSuperindicator) 895 { /*lint --e{715}*/ 896 SCIP_CONSDATA* sourcedata; 897 SCIP_CONSDATA* targetdata; 898 char newname[SCIP_MAXSTRLEN]; 899 900 SCIPdebugMsg(scip, "transforming superindicator constraint <%s>\n", SCIPconsGetName(sourcecons)); 901 902 /* get constraint data of source constraint */ 903 sourcedata = SCIPconsGetData(sourcecons); 904 assert(sourcedata != NULL); 905 906 (void) SCIPsnprintf(newname, SCIP_MAXSTRLEN, "t_%s", SCIPconsGetName(sourcecons) ); 907 SCIP_CALL( consdataCreateSuperindicator(scip, &targetdata, sourcedata->binvar, sourcedata->slackcons) ); 908 909 /* create target constraint and capture it at the same time */ 910 SCIP_CALL( SCIPcreateCons(scip, targetcons, newname, conshdlr, targetdata, 911 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons), 912 SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons), SCIPconsIsLocal(sourcecons), 913 SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), 914 SCIPconsIsStickingAtNode(sourcecons)) ); 915 916 return SCIP_OKAY; 917 } 918 919 /** LP initialization method of constraint handler */ 920 static 921 SCIP_DECL_CONSINITLP(consInitlpSuperindicator) 922 { 923 int c; 924 925 assert(scip != NULL); 926 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 927 assert(infeasible != NULL); 928 929 *infeasible = FALSE; 930 931 SCIPdebugMsg(scip, "executing initlp callback\n"); 932 933 for( c = nconss-1; c >= 0 && !(*infeasible); c-- ) 934 { 935 SCIP_CONSDATA* consdata; 936 937 consdata = SCIPconsGetData(conss[c]); 938 939 assert(consdata != NULL); 940 assert(SCIPconsIsInitial(conss[c])); 941 942 if( SCIPvarGetLbLocal(consdata->binvar) > 0.5 ) 943 { 944 assert(SCIPisFeasEQ(scip, SCIPvarGetLbLocal(consdata->binvar), 1.0)); 945 946 SCIPdebugMsg(scip, "binvar <%s> == 1 --> SCIPinitlpCons() on constraint <%s>\n", 947 SCIPvarGetName(consdata->binvar), SCIPconsGetName(consdata->slackcons)); 948 949 SCIP_CALL( SCIPinitlpCons(scip, consdata->slackcons, infeasible) ); 950 } 951 } 952 953 return SCIP_OKAY; 954 } 955 956 /** separation method of constraint handler for LP solutions */ 957 static 958 SCIP_DECL_CONSSEPALP(consSepalpSuperindicator) 959 { /*lint --e{715}*/ 960 int c; 961 962 assert(conshdlr != NULL); 963 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 964 assert(conss != NULL); 965 assert(result != NULL); 966 967 *result = SCIP_DELAYED; 968 969 SCIPdebugMsg(scip, "executing sepalp callback\n"); 970 971 #ifdef SCIP_OUTPUT 972 SCIP_CALL( SCIPprintSol(scip, NULL, NULL, FALSE) ); 973 #endif 974 975 /* check all useful constraints */ 976 for( c = nusefulconss-1; c >= 0 && *result != SCIP_CUTOFF; c-- ) 977 { 978 SCIP_CONSDATA* consdata; 979 SCIP_RESULT locresult; 980 981 consdata = SCIPconsGetData(conss[c]); 982 assert(consdata != NULL); 983 984 locresult = SCIP_DELAYED; 985 986 /* separate only if binvar is fixed to one */ 987 if( SCIPvarGetLbLocal(consdata->binvar) > 0.5 ) 988 { 989 assert(SCIPisFeasEQ(scip, SCIPvarGetLbLocal(consdata->binvar), 1.0)); 990 991 SCIPdebugMsg(scip, "binvar <%s> == 1 --> SCIPsepalpCons() on constraint <%s>\n", 992 SCIPvarGetName(consdata->binvar), SCIPconsGetName(consdata->slackcons)); 993 994 SCIP_CALL( SCIPsepalpCons(scip, consdata->slackcons, &locresult) ); 995 996 SCIPdebugMsgPrint(scip, " --> locresult=%d\n", locresult); 997 } 998 999 /* evaluate result value */ 1000 switch( locresult ) 1001 { 1002 case SCIP_CUTOFF: 1003 case SCIP_CONSADDED: 1004 assert(*result != SCIP_CUTOFF); 1005 *result = locresult; 1006 break; 1007 case SCIP_REDUCEDDOM: 1008 assert(*result != SCIP_CUTOFF); 1009 if( *result != SCIP_CONSADDED ) 1010 *result = locresult; 1011 break; 1012 case SCIP_SEPARATED: 1013 assert(*result != SCIP_CUTOFF); 1014 if( *result != SCIP_CONSADDED 1015 && *result != SCIP_REDUCEDDOM ) 1016 *result = locresult; 1017 break; 1018 case SCIP_NEWROUND: 1019 assert(*result != SCIP_CUTOFF); 1020 if( *result != SCIP_CONSADDED 1021 && *result != SCIP_REDUCEDDOM 1022 && *result != SCIP_SEPARATED ) 1023 *result = locresult; 1024 break; 1025 case SCIP_DIDNOTFIND: 1026 assert(*result != SCIP_CUTOFF); 1027 if( *result != SCIP_CONSADDED 1028 && *result != SCIP_REDUCEDDOM 1029 && *result != SCIP_NEWROUND 1030 && *result != SCIP_SEPARATED ) 1031 *result = locresult; 1032 break; 1033 case SCIP_DIDNOTRUN: 1034 assert(*result != SCIP_CUTOFF); 1035 if( *result != SCIP_CONSADDED 1036 && *result != SCIP_REDUCEDDOM 1037 && *result != SCIP_NEWROUND 1038 && *result != SCIP_SEPARATED 1039 && *result != SCIP_DIDNOTFIND ) 1040 *result = locresult; 1041 break; 1042 case SCIP_INFEASIBLE: 1043 assert(*result != SCIP_CUTOFF); 1044 if( *result != SCIP_CONSADDED 1045 && *result != SCIP_REDUCEDDOM 1046 && *result != SCIP_SEPARATED 1047 && *result != SCIP_DIDNOTFIND 1048 && *result != SCIP_DIDNOTRUN 1049 && *result != SCIP_NEWROUND ) 1050 *result = locresult; 1051 break; 1052 case SCIP_DELAYED: 1053 break; 1054 default: 1055 SCIPerrorMessage("invalid SCIP result %d\n", locresult); 1056 return SCIP_INVALIDRESULT; 1057 } /*lint !e788*/ 1058 } 1059 1060 SCIPdebugMsg(scip, "sepalp result=%d\n", *result); 1061 1062 return SCIP_OKAY; 1063 } 1064 1065 /** separation method of constraint handler for arbitrary primal solutions */ 1066 static 1067 SCIP_DECL_CONSSEPASOL(consSepasolSuperindicator) 1068 { /*lint --e{715}*/ 1069 int c; 1070 1071 assert(conshdlr != NULL); 1072 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 1073 assert(conss != NULL); 1074 assert(result != NULL); 1075 1076 *result = SCIP_DELAYED; 1077 1078 SCIPdebugMsg(scip, "executing sepasol callback\n"); 1079 1080 #ifdef SCIP_OUTPUT 1081 SCIP_CALL( SCIPprintSol(scip, NULL, NULL, FALSE) ); 1082 #endif 1083 1084 /* check all the useful constraint */ 1085 for( c = 0; c < nusefulconss && *result != SCIP_CUTOFF; ++c ) 1086 { 1087 SCIP_CONSDATA* consdata; 1088 SCIP_RESULT locresult; 1089 1090 consdata = SCIPconsGetData(conss[c]); 1091 assert(consdata != NULL); 1092 1093 locresult = SCIP_DELAYED; 1094 1095 /* separate only if binvar is fixed to one */ 1096 if( SCIPvarGetLbLocal(consdata->binvar) > 0.5 ) 1097 { 1098 assert(SCIPisFeasEQ(scip, SCIPvarGetLbLocal(consdata->binvar), 1.0)); 1099 1100 SCIPdebugMsg(scip, "binvar <%s> == 0 --> SCIPsepasolCons() on constraint <%s>\n", 1101 SCIPvarGetName(consdata->binvar), SCIPconsGetName(consdata->slackcons)); 1102 1103 SCIP_CALL( SCIPsepasolCons(scip, consdata->slackcons, sol, &locresult) ); 1104 1105 SCIPdebugMsgPrint(scip, " --> result=%d\n", locresult); 1106 } 1107 1108 /* evaluate result value */ 1109 switch( locresult ) 1110 { 1111 case SCIP_CUTOFF: 1112 case SCIP_CONSADDED: 1113 assert(*result != SCIP_CUTOFF); 1114 *result = locresult; 1115 break; 1116 case SCIP_REDUCEDDOM: 1117 assert(*result != SCIP_CUTOFF); 1118 if( *result != SCIP_CONSADDED ) 1119 *result = locresult; 1120 break; 1121 case SCIP_SEPARATED: 1122 assert(*result != SCIP_CUTOFF); 1123 if( *result != SCIP_CONSADDED 1124 && *result != SCIP_REDUCEDDOM ) 1125 *result = locresult; 1126 break; 1127 case SCIP_NEWROUND: 1128 assert(*result != SCIP_CUTOFF); 1129 if( *result != SCIP_CONSADDED 1130 && *result != SCIP_REDUCEDDOM 1131 && *result != SCIP_SEPARATED ) 1132 *result = locresult; 1133 break; 1134 case SCIP_DIDNOTFIND: 1135 assert(*result != SCIP_CUTOFF); 1136 if( *result != SCIP_CONSADDED 1137 && *result != SCIP_REDUCEDDOM 1138 && *result != SCIP_NEWROUND 1139 && *result != SCIP_SEPARATED ) 1140 *result = locresult; 1141 break; 1142 case SCIP_DIDNOTRUN: 1143 assert(*result != SCIP_CUTOFF); 1144 if( *result != SCIP_CONSADDED 1145 && *result != SCIP_REDUCEDDOM 1146 && *result != SCIP_NEWROUND 1147 && *result != SCIP_SEPARATED 1148 && *result != SCIP_DIDNOTFIND ) 1149 *result = locresult; 1150 break; 1151 case SCIP_INFEASIBLE: 1152 assert(*result != SCIP_CUTOFF); 1153 if( *result != SCIP_CONSADDED 1154 && *result != SCIP_REDUCEDDOM 1155 && *result != SCIP_SEPARATED 1156 && *result != SCIP_DIDNOTFIND 1157 && *result != SCIP_DIDNOTRUN 1158 && *result != SCIP_NEWROUND ) 1159 *result = locresult; 1160 break; 1161 case SCIP_DELAYED: 1162 break; 1163 default: 1164 SCIPerrorMessage("invalid SCIP result %d\n", locresult); 1165 return SCIP_INVALIDRESULT; 1166 } /*lint !e788*/ 1167 } 1168 1169 SCIPdebugMsg(scip, "sepa sol result=%d\n", *result); 1170 1171 return SCIP_OKAY; 1172 } 1173 1174 /** constraint enforcing method of constraint handler for LP solutions */ 1175 static 1176 SCIP_DECL_CONSENFOLP(consEnfolpSuperindicator) 1177 { /*lint --e{715}*/ 1178 SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, nusefulconss, NULL, solinfeasible, result) ); 1179 1180 return SCIP_OKAY; 1181 } 1182 1183 /** constraint enforcing method of constraint handler for relaxation solutions */ 1184 static 1185 SCIP_DECL_CONSENFORELAX(consEnforelaxSuperindicator) 1186 { /*lint --e{715}*/ 1187 SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, nusefulconss, sol, solinfeasible, result) ); 1188 1189 return SCIP_OKAY; 1190 } 1191 1192 /** constraint enforcing method of constraint handler for pseudo solutions */ 1193 static 1194 SCIP_DECL_CONSENFOPS(consEnfopsSuperindicator) 1195 { /*lint --e{715}*/ 1196 SCIP_Bool cont; 1197 int i; 1198 1199 assert(scip != NULL); 1200 assert(conshdlr != NULL); 1201 assert(result != NULL); 1202 1203 /* if the solution is infeasible anyway, skip the enforcement */ 1204 if( solinfeasible ) 1205 { 1206 *result = SCIP_FEASIBLE; 1207 return SCIP_OKAY; 1208 } 1209 else if( objinfeasible ) 1210 { 1211 *result = SCIP_DIDNOTRUN; 1212 return SCIP_OKAY; 1213 } 1214 1215 SCIPdebugMsg(scip, "executing enfops callback\n"); 1216 1217 *result = SCIP_FEASIBLE; 1218 cont = TRUE; 1219 1220 /* check all contraints */ 1221 for( i = nconss-1; i >= 0 && cont; i-- ) 1222 { 1223 SCIP_CONSDATA* consdata; 1224 SCIP_RESULT locresult; 1225 1226 consdata = SCIPconsGetData(conss[i]); 1227 assert(consdata != NULL); 1228 1229 locresult = SCIP_DIDNOTRUN; 1230 1231 /* enforce only if binvar is fixed to one */ 1232 if( SCIPvarGetLbLocal(consdata->binvar) > 0.5 ) 1233 { 1234 assert(SCIPisFeasEQ(scip, SCIPvarGetLbLocal(consdata->binvar), 1.0)); 1235 1236 SCIPdebugMsg(scip, "binvar <%s> == 1 locally --> SCIPenfopsCons() on constraint <%s>\n", 1237 SCIPvarGetName(consdata->binvar), SCIPconsGetName(consdata->slackcons)); 1238 1239 SCIP_CALL( SCIPenfopsCons(scip, consdata->slackcons, solinfeasible, objinfeasible, &locresult) ); 1240 1241 SCIPdebugMsgPrint(scip, " --> %slocresult=%d\n", locresult == SCIP_FEASIBLE ? "satisfied, " : "", locresult); 1242 } 1243 /* otherwise check if we have not yet detected infeasibility */ 1244 else if( *result == SCIP_FEASIBLE || *result == SCIP_DIDNOTRUN ) 1245 { 1246 SCIP_CALL( consdataCheckSuperindicator(scip, consdata, NULL, TRUE, FALSE, FALSE, &locresult) ); 1247 } 1248 1249 /* evaluate result value */ 1250 switch( locresult ) 1251 { 1252 case SCIP_CUTOFF: 1253 case SCIP_BRANCHED: 1254 assert(*result != SCIP_CUTOFF); 1255 assert(*result != SCIP_BRANCHED); 1256 *result = locresult; 1257 cont = FALSE; 1258 break; 1259 case SCIP_CONSADDED: 1260 assert(*result != SCIP_CUTOFF); 1261 assert(*result != SCIP_BRANCHED); 1262 if( *result != SCIP_CUTOFF ) 1263 *result = locresult; 1264 break; 1265 case SCIP_REDUCEDDOM: 1266 assert(*result != SCIP_CUTOFF); 1267 assert(*result != SCIP_BRANCHED); 1268 if( *result != SCIP_CUTOFF 1269 && *result != SCIP_CONSADDED ) 1270 *result = locresult; 1271 break; 1272 case SCIP_SOLVELP: 1273 assert(*result != SCIP_CUTOFF); 1274 assert(*result != SCIP_BRANCHED); 1275 if( *result != SCIP_CUTOFF 1276 && *result != SCIP_CONSADDED 1277 && *result != SCIP_REDUCEDDOM 1278 && *result != SCIP_BRANCHED ) 1279 *result = locresult; 1280 break; 1281 case SCIP_INFEASIBLE: 1282 assert(*result != SCIP_CUTOFF); 1283 assert(*result != SCIP_BRANCHED); 1284 if( *result != SCIP_CUTOFF 1285 && *result != SCIP_CONSADDED 1286 && *result != SCIP_REDUCEDDOM 1287 && *result != SCIP_BRANCHED 1288 && *result != SCIP_SOLVELP ) 1289 *result = locresult; 1290 break; 1291 case SCIP_DIDNOTRUN: 1292 assert(*result != SCIP_CUTOFF); 1293 assert(*result != SCIP_BRANCHED); 1294 if( *result != SCIP_CUTOFF 1295 && *result != SCIP_CONSADDED 1296 && *result != SCIP_REDUCEDDOM 1297 && *result != SCIP_BRANCHED 1298 && *result != SCIP_SOLVELP 1299 && *result != SCIP_INFEASIBLE ) 1300 *result = locresult; 1301 break; 1302 case SCIP_FEASIBLE: 1303 assert(*result != SCIP_CUTOFF); 1304 assert(*result != SCIP_BRANCHED); 1305 if( *result != SCIP_CUTOFF 1306 && *result != SCIP_CONSADDED 1307 && *result != SCIP_REDUCEDDOM 1308 && *result != SCIP_BRANCHED 1309 && *result != SCIP_SOLVELP 1310 && *result != SCIP_INFEASIBLE 1311 && *result != SCIP_DIDNOTRUN ) 1312 *result = locresult; 1313 break; 1314 default: 1315 SCIPerrorMessage("invalid SCIP result %d\n", locresult); 1316 return SCIP_INVALIDRESULT; 1317 } /*lint !e788*/ 1318 } 1319 1320 SCIPdebugMsg(scip, "enfops result=%d\n", *result); 1321 1322 return SCIP_OKAY; 1323 } 1324 1325 /** feasibility check method of constraint handler for integral solutions */ 1326 static 1327 SCIP_DECL_CONSCHECK(consCheckSuperindicator) 1328 { /*lint --e{715}*/ 1329 int i; 1330 1331 assert(scip != NULL); 1332 assert(conshdlr != NULL); 1333 assert(result != NULL); 1334 assert(sol != NULL); 1335 1336 *result = SCIP_FEASIBLE; 1337 1338 for( i = nconss-1; i >= 0 && (*result == SCIP_FEASIBLE || completely); i-- ) 1339 { 1340 SCIP_CONSDATA* consdata; 1341 1342 consdata = SCIPconsGetData(conss[i]); 1343 SCIP_CALL( consdataCheckSuperindicator(scip, consdata, sol, checkintegrality, checklprows, printreason, result) ); 1344 } 1345 1346 SCIPdebugMsg(scip, "checked solution from <%s> (checkintegrality=%u, checklprows=%u) --> result=%d (%sfeasible)\n", 1347 SCIPsolGetHeur(sol) == NULL ? "NULL" : SCIPheurGetName(SCIPsolGetHeur(sol)), checkintegrality, checklprows, 1348 *result, *result == SCIP_INFEASIBLE ? "in" : ""); 1349 1350 return SCIP_OKAY; 1351 } 1352 1353 /** domain propagation method of constraint handler */ 1354 static 1355 SCIP_DECL_CONSPROP(consPropSuperindicator) 1356 { /*lint --e{715}*/ 1357 int i; 1358 1359 assert(scip != NULL); 1360 assert(conshdlr != NULL); 1361 assert(result != NULL); 1362 1363 *result = SCIP_DIDNOTRUN; 1364 1365 SCIPdebugMsg(scip, "executing prop callback\n"); 1366 1367 /* loop over all useful contraints */ 1368 for( i = nusefulconss-1; i >= 0 && *result != SCIP_CUTOFF; i-- ) 1369 { 1370 SCIP_CONSDATA* consdata; 1371 SCIP_RESULT locresult; 1372 1373 consdata = SCIPconsGetData(conss[i]); 1374 assert(consdata != NULL); 1375 1376 locresult = SCIP_DIDNOTRUN; 1377 1378 /* propagate only if binvar is fixed to one */ 1379 if( SCIPvarGetLbGlobal(consdata->binvar) > 0.5 ) 1380 { 1381 assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(consdata->binvar), 1.0)); 1382 1383 SCIPdebugMsg(scip, "binvar <%s> == 1 globally --> deleting superindicator and adding slack constraint <%s>\n", 1384 SCIPvarGetName(consdata->binvar), SCIPconsGetName(consdata->slackcons)); 1385 1386 SCIP_CALL( SCIPsetConsLocal(scip, consdata->slackcons, FALSE) ); 1387 SCIP_CALL( SCIPaddCons(scip, consdata->slackcons) ); 1388 SCIP_CALL( SCIPdelCons(scip, conss[i]) ); 1389 1390 locresult = SCIP_DIDNOTFIND; 1391 } 1392 else if( SCIPvarGetLbLocal(consdata->binvar) > 0.5 ) 1393 { 1394 assert(SCIPisFeasEQ(scip, SCIPvarGetLbLocal(consdata->binvar), 1.0)); 1395 1396 SCIPdebugMsg(scip, "binvar <%s> == 1 locally --> propagating slack constraint <%s>\n", 1397 SCIPvarGetName(consdata->binvar), SCIPconsGetName(consdata->slackcons)); 1398 1399 SCIP_CALL( SCIPpropCons(scip, consdata->slackcons, proptiming, &locresult) ); 1400 1401 SCIPdebugMsgPrint(scip, " --> locresult=%d\n", locresult); 1402 } 1403 /**@todo else propagate the domain of the binvar as well: start probing mode, fix binvar to one, propagate 1404 * constraint, and see whether we become infeasible; if this is implemented, the resprop callback must be 1405 * updated 1406 */ 1407 1408 /* evaluate result value */ 1409 switch( locresult ) 1410 { 1411 case SCIP_CUTOFF: 1412 case SCIP_DELAYED: 1413 /* if propagation of one constraint is delayed, we want to propagate again unless the node is cut off */ 1414 assert(*result != SCIP_CUTOFF); 1415 *result = locresult; 1416 break; 1417 case SCIP_REDUCEDDOM: 1418 assert(*result != SCIP_CUTOFF); 1419 if( *result != SCIP_DELAYED ) 1420 *result = locresult; 1421 break; 1422 case SCIP_DIDNOTFIND: 1423 assert(*result != SCIP_CUTOFF); 1424 if( *result != SCIP_REDUCEDDOM 1425 && *result != SCIP_DELAYED ) 1426 *result = locresult; 1427 break; 1428 case SCIP_DIDNOTRUN: 1429 assert(*result != SCIP_CUTOFF); 1430 if( *result != SCIP_REDUCEDDOM 1431 && *result != SCIP_DIDNOTFIND 1432 && *result != SCIP_DELAYED ) 1433 *result = locresult; 1434 break; 1435 default: 1436 SCIPerrorMessage("invalid SCIP result %d\n", locresult); 1437 return SCIP_INVALIDRESULT; 1438 } /*lint !e788*/ 1439 } 1440 1441 SCIPdebugMsg(scip, "prop result=%d\n", *result); 1442 1443 return SCIP_OKAY; 1444 } 1445 1446 /** presolving method of constraint handler */ 1447 static 1448 SCIP_DECL_CONSPRESOL(consPresolSuperindicator) 1449 { /*lint --e{715}*/ 1450 int i; 1451 1452 assert(scip != NULL); 1453 assert(conss != NULL); 1454 assert(conshdlr != NULL); 1455 1456 *result = SCIP_DIDNOTRUN; 1457 1458 SCIPdebugMsg(scip, "executing presol callback\n"); 1459 1460 for( i = nconss-1; i >= 0 && *result != SCIP_CUTOFF; i-- ) 1461 { 1462 SCIP_CONSDATA* consdata; 1463 SCIP_RESULT locresult; 1464 1465 consdata = SCIPconsGetData(conss[i]); 1466 assert(consdata != NULL); 1467 1468 locresult = SCIP_DIDNOTFIND; 1469 1470 /**@todo check whether the slack constraint is added to SCIP; in this case the superindicator can be deleted */ 1471 1472 /**@todo check whether the slack constraint is a superindicator constraint and presolve */ 1473 1474 /* if binvar is globally fixed to 1, we add the slack constraint and remove the superindicator */ 1475 if( SCIPvarGetLbGlobal(consdata->binvar) > 0.5 ) 1476 { 1477 assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(consdata->binvar), 1.0)); 1478 1479 SCIPdebugMsg(scip, "binvar <%s> == 1 globally --> deleting superindicator and adding slack constraint <%s>\n", 1480 SCIPvarGetName(consdata->binvar), SCIPconsGetName(consdata->slackcons)); 1481 1482 SCIP_CALL( SCIPsetConsLocal(scip, consdata->slackcons, FALSE) ); 1483 SCIP_CALL( SCIPaddCons(scip, consdata->slackcons) ); 1484 SCIP_CALL( SCIPdelCons(scip, conss[i]) ); 1485 1486 locresult = SCIP_SUCCESS; 1487 } 1488 /* otherwise try upgrading */ 1489 else 1490 { 1491 SCIP_Bool success; 1492 SCIP_Bool deleted; 1493 1494 SCIP_CALL( upgradeSuperindicator(scip, conss[i], &success, &deleted) ); 1495 1496 /* update statistics */ 1497 if( deleted ) 1498 (*ndelconss)++; 1499 else if( success ) 1500 (*nupgdconss)++; 1501 1502 /**@todo mark if upgrading failed to avoid trying too often; however, since upgrading might fail only due to 1503 * large domains, we may want to try again later, e.g., if SCIPisPresolveFinished() is TRUE 1504 */ 1505 1506 if( deleted || success ) 1507 locresult = SCIP_SUCCESS; 1508 } 1509 /**@todo else propagate the domain of the binvar as well: start probing mode, fix binvar to one, propagate 1510 * constraint, and see whether we become infeasible 1511 */ 1512 1513 /* evaluate result value */ 1514 switch( locresult ) 1515 { 1516 case SCIP_SUCCESS: 1517 assert(*result != SCIP_CUTOFF); 1518 if( *result != SCIP_DELAYED ) 1519 *result = locresult; 1520 break; 1521 default: 1522 assert(locresult == SCIP_DIDNOTFIND); 1523 assert(*result != SCIP_CUTOFF); 1524 if( *result != SCIP_UNBOUNDED && *result != SCIP_DELAYED && *result != SCIP_SUCCESS ) 1525 *result = locresult; 1526 break; 1527 } /*lint !e788*/ 1528 } 1529 1530 SCIPdebugMsg(scip, "presol result=%d\n", *result); 1531 1532 return SCIP_OKAY; 1533 } 1534 1535 /** propagation conflict resolving method of constraint handler */ 1536 static 1537 SCIP_DECL_CONSRESPROP(consRespropSuperindicator) 1538 { /*lint --e{715}*/ 1539 SCIP_CONSDATA* consdata; 1540 1541 assert(scip != NULL); 1542 assert(cons != NULL); 1543 assert(infervar != NULL); 1544 assert(bdchgidx != NULL); 1545 assert(result != NULL); 1546 1547 SCIPdebugMsg(scip, "executing resprop callback for constraint <%s>\n", SCIPconsGetName(cons)); 1548 1549 consdata = SCIPconsGetData(cons); 1550 assert(consdata != NULL); 1551 1552 *result = SCIP_DIDNOTFIND; 1553 1554 /* check that we only propagated if the binvar is fixed to one */ 1555 assert(SCIPisFeasEQ(scip, SCIPgetVarUbAtIndex(scip, consdata->binvar, bdchgidx, TRUE), 1.0)); 1556 1557 /* add tightened lower bound on binvar to conflict set */ 1558 SCIP_CALL( SCIPaddConflictLb(scip, consdata->binvar, bdchgidx) ); 1559 1560 /* call propagation conflict resolving method for the slack constraint */ 1561 SCIP_CALL( SCIPrespropCons(scip, consdata->slackcons, infervar, inferinfo, boundtype, bdchgidx, relaxedbd, result) ); 1562 1563 SCIPdebugMsgPrint(scip, " --> result=%d\n", *result); 1564 1565 return SCIP_OKAY; 1566 } 1567 1568 /** variable rounding lock method of constraint handler */ 1569 static 1570 SCIP_DECL_CONSLOCK(consLockSuperindicator) 1571 { /*lint --e{715}*/ 1572 SCIP_CONSDATA* consdata; 1573 1574 assert(scip != NULL); 1575 assert(locktype == SCIP_LOCKTYPE_MODEL); 1576 1577 SCIPdebugMsg(scip, "locking variables for constraint <%s>\n", SCIPconsGetName(cons)); 1578 1579 consdata = SCIPconsGetData(cons); 1580 assert(consdata != NULL); 1581 1582 /* lock binvar up */ 1583 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->binvar, locktype, nlocksneg, nlockspos) ); 1584 1585 /* call lock method for the slack constraint */ 1586 SCIP_CALL( SCIPaddConsLocksType(scip, consdata->slackcons, locktype, nlockspos, nlocksneg) ); 1587 1588 return SCIP_OKAY; 1589 } 1590 1591 1592 /** constraint display method of constraint handler */ 1593 static 1594 SCIP_DECL_CONSPRINT(consPrintSuperindicator) 1595 { /*lint --e{715}*/ 1596 SCIP_CONSDATA* consdata; 1597 SCIP_VAR* binvar; 1598 int zeroone; 1599 1600 assert(scip != NULL); 1601 assert(conshdlr != NULL); 1602 assert(cons != NULL); 1603 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 1604 1605 consdata = SCIPconsGetData(cons); 1606 assert(consdata != NULL); 1607 1608 /* get binary variable */ 1609 binvar = consdata->binvar; 1610 assert(binvar != NULL); 1611 1612 /* resolve negation if necessary */ 1613 zeroone = 1; 1614 if ( SCIPvarGetStatus(binvar) == SCIP_VARSTATUS_NEGATED ) 1615 { 1616 zeroone = 0; 1617 binvar = SCIPvarGetNegatedVar(binvar); 1618 assert(binvar != NULL); 1619 } 1620 1621 /* print name of the binary variable */ 1622 SCIP_CALL( SCIPwriteVarName(scip, file, binvar, TRUE) ); 1623 1624 /* print implication */ 1625 SCIPinfoMessage(scip, file, " = %d ->", zeroone); 1626 1627 /* print slack constraint */ 1628 assert(consdata->slackcons != NULL); 1629 SCIP_CALL( SCIPprintCons(scip, consdata->slackcons, file) ); 1630 1631 return SCIP_OKAY; 1632 } 1633 1634 /** constraint copying method of constraint handler */ 1635 static 1636 SCIP_DECL_CONSCOPY(consCopySuperindicator) 1637 { /*lint --e{715}*/ 1638 SCIP_CONSHDLR* conshdlrslack; 1639 SCIP_CONSDATA* sourceconsdata; 1640 SCIP_CONS* sourceslackcons; 1641 SCIP_CONS* targetslackcons; 1642 SCIP_VAR* targetbinvar; 1643 const char* consname; 1644 1645 assert(scip != NULL); 1646 assert(sourcescip != NULL); 1647 assert(sourcecons != NULL); 1648 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(sourcecons)), CONSHDLR_NAME) == 0); 1649 1650 *valid = TRUE; 1651 1652 if( name != NULL ) 1653 consname = name; 1654 else 1655 consname = SCIPconsGetName(sourcecons); 1656 1657 SCIPdebugMsg(scip, "copying superindicator constraint <%s> to <%s>\n", SCIPconsGetName(sourcecons), consname); 1658 1659 if( modifiable ) 1660 { 1661 SCIPwarningMessage(scip, "cannot create modifiable superindicator constraint when trying to copy constraint <%s>\n", 1662 SCIPconsGetName(sourcecons)); 1663 *valid = FALSE; 1664 return SCIP_OKAY; 1665 } 1666 1667 sourceconsdata = SCIPconsGetData(sourcecons); 1668 assert(sourceconsdata != NULL); 1669 1670 /* get slack constraint */ 1671 sourceslackcons = sourceconsdata->slackcons; 1672 assert(sourceslackcons != NULL); 1673 1674 /* if the slack constraint has been deleted, create an empty linear constraint */ 1675 if( SCIPconsIsDeleted(sourceslackcons) ) 1676 { 1677 SCIPdebugMsg(scip, "slack constraint <%s> deleted; creating empty linear constraint\n", 1678 SCIPconsGetName(sourceslackcons)); 1679 1680 SCIP_CALL( SCIPcreateConsLinear(scip, &targetslackcons, "dummy", 0, NULL, NULL, 0.0, SCIPinfinity(scip), 1681 FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 1682 1683 SCIP_CALL( SCIPaddCons(scip, targetslackcons) ); 1684 } 1685 else 1686 { 1687 /* get copied version of slack constraint */ 1688 conshdlrslack = SCIPconsGetHdlr(sourceslackcons); 1689 assert(conshdlrslack != NULL); 1690 1691 /* if copying scip after transforming the original instance before presolving, we need to correct the slack 1692 * constraint pointer 1693 */ 1694 assert(!SCIPisTransformed(sourcescip) || SCIPconsIsTransformed(sourceslackcons)); 1695 if( SCIPisTransformed(sourcescip) && !SCIPconsIsTransformed(sourceslackcons) ) 1696 { 1697 SCIP_CONS* transslackcons; 1698 1699 SCIP_CALL( SCIPgetTransformedCons(sourcescip, sourceslackcons, &transslackcons) ); 1700 assert(transslackcons != NULL); 1701 SCIP_CALL( SCIPreleaseCons(sourcescip, &sourceconsdata->slackcons) ); 1702 SCIP_CALL( SCIPcaptureCons(sourcescip, transslackcons) ); 1703 1704 sourceconsdata->slackcons = transslackcons; 1705 sourceslackcons = transslackcons; 1706 } 1707 1708 SCIP_CALL( SCIPgetConsCopy(sourcescip, scip, sourceslackcons, &targetslackcons, conshdlrslack, varmap, consmap, 1709 SCIPconsGetName(sourceslackcons), SCIPconsIsInitial(sourceslackcons), SCIPconsIsSeparated(sourceslackcons), 1710 SCIPconsIsEnforced(sourceslackcons), SCIPconsIsChecked(sourceslackcons), SCIPconsIsPropagated(sourceslackcons), 1711 SCIPconsIsLocal(sourceslackcons), SCIPconsIsModifiable(sourceslackcons), SCIPconsIsDynamic(sourceslackcons), 1712 SCIPconsIsRemovable(sourceslackcons), SCIPconsIsStickingAtNode(sourceslackcons), global, valid) ); 1713 } 1714 1715 /* find copied variable corresponding to binvar */ 1716 if( *valid ) 1717 { 1718 SCIP_VAR* sourcebinvar; 1719 1720 sourcebinvar = sourceconsdata->binvar; 1721 assert(sourcebinvar != NULL); 1722 1723 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcebinvar, &targetbinvar, varmap, consmap, global, valid) ); 1724 } 1725 else 1726 targetbinvar = NULL; 1727 1728 /* create superindicator constraint */ 1729 if( *valid ) 1730 { 1731 assert(targetslackcons != NULL); 1732 assert(targetbinvar != NULL); 1733 assert(!modifiable); 1734 1735 SCIP_CALL( SCIPcreateConsSuperindicator(scip, cons, consname, targetbinvar, targetslackcons, 1736 initial, separate, enforce, check, propagate, local, dynamic, removable, stickingatnode) ); 1737 } 1738 1739 /* relase slack constraint */ 1740 if( targetslackcons != NULL ) 1741 { 1742 SCIP_CALL( SCIPreleaseCons(scip, &targetslackcons) ); 1743 } 1744 1745 if( !(*valid) ) 1746 { 1747 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "could not copy superindicator constraint <%s>\n", SCIPconsGetName(sourcecons)); 1748 } 1749 1750 return SCIP_OKAY; 1751 } 1752 1753 /** constraint parsing method of constraint handler */ 1754 static 1755 SCIP_DECL_CONSPARSE(consParseSuperindicator) 1756 { /*lint --e{715}*/ 1757 SCIP_VAR* binvar; 1758 SCIP_CONS* slackcons; 1759 char binvarname[1024]; 1760 const char* slackstr; 1761 int zeroone; 1762 int nargs; 1763 1764 assert(cons != NULL); 1765 assert(scip != NULL); 1766 assert(success != NULL); 1767 assert(str != NULL); 1768 assert(name != NULL); 1769 1770 *success = FALSE; 1771 1772 /* extract binary variable name and value which triggers slack constraint */ 1773 /* coverity[secure_coding] */ 1774 nargs = sscanf(str, " <%1023[^>]>[B] = %d", binvarname, &zeroone); 1775 1776 if( nargs != 2 || (zeroone != 0 && zeroone != 1) ) 1777 { 1778 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "Syntax error: expected the following form: <var> = [0|1] -> <cons>\n"); 1779 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "got: %s\n", str); 1780 return SCIP_OKAY; 1781 } 1782 1783 /* extract string describing slack constraint */ 1784 slackstr = strstr(str, "->"); 1785 1786 if( slackstr == NULL ) 1787 { 1788 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "Syntax error: expected the following form: <var> = [0|1] -> <cons>\n"); 1789 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "got: %s\n", str); 1790 return SCIP_OKAY; 1791 } 1792 1793 slackstr = strstr(slackstr, "["); 1794 1795 if( slackstr == NULL ) 1796 { 1797 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "Syntax error: expected the following form: <var> = [0|1] -> <cons>\n"); 1798 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "got: %s\n", str); 1799 return SCIP_OKAY; 1800 } 1801 1802 SCIPdebugMsg(scip, "binvarname=%s, zeroone=%d, slackstr=%s\n", binvarname, zeroone, slackstr); 1803 1804 /* get binary variable */ 1805 binvar = SCIPfindVar(scip, binvarname); 1806 if( binvar == NULL ) 1807 { 1808 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "unknown variable <%s>\n", binvarname); 1809 return SCIP_OKAY; 1810 } 1811 1812 /* resolve negation if necessary */ 1813 if( zeroone == 0 ) 1814 { 1815 SCIP_CALL( SCIPgetNegatedVar(scip, binvar, &binvar) ); 1816 } 1817 1818 /**@todo get slack constraint name and check whether constraint already exists; however, using only SCIPfindCons() is 1819 * not sufficient since slack constraints are not added to the problem; do we need something like 1820 * SCIPfindConsInConshdlr()?; currently, if there are two superindicator constraints with same slack constraint 1821 * (binvars may be different), then after writing and reading, the slack constraint will be created twice with 1822 * identical constraint name; this is not incorrect, but might consume more memory or time 1823 */ 1824 1825 /* parse slack constraint string */ 1826 SCIP_CALL( SCIPparseCons(scip, &slackcons, slackstr, initial, separate, enforce, check, propagate, local, modifiable, 1827 dynamic, removable, stickingatnode, success) ); 1828 1829 if( *success ) 1830 { 1831 assert(binvar != NULL); 1832 assert(slackcons != NULL); 1833 1834 /* create the superindicator constraint */ 1835 SCIP_CALL( SCIPcreateConsSuperindicator(scip, cons, name, binvar, slackcons, 1836 initial, separate, enforce, check, propagate, local, dynamic, removable, stickingatnode) ); 1837 1838 /* the new superindicator constraint captured the slack constraint, so we can release it now */ 1839 SCIP_CALL( SCIPreleaseCons(scip, &slackcons) ); 1840 } 1841 1842 return SCIP_OKAY; 1843 } 1844 1845 /** constraint method of constraint handler which returns the variables (if possible) */ 1846 static 1847 SCIP_DECL_CONSGETVARS(consGetVarsSuperindicator) 1848 { /*lint --e{715}*/ 1849 SCIP_CONSDATA* consdata; 1850 1851 consdata = SCIPconsGetData(cons); 1852 assert(consdata != NULL); 1853 1854 /* must be ready to hold at least the binary variable */ 1855 if( varssize <= 0 ) 1856 *success = FALSE; 1857 else 1858 { 1859 /* add binary variable */ 1860 vars[0] = consdata->binvar; 1861 1862 /* add variables of slack constraint */ 1863 SCIP_CALL( SCIPgetConsVars(scip, consdata->slackcons, &(vars[1]), varssize-1, success) ); 1864 } 1865 1866 return SCIP_OKAY; 1867 } 1868 1869 /** constraint method of constraint handler which returns the number of variables (if possible) */ 1870 static 1871 SCIP_DECL_CONSGETNVARS(consGetNVarsSuperindicator) 1872 { /*lint --e{715}*/ 1873 SCIP_CONSDATA* consdata; 1874 1875 consdata = SCIPconsGetData(cons); 1876 assert(consdata != NULL); 1877 1878 /* get number of variables in slack constraint */ 1879 SCIP_CALL( SCIPgetConsNVars(scip, consdata->slackcons, nvars, success) ); 1880 1881 /* add binary variable */ 1882 if( *success ) 1883 (*nvars)++; 1884 1885 return SCIP_OKAY; 1886 } 1887 1888 1889 /* 1890 * constraint specific interface methods 1891 */ 1892 1893 /** creates the handler for superindicator constraints and includes it in SCIP */ 1894 SCIP_RETCODE SCIPincludeConshdlrSuperindicator( 1895 SCIP* scip /**< SCIP data structure */ 1896 ) 1897 { 1898 SCIP_CONSHDLRDATA* conshdlrdata; 1899 SCIP_CONSHDLR* conshdlr; 1900 SCIP_DIALOG* root; 1901 SCIP_DIALOG* changemenu; 1902 SCIP_DIALOG* dialog; 1903 1904 /* create superindicator constraint handler data */ 1905 SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) ); 1906 1907 conshdlrdata->nrejects = 0; 1908 1909 /* include constraint handler */ 1910 SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC, 1911 CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY, CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS, 1912 consEnfolpSuperindicator, consEnfopsSuperindicator, consCheckSuperindicator, consLockSuperindicator, 1913 conshdlrdata) ); 1914 1915 assert(conshdlr != NULL); 1916 1917 /* set non-fundamental callbacks via specific setter functions */ 1918 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopySuperindicator, consCopySuperindicator) ); 1919 SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteSuperindicator) ); 1920 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeSuperindicator) ); 1921 SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsSuperindicator) ); 1922 SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsSuperindicator) ); 1923 SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpSuperindicator) ); 1924 SCIP_CALL( SCIPsetConshdlrInitpre(scip, conshdlr, consInitpreSuperindicator) ); 1925 SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseSuperindicator) ); 1926 SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolSuperindicator, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) ); 1927 SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintSuperindicator) ); 1928 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropSuperindicator, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP, CONSHDLR_PROP_TIMING) ); 1929 SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropSuperindicator) ); 1930 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpSuperindicator, consSepasolSuperindicator, CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, CONSHDLR_DELAYSEPA) ); 1931 SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransSuperindicator) ); 1932 SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxSuperindicator) ); 1933 1934 /* add dialogs if they are not disabled */ 1935 root = SCIPgetRootDialog(scip); 1936 if( root != NULL ) 1937 { 1938 /* find change menu */ 1939 if( !SCIPdialogHasEntry(root, "change") ) 1940 { 1941 SCIP_CALL( SCIPincludeDialog(scip, &changemenu, 1942 NULL, 1943 SCIPdialogExecMenu, NULL, NULL, 1944 "change", "change the problem", TRUE, NULL) ); 1945 SCIP_CALL( SCIPaddDialogEntry(scip, root, changemenu) ); 1946 SCIP_CALL( SCIPreleaseDialog(scip, &changemenu) ); 1947 } 1948 1949 if( SCIPdialogFindEntry(root, "change", &changemenu) != 1 ) 1950 { 1951 SCIPerrorMessage("change sub menu not found\n"); 1952 return SCIP_PLUGINNOTFOUND; 1953 } 1954 1955 /* add minuc dialog */ 1956 if( !SCIPdialogHasEntry(changemenu, "minuc") ) 1957 { 1958 SCIP_CALL( SCIPincludeDialog(scip, &dialog, 1959 NULL, 1960 SCIPdialogExecChangeMinUC, NULL, NULL, 1961 "minuc", "transforms the current problem into a MinUC problem minimizing the number of unsatisfied constraints", 1962 FALSE, NULL) ); 1963 SCIP_CALL( SCIPaddDialogEntry(scip, changemenu, dialog) ); 1964 SCIP_CALL( SCIPreleaseDialog(scip, &dialog) ); 1965 } 1966 } 1967 1968 /* add constraint handler parameters */ 1969 SCIP_CALL( SCIPaddBoolParam(scip, 1970 "constraints/" CONSHDLR_NAME "/checkslacktype", 1971 "should type of slack constraint be checked when creating superindicator constraint?", 1972 &conshdlrdata->checkslacktype, TRUE, DEFAULT_CHECKSLACKTYPE, NULL, NULL) ); 1973 1974 SCIP_CALL( SCIPaddRealParam(scip, 1975 "constraints/" CONSHDLR_NAME "/maxupgdcoeflinear", 1976 "maximum big-M coefficient of binary variable in upgrade to a linear constraint (relative to smallest coefficient)", 1977 &conshdlrdata->maxupgdcoeflinear, TRUE, DEFAULT_MAXUPGDCOEFLINEAR, 0.0, 1e15, NULL, NULL) ); 1978 1979 SCIP_CALL( SCIPaddIntParam(scip, 1980 "constraints/" CONSHDLR_NAME "/upgdprioindicator", 1981 "priority for upgrading to an indicator constraint (-1: never)", 1982 &conshdlrdata->upgdprioindicator, TRUE, DEFAULT_UPGDPRIOINDICATOR, -1, INT_MAX, NULL, NULL) ); 1983 1984 SCIP_CALL( SCIPaddIntParam(scip, 1985 "constraints/" CONSHDLR_NAME "/upgdpriolinear", 1986 "priority for upgrading to an indicator constraint (-1: never)", 1987 &conshdlrdata->upgdpriolinear, TRUE, DEFAULT_UPGDPRIOLINEAR, -1, INT_MAX, NULL, NULL) ); 1988 1989 return SCIP_OKAY; 1990 } 1991 1992 /** creates and captures a superindicator constraint 1993 * 1994 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 1995 */ 1996 SCIP_RETCODE SCIPcreateConsSuperindicator( 1997 SCIP* scip, /**< SCIP data structure */ 1998 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 1999 const char* name, /**< name of constraint */ 2000 SCIP_VAR* binvar, /**< pointer to the indicator constraint */ 2001 SCIP_CONS* slackcons, /**< constraint corresponding to the handled constraint */ 2002 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? 2003 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */ 2004 SCIP_Bool separate, /**< should the constraint be separated during LP processing? 2005 * Usually set to TRUE. */ 2006 SCIP_Bool enforce, /**< should the constraint be enforced during node processing? 2007 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 2008 SCIP_Bool check, /**< should the constraint be checked for feasibility? 2009 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 2010 SCIP_Bool propagate, /**< should the constraint be propagated during node processing? 2011 * Usually set to TRUE. */ 2012 SCIP_Bool local, /**< is constraint only valid locally? 2013 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */ 2014 SCIP_Bool dynamic, /**< is constraint subject to aging? 2015 * Usually set to FALSE. Set to TRUE for own cuts which 2016 * are separated as constraints. */ 2017 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? 2018 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */ 2019 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even 2020 * if it may be moved to a more global node? 2021 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */ 2022 ) 2023 { 2024 SCIP_CONSHDLRDATA* conshdlrdata; 2025 SCIP_CONSHDLR* conshdlr; 2026 SCIP_CONSDATA* consdata; 2027 SCIP_Bool modifiable; 2028 2029 assert(scip != NULL); 2030 assert(cons != NULL); 2031 assert(name != NULL); 2032 assert(binvar != NULL); 2033 assert(slackcons != NULL); 2034 2035 modifiable = FALSE; 2036 2037 /* find the superindicator constraint handler */ 2038 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME); 2039 if( conshdlr == NULL ) 2040 { 2041 SCIPerrorMessage("superindicator constraint handler not found\n"); 2042 return SCIP_PLUGINNOTFOUND; 2043 } 2044 2045 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2046 assert(conshdlrdata != NULL); 2047 2048 /* only allow types of slack constraints that can be handled */ 2049 if( conshdlrdata->checkslacktype && 2050 strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(slackcons)), "and") != 0 && 2051 strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(slackcons)), "bounddisjunction") != 0 && 2052 strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(slackcons)), "conjunction") != 0 && 2053 strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(slackcons)), "disjunction") != 0 && 2054 strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(slackcons)), "knapsack") != 0 && 2055 strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(slackcons)), "linear") != 0 && 2056 strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(slackcons)), "linking") != 0 && 2057 strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(slackcons)), "logicor") != 0 && 2058 strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(slackcons)), "nonlinear") != 0 && 2059 strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(slackcons)), "or") != 0 && 2060 strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(slackcons)), "SOS1") != 0 && 2061 strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(slackcons)), "SOS2") != 0 && 2062 strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(slackcons)), "cumulative") != 0 && 2063 strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(slackcons)), "varbound") != 0 && 2064 strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(slackcons)), "superindicator") != 0 2065 ) 2066 { 2067 if( conshdlrdata->nrejects < 5 ) 2068 { 2069 SCIPwarningMessage(scip, "rejected creation of superindicator with slack constraint <%s> of type <%s> " 2070 "(use parameter <checkslacktype> to disable check)\n", 2071 SCIPconsGetName(slackcons), SCIPconshdlrGetName(SCIPconsGetHdlr(slackcons))); 2072 conshdlrdata->nrejects++; 2073 } 2074 2075 if( conshdlrdata->nrejects == 5 ) 2076 { 2077 SCIPwarningMessage(scip, "suppressing further warning messages of this type\n"); 2078 conshdlrdata->nrejects++; 2079 } 2080 2081 return SCIP_INVALIDCALL; 2082 } 2083 2084 /* create constraint data */ 2085 SCIP_CALL( consdataCreateSuperindicator(scip, &consdata, binvar, slackcons) ); 2086 assert(consdata != NULL); 2087 2088 /* create constraint */ 2089 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate, 2090 local, modifiable, dynamic, removable, stickingatnode) ); 2091 2092 return SCIP_OKAY; 2093 } 2094 2095 /** creates and captures a superindicator constraint 2096 * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the 2097 * method SCIPcreateConsSuperindicator(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h 2098 * 2099 * @see SCIPcreateConsSuperindicator() for information about the basic constraint flag configuration 2100 * 2101 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 2102 */ 2103 SCIP_RETCODE SCIPcreateConsBasicSuperindicator( 2104 SCIP* scip, /**< SCIP data structure */ 2105 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 2106 const char* name, /**< name of constraint */ 2107 SCIP_VAR* binvar, /**< pointer to the indicator constraint */ 2108 SCIP_CONS* slackcons /**< constraint corresponding to the handled constraint */ 2109 ) 2110 { 2111 assert(scip != NULL); 2112 assert(cons != NULL); 2113 assert(name != NULL); 2114 assert(binvar != NULL); 2115 assert(slackcons != NULL); 2116 2117 SCIP_CALL( SCIPcreateConsSuperindicator(scip, cons, name, binvar, slackcons, 2118 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 2119 2120 return SCIP_OKAY; 2121 } 2122 2123 2124 /** gets binary variable corresponding to the general indicator constraint */ 2125 SCIP_VAR* SCIPgetBinaryVarSuperindicator( 2126 SCIP_CONS* cons /**< superindicator constraint */ 2127 ) 2128 { 2129 assert(cons != NULL); 2130 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0); 2131 assert(SCIPconsGetData(cons) != NULL); 2132 2133 return SCIPconsGetData(cons)->binvar; 2134 } 2135 2136 /** gets the slack constraint corresponding to the general indicator constraint */ 2137 SCIP_CONS* SCIPgetSlackConsSuperindicator( 2138 SCIP_CONS* cons /**< superindicator constraint */ 2139 ) 2140 { 2141 assert(cons != NULL); 2142 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0); 2143 assert(SCIPconsGetData(cons) != NULL); 2144 2145 return SCIPconsGetData(cons)->slackcons; 2146 } 2147 2148 2149 /* 2150 * constraint-dependent SCIP methods 2151 */ 2152 2153 /** transforms the current problem into a MinUC problem (minimizing the number of unsatisfied constraints), 2154 * a CIP generalization of the MinULR (min. unsatisfied linear relations) problem 2155 */ 2156 SCIP_RETCODE SCIPtransformMinUC( 2157 SCIP* scip, /**< SCIP data structure */ 2158 SCIP_Bool* success /**< pointer to store whether all constraints could be transformed */ 2159 ) 2160 { 2161 SCIP_CONS** conss; 2162 SCIP_CONS** probconss; 2163 SCIP_VAR** vars; 2164 char consname[SCIP_MAXSTRLEN]; 2165 char varname[SCIP_MAXSTRLEN]; 2166 int maxbranchprio; 2167 int ntransconss; 2168 int nconss; 2169 int nvars; 2170 int i; 2171 2172 assert(scip != NULL); 2173 assert(success != NULL); 2174 2175 *success = FALSE; 2176 2177 if( SCIPgetStage(scip) != SCIP_STAGE_PROBLEM ) 2178 { 2179 SCIPerrorMessage("method <SCIPtransformMinUC> can only be called in problem stage\n"); 2180 return SCIP_INVALIDCALL; 2181 } 2182 2183 /* get variable data */ 2184 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) ); 2185 2186 /* copy the conss array because it changes when adding and deleting constraints */ 2187 nconss = SCIPgetNConss(scip); 2188 probconss = SCIPgetConss(scip); 2189 SCIP_CALL( SCIPduplicateBufferArray(scip, &conss, probconss, nconss) ); 2190 2191 /* clear objective function and compute maximal branching priority */ 2192 maxbranchprio = 0; 2193 for( i = nvars-1; i >= 0; i-- ) 2194 { 2195 SCIP_CALL( SCIPchgVarObj(scip, vars[i], 0.0) ); 2196 2197 if( SCIPvarGetBranchPriority(vars[i]) > maxbranchprio ) 2198 maxbranchprio = SCIPvarGetBranchPriority(vars[i]); 2199 } 2200 2201 maxbranchprio++; 2202 2203 /* transform each constraint to slack constraint in a newly created superindicator constraint; note that we also need 2204 * to transform superindicator constraints, since their binary variable might have down-locks 2205 */ 2206 ntransconss = 0; 2207 for( i = 0; i < nconss; ++i ) 2208 { 2209 SCIP_CONS* cons; 2210 SCIP_CONS* supindcons; 2211 SCIP_VAR* binvar; 2212 SCIP_VAR* negbinvar; 2213 SCIP_RETCODE retcode; 2214 2215 cons = conss[i]; 2216 assert(cons != NULL); 2217 2218 /* create a new binary variable with objective coefficient one */ 2219 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "%s_master", SCIPconsGetName(cons)); 2220 2221 SCIP_CALL( SCIPcreateVar(scip, &binvar, varname, 0.0, 1.0, 1.0, SCIP_VARTYPE_BINARY, 2222 TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) ); 2223 2224 /* get negated variable, since we want to minimize the number of violated constraints */ 2225 SCIP_CALL( SCIPgetNegatedVar(scip, binvar, &negbinvar) ); 2226 2227 /* create superindicator constraint */ 2228 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_super", SCIPconsGetName(cons)); 2229 2230 retcode = SCIPcreateConsSuperindicator(scip, &supindcons, consname, negbinvar, cons, 2231 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons), SCIPconsIsChecked(cons), 2232 SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), 2233 SCIPconsIsStickingAtNode(cons)); 2234 2235 if( retcode == SCIP_OKAY ) 2236 { 2237 /* add binary variable and increase its branching priority */ 2238 SCIP_CALL( SCIPaddVar(scip, binvar) ); 2239 SCIP_CALL( SCIPchgVarBranchPriority(scip, binvar, maxbranchprio) ); 2240 2241 /* add superindicator constraint */ 2242 SCIP_CALL( SCIPaddCons(scip, supindcons) ); 2243 2244 /* release binary variable and superindicator constraint */ 2245 SCIP_CALL( SCIPreleaseVar(scip, &binvar) ); 2246 SCIP_CALL( SCIPreleaseCons(scip, &supindcons) ); 2247 2248 /* delete slack constraint; it is still captured by the superindicator constraint */ 2249 SCIP_CALL( SCIPdelCons(scip, cons) ); 2250 2251 ntransconss++; 2252 } 2253 else if( retcode == SCIP_INVALIDCALL ) 2254 { 2255 SCIPdebugMsg(scip, "constraint <%s> of type <%s> could not be transformed to superindicator and was removed\n", 2256 SCIPconsGetName(cons), SCIPconshdlrGetName(SCIPconsGetHdlr(cons))); 2257 2258 /* release binary variable */ 2259 SCIP_CALL( SCIPreleaseVar(scip, &binvar) ); 2260 2261 /* delete slack constraint; this is necessary, because, e.g., the indicator expects its linear slack constraint 2262 * present in the problem, but this has just be transformed; hence, it cannot function any more and we have to 2263 * remove it 2264 */ 2265 SCIP_CALL( SCIPdelCons(scip, cons) ); 2266 } 2267 else 2268 { 2269 /* return all other error codes */ 2270 SCIP_CALL( retcode ); 2271 } 2272 } 2273 2274 if( ntransconss == nconss ) 2275 *success = TRUE; 2276 2277 /* minimize the number of violated constraints */ 2278 SCIP_CALL( SCIPsetObjsense(scip, SCIP_OBJSENSE_MINIMIZE) ); 2279 2280 /* free the allocated memory for the copied constraint array */ 2281 SCIPfreeBufferArray(scip, &conss); 2282 2283 return SCIP_OKAY; 2284 } 2285 2286 2287 /* 2288 * constraint-dependent dialog entries 2289 */ 2290 2291 /** dialog execution method for the SCIPtransformMinUC() method */ 2292 SCIP_DECL_DIALOGEXEC(SCIPdialogExecChangeMinUC) 2293 { /*lint --e{715}*/ 2294 SCIP_Bool success; 2295 2296 SCIP_CALL( SCIPdialoghdlrAddHistory(dialoghdlr, dialog, NULL, FALSE) ); 2297 SCIPdialogMessage(scip, NULL, "\n"); 2298 2299 switch( SCIPgetStage(scip) ) 2300 { 2301 case SCIP_STAGE_INIT: 2302 SCIPdialogMessage(scip, NULL, "no problem exists\n"); 2303 break; 2304 case SCIP_STAGE_PROBLEM: 2305 SCIPdialogMessage(scip, NULL, "change problem to MinUC\n"); 2306 SCIPdialogMessage(scip, NULL, "==============\n"); 2307 2308 SCIP_CALL( SCIPtransformMinUC(scip, &success) ); 2309 2310 if( !success ) 2311 { 2312 SCIPdialogMessage(scip, NULL, "some constraints could not be transformed to superindicator constraints and were removed\n"); 2313 } 2314 2315 SCIPdialogMessage(scip, NULL, "\n"); 2316 SCIPdialogMessage(scip, NULL, "changed problem has %d variables (%d bin, %d int, %d impl, %d cont) and %d constraints\n", 2317 SCIPgetNVars(scip), SCIPgetNBinVars(scip), SCIPgetNIntVars(scip), SCIPgetNImplVars(scip), SCIPgetNContVars(scip), 2318 SCIPgetNConss(scip)); 2319 2320 SCIPdialogMessage(scip, NULL, "increased branching priority of new binary variables"); 2321 2322 break; 2323 case SCIP_STAGE_TRANSFORMED: 2324 case SCIP_STAGE_INITPRESOLVE: 2325 case SCIP_STAGE_PRESOLVING: 2326 case SCIP_STAGE_EXITPRESOLVE: 2327 case SCIP_STAGE_PRESOLVED: 2328 case SCIP_STAGE_SOLVING: 2329 case SCIP_STAGE_SOLVED: 2330 case SCIP_STAGE_TRANSFORMING: 2331 case SCIP_STAGE_INITSOLVE: 2332 case SCIP_STAGE_EXITSOLVE: 2333 case SCIP_STAGE_FREETRANS: 2334 case SCIP_STAGE_FREE: 2335 SCIPdialogMessage(scip, NULL, "problem has to be in problem stage to create MinUC problem\n"); 2336 break; 2337 default: 2338 SCIPerrorMessage("invalid SCIP stage\n"); 2339 return SCIP_INVALIDCALL; 2340 } /*lint --e{616}*/ 2341 2342 SCIPdialogMessage(scip, NULL, "\n"); 2343 *nextdialog = SCIPdialoghdlrGetRoot(dialoghdlr); 2344 2345 return SCIP_OKAY; 2346 } 2347