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