1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright (c) 2002-2023 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 	}
1830