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_orbisack.c 26 * @ingroup DEFPLUGINS_CONS 27 * @brief constraint handler for orbisack constraints 28 * @author Christopher Hojny 29 * @author Jasper van Doornmalen 30 * 31 * 32 * The type of constraints of this constraint handler is described in cons_orbisack.h. 33 * 34 * The details of the method implemented here are described in the following papers: 35 * 36 * Describing Orbitopes by Linear Inequalities and Projection Based Tools@n 37 * Andreas Loos,@n 38 * PhD thesis, Otto-von-Guericke-Universitaet Magdeburg (2010). 39 * 40 * This thesis provides a complete linear description of orbisacks and a separation 41 * routine for its inequalities. 42 * 43 * Polytopes Associated with Symmetry Handling@n 44 * Christopher Hojny and Marc E. Pfetsch,@n 45 * (2017), preprint available at http://www.optimization-online.org/DB_HTML/2017/01/5835.html 46 * 47 * This paper describes a linear time separation routine for so-called cover inequalities of 48 * orbisacks. 49 */ 50 51 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 52 53 #include "blockmemshell/memory.h" 54 #include "scip/cons_orbisack.h" 55 #include "scip/cons_orbitope.h" 56 #include "scip/cons_setppc.h" 57 #include "scip/pub_cons.h" 58 #include "scip/pub_message.h" 59 #include "scip/pub_var.h" 60 #include "scip/scip.h" 61 #include "scip/scip_branch.h" 62 #include "scip/scip_conflict.h" 63 #include "scip/scip_cons.h" 64 #include "scip/scip_cut.h" 65 #include "scip/scip_general.h" 66 #include "scip/scip_lp.h" 67 #include "scip/scip_mem.h" 68 #include "scip/scip_message.h" 69 #include "scip/scip_numerics.h" 70 #include "scip/scip_param.h" 71 #include "scip/scip_sol.h" 72 #include "scip/scip_var.h" 73 #include "scip/symmetry.h" 74 75 76 /* constraint handler properties */ 77 #define CONSHDLR_NAME "orbisack" 78 #define CONSHDLR_DESC "symmetry breaking constraint handler for orbisacks" 79 #define CONSHDLR_SEPAPRIORITY +40100 /**< priority of the constraint handler for separation */ 80 #define CONSHDLR_ENFOPRIORITY -1005200 /**< priority of the constraint handler for constraint enforcing */ 81 #define CONSHDLR_CHECKPRIORITY -1005200 /**< priority of the constraint handler for checking feasibility */ 82 #define CONSHDLR_SEPAFREQ 5 /**< frequency for separating cuts; zero means to separate only in the root node */ 83 #define CONSHDLR_PROPFREQ 5 /**< frequency for propagating domains; zero means only preprocessing propagation */ 84 #define CONSHDLR_EAGERFREQ -1 /**< frequency for using all instead of only the useful constraints in separation, 85 * propagation and enforcement, -1 for no eager evaluations, 0 for first only */ 86 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */ 87 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */ 88 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */ 89 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */ 90 91 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP 92 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE 93 94 /* default parameters for separation routines: */ 95 #define DEFAULT_ORBISEPARATION FALSE /**< whether orbisack inequalities should be separated */ 96 #define DEFAULT_COVERSEPARATION TRUE /**< whether cover inequalities should be separated */ 97 98 /* default parameters for constraints */ 99 #define DEFAULT_COEFFBOUND 1000000.0 /**< maximum size of coefficients in orbisack inequalities */ 100 #define DEFAULT_PPORBISACK TRUE /**< whether we allow upgrading to packing/partitioning orbisacks */ 101 #define DEFAULT_FORCECONSCOPY FALSE /**< whether orbisack constraints should be forced to be copied to sub SCIPs */ 102 103 /* Constants to store fixings */ 104 #define FIXED0 1 /* When a variable is fixed to 0. */ 105 #define FIXED1 2 /* When a variable is fixed to 1. */ 106 #define UNFIXED 3 /* When a variable is neither fixed to 0 or to 1. */ 107 108 109 /* 110 * Data structures 111 */ 112 113 /** constraint handler data */ 114 struct SCIP_ConshdlrData 115 { 116 SCIP_Bool coverseparation; /**< whether only cover inequalities should be separated */ 117 SCIP_Bool orbiseparation; /**< whether orbisack as well as cover inequalities should be separated */ 118 SCIP_Real coeffbound; /**< maximum size of coefficients in orbisack inequalities */ 119 SCIP_Bool checkpporbisack; /**< whether we allow upgrading to packing/partitioning orbisacks */ 120 int maxnrows; /**< maximal number of rows in an orbisack constraint */ 121 SCIP_Bool forceconscopy; /**< whether orbisack constraints should be forced to be copied to sub SCIPs */ 122 }; 123 124 /** constraint data for orbisack constraints */ 125 struct SCIP_ConsData 126 { 127 SCIP_VAR** vars1; /**< first column of variable matrix */ 128 SCIP_VAR** vars2; /**< second column of variable matrix */ 129 int nrows; /**< number of rows of variable matrix */ 130 SCIP_Bool ismodelcons; /**< whether the orbisack is a model constraint */ 131 }; 132 133 134 /* 135 * Local methods 136 */ 137 138 /** frees orbisack constraint data */ 139 static 140 SCIP_RETCODE consdataFree( 141 SCIP* scip, /**< SCIP data structure */ 142 SCIP_CONSDATA** consdata /**< pointer to orbisack constraint data */ 143 ) 144 { 145 int nrows; 146 int i; 147 148 assert( consdata != NULL ); 149 assert( *consdata != NULL ); 150 151 nrows = (*consdata)->nrows; 152 153 /* release variables in vars1 and vars2 array */ 154 for (i = 0; i < nrows; ++i) 155 { 156 assert( (*consdata)->vars1[i] != NULL ); 157 SCIP_CALL( SCIPreleaseVar(scip, &(*consdata)->vars1[i] ) ); 158 159 assert( (*consdata)->vars2[i] != NULL ); 160 SCIP_CALL( SCIPreleaseVar(scip, &(*consdata)->vars2[i] ) ); 161 } 162 163 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vars2), nrows); 164 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vars1), nrows); 165 166 SCIPfreeBlockMemory(scip, consdata); 167 168 return SCIP_OKAY; 169 } 170 171 172 /** creates orbisack constraint data */ 173 static 174 SCIP_RETCODE consdataCreate( 175 SCIP* scip, /**< SCIP data structure */ 176 SCIP_CONSDATA** consdata, /**< pointer to store constraint data */ 177 SCIP_VAR*const* vars1, /**< first column of variable matrix */ 178 SCIP_VAR*const* vars2, /**< second column of variable matrix */ 179 int nrows, /**< number of rows in variable matrix */ 180 SCIP_Bool ismodelcons /**< whether the orbisack is a model constraint */ 181 ) 182 { 183 int i; 184 185 assert( consdata != NULL ); 186 187 SCIP_CALL( SCIPallocBlockMemory(scip, consdata) ); 188 189 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars1, vars1, nrows) ); 190 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars2, vars2, nrows) ); 191 192 #ifndef NDEBUG 193 { 194 for (i = 0; i < nrows; ++i) 195 { 196 assert( SCIPvarIsBinary(vars1[i]) ); 197 assert( SCIPvarIsBinary(vars2[i]) ); 198 } 199 } 200 #endif 201 202 (*consdata)->nrows = nrows; 203 (*consdata)->ismodelcons = ismodelcons; 204 205 /* get transformed variables, if we are in the transformed problem */ 206 if ( SCIPisTransformed(scip) ) 207 { 208 /* Make sure that all variables cannot be multiaggregated (cannot be handled by cons_orbisack, since one cannot 209 * easily eliminate single variables from an orbisack constraint. */ 210 for (i = 0; i < nrows; ++i) 211 { 212 SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->vars1[i], &(*consdata)->vars1[i]) ); 213 SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, (*consdata)->vars1[i]) ); 214 215 SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->vars2[i], &(*consdata)->vars2[i]) ); 216 SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, (*consdata)->vars2[i]) ); 217 } 218 } 219 220 /* capture vars in vars1 and vars2 array */ 221 for (i = 0; i < nrows; ++i) 222 { 223 SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->vars1[i] ) ); 224 SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->vars2[i] ) ); 225 } 226 227 return SCIP_OKAY; 228 } 229 230 231 /** check wether an orbisack is even a packing/partitioning orbisack */ 232 static 233 SCIP_RETCODE packingUpgrade( 234 SCIP* scip, /**< SCIP pointer */ 235 SCIP_VAR*const* vars1, /**< first column of matrix of variables on which the symmetry acts */ 236 SCIP_VAR*const* vars2, /**< variables of second column */ 237 int nrows, /**< number of rows of orbisack */ 238 SCIP_Bool* success, /**< memory address to store whether constraint can be upgraded */ 239 SCIP_Bool* isparttype /**< memory address to store whether upgraded orbisack is partitioning orbisack */ 240 ) 241 { 242 SCIP_VAR*** vars; 243 SCIP_ORBITOPETYPE type; 244 int i; 245 246 assert( scip != NULL ); 247 assert( vars1 != NULL ); 248 assert( vars2 != NULL ); 249 assert( success != NULL ); 250 assert( isparttype != NULL ); 251 252 *success = FALSE; 253 *isparttype = FALSE; 254 255 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nrows) ); 256 for (i = 0; i < nrows; ++i) 257 { 258 SCIP_CALL( SCIPallocBufferArray(scip, &vars[i], 2) ); 259 vars[i][0] = vars1[i]; 260 vars[i][1] = vars2[i]; 261 } 262 263 SCIP_CALL( SCIPisPackingPartitioningOrbitope(scip, vars, nrows, 2, NULL, NULL, &type) ); 264 265 if ( type == SCIP_ORBITOPETYPE_PACKING ) 266 *success = TRUE; 267 else if ( type == SCIP_ORBITOPETYPE_PARTITIONING ) 268 { 269 *success = TRUE; 270 *isparttype = TRUE; 271 } 272 273 for (i = nrows - 1; i >= 0; --i) 274 { 275 SCIPfreeBufferArray(scip, &vars[i]); 276 } 277 SCIPfreeBufferArray(scip, &vars); 278 279 return SCIP_OKAY; 280 } 281 282 283 /** generate initial LP cut 284 * 285 * We generate the inequality of the orbisack on the elements of the first row, i.e., 286 * the inequality \f$-x_{1,1} + x_{1,2} \leq 0\f$. 287 */ 288 static 289 SCIP_RETCODE initLP( 290 SCIP* scip, /**< SCIP pointer */ 291 SCIP_CONS* cons, /**< constraint */ 292 SCIP_Bool* infeasible /**< pointer to store whether we detected infeasibility */ 293 ) 294 { 295 SCIP_CONSDATA* consdata; 296 SCIP_VAR** vars1; 297 SCIP_VAR** vars2; 298 SCIP_VAR* tmpvars[2]; 299 SCIP_ROW* row; 300 301 assert( scip != NULL ); 302 assert( cons != NULL ); 303 assert( infeasible != NULL ); 304 305 *infeasible = FALSE; 306 307 consdata = SCIPconsGetData(cons); 308 assert( consdata != 0 ); 309 assert( consdata->nrows > 0 ); 310 assert( consdata->vars1 != NULL ); 311 assert( consdata->vars2 != NULL ); 312 313 vars1 = consdata->vars1; 314 vars2 = consdata->vars2; 315 316 tmpvars[0] = vars1[0]; 317 tmpvars[1] = vars2[0]; 318 319 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "orbisack0#0", -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) ); 320 SCIP_CALL( SCIPaddVarToRow(scip, row, tmpvars[0], -1.0) ); 321 SCIP_CALL( SCIPaddVarToRow(scip, row, tmpvars[1], 1.0) ); 322 323 SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) ); 324 #ifdef SCIP_DEBUG 325 SCIP_CALL( SCIPprintRow(scip, row, NULL) ); 326 #endif 327 SCIP_CALL( SCIPreleaseRow(scip, &row) ); 328 329 return SCIP_OKAY; 330 } 331 332 333 /** add orbisack cover inequality */ 334 static 335 SCIP_RETCODE addOrbisackCover( 336 SCIP* scip, /**< SCIP pointer */ 337 SCIP_CONS* cons, /**< constraint */ 338 int nrows, /**< number of rows of orbisack */ 339 SCIP_VAR*const* vars1, /**< first column of matrix of variables on which the symmetry acts */ 340 SCIP_VAR*const* vars2, /**< variables of second column */ 341 SCIP_Real* coeffs1, /**< coefficients of the variables of the first column of the inequality to be added */ 342 SCIP_Real* coeffs2, /**< coefficients of the variables of the second column of the inequality to be added */ 343 SCIP_Real rhs, /**< right-hand side of inequality to be added */ 344 SCIP_Bool* infeasible /**< pointer to store whether we detected infeasibility */ 345 ) 346 { 347 SCIP_ROW* row; 348 int i; 349 350 assert( scip != NULL ); 351 assert( cons != NULL ); 352 assert( vars1 != NULL ); 353 assert( vars2 != NULL ); 354 assert( coeffs1 != NULL ); 355 assert( coeffs2 != NULL ); 356 assert( infeasible != NULL ); 357 358 *infeasible = FALSE; 359 360 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "orbisackcover", -SCIPinfinity(scip), rhs, FALSE, FALSE, TRUE) ); 361 SCIP_CALL( SCIPcacheRowExtensions(scip, row) ); 362 for (i = 0; i < nrows; ++i) 363 { 364 SCIP_CALL( SCIPaddVarToRow(scip, row, vars1[i], coeffs1[i]) ); 365 SCIP_CALL( SCIPaddVarToRow(scip, row, vars2[i], coeffs2[i]) ); 366 } 367 SCIP_CALL( SCIPflushRowExtensions(scip, row) ); 368 369 SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) ); 370 #ifdef SCIP_DEBUG 371 SCIP_CALL( SCIPprintRow(scip, row, NULL) ); 372 #endif 373 SCIP_CALL( SCIPreleaseRow(scip, &row) ); 374 375 return SCIP_OKAY; 376 } 377 378 379 /** Separate lifted orbisack cover inequalities 380 * 381 * We currently do NOT enter cuts into the pool. 382 * 383 * We iterate over the nrows-many cover inequalities which are potentially 384 * maximal w.r.t. their violation. 385 */ 386 static 387 SCIP_RETCODE separateOrbisackCovers( 388 SCIP* scip, /**< SCIP pointer */ 389 SCIP_CONS* cons, /**< constraint */ 390 int nrows, /**< number of rows of orbisack */ 391 SCIP_VAR*const* vars1, /**< first column of matrix of variables on which the symmetry acts */ 392 SCIP_VAR*const* vars2, /**< variables of second column */ 393 SCIP_Real* vals1, /**< LP-solution for those variables in first column */ 394 SCIP_Real* vals2, /**< LP-solution for those variables in second column */ 395 int* ngen, /**< number of separated covers */ 396 SCIP_Bool* infeasible /**< pointer to store whether we detected infeasibility */ 397 ) 398 { 399 SCIP_Real rhs = 0.0; 400 SCIP_Real lhs = 0.0; 401 SCIP_Real* coeff1; 402 SCIP_Real* coeff2; 403 int i; 404 405 assert( scip != NULL ); 406 assert( cons != NULL ); 407 assert( nrows > 0 ); 408 assert( vars1 != NULL ); 409 assert( vars2 != NULL ); 410 assert( infeasible != NULL ); 411 assert( ngen != NULL ); 412 413 *infeasible = FALSE; 414 *ngen = 0; 415 416 /* allocate memory for inequality coefficients */ 417 SCIP_CALL( SCIPallocBufferArray(scip, &coeff1, nrows) ); 418 SCIP_CALL( SCIPallocBufferArray(scip, &coeff2, nrows) ); 419 420 /* initialize coefficient matrix */ 421 for (i = 0; i < nrows; ++i) 422 { 423 coeff1[i] = 0.0; 424 coeff2[i] = 0.0; 425 } 426 427 /* detect violated covers */ 428 for (i = 0; i < nrows; ++i) 429 { 430 /* cover inequality is violated */ 431 if ( SCIPisEfficacious(scip, -vals1[i] + vals2[i] + lhs - rhs) ) 432 { 433 /* set coefficients for inequality */ 434 coeff1[i] = -1.0; 435 coeff2[i] = 1.0; 436 437 SCIP_CALL( addOrbisackCover(scip, cons, nrows, vars1, vars2, coeff1, coeff2, rhs, infeasible) ); 438 ++(*ngen); 439 if ( *infeasible ) 440 break; 441 442 /* reset coefficients for next inequality */ 443 coeff1[i] = 0.0; 444 coeff2[i] = 0.0; 445 } 446 447 /* add argmax( 1 - vals[i][0], vals[i][1] ) as coefficient and ensure that both vars1[0] and vars2[0] are 448 * contained in the LIFTED cover inequality */ 449 if ( SCIPisEfficacious(scip, 1.0 - vals1[i] - vals2[i]) ) 450 { 451 coeff1[i] = -1.0; 452 lhs = lhs - vals1[i]; 453 454 /* lifting */ 455 if ( i == 0 ) 456 { 457 coeff2[0] = 1.0; 458 lhs += vals2[i]; 459 } 460 } 461 else 462 { 463 coeff2[i] = 1.0; 464 rhs += 1.0; 465 lhs = lhs + vals2[i]; 466 467 /* lifting */ 468 if ( i == 0 ) 469 { 470 coeff1[0] = -1.0; 471 lhs -= vals1[i]; 472 rhs -= 1.0; 473 } 474 } 475 } 476 477 /* free coefficient matrix */ 478 SCIPfreeBufferArray(scip, &coeff2); 479 SCIPfreeBufferArray(scip, &coeff1); 480 481 return SCIP_OKAY; 482 } 483 484 485 /** add orbisack inequality */ 486 static 487 SCIP_RETCODE addOrbisackInequality( 488 SCIP* scip, /**< SCIP pointer */ 489 SCIP_CONS* cons, /**< constraint */ 490 int nrows, /**< number of rows of orbisack */ 491 SCIP_VAR*const* vars1, /**< first column of matrix of variables on which the symmetry acts */ 492 SCIP_VAR*const* vars2, /**< variables of second column */ 493 SCIP_Real* coeffs1, /**< first column of coefficient matrix of inequality to be added */ 494 SCIP_Real* coeffs2, /**< second column of coefficient matrix of inequality to be added */ 495 SCIP_Real rhs, /**< right-hand side of inequality to be added */ 496 SCIP_Bool* infeasible /**< pointer to store whether we detected infeasibility */ 497 ) 498 { 499 SCIP_ROW* row; 500 int i; 501 502 assert( scip != NULL ); 503 assert( cons != NULL ); 504 assert( vars1 != NULL ); 505 assert( vars2 != NULL ); 506 assert( coeffs1 != NULL ); 507 assert( coeffs2 != NULL ); 508 assert( infeasible != NULL ); 509 510 *infeasible = FALSE; 511 512 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "orbisack", -SCIPinfinity(scip), rhs, FALSE, FALSE, TRUE) ); 513 SCIP_CALL( SCIPcacheRowExtensions(scip, row) ); 514 515 for (i = 0; i < nrows; ++i) 516 { 517 SCIP_CALL( SCIPaddVarToRow(scip, row, vars1[i], coeffs1[i]) ); 518 SCIP_CALL( SCIPaddVarToRow(scip, row, vars2[i], coeffs2[i]) ); 519 } 520 SCIP_CALL( SCIPflushRowExtensions(scip, row) ); 521 522 SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) ); 523 #ifdef SCIP_DEBUG 524 SCIP_CALL( SCIPprintRow(scip, row, NULL) ); 525 #endif 526 SCIP_CALL( SCIPreleaseRow(scip, &row) ); 527 528 return SCIP_OKAY; 529 } 530 531 532 /** separate orbisack inequalities 533 * 534 * We currently do NOT enter cuts into the pool. 535 * 536 * We stop if we checked for each possible basement row, whether a cut could be added. If the coefficients grow too 537 * large, we start separating cover inequalities. 538 * 539 * We implement the separation algorithm for orbisacks described in@n 540 * A. Loos. Describing Orbitopes by Linear Inequalities and Projection Based Tools. 541 * PhD thesis, Otto-von-Guericke-Universitaet Magdeburg, 2010. 542 */ 543 static 544 SCIP_RETCODE separateOrbisack( 545 SCIP* scip, /**< SCIP pointer */ 546 SCIP_CONS* cons, /**< constraint */ 547 int nrows, /**< number of rows of orbisack */ 548 SCIP_VAR*const* vars1, /**< first column of matrix of variables on which the symmetry acts */ 549 SCIP_VAR*const* vars2, /**< variables of second column */ 550 SCIP_Real* vals1, /**< LP-solution for those variables in first column */ 551 SCIP_Real* vals2, /**< LP-solution for those variables in second column */ 552 SCIP_Bool coverseparation, /**< whether we separate cover inequalities */ 553 SCIP_Real coeffbound, /**< maximum size of coefficients in orbisack inequalities */ 554 int* ngen, /**< pointer to store the number of generated cuts */ 555 SCIP_Bool* infeasible /**< pointer to store whether we detected infeasibility */ 556 ) 557 { 558 SCIP_Real* coeff1; 559 SCIP_Real* coeff2; 560 SCIP_Real rhs; 561 SCIP_Real lhs; 562 SCIP_Real valueA; 563 SCIP_Real valueB; 564 SCIP_Real valueC; 565 int basement; 566 int i; 567 568 assert( scip != NULL ); 569 assert( cons != NULL ); 570 assert( nrows > 0 ); 571 assert( vars1 != NULL ); 572 assert( vars2 != NULL ); 573 assert( coeffbound >= 0.0 ); 574 assert( ngen != NULL ); 575 assert( infeasible != NULL ); 576 577 *infeasible = FALSE; 578 *ngen = 0; 579 580 /* if there is only one row, all cuts are added by initLP */ 581 if ( nrows < 2 ) 582 return SCIP_OKAY; 583 584 /* allocate memory for inequality coefficients */ 585 SCIP_CALL( SCIPallocBufferArray(scip, &coeff1, nrows) ); 586 SCIP_CALL( SCIPallocBufferArray(scip, &coeff2, nrows) ); 587 588 /* initialize coefficient matrix row 0 */ 589 coeff1[0] = -1.0; 590 coeff2[0] = 1.0; 591 for (i = 2; i < nrows; ++i) 592 { 593 coeff1[i] = 0.0; 594 coeff2[i] = 0.0; 595 } 596 597 /* initialize right-hand side and left-hand side (lhs for row 0) */ 598 rhs = 0.0; 599 lhs = - vals1[0] + vals2[0]; 600 601 /* basement row of orbisack */ 602 basement = 1; 603 604 /* update value of left-hand side and coefficients for basement row = 1 */ 605 lhs += - vals1[1] + vals2[1]; 606 coeff1[1] = -1.0; 607 coeff2[1] = 1.0; 608 609 /* check whether cut for basement row = 1 is violated */ 610 if ( SCIPisEfficacious(scip, lhs - rhs) ) 611 { 612 SCIP_CALL( addOrbisackInequality(scip, cons, nrows, vars1, vars2, coeff1, coeff2, rhs, infeasible) ); 613 ++(*ngen); 614 } 615 616 /* check whether there exists a cut with basement rows > 1 that is violated */ 617 while ( basement < nrows - 1 && ! *infeasible ) 618 { 619 valueA = lhs + vals1[basement] - vals1[basement + 1] + vals2[basement + 1] - rhs - 1.0; /*lint !e679, !e834*/ 620 valueB = lhs - vals2[basement] - vals1[basement + 1] + vals2[basement + 1] - rhs; /*lint !e679, !e834*/ 621 valueC = 2.0 * lhs + vals1[basement] - vals2[basement] - vals1[basement + 1] + vals2[basement + 1] - 2.0 * rhs; /*lint !e679, !e834*/ 622 623 /* update inequality */ 624 if ( valueA >= valueB && valueA >= valueC ) 625 { 626 ++rhs; 627 coeff1[basement] = 0.0; 628 lhs += vals1[basement++]; 629 coeff1[basement] = -1.0; 630 coeff2[basement] = 1.0; 631 lhs += - vals1[basement] + vals2[basement]; 632 } 633 else if ( valueB >= valueA && valueB >= valueC ) 634 { 635 coeff2[basement] = 0.0; 636 lhs -= vals2[basement++]; 637 coeff1[basement] = -1.0; 638 coeff2[basement] = 1.0; 639 lhs += - vals1[basement] + vals2[basement]; 640 } 641 else 642 { 643 rhs *= 2.0; 644 lhs = 0.0; 645 for (i = 0; i < basement; ++i) 646 { 647 coeff1[i] = 2.0 * coeff1[i]; 648 coeff2[i] = 2.0 * coeff2[i]; 649 lhs += coeff1[i] * vals1[i] + coeff2[i] * vals2[i]; 650 } 651 coeff1[basement] = -1.0; 652 coeff2[basement] = 1.0; 653 lhs -= vals1[basement]; 654 lhs += vals2[basement++]; 655 coeff1[basement] = -1.0; 656 coeff2[basement] = 1.0; 657 lhs -= vals1[basement]; 658 lhs += vals2[basement]; 659 } 660 661 /* to avoid numerical troubles, we bound the size of coefficients and rhs */ 662 if ( rhs > coeffbound || -coeff1[0] > coeffbound || coeff2[0] > coeffbound ) 663 { 664 /* avoid separating cover inequalities twice */ 665 if ( ! coverseparation ) 666 { 667 int ncuts; 668 SCIP_CALL( separateOrbisackCovers(scip, cons, nrows, vars1, vars2, vals1, vals2, &ncuts, infeasible) ); 669 *ngen += ncuts; 670 } 671 break; 672 } 673 674 /* if current inequality is violated */ 675 if ( SCIPisEfficacious(scip, lhs - rhs) ) 676 { 677 SCIP_CALL( addOrbisackInequality(scip, cons, nrows, vars1, vars2, coeff1, coeff2, rhs, infeasible) ); 678 ++(*ngen); 679 } 680 } 681 682 /* free allocated memory */ 683 SCIPfreeBufferArray(scip, &coeff2); 684 SCIPfreeBufferArray(scip, &coeff1); 685 686 return SCIP_OKAY; 687 } 688 689 690 /** Determines if a vector with additional fixings could exist that is lexicographically larger than another vector. 691 * 692 * Given two vectors of variables with local lower and upper bounds, and a set of additional (virtual) fixings. 693 * Assuming that the entries of both vectors are equal until entry "start", this function determines if there exists 694 * a vector where the left vector is lexicographically larger or equal to the right vector. 695 * If a vector exsits, infeasible is set to FALSE, otherwise TRUE. 696 */ 697 static 698 SCIP_RETCODE checkFeasible( 699 SCIP* scip, /**< SCIP pointer */ 700 SCIP_VAR** vars1, /**< array of variables in first vector */ 701 SCIP_VAR** vars2, /**< array of variables in second vector */ 702 int nrows, /**< number of rows */ 703 int start, /**< at which row to start (assuming previous rows are equal) */ 704 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is detected in these fixings */ 705 int* infeasiblerow /**< pointer to store at which row a (0, 1) pattern is found */ 706 ) 707 { 708 SCIP_VAR* var1; 709 SCIP_VAR* var2; 710 int var1fix; 711 int var2fix; 712 int i; 713 714 assert( scip != NULL ); 715 assert( vars1 != NULL ); 716 assert( vars2 != NULL ); 717 assert( infeasible != NULL ); 718 assert( start >= 0 ); 719 720 *infeasible = FALSE; 721 722 for (i = start; i < nrows; ++i) 723 { 724 /* get variables of first and second vector */ 725 var1 = vars1[i]; 726 var2 = vars2[i]; 727 728 assert( var1 != NULL ); 729 assert( var2 != NULL ); 730 731 /* Get virtual fixing of variable in first vector, for var1 */ 732 if ( SCIPvarGetUbLocal(var1) < 0.5 ) 733 { 734 var1fix = FIXED0; 735 assert( SCIPvarGetLbLocal(var1) <= 0.5 ); 736 } 737 else if ( SCIPvarGetLbLocal(var1) > 0.5 ) 738 var1fix = FIXED1; 739 else 740 var1fix = UNFIXED; 741 742 /* Get virtual fixing of variable in second vector, for var2 */ 743 if ( SCIPvarGetUbLocal(var2) < 0.5 ) 744 { 745 var2fix = FIXED0; 746 assert( SCIPvarGetLbLocal(var2) <= 0.5 ); 747 } 748 else if ( SCIPvarGetLbLocal(var2) > 0.5 ) 749 var2fix = FIXED1; 750 else 751 var2fix = UNFIXED; 752 753 /* Encounter one of (_, _), (_, 0), (1, _), (1, 0). In all cases (1, 0) can be constructed. Thus feasible. */ 754 if ( var1fix != FIXED0 && var2fix != FIXED1 ) 755 break; 756 /* Encounter (0, 1). Infeasible. */ 757 else if ( var1fix == FIXED0 && var2fix == FIXED1 ) 758 { 759 *infeasible = TRUE; 760 *infeasiblerow = i; 761 break; 762 } 763 /* Remaining cases are (0, _), (_, 1), (0, 0) and (1, 1). In all cases: continue. */ 764 } 765 766 return SCIP_OKAY; 767 } 768 769 770 /** propagation */ 771 static 772 SCIP_RETCODE propVariables( 773 SCIP* scip, /**< SCIP pointer */ 774 SCIP_CONS* cons, /**< constraint to be propagated */ 775 SCIP_Bool* infeasible, /**< pointer to store whether it was detected that the node is infeasible */ 776 SCIP_Bool* found, /**< pointer to store whether a new propagation could be found */ 777 int* ngen /**< pointer to store the number of generated bound strengthenings */ 778 ) 779 { 780 SCIP_CONSDATA* consdata; 781 SCIP_VAR** vars1; 782 SCIP_VAR** vars2; 783 SCIP_VAR* var1; 784 SCIP_VAR* var2; 785 int var1fix; 786 int var2fix; 787 SCIP_Bool tightened; 788 SCIP_Bool peekinfeasible; 789 int peekinfeasiblerow; 790 int nrows; 791 int i; 792 793 assert( scip != NULL ); 794 assert( cons != NULL ); 795 assert( infeasible != NULL ); 796 assert( ngen != NULL ); 797 assert( found != NULL ); 798 799 SCIPdebugMsg(scip, "Propagating variables of constraint <%s>.\n", SCIPconsGetName(cons)); 800 801 *ngen = 0; 802 *infeasible = FALSE; 803 *found = FALSE; 804 805 /* get data of constraint */ 806 consdata = SCIPconsGetData(cons); 807 assert( consdata != NULL ); 808 assert( consdata->vars1 != NULL ); 809 assert( consdata->vars2 != NULL ); 810 assert( consdata->nrows > 0 ); 811 812 nrows = consdata->nrows; 813 vars1 = consdata->vars1; 814 vars2 = consdata->vars2; 815 816 /* loop through all variables */ 817 for (i = 0; i < nrows; ++i) 818 { 819 /* get variables of first and second column */ 820 var1 = vars1[i]; 821 var2 = vars2[i]; 822 assert( var1 != NULL ); 823 assert( var2 != NULL ); 824 825 /* Get the fixing status of the left column variable var1 */ 826 if ( SCIPvarGetUbLocal(var1) < 0.5 ) 827 { 828 var1fix = FIXED0; 829 assert( SCIPvarGetLbLocal(var1) <= 0.5 ); 830 } 831 else if ( SCIPvarGetLbLocal(var1) > 0.5 ) 832 var1fix = FIXED1; 833 else 834 var1fix = UNFIXED; 835 836 /* Get the fixing status of the right column variable var2 */ 837 if ( SCIPvarGetUbLocal(var2) < 0.5 ) 838 { 839 var2fix = FIXED0; 840 assert( SCIPvarGetLbLocal(var2) <= 0.5 ); 841 } 842 else if ( SCIPvarGetLbLocal(var2) > 0.5 ) 843 var2fix = FIXED1; 844 else 845 var2fix = UNFIXED; 846 847 /* Encounter one of (1, 0). All above rows are constant. This is a feasible situation. Stop. */ 848 if ( var1fix == FIXED1 && var2fix == FIXED0 ) 849 { 850 assert( SCIPvarGetLbLocal(var1) > 0.5 ); 851 assert( SCIPvarGetUbLocal(var2) < 0.5 ); 852 853 SCIPdebugMsg(scip, "Row %d is (1, 0)\n", i); 854 break; 855 } 856 /* Encounter one of (_, _), (_, 0), (1, _). Check if a constant row is possible, otherwise fix to (1, 0). */ 857 if ( var1fix != FIXED0 && var2fix != FIXED1 ) 858 { 859 assert( SCIPvarGetUbLocal(var1) > 0.5 ); 860 assert( SCIPvarGetLbLocal(var2) < 0.5 ); 861 862 SCIPdebugMsg(scip, "Row %d is (_, _), (_, 0) or (1, _).\n", i); 863 864 SCIP_CALL( checkFeasible(scip, vars1, vars2, nrows, i + 1, &peekinfeasible, &peekinfeasiblerow) ); 865 866 if ( peekinfeasible ) 867 { 868 /* If row i is constant, then we end up in an infeasible solution. Hence, row i must be (1, 0). */ 869 SCIPdebugMsg(scip, "Making row %d constant is infeasible. Fix to (1, 0).\n", i); 870 871 assert( peekinfeasiblerow > i ); 872 assert( peekinfeasiblerow < nrows ); 873 874 if ( var1fix != FIXED1 ) 875 { 876 /* Fix variable in first column to 1 */ 877 SCIP_CALL( SCIPinferVarLbCons(scip, var1, 1.0, cons, i + nrows * peekinfeasiblerow, FALSE, infeasible, 878 &tightened) ); /*lint !e713*/ 879 assert( ! *infeasible ); 880 881 *found = *found || tightened; 882 if ( tightened ) 883 ++(*ngen); 884 } 885 886 if ( var2fix != FIXED0 ) 887 { 888 /* Fix variable in second column to 0 */ 889 SCIP_CALL( SCIPinferVarUbCons(scip, var2, 0.0, cons, i + nrows * peekinfeasiblerow, FALSE, infeasible, 890 &tightened) ); /*lint !e713*/ 891 assert( ! *infeasible ); 892 893 *found = *found || tightened; 894 if ( tightened ) 895 ++(*ngen); 896 } 897 } 898 899 /* In all cases, we could make this row (1, 0), so it is feasible. Stop. */ 900 break; 901 } 902 /* Encounter (0, 1): if variable in first column is fixed to 0 and variable in second column is fixed to 1 */ 903 else if ( var1fix == FIXED0 && var2fix == FIXED1 ) 904 { 905 assert( SCIPvarGetUbLocal(var1) < 0.5 ); 906 assert( SCIPvarGetLbLocal(var2) > 0.5 ); 907 908 SCIPdebugMsg(scip, "Row %d is (0, 1). Infeasible!\n", i); 909 910 /* Mark solution as infeasible. */ 911 *infeasible = TRUE; 912 913 /* Perform conflict analysis */ 914 if ( SCIPisConflictAnalysisApplicable(scip) ) 915 { 916 SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) ); 917 918 /* Mark all variables from row i and above as part of the conflict */ 919 while (i >= 0) 920 { 921 SCIP_CALL( SCIPaddConflictBinvar(scip, vars1[i]) ); 922 SCIP_CALL( SCIPaddConflictBinvar(scip, vars2[i--]) ); /*lint !e850*/ 923 } 924 925 SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) ); 926 } 927 928 break; 929 } 930 /* Encounter (0, _): Fix second part to 0 */ 931 else if ( var1fix == FIXED0 && var2fix != FIXED0 ) 932 { 933 assert( SCIPvarGetUbLocal(var1) < 0.5 ); 934 assert( SCIPvarGetLbLocal(var2) < 0.5 ); 935 assert( SCIPvarGetUbLocal(var2) > 0.5 ); 936 937 SCIPdebugMsg(scip, "Row %d is (0, _). Fixing to (0, 0).\n", i); 938 939 SCIP_CALL( SCIPinferVarUbCons(scip, var2, 0.0, cons, i, FALSE, infeasible, &tightened) ); /*lint !e713*/ 940 assert( ! *infeasible ); 941 942 *found = *found || tightened; 943 if ( tightened ) 944 ++(*ngen); 945 } 946 /* Encounter (_, 1): fix first part to 1 */ 947 else if ( var1fix != FIXED1 && var2fix == FIXED1 ) 948 { 949 assert( SCIPvarGetLbLocal(var1) < 0.5 ); 950 assert( SCIPvarGetUbLocal(var1) > 0.5 ); 951 assert( SCIPvarGetLbLocal(var2) > 0.5 ); 952 953 SCIPdebugMsg(scip, "Row %d is (_, 1). Fixing to (1, 1).\n", i); 954 955 SCIP_CALL( SCIPinferVarLbCons(scip, var1, 1.0, cons, i, FALSE, infeasible, &tightened) ); /*lint !e713*/ 956 assert( ! *infeasible ); 957 958 *found = *found || tightened; 959 if ( tightened ) 960 ++(*ngen); 961 } 962 /* Remaining cases are (0, 0) and (1, 1). In these cases we can continue! */ 963 } 964 965 SCIPdebugMsg(scip, "No further fixings possible. Stopping at row %d\n", i); 966 return SCIP_OKAY; 967 } 968 969 970 /** separate orbisack and cover inequalities */ 971 static 972 SCIP_RETCODE separateInequalities( 973 SCIP* scip, /**< pointer to scip */ 974 SCIP_RESULT* result, /**< pointer to store the result of separation */ 975 SCIP_CONS* cons, /**< constraint */ 976 int nrows, /**< number of rows of orbisack */ 977 SCIP_VAR*const* vars1, /**< first column of matrix of variables on which the symmetry acts */ 978 SCIP_VAR*const* vars2, /**< variables of second column */ 979 SCIP_Real* vals1, /**< LP-solution for those variables in first column */ 980 SCIP_Real* vals2 /**< LP-solution for those variables in second column */ 981 ) 982 { 983 SCIP_CONSHDLRDATA* conshdlrdata; 984 SCIP_Bool infeasible = FALSE; 985 int ngen1 = 0; 986 int ngen2 = 0; 987 988 assert( scip != NULL ); 989 assert( result != NULL ); 990 assert( cons != NULL ); 991 assert( vars1 != NULL ); 992 assert( vars2 != NULL ); 993 assert( vals1 != NULL ); 994 assert( vals2 != NULL ); 995 996 conshdlrdata = SCIPconshdlrGetData(SCIPconsGetHdlr(cons)); 997 assert( conshdlrdata != NULL ); 998 999 if ( conshdlrdata->orbiseparation ) 1000 { 1001 SCIP_CALL( separateOrbisack(scip, cons, nrows, vars1, vars2, vals1, vals2, FALSE, conshdlrdata->coeffbound, &ngen1, &infeasible) ); 1002 } 1003 1004 if ( ! infeasible && conshdlrdata->coverseparation ) 1005 { 1006 SCIP_CALL( separateOrbisackCovers(scip, cons, nrows, vars1, vars2, vals1, vals2, &ngen2, &infeasible) ); 1007 } 1008 1009 if ( infeasible ) 1010 { 1011 *result = SCIP_CUTOFF; 1012 return SCIP_OKAY; 1013 } 1014 1015 if ( ngen1 + ngen2 > 0 ) 1016 *result = SCIP_SEPARATED; 1017 1018 return SCIP_OKAY; 1019 } 1020 1021 1022 /*-------------------------------------------------------------------------------------------- 1023 *--------------------------------- SCIP functions ------------------------------------------- 1024 *--------------------------------------------------------------------------------------------*/ 1025 1026 /** copy method for constraint handler plugins (called when SCIP copies plugins) */ 1027 static 1028 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyOrbisack) 1029 { /*lint --e{715}*/ 1030 assert(scip != NULL); 1031 assert(conshdlr != NULL); 1032 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0); 1033 1034 /* call inclusion method of constraint handler */ 1035 SCIP_CALL( SCIPincludeConshdlrOrbisack(scip) ); 1036 1037 *valid = TRUE; 1038 1039 return SCIP_OKAY; 1040 } 1041 1042 /** frees specific constraint data */ 1043 static 1044 SCIP_DECL_CONSDELETE(consDeleteOrbisack) 1045 { /*lint --e{715}*/ 1046 assert( scip != 0 ); 1047 assert( conshdlr != 0 ); 1048 assert( consdata != 0 ); 1049 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1050 1051 SCIP_CALL( consdataFree(scip, consdata) ); 1052 1053 return SCIP_OKAY; 1054 } 1055 1056 1057 /** frees constraint handler */ 1058 static 1059 SCIP_DECL_CONSFREE(consFreeOrbisack) 1060 { /*lint --e{715}*/ 1061 SCIP_CONSHDLRDATA* conshdlrdata; 1062 1063 assert( scip != 0 ); 1064 assert( conshdlr != 0 ); 1065 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1066 1067 conshdlrdata = SCIPconshdlrGetData(conshdlr); 1068 assert( conshdlrdata != NULL ); 1069 1070 SCIPfreeBlockMemory(scip, &conshdlrdata); 1071 1072 return SCIP_OKAY; 1073 } 1074 1075 1076 /** transforms constraint data into data belonging to the transformed problem */ 1077 static 1078 SCIP_DECL_CONSTRANS(consTransOrbisack) 1079 { 1080 SCIP_CONSDATA* sourcedata; 1081 SCIP_CONSDATA* consdata = NULL; 1082 1083 assert( scip != NULL ); 1084 assert( conshdlr != NULL ); 1085 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1086 assert( sourcecons != NULL ); 1087 assert( targetcons != NULL ); 1088 1089 SCIPdebugMsg(scip, "Transforming constraint.\n"); 1090 1091 /* get data of original constraint */ 1092 sourcedata = SCIPconsGetData(sourcecons); 1093 1094 /* create constraint data */ 1095 SCIP_CALL( consdataCreate(scip, &consdata, sourcedata->vars1, sourcedata->vars2, 1096 sourcedata->nrows, sourcedata->ismodelcons) ); 1097 1098 /* create transformed constraint */ 1099 SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, consdata, 1100 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), 1101 SCIPconsIsEnforced(sourcecons), SCIPconsIsChecked(sourcecons), 1102 SCIPconsIsPropagated(sourcecons), SCIPconsIsLocal(sourcecons), 1103 SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons), 1104 SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) ); 1105 1106 return SCIP_OKAY; 1107 } 1108 1109 1110 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */ 1111 static 1112 SCIP_DECL_CONSINITLP(consInitlpOrbisack) 1113 { 1114 int c; 1115 1116 assert( infeasible != NULL ); 1117 *infeasible = FALSE; 1118 1119 assert( scip != 0 ); 1120 assert( conshdlr != 0 ); 1121 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1122 1123 /* loop through constraints */ 1124 for (c = 0; c < nconss; ++c) 1125 { 1126 assert( conss[c] != 0 ); 1127 1128 SCIPdebugMsg(scip, "Generating initial orbisack cut for constraint <%s> ...\n", SCIPconsGetName(conss[c])); 1129 1130 SCIP_CALL( initLP(scip, conss[c], infeasible) ); 1131 if ( *infeasible ) 1132 break; 1133 1134 SCIPdebugMsg(scip, "Generated initial orbisack cut.\n"); 1135 } 1136 1137 return SCIP_OKAY; 1138 } 1139 1140 1141 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */ 1142 static 1143 SCIP_DECL_CONSINITSOL(consInitsolOrbisack) 1144 { 1145 SCIP_CONSHDLRDATA* conshdlrdata; 1146 int c; 1147 1148 assert( scip != NULL ); 1149 assert( conshdlr != NULL ); 1150 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1151 1152 /* determine maximum number of rows in an orbisack constraint */ 1153 conshdlrdata = SCIPconshdlrGetData(conshdlr); 1154 assert( conshdlrdata != NULL ); 1155 1156 conshdlrdata->maxnrows = 0; 1157 1158 /* loop through constraints */ 1159 for (c = 0; c < nconss; ++c) 1160 { 1161 SCIP_CONSDATA* consdata; 1162 1163 assert( conss[c] != NULL ); 1164 1165 consdata = SCIPconsGetData(conss[c]); 1166 assert( consdata != NULL ); 1167 1168 /* update conshdlrdata if necessary */ 1169 if ( consdata->nrows > conshdlrdata->maxnrows ) 1170 conshdlrdata->maxnrows = consdata->nrows; 1171 } 1172 1173 return SCIP_OKAY; 1174 } 1175 1176 1177 /** separation method of constraint handler for LP solution */ 1178 static 1179 SCIP_DECL_CONSSEPALP(consSepalpOrbisack) 1180 { /*lint --e{715}*/ 1181 SCIP_CONSDATA* consdata; 1182 SCIP_Real* vals1; 1183 SCIP_Real* vals2; 1184 int c; 1185 1186 assert( scip != NULL ); 1187 assert( conshdlr != NULL ); 1188 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1189 assert( result != NULL ); 1190 1191 SCIPdebugMsg(scip, "Separation method for orbisack constraints.\n"); 1192 1193 *result = SCIP_DIDNOTRUN; 1194 1195 /* if solution is not integer */ 1196 if ( SCIPgetNLPBranchCands(scip) > 0 ) 1197 { 1198 SCIP_CONSHDLRDATA* conshdlrdata; 1199 int nvals; 1200 1201 *result = SCIP_DIDNOTFIND; 1202 1203 conshdlrdata = SCIPconshdlrGetData(conshdlr); 1204 assert( conshdlrdata != NULL ); 1205 1206 nvals = conshdlrdata->maxnrows; 1207 assert( nvals > 0 ); 1208 1209 SCIP_CALL( SCIPallocBufferArray(scip, &vals1, nvals) ); 1210 SCIP_CALL( SCIPallocBufferArray(scip, &vals2, nvals) ); 1211 1212 /* loop through constraints */ 1213 for (c = 0; c < nconss; ++c) 1214 { 1215 /* get data of constraint */ 1216 assert( conss[c] != NULL ); 1217 consdata = SCIPconsGetData(conss[c]); 1218 1219 /* get solution */ 1220 SCIP_CALL( SCIPgetSolVals(scip, NULL, consdata->nrows, consdata->vars1, vals1) ); 1221 SCIP_CALL( SCIPgetSolVals(scip, NULL, consdata->nrows, consdata->vars2, vals2) ); 1222 1223 SCIPdebugMsg(scip, "Separating orbisack constraint <%s> ...\n", SCIPconsGetName(conss[c])); 1224 1225 SCIP_CALL( separateInequalities(scip, result, conss[c], consdata->nrows, consdata->vars1, consdata->vars2, vals1, vals2) ); 1226 1227 if ( *result == SCIP_CUTOFF ) 1228 break; 1229 } 1230 1231 SCIPfreeBufferArray(scip, &vals2); 1232 SCIPfreeBufferArray(scip, &vals1); 1233 } 1234 1235 return SCIP_OKAY; 1236 } 1237 1238 1239 /** separation method of constraint handler for arbitrary primal solution */ 1240 static 1241 SCIP_DECL_CONSSEPASOL(consSepasolOrbisack) 1242 { /*lint --e{715}*/ 1243 SCIP_CONSDATA* consdata; 1244 SCIP_Real* vals1; 1245 SCIP_Real* vals2; 1246 int c; 1247 1248 assert( scip != NULL ); 1249 assert( conshdlr != NULL ); 1250 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1251 assert( result != NULL ); 1252 1253 SCIPdebugMsg(scip, "Separation method for orbisack constraints\n"); 1254 1255 *result = SCIP_DIDNOTFIND; 1256 1257 if ( nconss > 0 ) 1258 { 1259 SCIP_CONSHDLRDATA* conshdlrdata; 1260 int nvals; 1261 1262 conshdlrdata = SCIPconshdlrGetData(conshdlr); 1263 assert( conshdlrdata != NULL ); 1264 1265 nvals = conshdlrdata->maxnrows; 1266 assert( nvals > 0 ); 1267 1268 SCIP_CALL( SCIPallocBufferArray(scip, &vals1, nvals) ); 1269 SCIP_CALL( SCIPallocBufferArray(scip, &vals2, nvals) ); 1270 1271 /* loop through constraints */ 1272 for (c = 0; c < nconss; ++c) 1273 { 1274 /* get data of constraint */ 1275 assert( conss[c] != NULL ); 1276 consdata = SCIPconsGetData(conss[c]); 1277 1278 /* get solution */ 1279 assert( consdata->nrows <= nvals ); 1280 SCIP_CALL( SCIPgetSolVals(scip, sol, consdata->nrows, consdata->vars1, vals1) ); 1281 SCIP_CALL( SCIPgetSolVals(scip, sol, consdata->nrows, consdata->vars2, vals2) ); 1282 1283 SCIPdebugMsg(scip, "Separating orbisack constraint <%s> ...\n", SCIPconsGetName(conss[c])); 1284 1285 SCIP_CALL( separateInequalities(scip, result, conss[c], consdata->nrows, consdata->vars1, consdata->vars2, vals1, vals2) ); 1286 if ( *result == SCIP_CUTOFF ) 1287 break; 1288 } 1289 1290 SCIPfreeBufferArray(scip, &vals2); 1291 SCIPfreeBufferArray(scip, &vals1); 1292 } 1293 1294 return SCIP_OKAY; 1295 } 1296 1297 1298 /** constraint enforcing method of constraint handler for LP solutions 1299 * 1300 * @pre It is assumed that the solution is integral (this can be ensured by appropriate priorities). 1301 */ 1302 static 1303 SCIP_DECL_CONSENFOLP(consEnfolpOrbisack) 1304 { /*lint --e{715}*/ 1305 SCIP_CONSDATA* consdata; 1306 SCIP_Bool infeasible = FALSE; 1307 SCIP_Real* vals1; 1308 SCIP_Real* vals2; 1309 int ngen = 0; 1310 int c; 1311 1312 assert( scip != 0 ); 1313 assert( conshdlr != 0 ); 1314 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1315 assert( result != 0 ); 1316 1317 SCIPdebugMsg(scip, "Enfolp method for orbisack constraints\n"); 1318 1319 /* we have a negative priority, so we should come after the integrality conshdlr. */ 1320 assert( SCIPgetNLPBranchCands(scip) == 0 ); 1321 1322 *result = SCIP_FEASIBLE; 1323 1324 if ( nconss > 0 ) 1325 { 1326 SCIP_CONSHDLRDATA* conshdlrdata; 1327 int nvals; 1328 1329 conshdlrdata = SCIPconshdlrGetData(conshdlr); 1330 assert( conshdlrdata != NULL ); 1331 1332 nvals = conshdlrdata->maxnrows; 1333 assert( nvals > 0 ); 1334 1335 SCIP_CALL( SCIPallocBufferArray(scip, &vals1, nvals) ); 1336 SCIP_CALL( SCIPallocBufferArray(scip, &vals2, nvals) ); 1337 1338 /* loop through constraints */ 1339 for (c = 0; c < nconss; ++c) 1340 { 1341 /* get data of constraint */ 1342 assert( conss[c] != 0 ); 1343 consdata = SCIPconsGetData(conss[c]); 1344 assert( consdata != NULL ); 1345 1346 /* do not enforce non-model constraints */ 1347 if ( !consdata->ismodelcons ) 1348 continue; 1349 1350 /* get solution */ 1351 assert( consdata->nrows <= nvals ); 1352 SCIP_CALL( SCIPgetSolVals(scip, NULL, consdata->nrows, consdata->vars1, vals1) ); 1353 SCIP_CALL( SCIPgetSolVals(scip, NULL, consdata->nrows, consdata->vars2, vals2) ); 1354 1355 SCIPdebugMsg(scip, "Enforcing orbisack constraint <%s> ...\n", SCIPconsGetName(conss[c])); 1356 1357 /* Separate only cover inequalities to ensure that enforcing works correctly. */ 1358 /* Otherwise, it may happen that infeasible solutions cannot be detected, since */ 1359 /* we bound the size of the coefficients for the orbisack inequalities. */ 1360 SCIP_CALL( separateOrbisackCovers(scip, conss[c], consdata->nrows, consdata->vars1, consdata->vars2, vals1, vals2, &ngen, &infeasible) ); 1361 1362 if ( infeasible ) 1363 { 1364 *result = SCIP_CUTOFF; 1365 break; 1366 } 1367 1368 SCIPdebugMsg(scip, "Generated orbisack inequalities for <%s>: %d\n", SCIPconsGetName(conss[c]), ngen); 1369 1370 if ( ngen > 0 ) 1371 *result = SCIP_SEPARATED; 1372 } 1373 1374 SCIPfreeBufferArray(scip, &vals2); 1375 SCIPfreeBufferArray(scip, &vals1); 1376 } 1377 1378 return SCIP_OKAY; 1379 } 1380 1381 1382 /** constraint enforcing method of constraint handler for pseudo solutions */ 1383 static 1384 SCIP_DECL_CONSENFOPS(consEnfopsOrbisack) 1385 { /*lint --e{715}*/ 1386 SCIP_Bool feasible = TRUE; 1387 SCIP_CONSDATA* consdata; 1388 int c; 1389 1390 assert( scip != NULL ); 1391 assert( conshdlr != NULL ); 1392 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1393 assert( result != NULL ); 1394 1395 SCIPdebugMsg(scip, "Enforcing method for orbisack constraints (pseudo solutions) ...\n"); 1396 1397 *result = SCIP_FEASIBLE; 1398 1399 if ( objinfeasible || solinfeasible ) 1400 return SCIP_OKAY; 1401 1402 /* loop through constraints */ 1403 for (c = 0; c < nconss; ++c) 1404 { 1405 /* get data of constraint */ 1406 assert( conss[c] != NULL ); 1407 consdata = SCIPconsGetData(conss[c]); 1408 assert( consdata != NULL); 1409 assert( consdata->nrows > 0 ); 1410 assert( consdata->vars1 != NULL ); 1411 assert( consdata->vars2 != NULL ); 1412 1413 /* do not enforce non-model constraints */ 1414 if ( !consdata->ismodelcons ) 1415 continue; 1416 1417 SCIP_CALL( SCIPcheckSolutionOrbisack(scip, NULL, consdata->vars1, consdata->vars2, consdata->nrows, FALSE, &feasible) ); 1418 1419 if ( ! feasible ) 1420 { 1421 *result = SCIP_INFEASIBLE; 1422 break; 1423 } 1424 } 1425 1426 return SCIP_OKAY; 1427 } 1428 1429 1430 /** constraint enforcing method of constraint handler for relaxation solutions */ 1431 static 1432 SCIP_DECL_CONSENFORELAX(consEnforelaxOrbisack) 1433 { /*lint --e{715}*/ 1434 SCIP_CONSDATA* consdata; 1435 SCIP_Bool infeasible = FALSE; 1436 SCIP_Real* vals1; 1437 SCIP_Real* vals2; 1438 int ngen = 0; 1439 int c; 1440 1441 assert( scip != 0 ); 1442 assert( conshdlr != 0 ); 1443 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1444 assert( result != 0 ); 1445 1446 SCIPdebugMsg(scip, "Enforelax method for orbisack constraints.\n"); 1447 1448 /* we have a negative priority, so we should come after the integrality conshdlr. */ 1449 assert( SCIPgetNLPBranchCands(scip) == 0 ); 1450 1451 *result = SCIP_FEASIBLE; 1452 1453 if ( nconss > 0 ) 1454 { 1455 SCIP_CONSHDLRDATA* conshdlrdata; 1456 int nvals; 1457 1458 conshdlrdata = SCIPconshdlrGetData(conshdlr); 1459 assert( conshdlrdata != NULL ); 1460 1461 nvals = conshdlrdata->maxnrows; 1462 assert( nvals > 0 ); 1463 1464 SCIP_CALL( SCIPallocBufferArray(scip, &vals1, nvals) ); 1465 SCIP_CALL( SCIPallocBufferArray(scip, &vals2, nvals) ); 1466 1467 /* loop through constraints */ 1468 for (c = 0; c < nconss; ++c) 1469 { 1470 /* get data of constraint */ 1471 assert( conss[c] != 0 ); 1472 consdata = SCIPconsGetData(conss[c]); 1473 assert( consdata != NULL ); 1474 1475 /* do not enforce non-model constraints */ 1476 if ( !consdata->ismodelcons ) 1477 continue; 1478 1479 /* get solution */ 1480 assert( consdata->nrows <= nvals ); 1481 SCIP_CALL( SCIPgetSolVals(scip, sol, consdata->nrows, consdata->vars1, vals1) ); 1482 SCIP_CALL( SCIPgetSolVals(scip, sol, consdata->nrows, consdata->vars2, vals2) ); 1483 1484 SCIPdebugMsg(scip, "Enforcing orbisack constraint <%s> ...\n", SCIPconsGetName(conss[c])); 1485 1486 /* Separate only cover inequalities to ensure that enforcing works correctly. */ 1487 /* Otherwise, it may happen that infeasible solutions cannot be detected, since */ 1488 /* we bound the size of the coefficients for the orbisack inequalities. */ 1489 SCIP_CALL( separateOrbisackCovers(scip, conss[c], consdata->nrows, consdata->vars1, consdata->vars2, vals1, vals2, &ngen, &infeasible) ); 1490 1491 if ( infeasible ) 1492 { 1493 *result = SCIP_CUTOFF; 1494 break; 1495 } 1496 1497 SCIPdebugMsg(scip, "Generated orbisack inequalities for <%s>: %d\n", SCIPconsGetName(conss[c]), ngen); 1498 1499 if ( ngen > 0 ) 1500 *result = SCIP_SEPARATED; 1501 } 1502 1503 SCIPfreeBufferArray(scip, &vals2); 1504 SCIPfreeBufferArray(scip, &vals1); 1505 } 1506 1507 return SCIP_OKAY; 1508 } 1509 1510 1511 /** feasibility check method of constraint handler for integral solutions */ 1512 static 1513 SCIP_DECL_CONSCHECK(consCheckOrbisack) 1514 { /*lint --e{715}*/ 1515 SCIP_Bool feasible = TRUE; 1516 SCIP_CONSDATA* consdata; 1517 int c; 1518 1519 assert( scip != NULL ); 1520 assert( conshdlr != NULL ); 1521 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1522 assert( result != NULL ); 1523 1524 *result = SCIP_FEASIBLE; 1525 1526 /* loop through constraints */ 1527 for (c = 0; c < nconss; ++c) 1528 { 1529 /* get data of constraint */ 1530 assert( conss[c] != NULL ); 1531 consdata = SCIPconsGetData(conss[c]); 1532 assert( consdata != NULL); 1533 assert( consdata->nrows > 0 ); 1534 assert( consdata->vars1 != NULL ); 1535 assert( consdata->vars2 != NULL ); 1536 1537 SCIPdebugMsg(scip, "Check method for orbisack constraint <%s> (%d rows) ...\n", SCIPconsGetName(conss[c]), consdata->nrows); 1538 1539 /* do not check non-model constraints */ 1540 if ( !consdata->ismodelcons ) 1541 continue; 1542 1543 SCIP_CALL( SCIPcheckSolutionOrbisack(scip, sol, consdata->vars1, consdata->vars2, consdata->nrows, printreason, &feasible) ); 1544 1545 if ( ! feasible ) 1546 { 1547 *result = SCIP_INFEASIBLE; 1548 SCIPdebugMsg(scip, "Solution is feasible.\n"); 1549 break; 1550 } 1551 } 1552 1553 if ( feasible ) 1554 SCIPdebugMsg(scip, "Solution is feasible.\n"); 1555 1556 return SCIP_OKAY; 1557 } 1558 1559 1560 /** domain propagation method of constraint handler */ 1561 static 1562 SCIP_DECL_CONSPROP(consPropOrbisack) 1563 { /*lint --e{715}*/ 1564 int c; 1565 1566 assert( scip != NULL ); 1567 assert( conshdlr != NULL ); 1568 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1569 assert( result != NULL ); 1570 1571 *result = SCIP_DIDNOTRUN; 1572 1573 SCIPdebugMsg(scip, "Propagation method of orbisack constraint handler.\n"); 1574 1575 /* loop through constraints */ 1576 for (c = 0; c < nconss; ++c) 1577 { 1578 SCIP_Bool infeasible = FALSE; 1579 SCIP_Bool found = FALSE; 1580 int ngen = 0; 1581 1582 assert( conss[c] != NULL ); 1583 1584 SCIP_CALL( propVariables(scip, conss[c], &infeasible, &found, &ngen) ); 1585 1586 if ( infeasible ) 1587 { 1588 *result = SCIP_CUTOFF; 1589 return SCIP_OKAY; 1590 } 1591 1592 if ( found ) 1593 *result = SCIP_REDUCEDDOM; 1594 } 1595 1596 return SCIP_OKAY; 1597 } 1598 1599 1600 /** presolving method of constraint handler */ 1601 static 1602 SCIP_DECL_CONSPRESOL(consPresolOrbisack) 1603 { /*lint --e{715}*/ 1604 int c; 1605 int ngen = 0; 1606 1607 assert( scip != NULL ); 1608 assert( conshdlr != NULL ); 1609 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1610 assert( result != NULL ); 1611 1612 SCIPdebugMsg(scip, "Presolving method of orbisack constraint handler. Propagating orbisack inequalities.\n"); 1613 1614 *result = SCIP_DIDNOTFIND; 1615 1616 /* loop through constraints */ 1617 for (c = 0; c < nconss; ++c) 1618 { 1619 SCIP_Bool infeasible = FALSE; 1620 SCIP_Bool found = FALSE; 1621 int curngen = 0; 1622 1623 assert( conss[c] != NULL ); 1624 SCIP_CALL( propVariables(scip, conss[c], &infeasible, &found, &curngen) ); 1625 1626 if ( infeasible ) 1627 { 1628 *result = SCIP_CUTOFF; 1629 break; 1630 } 1631 1632 ngen += curngen; 1633 } 1634 1635 if ( ngen > 0 ) 1636 { 1637 *nfixedvars += ngen; 1638 *result = SCIP_SUCCESS; 1639 } 1640 1641 return SCIP_OKAY; 1642 } 1643 1644 1645 /** Propagation resolution for conflict analysis */ 1646 static 1647 SCIP_DECL_CONSRESPROP(consRespropOrbisack) 1648 { /*lint --e{715}*/ 1649 SCIP_CONSDATA* consdata; 1650 SCIP_VAR** vars1; 1651 SCIP_VAR** vars2; 1652 int i; 1653 int varrow; 1654 int infrow; 1655 1656 assert( scip != NULL ); 1657 assert( conshdlr != NULL ); 1658 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1659 assert( cons != NULL ); 1660 assert( infervar != NULL ); 1661 assert( bdchgidx != NULL ); 1662 assert( result != NULL ); 1663 1664 SCIPdebugMsg(scip, "Propagation resolution method of orbisack constraint handler.\n"); 1665 1666 *result = SCIP_DIDNOTFIND; 1667 1668 consdata = SCIPconsGetData(cons); 1669 assert( consdata != NULL); 1670 assert( consdata->nrows > 0 ); 1671 assert( consdata->vars1 != NULL ); 1672 assert( consdata->vars2 != NULL ); 1673 1674 vars1 = consdata->vars1; 1675 vars2 = consdata->vars2; 1676 1677 /* inferinfo == varrow + infrow * nrows. infrow is 0 if the fixing is not caused by a lookahead. */ 1678 varrow = inferinfo % consdata->nrows; 1679 infrow = inferinfo / consdata->nrows; 1680 1681 assert( varrow >= 0 ); 1682 assert( varrow < consdata->nrows ); 1683 assert( infrow >= 0 ); 1684 assert( infrow < consdata->nrows ); 1685 1686 /* In both cases, the rows until "varrow" are constants. */ 1687 for (i = 0; i < varrow; ++i) 1688 { 1689 /* Conflict caused by bounds of previous variables */ 1690 SCIP_CALL( SCIPaddConflictUb(scip, vars1[i], bdchgidx) ); 1691 SCIP_CALL( SCIPaddConflictLb(scip, vars1[i], bdchgidx) ); 1692 SCIP_CALL( SCIPaddConflictUb(scip, vars2[i], bdchgidx) ); 1693 SCIP_CALL( SCIPaddConflictLb(scip, vars2[i], bdchgidx) ); 1694 } 1695 1696 if ( infrow > 0 ) 1697 { 1698 /* The fixing of infervar is caused by a lookahead (checkFeasible). 1699 * The rows until "varrow" are constants, and row "varrow" is (_, _), (1, _), (_, 0). 1700 * If we assume "varrow" is constant, then the next rows until infrow are constants, and infrow is (0, 1). 1701 */ 1702 for (i = varrow + 1; i < infrow; ++i) 1703 { 1704 /* These rows are one of (0, 0), (1, 1), (0, _), (_, 1), making them constants. */ 1705 SCIP_CALL( SCIPaddConflictUb(scip, vars1[i], bdchgidx) ); 1706 SCIP_CALL( SCIPaddConflictLb(scip, vars1[i], bdchgidx) ); 1707 SCIP_CALL( SCIPaddConflictUb(scip, vars2[i], bdchgidx) ); 1708 SCIP_CALL( SCIPaddConflictLb(scip, vars2[i], bdchgidx) ); 1709 } 1710 1711 /* And infrow itself is (0, 1). */ 1712 assert( SCIPvarGetUbAtIndex(vars1[infrow], bdchgidx, TRUE) < 0.5 ); 1713 assert( SCIPvarGetUbAtIndex(vars1[infrow], bdchgidx, FALSE) < 0.5 ); 1714 assert( SCIPvarGetLbAtIndex(vars2[infrow], bdchgidx, TRUE) > 0.5 ); 1715 assert( SCIPvarGetLbAtIndex(vars2[infrow], bdchgidx, FALSE) > 0.5 ); 1716 1717 SCIP_CALL( SCIPaddConflictUb(scip, vars1[infrow], bdchgidx) ); 1718 SCIP_CALL( SCIPaddConflictLb(scip, vars2[infrow], bdchgidx) ); 1719 } 1720 else 1721 { 1722 /* This is not a fixing caused by lookahead (checkFeasible), 1723 * so row "varrow" was (0, _) or (_, 1) and its previous rows are constants. 1724 */ 1725 if ( boundtype == SCIP_BOUNDTYPE_LOWER ) 1726 { 1727 /* We changed the lower bound of infervar to 1. This means that this fixing is due to (_, 1) */ 1728 assert( infervar == vars1[varrow] ); 1729 assert( SCIPvarGetLbAtIndex(vars1[varrow], bdchgidx, FALSE) < 0.5 ); 1730 assert( SCIPvarGetLbAtIndex(vars1[varrow], bdchgidx, TRUE) > 0.5 ); 1731 assert( SCIPvarGetLbAtIndex(vars2[varrow], bdchgidx, FALSE ) > 0.5); 1732 assert( SCIPvarGetUbAtIndex(vars2[varrow], bdchgidx, FALSE ) > 0.5); 1733 1734 SCIP_CALL( SCIPaddConflictUb(scip, vars2[varrow], bdchgidx) ); 1735 SCIP_CALL( SCIPaddConflictLb(scip, vars2[varrow], bdchgidx) ); 1736 } 1737 else 1738 { 1739 /* We changed the upper bound to 0. This means that this fixing is due to (0, _) */ 1740 assert( infervar == vars2[varrow] ); 1741 assert( SCIPvarGetLbAtIndex(vars1[varrow], bdchgidx, FALSE ) < 0.5); 1742 assert( SCIPvarGetUbAtIndex(vars1[varrow], bdchgidx, FALSE ) < 0.5); 1743 assert( SCIPvarGetUbAtIndex(vars2[varrow], bdchgidx, FALSE) > 0.5 ); 1744 assert( SCIPvarGetUbAtIndex(vars2[varrow], bdchgidx, TRUE) < 0.5 ); 1745 1746 SCIP_CALL( SCIPaddConflictUb(scip, vars1[varrow], bdchgidx) ); 1747 SCIP_CALL( SCIPaddConflictLb(scip, vars1[varrow], bdchgidx) ); 1748 } 1749 } 1750 1751 *result = SCIP_SUCCESS; 1752 return SCIP_OKAY; 1753 } 1754 1755 1756 /** Lock variables 1757 * 1758 * We assume we have only one global (void) constraint and lock all variables. 1759 * 1760 * - Orbisack constraints may get violated if the variables of the first column 1761 * are rounded down, we therefor call SCIPaddVarLocksType(..., nlockspos, nlocksneg). 1762 * - Orbisack constraints may get violated if the variables of the second column 1763 * are rounded up , we therefor call SCIPaddVarLocksType(..., nlocksneg, nlockspo ). 1764 */ 1765 static 1766 SCIP_DECL_CONSLOCK(consLockOrbisack) 1767 { /*lint --e{715}*/ 1768 SCIP_CONSDATA* consdata; 1769 SCIP_VAR** vars1; 1770 SCIP_VAR** vars2; 1771 int nrows; 1772 int i; 1773 1774 assert( scip != NULL ); 1775 assert( conshdlr != NULL ); 1776 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 1777 assert( cons != NULL ); 1778 1779 SCIPdebugMsg(scip, "Locking method for orbisack constraint handler.\n"); 1780 1781 /* get data of original constraint */ 1782 consdata = SCIPconsGetData(cons); 1783 assert( consdata != NULL); 1784 assert( consdata->nrows > 0 ); 1785 assert( consdata->vars1 != NULL ); 1786 assert( consdata->vars2 != NULL ); 1787 1788 nrows = consdata->nrows; 1789 vars1 = consdata->vars1; 1790 vars2 = consdata->vars2; 1791 1792 for (i = 0; i < nrows; ++i) 1793 { 1794 SCIP_CALL( SCIPaddVarLocksType(scip, vars1[i], locktype, nlockspos, nlocksneg) ); 1795 SCIP_CALL( SCIPaddVarLocksType(scip, vars2[i], locktype, nlocksneg, nlockspos) ); 1796 } 1797 1798 return SCIP_OKAY; 1799 } 1800 1801 1802 /** constraint copying method of constraint handler */ 1803 static 1804 SCIP_DECL_CONSCOPY(consCopyOrbisack) 1805 { 1806 SCIP_CONSHDLRDATA* conshdlrdata; 1807 SCIP_CONSDATA* sourcedata; 1808 SCIP_VAR** sourcevars1; 1809 SCIP_VAR** sourcevars2; 1810 SCIP_VAR** vars1; 1811 SCIP_VAR** vars2; 1812 int nrows; 1813 int i; 1814 1815 assert( scip != NULL ); 1816 assert( cons != NULL ); 1817 assert( sourcescip != NULL ); 1818 assert( sourceconshdlr != NULL ); 1819 assert( strcmp(SCIPconshdlrGetName(sourceconshdlr), CONSHDLR_NAME) == 0 ); 1820 assert( sourcecons != NULL ); 1821 assert( varmap != NULL ); 1822 assert( valid != NULL ); 1823 1824 *valid = TRUE; 1825 1826 SCIPdebugMsg(scip, "Copying method for orbisack constraint handler.\n"); 1827 1828 sourcedata = SCIPconsGetData(sourcecons); 1829 assert( sourcedata != NULL ); 1830 assert( sourcedata->vars1 != NULL ); 1831 assert( sourcedata->vars2 != NULL ); 1832 assert( sourcedata->nrows > 0 ); 1833 1834 conshdlrdata = SCIPconshdlrGetData(sourceconshdlr); 1835 assert( conshdlrdata != NULL ); 1836 1837 /* do not copy non-model constraints */ 1838 if ( !sourcedata->ismodelcons && !conshdlrdata->forceconscopy ) 1839 { 1840 *valid = FALSE; 1841 1842 return SCIP_OKAY; 1843 } 1844 1845 sourcevars1 = sourcedata->vars1; 1846 sourcevars2 = sourcedata->vars2; 1847 nrows = sourcedata->nrows; 1848 1849 SCIP_CALL( SCIPallocBufferArray(scip, &vars1, nrows) ); 1850 1851 for (i = 0; i < nrows && *valid; ++i) 1852 { 1853 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars1[i], &(vars1[i]), varmap, consmap, global, valid) ); 1854 assert( !(*valid) || vars1[i] != NULL ); 1855 } 1856 1857 /* only create the target constraint, if all variables could be copied */ 1858 if ( !(*valid) ) 1859 { 1860 SCIPfreeBufferArray(scip, &vars1); 1861 1862 return SCIP_OKAY; 1863 } 1864 1865 SCIP_CALL( SCIPallocBufferArray(scip, &vars2, nrows) ); 1866 1867 for (i = 0; i < nrows && *valid; ++i) 1868 { 1869 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars2[i], &(vars2[i]), varmap, consmap, global, valid) ); 1870 assert( !(*valid) || vars2[i] != NULL ); 1871 } 1872 1873 /* only create the target constraint, if all variables could be copied */ 1874 if ( *valid ) 1875 { 1876 /* create copied constraint */ 1877 if ( name == NULL ) 1878 name = SCIPconsGetName(sourcecons); 1879 1880 SCIP_CALL( SCIPcreateConsOrbisack(scip, cons, name, vars1, vars2, nrows, FALSE, FALSE, sourcedata->ismodelcons, 1881 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) ); 1882 } 1883 1884 SCIPfreeBufferArray(scip, &vars2); 1885 SCIPfreeBufferArray(scip, &vars1); 1886 1887 return SCIP_OKAY; 1888 } 1889 1890 1891 /** constraint parsing method of constraint handler */ 1892 static 1893 SCIP_DECL_CONSPARSE(consParseOrbisack) 1894 { /*lint --e{715}*/ 1895 const char* s; 1896 char* endptr; 1897 SCIP_VAR** vars1; 1898 SCIP_VAR** vars2; 1899 SCIP_VAR* var; 1900 int nrows = 0; 1901 int maxnrows = 128; 1902 SCIP_Bool firstcolumn = TRUE; 1903 SCIP_Bool ispporbisack = FALSE; 1904 SCIP_Bool isparttype = FALSE; 1905 1906 assert( success != NULL ); 1907 1908 *success = TRUE; 1909 s = str; 1910 1911 /* skip white space */ 1912 SCIP_CALL( SCIPskipSpace((char**)&s) ); 1913 1914 if( strncmp(s, "partOrbisack(", 13) == 0 ) 1915 { 1916 ispporbisack = TRUE; 1917 isparttype = TRUE; 1918 } 1919 else if( strncmp(s, "packOrbisack(", 13) == 0 ) 1920 ispporbisack = TRUE; 1921 else 1922 { 1923 if( strncmp(s, "fullOrbisack(", 13) != 0 ) 1924 { 1925 SCIPerrorMessage("Syntax error - expected \"fullOrbisack(\", \"partOrbisack\" or \"packOrbisacj\": %s\n", s); 1926 *success = FALSE; 1927 return SCIP_OKAY; 1928 } 1929 } 1930 s += 13; 1931 1932 /* loop through string */ 1933 SCIP_CALL( SCIPallocBufferArray(scip, &vars1, maxnrows) ); 1934 SCIP_CALL( SCIPallocBufferArray(scip, &vars2, maxnrows) ); 1935 1936 do 1937 { 1938 /* parse variable name */ 1939 SCIP_CALL( SCIPparseVarName(scip, s, &var, &endptr) ); 1940 1941 if( var == NULL ) 1942 { 1943 endptr = strchr(endptr, ')'); 1944 1945 if( endptr == NULL || !firstcolumn ) 1946 { 1947 SCIPerrorMessage("variable is missing.\n"); 1948 *success = FALSE; 1949 } 1950 1951 break; 1952 } 1953 1954 s = endptr; 1955 assert( s != NULL ); 1956 1957 /* skip white space */ 1958 SCIP_CALL( SCIPskipSpace((char**)&s) ); 1959 1960 if( firstcolumn == ( *s == '.' || *s == ')' ) ) 1961 { 1962 SCIPerrorMessage("there are not two variables per row.\n"); 1963 *success = FALSE; 1964 break; 1965 } 1966 1967 /* begin new row if required */ 1968 if( firstcolumn ) 1969 { 1970 ++nrows; 1971 1972 if( nrows > maxnrows ) 1973 { 1974 maxnrows = SCIPcalcMemGrowSize(scip, nrows); 1975 SCIP_CALL( SCIPreallocBufferArray(scip, &vars1, maxnrows) ); 1976 SCIP_CALL( SCIPreallocBufferArray(scip, &vars2, maxnrows) ); 1977 assert( nrows <= maxnrows ); 1978 } 1979 1980 vars1[nrows-1] = var; 1981 } 1982 else 1983 vars2[nrows-1] = var; 1984 1985 firstcolumn = !firstcolumn; 1986 1987 /* skip ',' or '.' */ 1988 if( *s == ',' || *s == '.' ) 1989 ++s; 1990 } 1991 while( *s != ')' ); 1992 1993 if( *success ) 1994 SCIP_CALL( SCIPcreateConsBasicOrbisack(scip, cons, name, vars1, vars2, nrows, ispporbisack, isparttype, TRUE) ); 1995 1996 SCIPfreeBufferArray(scip, &vars2); 1997 SCIPfreeBufferArray(scip, &vars1); 1998 1999 return SCIP_OKAY; 2000 } 2001 2002 2003 /** constraint display method of constraint handler 2004 * 2005 * The constraint handler should output a representation of the constraint into the given text file. 2006 */ 2007 static 2008 SCIP_DECL_CONSPRINT(consPrintOrbisack) 2009 { /*lint --e{715}*/ 2010 SCIP_CONSDATA* consdata; 2011 SCIP_VAR** vars1; 2012 SCIP_VAR** vars2; 2013 int nrows; 2014 int i; 2015 2016 assert( scip != NULL ); 2017 assert( conshdlr != NULL ); 2018 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 ); 2019 assert( cons != NULL ); 2020 2021 consdata = SCIPconsGetData(cons); 2022 assert( consdata != NULL ); 2023 assert( consdata->vars1 != NULL ); 2024 assert( consdata->vars2 != NULL ); 2025 assert( consdata->nrows > 0 ); 2026 2027 vars1 = consdata->vars1; 2028 vars2 = consdata->vars2; 2029 nrows = consdata->nrows; 2030 2031 SCIPdebugMsg(scip, "Printing method for orbisack constraint handler\n"); 2032 2033 SCIPinfoMessage(scip, file, "fullOrbisack("); 2034 2035 for (i = 0; i < nrows; ++i) 2036 { 2037 SCIP_CALL( SCIPwriteVarName(scip, file, vars1[i], TRUE) ); 2038 SCIPinfoMessage(scip, file, ","); 2039 SCIP_CALL( SCIPwriteVarName(scip, file, vars2[i], TRUE) ); 2040 if ( i < nrows-1 ) 2041 SCIPinfoMessage(scip, file, "."); 2042 } 2043 2044 SCIPinfoMessage(scip, file, ")"); 2045 2046 return SCIP_OKAY; 2047 } 2048 2049 2050 /** checks given solution for feasibility */ 2051 SCIP_RETCODE SCIPcheckSolutionOrbisack( 2052 SCIP* scip, /**< SCIP data structure */ 2053 SCIP_SOL* sol, /**< solution to check for feasibility */ 2054 SCIP_VAR** vars1, /**< variables of first column */ 2055 SCIP_VAR** vars2, /**< variables of second column */ 2056 int nrows, /**< number of rows */ 2057 SCIP_Bool printreason, /**< whether reason for infeasibility should be printed */ 2058 SCIP_Bool* feasible /**< memory address to store whether sol is feasible */ 2059 ) 2060 { 2061 int i; 2062 int val1; 2063 int val2; 2064 2065 assert( scip != NULL ); 2066 assert( vars1 != NULL ); 2067 assert( vars2 != NULL ); 2068 assert( nrows > 0 ); 2069 assert( feasible != NULL ); 2070 2071 *feasible = TRUE; 2072 2073 /* find first non-constant row and check for feasibility */ 2074 for (i = 0; i < nrows; ++i) 2075 { 2076 assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, vars1[i])) ); 2077 assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, vars2[i])) ); 2078 2079 /* get values of i-th row */ 2080 val1 = SCIPgetSolVal(scip, sol, vars1[i]) > 0.5 ? 1 : 0; 2081 val2 = SCIPgetSolVal(scip, sol, vars2[i]) > 0.5 ? 1 : 0; 2082 2083 /* if row i is constrant */ 2084 if ( val1 == val2 ) 2085 continue; 2086 /* row i has type (1,0) -> feasible */ 2087 else if ( val1 == 1 ) 2088 { 2089 assert( val2 == 0 ); 2090 break; 2091 } 2092 else /* infeasible */ 2093 { 2094 if ( printreason ) 2095 SCIPinfoMessage(scip, NULL, "First non-constant row %d is fixed to (0,1).\n", i); 2096 *feasible = FALSE; 2097 break; 2098 } 2099 } 2100 2101 return SCIP_OKAY; 2102 } 2103 2104 2105 /** constraint method of constraint handler which returns the variables (if possible) */ 2106 static 2107 SCIP_DECL_CONSGETVARS(consGetVarsOrbisack) 2108 { /*lint --e{715}*/ 2109 SCIP_CONSDATA* consdata; 2110 2111 assert( cons != NULL ); 2112 assert( success != NULL ); 2113 assert( vars != NULL ); 2114 2115 consdata = SCIPconsGetData(cons); 2116 assert( consdata != NULL ); 2117 2118 if ( varssize < 2 * consdata->nrows ) 2119 (*success) = FALSE; 2120 else 2121 { 2122 int cnt = 0; 2123 int i; 2124 2125 for (i = 0; i < consdata->nrows; ++i) 2126 { 2127 vars[cnt++] = consdata->vars1[i]; 2128 vars[cnt++] = consdata->vars2[i]; 2129 } 2130 (*success) = TRUE; 2131 } 2132 2133 return SCIP_OKAY; 2134 } 2135 2136 2137 /** constraint method of constraint handler which returns the number of variables (if possible) */ 2138 static 2139 SCIP_DECL_CONSGETNVARS(consGetNVarsOrbisack) 2140 { /*lint --e{715}*/ 2141 SCIP_CONSDATA* consdata; 2142 2143 assert( cons != NULL ); 2144 2145 consdata = SCIPconsGetData(cons); 2146 assert( consdata != NULL ); 2147 2148 (*nvars) = 2 * consdata->nrows; 2149 (*success) = TRUE; 2150 2151 return SCIP_OKAY; 2152 } 2153 2154 2155 /** creates the handler for orbisack constraints and includes it in SCIP */ 2156 SCIP_RETCODE SCIPincludeConshdlrOrbisack( 2157 SCIP* scip /**< SCIP data structure */ 2158 ) 2159 { 2160 SCIP_CONSHDLRDATA* conshdlrdata = NULL; 2161 SCIP_CONSHDLR* conshdlr; 2162 2163 SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) ); 2164 2165 /* include constraint handler */ 2166 SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC, 2167 CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY, 2168 CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS, 2169 consEnfolpOrbisack, consEnfopsOrbisack, consCheckOrbisack, consLockOrbisack, 2170 conshdlrdata) ); 2171 assert( conshdlr != NULL ); 2172 2173 /* set non-fundamental callbacks via specific setter functions */ 2174 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyOrbisack, consCopyOrbisack) ); 2175 SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxOrbisack) ); 2176 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeOrbisack) ); 2177 SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteOrbisack) ); 2178 SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsOrbisack) ); 2179 SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsOrbisack) ); 2180 SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseOrbisack) ); 2181 SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolOrbisack, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) ); 2182 SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintOrbisack) ); 2183 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropOrbisack, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP, CONSHDLR_PROP_TIMING) ); 2184 SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropOrbisack) ); 2185 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpOrbisack, consSepasolOrbisack, CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, CONSHDLR_DELAYSEPA) ); 2186 SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransOrbisack) ); 2187 SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpOrbisack) ); 2188 SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolOrbisack) ); 2189 2190 /* separation methods */ 2191 SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/coverseparation", 2192 "Separate cover inequalities for orbisacks?", 2193 &conshdlrdata->coverseparation, TRUE, DEFAULT_COVERSEPARATION, NULL, NULL) ); 2194 2195 SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/orbiSeparation", 2196 "Separate orbisack inequalities?", 2197 &conshdlrdata->orbiseparation, TRUE, DEFAULT_ORBISEPARATION, NULL, NULL) ); 2198 2199 SCIP_CALL( SCIPaddRealParam(scip, "constraints/" CONSHDLR_NAME "/coeffbound", 2200 "Maximum size of coefficients for orbisack inequalities", 2201 &conshdlrdata->coeffbound, TRUE, DEFAULT_COEFFBOUND, 0.0, DBL_MAX, NULL, NULL) ); 2202 2203 /* whether we allow upgrading to packing/partioning orbisack constraints*/ 2204 SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/checkpporbisack", 2205 "Upgrade orbisack constraints to packing/partioning orbisacks?", 2206 &conshdlrdata->checkpporbisack, TRUE, DEFAULT_PPORBISACK, NULL, NULL) ); 2207 2208 SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/forceconscopy", 2209 "Whether orbisack constraints should be forced to be copied to sub SCIPs.", 2210 &conshdlrdata->forceconscopy, TRUE, DEFAULT_FORCECONSCOPY, NULL, NULL) ); 2211 2212 return SCIP_OKAY; 2213 } 2214 2215 2216 /* 2217 * constraint specific interface methods 2218 */ 2219 2220 /** creates and captures a orbisack constraint 2221 * 2222 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 2223 */ 2224 SCIP_RETCODE SCIPcreateConsOrbisack( 2225 SCIP* scip, /**< SCIP data structure */ 2226 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 2227 const char* name, /**< name of constraint */ 2228 SCIP_VAR*const* vars1, /**< first column of matrix of variables on which the symmetry acts */ 2229 SCIP_VAR*const* vars2, /**< second column of matrix of variables on which the symmetry acts */ 2230 int nrows, /**< number of rows in variable matrix */ 2231 SCIP_Bool ispporbisack, /**< whether the orbisack is a packing/partitioning orbisack */ 2232 SCIP_Bool isparttype, /**< whether the orbisack is a partitioning orbisack */ 2233 SCIP_Bool ismodelcons, /**< whether the orbisack is a model constraint */ 2234 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? 2235 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */ 2236 SCIP_Bool separate, /**< should the constraint be separated during LP processing? 2237 * Usually set to TRUE. */ 2238 SCIP_Bool enforce, /**< should the constraint be enforced during node processing? 2239 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 2240 SCIP_Bool check, /**< should the constraint be checked for feasibility? 2241 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 2242 SCIP_Bool propagate, /**< should the constraint be propagated during node processing? 2243 * Usually set to TRUE. */ 2244 SCIP_Bool local, /**< is constraint only valid locally? 2245 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */ 2246 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)? 2247 * Usually set to FALSE. In column generation applications, set to TRUE if pricing 2248 * adds coefficients to this constraint. */ 2249 SCIP_Bool dynamic, /**< is constraint subject to aging? 2250 * Usually set to FALSE. Set to TRUE for own cuts which 2251 * are separated as constraints. */ 2252 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? 2253 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */ 2254 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even 2255 * if it may be moved to a more global node? 2256 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */ 2257 ) 2258 { 2259 SCIP_CONSHDLR* conshdlr; 2260 SCIP_CONSHDLRDATA* conshdlrdata; 2261 SCIP_CONSDATA* consdata; 2262 SCIP_VAR*** vars; 2263 SCIP_Bool success; 2264 SCIP_ORBITOPETYPE orbitopetype; 2265 int i; 2266 2267 /* find the orbisack constraint handler */ 2268 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME); 2269 if ( conshdlr == NULL ) 2270 { 2271 SCIPerrorMessage("orbisack constraint handler not found\n"); 2272 return SCIP_PLUGINNOTFOUND; 2273 } 2274 2275 assert( nrows > 0 ); 2276 2277 /* check for upgrade to packing/partitioning orbisacks*/ 2278 conshdlrdata = SCIPconshdlrGetData(conshdlr); 2279 if ( ! ispporbisack && conshdlrdata->checkpporbisack ) 2280 { 2281 SCIP_CALL( packingUpgrade(scip, vars1, vars2, nrows, &success, &isparttype) ); 2282 2283 if ( success ) 2284 ispporbisack = TRUE; 2285 } 2286 2287 /* create constraint, if it is a packing/partitioning orbisack, add orbitope constraint 2288 * instead of orbitsack constraint */ 2289 if ( ispporbisack ) 2290 { 2291 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nrows) ); 2292 for (i = 0; i < nrows; ++i) 2293 { 2294 SCIP_CALL( SCIPallocBufferArray(scip, &vars[i], 2) ); /*lint !e866*/ 2295 vars[i][0] = vars1[i]; 2296 vars[i][1] = vars2[i]; 2297 } 2298 2299 if ( isparttype ) 2300 orbitopetype = SCIP_ORBITOPETYPE_PARTITIONING; 2301 else 2302 orbitopetype = SCIP_ORBITOPETYPE_PACKING; 2303 2304 SCIP_CALL( SCIPcreateConsOrbitope(scip, cons, "pporbisack", vars, orbitopetype, nrows, 2305 2, FALSE, TRUE, TRUE, ismodelcons, initial, separate, enforce, check, propagate, local, 2306 modifiable, dynamic, removable, stickingatnode) ); 2307 2308 for (i = 0; i < nrows; ++i) 2309 SCIPfreeBufferArray(scip, &vars[i]); 2310 SCIPfreeBufferArray(scip, &vars); 2311 } 2312 else 2313 { 2314 /* create constraint data */ 2315 SCIP_CALL( consdataCreate(scip, &consdata, vars1, vars2, nrows, ismodelcons) ); 2316 2317 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate, 2318 local, modifiable, dynamic, removable, stickingatnode) ); 2319 } 2320 2321 return SCIP_OKAY; 2322 } 2323 2324 2325 /** creates and captures an orbisack constraint in its most basic variant 2326 * 2327 * All constraint flags set to their default values, which can be set afterwards using SCIPsetConsFLAGNAME() in scip.h. 2328 * 2329 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 2330 */ 2331 SCIP_RETCODE SCIPcreateConsBasicOrbisack( 2332 SCIP* scip, /**< SCIP data structure */ 2333 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 2334 const char* name, /**< name of constraint */ 2335 SCIP_VAR** vars1, /**< first column of matrix of variables on which the symmetry acts */ 2336 SCIP_VAR** vars2, /**< second column of matrix of variables on which the symmetry acts */ 2337 int nrows, /**< number of rows in constraint matrix */ 2338 SCIP_Bool ispporbisack, /**< whether the orbisack is a packing/partitioning orbisack */ 2339 SCIP_Bool isparttype, /**< whether the orbisack is a partitioning orbisack */ 2340 SCIP_Bool ismodelcons /**< whether the orbisack is a model constraint */ 2341 ) 2342 { 2343 SCIP_CALL( SCIPcreateConsOrbisack(scip, cons, name, vars1, vars2, nrows, ispporbisack, isparttype, ismodelcons, 2344 TRUE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 2345 2346 return SCIP_OKAY; 2347 } 2348