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