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