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  assert(SCIPconsIsActive(usefulconss[c]));
379  assert(SCIPgetNVarsSetppc(scip, usefulconss[c]) == 2);
380 
381  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(presoldata->setppchashdatas[h].vars), SCIPgetVarsSetppc(scip, usefulconss[c]), 2) );
382 
383  SCIP_CALL( SCIPgetBinvarRepresentative(scip, presoldata->setppchashdatas[h].vars[0], &(presoldata->setppchashdatas[h].vars[0]), &(negated[0])) );
384  SCIP_CALL( SCIPgetBinvarRepresentative(scip, presoldata->setppchashdatas[h].vars[1], &(presoldata->setppchashdatas[h].vars[1]), &(negated[1])) );
385 
386  if( SCIPvarGetStatus(presoldata->setppchashdatas[h].vars[0]) == SCIP_VARSTATUS_FIXED || SCIPvarGetStatus(presoldata->setppchashdatas[h].vars[0]) == SCIP_VARSTATUS_MULTAGGR
387  || SCIPvarGetStatus(presoldata->setppchashdatas[h].vars[1]) == SCIP_VARSTATUS_FIXED || SCIPvarGetStatus(presoldata->setppchashdatas[h].vars[1]) == SCIP_VARSTATUS_MULTAGGR )
388  {
389  SCIPfreeBlockMemoryArray(scip, &(presoldata->setppchashdatas[h].vars), 2);
390  continue;
391  }
392 
393  presoldata->setppchashdatas[h].nvars = 2;
394 
395  /* capture variables */
396  SCIP_CALL( SCIPcaptureVar(scip, presoldata->setppchashdatas[h].vars[0]) );
397  SCIP_CALL( SCIPcaptureVar(scip, presoldata->setppchashdatas[h].vars[1]) );
398 
399  /* order the variables after their index */
400  if( SCIPvarGetIndex(presoldata->setppchashdatas[h].vars[0]) > SCIPvarGetIndex(presoldata->setppchashdatas[h].vars[1]) )
401  {
402  SCIP_VAR* tmp = presoldata->setppchashdatas[h].vars[0];
403  presoldata->setppchashdatas[h].vars[0] = presoldata->setppchashdatas[h].vars[1];
404  presoldata->setppchashdatas[h].vars[1] = tmp;
405  }
406 
407  presoldata->setppchashdatas[h].cons = usefulconss[c];
408 
409  SCIP_CALL( SCIPhashtableInsert(presoldata->hashdatatable, (void*) &presoldata->setppchashdatas[h]) );
410  SCIP_CALL( SCIPcaptureCons(scip, usefulconss[c]) );
411 
412  ++h;
413  }
414  presoldata->nsetppchashdatas = h;
415 
416  if( presoldata->nsetppchashdatas > 0 )
417  presoldata->newsetppchashdatas = TRUE;
418  }
419  }
420 
421  nusefulconss = 0;
422 
423  if( !presoldata->usefullogicorexist )
424  {
425  /* capture all logicor constraints */
426  for( c = 0; c < nlogicors; ++c )
427  {
428  assert(SCIPconsIsActive(logicors[c]));
429 
430  if( !SCIPconsIsModifiable(logicors[c]) && SCIPgetNVarsLogicor(scip, logicors[c]) >= 3 )
431  {
432  /* insert new element in hashtable */
433  SCIP_CALL( SCIPhashtableInsert(presoldata->logicorhashtable, (void*) logicors[c]) );
434  SCIP_CALL( SCIPcaptureCons(scip, logicors[c]) );
435 
436  usefulconss[nusefulconss] = logicors[c];
437  ++nusefulconss;
438 
439  /* update maximal entries in a logicor constraint */
440  if( presoldata->maxnvarslogicor < SCIPgetNVarsLogicor(scip, logicors[c]) )
441  presoldata->maxnvarslogicor = SCIPgetNVarsLogicor(scip, logicors[c]);
442  }
443  }
444 
445  /* no usefulconss constraints */
446  if( nusefulconss > 0 )
447  {
448  presoldata->firstchangedlogicor = 0;
449  presoldata->usefullogicorexist = TRUE;
450  presoldata->susefullogicor = nusefulconss;
451  presoldata->nusefullogicor = nusefulconss;
452  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &presoldata->usefullogicor, usefulconss, presoldata->susefullogicor) );
453  }
454  }
455 
456  /* free temporary memory */
457  SCIPfreeBufferArray(scip, &usefulconss);
458 
459  return SCIP_OKAY;
460 }
461 
462 
463 /** remove old setppchashdatas objects, so that the allocated memory will stay low */
464 static
466  SCIP* scip, /**< SCIP data structure */
467  SCIP_PRESOLDATA* presoldata /**< data object of presolver */
468  )
469 {
470  assert(scip != NULL);
471  assert(presoldata != NULL);
472 
473  if( presoldata->usefulsetppcexist )
474  {
475  int c;
476 
477  assert(presoldata->setppchashdatas != NULL || presoldata->nsetppchashdatas == 0);
478 
479  for( c = presoldata->nsetppchashdatas - 1; c >= 0; --c )
480  {
481  SCIP_Bool removeentry = FALSE;
482 
483  assert(presoldata->setppchashdatas[c].cons != NULL);
484 
485  if( SCIPconsIsDeleted(presoldata->setppchashdatas[c].cons) || SCIPconsIsModifiable(presoldata->setppchashdatas[c].cons)
486  || SCIPgetTypeSetppc(scip, presoldata->setppchashdatas[c].cons) != SCIP_SETPPCTYPE_PACKING || SCIPgetNVarsSetppc(scip, presoldata->setppchashdatas[c].cons) != 2 )
487  {
488  removeentry = TRUE;
489  }
490  else
491  {
492  SCIP_VAR* vars[2];
493  SCIP_Bool negated[2];
494 
495  SCIP_CALL( SCIPgetBinvarRepresentative(scip, presoldata->setppchashdatas[c].vars[0], &(vars[0]), &(negated[0])) );
496  SCIP_CALL( SCIPgetBinvarRepresentative(scip, presoldata->setppchashdatas[c].vars[1], &(vars[1]), &(negated[1])) );
497 
500  || presoldata->setppchashdatas[c].vars[0] != vars[0] || presoldata->setppchashdatas[c].vars[1] != vars[1] )
501  {
502  removeentry = TRUE;
503  }
504  }
505 
506  if( removeentry )
507  {
508  /* remove constraint from setppc-hashtable */
509  assert(SCIPhashtableExists(presoldata->setppchashtable, (void*) presoldata->setppchashdatas[c].cons));
510  SCIP_CALL( SCIPhashtableRemove(presoldata->setppchashtable, (void*) presoldata->setppchashdatas[c].cons) );
511 
512  /* remove hashdata entry from hashtable */
513  SCIP_CALL( SCIPhashtableRemove(presoldata->hashdatatable, (void*) &presoldata->setppchashdatas[c]) );
514 
515  /* release old constraints */
516  SCIP_CALL( SCIPreleaseCons(scip, &(presoldata->setppchashdatas[c].cons)) );
517 
518  /* release variables */
519  SCIP_CALL( SCIPreleaseVar(scip, &(presoldata->setppchashdatas[c].vars[0])) );
520  SCIP_CALL( SCIPreleaseVar(scip, &(presoldata->setppchashdatas[c].vars[1])) );
521 
522  /* free memory for variables */
523  SCIPfreeBlockMemoryArray(scip, &(presoldata->setppchashdatas[c].vars), 2);
524 
525  if( c < presoldata->nsetppchashdatas - 1 )
526  {
527  /* remove old hashdata entry from hashtable */
528  SCIP_CALL( SCIPhashtableRemove(presoldata->hashdatatable, (void*) &presoldata->setppchashdatas[presoldata->nsetppchashdatas - 1]) );
529  }
530 
531  /* move last content to free position */
532  presoldata->setppchashdatas[c].cons = presoldata->setppchashdatas[presoldata->nsetppchashdatas - 1].cons;
533  presoldata->setppchashdatas[c].vars = presoldata->setppchashdatas[presoldata->nsetppchashdatas - 1].vars;
534  presoldata->setppchashdatas[c].nvars = presoldata->setppchashdatas[presoldata->nsetppchashdatas - 1].nvars;
535 
536  if( c < presoldata->nsetppchashdatas - 1 )
537  {
538  /* add new hashdata entry from hashtable */
539  SCIP_CALL( SCIPhashtableInsert(presoldata->hashdatatable, (void*) &presoldata->setppchashdatas[c]) );
540  }
541  --(presoldata->nsetppchashdatas);
542  }
543  }
544 
545 #ifndef NDEBUG
546  for( c = presoldata->nsetppchashdatas - 1; c >= 0; --c )
547  {
548  assert(presoldata->setppchashdatas[c].nvars == 2);
549  assert(presoldata->setppchashdatas[c].vars != NULL);
550  assert(presoldata->setppchashdatas[c].vars[0] != NULL);
551  assert(presoldata->setppchashdatas[c].vars[1] != NULL);
552  assert(presoldata->setppchashdatas[c].cons != NULL);
553  assert(SCIPconsIsActive(presoldata->setppchashdatas[c].cons));
554  assert(SCIPhashtableExists(presoldata->hashdatatable, (void*) &presoldata->setppchashdatas[c]));
555  assert(SCIPhashtableExists(presoldata->setppchashtable, (void*) presoldata->setppchashdatas[c].cons));
556  }
557 #endif
558  }
559 
560  return SCIP_OKAY;
561 }
562 
563 /** refresh useful set-packing information, delete redundant constraints and add new constraints */
564 static
566  SCIP* scip, /**< SCIP data structure */
567  SCIP_PRESOLDATA* presoldata, /**< data object of presolver */
568  SCIP_CONS** setppcs, /**< active setppc constraints */
569  int nsetppcs, /**< number of active setppc constraints */
570  SCIP_CONS** logicors, /**< active setppc constraints */
571  int nlogicors /**< number of active setppc constraints */
572  )
573 {
574  int oldnsetppchashdatas;
575  int c;
576 
577  assert(scip != NULL);
578  assert(presoldata != NULL);
579  assert(setppcs != NULL);
580  assert(nsetppcs > 0);
581  assert(logicors != NULL);
582  assert(nlogicors > 0);
583  assert(presoldata->initialized);
584  assert(presoldata->setppchashtable != NULL);
585  assert(presoldata->logicorhashtable != NULL);
586 
587  /* check if there already exist some set-packing and some logicor constraints with the right amount of variables */
588  if( !presoldata->usefulsetppcexist || !presoldata->usefullogicorexist )
589  {
590  SCIP_Bool usefullogicorexisted = presoldata->usefullogicorexist;
591 
592  SCIP_CALL( createPresoldata(scip, presoldata, setppcs, nsetppcs, logicors, nlogicors) );
593 
594  /* if we already had useful logicor constraints but did not find any useful setppc constraint, the maximal number
595  * of variables appearing in a logicor constraint was not updated, so we do it here
596  */
597  if( usefullogicorexisted && !presoldata->usefulsetppcexist )
598  {
599  /* correct maximal number of varables in logicor constraints */
600  for( c = nlogicors - 1; c >= 0; --c )
601  {
602  assert(SCIPconsIsActive(logicors[c]));
603 
604  /* update maximal entries in a logicor constraint */
605  if( presoldata->maxnvarslogicor < SCIPgetNVarsLogicor(scip, logicors[c]) )
606  presoldata->maxnvarslogicor = SCIPgetNVarsLogicor(scip, logicors[c]);
607  }
608  }
609 
610  /* no correct logicor or set-packing constraints available, so abort */
611  if( !presoldata->usefulsetppcexist || !presoldata->usefullogicorexist )
612  return SCIP_OKAY;
613  }
614 
615  /* correct old data */
616  SCIP_CALL( cleanupHashDatas(scip, presoldata) );
617 
618  oldnsetppchashdatas = presoldata->nsetppchashdatas;
619 
620  /* first update setppc part */
621  /* add new setppc constraints */
622  for( c = nsetppcs - 1; c >= 0; --c )
623  {
624  assert(SCIPconsIsActive(setppcs[c]));
625 
626  if( SCIPgetTypeSetppc(scip, setppcs[c]) == SCIP_SETPPCTYPE_PACKING && SCIPgetNVarsSetppc(scip, setppcs[c]) == 2 && !SCIPconsIsModifiable(setppcs[c]) )
627  {
628  /* check if constraint is new, and correct array size if necessary */
629  if( !SCIPhashtableExists(presoldata->setppchashtable, (void*) setppcs[c]) )
630  {
631  SCIP_Bool negated[2];
632 
633  /* resize array if necessary */
634  if( presoldata->nsetppchashdatas == presoldata->ssetppchashdatas )
635  {
636  int newsize;
637  int d;
638 
639  newsize = SCIPcalcMemGrowSize(scip, presoldata->nsetppchashdatas + 1);
640 
641  /* array already at maximal size */
642  if( newsize <= presoldata->ssetppchashdatas )
643  return SCIP_NOMEMORY;
644 
645  /* correct hashtable, remove old elements */
646  SCIPhashtableRemoveAll(presoldata->hashdatatable);
647 
648  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(presoldata->setppchashdatas), presoldata->ssetppchashdatas, newsize) );
649  presoldata->ssetppchashdatas = newsize;
650 
651  /* add all elements to the hashtable again */
652  for( d = presoldata->nsetppchashdatas - 1; d >= 0; --d )
653  {
654  SCIP_CALL( SCIPhashtableInsert(presoldata->hashdatatable, (void*) &presoldata->setppchashdatas[d]) );
655  }
656  }
657 
658  /* insert new element in hashtable */
659  SCIP_CALL( SCIPhashtableInsert(presoldata->setppchashtable, (void*) setppcs[c]) );
660 
661  assert(SCIPgetNVarsSetppc(scip, setppcs[c]) == 2);
662 
663  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars), SCIPgetVarsSetppc(scip, setppcs[c]), 2) );
664  SCIP_CALL( SCIPgetBinvarRepresentative(scip, presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[0], &(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[0]), &(negated[0])) );
665  SCIP_CALL( SCIPgetBinvarRepresentative(scip, presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[1], &(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[1]), &(negated[1])) );
666 
667  if( SCIPvarGetStatus(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[0]) == SCIP_VARSTATUS_FIXED || SCIPvarGetStatus(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[0]) == SCIP_VARSTATUS_MULTAGGR
668  || SCIPvarGetStatus(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[1]) == SCIP_VARSTATUS_FIXED || SCIPvarGetStatus(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[1]) == SCIP_VARSTATUS_MULTAGGR )
669  {
670  SCIPfreeBlockMemoryArray(scip, &(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars), 2);
671  continue;
672  }
673 
674  presoldata->setppchashdatas[presoldata->nsetppchashdatas].nvars = 2;
675 
676  /* capture variables */
677  SCIP_CALL( SCIPcaptureVar(scip, presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[0]) );
678  SCIP_CALL( SCIPcaptureVar(scip, presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[1]) );
679 
680  /* order the variables after their index */
681  if( SCIPvarGetIndex(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[0]) > SCIPvarGetIndex(presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[1]) )
682  {
683  SCIP_VAR* tmp = presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[0];
684  presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[0] = presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[1];
685  presoldata->setppchashdatas[presoldata->nsetppchashdatas].vars[1] = tmp;
686  }
687 
688  presoldata->setppchashdatas[presoldata->nsetppchashdatas].cons = setppcs[c];
689 
690  SCIP_CALL( SCIPhashtableInsert(presoldata->hashdatatable, (void*) &presoldata->setppchashdatas[presoldata->nsetppchashdatas]) );
691  SCIP_CALL( SCIPcaptureCons(scip, setppcs[c]) );
692 
693  ++(presoldata->nsetppchashdatas);
694  }
695  }
696  }
697 
698  /* if we found new set-packing constraints, we want to check against all logicors */
699  if( oldnsetppchashdatas < presoldata->nsetppchashdatas )
700  presoldata->newsetppchashdatas = TRUE;
701 
702  /* now logicor part */
703  /* removed last deleted logicor constraints from local presolver data */
704  while( presoldata->nusefullogicor > 0 && !SCIPconsIsActive(presoldata->usefullogicor[presoldata->nusefullogicor - 1]) )
705  {
706  SCIP_CALL( SCIPhashtableRemove(presoldata->logicorhashtable, (void*) presoldata->usefullogicor[presoldata->nusefullogicor - 1]) );
707  SCIP_CALL( SCIPreleaseCons(scip, &(presoldata->usefullogicor[presoldata->nusefullogicor - 1])) );
708 
709  --(presoldata->nusefullogicor);
710  }
711 
712  /* remove old inactive logicor constraints */
713  for( c = presoldata->nusefullogicor - 1; c >= 0; --c )
714  {
715  /* update maximal entries in a logicor constraint */
716  if( presoldata->maxnvarslogicor < SCIPgetNVarsLogicor(scip, presoldata->usefullogicor[c]) )
717  presoldata->maxnvarslogicor = SCIPgetNVarsLogicor(scip, presoldata->usefullogicor[c]);
718 
719  if( !SCIPconsIsActive(presoldata->usefullogicor[c]) || SCIPconsIsModifiable(presoldata->usefullogicor[c]) || SCIPgetNVarsLogicor(scip, presoldata->usefullogicor[c]) < 3 )
720  {
721  SCIP_CALL( SCIPhashtableRemove(presoldata->logicorhashtable, (void*) presoldata->usefullogicor[c]) );
722  SCIP_CALL( SCIPreleaseCons(scip, &(presoldata->usefullogicor[c])) );
723 
724  presoldata->usefullogicor[c] = presoldata->usefullogicor[presoldata->nusefullogicor - 1];
725  --(presoldata->nusefullogicor);
726  }
727  }
728 
729  presoldata->firstchangedlogicor = presoldata->nusefullogicor;
730  assert(presoldata->firstchangedlogicor >= 0);
731 
732  /* add new logicor constraints */
733  for( c = nlogicors - 1; c >= 0; --c )
734  {
735  assert(SCIPconsIsActive(logicors[c]));
736 
737  if( !SCIPconsIsModifiable(logicors[c]) && SCIPgetNVarsLogicor(scip, logicors[c]) >= 3 )
738  {
739  /* check if constraint is new, and correct array size if necessary */
740  if( !SCIPhashtableExists(presoldata->logicorhashtable, (void*) logicors[c]) )
741  {
742  /* resize array if necessary */
743  if( presoldata->nusefullogicor == presoldata->susefullogicor )
744  {
745  int newsize;
746 
747  newsize = SCIPcalcMemGrowSize(scip, presoldata->nusefullogicor + 1);
748 
749  /* array already at maximal size */
750  if( newsize <= presoldata->susefullogicor )
751  return SCIP_NOMEMORY;
752 
753  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(presoldata->usefullogicor), presoldata->susefullogicor, newsize) );
754  presoldata->susefullogicor = newsize;
755  }
756 
757  /* insert new element in hashtable */
758  SCIP_CALL( SCIPhashtableInsert(presoldata->logicorhashtable, (void*) logicors[c]) );
759  SCIP_CALL( SCIPcaptureCons(scip, logicors[c]) );
760 
761  presoldata->usefullogicor[presoldata->nusefullogicor] = logicors[c];
762  ++(presoldata->nusefullogicor);
763 
764  /* update maximal entries in a logicor constraint */
765  if( presoldata->maxnvarslogicor < SCIPgetNVarsLogicor(scip, logicors[c]) )
766  presoldata->maxnvarslogicor = SCIPgetNVarsLogicor(scip, logicors[c]);
767  }
768  }
769  }
770 
771  return SCIP_OKAY;
772 }
773 
774 
775 /** extract and-constraints and set-partitioning constraints */
776 static
778  SCIP* scip, /**< SCIP data structure */
779  SCIP_PRESOLDATA* presoldata, /**< data object of presolver */
780  int pos, /**< position of logicor in usefullogicor array to presolve */
781  SCIP_HASHMAP* varmap, /**< variable map mapping inactive variables to their active representation */
782  SCIP_CONS** gateconss, /**< allocated memory for all gate-constraints */
783  SCIP_VAR** activevars, /**< allocated memory for active variables */
784  SCIP_VAR** posresultants, /**< allocated memory for all possible resultant variables */
785  HASHDATA* hashdata, /**< allocated memory for a hashdata object */
786  int* ndelconss, /**< pointer to store number of deleted constraints */
787  int* naddconss /**< pointer to store number of added constraints */
788  )
789 {
790  SCIP_VAR** logicorvars;
791  HASHDATA* hashmaphashdata;
792  SCIP_CONS* logicor;
793  SCIP_Bool negated;
794  int ngateconss;
795  int nlogicorvars;
796  int nposresultants;
797  int d;
798  int v;
799 
800  assert(scip != NULL);
801  assert(presoldata != NULL);
802  assert(0 <= pos && pos < presoldata->nusefullogicor);
803  assert(gateconss != NULL);
804  assert(activevars != NULL);
805  assert(posresultants != NULL);
806  assert(hashdata != NULL);
807  assert(hashdata->vars != NULL);
808  assert(hashdata->nvars == 2);
809  assert(hashdata->cons == NULL);
810  assert(ndelconss != NULL);
811  assert(naddconss != NULL);
812 
813  assert(presoldata->usefullogicor != NULL);
814  logicor = presoldata->usefullogicor[pos];
815  assert(logicor != NULL);
816 
817  if( !SCIPconsIsActive(logicor) )
818  return SCIP_OKAY;
819 
820  assert(!SCIPconsIsModifiable(logicor));
821 
822  nlogicorvars = SCIPgetNVarsLogicor(scip, logicor);
823  assert(nlogicorvars >= 3 && nlogicorvars <= presoldata->maxnvarslogicor);
824 
825  logicorvars = SCIPgetVarsLogicor(scip, logicor);
826  assert(logicorvars != NULL);
827 
828  nposresultants = 0;
829 
830  /* get active logicor variables and determine all possible resultants */
831  for( d = nlogicorvars - 1; d >= 0; --d )
832  {
833  /* do not work with fixed variables */
834  if( SCIPvarGetLbLocal(logicorvars[d]) > 0.5 || SCIPvarGetUbLocal(logicorvars[d]) < 0.5 )
835  return SCIP_OKAY;
836 
837  activevars[d] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, logicorvars[d]);
838 
839  if( activevars[d] == NULL )
840  {
841  SCIP_CALL( SCIPgetBinvarRepresentative(scip, logicorvars[d], &(activevars[d]), &negated) );
842  SCIP_CALL( SCIPhashmapInsert(varmap, logicorvars[d], activevars[d]) );
843  }
844 
845  /* determine possible resultants a check if the other variables can appear in a set-packing constraint */
846  if( SCIPvarIsNegated(activevars[d]) )
847  {
848  assert(SCIPvarIsActive(SCIPvarGetNegatedVar(activevars[d])));
849 
850  if( SCIPvarGetNLocksDown(SCIPvarGetNegatedVar(activevars[d])) >= nlogicorvars - 1 )
851  {
852  posresultants[nposresultants] = activevars[d];
853  ++nposresultants;
854  }
855  else if( SCIPvarGetNLocksDown(SCIPvarGetNegatedVar(activevars[d])) == 0 )
856  return SCIP_OKAY;
857  }
858  else
859  {
860  assert(SCIPvarIsActive(activevars[d]));
861 
862  if( SCIPvarGetNLocksUp(activevars[d]) >= nlogicorvars - 1 )
863  {
864  posresultants[nposresultants] = activevars[d];
865  ++nposresultants;
866  }
867  else if( SCIPvarGetNLocksUp(activevars[d]) == 0 )
868  return SCIP_OKAY;
869  }
870  }
871 
872  if( nposresultants == 0 )
873  return SCIP_OKAY;
874 
875  /* sort variables after indices */
876  SCIPsortPtr((void**)activevars, SCIPvarComp, nlogicorvars);
877 
878  /* check that we have really different variables, if not remove the constraint from the hashmap and the data
879  * storage
880  */
881  for( d = nlogicorvars - 1; d > 0; --d )
882  {
883  if( SCIPvarGetIndex(activevars[d]) == SCIPvarGetIndex(activevars[d - 1]) )
884  {
885  assert(presoldata->usefullogicor[pos] == logicor);
886 
887  SCIP_CALL( SCIPhashtableRemove(presoldata->logicorhashtable, (void*) logicor) );
888  SCIP_CALL( SCIPreleaseCons(scip, &logicor) );
889 
890  presoldata->usefullogicor[pos] = presoldata->usefullogicor[presoldata->nusefullogicor - 1];
891  --(presoldata->nusefullogicor);
892 
893  return SCIP_OKAY;
894  }
895  }
896 
897  ngateconss = 0;
898 
899  for( d = nposresultants - 1; d >= 0; --d )
900  {
901  ngateconss = 0;
902 
903  for( v = nlogicorvars - 1; v >= 0; --v )
904  {
905  if( activevars[v] == posresultants[d] )
906  continue;
907 
908  /* variables need to be sorted */
909  if( SCIPvarCompare(posresultants[d], activevars[v]) > 0 )
910  {
911  hashdata->vars[0] = activevars[v];
912  hashdata->vars[1] = posresultants[d];
913  }
914  else
915  {
916  hashdata->vars[0] = posresultants[d];
917  hashdata->vars[1] = activevars[v];
918  }
919 
920  hashmaphashdata = (HASHDATA*) SCIPhashtableRetrieve(presoldata->hashdatatable, (void*) hashdata);
921 
922  if( hashmaphashdata != NULL && SCIPconsIsActive(hashmaphashdata->cons) )
923  {
924  gateconss[ngateconss] = hashmaphashdata->cons;
925  ++ngateconss;
926  }
927  else
928  break;
929  }
930  if( ngateconss == nlogicorvars - 1 )
931  break;
932  }
933 
934  /* @todo, check for clique of all variables except the resultant */
935  /* check if we have a set-partitioning 'gate' */
936  if( ngateconss == nlogicorvars - 1 && nlogicorvars == 3 )
937  {
938  assert(d >= 0 && d < nposresultants);
939  assert(ngateconss >= 2);
940 
941  if( activevars[0] == posresultants[d] )
942  {
943  hashdata->vars[0] = activevars[1];
944  hashdata->vars[1] = activevars[2];
945  }
946  else if( activevars[1] == posresultants[d] )
947  {
948  hashdata->vars[0] = activevars[0];
949  hashdata->vars[1] = activevars[2];
950  }
951  else
952  {
953  assert(activevars[2] == posresultants[d]);
954  hashdata->vars[0] = activevars[0];
955  hashdata->vars[1] = activevars[1];
956  }
957 
958  hashmaphashdata = (HASHDATA*) SCIPhashtableRetrieve(presoldata->hashdatatable, (void*) hashdata);
959  assert(hashmaphashdata == NULL || hashmaphashdata->cons != NULL);
960 
961  if( hashmaphashdata != NULL && SCIPconsIsActive(hashmaphashdata->cons) )
962  {
963  gateconss[ngateconss] = hashmaphashdata->cons;
964  ++ngateconss;
965  }
966  }
967 
968  /* did we find enough (>= number of variables in logicor - 1) set-packing constraints for an upgrade to either
969  * an and-constraint or even a set-partitioning constraint
970  */
971  if( ngateconss == nlogicorvars || (ngateconss >= nlogicorvars - 1 && !presoldata->onlysetpart))
972  {
973  SCIP_CONS* newcons;
974  char name[SCIP_MAXSTRLEN];
975  SCIP_Bool initial;
976  SCIP_Bool separate;
977  SCIP_Bool enforce;
978  SCIP_Bool check;
979  SCIP_Bool propagate;
980  SCIP_Bool local;
981  SCIP_Bool modifiable;
982  SCIP_Bool dynamic;
983  SCIP_Bool removable;
984  SCIP_Bool stickingatnode;
985  int i;
986 
987  assert(ngateconss <= nlogicorvars);
988  assert(d >= 0 && d < nposresultants);
989 
990  initial = SCIPconsIsInitial(logicor);
991  separate = SCIPconsIsSeparated(logicor);
992  enforce = SCIPconsIsEnforced(logicor);
993  check = SCIPconsIsChecked(logicor);
994  propagate = SCIPconsIsPropagated(logicor);
995  local = SCIPconsIsLocal(logicor);
996  modifiable = SCIPconsIsModifiable(logicor);
997  dynamic = SCIPconsIsDynamic(logicor);
998  removable = SCIPconsIsRemovable(logicor);
999  stickingatnode = SCIPconsIsStickingAtNode(logicor);
1000 
1001 #ifdef SCIP_DEBUG
1002  if( ngateconss == nlogicorvars )
1003  {
1004  SCIPdebugMsg(scip, "Following constraints form a set-partitioning constraint.\n");
1005  }
1006  else
1007  {
1008  SCIPdebugMsg(scip, "Following constraints form an and-constraint.\n");
1009  }
1010 #endif
1011 
1012  for( v = ngateconss - 1; v >= 0; --v )
1013  {
1014  assert(gateconss[v] != NULL);
1015 
1016  initial |= SCIPconsIsInitial(gateconss[v]);
1017  separate |= SCIPconsIsSeparated(gateconss[v]);
1018  enforce |= SCIPconsIsEnforced(gateconss[v]);
1019  check |= SCIPconsIsChecked(gateconss[v]);
1020  propagate |= SCIPconsIsPropagated(gateconss[v]);
1021  local &= SCIPconsIsLocal(gateconss[v]);
1022  modifiable &= SCIPconsIsModifiable(gateconss[v]);
1023  dynamic &= SCIPconsIsDynamic(gateconss[v]);
1024  removable &= SCIPconsIsRemovable(gateconss[v]);
1025  stickingatnode &= SCIPconsIsStickingAtNode(gateconss[v]);
1026 
1027  SCIPdebugPrintCons(scip, gateconss[v], NULL);
1028 
1029  SCIP_CALL( SCIPdelCons(scip, gateconss[v]) );
1030  ++(*ndelconss);
1031  }
1032 
1033  SCIPdebugPrintCons(scip, logicor, NULL);
1034 
1035  if( ngateconss == nlogicorvars - 1 )
1036  {
1037  SCIP_VAR** consvars;
1038 
1039  assert(!presoldata->onlysetpart);
1040 
1041  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, ngateconss) );
1042  i = 0;
1043 
1044  /* determine and operands */
1045  for( v = nlogicorvars - 1; v >= 0; --v )
1046  {
1047  if( activevars[v] == posresultants[d] )
1048  continue;
1049 
1050  SCIP_CALL( SCIPgetNegatedVar(scip, activevars[v], &consvars[i]) );
1051  ++i;
1052  }
1053  assert(i == ngateconss);
1054 
1055  /* create and add "and" constraint for the extracted gate */
1056  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "andgate_%d", presoldata->ngates);
1057  SCIP_CALL( SCIPcreateConsAnd(scip, &newcons, name, posresultants[d], ngateconss, consvars,
1058  initial, separate, enforce, check, propagate,
1059  local, modifiable, dynamic, removable, stickingatnode) );
1060 
1061  SCIP_CALL( SCIPaddCons(scip, newcons) );
1062  SCIPdebugMsg(scip, "-------------->\n");
1063  SCIPdebugPrintCons(scip, newcons, NULL);
1064 
1065  ++(*naddconss);
1066  ++(presoldata->ngates);
1067 
1068  SCIP_CALL( SCIPdelCons(scip, logicor) );
1069  ++(*ndelconss);
1070 
1071  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
1072 
1073  SCIPfreeBufferArray(scip, &consvars);
1074  }
1075  else
1076  {
1077  assert(ngateconss == nlogicorvars);
1078 
1079  /* create and add set-partitioning constraint */
1080  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "setpart_%d", presoldata->ngates);
1081  SCIP_CALL( SCIPcreateConsSetpart(scip, &newcons, name, nlogicorvars, activevars,
1082  initial, separate, enforce, check, propagate,
1083  local, modifiable, dynamic, removable, stickingatnode) );
1084 
1085  SCIP_CALL( SCIPaddCons(scip, newcons) );
1086  SCIPdebugMsg(scip, "-------------->\n");
1087  SCIPdebugPrintCons(scip, newcons, NULL);
1088 
1089  ++(*naddconss);
1090  ++(presoldata->ngates);
1091 
1092  SCIP_CALL( SCIPdelCons(scip, logicor) );
1093  ++(*ndelconss);
1094 
1095  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
1096  }
1097  }
1098 
1099  return SCIP_OKAY;
1100 }
1101 
1102 
1103 /*
1104  * Callback methods of presolver
1105  */
1106 
1107 
1108 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
1109 static
1110 SCIP_DECL_PRESOLCOPY(presolCopyGateextraction)
1111 { /*lint --e{715}*/
1112  assert(scip != NULL);
1113  assert(presol != NULL);
1114  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
1115 
1116  /* call inclusion method of presolver */
1118 
1119  return SCIP_OKAY;
1120 }
1121 
1122 
1123 /** destructor of presolver to free user data (called when SCIP is exiting) */
1124 static
1125 SCIP_DECL_PRESOLFREE(presolFreeGateextraction)
1126 { /*lint --e{715}*/
1127  SCIP_PRESOLDATA* presoldata;
1128 
1129  /* free presolver data */
1130  presoldata = SCIPpresolGetData(presol);
1131  assert(presoldata != NULL);
1132 
1133  if( presoldata->hashdatatable != NULL )
1134  {
1135  assert(presoldata->setppchashtable != NULL);
1136  assert(presoldata->logicorhashtable != NULL);
1137 
1138  SCIPhashtableFree(&(presoldata->logicorhashtable));
1139  SCIPhashtableFree(&(presoldata->setppchashtable));
1140  SCIPhashtableFree(&(presoldata->hashdatatable));
1141  }
1142 
1143  SCIPfreeBlockMemory(scip, &presoldata);
1144  SCIPpresolSetData(presol, NULL);
1145 
1146  return SCIP_OKAY;
1147 }
1148 
1149 
1150 /** deinitialization method of presolver (called before transformed problem is freed) */
1151 static
1152 SCIP_DECL_PRESOLEXIT(presolExitGateextraction)
1153 { /*lint --e{715}*/
1154  SCIP_PRESOLDATA* presoldata;
1155  int c;
1157  /* free presolver data */
1158  presoldata = SCIPpresolGetData(presol);
1159  assert(presoldata != NULL);
1160 
1161  /* release old constraints */
1162  for( c = presoldata->nusefullogicor - 1; c >= 0; --c )
1163  {
1164  SCIP_CALL( SCIPreleaseCons(scip, &(presoldata->usefullogicor[c])) );
1165  }
1166 
1167  if( presoldata->usefullogicorexist )
1168  {
1169  SCIPfreeBlockMemoryArray(scip, &presoldata->usefullogicor, presoldata->susefullogicor);
1170  }
1171 
1172  if( presoldata->usefulsetppcexist )
1173  {
1174  assert(presoldata->setppchashdatas != NULL || presoldata->nsetppchashdatas == 0);
1175  for( c = presoldata->nsetppchashdatas - 1; c >= 0; --c )
1176  {
1177  assert(presoldata->setppchashdatas[c].cons != NULL);
1178  assert(presoldata->setppchashdatas[c].vars != NULL);
1179 
1180  /* remove constraint from setppc-hashtable */
1181  assert(SCIPhashtableExists(presoldata->setppchashtable, (void*) presoldata->setppchashdatas[c].cons));
1182  SCIP_CALL( SCIPhashtableRemove(presoldata->setppchashtable, (void*) presoldata->setppchashdatas[c].cons) );
1183 
1184 
1185  /* remove hashdata entry from hashtable */
1186  SCIP_CALL( SCIPhashtableRemove(presoldata->hashdatatable, (void*) &presoldata->setppchashdatas[c]) );
1187 
1188  /* release old constraints */
1189  SCIP_CALL( SCIPreleaseCons(scip, &(presoldata->setppchashdatas[c].cons)) );
1190 
1191  /* release variables */
1192  SCIP_CALL( SCIPreleaseVar(scip, &(presoldata->setppchashdatas[c].vars[0])) );
1193  SCIP_CALL( SCIPreleaseVar(scip, &(presoldata->setppchashdatas[c].vars[1])) );
1194 
1195  /* free memory for variables */
1196  SCIPfreeBlockMemoryArray(scip, &(presoldata->setppchashdatas[c].vars), 2);
1197  }
1198 
1199  SCIPfreeBlockMemoryArray(scip, &(presoldata->setppchashdatas), presoldata->ssetppchashdatas);
1200  }
1201 
1202  if( presoldata->hashdatatable != NULL )
1203  {
1204  assert(presoldata->setppchashtable != NULL);
1205  assert(presoldata->logicorhashtable != NULL);
1206 
1207  /* clear old hashtable entries */
1208  SCIPhashtableRemoveAll(presoldata->hashdatatable);
1209  SCIPhashtableRemoveAll(presoldata->setppchashtable);
1210  SCIPhashtableRemoveAll(presoldata->logicorhashtable);
1211  }
1212 
1213  presoldata->nusefullogicor = 0;
1214  presoldata->susefullogicor = 0;
1215  presoldata->nsetppchashdatas = 0;
1216  presoldata->ssetppchashdatas = 0;
1217  presoldata->firstchangedlogicor = -1;
1218  presoldata->ngates = 0;
1219  presoldata->usefullogicorexist = FALSE;
1220  presoldata->usefulsetppcexist = FALSE;
1221  presoldata->newsetppchashdatas = FALSE;
1222  presoldata->initialized = FALSE;
1223 
1224  return SCIP_OKAY;
1225 }
1226 
1227 
1228 /** presolving initialization method of presolver (called when presolving is about to begin) */
1229 static
1230 SCIP_DECL_PRESOLINITPRE(presolInitpreGateextraction)
1231 { /*lint --e{715}*/
1232  return SCIP_OKAY;
1233 }
1235 
1236 /** presolving deinitialization method of presolver (called after presolving has been finished) */
1237 static
1238 SCIP_DECL_PRESOLEXITPRE(presolExitpreGateextraction)
1239 { /*lint --e{715}*/
1240  return SCIP_OKAY;
1241 }
1243 
1244 /** execution method of presolver */
1245 static
1246 SCIP_DECL_PRESOLEXEC(presolExecGateextraction)
1247 { /*lint --e{715}*/
1248  SCIP_PRESOLDATA* presoldata;
1249  SCIP_HASHMAP* varmap;
1250  HASHDATA hashdata;
1251  SCIP_VAR* tmpvars[2];
1252  SCIP_CONSHDLR* conshdlrsetppc;
1253  SCIP_CONSHDLR* conshdlrlogicor;
1254  SCIP_CONSHDLR* conshdlrand;
1255  SCIP_CONS** setppcconss;
1256  SCIP_CONS** logicorconss;
1257  int nsetppcconss;
1258  int nlogicorconss;
1259  int size;
1260  int c;
1261  SCIP_Bool paramvalue;
1262 
1263  assert(scip != NULL);
1264  assert(presol != NULL);
1265  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
1266  assert(result != NULL);
1267 
1268  *result = SCIP_DIDNOTRUN;
1269 
1270 #if 0 /* need to include cons_knapsack on top of this file */
1271  /* check for possible knapsacks that form with a logicor a weak relaxation of an and-constraint
1272  *
1273  * the weak relaxation of an and-constraint looks like:
1274  * - row1: resvar - v1 - ... - vn >= 1-n
1275  * - row2: n*resvar - v1 - ... - vn <= 0.0
1276  *
1277  * which look like the following contraints
1278  * - logicor: resvar + ~v1 + ... + ~vn >= 1
1279  * - knapsack: n*resvar + ~v1 + ... + ~vn <= n
1280  */
1281  {
1282  SCIP_CONSHDLR* conshdlrknapsack;
1283  SCIP_CONS** knapsackconss;
1284  int nknapsackconss;
1285  SCIP_VAR** vars;
1286  SCIP_Longint* vals;
1287  SCIP_Longint capacity;
1288  int nvars;
1289 
1290  conshdlrknapsack = SCIPfindConshdlr(scip, "knapsack");
1291 
1292  /* get number of active constraints */
1293  knapsackconss = SCIPconshdlrGetConss(conshdlrknapsack);
1294  nknapsackconss = SCIPconshdlrGetNActiveConss(conshdlrknapsack);
1295  assert(nknapsackconss >= 0);
1296  assert(knapsackconss != NULL || nknapsackconss == 0);
1297 
1298  for( c = nknapsackconss - 1; c >= 0; --c )
1299  {
1300  /* not implemented in master branch, but the constraint may be already sorted */
1301  /*SCIPsortKnapsack(scip, knapsackconss[c]);*/
1302 
1303  nvars = SCIPgetNVarsKnapsack(scip, knapsackconss[c]);
1304  vals = SCIPgetWeightsKnapsack(scip, knapsackconss[c]);
1305  vars = SCIPgetVarsKnapsack(scip, knapsackconss[c]);
1306  capacity = SCIPgetCapacityKnapsack(scip, knapsackconss[c]);
1307 
1308  if( nvars > 1 && capacity == nvars - 1 && vals[0] == capacity && vals[1] == 1 )
1309  {
1310  printf("possible knapsack for gate extraction\n");
1311  }
1312  }
1313  }
1314 #endif
1315 
1316  /* get necessary constraint handlers */
1317  conshdlrsetppc = SCIPfindConshdlr(scip, "setppc");
1318  conshdlrlogicor = SCIPfindConshdlr(scip, "logicor");
1319 
1320  if( conshdlrsetppc == NULL || conshdlrlogicor == NULL )
1321  return SCIP_OKAY;
1322 
1323  /* get number of active constraints */
1324  nsetppcconss = SCIPconshdlrGetNActiveConss(conshdlrsetppc);
1325  assert(nsetppcconss >= 0);
1326  nlogicorconss = SCIPconshdlrGetNActiveConss(conshdlrlogicor);
1327  assert(nlogicorconss >= 0);
1328 
1329  if( nsetppcconss == 0 || nlogicorconss == 0 )
1330  return SCIP_OKAY;
1331 
1332  /* get presolver data */
1333  presoldata = SCIPpresolGetData(presol);
1334  assert(presoldata != NULL);
1335 
1336  conshdlrand = SCIPfindConshdlr(scip, "and");
1337 
1338  /* need and-constraint handler to extract and-gates */
1339  if( conshdlrand == NULL )
1340  {
1341  /* nothing to do when we cannot extract anything */
1342  if( !presoldata->searchequations )
1343  return SCIP_OKAY;
1344  else
1345  {
1346  /* make sure that we correct the parameter for only extrating set-partitioning constraints */
1347  if( SCIPisParamFixed(scip, "presolving/" PRESOL_NAME "/onlysetpart") )
1348  {
1349  SCIPwarningMessage(scip, "unfixing parameter <presolving/" PRESOL_NAME "/onlysetpart> in gate extration presolver\n");
1350  SCIP_CALL( SCIPunfixParam(scip, "presolving/" PRESOL_NAME "/onlysetpart") );
1351  }
1352  SCIP_CALL( SCIPsetBoolParam(scip, "presolving/" PRESOL_NAME "/onlysetpart", TRUE) );
1353  assert(presoldata->onlysetpart);
1354  }
1355  }
1356 
1357  paramvalue = FALSE;
1358  if( conshdlrand != NULL && SCIPgetBoolParam(scip, "constraints/and/linearize", &paramvalue) == SCIP_OKAY )
1359  {
1360  if( paramvalue )
1361  {
1362  SCIPwarningMessage(scip, "Gate-presolving is the 'counterpart' of linearizing all and-constraints, so enabling both presolving steps at ones does not make sense.\n");
1363  }
1364  }
1365  *result = SCIP_DIDNOTFIND;
1366 
1367  /* get active constraints */
1368  SCIP_CALL( SCIPduplicateBufferArray(scip, &setppcconss, SCIPconshdlrGetConss(conshdlrsetppc), nsetppcconss) );
1369 
1370  assert(setppcconss != NULL);
1371  logicorconss = SCIPconshdlrGetConss(conshdlrlogicor);
1372  assert(logicorconss != NULL);
1373 
1374  /* first we need to initialized the hashtables if not yet done */
1375  if( presoldata->hashdatatable == NULL )
1376  {
1377  SCIP_CALL( presoldataInitHashtables(scip, presoldata) );
1378  }
1379  assert(presoldata->hashdatatable != NULL);
1380  assert(presoldata->setppchashtable != NULL);
1381  assert(presoldata->logicorhashtable != NULL);
1382 
1383  presoldata->newsetppchashdatas = FALSE;
1384 
1385  if( !presoldata->initialized )
1386  {
1387  assert(presoldata->usefullogicor == NULL);
1388 
1389  /* create useful set-packing information by adding new set-packing constraints with two variables */
1390  SCIP_CALL( createPresoldata(scip, presoldata, setppcconss, nsetppcconss, logicorconss, nlogicorconss) );
1391  }
1392  else
1393  {
1394  /* refresh useful set-packing information, delete redundant constraints and add new constraints */
1395  SCIP_CALL( correctPresoldata(scip, presoldata, setppcconss, nsetppcconss, logicorconss, nlogicorconss) );
1396  }
1397  assert(presoldata->initialized);
1398 
1399  if( presoldata->nusefullogicor == 0 )
1400  goto TERMINATE;
1401 
1402  /* move the biggate extraction to front or back by sort the logicors after number of variables */
1403 
1404  if( presoldata->sorting != 0 )
1405  {
1406  int* lengths;
1407 
1408  SCIP_CALL( SCIPallocBufferArray(scip, &lengths, presoldata->nusefullogicor) );
1409 
1410  for( c = presoldata->nusefullogicor - 1; c >= 0; --c )
1411  {
1412  lengths[c] = SCIPgetNVarsLogicor(scip, presoldata->usefullogicor[c]);
1413  }
1414 
1415  if( presoldata->sorting == -1 )
1416  SCIPsortDownIntPtr(lengths, (void**)presoldata->usefullogicor, presoldata->nusefullogicor);
1417  else
1418  SCIPsortIntPtr(lengths, (void**)presoldata->usefullogicor, presoldata->nusefullogicor);
1419 
1420  SCIPfreeBufferArray(scip, &lengths);
1421  }
1422 
1423  /* maximal number of binary variables */
1424  size = SCIPgetNBinVars(scip) + SCIPgetNImplVars(scip);
1425 
1426  /* create the variable mapping hash map */
1427  SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(scip), size) );
1428 
1429  /* search for set-partitioning constraints arising from a logicor and a set-packing constraints with equal variables */
1430  if( presoldata->searchequations && !SCIPisStopped(scip) )
1431  {
1432  SCIP_HASHTABLE* setppchashdatatable;
1433  HASHDATA** setppchashdatas;
1434  HASHDATA* setppchashdatastore;
1435  HASHDATA* hashmaphashdata;
1436  SCIP_CONS* logicor;
1437  SCIP_CONS* setppc;
1438  SCIP_VAR** logicorvars;
1439  SCIP_VAR** setppcvars;
1440  SCIP_VAR** activevarslogicor;
1441  SCIP_VAR** activevarssetppc;
1442  SCIP_Bool negated;
1443  int nsetppchashdatas;
1444  int nlogicorvars;
1445  int nsetppcvars;
1446  int d;
1447  int v;
1448 
1449  assert(nsetppcconss > 0);
1450 
1451  /* create local hashtable */
1452  SCIP_CALL( SCIPhashtableCreate(&setppchashdatatable, SCIPblkmem(scip), nsetppcconss, SCIPhashGetKeyStandard, setppcHashdataKeyEqCons, setppcHashdataKeyValCons, (void*) scip) );
1453 
1454  /* maximal number of binary variables */
1455  size = presoldata->maxnvarslogicor;
1456  assert(size >= 3);
1457 
1458  /* get temporary memory */
1459  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &setppchashdatastore, nsetppcconss) );
1460  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &setppchashdatas, nsetppcconss) );
1461  SCIP_CALL( SCIPallocBufferArray(scip, &activevarssetppc, size) );
1462  SCIP_CALL( SCIPallocBufferArray(scip, &activevarslogicor, size) );
1463 
1464  hashdata.cons = NULL;
1465 
1466  nsetppchashdatas = 0;
1467 
1468  /* collect all set-packing/-partitioning constraints and corresponding data to be able to search faster */
1469  for( d = nsetppcconss - 1; d >= 0; --d )
1470  {
1471  setppc = setppcconss[d];
1472  assert(setppc != NULL);
1473 
1474  if( SCIPconsIsDeleted(setppc) )
1475  continue;
1476 
1477  /* @todo if of interest could also be implemented for set-covering constraints */
1478 #if 1
1479  if( SCIPgetTypeSetppc(scip, setppc) == SCIP_SETPPCTYPE_COVERING )
1480  continue;
1481 #endif
1482 
1483  nsetppcvars = SCIPgetNVarsSetppc(scip, setppc);
1484 
1485  if( nsetppcvars < 2 )
1486  continue;
1487 
1488  if( SCIPconsIsModifiable(setppc) )
1489  continue;
1490 
1491  /* to big setppc constraints are picked out */
1492  if( nsetppcvars > size )
1493  continue;
1494 
1495  setppcvars = SCIPgetVarsSetppc(scip, setppc);
1496  assert(setppcvars != NULL);
1497 
1498  /* get active setppc variables */
1499  for( v = nsetppcvars - 1; v >= 0; --v )
1500  {
1501  /* do not work with fixed variables */
1502  if( SCIPvarGetLbLocal(setppcvars[v]) > 0.5 || SCIPvarGetUbLocal(setppcvars[v]) < 0.5 )
1503  break;
1504 
1505  activevarssetppc[v] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, setppcvars[v]);
1506 
1507  if( activevarssetppc[v] == NULL )
1508  {
1509  SCIP_CALL( SCIPgetBinvarRepresentative(scip, setppcvars[v], &(activevarssetppc[v]), &negated) );
1510  SCIP_CALL( SCIPhashmapInsert(varmap, setppcvars[v], activevarssetppc[v]) );
1511  }
1512  }
1513 
1514  /* if we found a fixed variable we want disregard this constraint */
1515  if( v >= 0 )
1516  continue;
1517 
1518  /* variables need to be sorted after indices to be able to do a fast comparison */
1519  SCIPsortPtr((void**)activevarssetppc, SCIPvarComp, nsetppcvars);
1520 
1521  setppchashdatas[nsetppchashdatas] = &(setppchashdatastore[nsetppchashdatas]);
1522 
1523  /* memorize set-packing data */
1524  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(setppchashdatas[nsetppchashdatas]->vars), activevarssetppc, nsetppcvars) );
1525 
1526  setppchashdatas[nsetppchashdatas]->nvars = nsetppcvars;
1527  setppchashdatas[nsetppchashdatas]->cons = setppc;
1528  /* need to capture this constraint, because it might get deleted during the process */
1529  SCIP_CALL( SCIPcaptureCons(scip, setppc) );
1530 
1531  /* add entry to local hashtable */
1532  SCIP_CALL( SCIPhashtableInsert(setppchashdatatable, (void*) setppchashdatas[nsetppchashdatas]) );
1533  ++nsetppchashdatas;
1534  }
1535 
1536  /* check all (new) logicors against all collected set-packing/-partitioning constraints */
1537  for( c = nlogicorconss - 1; c >= 0 && !SCIPisStopped(scip); --c )
1538  {
1539  logicor = logicorconss[c];
1540  assert(logicor != NULL);
1541 
1542  if( SCIPconsIsDeleted(logicor) )
1543  continue;
1544 
1545  nlogicorvars = SCIPgetNVarsLogicor(scip, logicor);
1546 
1547  if( nlogicorvars < 2 )
1548  continue;
1549 
1550  if( SCIPconsIsModifiable(logicor) )
1551  continue;
1552 
1553  assert(nlogicorvars <= size);
1554 
1555  logicorvars = SCIPgetVarsLogicor(scip, logicor);
1556  assert(logicorvars != NULL);
1557 
1558  /* get active logicor variables */
1559  for( v = nlogicorvars - 1; v >= 0; --v )
1560  {
1561  /* do not work with fixed variables */
1562  if( SCIPvarGetLbLocal(logicorvars[v]) > 0.5 || SCIPvarGetUbLocal(logicorvars[v]) < 0.5 )
1563  break;
1564 
1565  activevarslogicor[v] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, logicorvars[v]);
1566 
1567  /* if image does not exist, then there is no corresponding set-packing constraint */
1568  if( activevarslogicor[v] == NULL )
1569  break;
1570  }
1571 
1572  if( v == -1 )
1573  {
1574  /* need sorting to be able to find the correct hashdata element */
1575  SCIPsortPtr((void**)activevarslogicor, SCIPvarComp, nlogicorvars);
1576 
1577  hashdata.nvars = nlogicorvars;
1578  hashdata.vars = activevarslogicor;
1579 
1580  hashmaphashdata = (HASHDATA*) SCIPhashtableRetrieve(setppchashdatatable, (void*) &hashdata);
1581  assert(hashmaphashdata == NULL || hashmaphashdata->cons != NULL);
1582 
1583  if( hashmaphashdata != NULL && !SCIPconsIsDeleted(hashmaphashdata->cons) )
1584  {
1585  SCIP_Bool initial;
1586  SCIP_Bool separate;
1587  SCIP_Bool enforce;
1588  SCIP_Bool check;
1589  SCIP_Bool propagate;
1590  SCIP_Bool local;
1591  SCIP_Bool modifiable;
1592  SCIP_Bool dynamic;
1593  SCIP_Bool removable;
1594  SCIP_Bool stickingatnode;
1595 
1596  setppc = hashmaphashdata->cons;
1597  assert(SCIPconsGetHdlr(setppc) == SCIPfindConshdlr(scip, "setppc"));
1598 
1599  initial = SCIPconsIsInitial(logicor) || SCIPconsIsInitial(setppc);
1600  separate = SCIPconsIsSeparated(logicor) || SCIPconsIsSeparated(setppc);
1601  enforce = SCIPconsIsEnforced(logicor) || SCIPconsIsEnforced(setppc);
1602  check = SCIPconsIsChecked(logicor) || SCIPconsIsChecked(setppc);
1603  propagate = SCIPconsIsPropagated(logicor) || SCIPconsIsPropagated(setppc);
1604  local = SCIPconsIsLocal(logicor) && SCIPconsIsLocal(setppc);
1605  modifiable = SCIPconsIsModifiable(logicor) && SCIPconsIsModifiable(setppc);
1606  dynamic = SCIPconsIsDynamic(logicor) && SCIPconsIsDynamic(setppc);
1607  removable = SCIPconsIsRemovable(logicor) && SCIPconsIsRemovable(setppc);
1608  stickingatnode = SCIPconsIsStickingAtNode(logicor) && SCIPconsIsStickingAtNode(setppc);
1609 
1610  /* check if logicor is redundant against a set-partitioning constraint */
1611  if( SCIPgetTypeSetppc(scip, setppc) == SCIP_SETPPCTYPE_PARTITIONING )
1612  {
1613  SCIP_CALL( SCIPsetConsInitial(scip, setppc, initial) );
1614  SCIP_CALL( SCIPsetConsSeparated(scip, setppc, separate) );
1615  SCIP_CALL( SCIPsetConsEnforced(scip, setppc, enforce) );
1616  SCIP_CALL( SCIPsetConsChecked(scip, setppc, check) );
1617  SCIP_CALL( SCIPsetConsPropagated(scip, setppc, propagate) );
1618  SCIP_CALL( SCIPsetConsLocal(scip, setppc, local) );
1619  SCIP_CALL( SCIPsetConsModifiable(scip, setppc, modifiable) );
1620  SCIP_CALL( SCIPsetConsDynamic(scip, setppc, dynamic) );
1621  SCIP_CALL( SCIPsetConsRemovable(scip, setppc, removable) );
1622  SCIP_CALL( SCIPsetConsStickingAtNode(scip, setppc, stickingatnode) );
1623 
1624  SCIPdebugMsg(scip, "Following logicor is redundant to the set-partitioning constraint.\n");
1625  SCIPdebugPrintCons(scip, logicor, NULL);
1626  SCIPdebugPrintCons(scip, setppc, NULL);
1627  }
1628  else
1629  {
1630  SCIP_CONS* newcons;
1631  char name[SCIP_MAXSTRLEN];
1632 
1633  assert(SCIPgetTypeSetppc(scip, setppc) == SCIP_SETPPCTYPE_PACKING);
1634 
1635  SCIPdebugMsg(scip, "Following logicor and set-packing constraints form a set-partitioning constraint.\n");
1636  SCIPdebugPrintCons(scip, logicor, NULL);
1637  SCIPdebugPrintCons(scip, setppc, NULL);
1638 
1639  /* create and add set-partitioning constraint */
1640  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "setpart_%d", presoldata->ngates);
1641  SCIP_CALL( SCIPcreateConsSetpart(scip, &newcons, name, nlogicorvars, activevarslogicor,
1642  initial, separate, enforce, check, propagate,
1643  local, modifiable, dynamic, removable, stickingatnode) );
1644 
1645  SCIP_CALL( SCIPaddCons(scip, newcons) );
1646  SCIPdebugMsg(scip, "-------------->\n");
1647  SCIPdebugPrintCons(scip, newcons, NULL);
1648 
1649  ++(*naddconss);
1650  ++(presoldata->ngates);
1651 
1652  /* delete redundant set-packing constraint */
1653  SCIP_CALL( SCIPdelCons(scip, setppc) );
1654  ++(*ndelconss);
1655 
1656  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
1657  }
1658 
1659  /* delete redundant logicor constraint */
1660  SCIP_CALL( SCIPdelCons(scip, logicor) );
1661  ++(*ndelconss);
1662  }
1663  }
1664  }
1665 
1666  /* need to clear/release parts of hashdata objects */
1667  for( d = nsetppchashdatas - 1; d >= 0; --d )
1668  {
1669  /* need to release captured constraint */
1670  SCIP_CALL( SCIPreleaseCons(scip, &(setppchashdatas[d]->cons)) );
1671  /* need to free copied memory */
1672  SCIPfreeBlockMemoryArray(scip, &(setppchashdatas[d]->vars), setppchashdatas[d]->nvars);
1673  }
1674 
1675  /* delete local hashtable */
1676  SCIPhashtableFree(&setppchashdatatable);
1677 
1678  /* free all temporary memory */
1679  SCIPfreeBufferArray(scip, &activevarslogicor);
1680  SCIPfreeBufferArray(scip, &activevarssetppc);
1681  SCIPfreeBlockMemoryArray(scip, &setppchashdatas, nsetppcconss);
1682  SCIPfreeBlockMemoryArray(scip, &setppchashdatastore, nsetppcconss);
1683  }
1684 
1685  /* we do not have any useful set-packing or logicor constraint, or since last run did not get any new constraints, so abort */
1686  if( presoldata->nsetppchashdatas == 0 || (presoldata->firstchangedlogicor == presoldata->nusefullogicor && !presoldata->newsetppchashdatas) )
1687  {
1688  SCIPhashmapFree(&varmap);
1689  goto TERMINATE;
1690  }
1691 
1692  assert(presoldata->usefullogicor != NULL);
1693  assert(presoldata->nusefullogicor > 0);
1694  assert(presoldata->firstchangedlogicor >= 0);
1695  assert(presoldata->nsetppchashdatas > 0);
1696 
1697  /* search for gates */
1698  if( presoldata->nsetppchashdatas > 0 && !SCIPisStopped(scip) )
1699  {
1700  SCIP_CONS** gateconss;
1701  SCIP_VAR** activevars;
1702  SCIP_VAR** posresultants;
1703  int endloop;
1704 
1705  /* if we found new setppcs we want to check all logicors again */
1706  if( presoldata->newsetppchashdatas )
1707  endloop = 0;
1708  else
1709  endloop = MAX(presoldata->firstchangedlogicor, 0);
1710 
1711  assert(presoldata->maxnvarslogicor >= 3);
1712  SCIP_CALL( SCIPallocBufferArray(scip, &gateconss, presoldata->maxnvarslogicor) );
1713  SCIP_CALL( SCIPallocBufferArray(scip, &activevars, presoldata->maxnvarslogicor) );
1714  SCIP_CALL( SCIPallocBufferArray(scip, &posresultants, presoldata->maxnvarslogicor) );
1715 
1716  hashdata.nvars = 2;
1717  hashdata.cons = NULL;
1718  /* assign array of two variables as temporary storage to hashdata */
1719  hashdata.vars = tmpvars;
1720 
1721  /* check all (new) logicors against all set-packing constraints, to extract and-constraints with two or more
1722  * operands or set-partitioning constraints three or more variables
1723  */
1724  for( c = presoldata->nusefullogicor - 1; c >= endloop && !SCIPisStopped(scip); --c )
1725  {
1726  assert(presoldata->usefullogicor[c] != NULL);
1727 
1728  /* logicor constraint has the form: x + y + z >= 1
1729  *
1730  * find set-packing constraints: (~x + ~y >= 1 and ~x + ~z >= 1) <=> (x + y <= 1 and x + z <= 1)
1731  *
1732  * - these three constraints are aquivalent to: x = ~y * ~z (x = AND(~y,~z))
1733  *
1734  * if an additional set-packing constraint exists: y + z <= 1
1735  *
1736  * - these four constraints are aquivalent to: x + y + z = 1
1737  */
1738  SCIP_CALL( extractGates(scip, presoldata, c, varmap, gateconss, activevars, posresultants, &hashdata, ndelconss, naddconss) );
1739  }
1740 
1741  SCIPfreeBufferArray(scip, &posresultants);
1742  SCIPfreeBufferArray(scip, &activevars);
1743  SCIPfreeBufferArray(scip, &gateconss);
1744  }
1745 
1746  SCIPhashmapFree(&varmap);
1747 
1748  TERMINATE:
1749  SCIPfreeBufferArray(scip, &setppcconss);
1750 
1751  /* remove old setppchashdatas objects */
1752  SCIP_CALL( cleanupHashDatas(scip, presoldata) );
1753 
1754  return SCIP_OKAY;
1755 }
1756 
1757 
1758 /*
1759  * presolver specific interface methods
1760  */
1761 
1762 /** creates the gateextraction presolver and includes it in SCIP */
1764  SCIP* scip /**< SCIP data structure */
1765  )
1766 {
1767  SCIP_PRESOLDATA* presoldata;
1768  SCIP_PRESOL* presol;
1769 
1770  /* alloc presolve data object */
1771  SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );
1772 
1773  /* initialize gateextraction presolver data */
1774  presoldataInit(presoldata);
1775 
1776  /* include presolver */
1778  PRESOL_TIMING, presolExecGateextraction, presoldata) );
1779 
1780  SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyGateextraction) );
1781  SCIP_CALL( SCIPsetPresolFree(scip, presol, presolFreeGateextraction) );
1782  SCIP_CALL( SCIPsetPresolExit(scip, presol, presolExitGateextraction) );
1783  SCIP_CALL( SCIPsetPresolInitpre(scip, presol, presolInitpreGateextraction) );
1784  SCIP_CALL( SCIPsetPresolExitpre(scip, presol, presolExitpreGateextraction) );
1785 
1786  /* add gateextraction presolver parameters */
1788  "presolving/" PRESOL_NAME "/onlysetpart",
1789  "should we only try to extract set-partitioning constraints and no and-constraints",
1790  &presoldata->onlysetpart, TRUE, DEFAULT_ONLYSETPART, NULL, NULL) );
1791 
1792  /* add gateextraction presolver parameters */
1794  "presolving/" PRESOL_NAME "/searchequations",
1795  "should we try to extract set-partitioning constraint out of one logicor and one corresponding set-packing constraint",
1796  &presoldata->searchequations, TRUE, DEFAULT_SEARCHEQUATIONS, NULL, NULL) );
1797 
1798  /* add gateextraction presolver parameters */
1799  SCIP_CALL( SCIPaddIntParam(scip,
1800  "presolving/" PRESOL_NAME "/sorting",
1801  "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)",
1802  &presoldata->sorting, TRUE, DEFAULT_SORTING, -1, 1, NULL, NULL) );
1803 
1804  return SCIP_OKAY;
1805 }
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21909
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:6854
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip.h:21898
struct SCIP_PresolData SCIP_PRESOLDATA
Definition: type_presol.h:37
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21892
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLFREE((*presolfree)))
Definition: scip.c:6905
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8140
SCIP_RETCODE SCIPgetBinvarRepresentative(SCIP *scip, SCIP_VAR *var, SCIP_VAR **repvar, SCIP_Bool *negated)
Definition: scip.c:18733
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:2254
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:6541
SCIP_RETCODE SCIPsetPresolExit(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLEXIT((*presolexit)))
Definition: scip.c:6937
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9172
int SCIPgetNVarsLogicor(SCIP *scip, SCIP_CONS *cons)
#define SCIP_MAXSTRLEN
Definition: def.h:215
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:12481
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip.c:45601
SCIP_RETCODE SCIPsetConsPropagated(SCIP *scip, SCIP_CONS *cons, SCIP_Bool propagate)
Definition: scip.c:27521
#define DEFAULT_ONLYSETPART
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17222
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip.c:18384
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:2765
static SCIP_DECL_PRESOLFREE(presolFreeGateextraction)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:9340
#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:8160
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:21907
void SCIPsortDownIntPtr(int *intarray, void **ptrarray, int len)
Constraint handler for AND constraints, .
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip.h:21933
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2903
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:21937
Constraint handler for the set partitioning / packing / covering constraints .
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21890
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:83
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8150
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip.c:1260
#define SCIPdebugMsg
Definition: scip.h:451
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:4202
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
Definition: cons.c:7942
#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:2015
SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
Definition: var.c:16982
void SCIPsortIntPtr(int *intarray, void **ptrarray, int len)
SCIP_RETCODE SCIPsetConsSeparated(SCIP *scip, SCIP_CONS *cons, SCIP_Bool separate)
Definition: scip.c:27446
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip.h:21904
SCIP_RETCODE SCIPsetConsRemovable(SCIP *scip, SCIP_CONS *cons, SCIP_Bool removable)
Definition: scip.c:27624
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:4948
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip.c:4338
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:12410
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:4567
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:45519
SCIP_RETCODE SCIPsetConsChecked(SCIP *scip, SCIP_CONS *cons, SCIP_Bool check)
Definition: scip.c:27496
SCIP_RETCODE SCIPsetConsDynamic(SCIP *scip, SCIP_CONS *cons, SCIP_Bool dynamic)
Definition: scip.c:27599
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8100
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:8976
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2798
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip.c:4369
#define NULL
Definition: lpi_spx1.cpp:137
SCIP_RETCODE SCIPunfixParam(SCIP *scip, const char *name)
Definition: scip.c:4504
#define PRESOL_DESC
void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
#define SCIP_CALL(x)
Definition: def.h:306
#define SCIPhashTwo(a, b)
Definition: pub_misc.h:471
#define PRESOL_MAXROUNDS
void SCIPhashtableRemoveAll(SCIP_HASHTABLE *hashtable)
Definition: misc.c:2462
SCIP_RETCODE SCIPhashtableRemove(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2384
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8120
SCIP_RETCODE SCIPcaptureCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:27288
SCIP_RETCODE SCIPsetPresolInitpre(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLINITPRE((*presolinitpre)))
Definition: scip.c:6953
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:21925
#define HASHSIZE_SETPPCCONS
#define SCIP_Bool
Definition: def.h:61
SCIP_RETCODE SCIPsetConsLocal(SCIP *scip, SCIP_CONS *cons, SCIP_Bool local)
Definition: scip.c:27548
int SCIPgetNImplVars(SCIP *scip)
Definition: scip.c:11766
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9214
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:7901
#define PRESOL_NAME
int SCIPvarCompare(SCIP_VAR *var1, SCIP_VAR *var2)
Definition: var.c:11249
static SCIP_RETCODE cleanupHashDatas(SCIP *scip, SCIP_PRESOLDATA *presoldata)
SCIP_Bool SCIPconsIsDeleted(SCIP_CONS *cons)
Definition: cons.c:8010
static SCIP_DECL_PRESOLEXIT(presolExitGateextraction)
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:553
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8080
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8050
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2315
int SCIPgetNBinVars(SCIP *scip)
Definition: scip.c:11676
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:9193
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2065
#define DEFAULT_SORTING
SCIP_RETCODE SCIPsetConsStickingAtNode(SCIP *scip, SCIP_CONS *cons, SCIP_Bool stickingatnode)
Definition: scip.c:27649
int SCIPvarGetNLocksDown(SCIP_VAR *var)
Definition: var.c:3162
SCIP_RETCODE SCIPsetConsEnforced(SCIP *scip, SCIP_CONS *cons, SCIP_Bool enforce)
Definition: scip.c:27471
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip.c:27323
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip.c:6889
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16671
static SCIP_DECL_HASHKEYEQ(hashdataKeyEqCons)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:18350
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8130
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1138
gateextraction presolver
int SCIPgetNVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8070
#define DEFAULT_SEARCHEQUATIONS
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8060
SCIP_RETCODE SCIPsetConsModifiable(SCIP *scip, SCIP_CONS *cons, SCIP_Bool modifiable)
Definition: scip.c:27574
#define SCIP_Longint
Definition: def.h:120
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:16849
SCIP_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2366
SCIP_RETCODE SCIPincludePresolGateextraction(SCIP *scip)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17232
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:2846
#define PRESOL_TIMING
SCIP_Longint * SCIPgetWeightsKnapsack(SCIP *scip, SCIP_CONS *cons)
#define SCIPcombineTwoInt(a, b)
Definition: pub_misc.h:477
static SCIP_DECL_PRESOLINITPRE(presolInitpreGateextraction)
SCIP_RETCODE SCIPsetPresolExitpre(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLEXITPRE((*presolexitpre)))
Definition: scip.c:6969
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition: scip.c:18663
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:4176
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:16839
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition: var.c:16707
SCIP_RETCODE SCIPsetConsInitial(SCIP *scip, SCIP_CONS *cons, SCIP_Bool initial)
Definition: scip.c:27421