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