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