Scippy

SCIP

Solving Constraint Integer Programs

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