# 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 2002-2022 Zuse Institute Berlin */
7 /* */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
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 */
91 /* SCIPcalcRowIntegralScalar parameters */
92 #define MAXDNOM 1000LL
93 #define MAXSCALE 1000.0
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))
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 */
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 */
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
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
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 */
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
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  {
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 )
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 */
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);
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
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
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 */
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  {
1840
1842  {
1843  int newsize = SCIPcalcMemGrowSize(scip, sepadata->ncuts);
1846  }
1847
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 */
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) */
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
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);
1982
1983  assert(row->nnonzcols == 0 || row->nonzcols != NULL);
1985
1986  nlprows = SCIPgetNLPRows(scip);
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  {
2012  }
2013
2014  /* remove the entries that are in both rows from the row (1 + 1 = 0 (mod 2)) */
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
2034  for ( i = 0; i < rowtoadd->nrowinds; ++i )
2035  {
2037  {
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  {
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  {
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  {
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);
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)
2121
2122  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
2123
2124  /* free separator data */
2127
2129  SCIPsepaSetData(sepa, NULL);
2130
2131  return SCIP_OKAY;
2132 }
2133
2134 static
2135 SCIP_DECL_SEPAINITSOL(sepaInitsolZerohalf)
2138
2139  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
2140
2141  /* allocate random generator */
2144
2147
2148  return SCIP_OKAY;
2149 }
2150
2151 static
2152 SCIP_DECL_SEPAEXITSOL(sepaExitsolZerohalf)
2155
2156  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
2157
2158  /* free random generator */
2161
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;
2183  MOD2_MATRIX mod2matrix;
2184  MOD2_ROW** nonzrows;
2185
2186  assert(result != NULL);
2187  assert(sepa != NULL);
2188
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
2202  maxslack += 2 * SCIPfeastol(scip);
2203  }
2204
2205  *result = SCIP_DIDNOTFIND;
2206
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
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,
2231
2232  if( mod2matrix.nrows == 0 )
2233  break;
2234
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
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
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
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 */
2356  {
2358  }
2359  else
2360  {
2362  }
2363  }
2364
2365  /* release current cut */
2367  }
2368
2370
2372  *result = SCIP_CUTOFF;
2373  else
2374  *result = SCIP_SEPARATED;
2375  }
2376
2377  SCIPfreeBufferArray(scip, &nonzrows);
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 {
2437  SCIP_SEPA* sepa;
2438
2439  /* create zerohalf separator data */
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 */
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) );
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) );
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) );
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) );
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) );
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) );
2494  "threshold for score of cut relative to best score to be discarded",
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) );
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:1695
#define DEFAULT_DIRCUTOFFDISTWEIGHT
Definition: sepa_zerohalf.c:88
SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
Definition: var.c:18133
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:3807
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2496
static void mod2matrixRemoveCol(SCIP *scip, MOD2_MATRIX *mod2matrix, MOD2_COL *col)
int SCIPhashsetGetNElements(SCIP_HASHSET *hashset)
Definition: misc.c:3941
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1658
void ** SCIPhashsetGetSlots(SCIP_HASHSET *hashset)
Definition: misc.c:3957
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17919
#define SCIP_MAXSTRLEN
Definition: def.h:302
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:1695
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:17205
#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:17975
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:17219
#define DEFAULT_GOODSCORE
Definition: sepa_zerohalf.c:77
void SCIPswapPointers(void **pointer1, void **pointer2)
Definition: misc.c:10300
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:17284
#define FALSE
Definition: def.h:96
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3023
#define TRANSROW
SCIP_Bool SCIPcolIsIntegral(SCIP_COL *col)
Definition: lp.c:17064
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
Definition: misc.c:11072
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:10764
#define TRUE
Definition: def.h:95
SCIP_RETCODE SCIPhashsetCreate(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem, int size)
Definition: misc.c:3708
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:17609
SCIP_Bool SCIPhashsetExists(SCIP_HASHSET *hashset, void *element)
Definition: misc.c:3766
#define SCIP_UNUSED(x)
Definition: def.h:447
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:18123
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3210
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:3949
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2180
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:6615
#define DEFAULT_MAXROUNDSROOT
Definition: sepa_zerohalf.c:71
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
static SCIP_DECL_SEPAEXITSOL(sepaExitsolZerohalf)
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:2245
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
#define SCIP_DEFAULT_EPSILON
Definition: def.h:192
#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:17929
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:17393
TRANSINTROW * transintrows
void SCIPhashsetFree(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem)
Definition: misc.c:3739
#define BMSmoveMemoryArray(ptr, source, num)
Definition: memory.h:140
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:18185
#define SEPA_NAME
Definition: sepa_zerohalf.c:62
SCIP_Bool local
SCIP_Bool SCIProwIsIntegral(SCIP_ROW *row)
Definition: lp.c:17383
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3057
Definition: sepa.c:643
#define NULL
Definition: lpi_spx1.cpp:164
#define SCIP_Shortbool
Definition: def.h:101
#define SEPA_USESSUBSCIP
Definition: sepa_zerohalf.c:67
#define REALABS(x)
Definition: def.h:210
#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:393
#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:18143
#define SCIPhashSignature64(a)
Definition: pub_misc.h:517
#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:6638
SCIP_RETCODE SCIPhashtableRemove(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2626
#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:17294
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
Definition: var.c:18175
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:17403
MOD2_COL ** cols
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:17230
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:17240
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:93
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:1471
SCIP_RETCODE SCIPselectCutsHybrid(SCIP *scip, SCIP_ROW **cuts, SCIP_ROW **forcedcuts, SCIP_RANDNUMGEN *randnumgen, SCIP_Real goodscorefac, SCIP_Real badscorefac, SCIP_Real goodmaxparall, SCIP_Real maxparall, SCIP_Real dircutoffdistweight, SCIP_Real efficacyweight, SCIP_Real objparalweight, SCIP_Real intsupportweight, int ncuts, int nforcedcuts, int maxselectedcuts, int *nselectedcuts)
static SCIP_RETCODE mod2MatrixAddTransRow(SCIP *scip, MOD2_MATRIX *mod2matrix, SCIP_HASHMAP *origcol2col, int transrowind)
static void destroyMod2Matrix(SCIP *scip, MOD2_MATRIX *mod2matrix)
#define MAX(x, y)
Definition: tclique_def.h:92
#define DEFAULT_GOODMAXPARALL
Definition: sepa_zerohalf.c:89
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:136
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:2557
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:2138
#define BMSclearMemory(ptr)
Definition: memory.h:131
#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:17373
{0,1/2}-cuts separator
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2295
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:2000
#define SCIP_REAL_MAX
Definition: def.h:187
static SCIP_RETCODE mod2MatrixAddOrigRow(SCIP *scip, BMS_BLKMEM *blkmem, MOD2_MATRIX *mod2matrix, SCIP_HASHMAP *origcol2col, SCIP_ROW *origrow, SCIP_Real slack, ROWIND_TYPE side, int rhsmod2)
unsigned int type
int nzeroslackrows
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:17250
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1562
#define DEFAULT_MINVIOL
Definition: sepa_zerohalf.c:81
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:17034
unsigned int index
#define COLINFO_GET_MOD2COL(x)
void SCIProwChgRank(SCIP_ROW *row, int rank)
Definition: lp.c:17526
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:3749
#define SEPA_MAXBOUNDDIST
Definition: sepa_zerohalf.c:66
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1955
int SCIProwGetLPPos(SCIP_ROW *row)
Definition: lp.c:17493
static SCIP_Real computeViolation(MOD2_ROW *row)
#define SCIP_Real
Definition: def.h:186
#define SCIPfreeCleanBufferArray(scip, ptr)
Definition: scip_mem.h:146
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:703
#define DEFAULT_MAXROUNDS
Definition: sepa_zerohalf.c:70
int nrowinds
SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition: cuts.c:1663
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
Definition: var.c:18165
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:9467
SCIP_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2608
#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:17985
#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:453
SCIP_Real SCIPsumepsilon(SCIP *scip)
int nnonzcols
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3105
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:10274
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:439
#define SCIP_ALLOC(x)
Definition: def.h:404
SCIP_Longint SCIPgetNLPs(SCIP *scip)
#define SCIPABORT()
Definition: def.h:365
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:1361
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:216
static SCIP_RETCODE mod2colLinkRow(BMS_BLKMEM *blkmem, MOD2_COL *col, MOD2_ROW *row)
static SCIP_DECL_SEPAFREE(sepaFreeZerohalf)