Scippy

SCIP

Solving Constraint Integer Programs

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