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