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