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