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