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 presol_gateextraction.c 26 * @ingroup DEFPLUGINS_PRESOL 27 * @brief gateextraction presolver 28 * @author Michael Winkler 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include "blockmemshell/memory.h" 34 #include "scip/cons_and.h" 35 #include "scip/cons_logicor.h" 36 #include "scip/cons_setppc.h" 37 #include "scip/presol_gateextraction.h" 38 #include "scip/pub_cons.h" 39 #include "scip/pub_message.h" 40 #include "scip/pub_misc.h" 41 #include "scip/pub_misc_sort.h" 42 #include "scip/pub_presol.h" 43 #include "scip/pub_var.h" 44 #include "scip/scip_cons.h" 45 #include "scip/scip_general.h" 46 #include "scip/scip_mem.h" 47 #include "scip/scip_message.h" 48 #include "scip/scip_param.h" 49 #include "scip/scip_presol.h" 50 #include "scip/scip_prob.h" 51 #include "scip/scip_var.h" 52 #include <string.h> 53 54 #define PRESOL_NAME "gateextraction" 55 #define PRESOL_DESC "presolver extracting gate(and)-constraints" 56 #define PRESOL_PRIORITY 1000000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers); combined with propagators */ 57 #define PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */ 58 #define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */ 59 60 #define HASHSIZE_LOGICORCONS 500 /**< minimal size of hash table in logicor constraint tables */ 61 #define HASHSIZE_SETPPCCONS 500 /**< minimal size of hash table in setppc constraint tables */ 62 63 #define DEFAULT_ONLYSETPART FALSE /**< should only set-partitioning constraints be extracted and no and-constraints */ 64 #define DEFAULT_SEARCHEQUATIONS TRUE /**< should we try to extract set-partitioning constraint out of one logicor 65 * and one corresponding set-packing constraint 66 */ 67 #define DEFAULT_SORTING 1 /**< order logicor contraints to extract big-gates before smaller ones (-1), do 68 * not order them (0) or order them to extract smaller gates at first (1) 69 */ 70 71 72 /* This presolver tries to extract gate-constraints meaning and-constraints and set-partitioning constraints (and could 73 * be expanded to find xor-constraints too). This is done by detecting linearizations or systems of inequalities which 74 * form an and-constraint or a set-partitioning constraint. An example: 75 * 76 * we have a logicor constraint of the form: x + y + z >= 1 77 * 78 * and we also have the following set-packing constraints: (x + y <= 1 and x + z <= 1) <=> (~x + ~y >= 1 and ~x + ~z >= 1) 79 * 80 * - these three constraints form an and-constraint: x = ~y * ~z (x = AND(~y,~z)) 81 * 82 * if an additional set-packing constraint exists: y + z <= 1 83 * 84 * - these four constraints form a set-partitioning cons.: x + y + z = 1 85 * 86 * some information can be found: 87 * 88 * http://www.cs.ubc.ca/~hutter/earg/papers07/cnf-structure.pdf 89 * http://www.cadence.com/cn/cadence/cadence_labs/Documents/niklas_SAT_2005_Effective.pdf 90 * 91 * We also do some check for logicor and set-packing/-partitioning constraint with the same variables to upgrade these 92 * both constraints into one. For example: 93 * 94 * x + y + z >= 1 and x + y + z <= 1 form x + y + z = 1 95 * 96 */ 97 98 99 /* 100 * Data structures 101 */ 102 103 104 /** data object to compare constraint easier */ 105 struct HashData 106 { 107 SCIP_CONS* cons; /**< pointer the the corresponding constraint */ 108 SCIP_VAR** vars; /**< constraint variables used for hash comparison */ 109 int nvars; /**< number of variables */ 110 }; 111 typedef struct HashData HASHDATA; 112 113 114 /** presolver data */ 115 struct SCIP_PresolData 116 { 117 HASHDATA* setppchashdatas; /**< setppc-hashdata storage */ 118 SCIP_HASHTABLE* hashdatatable; /**< setppc-hashdata hashtable for usable setppc constraints */ 119 SCIP_HASHTABLE* setppchashtable; /**< setppc hashtable for usable setppc constraints */ 120 SCIP_HASHTABLE* logicorhashtable; /**< logicor hashtable for usable logicor constraints */ 121 SCIP_CONS** usefullogicor; /**< array for usable logicors */ 122 int nusefullogicor; /**< number of usable logicors */ 123 int susefullogicor; /**< size of array for usable logicor constraints */ 124 int nsetppchashdatas; /**< number of setppchashdata elements added to the hashtable */ 125 int ssetppchashdatas; /**< size of setppchashdata elements added to the hashtable */ 126 int ngates; /**< number of found gates in presolving */ 127 int firstchangedlogicor;/**< position of the first new/changed logicor constraint in the 128 * usefullogicor array 129 */ 130 int maxnvarslogicor; /**< maximal number of variables a logicor constraint has */ 131 int sorting; /**< integer parameter how to sort logicor constraints for extracting gates */ 132 SCIP_Bool usefulsetppcexist; /**< did we find usable set-packing constraints for gate extraction */ 133 SCIP_Bool usefullogicorexist; /**< did we find usable logicor constraints for gate extraction */ 134 SCIP_Bool newsetppchashdatas; /**< flag indicating whether we found new set-packing constraint with two 135 * variables since the last presolving round 136 */ 137 SCIP_Bool initialized; /**< was data alredy be initialized */ 138 SCIP_Bool onlysetpart; /**< boolean parameter whetehr we only want to extract linear gates */ 139 SCIP_Bool searchequations; /**< boolean parameter whetehr we want to search for equations arising from 140 * logicor and setppc constraints 141 */ 142 }; 143 144 145 /* 146 * Local methods 147 */ 148 149 150 /** returns TRUE iff both keys are equal; two constraints are equal if they have the same pointer */ 151 static 152 SCIP_DECL_HASHKEYEQ(hashdataKeyEqCons) 153 { 154 #ifndef NDEBUG 155 SCIP* scip; 156 #endif 157 HASHDATA* hashdata1; 158 HASHDATA* hashdata2; 159 int v; 160 161 hashdata1 = (HASHDATA*)key1; 162 hashdata2 = (HASHDATA*)key2; 163 #ifndef NDEBUG 164 scip = (SCIP*)userptr; 165 assert(scip != NULL); 166 #endif 167 168 /* check data structure */ 169 assert(hashdata1->nvars == 2); 170 assert(hashdata2->nvars == 2); 171 /* at least one data object needs to be have a real set packing constraint */ 172 /* TODO why does this assert fail on one instance when problem is freed 173 * using the new hashing: assert(hashdata1->cons != NULL || hashdata2->cons != NULL); 174 */ 175 176 for( v = 1; v >= 0; --v ) 177 { 178 /* tests if variables are equal */ 179 if( hashdata1->vars[v] != hashdata2->vars[v] ) 180 return FALSE; 181 182 assert(SCIPvarCompare(hashdata1->vars[v], hashdata2->vars[v]) == 0); 183 } 184 185 /* a hashdata object is only equal if it has the same constraint pointer, or one has no constraint pointer, latter 186 * means that this hashdata object is derived from a logicor constraint 187 */ 188 if( hashdata1->cons == NULL || hashdata2->cons == NULL || hashdata1->cons == hashdata2->cons ) 189 return TRUE; 190 else 191 return FALSE; 192 } 193 194 /** returns the hash value of the key */ 195 static 196 SCIP_DECL_HASHKEYVAL(hashdataKeyValCons) 197 { /*lint --e{715}*/ 198 HASHDATA* hashdata; 199 unsigned int hashval; 200 201 hashdata = (HASHDATA*)key; 202 assert(hashdata != NULL); 203 assert(hashdata->vars != NULL); 204 assert(hashdata->nvars == 2); 205 206 /* if we have only two variables we store at each 16 bits of the hash value the index of a variable */ 207 hashval = ((unsigned int)SCIPvarGetIndex(hashdata->vars[1]) << 16) + (unsigned int) SCIPvarGetIndex(hashdata->vars[0]); /*lint !e701*/ 208 209 return hashval; 210 } 211 212 213 /** returns TRUE iff both keys are equal; two constraints are equal if they have the same pointer */ 214 static 215 SCIP_DECL_HASHKEYEQ(setppcHashdataKeyEqCons) 216 { 217 #ifndef NDEBUG 218 SCIP* scip; 219 #endif 220 HASHDATA* hashdata1; 221 HASHDATA* hashdata2; 222 int v; 223 224 hashdata1 = (HASHDATA*)key1; 225 hashdata2 = (HASHDATA*)key2; 226 #ifndef NDEBUG 227 scip = (SCIP*)userptr; 228 assert(scip != NULL); 229 #endif 230 231 /* check data structure */ 232 assert(hashdata1->nvars >= 2); 233 assert(hashdata2->nvars >= 2); 234 /* at least one data object needs to be have a real set-packing/partitioning constraint */ 235 assert(hashdata1->cons != NULL || hashdata2->cons != NULL); 236 237 if( hashdata1->nvars != hashdata2->nvars ) 238 return FALSE; 239 240 for( v = hashdata1->nvars - 1; v >= 0; --v ) 241 { 242 /* tests if variables are equal */ 243 if( hashdata1->vars[v] != hashdata2->vars[v] ) 244 return FALSE; 245 246 assert(SCIPvarCompare(hashdata1->vars[v], hashdata2->vars[v]) == 0); 247 } 248 249 /* a hashdata object is only equal if it has the same constraint pointer, or one has no constraint pointer, latter 250 * means that this hashdata object is derived from a logicor constraint 251 */ 252 if( hashdata1->cons == NULL || hashdata2->cons == NULL || hashdata1->cons == hashdata2->cons ) 253 return TRUE; 254 else 255 return FALSE; 256 } 257 258 /** returns the hash value of the key */ 259 static 260 SCIP_DECL_HASHKEYVAL(setppcHashdataKeyValCons) 261 { /*lint --e{715}*/ 262 HASHDATA* hashdata; 263 264 hashdata = (HASHDATA*)key; 265 assert(hashdata != NULL); 266 assert(hashdata->vars != NULL); 267 assert(hashdata->nvars >= 2); 268 269 return SCIPhashFour(hashdata->nvars, SCIPvarGetIndex(hashdata->vars[0]), \ 270 SCIPvarGetIndex(hashdata->vars[hashdata->nvars/2]), \ 271 SCIPvarGetIndex(hashdata->vars[hashdata->nvars-1])); 272 } 273 274 /** initialize gateextraction presolver data */ 275 static 276 void presoldataInit( 277 SCIP_PRESOLDATA* presoldata /**< data object of presolver */ 278 ) 279 { 280 assert(presoldata != NULL); 281 282 presoldata->usefullogicor = NULL; 283 presoldata->nusefullogicor = 0; 284 presoldata->susefullogicor = 0; 285 presoldata->firstchangedlogicor = -1; 286 presoldata->maxnvarslogicor = 0;; 287 presoldata->nsetppchashdatas = 0; 288 presoldata->ssetppchashdatas = 0; 289 presoldata->ngates = 0; 290 presoldata->usefulsetppcexist = FALSE; 291 presoldata->usefullogicorexist = FALSE; 292 presoldata->newsetppchashdatas = FALSE; 293 presoldata->initialized = FALSE; 294 295 presoldata->hashdatatable = NULL; 296 presoldata->setppchashtable = NULL; 297 presoldata->logicorhashtable = NULL; 298 } 299 300 /** initialize gateextraction hashtables */ 301 static 302 SCIP_RETCODE presoldataInitHashtables( 303 SCIP* scip, /**< SCIP data structure */ 304 SCIP_PRESOLDATA* presoldata /**< data object of presolver */ 305 ) 306 { 307 assert(scip != NULL); 308 assert(presoldata != NULL); 309 310 assert(presoldata->nusefullogicor == 0); 311 assert(presoldata->susefullogicor == 0); 312 assert(presoldata->nsetppchashdatas == 0); 313 assert(presoldata->ssetppchashdatas == 0); 314 assert(presoldata->firstchangedlogicor == -1); 315 assert(presoldata->ngates == 0); 316 assert(presoldata->usefullogicorexist == FALSE); 317 assert(presoldata->usefulsetppcexist == FALSE); 318 assert(presoldata->newsetppchashdatas == FALSE); 319 assert(presoldata->initialized == FALSE); 320 321 assert(presoldata->hashdatatable == NULL); 322 assert(presoldata->setppchashtable == NULL); 323 assert(presoldata->logicorhashtable == NULL); 324 325 /* create hashtables */ 326 SCIP_CALL( SCIPhashtableCreate(&(presoldata->hashdatatable), SCIPblkmem(scip), HASHSIZE_SETPPCCONS, 327 SCIPhashGetKeyStandard, hashdataKeyEqCons, hashdataKeyValCons, (void*) scip) ); 328 SCIP_CALL( SCIPhashtableCreate(&(presoldata->setppchashtable), SCIPblkmem(scip), HASHSIZE_SETPPCCONS, 329 SCIPhashGetKeyStandard, SCIPhashKeyEqPtr, SCIPhashKeyValPtr, (void*) scip) ); 330 SCIP_CALL( SCIPhashtableCreate(&(presoldata->logicorhashtable), SCIPblkmem(scip), HASHSIZE_LOGICORCONS, 331 SCIPhashGetKeyStandard, SCIPhashKeyEqPtr, SCIPhashKeyValPtr, (void*) scip) ); 332 333 return SCIP_OKAY; 334 } 335 336 337 /** create useful set-packing information by adding new set-packing constraints with two variables */ 338 static 339 SCIP_RETCODE createPresoldata( 340 SCIP* scip, /**< SCIP data structure */ 341 SCIP_PRESOLDATA* presoldata, /**< data object of presolver */ 342 SCIP_CONS** setppcs, /**< active setppc constraints */ 343 int nsetppcs, /**< number of active setppc constraints */ 344 SCIP_CONS** logicors, /**< active logicor constraints */ 345 int nlogicors /**< number of active logicor constraints */ 346 ) 347 { 348 SCIP_CONS** usefulconss; 349 int nusefulconss = 0; 350 int size; 351 int c; 352 353 assert(scip != NULL); 354 assert(presoldata != NULL); 355 assert(setppcs != NULL); 356 assert(nsetppcs > 0); 357 assert(logicors != NULL); 358 assert(nlogicors > 0); 359 assert(presoldata->setppchashtable != NULL); 360 assert(presoldata->logicorhashtable != NULL); 361 362 presoldata->initialized = TRUE; 363 364 size = MAX(nsetppcs, nlogicors); 365 366 /* temporary memory for collecting set-packing constraints */ 367 SCIP_CALL( SCIPallocBufferArray(scip, &usefulconss, size) ); 368 369 if( !presoldata->usefulsetppcexist ) 370 { 371 /* find set-packing constraints with exactly two variables */ 372 for( c = 0; c < nsetppcs; ++c ) 373 { 374 assert(SCIPconsIsActive(setppcs[c])); 375 376 if( SCIPgetTypeSetppc(scip, setppcs[c]) == SCIP_SETPPCTYPE_PACKING && SCIPgetNVarsSetppc(scip, setppcs[c]) == 2 && !SCIPconsIsModifiable(setppcs[c]) ) 377 { 378 /* insert new element in hashtable */ 379 SCIP_CALL( SCIPhashtableInsert(presoldata->setppchashtable, (void*) setppcs[c]) ); 380 381 usefulconss[nusefulconss] = setppcs[c]; 382 ++nusefulconss; 383 } 384 } 385 386 /* add usefulconss constraints to hashdata elements */ 387 if( nusefulconss > 0 ) 388 { 389 SCIP_Bool negated[2]; 390 int h; 391 392 presoldata->usefulsetppcexist = TRUE; 393 presoldata->ssetppchashdatas = nusefulconss; 394 395 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(presoldata->setppchashdatas), nusefulconss) ); 396 397 h = 0; 398 for( c = 0; c < nusefulconss; ++c ) 399 { 400 SCIP_VAR** setppcvars = SCIPgetVarsSetppc(scip, usefulconss[c]); 401 assert(SCIPconsIsActive(usefulconss[c])); 402 assert(SCIPgetNVarsSetppc(scip, usefulconss[c]) == 2); 403 404 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(presoldata->setppchashdatas[h].vars), setppcvars, 2) ); 405 406 SCIP_CALL( SCIPgetBinvarRepresentative(scip, presoldata->setppchashdatas[h].vars[0], &(presoldata->setppchashdatas[h].vars[0]), &(negated[0])) ); 407 SCIP_CALL( SCIPgetBinvarRepresentative(scip, presoldata->setppchashdatas[h].vars[1], &(presoldata->setppchashdatas[h].vars[1]), &(negated[1])) ); 408 409 if( SCIPvarGetStatus(presoldata->setppchashdatas[h].vars[0]) == SCIP_VARSTATUS_FIXED || SCIPvarGetStatus(presoldata->setppchashdatas[h].vars[0]) == SCIP_VARSTATUS_MULTAGGR 410 || SCIPvarGetStatus(presoldata->setppchashdatas[h].vars[1]) == SCIP_VARSTATUS_FIXED || SCIPvarGetStatus(presoldata->setppchashdatas[h].vars[1]) == SCIP_VARSTATUS_MULTAGGR ) 411 { 412 SCIPfreeBlockMemoryArray(scip, &(presoldata->setppchashdatas[h].vars), 2); 413 continue; 414 } 415 416 presoldata->setppchashdatas[h].nvars = 2; 417 418 /* capture variables */ 419 SCIP_CALL( SCIPcaptureVar(scip, presoldata->setppchashdatas[h].vars[0]) ); 420 SCIP_CALL( SCIPcaptureVar(scip, presoldata->setppchashdatas[h].vars[1]) ); 421 422 /* order the variables after their index */ 423 if( SCIPvarGetIndex(presoldata->setppchashdatas[h].vars[0]) > SCIPvarGetIndex(presoldata->setppchashdatas[h].vars[1]) ) 424 { 425 SCIP_VAR* tmp = presoldata->setppchashdatas[h].vars[0]; 426 presoldata->setppchashdatas[h].vars[0] = presoldata->setppchashdatas[h].vars[1]; 427 presoldata->setppchashdatas[h].vars[1] = tmp; 428 } 429 430 presoldata->setppchashdatas[h].cons = usefulconss[c]; 431 432 SCIP_CALL( SCIPhashtableInsert(presoldata->hashdatatable, (void*) &presoldata->setppchashdatas[h]) ); 433 SCIP_CALL( SCIPcaptureCons(scip, usefulconss[c]) ); 434 435 ++h; 436 } 437 presoldata->nsetppchashdatas = h; 438 439 if( presoldata->nsetppchashdatas > 0 ) 440 presoldata->newsetppchashdatas = TRUE; 441 } 442 } 443 444 nusefulconss = 0; 445 446 if( !presoldata->usefullogicorexist ) 447 { 448 /* capture all logicor constraints */ 449 for( c = 0; c < nlogicors; ++c ) 450 { 451 assert(SCIPconsIsActive(logicors[c])); 452 453 if( !SCIPconsIsModifiable(logicors[c]) && SCIPgetNVarsLogicor(scip, logicors[c]) >= 3 ) 454 { 455 /* insert new element in hashtable */ 456 SCIP_CALL( SCIPhashtableInsert(presoldata->logicorhashtable, (void*) logicors[c]) ); 457 SCIP_CALL( SCIPcaptureCons(scip, logicors[c]) ); 458 459 usefulconss[nusefulconss] = logicors[c]; 460 ++nusefulconss; 461 462 /* update maximal entries in a logicor constraint */ 463 if( presoldata->maxnvarslogicor < SCIPgetNVarsLogicor(scip, logicors[c]) ) 464 presoldata->maxnvarslogicor = SCIPgetNVarsLogicor(scip, logicors[c]); 465 } 466 } 467 468 /* no usefulconss constraints */ 469 if( nusefulconss > 0 ) 470 { 471 presoldata->firstchangedlogicor = 0; 472 presoldata->usefullogicorexist = TRUE; 473 presoldata->susefullogicor = nusefulconss; 474 presoldata->nusefullogicor = nusefulconss; 475 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &presoldata->usefullogicor, usefulconss, presoldata->susefullogicor) ); 476 } 477 } 478 479 /* free temporary memory */ 480 SCIPfreeBufferArray(scip, &usefulconss); 481 482 return SCIP_OKAY; 483 } 484 485 486 /** remove old setppchashdatas objects, so that the allocated memory will stay low */ 487 static 488 SCIP_RETCODE cleanupHashDatas( 489 SCIP* scip, /**< SCIP data structure */ 490 SCIP_PRESOLDATA* presoldata /**< data object of presolver */ 491 ) 492 { 493 assert(scip != NULL); 494 assert(presoldata != NULL); 495 496 if( presoldata->usefulsetppcexist ) 497 { 498 int c; 499 500 assert(presoldata->setppchashdatas != NULL || presoldata->nsetppchashdatas == 0); 501 502 for( c = presoldata->nsetppchashdatas - 1; c >= 0; --c ) 503 { 504 SCIP_Bool removeentry = FALSE; 505 506 assert(presoldata->setppchashdatas[c].cons != NULL); 507 508 if( SCIPconsIsDeleted(presoldata->setppchashdatas[c].cons) || SCIPconsIsModifiable(presoldata->setppchashdatas[c].cons) 509 || SCIPgetTypeSetppc(scip, presoldata->setppchashdatas[c].cons) != SCIP_SETPPCTYPE_PACKING || SCIPgetNVarsSetppc(scip, presoldata->setppchashdatas[c].cons) != 2 ) 510 { 511 removeentry = TRUE; 512 } 513 else 514 { 515 SCIP_VAR* vars[2]; 516 SCIP_Bool negated[2]; 517 518 SCIP_CALL( SCIPgetBinvarRepresentative(scip, presoldata->setppchashdatas[c].vars[0], &(vars[0]), &(negated[0])) ); 519 SCIP_CALL( SCIPgetBinvarRepresentative(scip, presoldata->setppchashdatas[c].vars[1], &(vars[1]), &(negated[1])) ); 520 521 if( SCIPvarGetStatus(vars[0]) == SCIP_VARSTATUS_FIXED || SCIPvarGetStatus(vars[0]) == SCIP_VARSTATUS_MULTAGGR 522 || SCIPvarGetStatus(vars[1]) == SCIP_VARSTATUS_FIXED || SCIPvarGetStatus(vars[1]) == SCIP_VARSTATUS_MULTAGGR 523 || presoldata->setppchashdatas[c].vars[0] != vars[0] || presoldata->setppchashdatas[c].vars[1] != vars[1] ) 524 { 525 removeentry = TRUE; 526 } 527 } 528 529 if( removeentry ) 530 { 531 /* remove constraint from setppc-hashtable */ 532 assert(SCIPhashtableExists(presoldata->setppchashtable, (void*) presoldata->setppchashdatas[c].cons)); 533 SCIP_CALL( SCIPhashtableRemove(presoldata->setppchashtable, (void*) presoldata->setppchashdatas[c].cons) ); 534 535 /* remove hashdata entry from hashtable */ 536 SCIP_CALL( SCIPhashtableRemove(presoldata->hashdatatable, (void*) &presoldata->setppchashdatas[c]) ); 537 538 /* release old constraints */ 539 SCIP_CALL( SCIPreleaseCons(scip, &(presoldata->setppchashdatas[c].cons)) ); 540 541 /* release variables */ 542 SCIP_CALL( SCIPreleaseVar(scip, &(presoldata->setppchashdatas[c].vars[0])) ); 543 SCIP_CALL( SCIPreleaseVar(scip, &(presoldata->setppchashdatas[c].vars[1])) ); 544 545 /* free memory for variables */ 546 SCIPfreeBlockMemoryArray(scip, &(presoldata->setppchashdatas[c].vars), 2); 547 548 if( c < presoldata->nsetppchashdatas - 1 ) 549 { 550 /* remove old hashdata entry from hashtable */ 551 SCIP_CALL( SCIPhashtableRemove(presoldata->hashdatatable, (void*) &presoldata->setppchashdatas[presoldata->nsetppchashdatas - 1]) ); 552 } 553 554 /* move last content to free position */ 555 presoldata->setppchashdatas[c].cons = presoldata->setppchashdatas[presoldata->nsetppchashdatas - 1].cons; 556 presoldata->setppchashdatas[c].vars = presoldata->setppchashdatas[presoldata->nsetppchashdatas - 1].vars; 557 presoldata->setppchashdatas[c].nvars = presoldata->setppchashdatas[presoldata->nsetppchashdatas - 1].nvars; 558 559 if( c < presoldata->nsetppchashdatas - 1 ) 560 { 561 /* add new hashdata entry from hashtable */ 562 SCIP_CALL( SCIPhashtableInsert(presoldata->hashdatatable, (void*) &presoldata->setppchashdatas[c]) ); 563 } 564 --(presoldata->nsetppchashdatas); 565 } 566 } 567 568 #ifndef NDEBUG 569 for( c = presoldata->nsetppchashdatas - 1; c >= 0; --c ) 570 { 571 assert(presoldata->setppchashdatas[c].nvars == 2); 572 assert(presoldata->setppchashdatas[c].vars != NULL); 573 assert(presoldata->setppchashdatas[c].vars[0] != NULL); 574 assert(presoldata->setppchashdatas[c].vars[1] != NULL); 575 assert(presoldata->setppchashdatas[c].cons != NULL); 576 assert(SCIPconsIsActive(presoldata->setppchashdatas[c].cons)); 577 assert(SCIPhashtableExists(presoldata->hashdatatable, (void*) &presoldata->setppchashdatas[c])); 578 assert(SCIPhashtableExists(presoldata->setppchashtable, (void*) presoldata->setppchashdatas[c].cons)); 579 } 580 #endif 581 } 582 583 return SCIP_OKAY; 584 } 585 586 /** refresh useful set-packing information, delete redundant constraints and add new constraints */ 587 static 588 SCIP_RETCODE correctPresoldata( 589 SCIP* scip, /**< SCIP data structure */ 590 SCIP_PRESOLDATA* presoldata, /**< data object of presolver */ 591 SCIP_CONS** setppcs, /**< active setppc constraints */ 592 int nsetppcs, /**< number of active setppc constraints */ 593 SCIP_CONS** logicors, /**< active setppc constraints */ 594 int nlogicors /**< number of active setppc constraints */ 595 ) 596 { 597 int oldnsetppchashdatas; 598 int c; 599 600 assert(scip != NULL); 601 assert(presoldata != NULL); 602 assert(setppcs != NULL); 603 assert(nsetppcs > 0); 604 assert(logicors != NULL); 605 assert(nlogicors > 0); 606 assert(presoldata->initialized); 607 assert(presoldata->setppchashtable != NULL); 608 assert(presoldata->logicorhashtable != NULL); 609 610 /* check if there already exist some set-packing and some logicor constraints with the right amount of variables */ 611 if( !presoldata->usefulsetppcexist || !presoldata->usefullogicorexist ) 612 { 613 SCIP_Bool usefullogicorexisted = presoldata->usefullogicorexist; 614 615 SCIP_CALL( createPresoldata(scip, presoldata, setppcs, nsetppcs, logicors, nlogicors) ); 616 617 /* if we already had useful logicor constraints but did not find any useful setppc constraint, the maximal number 618 * of variables appearing in a logicor constraint was not updated, so we do it here 619 */ 620 if( usefullogicorexisted && !presoldata->usefulsetppcexist ) 621 { 622 /* correct maximal number of varables in logicor constraints */ 623 for( c = nlogicors - 1; c >= 0; --c ) 624 { 625 assert(SCIPconsIsActive(logicors[c])); 626 627 /* update maximal entries in a logicor constraint */ 628 if( presoldata->maxnvarslogicor < SCIPgetNVarsLogicor(scip, logicors[c]) ) 629 presoldata->maxnvarslogicor = SCIPgetNVarsLogicor(scip, logicors[c]); 630 } 631 } 632 633 /* no correct logicor or set-packing constraints available, so abort */ 634 if( !presoldata->usefulsetppcexist || !presoldata->usefullogicorexist ) 635 return SCIP_OKAY; 636 } 637 638 /* correct old data */ 639 SCIP_CALL( cleanupHashDatas(scip, presoldata) ); 640 641 oldnsetppchashdatas = presoldata->nsetppchashdatas; 642 643 /* first update setppc part */ 644 /* add new setppc constraints */ 645 for( c = nsetppcs - 1; c >= 0; --c ) 646 { 647 assert(SCIPconsIsActive(setppcs[c])); 648 649 if( SCIPgetTypeSetppc(scip, setppcs[c]) == SCIP_SETPPCTYPE_PACKING && SCIPgetNVarsSetppc(scip, setppcs[c]) == 2 && !SCIPconsIsModifiable(setppcs[c]) ) 650 { 651 /* check if constraint is new, and correct array size if necessary */ 652 if( !SCIPhashtableExists(presoldata->setppchashtable, (void*) setppcs[c]) ) 653 { 654 SCIP_VAR** setppcvars; 655 SCIP_Bool negated[2]; 656 657 /* resize array if necessary */ 658 if( presoldata->nsetppchashdatas == presoldata->ssetppchashdatas ) 659 { 660 int newsize; 661 int d; 662 663 newsize = SCIPcalcMemGrowSize(scip, presoldata->nsetppchashdatas + 1); 664 665 /* array already at maximal size */ 666 if( newsize <= presoldata->ssetppchashdatas ) 667 return SCIP_NOMEMORY; 668 669 /* correct hashtable, remove old elements */ 670 SCIPhashtableRemoveAll(presoldata->hashdatatable); 671 672 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(presoldata->setppchashdatas), presoldata->ssetppchashdatas, newsize) ); 673 presoldata->ssetppchashdatas = newsize; 674 675 /* add all elements to the hashtable again */ 676 for( d = presoldata->nsetppchashdatas - 1; d >= 0; --d ) 677 { 678 SCIP_CALL( SCIPhashtableInsert(presoldata->hashdatatable, (void*) &presoldata->setppchashdatas[d]) ); 679 } 680 } 681 682 /* insert new element in hashtable */ 683 SCIP_CALL( SCIPhashtableInsert(presoldata->setppchashtable, (void*) setppcs[c]) ); 684 685 assert(SCIPgetNVarsSetppc(scip, setppcs[c]) == 2); 686 setppcvars = SCIPgetVarsSetppc(scip, setppcs[c]); 687 688 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars), setppcvars, 2) ); 689 SCIP_CALL( SCIPgetBinvarRepresentative(scip, presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[0], &(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[0]), &(negated[0])) ); 690 SCIP_CALL( SCIPgetBinvarRepresentative(scip, presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[1], &(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[1]), &(negated[1])) ); 691 692 if( SCIPvarGetStatus(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[0]) == SCIP_VARSTATUS_FIXED || SCIPvarGetStatus(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[0]) == SCIP_VARSTATUS_MULTAGGR 693 || SCIPvarGetStatus(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[1]) == SCIP_VARSTATUS_FIXED || SCIPvarGetStatus(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[1]) == SCIP_VARSTATUS_MULTAGGR ) 694 { 695 SCIPfreeBlockMemoryArray(scip, &(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars), 2); 696 continue; 697 } 698 699 presoldata->setppchashdatas[presoldata->nsetppchashdatas].nvars = 2; 700 701 /* capture variables */ 702 SCIP_CALL( SCIPcaptureVar(scip, presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[0]) ); 703 SCIP_CALL( SCIPcaptureVar(scip, presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[1]) ); 704 705 /* order the variables after their index */ 706 if( SCIPvarGetIndex(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[0]) > SCIPvarGetIndex(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[1]) ) 707 { 708 SCIP_VAR* tmp = presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[0]; 709 presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[0] = presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[1]; 710 presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[1] = tmp; 711 } 712 713 presoldata->setppchashdatas[presoldata->nsetppchashdatas].cons = setppcs[c]; 714 715 SCIP_CALL( SCIPhashtableInsert(presoldata->hashdatatable, (void*) &presoldata->setppchashdatas[presoldata->nsetppchashdatas]) ); 716 SCIP_CALL( SCIPcaptureCons(scip, setppcs[c]) ); 717 718 ++(presoldata->nsetppchashdatas); 719 } 720 } 721 } 722 723 /* if we found new set-packing constraints, we want to check against all logicors */ 724 if( oldnsetppchashdatas < presoldata->nsetppchashdatas ) 725 presoldata->newsetppchashdatas = TRUE; 726 727 /* now logicor part */ 728 /* removed last deleted logicor constraints from local presolver data */ 729 while( presoldata->nusefullogicor > 0 && !SCIPconsIsActive(presoldata->usefullogicor[presoldata->nusefullogicor - 1]) ) 730 { 731 SCIP_CALL( SCIPhashtableRemove(presoldata->logicorhashtable, (void*) presoldata->usefullogicor[presoldata->nusefullogicor - 1]) ); 732 SCIP_CALL( SCIPreleaseCons(scip, &(presoldata->usefullogicor[presoldata->nusefullogicor - 1])) ); 733 734 --(presoldata->nusefullogicor); 735 } 736 737 /* remove old inactive logicor constraints */ 738 for( c = presoldata->nusefullogicor - 1; c >= 0; --c ) 739 { 740 /* update maximal entries in a logicor constraint */ 741 if( presoldata->maxnvarslogicor < SCIPgetNVarsLogicor(scip, presoldata->usefullogicor[c]) ) 742 presoldata->maxnvarslogicor = SCIPgetNVarsLogicor(scip, presoldata->usefullogicor[c]); 743 744 if( !SCIPconsIsActive(presoldata->usefullogicor[c]) || SCIPconsIsModifiable(presoldata->usefullogicor[c]) || SCIPgetNVarsLogicor(scip, presoldata->usefullogicor[c]) < 3 ) 745 { 746 SCIP_CALL( SCIPhashtableRemove(presoldata->logicorhashtable, (void*) presoldata->usefullogicor[c]) ); 747 SCIP_CALL( SCIPreleaseCons(scip, &(presoldata->usefullogicor[c])) ); 748 749 presoldata->usefullogicor[c] = presoldata->usefullogicor[presoldata->nusefullogicor - 1]; 750 --(presoldata->nusefullogicor); 751 } 752 } 753 754 presoldata->firstchangedlogicor = presoldata->nusefullogicor; 755 assert(presoldata->firstchangedlogicor >= 0); 756 757 /* add new logicor constraints */ 758 for( c = nlogicors - 1; c >= 0; --c ) 759 { 760 assert(SCIPconsIsActive(logicors[c])); 761 762 if( !SCIPconsIsModifiable(logicors[c]) && SCIPgetNVarsLogicor(scip, logicors[c]) >= 3 ) 763 { 764 /* check if constraint is new, and correct array size if necessary */ 765 if( !SCIPhashtableExists(presoldata->logicorhashtable, (void*) logicors[c]) ) 766 { 767 /* resize array if necessary */ 768 if( presoldata->nusefullogicor == presoldata->susefullogicor ) 769 { 770 int newsize; 771 772 newsize = SCIPcalcMemGrowSize(scip, presoldata->nusefullogicor + 1); 773 774 /* array already at maximal size */ 775 if( newsize <= presoldata->susefullogicor ) 776 return SCIP_NOMEMORY; 777 778 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(presoldata->usefullogicor), presoldata->susefullogicor, newsize) ); 779 presoldata->susefullogicor = newsize; 780 } 781 782 /* insert new element in hashtable */ 783 SCIP_CALL( SCIPhashtableInsert(presoldata->logicorhashtable, (void*) logicors[c]) ); 784 SCIP_CALL( SCIPcaptureCons(scip, logicors[c]) ); 785 786 presoldata->usefullogicor[presoldata->nusefullogicor] = logicors[c]; 787 ++(presoldata->nusefullogicor); 788 789 /* update maximal entries in a logicor constraint */ 790 if( presoldata->maxnvarslogicor < SCIPgetNVarsLogicor(scip, logicors[c]) ) 791 presoldata->maxnvarslogicor = SCIPgetNVarsLogicor(scip, logicors[c]); 792 } 793 } 794 } 795 796 return SCIP_OKAY; 797 } 798 799 800 /** extract and-constraints and set-partitioning constraints */ 801 static 802 SCIP_RETCODE extractGates( 803 SCIP* scip, /**< SCIP data structure */ 804 SCIP_PRESOLDATA* presoldata, /**< data object of presolver */ 805 int pos, /**< position of logicor in usefullogicor array to presolve */ 806 SCIP_HASHMAP* varmap, /**< variable map mapping inactive variables to their active representation */ 807 SCIP_CONS** gateconss, /**< allocated memory for all gate-constraints */ 808 SCIP_VAR** activevars, /**< allocated memory for active variables */ 809 SCIP_VAR** posresultants, /**< allocated memory for all possible resultant variables */ 810 HASHDATA* hashdata, /**< allocated memory for a hashdata object */ 811 int* ndelconss, /**< pointer to store number of deleted constraints */ 812 int* naddconss /**< pointer to store number of added constraints */ 813 ) 814 { 815 SCIP_VAR** logicorvars; 816 HASHDATA* hashmaphashdata; 817 SCIP_CONS* logicor; 818 SCIP_Bool negated; 819 int ngateconss; 820 int nlogicorvars; 821 int nposresultants; 822 int d; 823 int v; 824 825 assert(scip != NULL); 826 assert(presoldata != NULL); 827 assert(0 <= pos && pos < presoldata->nusefullogicor); 828 assert(gateconss != NULL); 829 assert(activevars != NULL); 830 assert(posresultants != NULL); 831 assert(hashdata != NULL); 832 assert(hashdata->vars != NULL); 833 assert(hashdata->nvars == 2); 834 assert(hashdata->cons == NULL); 835 assert(ndelconss != NULL); 836 assert(naddconss != NULL); 837 838 assert(presoldata->usefullogicor != NULL); 839 logicor = presoldata->usefullogicor[pos]; 840 assert(logicor != NULL); 841 842 if( !SCIPconsIsActive(logicor) ) 843 return SCIP_OKAY; 844 845 assert(!SCIPconsIsModifiable(logicor)); 846 847 nlogicorvars = SCIPgetNVarsLogicor(scip, logicor); 848 assert(nlogicorvars >= 3 && nlogicorvars <= presoldata->maxnvarslogicor); 849 850 logicorvars = SCIPgetVarsLogicor(scip, logicor); 851 assert(logicorvars != NULL); 852 853 nposresultants = 0; 854 855 /* get active logicor variables and determine all possible resultants */ 856 for( d = nlogicorvars - 1; d >= 0; --d ) 857 { 858 /* do not work with fixed variables */ 859 if( SCIPvarGetLbLocal(logicorvars[d]) > 0.5 || SCIPvarGetUbLocal(logicorvars[d]) < 0.5 ) 860 return SCIP_OKAY; 861 862 activevars[d] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, logicorvars[d]); 863 864 if( activevars[d] == NULL ) 865 { 866 SCIP_CALL( SCIPgetBinvarRepresentative(scip, logicorvars[d], &(activevars[d]), &negated) ); 867 SCIP_CALL( SCIPhashmapInsert(varmap, logicorvars[d], activevars[d]) ); 868 } 869 870 /* determine possible resultants a check if the other variables can appear in a set-packing constraint */ 871 if( SCIPvarIsNegated(activevars[d]) ) 872 { 873 assert(SCIPvarIsActive(SCIPvarGetNegatedVar(activevars[d]))); 874 875 if( SCIPvarGetNLocksDownType(SCIPvarGetNegatedVar(activevars[d]), SCIP_LOCKTYPE_MODEL) >= nlogicorvars - 1 ) 876 { 877 posresultants[nposresultants] = activevars[d]; 878 ++nposresultants; 879 } 880 else if( SCIPvarGetNLocksDownType(SCIPvarGetNegatedVar(activevars[d]), SCIP_LOCKTYPE_MODEL) == 0 ) 881 return SCIP_OKAY; 882 } 883 else 884 { 885 assert(SCIPvarIsActive(activevars[d])); 886 887 if( SCIPvarGetNLocksUpType(activevars[d], SCIP_LOCKTYPE_MODEL) >= nlogicorvars - 1 ) 888 { 889 posresultants[nposresultants] = activevars[d]; 890 ++nposresultants; 891 } 892 else if( SCIPvarGetNLocksUpType(activevars[d], SCIP_LOCKTYPE_MODEL) == 0 ) 893 return SCIP_OKAY; 894 } 895 } 896 897 if( nposresultants == 0 ) 898 return SCIP_OKAY; 899 900 /* sort variables after indices */ 901 SCIPsortPtr((void**)activevars, SCIPvarComp, nlogicorvars); 902 903 /* check that we have really different variables, if not remove the constraint from the hashmap and the data 904 * storage 905 */ 906 for( d = nlogicorvars - 1; d > 0; --d ) 907 { 908 if( SCIPvarGetIndex(activevars[d]) == SCIPvarGetIndex(activevars[d - 1]) ) 909 { 910 assert(presoldata->usefullogicor[pos] == logicor); 911 912 SCIP_CALL( SCIPhashtableRemove(presoldata->logicorhashtable, (void*) logicor) ); 913 SCIP_CALL( SCIPreleaseCons(scip, &logicor) ); 914 915 presoldata->usefullogicor[pos] = presoldata->usefullogicor[presoldata->nusefullogicor - 1]; 916 --(presoldata->nusefullogicor); 917 918 return SCIP_OKAY; 919 } 920 } 921 922 ngateconss = 0; 923 924 for( d = nposresultants - 1; d >= 0; --d ) 925 { 926 ngateconss = 0; 927 928 for( v = nlogicorvars - 1; v >= 0; --v ) 929 { 930 if( activevars[v] == posresultants[d] ) 931 continue; 932 933 /* variables need to be sorted */ 934 if( SCIPvarCompare(posresultants[d], activevars[v]) > 0 ) 935 { 936 hashdata->vars[0] = activevars[v]; 937 hashdata->vars[1] = posresultants[d]; 938 } 939 else 940 { 941 hashdata->vars[0] = posresultants[d]; 942 hashdata->vars[1] = activevars[v]; 943 } 944 945 hashmaphashdata = (HASHDATA*) SCIPhashtableRetrieve(presoldata->hashdatatable, (void*) hashdata); 946 947 if( hashmaphashdata != NULL && SCIPconsIsActive(hashmaphashdata->cons) ) 948 { 949 gateconss[ngateconss] = hashmaphashdata->cons; 950 ++ngateconss; 951 } 952 else 953 break; 954 } 955 if( ngateconss == nlogicorvars - 1 ) 956 break; 957 } 958 959 /* @todo, check for clique of all variables except the resultant */ 960 /* check if we have a set-partitioning 'gate' */ 961 if( ngateconss == nlogicorvars - 1 && nlogicorvars == 3 ) 962 { 963 assert(d >= 0 && d < nposresultants); 964 assert(ngateconss >= 2); 965 966 if( activevars[0] == posresultants[d] ) 967 { 968 hashdata->vars[0] = activevars[1]; 969 hashdata->vars[1] = activevars[2]; 970 } 971 else if( activevars[1] == posresultants[d] ) 972 { 973 hashdata->vars[0] = activevars[0]; 974 hashdata->vars[1] = activevars[2]; 975 } 976 else 977 { 978 assert(activevars[2] == posresultants[d]); 979 hashdata->vars[0] = activevars[0]; 980 hashdata->vars[1] = activevars[1]; 981 } 982 983 hashmaphashdata = (HASHDATA*) SCIPhashtableRetrieve(presoldata->hashdatatable, (void*) hashdata); 984 assert(hashmaphashdata == NULL || hashmaphashdata->cons != NULL); 985 986 if( hashmaphashdata != NULL && SCIPconsIsActive(hashmaphashdata->cons) ) 987 { 988 gateconss[ngateconss] = hashmaphashdata->cons; 989 ++ngateconss; 990 } 991 } 992 993 /* did we find enough (>= number of variables in logicor - 1) set-packing constraints for an upgrade to either 994 * an and-constraint or even a set-partitioning constraint 995 */ 996 if( ngateconss == nlogicorvars || (ngateconss >= nlogicorvars - 1 && !presoldata->onlysetpart)) 997 { 998 SCIP_CONS* newcons; 999 char name[SCIP_MAXSTRLEN]; 1000 SCIP_Bool initial; 1001 SCIP_Bool separate; 1002 SCIP_Bool enforce; 1003 SCIP_Bool check; 1004 SCIP_Bool propagate; 1005 SCIP_Bool local; 1006 SCIP_Bool modifiable; 1007 SCIP_Bool dynamic; 1008 SCIP_Bool removable; 1009 SCIP_Bool stickingatnode; 1010 int i; 1011 1012 assert(ngateconss <= nlogicorvars); 1013 assert(d >= 0 && d < nposresultants); 1014 1015 initial = SCIPconsIsInitial(logicor); 1016 separate = SCIPconsIsSeparated(logicor); 1017 enforce = SCIPconsIsEnforced(logicor); 1018 check = SCIPconsIsChecked(logicor); 1019 propagate = SCIPconsIsPropagated(logicor); 1020 local = SCIPconsIsLocal(logicor); 1021 modifiable = SCIPconsIsModifiable(logicor); 1022 dynamic = SCIPconsIsDynamic(logicor); 1023 removable = SCIPconsIsRemovable(logicor); 1024 stickingatnode = SCIPconsIsStickingAtNode(logicor); 1025 1026 #ifdef SCIP_DEBUG 1027 if( ngateconss == nlogicorvars ) 1028 { 1029 SCIPdebugMsg(scip, "Following constraints form a set-partitioning constraint.\n"); 1030 } 1031 else 1032 { 1033 SCIPdebugMsg(scip, "Following constraints form an and-constraint.\n"); 1034 } 1035 #endif 1036 1037 for( v = ngateconss - 1; v >= 0; --v ) 1038 { 1039 assert(gateconss[v] != NULL); 1040 1041 initial |= SCIPconsIsInitial(gateconss[v]); 1042 separate |= SCIPconsIsSeparated(gateconss[v]); 1043 enforce |= SCIPconsIsEnforced(gateconss[v]); 1044 check |= SCIPconsIsChecked(gateconss[v]); 1045 propagate |= SCIPconsIsPropagated(gateconss[v]); 1046 local &= SCIPconsIsLocal(gateconss[v]); 1047 modifiable &= SCIPconsIsModifiable(gateconss[v]); 1048 dynamic &= SCIPconsIsDynamic(gateconss[v]); 1049 removable &= SCIPconsIsRemovable(gateconss[v]); 1050 stickingatnode &= SCIPconsIsStickingAtNode(gateconss[v]); 1051 1052 SCIPdebugPrintCons(scip, gateconss[v], NULL); 1053 1054 SCIP_CALL( SCIPdelCons(scip, gateconss[v]) ); 1055 ++(*ndelconss); 1056 } 1057 1058 SCIPdebugPrintCons(scip, logicor, NULL); 1059 1060 if( ngateconss == nlogicorvars - 1 ) 1061 { 1062 SCIP_VAR** consvars; 1063 1064 assert(!presoldata->onlysetpart); 1065 1066 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, ngateconss) ); 1067 i = 0; 1068 1069 /* determine and operands */ 1070 for( v = nlogicorvars - 1; v >= 0; --v ) 1071 { 1072 if( activevars[v] == posresultants[d] ) 1073 continue; 1074 1075 SCIP_CALL( SCIPgetNegatedVar(scip, activevars[v], &consvars[i]) ); 1076 ++i; 1077 } 1078 assert(i == ngateconss); 1079 1080 /* create and add "and" constraint for the extracted gate */ 1081 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "andgate_%d", presoldata->ngates); 1082 SCIP_CALL( SCIPcreateConsAnd(scip, &newcons, name, posresultants[d], ngateconss, consvars, 1083 initial, separate, enforce, check, propagate, 1084 local, modifiable, dynamic, removable, stickingatnode) ); 1085 1086 SCIP_CALL( SCIPaddCons(scip, newcons) ); 1087 SCIPdebugMsg(scip, "-------------->\n"); 1088 SCIPdebugPrintCons(scip, newcons, NULL); 1089 1090 ++(*naddconss); 1091 ++(presoldata->ngates); 1092 1093 SCIP_CALL( SCIPdelCons(scip, logicor) ); 1094 ++(*ndelconss); 1095 1096 SCIP_CALL( SCIPreleaseCons(scip, &newcons) ); 1097 1098 SCIPfreeBufferArray(scip, &consvars); 1099 } 1100 else 1101 { 1102 assert(ngateconss == nlogicorvars); 1103 1104 /* create and add set-partitioning constraint */ 1105 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "setpart_%d", presoldata->ngates); 1106 SCIP_CALL( SCIPcreateConsSetpart(scip, &newcons, name, nlogicorvars, activevars, 1107 initial, separate, enforce, check, propagate, 1108 local, modifiable, dynamic, removable, stickingatnode) ); 1109 1110 SCIP_CALL( SCIPaddCons(scip, newcons) ); 1111 SCIPdebugMsg(scip, "-------------->\n"); 1112 SCIPdebugPrintCons(scip, newcons, NULL); 1113 1114 ++(*naddconss); 1115 ++(presoldata->ngates); 1116 1117 SCIP_CALL( SCIPdelCons(scip, logicor) ); 1118 ++(*ndelconss); 1119 1120 SCIP_CALL( SCIPreleaseCons(scip, &newcons) ); 1121 } 1122 } 1123 1124 return SCIP_OKAY; 1125 } 1126 1127 1128 /* 1129 * Callback methods of presolver 1130 */ 1131 1132 1133 /** copy method for constraint handler plugins (called when SCIP copies plugins) */ 1134 static 1135 SCIP_DECL_PRESOLCOPY(presolCopyGateextraction) 1136 { /*lint --e{715}*/ 1137 assert(scip != NULL); 1138 assert(presol != NULL); 1139 assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0); 1140 1141 /* call inclusion method of presolver */ 1142 SCIP_CALL( SCIPincludePresolGateextraction(scip) ); 1143 1144 return SCIP_OKAY; 1145 } 1146 1147 1148 /** destructor of presolver to free user data (called when SCIP is exiting) */ 1149 static 1150 SCIP_DECL_PRESOLFREE(presolFreeGateextraction) 1151 { /*lint --e{715}*/ 1152 SCIP_PRESOLDATA* presoldata; 1153 1154 /* free presolver data */ 1155 presoldata = SCIPpresolGetData(presol); 1156 assert(presoldata != NULL); 1157 1158 if( presoldata->hashdatatable != NULL ) 1159 { 1160 assert(presoldata->setppchashtable != NULL); 1161 assert(presoldata->logicorhashtable != NULL); 1162 1163 SCIPhashtableFree(&(presoldata->logicorhashtable)); 1164 SCIPhashtableFree(&(presoldata->setppchashtable)); 1165 SCIPhashtableFree(&(presoldata->hashdatatable)); 1166 } 1167 1168 SCIPfreeBlockMemory(scip, &presoldata); 1169 SCIPpresolSetData(presol, NULL); 1170 1171 return SCIP_OKAY; 1172 } 1173 1174 1175 /** deinitialization method of presolver (called before transformed problem is freed) */ 1176 static 1177 SCIP_DECL_PRESOLEXIT(presolExitGateextraction) 1178 { /*lint --e{715}*/ 1179 SCIP_PRESOLDATA* presoldata; 1180 int c; 1181 1182 /* free presolver data */ 1183 presoldata = SCIPpresolGetData(presol); 1184 assert(presoldata != NULL); 1185 1186 /* release old constraints */ 1187 for( c = presoldata->nusefullogicor - 1; c >= 0; --c ) 1188 { 1189 SCIP_CALL( SCIPreleaseCons(scip, &(presoldata->usefullogicor[c])) ); 1190 } 1191 1192 if( presoldata->usefullogicorexist ) 1193 { 1194 SCIPfreeBlockMemoryArray(scip, &presoldata->usefullogicor, presoldata->susefullogicor); 1195 } 1196 1197 if( presoldata->usefulsetppcexist ) 1198 { 1199 assert(presoldata->setppchashdatas != NULL || presoldata->nsetppchashdatas == 0); 1200 for( c = presoldata->nsetppchashdatas - 1; c >= 0; --c ) 1201 { 1202 assert(presoldata->setppchashdatas[c].cons != NULL); 1203 assert(presoldata->setppchashdatas[c].vars != NULL); 1204 1205 /* remove constraint from setppc-hashtable */ 1206 assert(SCIPhashtableExists(presoldata->setppchashtable, (void*) presoldata->setppchashdatas[c].cons)); 1207 SCIP_CALL( SCIPhashtableRemove(presoldata->setppchashtable, (void*) presoldata->setppchashdatas[c].cons) ); 1208 1209 /* remove hashdata entry from hashtable */ 1210 SCIP_CALL( SCIPhashtableRemove(presoldata->hashdatatable, (void*) &presoldata->setppchashdatas[c]) ); 1211 1212 /* release old constraints */ 1213 SCIP_CALL( SCIPreleaseCons(scip, &(presoldata->setppchashdatas[c].cons)) ); 1214 1215 /* release variables */ 1216 SCIP_CALL( SCIPreleaseVar(scip, &(presoldata->setppchashdatas[c].vars[0])) ); 1217 SCIP_CALL( SCIPreleaseVar(scip, &(presoldata->setppchashdatas[c].vars[1])) ); 1218 1219 /* free memory for variables */ 1220 SCIPfreeBlockMemoryArray(scip, &(presoldata->setppchashdatas[c].vars), 2); 1221 } 1222 1223 SCIPfreeBlockMemoryArray(scip, &(presoldata->setppchashdatas), presoldata->ssetppchashdatas); 1224 } 1225 1226 if( presoldata->hashdatatable != NULL ) 1227 { 1228 assert(presoldata->setppchashtable != NULL); 1229 assert(presoldata->logicorhashtable != NULL); 1230 1231 /* clear old hashtable entries */ 1232 SCIPhashtableRemoveAll(presoldata->hashdatatable); 1233 SCIPhashtableRemoveAll(presoldata->setppchashtable); 1234 SCIPhashtableRemoveAll(presoldata->logicorhashtable); 1235 } 1236 1237 presoldata->nusefullogicor = 0; 1238 presoldata->susefullogicor = 0; 1239 presoldata->nsetppchashdatas = 0; 1240 presoldata->ssetppchashdatas = 0; 1241 presoldata->firstchangedlogicor = -1; 1242 presoldata->ngates = 0; 1243 presoldata->usefullogicorexist = FALSE; 1244 presoldata->usefulsetppcexist = FALSE; 1245 presoldata->newsetppchashdatas = FALSE; 1246 presoldata->initialized = FALSE; 1247 1248 return SCIP_OKAY; 1249 } 1250 1251 1252 /** presolving initialization method of presolver (called when presolving is about to begin) */ 1253 static 1254 SCIP_DECL_PRESOLINITPRE(presolInitpreGateextraction) 1255 { /*lint --e{715}*/ 1256 return SCIP_OKAY; 1257 } 1258 1259 1260 /** presolving deinitialization method of presolver (called after presolving has been finished) */ 1261 static 1262 SCIP_DECL_PRESOLEXITPRE(presolExitpreGateextraction) 1263 { /*lint --e{715}*/ 1264 return SCIP_OKAY; 1265 } 1266 1267 1268 /** execution method of presolver */ 1269 static 1270 SCIP_DECL_PRESOLEXEC(presolExecGateextraction) 1271 { /*lint --e{715}*/ 1272 SCIP_PRESOLDATA* presoldata; 1273 SCIP_HASHMAP* varmap; 1274 HASHDATA hashdata; 1275 SCIP_VAR* tmpvars[2]; 1276 SCIP_CONSHDLR* conshdlrsetppc; 1277 SCIP_CONSHDLR* conshdlrlogicor; 1278 SCIP_CONSHDLR* conshdlrand; 1279 SCIP_CONS** setppcconss; 1280 SCIP_CONS** logicorconss; 1281 int nsetppcconss; 1282 int nlogicorconss; 1283 int size; 1284 int c; 1285 SCIP_Bool paramvalue; 1286 1287 assert(scip != NULL); 1288 assert(presol != NULL); 1289 assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0); 1290 assert(result != NULL); 1291 1292 *result = SCIP_DIDNOTRUN; 1293 1294 #if 0 /* need to include cons_knapsack on top of this file */ 1295 /* check for possible knapsacks that form with a logicor a weak relaxation of an and-constraint 1296 * 1297 * the weak relaxation of an and-constraint looks like: 1298 * - row1: resvar - v1 - ... - vn >= 1-n 1299 * - row2: n*resvar - v1 - ... - vn <= 0.0 1300 * 1301 * which look like the following contraints 1302 * - logicor: resvar + ~v1 + ... + ~vn >= 1 1303 * - knapsack: n*resvar + ~v1 + ... + ~vn <= n 1304 */ 1305 { 1306 SCIP_CONSHDLR* conshdlrknapsack; 1307 SCIP_CONS** knapsackconss; 1308 int nknapsackconss; 1309 SCIP_VAR** vars; 1310 SCIP_Longint* vals; 1311 SCIP_Longint capacity; 1312 int nvars; 1313 1314 conshdlrknapsack = SCIPfindConshdlr(scip, "knapsack"); 1315 1316 /* get number of active constraints */ 1317 knapsackconss = SCIPconshdlrGetConss(conshdlrknapsack); 1318 nknapsackconss = SCIPconshdlrGetNActiveConss(conshdlrknapsack); 1319 assert(nknapsackconss >= 0); 1320 assert(knapsackconss != NULL || nknapsackconss == 0); 1321 1322 for( c = nknapsackconss - 1; c >= 0; --c ) 1323 { 1324 /* not implemented in master branch, but the constraint may be already sorted */ 1325 /*SCIPsortKnapsack(scip, knapsackconss[c]);*/ 1326 1327 nvars = SCIPgetNVarsKnapsack(scip, knapsackconss[c]); 1328 vals = SCIPgetWeightsKnapsack(scip, knapsackconss[c]); 1329 vars = SCIPgetVarsKnapsack(scip, knapsackconss[c]); 1330 capacity = SCIPgetCapacityKnapsack(scip, knapsackconss[c]); 1331 1332 if( nvars > 1 && capacity == nvars - 1 && vals[0] == capacity && vals[1] == 1 ) 1333 { 1334 printf("possible knapsack for gate extraction\n"); 1335 } 1336 } 1337 } 1338 #endif 1339 1340 /* get necessary constraint handlers */ 1341 conshdlrsetppc = SCIPfindConshdlr(scip, "setppc"); 1342 conshdlrlogicor = SCIPfindConshdlr(scip, "logicor"); 1343 1344 if( conshdlrsetppc == NULL || conshdlrlogicor == NULL ) 1345 return SCIP_OKAY; 1346 1347 /* get number of active constraints */ 1348 nsetppcconss = SCIPconshdlrGetNActiveConss(conshdlrsetppc); 1349 assert(nsetppcconss >= 0); 1350 nlogicorconss = SCIPconshdlrGetNActiveConss(conshdlrlogicor); 1351 assert(nlogicorconss >= 0); 1352 1353 if( nsetppcconss == 0 || nlogicorconss == 0 ) 1354 return SCIP_OKAY; 1355 1356 /* get presolver data */ 1357 presoldata = SCIPpresolGetData(presol); 1358 assert(presoldata != NULL); 1359 1360 conshdlrand = SCIPfindConshdlr(scip, "and"); 1361 1362 /* need and-constraint handler to extract and-gates */ 1363 if( conshdlrand == NULL ) 1364 { 1365 /* nothing to do when we cannot extract anything */ 1366 if( !presoldata->searchequations ) 1367 return SCIP_OKAY; 1368 else 1369 { 1370 /* make sure that we correct the parameter for only extrating set-partitioning constraints */ 1371 if( SCIPisParamFixed(scip, "presolving/" PRESOL_NAME "/onlysetpart") ) 1372 { 1373 SCIPwarningMessage(scip, "unfixing parameter <presolving/" PRESOL_NAME "/onlysetpart> in gate extration presolver\n"); 1374 SCIP_CALL( SCIPunfixParam(scip, "presolving/" PRESOL_NAME "/onlysetpart") ); 1375 } 1376 SCIP_CALL( SCIPsetBoolParam(scip, "presolving/" PRESOL_NAME "/onlysetpart", TRUE) ); 1377 assert(presoldata->onlysetpart); 1378 } 1379 } 1380 1381 paramvalue = FALSE; 1382 if( conshdlrand != NULL && SCIPgetBoolParam(scip, "constraints/and/linearize", ¶mvalue) == SCIP_OKAY ) 1383 { 1384 if( paramvalue ) 1385 { 1386 SCIPwarningMessage(scip, "Gate-presolving is the 'counterpart' of linearizing all and-constraints, so enabling both presolving steps simultaneously does not make sense.\n"); 1387 } 1388 } 1389 *result = SCIP_DIDNOTFIND; 1390 1391 /* get active constraints */ 1392 SCIP_CALL( SCIPduplicateBufferArray(scip, &setppcconss, SCIPconshdlrGetConss(conshdlrsetppc), nsetppcconss) ); /*lint !e666*/ 1393 1394 assert(setppcconss != NULL); 1395 logicorconss = SCIPconshdlrGetConss(conshdlrlogicor); 1396 assert(logicorconss != NULL); 1397 1398 /* first we need to initialized the hashtables if not yet done */ 1399 if( presoldata->hashdatatable == NULL ) 1400 { 1401 SCIP_CALL( presoldataInitHashtables(scip, presoldata) ); 1402 } 1403 assert(presoldata->hashdatatable != NULL); 1404 assert(presoldata->setppchashtable != NULL); 1405 assert(presoldata->logicorhashtable != NULL); 1406 1407 presoldata->newsetppchashdatas = FALSE; 1408 1409 if( !presoldata->initialized ) 1410 { 1411 assert(presoldata->usefullogicor == NULL); 1412 1413 /* create useful set-packing information by adding new set-packing constraints with two variables */ 1414 SCIP_CALL( createPresoldata(scip, presoldata, setppcconss, nsetppcconss, logicorconss, nlogicorconss) ); 1415 } 1416 else 1417 { 1418 /* refresh useful set-packing information, delete redundant constraints and add new constraints */ 1419 SCIP_CALL( correctPresoldata(scip, presoldata, setppcconss, nsetppcconss, logicorconss, nlogicorconss) ); 1420 } 1421 assert(presoldata->initialized); 1422 1423 if( presoldata->nusefullogicor == 0 ) 1424 goto TERMINATE; 1425 1426 /* move the biggate extraction to front or back by sort the logicors after number of variables */ 1427 1428 if( presoldata->sorting != 0 ) 1429 { 1430 int* lengths; 1431 1432 SCIP_CALL( SCIPallocBufferArray(scip, &lengths, presoldata->nusefullogicor) ); 1433 1434 for( c = presoldata->nusefullogicor - 1; c >= 0; --c ) 1435 { 1436 lengths[c] = SCIPgetNVarsLogicor(scip, presoldata->usefullogicor[c]); 1437 } 1438 1439 if( presoldata->sorting == -1 ) 1440 SCIPsortDownIntPtr(lengths, (void**)presoldata->usefullogicor, presoldata->nusefullogicor); 1441 else 1442 SCIPsortIntPtr(lengths, (void**)presoldata->usefullogicor, presoldata->nusefullogicor); 1443 1444 SCIPfreeBufferArray(scip, &lengths); 1445 } 1446 1447 /* maximal number of binary variables */ 1448 size = SCIPgetNBinVars(scip) + SCIPgetNImplVars(scip); 1449 1450 /* create the variable mapping hash map */ 1451 SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(scip), size) ); 1452 1453 /* search for set-partitioning constraints arising from a logicor and a set-packing constraints with equal variables */ 1454 if( presoldata->searchequations && !SCIPisStopped(scip) ) 1455 { 1456 SCIP_HASHTABLE* setppchashdatatable; 1457 HASHDATA** setppchashdatas; 1458 HASHDATA* setppchashdatastore; 1459 HASHDATA* hashmaphashdata; 1460 SCIP_CONS* logicor; 1461 SCIP_CONS* setppc; 1462 SCIP_VAR** logicorvars; 1463 SCIP_VAR** setppcvars; 1464 SCIP_VAR** activevarslogicor; 1465 SCIP_VAR** activevarssetppc; 1466 SCIP_Bool negated; 1467 int nsetppchashdatas; 1468 int nlogicorvars; 1469 int nsetppcvars; 1470 int d; 1471 int v; 1472 1473 assert(nsetppcconss > 0); 1474 1475 /* create local hashtable */ 1476 SCIP_CALL( SCIPhashtableCreate(&setppchashdatatable, SCIPblkmem(scip), nsetppcconss, SCIPhashGetKeyStandard, setppcHashdataKeyEqCons, setppcHashdataKeyValCons, (void*) scip) ); 1477 1478 /* maximal number of binary variables */ 1479 size = presoldata->maxnvarslogicor; 1480 assert(size >= 3); 1481 1482 /* get temporary memory */ 1483 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &setppchashdatastore, nsetppcconss) ); 1484 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &setppchashdatas, nsetppcconss) ); 1485 SCIP_CALL( SCIPallocBufferArray(scip, &activevarssetppc, size) ); 1486 SCIP_CALL( SCIPallocBufferArray(scip, &activevarslogicor, size) ); 1487 1488 hashdata.cons = NULL; 1489 1490 nsetppchashdatas = 0; 1491 1492 /* collect all set-packing/-partitioning constraints and corresponding data to be able to search faster */ 1493 for( d = nsetppcconss - 1; d >= 0; --d ) 1494 { 1495 setppc = setppcconss[d]; 1496 assert(setppc != NULL); 1497 1498 if( SCIPconsIsDeleted(setppc) ) 1499 continue; 1500 1501 /* @todo if of interest could also be implemented for set-covering constraints */ 1502 #if 1 1503 if( SCIPgetTypeSetppc(scip, setppc) == SCIP_SETPPCTYPE_COVERING ) 1504 continue; 1505 #endif 1506 1507 nsetppcvars = SCIPgetNVarsSetppc(scip, setppc); 1508 1509 if( nsetppcvars < 2 ) 1510 continue; 1511 1512 if( SCIPconsIsModifiable(setppc) ) 1513 continue; 1514 1515 /* to big setppc constraints are picked out */ 1516 if( nsetppcvars > size ) 1517 continue; 1518 1519 setppcvars = SCIPgetVarsSetppc(scip, setppc); 1520 assert(setppcvars != NULL); 1521 1522 /* get active setppc variables */ 1523 for( v = nsetppcvars - 1; v >= 0; --v ) 1524 { 1525 /* do not work with fixed variables */ 1526 if( SCIPvarGetLbLocal(setppcvars[v]) > 0.5 || SCIPvarGetUbLocal(setppcvars[v]) < 0.5 ) 1527 break; 1528 1529 activevarssetppc[v] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, setppcvars[v]); 1530 1531 if( activevarssetppc[v] == NULL ) 1532 { 1533 SCIP_CALL( SCIPgetBinvarRepresentative(scip, setppcvars[v], &(activevarssetppc[v]), &negated) ); 1534 SCIP_CALL( SCIPhashmapInsert(varmap, setppcvars[v], activevarssetppc[v]) ); 1535 } 1536 } 1537 1538 /* if we found a fixed variable we want disregard this constraint */ 1539 if( v >= 0 ) 1540 continue; 1541 1542 /* variables need to be sorted after indices to be able to do a fast comparison */ 1543 SCIPsortPtr((void**)activevarssetppc, SCIPvarComp, nsetppcvars); 1544 1545 setppchashdatas[nsetppchashdatas] = &(setppchashdatastore[nsetppchashdatas]); 1546 1547 /* memorize set-packing data */ 1548 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(setppchashdatas[nsetppchashdatas]->vars), activevarssetppc, nsetppcvars) ); 1549 1550 setppchashdatas[nsetppchashdatas]->nvars = nsetppcvars; 1551 setppchashdatas[nsetppchashdatas]->cons = setppc; 1552 /* need to capture this constraint, because it might get deleted during the process */ 1553 SCIP_CALL( SCIPcaptureCons(scip, setppc) ); 1554 1555 /* add entry to local hashtable */ 1556 SCIP_CALL( SCIPhashtableInsert(setppchashdatatable, (void*) setppchashdatas[nsetppchashdatas]) ); 1557 ++nsetppchashdatas; 1558 } 1559 1560 /* check all (new) logicors against all collected set-packing/-partitioning constraints */ 1561 for( c = nlogicorconss - 1; c >= 0 && !SCIPisStopped(scip); --c ) 1562 { 1563 logicor = logicorconss[c]; 1564 assert(logicor != NULL); 1565 1566 if( SCIPconsIsDeleted(logicor) ) 1567 continue; 1568 1569 nlogicorvars = SCIPgetNVarsLogicor(scip, logicor); 1570 1571 if( nlogicorvars < 2 ) 1572 continue; 1573 1574 if( SCIPconsIsModifiable(logicor) ) 1575 continue; 1576 1577 assert(nlogicorvars <= size); 1578 1579 logicorvars = SCIPgetVarsLogicor(scip, logicor); 1580 assert(logicorvars != NULL); 1581 1582 /* get active logicor variables */ 1583 for( v = nlogicorvars - 1; v >= 0; --v ) 1584 { 1585 /* do not work with fixed variables */ 1586 if( SCIPvarGetLbLocal(logicorvars[v]) > 0.5 || SCIPvarGetUbLocal(logicorvars[v]) < 0.5 ) 1587 break; 1588 1589 activevarslogicor[v] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, logicorvars[v]); 1590 1591 /* if image does not exist, then there is no corresponding set-packing constraint */ 1592 if( activevarslogicor[v] == NULL ) 1593 break; 1594 } 1595 1596 if( v == -1 ) 1597 { 1598 /* need sorting to be able to find the correct hashdata element */ 1599 SCIPsortPtr((void**)activevarslogicor, SCIPvarComp, nlogicorvars); 1600 1601 hashdata.nvars = nlogicorvars; 1602 hashdata.vars = activevarslogicor; 1603 1604 hashmaphashdata = (HASHDATA*) SCIPhashtableRetrieve(setppchashdatatable, (void*) &hashdata); 1605 assert(hashmaphashdata == NULL || hashmaphashdata->cons != NULL); 1606 1607 if( hashmaphashdata != NULL && !SCIPconsIsDeleted(hashmaphashdata->cons) ) 1608 { 1609 SCIP_Bool initial; 1610 SCIP_Bool separate; 1611 SCIP_Bool enforce; 1612 SCIP_Bool check; 1613 SCIP_Bool propagate; 1614 SCIP_Bool local; 1615 SCIP_Bool modifiable; 1616 SCIP_Bool dynamic; 1617 SCIP_Bool removable; 1618 SCIP_Bool stickingatnode; 1619 1620 setppc = hashmaphashdata->cons; 1621 assert(SCIPconsGetHdlr(setppc) == SCIPfindConshdlr(scip, "setppc")); 1622 1623 initial = SCIPconsIsInitial(logicor) || SCIPconsIsInitial(setppc); 1624 separate = SCIPconsIsSeparated(logicor) || SCIPconsIsSeparated(setppc); 1625 enforce = SCIPconsIsEnforced(logicor) || SCIPconsIsEnforced(setppc); 1626 check = SCIPconsIsChecked(logicor) || SCIPconsIsChecked(setppc); 1627 propagate = SCIPconsIsPropagated(logicor) || SCIPconsIsPropagated(setppc); 1628 local = SCIPconsIsLocal(logicor) && SCIPconsIsLocal(setppc); 1629 modifiable = SCIPconsIsModifiable(logicor) && SCIPconsIsModifiable(setppc); 1630 dynamic = SCIPconsIsDynamic(logicor) && SCIPconsIsDynamic(setppc); 1631 removable = SCIPconsIsRemovable(logicor) && SCIPconsIsRemovable(setppc); 1632 stickingatnode = SCIPconsIsStickingAtNode(logicor) && SCIPconsIsStickingAtNode(setppc); 1633 1634 /* check if logicor is redundant against a set-partitioning constraint */ 1635 if( SCIPgetTypeSetppc(scip, setppc) == SCIP_SETPPCTYPE_PARTITIONING ) 1636 { 1637 SCIP_CALL( SCIPsetConsInitial(scip, setppc, initial) ); 1638 SCIP_CALL( SCIPsetConsSeparated(scip, setppc, separate) ); 1639 SCIP_CALL( SCIPsetConsEnforced(scip, setppc, enforce) ); 1640 SCIP_CALL( SCIPsetConsChecked(scip, setppc, check) ); 1641 SCIP_CALL( SCIPsetConsPropagated(scip, setppc, propagate) ); 1642 SCIP_CALL( SCIPsetConsLocal(scip, setppc, local) ); 1643 SCIP_CALL( SCIPsetConsModifiable(scip, setppc, modifiable) ); 1644 SCIP_CALL( SCIPsetConsDynamic(scip, setppc, dynamic) ); 1645 SCIP_CALL( SCIPsetConsRemovable(scip, setppc, removable) ); 1646 SCIP_CALL( SCIPsetConsStickingAtNode(scip, setppc, stickingatnode) ); 1647 1648 SCIPdebugMsg(scip, "Following logicor is redundant to the set-partitioning constraint.\n"); 1649 SCIPdebugPrintCons(scip, logicor, NULL); 1650 SCIPdebugPrintCons(scip, setppc, NULL); 1651 } 1652 else 1653 { 1654 SCIP_CONS* newcons; 1655 char name[SCIP_MAXSTRLEN]; 1656 1657 assert(SCIPgetTypeSetppc(scip, setppc) == SCIP_SETPPCTYPE_PACKING); 1658 1659 SCIPdebugMsg(scip, "Following logicor and set-packing constraints form a set-partitioning constraint.\n"); 1660 SCIPdebugPrintCons(scip, logicor, NULL); 1661 SCIPdebugPrintCons(scip, setppc, NULL); 1662 1663 /* create and add set-partitioning constraint */ 1664 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "setpart_%d", presoldata->ngates); 1665 SCIP_CALL( SCIPcreateConsSetpart(scip, &newcons, name, nlogicorvars, activevarslogicor, 1666 initial, separate, enforce, check, propagate, 1667 local, modifiable, dynamic, removable, stickingatnode) ); 1668 1669 SCIP_CALL( SCIPaddCons(scip, newcons) ); 1670 SCIPdebugMsg(scip, "-------------->\n"); 1671 SCIPdebugPrintCons(scip, newcons, NULL); 1672 1673 ++(*naddconss); 1674 ++(presoldata->ngates); 1675 1676 /* delete redundant set-packing constraint */ 1677 SCIP_CALL( SCIPdelCons(scip, setppc) ); 1678 ++(*ndelconss); 1679 1680 SCIP_CALL( SCIPreleaseCons(scip, &newcons) ); 1681 } 1682 1683 /* delete redundant logicor constraint */ 1684 SCIP_CALL( SCIPdelCons(scip, logicor) ); 1685 ++(*ndelconss); 1686 } 1687 } 1688 } 1689 1690 /* need to clear/release parts of hashdata objects */ 1691 for( d = nsetppchashdatas - 1; d >= 0; --d ) 1692 { 1693 /* need to release captured constraint */ 1694 SCIP_CALL( SCIPreleaseCons(scip, &(setppchashdatas[d]->cons)) ); 1695 /* need to free copied memory */ 1696 SCIPfreeBlockMemoryArray(scip, &(setppchashdatas[d]->vars), setppchashdatas[d]->nvars); 1697 } 1698 1699 /* delete local hashtable */ 1700 SCIPhashtableFree(&setppchashdatatable); 1701 1702 /* free all temporary memory */ 1703 SCIPfreeBufferArray(scip, &activevarslogicor); 1704 SCIPfreeBufferArray(scip, &activevarssetppc); 1705 SCIPfreeBlockMemoryArray(scip, &setppchashdatas, nsetppcconss); 1706 SCIPfreeBlockMemoryArray(scip, &setppchashdatastore, nsetppcconss); 1707 } 1708 1709 /* we do not have any useful set-packing or logicor constraint, or since last run did not get any new constraints, so abort */ 1710 if( presoldata->nsetppchashdatas == 0 || (presoldata->firstchangedlogicor == presoldata->nusefullogicor && !presoldata->newsetppchashdatas) ) 1711 { 1712 SCIPhashmapFree(&varmap); 1713 goto TERMINATE; 1714 } 1715 1716 assert(presoldata->usefullogicor != NULL); 1717 assert(presoldata->nusefullogicor > 0); 1718 assert(presoldata->firstchangedlogicor >= 0); 1719 assert(presoldata->nsetppchashdatas > 0); 1720 1721 /* search for gates */ 1722 if( presoldata->nsetppchashdatas > 0 && !SCIPisStopped(scip) ) 1723 { 1724 SCIP_CONS** gateconss; 1725 SCIP_VAR** activevars; 1726 SCIP_VAR** posresultants; 1727 int endloop; 1728 1729 /* if we found new setppcs we want to check all logicors again */ 1730 if( presoldata->newsetppchashdatas ) 1731 endloop = 0; 1732 else 1733 endloop = MAX(presoldata->firstchangedlogicor, 0); 1734 1735 assert(presoldata->maxnvarslogicor >= 3); 1736 SCIP_CALL( SCIPallocBufferArray(scip, &gateconss, presoldata->maxnvarslogicor) ); 1737 SCIP_CALL( SCIPallocBufferArray(scip, &activevars, presoldata->maxnvarslogicor) ); 1738 SCIP_CALL( SCIPallocBufferArray(scip, &posresultants, presoldata->maxnvarslogicor) ); 1739 1740 hashdata.nvars = 2; 1741 hashdata.cons = NULL; 1742 /* assign array of two variables as temporary storage to hashdata */ 1743 hashdata.vars = tmpvars; 1744 1745 /* check all (new) logicors against all set-packing constraints, to extract and-constraints with two or more 1746 * operands or set-partitioning constraints three or more variables 1747 */ 1748 for( c = presoldata->nusefullogicor - 1; c >= endloop && !SCIPisStopped(scip); --c ) 1749 { 1750 assert(presoldata->usefullogicor[c] != NULL); 1751 1752 /* logicor constraint has the form: x + y + z >= 1 1753 * 1754 * find set-packing constraints: (~x + ~y >= 1 and ~x + ~z >= 1) <=> (x + y <= 1 and x + z <= 1) 1755 * 1756 * - these three constraints are equivalent to: x = ~y * ~z (x = AND(~y,~z)) 1757 * 1758 * if an additional set-packing constraint exists: y + z <= 1 1759 * 1760 * - these four constraints are equivalent to: x + y + z = 1 1761 */ 1762 SCIP_CALL( extractGates(scip, presoldata, c, varmap, gateconss, activevars, posresultants, &hashdata, ndelconss, naddconss) ); 1763 } 1764 1765 SCIPfreeBufferArray(scip, &posresultants); 1766 SCIPfreeBufferArray(scip, &activevars); 1767 SCIPfreeBufferArray(scip, &gateconss); 1768 } 1769 1770 SCIPhashmapFree(&varmap); 1771 1772 TERMINATE: 1773 SCIPfreeBufferArray(scip, &setppcconss); 1774 1775 /* remove old setppchashdatas objects */ 1776 SCIP_CALL( cleanupHashDatas(scip, presoldata) ); 1777 1778 return SCIP_OKAY; 1779 } 1780 1781 1782 /* 1783 * presolver specific interface methods 1784 */ 1785 1786 /** creates the gateextraction presolver and includes it in SCIP */ 1787 SCIP_RETCODE SCIPincludePresolGateextraction( 1788 SCIP* scip /**< SCIP data structure */ 1789 ) 1790 { 1791 SCIP_PRESOLDATA* presoldata; 1792 SCIP_PRESOL* presol; 1793 1794 /* alloc presolve data object */ 1795 SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) ); 1796 1797 /* initialize gateextraction presolver data */ 1798 presoldataInit(presoldata); 1799 1800 /* include presolver */ 1801 SCIP_CALL( SCIPincludePresolBasic(scip, &presol, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS, 1802 PRESOL_TIMING, presolExecGateextraction, presoldata) ); 1803 1804 SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyGateextraction) ); 1805 SCIP_CALL( SCIPsetPresolFree(scip, presol, presolFreeGateextraction) ); 1806 SCIP_CALL( SCIPsetPresolExit(scip, presol, presolExitGateextraction) ); 1807 SCIP_CALL( SCIPsetPresolInitpre(scip, presol, presolInitpreGateextraction) ); 1808 SCIP_CALL( SCIPsetPresolExitpre(scip, presol, presolExitpreGateextraction) ); 1809 1810 /* add gateextraction presolver parameters */ 1811 SCIP_CALL( SCIPaddBoolParam(scip, 1812 "presolving/" PRESOL_NAME "/onlysetpart", 1813 "should we only try to extract set-partitioning constraints and no and-constraints", 1814 &presoldata->onlysetpart, TRUE, DEFAULT_ONLYSETPART, NULL, NULL) ); 1815 1816 /* add gateextraction presolver parameters */ 1817 SCIP_CALL( SCIPaddBoolParam(scip, 1818 "presolving/" PRESOL_NAME "/searchequations", 1819 "should we try to extract set-partitioning constraint out of one logicor and one corresponding set-packing constraint", 1820 &presoldata->searchequations, TRUE, DEFAULT_SEARCHEQUATIONS, NULL, NULL) ); 1821 1822 /* add gateextraction presolver parameters */ 1823 SCIP_CALL( SCIPaddIntParam(scip, 1824 "presolving/" PRESOL_NAME "/sorting", 1825 "order logicor contraints to extract big-gates before smaller ones (-1), do not order them (0) or order them to extract smaller gates at first (1)", 1826 &presoldata->sorting, TRUE, DEFAULT_SORTING, -1, 1, NULL, NULL) ); 1827 1828 return SCIP_OKAY; 1829 } 1830