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   sepa_zerohalf.c
26   	 * @ingroup DEFPLUGINS_SEPA
27   	 * @brief  {0,1/2}-cuts separator
28   	 * @author Leona Gottwald
29   	 * @author Manuel Kutschka
30   	 * @author Kati Wolter
31   	 *
32   	 * {0,1/2}-Chvátal-Gomory cuts separator. It solves the following separation problem:
33   	 * Consider an integer program
34   	 * \f[
35   	 * \min \{ c^T x : Ax \leq b, x \geq 0, x \mbox{ integer} \}
36   	 * \f]
37   	 * and a fractional solution \f$x^*\f$ of its LP relaxation.  Find a weightvector \f$u\f$ whose entries \f$u_i\f$ are either 0 or
38   	 * \f$\frac{1}{2}\f$ such that the following inequality is valid for all integral solutions and violated by \f$x^*\f$:
39   	 * \f[
40   	 * \lfloor(u^T A) x \rfloor \leq \lfloor u^T b\rfloor
41   	 * \f]
42   	 *
43   	 * References:
44   	 * - Alberto Caprara, Matteo Fischetti. {0,1/2}-Chvatal-Gomory cuts. Math. Programming, Volume 74, p221--235, 1996.
45   	 * - Arie M. C. A. Koster, Adrian Zymolka and Manuel Kutschka. \n
46   	 *   Algorithms to separate {0,1/2}-Chvatal-Gomory cuts.
47   	 *   Algorithms - ESA 2007: 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, \n
48   	 *   Proceedings. Lecture Notes in Computer Science, Volume 4698, p. 693--704, 2007.
49   	 * - Arie M. C. A. Koster, Adrian Zymolka and Manuel Kutschka. \n
50   	 *   Algorithms to separate {0,1/2}-Chvatal-Gomory cuts (Extended Version). \n
51   	 *   ZIB Report 07-10, Zuse Institute Berlin, 2007. http://www.zib.de/Publications/Reports/ZR-07-10.pdf
52   	 * - Manuel Kutschka. Algorithmen zur Separierung von {0,1/2}-Schnitten. Diplomarbeit. Technische Universitaet Berlin, 2007.
53   	 */
54   	
55   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
56   	
57   	#include "string.h"
58   	#include "scip/sepa_zerohalf.h"
59   	#include "scip/scipdefplugins.h"
60   	#include "scip/cutsel_hybrid.h"
61   	
62   	#define SEPA_NAME              "zerohalf"
63   	#define SEPA_DESC              "{0,1/2}-cuts separator"
64   	#define SEPA_PRIORITY             -6000
65   	#define SEPA_FREQ                    10
66   	#define SEPA_MAXBOUNDDIST           1.0
67   	#define SEPA_USESSUBSCIP          FALSE
68   	#define SEPA_DELAY                FALSE
69   	
70   	#define DEFAULT_MAXROUNDS             5 /**< maximal number of zerohalf separation rounds per node (-1: unlimited) */
71   	#define DEFAULT_MAXROUNDSROOT        20 /**< maximal number of zerohalf separation rounds in the root node (-1: unlimited) */
72   	#define DEFAULT_MAXSEPACUTS          20 /**< maximal number of zerohalf cuts separated per separation round */
73   	#define DEFAULT_MAXSEPACUTSROOT     100 /**< maximal number of zerohalf cuts separated per separation round in root node */
74   	#define DEFAULT_MAXCUTCANDS        2000 /**< maximal number of zerohalf cuts considered per separation round */
75   	#define DEFAULT_MAXSLACK            0.0 /**< maximal slack of rows to be used in aggregation */
76   	#define DEFAULT_MAXSLACKROOT        0.0 /**< maximal slack of rows to be used in aggregation in the root node */
77   	#define DEFAULT_GOODSCORE           1.0 /**< threshold for score of cut relative to best score to be considered good,
78   	                                         *   so that less strict filtering is applied */
79   	#define DEFAULT_BADSCORE            0.5 /**< threshold for score of cut relative to best score to be discarded */
80   	#define DEFAULT_MINVIOL             0.1 /**< minimal violation to generate zerohalfcut for */
81   	#define DEFAULT_DYNAMICCUTS        TRUE /**< should generated cuts be removed from the LP if they are no longer tight? */
82   	#define DEFAULT_MAXROWDENSITY      0.05 /**< maximal density of row to be used in aggregation */
83   	#define DEFAULT_DENSITYOFFSET       100 /**< additional number of variables allowed in row on top of density */
84   	#define DEFAULT_INITSEED         0x5EED /**< default initial seed used for random tie-breaking in cut selection */
85   	#define DEFAULT_OBJPARALWEIGHT      0.0 /**< weight of objective parallelism in cut score calculation */
86   	#define DEFAULT_EFFICACYWEIGHT      1.0 /**< weight of efficacy in cut score calculation */
87   	#define DEFAULT_DIRCUTOFFDISTWEIGHT 0.0 /**< weight of directed cutoff distance in cut score calculation */
88   	#define DEFAULT_GOODMAXPARALL       0.1 /**< maximum parallelism for good cuts */
89   	#define DEFAULT_MAXPARALL           0.1 /**< maximum parallelism for non-good cuts */
90   	
91   	/* SCIPcalcRowIntegralScalar parameters */
92   	#define MAXDNOM                  1000LL
93   	#define MAXSCALE                 1000.0
94   	
95   	/* other defines */
96   	#define MAXREDUCTIONROUNDS          100 /**< maximum number of rounds to perform reductions on the mod 2 system */
97   	#define BOUNDSWITCH                 0.5 /**< threshold for bound switching */
98   	#define MAXAGGRLEN(nvars)           ((int)(0.1*(nvars)+1000))
99   	
100  	typedef struct Mod2Col MOD2_COL;
101  	typedef struct Mod2Row MOD2_ROW;
102  	typedef struct Mod2Matrix MOD2_MATRIX;
103  	typedef struct TransIntRow TRANSINTROW;
104  	typedef struct RowIndex ROWINDEX;
105  	
106  	/** enum for different types of row indices in ROWINDEX structure */
107  	
108  	#define ROWIND_TYPE unsigned int
109  	#define ORIG_RHS    0u
110  	#define ORIG_LHS    1u
111  	#define TRANSROW    2u
112  	
113  	/* macro to get a unique index from the rowindex */
114  	#define UNIQUE_INDEX(rowind) (3*(rowind).index + (rowind).type)
115  	
116  	struct RowIndex
117  	{
118  	   unsigned int          type:2;             /**< type of row index; 0 means lp row using the right hand side,
119  	                                              *   1 means lp row using the left hand side, and 2 means a
120  	                                              *   transformed integral row */
121  	   unsigned int          index:30;           /**< lp position of original row, or index of transformed integral row */
122  	};
123  	
124  	/** structure containing a transformed integral row obtained by relaxing an lp row */
125  	struct TransIntRow
126  	{
127  	   SCIP_Real             slack;              /**< slack of row after transformation */
128  	   SCIP_Real             rhs;                /**< right hand side value of integral row after transformation */
129  	   SCIP_Real*            vals;               /**< values of row */
130  	   int*                  varinds;            /**< problem variable indices of row */
131  	   int                   size;               /**< alloc size of row */
132  	   int                   len;                /**< length of row */
133  	   int                   rank;               /**< rank of row */
134  	   SCIP_Bool             local;              /**< is row local? */
135  	};
136  	
137  	/** structure representing a row in the mod 2 system */
138  	struct Mod2Row
139  	{
140  	   ROWINDEX*             rowinds;            /**< index set of rows associated with the mod 2 row */
141  	   MOD2_COL**            nonzcols;           /**< sorted array of non-zero mod 2 columns in this mod 2 row */
142  	   SCIP_Real             slack;              /**< slack of mod 2 row */
143  	   SCIP_Real             maxsolval;          /**< maximum solution value of columns in mod 2 row */
144  	   int                   index;              /**< unique index of mod 2 row */
145  	   int                   pos;                /**< position of mod 2 row in mod 2 matrix rows array */
146  	   int                   rhs;                /**< rhs of row */
147  	   int                   nrowinds;           /**< number of elements in rowinds */
148  	   int                   rowindssize;        /**< size of rowinds array */
149  	   int                   nnonzcols;          /**< number of columns in nonzcols */
150  	   int                   nonzcolssize;       /**< size of nonzcols array */
151  	};
152  	
153  	/** structure representing a column in the mod 2 system */
154  	struct Mod2Col
155  	{
156  	   SCIP_HASHSET*         nonzrows;           /**< the set of rows that contain this column */
157  	   SCIP_Real             solval;             /**< solution value of the column */
158  	   int                   pos;                /**< position of column in matrix */
159  	   int                   index;              /**< index of SCIP column associated to this column */
160  	};
161  	
162  	/** matrix representing the modulo 2 system */
163  	struct Mod2Matrix
164  	{
165  	   MOD2_COL**            cols;               /**< columns of the matrix */
166  	   MOD2_ROW**            rows;               /**< rows of the matrix */
167  	   TRANSINTROW*          transintrows;       /**< transformed integral rows obtained from non-integral lp rows */
168  	   int                   ntransintrows;      /**< number of transformed integral rows obtained from non-integral lp rows */
169  	   int                   nzeroslackrows;     /**< number of rows with zero slack */
170  	   int                   nrows;              /**< number of rows of the matrix; number of elements in rows */
171  	   int                   ncols;              /**< number of cols of the matrix; number of elements in cols */
172  	   int                   rowssize;           /**< length of rows array */
173  	   int                   colssize;           /**< length of cols array */
174  	};
175  	
176  	/** data of separator */
177  	struct SCIP_SepaData
178  	{
179  	   SCIP_RANDNUMGEN*      randnumgen;         /**< random generator for tiebreaking */
180  	   SCIP_AGGRROW*         aggrrow;            /**< aggregation row used for generating cuts */
181  	   SCIP_ROW**            cuts;               /**< generated in the current call */
182  	   SCIP_Real             minviol;            /**< minimal violation to generate zerohalfcut for */
183  	   SCIP_Real             maxslack;           /**< maximal slack of rows to be used in aggregation */
184  	   SCIP_Real             maxslackroot;       /**< maximal slack of rows to be used in aggregation in the root node */
185  	   SCIP_Real             maxrowdensity;      /**< maximal density of row to be used in aggregation */
186  	   SCIP_Real             goodscore;          /**< threshold for score of cut relative to best score to be considered good,
187  	                                              *   so that less strict filtering is applied */
188  	   SCIP_Real             badscore;           /**< threshold for score of cut relative to best score to be discarded */
189  	   SCIP_Real             objparalweight;     /**< weight of objective parallelism in cut score calculation */
190  	   SCIP_Real             efficacyweight;     /**< weight of efficacy in cut score calculation */
191  	   SCIP_Real             dircutoffdistweight;/**< weight of directed cutoff distance in cut score calculation */
192  	   SCIP_Real             goodmaxparall;      /**< maximum parallelism for good cuts */
193  	   SCIP_Real             maxparall;          /**< maximum parallelism for non-good cuts */
194  	   SCIP_Bool             infeasible;         /**< infeasibility was detected after adding a zerohalf cut */
195  	   SCIP_Bool             dynamiccuts;        /**< should generated cuts be removed from the LP if they are no longer tight? */
196  	   int                   maxrounds;          /**< maximal number of zerohalf separation rounds per node (-1: unlimited) */
197  	   int                   maxroundsroot;      /**< maximal number of zerohalf separation rounds in the root node (-1: unlimited) */
198  	   int                   maxsepacuts;        /**< maximal number of zerohalf cuts separated per separation round */
199  	   int                   maxsepacutsroot;    /**< maximal number of zerohalf cuts separated per separation round in root node */
200  	   int                   maxcutcands;        /**< maximal number of zerohalf cuts considered per separation round */
201  	   int                   densityoffset;      /**< additional number of variables allowed in row on top of density */
202  	   int                   initseed;           /**< initial seed used for random tie-breaking in cut selection */
203  	   int                   cutssize;           /**< size of cuts and cutscores arrays */
204  	   int                   ncuts;              /**< number of cuts generated in the current call */
205  	   int                   nreductions;        /**< number of reductions to the mod 2 system found so far */
206  	};
207  	
208  	
209  	#define COLINFO_GET_MOD2COL(x) ((MOD2_COL*)  (((uintptr_t)(x)) & ~((uintptr_t)1)))
210  	#define COLINFO_GET_RHSOFFSET(x) ((int)  (((uintptr_t)(x)) & ((uintptr_t)1)))
211  	#define COLINFO_CREATE(mod2col, rhsoffset)  ((void*) (((uintptr_t)(mod2col)) | ((uintptr_t)(rhsoffset))))
212  	
213  	
214  	#ifndef NDEBUG
215  	static
216  	void checkRow(MOD2_ROW* row)
217  	{
218  	   int i;
219  	   SCIP_Real maxsolval = 0.0;
220  	
221  	   for( i = 0; i < row->nnonzcols; ++i )
222  	   {
223  	      assert(row->nonzcols[i]->solval > 0.0);
224  	      maxsolval = MAX(maxsolval, row->nonzcols[i]->solval);
225  	
226  	      if( i + 1 < row->nnonzcols )
227  	         assert(row->nonzcols[i]->index < row->nonzcols[i+1]->index);
228  	   }
229  	
230  	   assert(row->maxsolval == maxsolval); /*lint !e777*/
231  	}
232  	#else
233  	#define checkRow(x)
234  	#endif
235  	
236  	/** compare to mod 2 columns by there index */
237  	static
238  	SCIP_DECL_SORTPTRCOMP(compareColIndex)
239  	{
240  	   MOD2_COL* col1;
241  	   MOD2_COL* col2;
242  	
243  	   col1 = (MOD2_COL*) elem1;
244  	   col2 = (MOD2_COL*) elem2;
245  	
246  	   if( col1->index < col2->index )
247  	      return -1;
248  	   if( col2->index < col1->index )
249  	      return 1;
250  	
251  	   return 0;
252  	}
253  	
254  	/** comparison function for slack of mod 2 rows */
255  	static
256  	SCIP_DECL_SORTPTRCOMP(compareRowSlack)
257  	{
258  	   MOD2_ROW* row1;
259  	   MOD2_ROW* row2;
260  	   SCIP_Bool slack1iszero;
261  	   SCIP_Bool slack2iszero;
262  	
263  	   row1 = (MOD2_ROW*) elem1;
264  	   row2 = (MOD2_ROW*) elem2;
265  	
266  	   slack1iszero = EPSZ(row1->slack, SCIP_DEFAULT_EPSILON);
267  	   slack2iszero = EPSZ(row2->slack, SCIP_DEFAULT_EPSILON);
268  	
269  	   /* zero slack comes first */
270  	   if( slack1iszero && !slack2iszero )
271  	      return -1;
272  	   if( slack2iszero && !slack1iszero )
273  	      return 1;
274  	   if( !slack1iszero && !slack2iszero )
275  	      return 0;
276  	
277  	   /* prefer rows that contain columns with large solution value */
278  	   if( row1->maxsolval > row2->maxsolval )
279  	      return -1;
280  	   if( row2->maxsolval > row1->maxsolval )
281  	      return 1;
282  	
283  	   /* rows with less non-zeros come first rows */
284  	   if( row1->nnonzcols < row2->nnonzcols )
285  	      return -1;
286  	   if( row2->nnonzcols < row1->nnonzcols )
287  	      return 1;
288  	
289  	   return 0;
290  	}
291  	
292  	/** take integral real value modulo 2 */
293  	static
294  	int mod2(
295  	   SCIP*                 scip,               /**< scip data structure */
296  	   SCIP_Real             val                 /**< value to take mod 2 */
297  	)
298  	{
299  	   assert(SCIPisFeasIntegral(scip, val));
300  	   val *= 0.5;
301  	   return (REALABS(SCIPround(scip, val) - val) > 0.1) ? 1 : 0;
302  	}
303  	
304  	/** returns the integral value for the given scaling parameters, see SCIPcalcIntegralScalar() */
305  	static
306  	void getIntegralScalar(
307  	   SCIP_Real             val,                /**< value that should be scaled to an integral value */
308  	   SCIP_Real             scalar,             /**< scalar that should be tried */
309  	   SCIP_Real             mindelta,           /**< minimal relative allowed difference of scaled coefficient s*c and integral i */
310  	   SCIP_Real             maxdelta,           /**< maximal relative allowed difference of scaled coefficient s*c and integral i */
311  	   SCIP_Real*            sval,               /**< pointer to store the scaled value */
312  	   SCIP_Real*            intval              /**< pointer to store the scaled integral value */
313  	   )
314  	{
315  	   SCIP_Real upviol;
316  	   SCIP_Real downviol;
317  	   SCIP_Real downval;
318  	   SCIP_Real upval;
319  	
320  	   assert(mindelta <= 0.0);
321  	   assert(maxdelta >= 0.0);
322  	
323  	   *sval = val * scalar;
324  	   downval = floor(*sval);
325  	   upval = ceil(*sval);
326  	
327  	   downviol = SCIPrelDiff(*sval, downval) - maxdelta;
328  	   upviol = mindelta - SCIPrelDiff(*sval, upval);
329  	
330  	   if( downviol < upviol )
331  	      *intval = downval;
332  	   else
333  	      *intval = upval;
334  	}
335  	
336  	/** Tries to transform a non-integral row into an integral row that can be used in zerohalf separation */
337  	static
338  	SCIP_RETCODE transformNonIntegralRow(
339  	   SCIP*                 scip,               /**< scip data structure */
340  	   SCIP_SOL*             sol,                /**< solution to separate, or NULL for LP solution */
341  	   SCIP_Bool             allowlocal,         /**< should local cuts be allowed */
342  	   SCIP_Real             maxslack,           /**< maximum slack allowed for transformed row */
343  	   int                   sign,               /**< +1 or -1 scale to select the side of the row */
344  	   SCIP_Bool             local,              /**< is the row only valid locally? */
345  	   int                   rank,               /**< rank of row */
346  	   int                   rowlen,             /**< length of row */
347  	   SCIP_Real*            rowvals,            /**< coefficients of columns in row */
348  	   SCIP_COL**            rowcols,            /**< columns of row */
349  	   SCIP_Real             rhs,                /**< right hand side of row */
350  	   int*                  intvarpos,          /**< clean buffer array of size SCIPgetNVars that will be clean when the function returns */
351  	   TRANSINTROW*          introw,             /**< pointer to return transformed row */
352  	   SCIP_Bool*            success             /**< pointer to return whether the transformation succeeded */
353  	   )
354  	{
355  	   int i;
356  	   int transrowlen;
357  	   SCIP_Real transrowrhs;
358  	   int* transrowvars;
359  	   SCIP_Real* transrowvals;
360  	
361  	   assert(scip != NULL);
362  	   assert(sign == +1 || sign == -1);
363  	   assert(rowvals != NULL || rowlen == 0);
364  	   assert(rowcols != NULL || rowlen == 0);
365  	   assert(intvarpos != NULL);
366  	   assert(introw != NULL);
367  	   assert(success != NULL);
368  	
369  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &transrowvars, rowlen) );
370  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &transrowvals, rowlen) );
371  	   transrowlen = 0;
372  	   transrowrhs = rhs;
373  	
374  	   /* first add all integral variables to the transformed row and remember their positions in the row */
375  	   for( i = 0; i < rowlen; ++i )
376  	   {
377  	      int probindex;
378  	
379  	      if( !SCIPcolIsIntegral(rowcols[i]) )  /*lint !e613*/
380  	         continue;
381  	
382  	      probindex = SCIPcolGetVarProbindex(rowcols[i]);
383  	      transrowvars[transrowlen] = probindex;
384  	      transrowvals[transrowlen] = sign * rowvals[i];
385  	      intvarpos[probindex] = ++transrowlen;
386  	   }
387  	
388  	   /* now loop over the non-integral columns of the row and project them out using simple or variable bounds */
389  	   *success = TRUE;
390  	
391  	   for( i = 0; i < rowlen; ++i )
392  	   {
393  	      int closestvbdind;
394  	      SCIP_Real closestbound;
395  	      SCIP_VAR* vbdvar;
396  	      SCIP_Real vbdcoef;
397  	      SCIP_Real vbdconst;
398  	      SCIP_VAR* colvar;
399  	      SCIP_Real val;
400  	      SCIP_Real closestvbd;
401  	      SCIP_Bool localbound;
402  	
403  	      if( SCIPcolIsIntegral(rowcols[i]) ) /*lint !e613*/
404  	         continue;
405  	
406  	      localbound = FALSE;
407  	
408  	      colvar = SCIPcolGetVar(rowcols[i]); /*lint !e613*/
409  	
410  	      val = sign * rowvals[i]; /*lint !e613*/
411  	
412  	      /* if the value is positive we need to use a lower bound constraint */
413  	      if( val > 0.0 )
414  	      {
415  	         /* retrieve simple variable bound */
416  	         closestbound = SCIPvarGetLbGlobal(colvar);
417  	         if( allowlocal && SCIPisSumGT(scip, SCIPvarGetLbLocal(colvar), closestbound) )
418  	         {
419  	            /* only use local bound if it is better thatn the global bound */
420  	            closestbound = SCIPvarGetLbLocal(colvar);
421  	            localbound = TRUE;
422  	         }
423  	
424  	         /* retrieve closest variable bound */
425  	         SCIP_CALL( SCIPgetVarClosestVlb(scip, colvar, NULL, &closestvbd, &closestvbdind) );
426  	
427  	         /* if a suitable variable bound exists which is at least as good as a local simple bound
428  	          * or better than a global simple bound we use it
429  	          */
430  	         if( closestvbdind >= 0 && (SCIPisGT(scip, closestvbd, closestbound) || (localbound && SCIPisSumEQ(scip, closestvbd, closestbound))) )
431  	         {
432  	            vbdcoef = SCIPvarGetVlbCoefs(colvar)[closestvbdind];
433  	            vbdvar = SCIPvarGetVlbVars(colvar)[closestvbdind];
434  	            vbdconst = SCIPvarGetVlbConstants(colvar)[closestvbdind];
435  	            closestbound = closestvbd;
436  	         }
437  	         else
438  	         {
439  	            closestvbdind = -1;
440  	         }
441  	      }
442  	      else
443  	      {
444  	         /* retrieve simple variable bound */
445  	         closestbound = SCIPvarGetUbGlobal(colvar);
446  	         if( allowlocal && SCIPisSumLT(scip, SCIPvarGetUbLocal(colvar), closestbound) )
447  	         {
448  	            closestbound = SCIPvarGetUbLocal(colvar);
449  	            localbound = TRUE;
450  	         }
451  	
452  	         /* retrieve closest variable bound */
453  	         SCIP_CALL( SCIPgetVarClosestVub(scip, colvar, NULL, &closestvbd, &closestvbdind) );
454  	
455  	         /* if a suitable variable bound exists which is at least as good as a local simple bound
456  	          * or better than a global simple bound we use it
457  	          */
458  	         if( closestvbdind >= 0 && (SCIPisLT(scip, closestvbd, closestbound) || (localbound && SCIPisSumEQ(scip, closestvbd, closestbound))) )
459  	         {
460  	            vbdcoef = SCIPvarGetVubCoefs(colvar)[closestvbdind];
461  	            vbdvar = SCIPvarGetVubVars(colvar)[closestvbdind];
462  	            vbdconst = SCIPvarGetVubConstants(colvar)[closestvbdind];
463  	            closestbound = closestvbd;
464  	         }
465  	         else
466  	         {
467  	            closestvbdind = -1;
468  	         }
469  	      }
470  	
471  	      if( closestvbdind >= 0 )
472  	      {
473  	         SCIP_Real coef;
474  	         int pos;
475  	
476  	         coef = val * vbdcoef; /*lint !e644*/
477  	         transrowrhs -= val * vbdconst; /*lint !e644*/
478  	
479  	         pos = intvarpos[SCIPvarGetProbindex(vbdvar)] - 1; /*lint !e644*/
480  	         if( pos >= 0 )
481  	         {
482  	            transrowvals[pos] += coef;
483  	         }
484  	         else
485  	         {
486  	            transrowvars[transrowlen] = SCIPvarGetProbindex(vbdvar);
487  	            transrowvals[transrowlen] = coef;
488  	            intvarpos[SCIPvarGetProbindex(vbdvar)] = ++transrowlen;
489  	         }
490  	      }
491  	      else if( !SCIPisInfinity(scip, REALABS(closestbound)) )
492  	      {
493  	         local = local || localbound;
494  	         transrowrhs -= val * closestbound;
495  	      }
496  	      else
497  	      {
498  	         *success = FALSE;
499  	         break;
500  	      }
501  	   }
502  	
503  	   for( i = 0; i < transrowlen;)
504  	   {
505  	      intvarpos[transrowvars[i]] = 0;
506  	      if( SCIPisZero(scip, transrowvals[i]) )
507  	      {
508  	         --transrowlen;
509  	         transrowvals[i] = transrowvals[transrowlen];
510  	         transrowvars[i] = transrowvars[transrowlen];
511  	      }
512  	      else
513  	         ++i;
514  	   }
515  	
516  	   if( transrowlen <= 1 )
517  	      *success = FALSE;
518  	
519  	   if( *success )
520  	   {
521  	      SCIP_Real mindelta;
522  	      SCIP_Real maxdelta;
523  	      SCIP_Real intscalar;
524  	      int nchgcoefs;
525  	
526  	      SCIP_VAR** vars = SCIPgetVars(scip);
527  	
528  	      *success = ! SCIPcutsTightenCoefficients(scip, local, transrowvals, &transrowrhs, transrowvars, &transrowlen, &nchgcoefs);
529  	
530  	      mindelta = -SCIPepsilon(scip);
531  	      maxdelta = SCIPsumepsilon(scip);
532  	
533  	      if( *success )
534  	      {
535  	         SCIP_CALL( SCIPcalcIntegralScalar(transrowvals, transrowlen, mindelta, maxdelta, MAXDNOM, MAXSCALE, &intscalar, success) );
536  	
537  	         if( *success )
538  	         {
539  	            SCIP_Real floorrhs;
540  	            SCIP_Real slack;
541  	
542  	            transrowrhs *= intscalar; /*lint !e644*/
543  	
544  	            /* slack is initialized to zero since the transrowrhs can still change due to bound usage in the loop below;
545  	             * the floored right hand side is then added afterwards
546  	             */
547  	            slack = 0.0;
548  	            for( i = 0; i < transrowlen; ++i )
549  	            {
550  	               SCIP_Real solval = SCIPgetSolVal(scip, sol, vars[transrowvars[i]]);
551  	               SCIP_Real intval;
552  	               SCIP_Real newval;
553  	
554  	               getIntegralScalar(transrowvals[i], intscalar, mindelta, maxdelta, &newval, &intval);
555  	
556  	               if( !SCIPisEQ(scip, intval, newval) )
557  	               {
558  	                  if( intval < newval )
559  	                  {
560  	                     SCIP_Real lb = local ? SCIPvarGetLbLocal(vars[transrowvars[i]]) : SCIPvarGetLbGlobal(vars[transrowvars[i]]);
561  	
562  	                     if( SCIPisInfinity(scip, -lb) )
563  	                     {
564  	                        *success = FALSE;
565  	                        break;
566  	                     }
567  	
568  	                     transrowrhs += (intval - newval) * lb;
569  	                  }
570  	                  else
571  	                  {
572  	                     SCIP_Real ub = local ? SCIPvarGetUbLocal(vars[transrowvars[i]]) : SCIPvarGetUbGlobal(vars[transrowvars[i]]);
573  	
574  	                     if( SCIPisInfinity(scip, ub) )
575  	                     {
576  	                        *success = FALSE;
577  	                        break;
578  	                     }
579  	
580  	                     transrowrhs += (intval - newval) * ub;
581  	                  }
582  	               }
583  	
584  	               slack -= solval * intval;
585  	               transrowvals[i] = intval;
586  	            }
587  	
588  	            if( *success )
589  	            {
590  	               floorrhs = SCIPfeasFloor(scip, transrowrhs);
591  	               slack += floorrhs;
592  	
593  	               if( slack <= maxslack )
594  	               {
595  	                  introw->rhs = floorrhs;
596  	                  introw->slack = slack;
597  	                  introw->vals = transrowvals;
598  	                  introw->varinds = transrowvars;
599  	                  introw->len = transrowlen;
600  	                  introw->size = rowlen;
601  	                  introw->local = local;
602  	                  introw->rank = rank;
603  	
604  	                  if( !SCIPisEQ(scip, floorrhs, transrowrhs) )
605  	                     introw->rank += 1;
606  	               }
607  	               else
608  	               {
609  	                  *success = FALSE;
610  	               }
611  	            }
612  	         }
613  	      }
614  	   }
615  	
616  	   if( !(*success) )
617  	   {
618  	      SCIPfreeBlockMemoryArray(scip, &transrowvals, rowlen);
619  	      SCIPfreeBlockMemoryArray(scip, &transrowvars, rowlen);
620  	   }
621  	
622  	   return SCIP_OKAY;
623  	}
624  	
625  	
626  	/** Tries to transform non-integral rows into an integral form by using simple and variable bounds */
627  	static
628  	SCIP_RETCODE mod2MatrixTransformContRows(
629  	   SCIP*                 scip,               /**< scip data structure */
630  	   SCIP_SOL*             sol,                /**< solution to separate, or NULL for LP solution */
631  	   SCIP_SEPADATA*        sepadata,           /**< zerohalf separator data */
632  	   MOD2_MATRIX*          mod2matrix,         /**< mod2 matrix structure */
633  	   SCIP_Bool             allowlocal,         /**< should local cuts be allowed */
634  	   SCIP_Real             maxslack            /**< maximum slack allowed for mod 2 rows */
635  	   )
636  	{
637  	   SCIP_ROW** rows;
638  	   int nrows;
639  	   int* intvarpos;
640  	   int i;
641  	   int maxnonzeros;
642  	   SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
643  	   SCIP_CALL( SCIPallocBlockMemoryArray(scip, &mod2matrix->transintrows, 2*nrows) );
644  	   mod2matrix->ntransintrows = 0;
645  	
646  	   SCIP_CALL( SCIPallocCleanBufferArray(scip, &intvarpos, SCIPgetNVars(scip)) );
647  	
648  	   maxnonzeros = (int)(SCIPgetNLPCols(scip) * sepadata->maxrowdensity) + sepadata->densityoffset;
649  	
650  	   for( i = 0; i < nrows; ++i )
651  	   {
652  	      int rowlen;
653  	      SCIP_Real activity;
654  	      SCIP_Real lhs;
655  	      SCIP_Real rhs;
656  	      SCIP_Real lhsslack;
657  	      SCIP_Real rhsslack;
658  	      SCIP_Real* rowvals;
659  	      SCIP_COL** rowcols;
660  	
661  	      /* skip integral rows and rows not suitable for generating cuts */
662  	      if( SCIProwIsModifiable(rows[i]) || SCIProwIsIntegral(rows[i]) || (SCIProwIsLocal(rows[i]) && !allowlocal) || SCIProwGetNNonz(rows[i]) > maxnonzeros )
663  	         continue;
664  	
665  	      lhs = SCIProwGetLhs(rows[i]) - SCIProwGetConstant(rows[i]);
666  	      rhs = SCIProwGetRhs(rows[i]) - SCIProwGetConstant(rows[i]);
667  	      activity = SCIPgetRowSolActivity(scip, rows[i], sol) - SCIProwGetConstant(rows[i]);
668  	
669  	      /* compute lhsslack: activity - lhs */
670  	      if( SCIPisInfinity(scip, -SCIProwGetLhs(rows[i])) )
671  	         lhsslack = SCIPinfinity(scip);
672  	      else
673  	      {
674  	         lhsslack = activity - lhs;
675  	      }
676  	
677  	      /* compute rhsslack: rhs - activity */
678  	      if( SCIPisInfinity(scip, SCIProwGetRhs(rows[i])) )
679  	         rhsslack = SCIPinfinity(scip);
680  	      else
681  	         rhsslack = rhs - activity;
682  	
683  	      if( rhsslack > maxslack && lhsslack > maxslack )
684  	         continue;
685  	
686  	      rowlen = SCIProwGetNLPNonz(rows[i]);
687  	      rowvals = SCIProwGetVals(rows[i]);
688  	      rowcols = SCIProwGetCols(rows[i]);
689  	
690  	      if( rhsslack <= maxslack )
691  	      {
692  	         SCIP_Bool success;
693  	         TRANSINTROW* introw = &mod2matrix->transintrows[mod2matrix->ntransintrows];
694  	         SCIP_CALL( transformNonIntegralRow(scip, sol, allowlocal, maxslack, 1, SCIProwIsLocal(rows[i]), SCIProwGetRank(rows[i]), \
695  	               rowlen, rowvals, rowcols, rhs, intvarpos, introw, &success) );
696  	
697  	         assert(success == 1 || success == 0);
698  	         mod2matrix->ntransintrows += (int)success;
699  	      }
700  	
701  	      if( lhsslack <= maxslack )
702  	      {
703  	         SCIP_Bool success;
704  	         TRANSINTROW* introw = &mod2matrix->transintrows[mod2matrix->ntransintrows];
705  	         SCIP_CALL( transformNonIntegralRow(scip, sol, allowlocal, maxslack, -1, SCIProwIsLocal(rows[i]), SCIProwGetRank(rows[i]), \
706  	               rowlen, rowvals, rowcols, -lhs, intvarpos, introw, &success) );
707  	
708  	         assert(success == 1 || success == 0);
709  	         mod2matrix->ntransintrows += (int)success;
710  	      }
711  	   }
712  	
713  	   SCIPfreeCleanBufferArray(scip, &intvarpos);
714  	
715  	   return SCIP_OKAY;
716  	}
717  	
718  	
719  	/** adds new column to the mod 2 matrix */
720  	static
721  	SCIP_RETCODE mod2MatrixAddCol(
722  	   SCIP*                 scip,               /**< SCIP datastructure */
723  	   MOD2_MATRIX*          mod2matrix,         /**< mod 2 matrix */
724  	   SCIP_HASHMAP*         origvar2col,        /**< hash map for mapping of problem variables to mod 2 columns */
725  	   SCIP_VAR*             origvar,            /**< problem variable to create mod 2 column for */
726  	   SCIP_Real             solval,             /**< solution value of problem variable */
727  	   int                   rhsoffset           /**< offset in right hand side due complementation (mod 2) */
728  	   )
729  	{
730  	   MOD2_COL* col;
731  	
732  	   /* allocate memory */
733  	   SCIP_CALL( SCIPallocBlockMemory(scip, &col) );
734  	
735  	   /* initialize fields */
736  	   col->pos = mod2matrix->ncols++;
737  	   col->index = SCIPvarGetProbindex(origvar);
738  	   col->solval = solval;
739  	   SCIP_CALL( SCIPhashsetCreate(&col->nonzrows, SCIPblkmem(scip), 1) );
740  	
741  	   /* add column to mod 2 matrix */
742  	   SCIP_CALL( SCIPensureBlockMemoryArray(scip, &mod2matrix->cols, &mod2matrix->colssize, mod2matrix->ncols) );
743  	   mod2matrix->cols[col->pos] = col;
744  	
745  	   /* create mapping of problem variable to mod 2 column with its right hand side offset */
746  	   assert(rhsoffset >= 0);
747  	   SCIP_CALL( SCIPhashmapInsert(origvar2col, (void*) origvar, COLINFO_CREATE(col, rhsoffset)) ); /*lint !e571*/
748  	
749  	   return SCIP_OKAY;
750  	}
751  	
752  	/** links row to mod 2 column */
753  	static
754  	SCIP_RETCODE mod2colLinkRow(
755  	   BMS_BLKMEM*           blkmem,             /**< block memory shell */
756  	   MOD2_COL*             col,                /**< mod 2 column */
757  	   MOD2_ROW*             row                 /**< mod 2 row */
758  	   )
759  	{
760  	   SCIP_CALL( SCIPhashsetInsert(col->nonzrows, blkmem, (void*)row) );
761  	
762  	   assert(SCIPhashsetExists(col->nonzrows, (void*)row));
763  	
764  	   row->maxsolval = MAX(col->solval, row->maxsolval);
765  	
766  	   return SCIP_OKAY;
767  	}
768  	
769  	/** unlinks row from mod 2 column */
770  	static
771  	SCIP_RETCODE mod2colUnlinkRow(
772  	   MOD2_COL*             col,                /**< mod 2 column */
773  	   MOD2_ROW*             row                 /**< mod 2 row */
774  	   )
775  	{
776  	   SCIP_CALL( SCIPhashsetRemove(col->nonzrows, (void*)row) );
777  	
778  	   assert(!SCIPhashsetExists(col->nonzrows, (void*)row));
779  	#ifndef NDEBUG
780  	   {
781  	      int nslots = SCIPhashsetGetNSlots(col->nonzrows);
782  	      MOD2_ROW** rows = (MOD2_ROW**) SCIPhashsetGetSlots(col->nonzrows);
783  	      int i;
784  	
785  	      for( i = 0; i < nslots; ++i )
786  	      {
787  	         assert(rows[i] != row);
788  	      }
789  	   }
790  	#endif
791  	
792  	   return SCIP_OKAY;
793  	}
794  	
795  	/** unlinks row from mod 2 column */
796  	static
797  	void mod2rowUnlinkCol(
798  	   MOD2_ROW*             row                 /**< mod 2 row */,
799  	   MOD2_COL*             col                 /**< mod 2 column */
800  	   )
801  	{
802  	   int i;
803  	
804  	   assert(row->nnonzcols == 0 || row->nonzcols != NULL);
805  	
806  	   SCIP_UNUSED( SCIPsortedvecFindPtr((void**) row->nonzcols, compareColIndex, col, row->nnonzcols, &i) );
807  	   assert(row->nonzcols[i] == col);
808  	
809  	   --row->nnonzcols;
810  	   BMSmoveMemoryArray(row->nonzcols + i, row->nonzcols + i + 1, row->nnonzcols - i); /*lint !e866*/
811  	
812  	   if( col->solval >= row->maxsolval )
813  	   {
814  	      row->maxsolval = 0.0;
815  	      for( i = 0; i < row->nnonzcols; ++i )
816  	      {
817  	         row->maxsolval = MAX(row->nonzcols[i]->solval, row->maxsolval);
818  	      }
819  	   }
820  	}
821  	
822  	/** adds a SCIP_ROW to the mod 2 matrix */
823  	static
824  	SCIP_RETCODE mod2MatrixAddOrigRow(
825  	   SCIP*                 scip,               /**< scip data structure */
826  	   BMS_BLKMEM*           blkmem,             /**< block memory shell */
827  	   MOD2_MATRIX*          mod2matrix,         /**< modulo 2 matrix */
828  	   SCIP_HASHMAP*         origcol2col,        /**< hashmap to retrieve the mod 2 column from a SCIP_COL */
829  	   SCIP_ROW*             origrow,            /**< original SCIP row */
830  	   SCIP_Real             slack,              /**< slack of row */
831  	   ROWIND_TYPE           side,               /**< side of row that is used for mod 2 row, must be ORIG_RHS or ORIG_LHS */
832  	   int                   rhsmod2             /**< modulo 2 value of the row's right hand side */
833  	   )
834  	{
835  	   SCIP_Real* rowvals;
836  	   SCIP_COL** rowcols;
837  	   int rowlen;
838  	   int i;
839  	   MOD2_ROW* row;
840  	
841  	   SCIP_ALLOC( BMSallocBlockMemory(blkmem, &row) );
842  	
843  	   row->index = mod2matrix->nrows++;
844  	   SCIP_CALL( SCIPensureBlockMemoryArray(scip, &mod2matrix->rows, &mod2matrix->rowssize, mod2matrix->nrows) );
845  	   mod2matrix->rows[row->index] = row;
846  	
847  	   row->slack = MAX(0.0, slack);
848  	   row->maxsolval = 0.0;
849  	   row->rhs = rhsmod2;
850  	   row->nrowinds = 1;
851  	   row->rowinds = NULL;
852  	   row->rowindssize = 0;
853  	
854  	   if( SCIPisZero(scip, row->slack) )
855  	      ++mod2matrix->nzeroslackrows;
856  	
857  	   SCIP_CALL( SCIPensureBlockMemoryArray(scip, &row->rowinds, &row->rowindssize, row->nrowinds) );
858  	   row->rowinds[0].type = side;
859  	   row->rowinds[0].index = (unsigned int)SCIProwGetLPPos(origrow);
860  	
861  	   row->nnonzcols = 0;
862  	   row->nonzcolssize = 0;
863  	   row->nonzcols = NULL;
864  	
865  	   rowlen = SCIProwGetNNonz(origrow);
866  	   rowvals = SCIProwGetVals(origrow);
867  	   rowcols = SCIProwGetCols(origrow);
868  	
869  	   for( i = 0; i < rowlen; ++i )
870  	   {
871  	      if( mod2(scip, rowvals[i]) == 1 )
872  	      {
873  	         void* colinfo;
874  	         MOD2_COL* col;
875  	         int rhsoffset;
876  	
877  	         colinfo = SCIPhashmapGetImage(origcol2col, (void*)SCIPcolGetVar(rowcols[i]));
878  	
879  	         /* extract the righthand side offset from the colinfo and update the righthand side */
880  	         rhsoffset = COLINFO_GET_RHSOFFSET(colinfo);
881  	         row->rhs = (row->rhs + rhsoffset) % 2;
882  	
883  	         /* extract the column pointer from the colinfo */
884  	         col = COLINFO_GET_MOD2COL(colinfo);
885  	
886  	         if( col != NULL )
887  	         {
888  	            int k;
889  	
890  	            k = row->nnonzcols++;
891  	
892  	            SCIP_CALL( SCIPensureBlockMemoryArray(scip, &row->nonzcols, &row->nonzcolssize, row->nnonzcols) );
893  	            row->nonzcols[k] = col;
894  	
895  	            SCIP_CALL( mod2colLinkRow(blkmem, col, row) );
896  	         }
897  	      }
898  	   }
899  	
900  	   SCIPsortPtr((void**)row->nonzcols, compareColIndex, row->nnonzcols);
901  	
902  	   checkRow(row);
903  	
904  	   return SCIP_OKAY;
905  	}
906  	
907  	/** adds a transformed integral row to the mod 2 matrix */
908  	static
909  	SCIP_RETCODE mod2MatrixAddTransRow(
910  	   SCIP*                 scip,               /**< scip data structure */
911  	   MOD2_MATRIX*          mod2matrix,         /**< modulo 2 matrix */
912  	   SCIP_HASHMAP*         origcol2col,        /**< hashmap to retrieve the mod 2 column from a SCIP_COL */
913  	   int                   transrowind         /**< index to transformed int row */
914  	   )
915  	{
916  	   int i;
917  	   SCIP_VAR** vars;
918  	   BMS_BLKMEM* blkmem;
919  	   MOD2_ROW* row;
920  	   TRANSINTROW* introw;
921  	
922  	   SCIP_CALL( SCIPallocBlockMemory(scip, &row) );
923  	
924  	   vars = SCIPgetVars(scip);
925  	   introw = &mod2matrix->transintrows[transrowind];
926  	
927  	   blkmem = SCIPblkmem(scip);
928  	   row->index = mod2matrix->nrows++;
929  	   SCIP_CALL( SCIPensureBlockMemoryArray(scip, &mod2matrix->rows, &mod2matrix->rowssize, mod2matrix->nrows) );
930  	   mod2matrix->rows[row->index] = row;
931  	
932  	   row->slack = MAX(0.0, introw->slack);
933  	   row->rhs = mod2(scip, introw->rhs);
934  	   row->nrowinds = 1;
935  	   row->rowinds = NULL;
936  	   row->rowindssize = 0;
937  	   row->maxsolval = 0.0;
938  	
939  	   if( SCIPisZero(scip, row->slack) )
940  	      ++mod2matrix->nzeroslackrows;
941  	
942  	   SCIP_CALL( SCIPensureBlockMemoryArray(scip, &row->rowinds, &row->rowindssize, row->nrowinds) );
943  	   row->rowinds[0].type = TRANSROW;
944  	   row->rowinds[0].index = (unsigned int)transrowind;
945  	
946  	   row->nnonzcols = 0;
947  	   row->nonzcolssize = 0;
948  	   row->nonzcols = NULL;
949  	
950  	   for( i = 0; i < introw->len; ++i )
951  	   {
952  	      if( mod2(scip, introw->vals[i]) == 1 )
953  	      {
954  	         void* colinfo;
955  	         MOD2_COL* col;
956  	         int rhsoffset;
957  	
958  	         colinfo = SCIPhashmapGetImage(origcol2col, (void*)vars[introw->varinds[i]]);
959  	
960  	         /* extract the righthand side offset from the colinfo and update the righthand side */
961  	         rhsoffset = COLINFO_GET_RHSOFFSET(colinfo);
962  	         row->rhs = (row->rhs + rhsoffset) % 2;
963  	
964  	         /* extract the column pointer from the colinfo */
965  	         col = COLINFO_GET_MOD2COL(colinfo);
966  	
967  	         if( col != NULL )
968  	         {
969  	            int k;
970  	
971  	            k = row->nnonzcols++;
972  	
973  	            SCIP_CALL( SCIPensureBlockMemoryArray(scip, &row->nonzcols, &row->nonzcolssize, row->nnonzcols) );
974  	            row->nonzcols[k] = col;
975  	
976  	            SCIP_CALL( mod2colLinkRow(blkmem, col, row) );
977  	         }
978  	      }
979  	   }
980  	
981  	   SCIPsortPtr((void**)row->nonzcols, compareColIndex, row->nnonzcols);
982  	
983  	   checkRow(row);
984  	
985  	   return SCIP_OKAY;
986  	}
987  	
988  	/** free all resources held by the mod 2 matrix */
989  	static
990  	void destroyMod2Matrix(
991  	   SCIP*                 scip,               /**< scip data structure */
992  	   MOD2_MATRIX*          mod2matrix          /**< pointer to mod2 matrix structure */
993  	   )
994  	{
995  	   int i;
996  	
997  	   for( i = 0; i < mod2matrix->ncols; ++i )
998  	   {
999  	      SCIPhashsetFree(&mod2matrix->cols[i]->nonzrows, SCIPblkmem(scip));
1000 	      SCIPfreeBlockMemory(scip, &mod2matrix->cols[i]); /*lint !e866*/
1001 	   }
1002 	
1003 	   for( i = 0; i < mod2matrix->nrows; ++i )
1004 	   {
1005 	      SCIPfreeBlockMemoryArrayNull(scip, &mod2matrix->rows[i]->nonzcols, mod2matrix->rows[i]->nonzcolssize);
1006 	      SCIPfreeBlockMemoryArrayNull(scip, &mod2matrix->rows[i]->rowinds, mod2matrix->rows[i]->rowindssize);
1007 	      SCIPfreeBlockMemory(scip, &mod2matrix->rows[i]); /*lint !e866*/
1008 	   }
1009 	
1010 	   for( i = 0; i < mod2matrix->ntransintrows; ++i )
1011 	   {
1012 	      SCIPfreeBlockMemoryArray(scip, &mod2matrix->transintrows[i].vals, mod2matrix->transintrows[i].size);
1013 	      SCIPfreeBlockMemoryArray(scip, &mod2matrix->transintrows[i].varinds, mod2matrix->transintrows[i].size);
1014 	   }
1015 	
1016 	   SCIPfreeBlockMemoryArray(scip, &mod2matrix->transintrows, 2*SCIPgetNLPRows(scip)); /*lint !e647*/
1017 	
1018 	   SCIPfreeBlockMemoryArrayNull(scip, &mod2matrix->rows, mod2matrix->rowssize);
1019 	   SCIPfreeBlockMemoryArrayNull(scip, &mod2matrix->cols, mod2matrix->colssize);
1020 	}
1021 	
1022 	/** build the modulo 2 matrix from all integral rows in the LP, and non-integral rows
1023 	 *  if the transformation to an integral row succeeds
1024 	 */
1025 	static
1026 	SCIP_RETCODE buildMod2Matrix(
1027 	   SCIP*                 scip,               /**< scip data structure */
1028 	   SCIP_SOL*             sol,                /**< solution to separate, or NULL for LP solution */
1029 	   SCIP_SEPADATA*        sepadata,           /**< zerohalf separator data */
1030 	   BMS_BLKMEM*           blkmem,             /**< block memory shell */
1031 	   MOD2_MATRIX*          mod2matrix,         /**< mod 2 matrix */
1032 	   SCIP_Bool             allowlocal,         /**< should local cuts be allowed */
1033 	   SCIP_Real             maxslack            /**< maximum slack allowed for mod 2 rows */
1034 	   )
1035 	{
1036 	   SCIP_VAR** vars;
1037 	   SCIP_ROW** rows;
1038 	   SCIP_COL** cols;
1039 	   SCIP_HASHMAP* origcol2col;
1040 	   int ncols;
1041 	   int nrows;
1042 	   int nintvars;
1043 	   int maxnonzeros;
1044 	   int i;
1045 	   SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
1046 	   SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
1047 	
1048 	   nintvars = SCIPgetNVars(scip) - SCIPgetNContVars(scip);
1049 	   vars = SCIPgetVars(scip);
1050 	
1051 	   /* initialize fields */
1052 	   mod2matrix->cols = NULL;
1053 	   mod2matrix->colssize = 0;
1054 	   mod2matrix->ncols = 0;
1055 	   mod2matrix->rows = NULL;
1056 	   mod2matrix->rowssize = 0;
1057 	   mod2matrix->nrows = 0;
1058 	   mod2matrix->nzeroslackrows = 0;
1059 	
1060 	   SCIP_CALL( SCIPhashmapCreate(&origcol2col, SCIPblkmem(scip), 1) );
1061 	
1062 	   /* add all integral vars if they are not at their bound */
1063 	   for( i = 0; i < nintvars; ++i )
1064 	   {
1065 	      SCIP_Real lb;
1066 	      SCIP_Real ub;
1067 	      SCIP_Real lbsol;
1068 	      SCIP_Real ubsol;
1069 	      SCIP_Real primsol;
1070 	      SCIP_Bool useub;
1071 	
1072 	      primsol = SCIPgetSolVal(scip, sol, vars[i]);
1073 	
1074 	      lb = allowlocal ? SCIPvarGetLbLocal(vars[i]) : SCIPvarGetLbGlobal(vars[i]);
1075 	      lbsol = MAX(0.0, primsol - lb);
1076 	      if( SCIPisZero(scip, lbsol) )
1077 	      {
1078 	         SCIP_CALL( SCIPhashmapInsert(origcol2col, (void*) vars[i], COLINFO_CREATE(NULL, mod2(scip, lb))) ); /*lint !e571*/
1079 	         continue;
1080 	      }
1081 	
1082 	      ub = allowlocal ? SCIPvarGetUbLocal(vars[i]) : SCIPvarGetUbGlobal(vars[i]);
1083 	      ubsol = MAX(0.0, ub - primsol);
1084 	      if( SCIPisZero(scip, ubsol) )
1085 	      {
1086 	         SCIP_CALL( SCIPhashmapInsert(origcol2col, (void*) vars[i], COLINFO_CREATE(NULL, mod2(scip, ub))) ); /*lint !e571*/
1087 	         continue;
1088 	      }
1089 	
1090 	      if( SCIPisInfinity(scip, ub) ) /* if there is no ub, use lb */
1091 	         useub = FALSE;
1092 	      else if( SCIPisInfinity(scip, -lb) ) /* if there is no lb, use ub */
1093 	         useub = TRUE;
1094 	      else if( SCIPisLT(scip, primsol, (1.0 - BOUNDSWITCH) * lb + BOUNDSWITCH * ub) )
1095 	         useub = FALSE;
1096 	      else
1097 	         useub = TRUE;
1098 	
1099 	      if( useub )
1100 	      {
1101 	         assert(ubsol > 0.0);
1102 	
1103 	         /* coverity[var_deref_model] */
1104 	         SCIP_CALL( mod2MatrixAddCol(scip, mod2matrix, origcol2col, vars[i], ubsol, mod2(scip, ub)) );
1105 	      }
1106 	      else
1107 	      {
1108 	         assert(lbsol > 0.0);
1109 	
1110 	         /* coverity[var_deref_model] */
1111 	         SCIP_CALL( mod2MatrixAddCol(scip, mod2matrix, origcol2col, vars[i], lbsol, mod2(scip, lb)) );
1112 	      }
1113 	   }
1114 	
1115 	   maxnonzeros = (int)(SCIPgetNLPCols(scip) * sepadata->maxrowdensity) + sepadata->densityoffset;
1116 	
1117 	   /* add all integral rows using the created columns */
1118 	   for( i = 0; i < nrows; ++i )
1119 	   {
1120 	      SCIP_Real lhs;
1121 	      SCIP_Real rhs;
1122 	      SCIP_Real activity;
1123 	      SCIP_Real lhsslack;
1124 	      SCIP_Real rhsslack;
1125 	      int lhsmod2;
1126 	      int rhsmod2;
1127 	
1128 	      /* skip non-integral rows and rows not suitable for generating cuts */
1129 	      if( SCIProwIsModifiable(rows[i]) || !SCIProwIsIntegral(rows[i]) || (SCIProwIsLocal(rows[i]) && !allowlocal) || SCIProwGetNNonz(rows[i]) > maxnonzeros )
1130 	         continue;
1131 	
1132 	      lhsmod2 = 0;
1133 	      rhsmod2 = 0;
1134 	      activity = SCIPgetRowSolActivity(scip, rows[i], sol) - SCIProwGetConstant(rows[i]);
1135 	
1136 	      /* since row is integral we can ceil/floor the lhs/rhs after subtracting the constant */
1137 	      lhs = SCIPfeasCeil(scip, SCIProwGetLhs(rows[i]) - SCIProwGetConstant(rows[i]));
1138 	      rhs = SCIPfeasFloor(scip, SCIProwGetRhs(rows[i]) - SCIProwGetConstant(rows[i]));
1139 	
1140 	      /* compute lhsslack: activity - lhs */
1141 	      if( SCIPisInfinity(scip, -SCIProwGetLhs(rows[i])) )
1142 	         lhsslack = SCIPinfinity(scip);
1143 	      else
1144 	      {
1145 	         lhsslack = activity - lhs;
1146 	         lhsmod2 = mod2(scip, lhs);
1147 	      }
1148 	
1149 	      /* compute rhsslack: rhs - activity */
1150 	      if( SCIPisInfinity(scip, SCIProwGetRhs(rows[i])) )
1151 	         rhsslack = SCIPinfinity(scip);
1152 	      else
1153 	      {
1154 	         rhsslack = rhs - activity;
1155 	         rhsmod2 = mod2(scip, rhs);
1156 	      }
1157 	
1158 	      if( rhsslack <= maxslack && lhsslack <= maxslack )
1159 	      {
1160 	         if( lhsmod2 == rhsmod2 )
1161 	         {
1162 	            /* maxslack < 1 implies rhs - lhs = rhsslack + lhsslack < 2. Therefore lhs = rhs (mod2) can only hold if they
1163 	             * are equal
1164 	             */
1165 	            assert(SCIPisEQ(scip, lhs, rhs));
1166 	
1167 	            /* use rhs */
1168 	            /* coverity[var_deref_model] */
1169 	            SCIP_CALL( mod2MatrixAddOrigRow(scip, blkmem, mod2matrix, origcol2col, rows[i], rhsslack, ORIG_RHS, rhsmod2) );
1170 	         }
1171 	         else
1172 	         {
1173 	            /* use both */
1174 	            /* coverity[var_deref_model] */
1175 	            SCIP_CALL( mod2MatrixAddOrigRow(scip, blkmem, mod2matrix, origcol2col, rows[i], lhsslack, ORIG_LHS, lhsmod2) );
1176 	            SCIP_CALL( mod2MatrixAddOrigRow(scip, blkmem, mod2matrix, origcol2col, rows[i], rhsslack, ORIG_RHS, rhsmod2) );
1177 	         }
1178 	      }
1179 	      else if( rhsslack <= maxslack )
1180 	      {
1181 	         /* use rhs */
1182 	         /* coverity[var_deref_model] */
1183 	         SCIP_CALL( mod2MatrixAddOrigRow(scip, blkmem, mod2matrix, origcol2col, rows[i], rhsslack, ORIG_RHS, rhsmod2) );
1184 	      }
1185 	      else if( lhsslack <= maxslack )
1186 	      {
1187 	         /* use lhs */
1188 	         /* coverity[var_deref_model] */
1189 	         SCIP_CALL( mod2MatrixAddOrigRow(scip, blkmem, mod2matrix, origcol2col, rows[i], lhsslack, ORIG_LHS, lhsmod2) );
1190 	      }
1191 	   }
1192 	
1193 	   /* transform non-integral rows */
1194 	   SCIP_CALL( mod2MatrixTransformContRows(scip, sol, sepadata, mod2matrix, allowlocal, maxslack) );
1195 	
1196 	   /* add all transformed integral rows using the created columns */
1197 	   for( i = 0; i < mod2matrix->ntransintrows; ++i )
1198 	   {
1199 	      SCIP_CALL( mod2MatrixAddTransRow(scip, mod2matrix, origcol2col, i) );
1200 	   }
1201 	
1202 	   SCIPhashmapFree(&origcol2col);
1203 	
1204 	   return SCIP_OKAY;
1205 	}
1206 	
1207 	/* compare two mod 2 columns for equality */
1208 	static
1209 	SCIP_DECL_HASHKEYEQ(columnsEqual)
1210 	{  /*lint --e{715}*/
1211 	   MOD2_COL* col1;
1212 	   MOD2_COL* col2;
1213 	   int nslotscol1;
1214 	   MOD2_ROW** col1rows;
1215 	   int i;
1216 	
1217 	   col1 = (MOD2_COL*) key1;
1218 	   col2 = (MOD2_COL*) key2;
1219 	
1220 	   if( SCIPhashsetGetNElements(col1->nonzrows) != SCIPhashsetGetNElements(col2->nonzrows) )
1221 	      return FALSE;
1222 	
1223 	   nslotscol1 = SCIPhashsetGetNSlots(col1->nonzrows);
1224 	   col1rows = (MOD2_ROW**) SCIPhashsetGetSlots(col1->nonzrows);
1225 	   for( i = 0; i < nslotscol1; ++i )
1226 	   {
1227 	      if( col1rows[i] != NULL && !SCIPhashsetExists(col2->nonzrows, (void*)col1rows[i]) )
1228 	         return FALSE;
1229 	   }
1230 	
1231 	   return TRUE;
1232 	}
1233 	
1234 	/* compute a signature of the rows in a mod 2 matrix as hash value */
1235 	static
1236 	SCIP_DECL_HASHKEYVAL(columnGetSignature)
1237 	{  /*lint --e{715}*/
1238 	   MOD2_COL* col;
1239 	   MOD2_ROW** rows;
1240 	   uint64_t signature;
1241 	   int i;
1242 	   int nslots;
1243 	
1244 	   col = (MOD2_COL*) key;
1245 	
1246 	   nslots = SCIPhashsetGetNSlots(col->nonzrows);
1247 	   rows = (MOD2_ROW**) SCIPhashsetGetSlots(col->nonzrows);
1248 	
1249 	   signature = 0;
1250 	   for( i = 0; i < nslots; ++i )
1251 	   {
1252 	      if( rows[i] != NULL )
1253 	         signature |= SCIPhashSignature64(rows[i]->index);
1254 	   }
1255 	
1256 	   return signature;
1257 	}
1258 	
1259 	/* compare two mod 2 rows for equality */
1260 	static
1261 	SCIP_DECL_HASHKEYEQ(rowsEqual)
1262 	{  /*lint --e{715}*/
1263 	   MOD2_ROW* row1;
1264 	   MOD2_ROW* row2;
1265 	   int i;
1266 	
1267 	   row1 = (MOD2_ROW*) key1;
1268 	   row2 = (MOD2_ROW*) key2;
1269 	
1270 	   assert(row1 != NULL);
1271 	   assert(row2 != NULL);
1272 	   assert(row1->nnonzcols == 0 || row1->nonzcols != NULL);
1273 	   assert(row2->nnonzcols == 0 || row2->nonzcols != NULL);
1274 	
1275 	   if( row1->nnonzcols != row2->nnonzcols || row1->rhs != row2->rhs )
1276 	      return FALSE;
1277 	
1278 	   for( i = 0; i < row1->nnonzcols; ++i )
1279 	   {
1280 	      if( row1->nonzcols[i] != row2->nonzcols[i] )
1281 	         return FALSE;
1282 	   }
1283 	
1284 	   return TRUE;
1285 	}
1286 	
1287 	/* compute a signature of a mod 2 row as hash value */
1288 	static
1289 	SCIP_DECL_HASHKEYVAL(rowGetSignature)
1290 	{  /*lint --e{715}*/
1291 	   MOD2_ROW* row;
1292 	   int i;
1293 	   uint64_t signature;
1294 	
1295 	   row = (MOD2_ROW*) key;
1296 	   assert(row->nnonzcols == 0 || row->nonzcols != NULL);
1297 	
1298 	   signature = row->rhs; /*lint !e732*/
1299 	
1300 	   for( i = 0; i < row->nnonzcols; ++i )
1301 	      signature |= SCIPhashSignature64(row->nonzcols[i]->index);
1302 	
1303 	   return signature;
1304 	}
1305 	
1306 	/** removes a row from the mod 2 matrix */
1307 	static
1308 	SCIP_RETCODE mod2matrixRemoveRow(
1309 	   SCIP*                 scip,               /**< scip data structure */
1310 	   MOD2_MATRIX*          mod2matrix,         /**< the mod 2 matrix */
1311 	   MOD2_ROW*             row                 /**< mod 2 row */
1312 	   )
1313 	{
1314 	   int i;
1315 	   int position = row->pos;
1316 	
1317 	   checkRow(row);
1318 	
1319 	   /* update counter for zero slack rows */
1320 	   if( SCIPisZero(scip, row->slack) )
1321 	      --mod2matrix->nzeroslackrows;
1322 	
1323 	   /* remove the row from the array */
1324 	   --mod2matrix->nrows;
1325 	   mod2matrix->rows[position] = mod2matrix->rows[mod2matrix->nrows];
1326 	   mod2matrix->rows[position]->pos = position;
1327 	
1328 	   /* unlink columns from row */
1329 	   for( i = 0; i < row->nnonzcols; ++i )
1330 	   {
1331 	      SCIP_CALL( mod2colUnlinkRow(row->nonzcols[i], row) );
1332 	   }
1333 	
1334 	   /* free row */
1335 	   SCIPfreeBlockMemoryArrayNull(scip, &row->nonzcols, row->nonzcolssize);
1336 	   SCIPfreeBlockMemoryArray(scip, &row->rowinds, row->rowindssize);
1337 	   SCIPfreeBlockMemory(scip, &row);
1338 	
1339 	   return SCIP_OKAY;
1340 	}
1341 	
1342 	/** removes a column from the mod 2 matrix */
1343 	static
1344 	void mod2matrixRemoveCol(
1345 	   SCIP*                 scip,               /**< scip data structure */
1346 	   MOD2_MATRIX*          mod2matrix,         /**< the mod 2 matrix */
1347 	   MOD2_COL*             col                 /**< a column in the mod 2 matrix */
1348 	   )
1349 	{
1350 	   int i;
1351 	   int nslots;
1352 	   MOD2_ROW** rows;
1353 	   int position;
1354 	
1355 	   assert(col != NULL);
1356 	
1357 	   /* cppcheck-suppress nullPointer */
1358 	   position = col->pos;
1359 	
1360 	   /* remove column from arrays */
1361 	   --mod2matrix->ncols;
1362 	   mod2matrix->cols[position] = mod2matrix->cols[mod2matrix->ncols];
1363 	   mod2matrix->cols[position]->pos = position;
1364 	
1365 	   /* cppcheck-suppress nullPointer */
1366 	   nslots = SCIPhashsetGetNSlots(col->nonzrows);
1367 	   /* cppcheck-suppress nullPointer */
1368 	   rows = (MOD2_ROW**) SCIPhashsetGetSlots(col->nonzrows);
1369 	
1370 	   /* adjust rows of column */
1371 	   for( i = 0; i < nslots; ++i )
1372 	   {
1373 	      if( rows[i] != NULL )
1374 	         mod2rowUnlinkCol(rows[i], col);
1375 	   }
1376 	
1377 	   /* free column */
1378 	   SCIPhashsetFree(&col->nonzrows, SCIPblkmem(scip));
1379 	   SCIPfreeBlockMemory(scip, &col);
1380 	}
1381 	
1382 	/* remove columns that are (Prop3 iii) zero (Prop3 iv) identify indentical columns (Prop3 v) unit vector columns */
1383 	static
1384 	SCIP_RETCODE mod2matrixPreprocessColumns(
1385 	   SCIP*                 scip,               /**< scip data structure */
1386 	   MOD2_MATRIX*          mod2matrix,         /**< mod 2 matrix */
1387 	   SCIP_SEPADATA*        sepadata            /**< zerohalf separator data */
1388 	   )
1389 	{
1390 	   int i;
1391 	   SCIP_HASHTABLE* columntable;
1392 	
1393 	   SCIP_CALL( SCIPhashtableCreate(&columntable, SCIPblkmem(scip), mod2matrix->ncols,
1394 	                                  SCIPhashGetKeyStandard, columnsEqual, columnGetSignature, NULL) );
1395 	
1396 	   for( i = 0; i < mod2matrix->ncols; )
1397 	   {
1398 	      MOD2_COL* col = mod2matrix->cols[i];
1399 	      int nnonzrows = SCIPhashsetGetNElements(col->nonzrows);
1400 	      if( nnonzrows == 0 )
1401 	      { /* Prop3 iii */
1402 	         mod2matrixRemoveCol(scip, mod2matrix, col);
1403 	      }
1404 	      else if( nnonzrows == 1 )
1405 	      { /* Prop3 v */
1406 	         MOD2_ROW* row;
1407 	
1408 	         {
1409 	            int j = 0;
1410 	            MOD2_ROW** rows;
1411 	            rows = (MOD2_ROW**) SCIPhashsetGetSlots(col->nonzrows);
1412 	            while( rows[j] == NULL )
1413 	               ++j;
1414 	
1415 	            row = rows[j];
1416 	         }
1417 	
1418 	         checkRow(row);
1419 	
1420 	         /* column is unit vector, so add its solution value to the rows slack and remove it */
1421 	         if( SCIPisZero(scip, row->slack) )
1422 	            --mod2matrix->nzeroslackrows;
1423 	
1424 	         row->slack += col->solval;
1425 	         assert(!SCIPisZero(scip, row->slack));
1426 	
1427 	         mod2matrixRemoveCol(scip, mod2matrix, col);
1428 	         ++sepadata->nreductions;
1429 	
1430 	         checkRow(row);
1431 	      }
1432 	      else
1433 	      {
1434 	         MOD2_COL* identicalcol;
1435 	         identicalcol = (MOD2_COL*)SCIPhashtableRetrieve(columntable, col);
1436 	         if( identicalcol != NULL )
1437 	         {
1438 	            assert(identicalcol != col);
1439 	
1440 	            /* column is identical to other column so add its solution value to the other one and then remove and free it */
1441 	            identicalcol->solval += col->solval;
1442 	
1443 	            /* also adjust the solval of the removed column so that the maxsolval of each row is properly updated */
1444 	            col->solval = identicalcol->solval;
1445 	
1446 	            mod2matrixRemoveCol(scip, mod2matrix, col);
1447 	         }
1448 	         else
1449 	         {
1450 	            SCIP_CALL( SCIPhashtableInsert(columntable, (void*)col) );
1451 	            ++i;
1452 	         }
1453 	      }
1454 	   }
1455 	
1456 	   SCIPhashtableFree(&columntable);
1457 	
1458 	   return SCIP_OKAY;
1459 	}
1460 	
1461 	#define NONZERO(x)   (COPYSIGN(1e-100, (x)) + (x))
1462 	
1463 	/** add original row to aggregation with weight 0.5 */
1464 	static
1465 	void addOrigRow(
1466 	   SCIP*                 scip,               /**< SCIP datastructure */
1467 	   SCIP_Real*            tmpcoefs,           /**< array to add coefficients to */
1468 	   SCIP_Real*            cutrhs,             /**< pointer to add right hand side */
1469 	   int*                  nonzeroinds,        /**< array of non-zeros in the aggregation */
1470 	   int*                  nnz,                /**< pointer to update number of non-zeros */
1471 	   int*                  cutrank,            /**< pointer to update cut rank */
1472 	   SCIP_Bool*            cutislocal,         /**< pointer to update local flag */
1473 	   SCIP_ROW*             row,                /**< row to add */
1474 	   int                   sign                /**< sign for weight, i.e. +1 to use right hand side or -1 to use left hand side */
1475 	   )
1476 	{
1477 	   int i;
1478 	   SCIP_Real weight = 0.5 * sign;
1479 	   SCIP_COL** rowcols;
1480 	   SCIP_Real* rowvals;
1481 	   int rowlen;
1482 	
1483 	   rowlen = SCIProwGetNNonz(row);
1484 	   rowcols = SCIProwGetCols(row);
1485 	   rowvals = SCIProwGetVals(row);
1486 	   for( i = 0; i < rowlen; ++i )
1487 	   {
1488 	      SCIP_Real val;
1489 	      int probindex;
1490 	
1491 	      probindex = SCIPcolGetVarProbindex(rowcols[i]);
1492 	      val = tmpcoefs[probindex];
1493 	      if( val == 0.0 )
1494 	      {
1495 	         nonzeroinds[(*nnz)++] = probindex;
1496 	      }
1497 	
1498 	      val += weight * rowvals[i];
1499 	      tmpcoefs[probindex] = NONZERO(val);
1500 	   }
1501 	
1502 	   if( sign == +1 )
1503 	   {
1504 	      *cutrhs += weight * SCIPfeasFloor(scip, SCIProwGetRhs(row) - SCIProwGetConstant(row));
1505 	   }
1506 	   else
1507 	   {
1508 	      assert(sign == -1);
1509 	      *cutrhs += weight * SCIPfeasCeil(scip, SCIProwGetLhs(row) - SCIProwGetConstant(row));
1510 	   }
1511 	
1512 	   if( SCIProwGetRank(row) > *cutrank )
1513 	      *cutrank = SCIProwGetRank(row);
1514 	   *cutislocal = *cutislocal || SCIProwIsLocal(row);
1515 	}
1516 	
1517 	/** add transformed integral row to aggregation with weight 0.5 */
1518 	static
1519 	void addTransRow(
1520 	   SCIP_Real*            tmpcoefs,           /**< array to add coefficients to */
1521 	   SCIP_Real*            cutrhs,             /**< pointer to add right hand side */
1522 	   int*                  nonzeroinds,        /**< array of non-zeros in the aggregation */
1523 	   int*                  nnz,                /**< pointer to update number of non-zeros */
1524 	   int*                  cutrank,            /**< pointer to update cut rank */
1525 	   SCIP_Bool*            cutislocal,         /**< pointer to update local flag */
1526 	   TRANSINTROW*          introw              /**< transformed integral row to add to the aggregation */
1527 	   )
1528 	{
1529 	   int i;
1530 	
1531 	   for( i = 0; i < introw->len; ++i )
1532 	   {
1533 	      int probindex = introw->varinds[i];
1534 	      SCIP_Real val = tmpcoefs[probindex];
1535 	
1536 	      if( val == 0.0 )
1537 	      {
1538 	         nonzeroinds[(*nnz)++] = probindex;
1539 	      }
1540 	
1541 	      val += 0.5 * introw->vals[i];
1542 	      tmpcoefs[probindex] = NONZERO(val);
1543 	   }
1544 	
1545 	   *cutrhs += 0.5 * introw->rhs;
1546 	
1547 	   *cutrank = MAX(*cutrank, introw->rank);
1548 	   *cutislocal = *cutislocal || introw->local;
1549 	}
1550 	
1551 	/* calculates the cuts efficacy of cut */
1552 	static
1553 	SCIP_Real calcEfficacy(
1554 	   SCIP*                 scip,               /**< SCIP data structure */
1555 	   SCIP_SOL*             sol,                /**< solution to separate, or NULL for LP solution */
1556 	   SCIP_Real*            cutcoefs,           /**< array of the non-zero coefficients in the cut */
1557 	   SCIP_Real             cutrhs,             /**< the right hand side of the cut */
1558 	   int*                  cutinds,            /**< array of the problem indices of variables with a non-zero coefficient in the cut */
1559 	   int                   cutnnz              /**< the number of non-zeros in the cut */
1560 	   )
1561 	{
1562 	   SCIP_VAR** vars;
1563 	   SCIP_Real norm;
1564 	   SCIP_Real activity;
1565 	   int i;
1566 	
1567 	   assert(scip != NULL);
1568 	   assert(cutcoefs != NULL);
1569 	   assert(cutinds != NULL);
1570 	
1571 	   norm = SCIPgetVectorEfficacyNorm(scip, cutcoefs, cutnnz);
1572 	   vars = SCIPgetVars(scip);
1573 	
1574 	   activity = 0.0;
1575 	   for( i = 0; i < cutnnz; ++i )
1576 	      activity += cutcoefs[i] * SCIPgetSolVal(scip, sol, vars[cutinds[i]]);
1577 	
1578 	   return (activity - cutrhs) / MAX(1e-6, norm);
1579 	}
1580 	
1581 	/** computes maximal violation that can be achieved for zerohalf cuts where this row particiaptes */
1582 	static
1583 	SCIP_Real computeMaxViolation(
1584 	   MOD2_ROW*             row                 /**< mod 2 row */
1585 	   )
1586 	{
1587 	   SCIP_Real viol;
1588 	
1589 	   viol = 1.0 - row->slack;
1590 	   viol *= 0.5;
1591 	
1592 	   return viol;
1593 	}
1594 	
1595 	/** computes violation of zerohalf cut generated from given mod 2 row */
1596 	static
1597 	SCIP_Real computeViolation(
1598 	   MOD2_ROW*             row                 /**< mod 2 row */
1599 	   )
1600 	{
1601 	   int i;
1602 	   SCIP_Real viol;
1603 	
1604 	   viol = 1.0 - row->slack;
1605 	
1606 	   for( i = 0; i < row->nnonzcols; ++i )
1607 	   {
1608 	      viol -= row->nonzcols[i]->solval;
1609 	   }
1610 	
1611 	   viol *= 0.5;
1612 	
1613 	   return viol;
1614 	}
1615 	
1616 	/** generate a zerohalf cut from a given mod 2 row, i.e., try if aggregations of rows of the
1617 	 *  mod2 matrix give violated cuts
1618 	 */
1619 	static
1620 	SCIP_RETCODE generateZerohalfCut(
1621 	   SCIP*                 scip,               /**< scip data structure */
1622 	   SCIP_SOL*             sol,                /**< solution to separate, or NULL for LP solution */
1623 	   MOD2_MATRIX*          mod2matrix,         /**< mod 2 matrix */
1624 	   SCIP_SEPA*            sepa,               /**< zerohalf separator */
1625 	   SCIP_SEPADATA*        sepadata,           /**< zerohalf separator data */
1626 	   SCIP_Bool             allowlocal,         /**< should local cuts be allowed */
1627 	   MOD2_ROW*             row                 /**< mod 2 row */
1628 	   )
1629 	{
1630 	   SCIP_Bool cutislocal;
1631 	   int i;
1632 	   int cutnnz;
1633 	   int cutrank;
1634 	   int nvars;
1635 	   int maxaggrlen;
1636 	   int nchgcoefs;
1637 	   int* cutinds;
1638 	   SCIP_ROW** rows;
1639 	   SCIP_VAR** vars;
1640 	   SCIP_Real* tmpcoefs;
1641 	   SCIP_Real* cutcoefs;
1642 	   SCIP_Real cutrhs;
1643 	   SCIP_Real cutefficacy;
1644 	
1645 	   if( computeViolation(row) < sepadata->minviol )
1646 	      return SCIP_OKAY;
1647 	
1648 	   rows = SCIPgetLPRows(scip);
1649 	   nvars = SCIPgetNVars(scip);
1650 	   vars = SCIPgetVars(scip);
1651 	
1652 	   maxaggrlen = MAXAGGRLEN(SCIPgetNLPCols(scip));
1653 	
1654 	   /* right hand side must be odd, otherwise no cut can be generated */
1655 	   assert(row->rhs == 1);
1656 	
1657 	   /* perform the summation of the rows defined by the mod 2 row*/
1658 	   SCIP_CALL( SCIPallocCleanBufferArray(scip, &tmpcoefs, nvars) );
1659 	   SCIP_CALL( SCIPallocBufferArray(scip, &cutinds,  nvars) );
1660 	   SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, nvars) );
1661 	
1662 	   /* the right hand side of the zerohalf cut will be rounded down by 0.5
1663 	    * thus we can instead subtract 0.5 directly
1664 	    */
1665 	   cutrhs = -0.5;
1666 	   cutnnz = 0;
1667 	   cutrank = 0;
1668 	   cutislocal = FALSE;
1669 	
1670 	   /* compute the aggregation of the rows with weight 0.5 */
1671 	   for( i = 0; i < row->nrowinds; ++i )
1672 	   {
1673 	      switch( row->rowinds[i].type )
1674 	      {
1675 	         case ORIG_RHS:
1676 	            addOrigRow(scip, tmpcoefs, &cutrhs, cutinds, &cutnnz, &cutrank, &cutislocal, rows[row->rowinds[i].index], 1);
1677 	            break;
1678 	         case ORIG_LHS:
1679 	            addOrigRow(scip, tmpcoefs, &cutrhs, cutinds, &cutnnz, &cutrank, &cutislocal, rows[row->rowinds[i].index], -1);
1680 	            break;
1681 	         case TRANSROW: {
1682 	            TRANSINTROW* introw = &mod2matrix->transintrows[row->rowinds[i].index];
1683 	            SCIPdebugMsg(scip, "using transformed row %i of length %i with slack %f and rhs %f for cut\n", row->rowinds[i].index, introw->len, introw->slack, introw->rhs);
1684 	            addTransRow(tmpcoefs, &cutrhs, cutinds, &cutnnz, &cutrank, &cutislocal, introw);
1685 	            break;
1686 	         }
1687 	         default:
1688 	            SCIPABORT();
1689 	      }
1690 	   }
1691 	
1692 	   /* abort if aggregation is too long */
1693 	   if( cutnnz > maxaggrlen )
1694 	   {
1695 	      /* clean buffer array must be set to zero before jumping to the terminate label */
1696 	      for( i = 0; i < cutnnz; ++i )
1697 	      {
1698 	         int k = cutinds[i];
1699 	         tmpcoefs[k] = 0.0;
1700 	      }
1701 	      goto TERMINATE;
1702 	   }
1703 	
1704 	   /* compute the cut coefficients and update right handside due to complementation if necessary */
1705 	   for( i = 0; i < cutnnz; )
1706 	   {
1707 	      int k = cutinds[i];
1708 	      SCIP_Real coef = tmpcoefs[k];
1709 	      SCIP_Real floorcoef = SCIPfeasFloor(scip, coef);
1710 	      tmpcoefs[k] = 0.0;
1711 	
1712 	      /* only check complementation if the coefficient was rounded down */
1713 	      if( REALABS(coef - floorcoef) > 0.1 )
1714 	      {
1715 	         SCIP_Real lb;
1716 	         SCIP_Real ub;
1717 	         SCIP_Bool loclb;
1718 	         SCIP_Bool locub;
1719 	         SCIP_Real primsol;
1720 	         SCIP_Bool useub;
1721 	
1722 	         /* complement with closest bound */
1723 	         primsol = SCIPgetSolVal(scip, sol, vars[k]);
1724 	         lb = SCIPvarGetLbGlobal(vars[k]);
1725 	         ub = SCIPvarGetUbGlobal(vars[k]);
1726 	         loclb = FALSE;
1727 	         locub = FALSE;
1728 	
1729 	         /* use local bounds if better */
1730 	         if( allowlocal )
1731 	         {
1732 	            if( SCIPisGT(scip, SCIPvarGetLbLocal(vars[k]), lb) )
1733 	            {
1734 	               loclb = TRUE;
1735 	               lb = SCIPvarGetLbLocal(vars[k]);
1736 	            }
1737 	
1738 	            if( SCIPisLT(scip, SCIPvarGetUbLocal(vars[k]), ub) )
1739 	            {
1740 	               locub = TRUE;
1741 	               ub = SCIPvarGetUbLocal(vars[k]);
1742 	            }
1743 	         }
1744 	
1745 	         if( SCIPisInfinity(scip, ub) ) /* if there is no ub, use lb */
1746 	            useub = FALSE;
1747 	         else if( SCIPisInfinity(scip, -lb) ) /* if there is no lb, use ub */
1748 	            useub = TRUE;
1749 	         else if( SCIPisLT(scip, primsol, (1.0 - BOUNDSWITCH) * lb + BOUNDSWITCH * ub) )
1750 	            useub = FALSE;
1751 	         else
1752 	            useub = TRUE;
1753 	
1754 	         if( useub )
1755 	         {
1756 	            /* set local flag if local bound was used */
1757 	            if( locub )
1758 	               cutislocal = TRUE;
1759 	
1760 	            /* upper bound was used so floor was the wrong direction to round, coefficient must be ceiled instead */
1761 	            floorcoef += 1.0;
1762 	
1763 	            assert(SCIPisFeasEQ(scip, floorcoef - coef, 0.5));
1764 	
1765 	            /* add delta of complementing then rounding by 0.5 and complementing back to the right hand side */
1766 	            cutrhs += 0.5 * ub;
1767 	         }
1768 	         else
1769 	         {
1770 	            /* set local flag if local bound was used */
1771 	            if( loclb )
1772 	               cutislocal = TRUE;
1773 	
1774 	            assert(SCIPisFeasEQ(scip, coef - floorcoef, 0.5));
1775 	
1776 	            /* add delta of complementing then rounding by 0.5 and complementing back to the right hand side */
1777 	            cutrhs -= 0.5 * lb;
1778 	         }
1779 	      }
1780 	
1781 	      /* make coefficient exactly integral */
1782 	      assert(SCIPisFeasIntegral(scip, floorcoef));
1783 	      floorcoef = SCIPfeasRound(scip, floorcoef);
1784 	
1785 	      /* if coefficient is zero remove entry, otherwise set to floorcoef */
1786 	      if( floorcoef == 0.0 )
1787 	      {
1788 	         --cutnnz;
1789 	         cutinds[i] = cutinds[cutnnz];
1790 	      }
1791 	      else
1792 	      {
1793 	         cutcoefs[i] = floorcoef;
1794 	         ++i;
1795 	      }
1796 	   }
1797 	
1798 	   /* make right hand side exactly integral */
1799 	   assert(SCIPisFeasIntegral(scip, cutrhs));
1800 	   cutrhs = SCIPfeasRound(scip, cutrhs);
1801 	
1802 	   if( ! SCIPcutsTightenCoefficients(scip, cutislocal, cutcoefs, &cutrhs, cutinds, &cutnnz, &nchgcoefs) )
1803 	   {
1804 	      /* calculate efficacy */
1805 	      cutefficacy = calcEfficacy(scip, sol, cutcoefs, cutrhs, cutinds, cutnnz);
1806 	
1807 	      if( SCIPisEfficacious(scip, cutefficacy) )
1808 	      {
1809 	         SCIP_ROW* cut;
1810 	         char cutname[SCIP_MAXSTRLEN];
1811 	         int v;
1812 	
1813 	         /* increase rank by 1 */
1814 	         cutrank += 1;
1815 	
1816 	         assert(allowlocal || !cutislocal);
1817 	
1818 	         /* create the cut */
1819 	         (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "zerohalf%" SCIP_LONGINT_FORMAT "_x%d", SCIPgetNLPs(scip), row->index);
1820 	
1821 	         SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), cutrhs, cutislocal, FALSE, sepadata->dynamiccuts) );
1822 	
1823 	         SCIProwChgRank(cut, cutrank);
1824 	
1825 	         /* cache the row extension and only flush them if the cut gets added */
1826 	         SCIP_CALL( SCIPcacheRowExtensions(scip, cut) );
1827 	
1828 	         /* collect all non-zero coefficients */
1829 	         for( v = 0; v < cutnnz; ++v )
1830 	         {
1831 	            SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cutinds[v]], cutcoefs[v]) );
1832 	         }
1833 	
1834 	         /* flush all changes before adding the cut */
1835 	         SCIP_CALL( SCIPflushRowExtensions(scip, cut) );
1836 	
1837 	         if( SCIPisCutNew(scip, cut) )
1838 	         {
1839 	            int pos = sepadata->ncuts++;
1840 	
1841 	            if( sepadata->ncuts > sepadata->cutssize )
1842 	            {
1843 	               int newsize = SCIPcalcMemGrowSize(scip, sepadata->ncuts);
1844 	               SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &sepadata->cuts, sepadata->cutssize, newsize) );
1845 	               sepadata->cutssize = newsize;
1846 	            }
1847 	
1848 	            sepadata->cuts[pos] = cut;
1849 	         }
1850 	         else
1851 	         {
1852 	            /* release the row */
1853 	            SCIP_CALL( SCIPreleaseRow(scip, &cut) );
1854 	         }
1855 	      }
1856 	   }
1857 	
1858 	  TERMINATE:
1859 	   SCIPfreeBufferArray(scip, &cutcoefs);
1860 	   SCIPfreeBufferArray(scip, &cutinds);
1861 	   SCIPfreeCleanBufferArray(scip, &tmpcoefs);
1862 	
1863 	   return SCIP_OKAY;
1864 	}
1865 	
1866 	
1867 	/** remove rows that are (a) zero (b) identical to other rows (keep the one with smallest slack) (c) have slack greater
1868 	 * than 1 (d) for zero rows with 1 as rhs and slack less than 1, we can directly generate a cut and remove the row (Lemma 4)
1869 	 */
1870 	static
1871 	SCIP_RETCODE mod2matrixPreprocessRows(
1872 	   SCIP*                 scip,               /**< scip data structure */
1873 	   SCIP_SOL*             sol,                /**< solution to separate, or NULL for LP solution */
1874 	   MOD2_MATRIX*          mod2matrix,         /**< the mod 2 matrix */
1875 	   SCIP_SEPA*            sepa,               /**< the zerohalf separator */
1876 	   SCIP_SEPADATA*        sepadata,           /**< data of the zerohalf separator */
1877 	   SCIP_Bool             allowlocal          /**< should local cuts be allowed */
1878 	   )
1879 	{
1880 	   int i;
1881 	   SCIP_HASHTABLE* rowtable;
1882 	
1883 	   SCIP_CALL( SCIPhashtableCreate(&rowtable, SCIPblkmem(scip), mod2matrix->nrows,
1884 	                                  SCIPhashGetKeyStandard, rowsEqual, rowGetSignature, NULL) );
1885 	
1886 	   for( i = 0; i < mod2matrix->nrows; )
1887 	   {
1888 	      MOD2_ROW* row = mod2matrix->rows[i];
1889 	      row->pos = i;
1890 	
1891 	      checkRow(row);
1892 	
1893 	      assert(row->nnonzcols == 0 || row->nonzcols != NULL);
1894 	
1895 	      if( (row->nnonzcols == 0 && row->rhs == 0) || computeMaxViolation(row) < sepadata->minviol )
1896 	      { /* (a) and (c) */
1897 	         sepadata->nreductions += row->nnonzcols;
1898 	         SCIP_CALL( mod2matrixRemoveRow(scip, mod2matrix, row) );
1899 	      }
1900 	      else if( row->nnonzcols > 0 )
1901 	      { /* (b) */
1902 	         MOD2_ROW* identicalrow;
1903 	         identicalrow = (MOD2_ROW*)SCIPhashtableRetrieve(rowtable, (void*)row);
1904 	         if( identicalrow != NULL )
1905 	         {
1906 	            assert(identicalrow != row);
1907 	            assert(identicalrow->nnonzcols == 0 || identicalrow->nonzcols != NULL);
1908 	
1909 	            checkRow(identicalrow);
1910 	
1911 	            /* row is identical to other row; only keep the one with smaller slack */
1912 	            if( identicalrow->slack <= row->slack )
1913 	            {
1914 	               SCIP_CALL( mod2matrixRemoveRow(scip, mod2matrix, row) );
1915 	            }
1916 	            else
1917 	            {
1918 	               assert(SCIPhashtableExists(rowtable, (void*)identicalrow));
1919 	
1920 	               SCIP_CALL( SCIPhashtableRemove(rowtable, (void*)identicalrow) );
1921 	               assert(!SCIPhashtableExists(rowtable, (void*)identicalrow));
1922 	
1923 	               SCIP_CALL( SCIPhashtableInsert(rowtable, (void*)row) );
1924 	
1925 	               SCIPswapPointers((void**) &mod2matrix->rows[row->pos], (void**) &mod2matrix->rows[identicalrow->pos]);
1926 	               SCIPswapInts(&row->pos, &identicalrow->pos);
1927 	
1928 	               assert(mod2matrix->rows[row->pos] == row && mod2matrix->rows[identicalrow->pos] == identicalrow);
1929 	               assert(identicalrow->pos == i);
1930 	               assert(row->pos < i);
1931 	
1932 	               SCIP_CALL( mod2matrixRemoveRow(scip, mod2matrix, identicalrow) );
1933 	            }
1934 	         }
1935 	         else
1936 	         {
1937 	            SCIP_CALL( SCIPhashtableInsert(rowtable, (void*)row) );
1938 	            ++i;
1939 	         }
1940 	      }
1941 	      else
1942 	      {
1943 	         /* (d) */
1944 	         assert(row->nnonzcols == 0 && row->rhs == 1 && SCIPisLT(scip, row->slack, 1.0));
1945 	
1946 	         SCIP_CALL( generateZerohalfCut(scip, sol, mod2matrix, sepa, sepadata, allowlocal, row) );
1947 	
1948 	         if( sepadata->infeasible )
1949 	            goto TERMINATE;
1950 	
1951 	         SCIP_CALL( mod2matrixRemoveRow(scip, mod2matrix, row) );
1952 	         ++i;
1953 	      }
1954 	   }
1955 	TERMINATE:
1956 	   SCIPhashtableFree(&rowtable);
1957 	
1958 	   return SCIP_OKAY;
1959 	}
1960 	
1961 	/** add a mod2 row to another one */
1962 	static
1963 	SCIP_RETCODE mod2rowAddRow(
1964 	   SCIP*                 scip,               /**< scip data structure */
1965 	   BMS_BLKMEM*           blkmem,             /**< block memory shell */
1966 	   MOD2_MATRIX*          mod2matrix,         /**< mod 2 matrix */
1967 	   MOD2_ROW*             row,                /**< mod 2 row */
1968 	   MOD2_ROW*             rowtoadd            /**< mod 2 row that is added to the other mod 2 row */
1969 	   )
1970 	{
1971 	   SCIP_Shortbool* contained;
1972 	   int i;
1973 	   int j;
1974 	   int k;
1975 	   int nnewentries;
1976 	   int nlprows;
1977 	   MOD2_COL** newnonzcols;
1978 	   SCIP_Real newslack;
1979 	
1980 	   checkRow(row);
1981 	   checkRow(rowtoadd);
1982 	
1983 	   assert(row->nnonzcols == 0 || row->nonzcols != NULL);
1984 	   assert(rowtoadd->nnonzcols == 0 || rowtoadd->nonzcols != NULL);
1985 	
1986 	   nlprows = SCIPgetNLPRows(scip);
1987 	   row->rhs ^= rowtoadd->rhs;
1988 	
1989 	   newslack = row->slack + rowtoadd->slack;
1990 	   blkmem = SCIPblkmem(scip);
1991 	
1992 	   if( SCIPisZero(scip, row->slack) && !SCIPisZero(scip, newslack) )
1993 	      --mod2matrix->nzeroslackrows;
1994 	
1995 	   row->slack = newslack;
1996 	
1997 	   {
1998 	      /* the maximum index return by the UNIQUE_INDEX macro is 3 times
1999 	       * the maximum index value in the ROWINDEX struct. The index value could
2000 	       * be the lp position of an original row or the index of a transformed row.
2001 	       * Hence we need to allocate 3 times the maximum of these two possible
2002 	       * index types.
2003 	       */
2004 	      int allocsize = 3 * MAX(nlprows, mod2matrix->ntransintrows);
2005 	      SCIP_CALL( SCIPallocCleanBufferArray(scip, &contained, allocsize) );
2006 	   }
2007 	
2008 	   /* remember entries that are in the row to add */
2009 	   for( i = 0; i < rowtoadd->nrowinds; ++i )
2010 	   {
2011 	      contained[UNIQUE_INDEX(rowtoadd->rowinds[i])] = 1;
2012 	   }
2013 	
2014 	   /* remove the entries that are in both rows from the row (1 + 1 = 0 (mod 2)) */
2015 	   nnewentries = rowtoadd->nrowinds;
2016 	   for( i = 0; i < row->nrowinds; )
2017 	   {
2018 	      if( contained[UNIQUE_INDEX(row->rowinds[i])] )
2019 	      {
2020 	         --nnewentries;
2021 	         contained[UNIQUE_INDEX(row->rowinds[i])] = 0;
2022 	         --row->nrowinds;
2023 	         row->rowinds[i] = row->rowinds[row->nrowinds];
2024 	      }
2025 	      else
2026 	      {
2027 	         ++i;
2028 	      }
2029 	   }
2030 	
2031 	   SCIP_CALL( SCIPensureBlockMemoryArray(scip, &row->rowinds, &row->rowindssize, row->nrowinds + nnewentries) );
2032 	
2033 	   /* add remaining entries of row to add */
2034 	   for ( i = 0; i < rowtoadd->nrowinds; ++i )
2035 	   {
2036 	      if( contained[UNIQUE_INDEX(rowtoadd->rowinds[i])] )
2037 	      {
2038 	         contained[UNIQUE_INDEX(rowtoadd->rowinds[i])] = 0;
2039 	         row->rowinds[row->nrowinds++] = rowtoadd->rowinds[i];
2040 	      }
2041 	   }
2042 	
2043 	   SCIPfreeCleanBufferArray(scip, &contained);
2044 	
2045 	   SCIP_CALL( SCIPallocBufferArray(scip, &newnonzcols, row->nnonzcols + rowtoadd->nnonzcols) );
2046 	
2047 	   i = 0;
2048 	   j = 0;
2049 	   k = 0;
2050 	   row->maxsolval = 0.0;
2051 	
2052 	   /* since columns are sorted we can merge them */
2053 	   while( i < row->nnonzcols && j < rowtoadd->nnonzcols )
2054 	   {
2055 	      if( row->nonzcols[i] == rowtoadd->nonzcols[j] )
2056 	      {
2057 	         SCIP_CALL( mod2colUnlinkRow(row->nonzcols[i], row) );
2058 	         ++i;
2059 	         ++j;
2060 	      }
2061 	      else if( row->nonzcols[i]->index < rowtoadd->nonzcols[j]->index )
2062 	      {
2063 	         row->maxsolval = MAX(row->maxsolval, row->nonzcols[i]->solval);
2064 	         newnonzcols[k++] = row->nonzcols[i++];
2065 	      }
2066 	      else
2067 	      {
2068 	         SCIP_CALL( mod2colLinkRow(blkmem, rowtoadd->nonzcols[j], row) );
2069 	         newnonzcols[k++] = rowtoadd->nonzcols[j++];
2070 	      }
2071 	   }
2072 	
2073 	   while( i < row->nnonzcols )
2074 	   {
2075 	      row->maxsolval = MAX(row->maxsolval, row->nonzcols[i]->solval);
2076 	      newnonzcols[k++] = row->nonzcols[i++];
2077 	   }
2078 	
2079 	   while( j <  rowtoadd->nnonzcols )
2080 	   {
2081 	      SCIP_CALL( mod2colLinkRow(blkmem, rowtoadd->nonzcols[j], row) );
2082 	      newnonzcols[k++] = rowtoadd->nonzcols[j++];
2083 	   }
2084 	
2085 	   row->nnonzcols = k;
2086 	   SCIP_CALL( SCIPensureBlockMemoryArray(scip, &row->nonzcols, &row->nonzcolssize, row->nnonzcols) );
2087 	   BMScopyMemoryArray(row->nonzcols, newnonzcols, row->nnonzcols);
2088 	
2089 	   SCIPfreeBufferArray(scip, &newnonzcols);
2090 	
2091 	   assert(row->nnonzcols == 0 || row->nonzcols != NULL);
2092 	   checkRow(row);
2093 	   checkRow(rowtoadd);
2094 	
2095 	   return SCIP_OKAY;
2096 	}
2097 	
2098 	/* --------------------------------------------------------------------------------------------------------------------
2099 	 * callback methods of separator
2100 	 * -------------------------------------------------------------------------------------------------------------------- */
2101 	
2102 	/** copy method for separator plugins (called when SCIP copies plugins) */
2103 	static
2104 	SCIP_DECL_SEPACOPY(sepaCopyZerohalf)
2105 	{  /*lint --e{715}*/
2106 	   assert(scip != NULL);
2107 	   assert(sepa != NULL);
2108 	   assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
2109 	
2110 	   /* call inclusion method of constraint handler */
2111 	   SCIP_CALL( SCIPincludeSepaZerohalf(scip) );
2112 	
2113 	   return SCIP_OKAY;
2114 	}
2115 	
2116 	/** destructor of separator to free user data (called when SCIP is exiting) */
2117 	static
2118 	SCIP_DECL_SEPAFREE(sepaFreeZerohalf)
2119 	{
2120 	   SCIP_SEPADATA* sepadata;
2121 	
2122 	   assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
2123 	
2124 	   /* free separator data */
2125 	   sepadata = SCIPsepaGetData(sepa);
2126 	   assert(sepadata != NULL);
2127 	
2128 	   SCIPfreeBlockMemory(scip, &sepadata);
2129 	   SCIPsepaSetData(sepa, NULL);
2130 	
2131 	   return SCIP_OKAY;
2132 	}
2133 	
2134 	static
2135 	SCIP_DECL_SEPAINITSOL(sepaInitsolZerohalf)
2136 	{
2137 	   SCIP_SEPADATA* sepadata;
2138 	
2139 	   assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
2140 	
2141 	   /* allocate random generator */
2142 	   sepadata = SCIPsepaGetData(sepa);
2143 	   assert(sepadata != NULL);
2144 	
2145 	   assert(sepadata->randnumgen == NULL);
2146 	   SCIP_CALL( SCIPcreateRandom(scip, &sepadata->randnumgen, (unsigned int)sepadata->initseed, TRUE) );
2147 	
2148 	   return SCIP_OKAY;
2149 	}
2150 	
2151 	static
2152 	SCIP_DECL_SEPAEXITSOL(sepaExitsolZerohalf)
2153 	{
2154 	   SCIP_SEPADATA* sepadata;
2155 	
2156 	   assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
2157 	
2158 	   /* free random generator */
2159 	   sepadata = SCIPsepaGetData(sepa);
2160 	   assert(sepadata != NULL);
2161 	
2162 	   SCIPfreeRandom(scip, &sepadata->randnumgen);
2163 	
2164 	   return SCIP_OKAY;
2165 	}
2166 	
2167 	/** perform the zerohalf cut separation */
2168 	static
2169 	SCIP_RETCODE doSeparation(
2170 	   SCIP*                 scip,
2171 	   SCIP_SEPA*            sepa,
2172 	   SCIP_SOL*             sol,
2173 	   SCIP_RESULT*          result,
2174 	   SCIP_Bool             allowlocal,
2175 	   int                   depth               /* current depth */
2176 	   )
2177 	{
2178 	   int i;
2179 	   int k;
2180 	   int maxsepacuts;
2181 	   SCIP_Real maxslack;
2182 	   SCIP_SEPADATA* sepadata;
2183 	   MOD2_MATRIX mod2matrix;
2184 	   MOD2_ROW** nonzrows;
2185 	
2186 	   assert(result != NULL);
2187 	   assert(sepa != NULL);
2188 	
2189 	   sepadata = SCIPsepaGetData(sepa);
2190 	   assert(sepadata != NULL);
2191 	
2192 	   {
2193 	      int ncalls = SCIPsepaGetNCallsAtNode(sepa);
2194 	
2195 	      /* only call the zerohalf cut separator a given number of times at each node */
2196 	      if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
2197 	         || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
2198 	         return SCIP_OKAY;
2199 	
2200 	      maxsepacuts = depth == 0 ? sepadata->maxsepacutsroot : sepadata->maxsepacuts;
2201 	      maxslack = depth == 0 ? sepadata->maxslackroot : sepadata->maxslack;
2202 	      maxslack += 2 * SCIPfeastol(scip);
2203 	   }
2204 	
2205 	   *result = SCIP_DIDNOTFIND;
2206 	
2207 	   SCIP_CALL( SCIPaggrRowCreate(scip, &sepadata->aggrrow) );
2208 	   sepadata->ncuts = 0;
2209 	   sepadata->cutssize = 0;
2210 	   sepadata->cuts = NULL;
2211 	   sepadata->infeasible = FALSE;
2212 	
2213 	   SCIP_CALL( buildMod2Matrix(scip, sol, sepadata, SCIPblkmem(scip), &mod2matrix, allowlocal, maxslack) );
2214 	
2215 	   SCIPdebugMsg(scip, "built mod2 matrix (%i rows, %i cols)\n", mod2matrix.nrows, mod2matrix.ncols);
2216 	
2217 	   SCIP_CALL( SCIPallocBufferArray(scip, &nonzrows, mod2matrix.nrows) );
2218 	
2219 	   for( k = 0; k < MAXREDUCTIONROUNDS; ++k )
2220 	   {
2221 	      int ncancel;
2222 	
2223 	      sepadata->nreductions = 0;
2224 	
2225 	      assert(mod2matrix.nzeroslackrows <= mod2matrix.nrows);
2226 	      SCIP_CALL( mod2matrixPreprocessRows(scip, sol, &mod2matrix, sepa, sepadata, allowlocal) );
2227 	      assert(mod2matrix.nzeroslackrows <= mod2matrix.nrows);
2228 	
2229 	      SCIPdebugMsg(scip, "preprocessed rows (%i rows, %i cols, %i cuts) \n", mod2matrix.nrows, mod2matrix.ncols,
2230 	                   sepadata->ncuts);
2231 	
2232 	      if( mod2matrix.nrows == 0 )
2233 	         break;
2234 	
2235 	      if( sepadata->ncuts >= sepadata->maxcutcands )
2236 	      {
2237 	         SCIPdebugMsg(scip, "enough cuts, stopping (%i rows, %i cols)\n", mod2matrix.nrows, mod2matrix.ncols);
2238 	         break;
2239 	      }
2240 	
2241 	      SCIP_CALL( mod2matrixPreprocessColumns(scip, &mod2matrix, sepadata) );
2242 	
2243 	      SCIPdebugMsg(scip, "preprocessed columns (%i rows, %i cols)\n", mod2matrix.nrows, mod2matrix.ncols);
2244 	
2245 	      ncancel = mod2matrix.nrows;
2246 	      if( ncancel > 100 )
2247 	      {
2248 	         ncancel = 100;
2249 	         SCIPselectPtr((void**) mod2matrix.rows, compareRowSlack, ncancel, mod2matrix.nrows);
2250 	      }
2251 	
2252 	      SCIPsortPtr((void**) mod2matrix.rows, compareRowSlack, ncancel);
2253 	
2254 	      if( mod2matrix.ncols == 0 )
2255 	         break;
2256 	
2257 	      assert(mod2matrix.nzeroslackrows <= mod2matrix.nrows);
2258 	
2259 	      /* apply Prop5 */
2260 	      for( i = 0; i < ncancel; ++i )
2261 	      {
2262 	         int j;
2263 	         MOD2_COL* col = NULL;
2264 	         MOD2_ROW* row = mod2matrix.rows[i];
2265 	
2266 	         if( SCIPisPositive(scip, row->slack) || row->nnonzcols == 0 )
2267 	            continue;
2268 	
2269 	         SCIPdebugMsg(scip, "processing row %i/%i (%i/%i cuts)\n", i, mod2matrix.nrows, sepadata->ncuts, sepadata->maxcutcands);
2270 	
2271 	         for( j = 0; j < row->nnonzcols; ++j )
2272 	         {
2273 	            if( row->nonzcols[j]->solval == row->maxsolval ) /*lint !e777*/
2274 	            {
2275 	               col = row->nonzcols[j];
2276 	               break;
2277 	            }
2278 	         }
2279 	
2280 	         assert( col != NULL );
2281 	
2282 	         {
2283 	            int nslots;
2284 	            int nnonzrows;
2285 	            MOD2_ROW** rows;
2286 	
2287 	            ++sepadata->nreductions;
2288 	
2289 	            nnonzrows = 0;
2290 	            /* cppcheck-suppress nullPointer */
2291 	            nslots = SCIPhashsetGetNSlots(col->nonzrows);
2292 	            /* cppcheck-suppress nullPointer */
2293 	            rows = (MOD2_ROW**) SCIPhashsetGetSlots(col->nonzrows);
2294 	
2295 	            for( j = 0; j < nslots; ++j )
2296 	            {
2297 	               if( rows[j] != NULL && rows[j] != row )
2298 	                  nonzrows[nnonzrows++] = rows[j];
2299 	            }
2300 	
2301 	            for( j = 0; j < nnonzrows; ++j )
2302 	            {
2303 	               SCIP_CALL( mod2rowAddRow(scip, SCIPblkmem(scip), &mod2matrix, nonzrows[j], row) );
2304 	            }
2305 	
2306 	            /* cppcheck-suppress nullPointer */
2307 	            row->slack = col->solval;
2308 	            --mod2matrix.nzeroslackrows;
2309 	
2310 	            mod2matrixRemoveCol(scip, &mod2matrix, col);
2311 	         }
2312 	      }
2313 	
2314 	      SCIPdebugMsg(scip, "applied proposition five (%i rows, %i cols)\n", mod2matrix.nrows, mod2matrix.ncols);
2315 	
2316 	      if( sepadata->nreductions == 0 )
2317 	      {
2318 	         SCIPdebugMsg(scip, "no change, stopping (%i rows, %i cols)\n", mod2matrix.nrows, mod2matrix.ncols);
2319 	         break;
2320 	      }
2321 	   }
2322 	
2323 	   for( i = 0; i < mod2matrix.nrows && sepadata->ncuts < sepadata->maxcutcands; ++i )
2324 	   {
2325 	      MOD2_ROW* row = mod2matrix.rows[i];
2326 	
2327 	      if( computeMaxViolation(row) < sepadata->minviol )
2328 	         break;
2329 	
2330 	      if( row->rhs == 0 )
2331 	         continue;
2332 	
2333 	      SCIP_CALL( generateZerohalfCut(scip, sol, &mod2matrix, sepa, sepadata, allowlocal, row) );
2334 	   }
2335 	
2336 	   SCIPdebugMsg(scip, "total number of cuts found: %i\n", sepadata->ncuts);
2337 	
2338 	   /* If cuts where found we apply a filtering procedure using the scores and the orthogonalities,
2339 	    * similar to the sepastore. We only add the cuts that make it through this process and discard
2340 	    * the rest.
2341 	    */
2342 	   if( sepadata->ncuts > 0  )
2343 	   {
2344 	      int nselectedcuts;
2345 	
2346 	      SCIP_CALL( SCIPselectCutsHybrid(scip, sepadata->cuts, NULL, sepadata->randnumgen, sepadata->goodscore, sepadata->badscore,
2347 	            sepadata->goodmaxparall, sepadata->maxparall, sepadata->dircutoffdistweight, sepadata->efficacyweight, sepadata->objparalweight, 0.0,
2348 	            sepadata->ncuts, 0, maxsepacuts, &nselectedcuts) );
2349 	
2350 	      for( i = 0; i < sepadata->ncuts; ++i )
2351 	      {
2352 	         if( i < nselectedcuts )
2353 	         {
2354 	            /* if selected, add global cuts to the pool and local cuts to the sepastore */
2355 	            if( SCIProwIsLocal(sepadata->cuts[i]) )
2356 	            {
2357 	               SCIP_CALL( SCIPaddRow(scip, sepadata->cuts[i], FALSE, &sepadata->infeasible) );
2358 	            }
2359 	            else
2360 	            {
2361 	               SCIP_CALL( SCIPaddPoolCut(scip, sepadata->cuts[i]) );
2362 	            }
2363 	         }
2364 	
2365 	         /* release current cut */
2366 	         SCIP_CALL( SCIPreleaseRow(scip, &sepadata->cuts[i]) );
2367 	      }
2368 	
2369 	      SCIPfreeBlockMemoryArray(scip, &sepadata->cuts, sepadata->cutssize);
2370 	
2371 	      if( sepadata->infeasible )
2372 	         *result = SCIP_CUTOFF;
2373 	      else
2374 	         *result = SCIP_SEPARATED;
2375 	   }
2376 	
2377 	   SCIPfreeBufferArray(scip, &nonzrows);
2378 	   SCIPaggrRowFree(scip, &sepadata->aggrrow);
2379 	
2380 	   destroyMod2Matrix(scip, &mod2matrix);
2381 	
2382 	   return SCIP_OKAY;
2383 	}
2384 	
2385 	/** LP solution separation method of separator */
2386 	static
2387 	SCIP_DECL_SEPAEXECLP(sepaExeclpZerohalf)
2388 	{
2389 	   assert(result != NULL);
2390 	   assert(sepa != NULL);
2391 	   assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
2392 	
2393 	   *result = SCIP_DIDNOTRUN;
2394 	
2395 	   /* only call separator, if we are not close to terminating */
2396 	   if( SCIPisStopped(scip) )
2397 	      return SCIP_OKAY;
2398 	
2399 	   /* only call separator, if an optimal LP solution is at hand */
2400 	   if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
2401 	      return SCIP_OKAY;
2402 	
2403 	   /* only call separator, if there are fractional variables */
2404 	   if( SCIPgetNLPBranchCands(scip) == 0 )
2405 	      return SCIP_OKAY;
2406 	
2407 	   SCIP_CALL( doSeparation(scip, sepa, NULL, result, allowlocal, depth) );
2408 	
2409 	   return SCIP_OKAY;
2410 	}
2411 	
2412 	/** custom solution separation method of separator */
2413 	static
2414 	SCIP_DECL_SEPAEXECSOL(sepaExecsolZerohalf)
2415 	{
2416 	   assert(result != NULL);
2417 	   assert(sepa != NULL);
2418 	   assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
2419 	
2420 	   *result = SCIP_DIDNOTRUN;
2421 	
2422 	   /* only call separator, if we are not close to terminating */
2423 	   if( SCIPisStopped(scip) )
2424 	      return SCIP_OKAY;
2425 	
2426 	   SCIP_CALL( doSeparation(scip, sepa, sol, result, allowlocal, depth) );
2427 	
2428 	   return SCIP_OKAY;
2429 	}
2430 	
2431 	/** creates the zerohalf separator and includes it in SCIP */
2432 	SCIP_RETCODE SCIPincludeSepaZerohalf(
2433 	   SCIP*                 scip                /**< SCIP data structure */
2434 	   )
2435 	{
2436 	   SCIP_SEPADATA* sepadata;
2437 	   SCIP_SEPA* sepa;
2438 	
2439 	   /* create zerohalf separator data */
2440 	   SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) );
2441 	   BMSclearMemory(sepadata);
2442 	
2443 	   /* include separator */
2444 	   SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST,
2445 	                                   SEPA_USESSUBSCIP, SEPA_DELAY, sepaExeclpZerohalf, sepaExecsolZerohalf, sepadata) );
2446 	
2447 	   assert(sepa != NULL);
2448 	
2449 	   /* set non-NULL pointers to callback methods */
2450 	   SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyZerohalf) );
2451 	   SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeZerohalf) );
2452 	   SCIP_CALL( SCIPsetSepaInitsol(scip, sepa, sepaInitsolZerohalf) );
2453 	   SCIP_CALL( SCIPsetSepaExitsol(scip, sepa, sepaExitsolZerohalf) );
2454 	
2455 	   /* add zerohalf separator parameters */
2456 	   SCIP_CALL( SCIPaddIntParam(scip,
2457 	         "separating/" SEPA_NAME "/maxrounds",
2458 	         "maximal number of zerohalf separation rounds per node (-1: unlimited)",
2459 	         &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
2460 	   SCIP_CALL( SCIPaddIntParam(scip,
2461 	         "separating/" SEPA_NAME "/maxroundsroot",
2462 	         "maximal number of zerohalf separation rounds in the root node (-1: unlimited)",
2463 	         &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
2464 	   SCIP_CALL( SCIPaddIntParam(scip,
2465 	         "separating/" SEPA_NAME "/maxsepacuts",
2466 	         "maximal number of zerohalf cuts separated per separation round",
2467 	         &sepadata->maxsepacuts, FALSE, DEFAULT_MAXSEPACUTS, 0, INT_MAX, NULL, NULL) );
2468 	   SCIP_CALL( SCIPaddIntParam(scip,
2469 	         "separating/" SEPA_NAME "/initseed",
2470 	         "initial seed used for random tie-breaking in cut selection",
2471 	         &sepadata->initseed, FALSE, DEFAULT_INITSEED, 0, INT_MAX, NULL, NULL) );
2472 	   SCIP_CALL( SCIPaddIntParam(scip,
2473 	         "separating/" SEPA_NAME "/maxsepacutsroot",
2474 	         "maximal number of zerohalf cuts separated per separation round in the root node",
2475 	         &sepadata->maxsepacutsroot, FALSE, DEFAULT_MAXSEPACUTSROOT, 0, INT_MAX, NULL, NULL) );
2476 	   SCIP_CALL( SCIPaddIntParam(scip,
2477 	         "separating/" SEPA_NAME "/maxcutcands",
2478 	         "maximal number of zerohalf cuts considered per separation round",
2479 	         &sepadata->maxcutcands, FALSE, DEFAULT_MAXCUTCANDS, 0, INT_MAX, NULL, NULL) );
2480 	   SCIP_CALL( SCIPaddRealParam(scip,
2481 	         "separating/" SEPA_NAME "/maxslack",
2482 	         "maximal slack of rows to be used in aggregation",
2483 	         &sepadata->maxslack, TRUE, DEFAULT_MAXSLACK, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2484 	   SCIP_CALL( SCIPaddRealParam(scip,
2485 	         "separating/" SEPA_NAME "/maxslackroot",
2486 	         "maximal slack of rows to be used in aggregation in the root node",
2487 	         &sepadata->maxslackroot, TRUE, DEFAULT_MAXSLACKROOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2488 	   SCIP_CALL( SCIPaddRealParam(scip,
2489 	         "separating/" SEPA_NAME "/goodscore",
2490 	         "threshold for score of cut relative to best score to be considered good, so that less strict filtering is applied",
2491 	         &sepadata->goodscore, TRUE, DEFAULT_GOODSCORE, 0.0, 1.0, NULL, NULL) );
2492 	   SCIP_CALL( SCIPaddRealParam(scip,
2493 	         "separating/" SEPA_NAME "/badscore",
2494 	         "threshold for score of cut relative to best score to be discarded",
2495 	         &sepadata->badscore, TRUE, DEFAULT_BADSCORE, 0.0, 1.0, NULL, NULL) );
2496 	   SCIP_CALL( SCIPaddRealParam(scip,
2497 	         "separating/" SEPA_NAME "/objparalweight",
2498 	         "weight of objective parallelism in cut score calculation",
2499 	         &sepadata->objparalweight, TRUE, DEFAULT_OBJPARALWEIGHT, 0.0, 1.0, NULL, NULL) );
2500 	   SCIP_CALL( SCIPaddRealParam(scip,
2501 	         "separating/" SEPA_NAME "/efficacyweight",
2502 	         "weight of efficacy in cut score calculation",
2503 	         &sepadata->efficacyweight, TRUE, DEFAULT_EFFICACYWEIGHT, 0.0, 1.0, NULL, NULL) );
2504 	   SCIP_CALL( SCIPaddRealParam(scip,
2505 	         "separating/" SEPA_NAME "/dircutoffdistweight",
2506 	         "weight of directed cutoff distance in cut score calculation",
2507 	         &sepadata->dircutoffdistweight, TRUE, DEFAULT_DIRCUTOFFDISTWEIGHT, 0.0, 1.0, NULL, NULL) );
2508 	   SCIP_CALL( SCIPaddRealParam(scip,
2509 	         "separating/" SEPA_NAME "/goodmaxparall",
2510 	         "maximum parallelism for good cuts",
2511 	         &sepadata->goodmaxparall, TRUE, DEFAULT_GOODMAXPARALL, 0.0, 1.0, NULL, NULL) );
2512 	   SCIP_CALL( SCIPaddRealParam(scip,
2513 	         "separating/" SEPA_NAME "/maxparall",
2514 	         "maximum parallelism for non-good cuts",
2515 	         &sepadata->maxparall, TRUE, DEFAULT_MAXPARALL, 0.0, 1.0, NULL, NULL) );
2516 	   SCIP_CALL( SCIPaddRealParam(scip,
2517 	         "separating/" SEPA_NAME "/minviol",
2518 	         "minimal violation to generate zerohalfcut for",
2519 	         &sepadata->minviol, TRUE, DEFAULT_MINVIOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2520 	   SCIP_CALL( SCIPaddBoolParam(scip,
2521 	         "separating/" SEPA_NAME "/dynamiccuts",
2522 	         "should generated cuts be removed from the LP if they are no longer tight?",
2523 	         &sepadata->dynamiccuts, FALSE, DEFAULT_DYNAMICCUTS, NULL, NULL) );
2524 	   SCIP_CALL( SCIPaddRealParam(scip,
2525 	         "separating/" SEPA_NAME "/maxrowdensity",
2526 	         "maximal density of row to be used in aggregation",
2527 	         &sepadata->maxrowdensity, TRUE, DEFAULT_MAXROWDENSITY, 0.0, 1.0, NULL, NULL) );
2528 	   SCIP_CALL( SCIPaddIntParam(scip,
2529 	         "separating/" SEPA_NAME "/densityoffset",
2530 	         "additional number of variables allowed in row on top of density",
2531 	         &sepadata->densityoffset, TRUE, DEFAULT_DENSITYOFFSET, 0, INT_MAX, NULL, NULL) );
2532 	
2533 	   return SCIP_OKAY;
2534 	}
2535