Scippy

SCIP

Solving Constraint Integer Programs

sepa_zerohalf.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2025 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file sepa_zerohalf.c
26 * @ingroup DEFPLUGINS_SEPA
27 * @brief {0,1/2}-cuts separator
28 * @author Leona Gottwald
29 * @author Manuel Kutschka
30 * @author Kati Wolter
31 *
32 * {0,1/2}-Chvátal-Gomory cuts separator. It solves the following separation problem:
33 * Consider an integer program
34 * \f[
35 * \min \{ c^T x : Ax \leq b, x \geq 0, x \mbox{ integer} \}
36 * \f]
37 * and a fractional solution \f$x^*\f$ of its LP relaxation. Find a weightvector \f$u\f$ whose entries \f$u_i\f$ are either 0 or
38 * \f$\frac{1}{2}\f$ such that the following inequality is valid for all integral solutions and violated by \f$x^*\f$:
39 * \f[
40 * \lfloor(u^T A) x \rfloor \leq \lfloor u^T b\rfloor
41 * \f]
42 *
43 * References:
44 * - Alberto Caprara, Matteo Fischetti. {0,1/2}-Chvatal-Gomory cuts. Math. Programming, Volume 74, p221--235, 1996.
45 * - Arie M. C. A. Koster, Adrian Zymolka and Manuel Kutschka. \n
46 * Algorithms to separate {0,1/2}-Chvatal-Gomory cuts.
47 * Algorithms - ESA 2007: 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, \n
48 * Proceedings. Lecture Notes in Computer Science, Volume 4698, p. 693--704, 2007.
49 * - Arie M. C. A. Koster, Adrian Zymolka and Manuel Kutschka. \n
50 * Algorithms to separate {0,1/2}-Chvatal-Gomory cuts (Extended Version). \n
51 * ZIB Report 07-10, Zuse Institute Berlin, 2007. http://www.zib.de/Publications/Reports/ZR-07-10.pdf
52 * - Manuel Kutschka. Algorithmen zur Separierung von {0,1/2}-Schnitten. Diplomarbeit. Technische Universitaet Berlin, 2007.
53 */
54
55/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
56
57#include <string.h>
58#include "scip/sepa_zerohalf.h"
59#include "scip/scipdefplugins.h"
60#include "scip/cutsel_hybrid.h"
61
62#define SEPA_NAME "zerohalf"
63#define SEPA_DESC "{0,1/2}-cuts separator"
64#define SEPA_PRIORITY -6000
65#define SEPA_FREQ 10
66#define SEPA_MAXBOUNDDIST 1.0
67#define SEPA_USESSUBSCIP FALSE
68#define SEPA_DELAY FALSE
69
70#define DEFAULT_MAXROUNDS 5 /**< maximal number of zerohalf separation rounds per node (-1: unlimited) */
71#define DEFAULT_MAXROUNDSROOT 20 /**< maximal number of zerohalf separation rounds in the root node (-1: unlimited) */
72#define DEFAULT_MAXSEPACUTS 20 /**< maximal number of zerohalf cuts separated per separation round */
73#define DEFAULT_MAXSEPACUTSROOT 100 /**< maximal number of zerohalf cuts separated per separation round in root node */
74#define DEFAULT_MAXCUTCANDS 2000 /**< maximal number of zerohalf cuts considered per separation round */
75#define DEFAULT_MAXSLACK 0.0 /**< maximal slack of rows to be used in aggregation */
76#define DEFAULT_MAXSLACKROOT 0.0 /**< maximal slack of rows to be used in aggregation in the root node */
77#define DEFAULT_GOODSCORE 1.0 /**< threshold for score of cut relative to best score to be considered good,
78 * so that less strict filtering is applied */
79#define DEFAULT_BADSCORE 0.5 /**< threshold for score of cut relative to best score to be discarded */
80#define DEFAULT_MINVIOL 0.1 /**< minimal violation to generate zerohalfcut for */
81#define DEFAULT_DYNAMICCUTS TRUE /**< should generated cuts be removed from the LP if they are no longer tight? */
82#define DEFAULT_MAXROWDENSITY 0.05 /**< maximal density of row to be used in aggregation */
83#define DEFAULT_DENSITYOFFSET 100 /**< additional number of variables allowed in row on top of density */
84#define DEFAULT_INITSEED 0x5EED /**< default initial seed used for random tie-breaking in cut selection */
85#define DEFAULT_OBJPARALWEIGHT 0.0 /**< weight of objective parallelism in cut score calculation */
86#define DEFAULT_EFFICACYWEIGHT 1.0 /**< weight of efficacy in cut score calculation */
87#define DEFAULT_DIRCUTOFFDISTWEIGHT 0.0 /**< weight of directed cutoff distance in cut score calculation */
88#define DEFAULT_GOODMAXPARALL 0.1 /**< maximum parallelism for good cuts */
89#define DEFAULT_MAXPARALL 0.1 /**< maximum parallelism for non-good cuts */
90
91/* SCIPcalcRowIntegralScalar parameters */
92#define MAXDNOM 1000LL
93#define MAXSCALE 1000.0
94
95/* other defines */
96#define MAXREDUCTIONROUNDS 100 /**< maximum number of rounds to perform reductions on the mod 2 system */
97#define BOUNDSWITCH 0.5 /**< threshold for bound switching */
98#define MAXAGGRLEN(nvars) ((int)(0.1*(nvars)+1000))
99
100typedef struct Mod2Col MOD2_COL;
101typedef struct Mod2Row MOD2_ROW;
102typedef struct Mod2Matrix MOD2_MATRIX;
103typedef struct TransIntRow TRANSINTROW;
104typedef struct RowIndex ROWINDEX;
105
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
112
113/* macro to get a unique index from the rowindex */
114#define UNIQUE_INDEX(rowind) (3*(rowind).index + (rowind).type)
115
116struct 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 */
125struct 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 */
138struct 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 */
154struct 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 */
163struct 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 */
177struct SCIP_SepaData
178{
179 SCIP_RANDNUMGEN* randnumgen; /**< random generator for tiebreaking */
180 SCIP_AGGRROW* aggrrow; /**< aggregation row used for generating cuts */
181 SCIP_ROW** cuts; /**< generated in the current call */
182 SCIP_Real minviol; /**< minimal violation to generate zerohalfcut for */
183 SCIP_Real maxslack; /**< maximal slack of rows to be used in aggregation */
184 SCIP_Real maxslackroot; /**< maximal slack of rows to be used in aggregation in the root node */
185 SCIP_Real maxrowdensity; /**< maximal density of row to be used in aggregation */
186 SCIP_Real goodscore; /**< threshold for score of cut relative to best score to be considered good,
187 * so that less strict filtering is applied */
188 SCIP_Real badscore; /**< threshold for score of cut relative to best score to be discarded */
189 SCIP_Real objparalweight; /**< weight of objective parallelism in cut score calculation */
190 SCIP_Real efficacyweight; /**< weight of efficacy in cut score calculation */
191 SCIP_Real dircutoffdistweight;/**< weight of directed cutoff distance in cut score calculation */
192 SCIP_Real goodmaxparall; /**< maximum parallelism for good cuts */
193 SCIP_Real maxparall; /**< maximum parallelism for non-good cuts */
194 SCIP_Bool infeasible; /**< infeasibility was detected after adding a zerohalf cut */
195 SCIP_Bool dynamiccuts; /**< should generated cuts be removed from the LP if they are no longer tight? */
196 int maxrounds; /**< maximal number of zerohalf separation rounds per node (-1: unlimited) */
197 int maxroundsroot; /**< maximal number of zerohalf separation rounds in the root node (-1: unlimited) */
198 int maxsepacuts; /**< maximal number of zerohalf cuts separated per separation round */
199 int maxsepacutsroot; /**< maximal number of zerohalf cuts separated per separation round in root node */
200 int maxcutcands; /**< maximal number of zerohalf cuts considered per separation round */
201 int densityoffset; /**< additional number of variables allowed in row on top of density */
202 int initseed; /**< initial seed used for random tie-breaking in cut selection */
203 int cutssize; /**< size of cuts and cutscores arrays */
204 int ncuts; /**< number of cuts generated in the current call */
205 int nreductions; /**< number of reductions to the mod 2 system found so far */
206};
207
208
209#define COLINFO_GET_MOD2COL(x) ((MOD2_COL*) (((uintptr_t)(x)) & ~((uintptr_t)1)))
210#define COLINFO_GET_RHSOFFSET(x) ((int) (((uintptr_t)(x)) & ((uintptr_t)1)))
211#define COLINFO_CREATE(mod2col, rhsoffset) ((void*) (((uintptr_t)(mod2col)) | ((uintptr_t)(rhsoffset))))
212
213
214#ifndef NDEBUG
215static
216void 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 */
237static
238SCIP_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 */
255static
256SCIP_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 */
293static
294int 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() */
305static
306void 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 */
337static
338SCIP_RETCODE transformNonIntegralRow(
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 */
627static
628SCIP_RETCODE mod2MatrixTransformContRows(
629 SCIP* scip, /**< scip data structure */
630 SCIP_SOL* sol, /**< solution to separate, or NULL for LP solution */
631 SCIP_SEPADATA* sepadata, /**< zerohalf separator data */
632 MOD2_MATRIX* mod2matrix, /**< mod2 matrix structure */
633 SCIP_Bool allowlocal, /**< should local cuts be allowed */
634 SCIP_Real maxslack /**< maximum slack allowed for mod 2 rows */
635 )
636{
637 SCIP_ROW** rows;
638 int nrows;
639 int* intvarpos;
640 int i;
641 int maxnonzeros;
642 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
643 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &mod2matrix->transintrows, 2*nrows) );
644 mod2matrix->ntransintrows = 0;
645
646 SCIP_CALL( SCIPallocCleanBufferArray(scip, &intvarpos, SCIPgetNVars(scip)) );
647
648 maxnonzeros = (int)(SCIPgetNLPCols(scip) * sepadata->maxrowdensity) + sepadata->densityoffset;
649
650 for( i = 0; i < nrows; ++i )
651 {
652 int rowlen;
653 SCIP_Real activity;
654 SCIP_Real lhs;
655 SCIP_Real rhs;
656 SCIP_Real lhsslack;
657 SCIP_Real rhsslack;
658 SCIP_Real* rowvals;
659 SCIP_COL** rowcols;
660
661 /* skip integral rows and rows not suitable for generating cuts */
662 if( SCIProwIsModifiable(rows[i]) || SCIProwIsIntegral(rows[i]) || (SCIProwIsLocal(rows[i]) && !allowlocal) || SCIProwGetNNonz(rows[i]) > maxnonzeros )
663 continue;
664
665 lhs = SCIProwGetLhs(rows[i]) - SCIProwGetConstant(rows[i]);
666 rhs = SCIProwGetRhs(rows[i]) - SCIProwGetConstant(rows[i]);
667 activity = SCIPgetRowSolActivity(scip, rows[i], sol) - SCIProwGetConstant(rows[i]);
668
669 /* compute lhsslack: activity - lhs */
670 if( SCIPisInfinity(scip, -SCIProwGetLhs(rows[i])) )
671 lhsslack = SCIPinfinity(scip);
672 else
673 {
674 lhsslack = activity - lhs;
675 }
676
677 /* compute rhsslack: rhs - activity */
678 if( SCIPisInfinity(scip, SCIProwGetRhs(rows[i])) )
679 rhsslack = SCIPinfinity(scip);
680 else
681 rhsslack = rhs - activity;
682
683 if( rhsslack > maxslack && lhsslack > maxslack )
684 continue;
685
686 rowlen = SCIProwGetNLPNonz(rows[i]);
687 rowvals = SCIProwGetVals(rows[i]);
688 rowcols = SCIProwGetCols(rows[i]);
689
690 if( rhsslack <= maxslack )
691 {
692 SCIP_Bool success;
693 TRANSINTROW* introw = &mod2matrix->transintrows[mod2matrix->ntransintrows];
694 SCIP_CALL( transformNonIntegralRow(scip, sol, allowlocal, maxslack, 1, SCIProwIsLocal(rows[i]), SCIProwGetRank(rows[i]), \
695 rowlen, rowvals, rowcols, rhs, intvarpos, introw, &success) );
696
697 assert(success == 1 || success == 0);
698 mod2matrix->ntransintrows += (int)success;
699 }
700
701 if( lhsslack <= maxslack )
702 {
703 SCIP_Bool success;
704 TRANSINTROW* introw = &mod2matrix->transintrows[mod2matrix->ntransintrows];
705 SCIP_CALL( transformNonIntegralRow(scip, sol, allowlocal, maxslack, -1, SCIProwIsLocal(rows[i]), SCIProwGetRank(rows[i]), \
706 rowlen, rowvals, rowcols, -lhs, intvarpos, introw, &success) );
707
708 assert(success == 1 || success == 0);
709 mod2matrix->ntransintrows += (int)success;
710 }
711 }
712
713 SCIPfreeCleanBufferArray(scip, &intvarpos);
714
715 return SCIP_OKAY;
716}
717
718
719/** adds new column to the mod 2 matrix */
720static
721SCIP_RETCODE mod2MatrixAddCol(
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 */
753static
754SCIP_RETCODE mod2colLinkRow(
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 */
770static
771SCIP_RETCODE mod2colUnlinkRow(
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 */
796static
797void mod2rowUnlinkCol(
798 MOD2_ROW* row /**< mod 2 row */,
799 MOD2_COL* col /**< mod 2 column */
800 )
801{
802 int i;
803
804 assert(row->nnonzcols == 0 || row->nonzcols != NULL);
805
806 SCIP_UNUSED( SCIPsortedvecFindPtr((void**) row->nonzcols, compareColIndex, col, row->nnonzcols, &i) );
807 assert(row->nonzcols[i] == col);
808
809 --row->nnonzcols;
810 BMSmoveMemoryArray(row->nonzcols + i, row->nonzcols + i + 1, row->nnonzcols - i); /*lint !e866*/
811
812 if( col->solval >= row->maxsolval )
813 {
814 row->maxsolval = 0.0;
815 for( i = 0; i < row->nnonzcols; ++i )
816 {
817 row->maxsolval = MAX(row->nonzcols[i]->solval, row->maxsolval);
818 }
819 }
820}
821
822/** adds a SCIP_ROW to the mod 2 matrix */
823static
824SCIP_RETCODE mod2MatrixAddOrigRow(
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
892 SCIP_CALL( SCIPensureBlockMemoryArray(scip, &row->nonzcols, &row->nonzcolssize, row->nnonzcols) );
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 */
908static
909SCIP_RETCODE mod2MatrixAddTransRow(
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
973 SCIP_CALL( SCIPensureBlockMemoryArray(scip, &row->nonzcols, &row->nonzcolssize, row->nnonzcols) );
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 */
989static
990void 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 */
1025static
1026SCIP_RETCODE buildMod2Matrix(
1027 SCIP* scip, /**< scip data structure */
1028 SCIP_SOL* sol, /**< solution to separate, or NULL for LP solution */
1029 SCIP_SEPADATA* sepadata, /**< zerohalf separator data */
1030 BMS_BLKMEM* blkmem, /**< block memory shell */
1031 MOD2_MATRIX* mod2matrix, /**< mod 2 matrix */
1032 SCIP_Bool allowlocal, /**< should local cuts be allowed */
1033 SCIP_Real maxslack /**< maximum slack allowed for mod 2 rows */
1034 )
1035{
1036 SCIP_VAR** vars;
1037 SCIP_ROW** rows;
1038 SCIP_COL** cols;
1039 SCIP_HASHMAP* origcol2col;
1040 int ncols;
1041 int nrows;
1042 int nintvars;
1043 int maxnonzeros;
1044 int i;
1045 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
1046 SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
1047
1048 nintvars = SCIPgetNVars(scip) - SCIPgetNContVars(scip);
1049 vars = SCIPgetVars(scip);
1050
1051 /* initialize fields */
1052 mod2matrix->cols = NULL;
1053 mod2matrix->colssize = 0;
1054 mod2matrix->ncols = 0;
1055 mod2matrix->rows = NULL;
1056 mod2matrix->rowssize = 0;
1057 mod2matrix->nrows = 0;
1058 mod2matrix->nzeroslackrows = 0;
1059
1060 SCIP_CALL( SCIPhashmapCreate(&origcol2col, SCIPblkmem(scip), 1) );
1061
1062 /* add all integral vars if they are not at their bound */
1063 for( i = 0; i < nintvars; ++i )
1064 {
1065 SCIP_Real lb;
1066 SCIP_Real ub;
1067 SCIP_Real lbsol;
1068 SCIP_Real ubsol;
1069 SCIP_Real primsol;
1070 SCIP_Bool useub;
1071
1072 primsol = SCIPgetSolVal(scip, sol, vars[i]);
1073
1074 lb = allowlocal ? SCIPvarGetLbLocal(vars[i]) : SCIPvarGetLbGlobal(vars[i]);
1075 lbsol = MAX(0.0, primsol - lb);
1076 if( SCIPisZero(scip, lbsol) )
1077 {
1078 SCIP_CALL( SCIPhashmapInsert(origcol2col, (void*) vars[i], COLINFO_CREATE(NULL, mod2(scip, lb))) ); /*lint !e571*/
1079 continue;
1080 }
1081
1082 ub = allowlocal ? SCIPvarGetUbLocal(vars[i]) : SCIPvarGetUbGlobal(vars[i]);
1083 ubsol = MAX(0.0, ub - primsol);
1084 if( SCIPisZero(scip, ubsol) )
1085 {
1086 SCIP_CALL( SCIPhashmapInsert(origcol2col, (void*) vars[i], COLINFO_CREATE(NULL, mod2(scip, ub))) ); /*lint !e571*/
1087 continue;
1088 }
1089
1090 if( SCIPisInfinity(scip, ub) ) /* if there is no ub, use lb */
1091 useub = FALSE;
1092 else if( SCIPisInfinity(scip, -lb) ) /* if there is no lb, use ub */
1093 useub = TRUE;
1094 else if( SCIPisLT(scip, primsol, (1.0 - BOUNDSWITCH) * lb + BOUNDSWITCH * ub) )
1095 useub = FALSE;
1096 else
1097 useub = TRUE;
1098
1099 if( useub )
1100 {
1101 assert(ubsol > 0.0);
1102
1103 /* coverity[var_deref_model] */
1104 SCIP_CALL( mod2MatrixAddCol(scip, mod2matrix, origcol2col, vars[i], ubsol, mod2(scip, ub)) );
1105 }
1106 else
1107 {
1108 assert(lbsol > 0.0);
1109
1110 /* coverity[var_deref_model] */
1111 SCIP_CALL( mod2MatrixAddCol(scip, mod2matrix, origcol2col, vars[i], lbsol, mod2(scip, lb)) );
1112 }
1113 }
1114
1115 maxnonzeros = (int)(SCIPgetNLPCols(scip) * sepadata->maxrowdensity) + sepadata->densityoffset;
1116
1117 /* add all integral rows using the created columns */
1118 for( i = 0; i < nrows; ++i )
1119 {
1120 SCIP_Real lhs;
1121 SCIP_Real rhs;
1122 SCIP_Real activity;
1123 SCIP_Real lhsslack;
1124 SCIP_Real rhsslack;
1125 int lhsmod2;
1126 int rhsmod2;
1127
1128 /* skip non-integral rows and rows not suitable for generating cuts */
1129 if( SCIProwIsModifiable(rows[i]) || !SCIProwIsIntegral(rows[i]) || (SCIProwIsLocal(rows[i]) && !allowlocal) || SCIProwGetNNonz(rows[i]) > maxnonzeros )
1130 continue;
1131
1132 lhsmod2 = 0;
1133 rhsmod2 = 0;
1134 activity = SCIPgetRowSolActivity(scip, rows[i], sol) - SCIProwGetConstant(rows[i]);
1135
1136 /* since row is integral we can ceil/floor the lhs/rhs after subtracting the constant */
1137 lhs = SCIPfeasCeil(scip, SCIProwGetLhs(rows[i]) - SCIProwGetConstant(rows[i]));
1138 rhs = SCIPfeasFloor(scip, SCIProwGetRhs(rows[i]) - SCIProwGetConstant(rows[i]));
1139
1140 /* compute lhsslack: activity - lhs */
1141 if( SCIPisInfinity(scip, -SCIProwGetLhs(rows[i])) )
1142 lhsslack = SCIPinfinity(scip);
1143 else
1144 {
1145 lhsslack = activity - lhs;
1146 lhsmod2 = mod2(scip, lhs);
1147 }
1148
1149 /* compute rhsslack: rhs - activity */
1150 if( SCIPisInfinity(scip, SCIProwGetRhs(rows[i])) )
1151 rhsslack = SCIPinfinity(scip);
1152 else
1153 {
1154 rhsslack = rhs - activity;
1155 rhsmod2 = mod2(scip, rhs);
1156 }
1157
1158 if( rhsslack <= maxslack && lhsslack <= maxslack )
1159 {
1160 if( lhsmod2 == rhsmod2 )
1161 {
1162 /* maxslack < 1 implies rhs - lhs = rhsslack + lhsslack < 2. Therefore lhs = rhs (mod2) can only hold if they
1163 * are equal
1164 */
1165 assert(SCIPisEQ(scip, lhs, rhs));
1166
1167 /* use rhs */
1168 /* coverity[var_deref_model] */
1169 SCIP_CALL( mod2MatrixAddOrigRow(scip, blkmem, mod2matrix, origcol2col, rows[i], rhsslack, ORIG_RHS, rhsmod2) );
1170 }
1171 else
1172 {
1173 /* use both */
1174 /* coverity[var_deref_model] */
1175 SCIP_CALL( mod2MatrixAddOrigRow(scip, blkmem, mod2matrix, origcol2col, rows[i], lhsslack, ORIG_LHS, lhsmod2) );
1176 SCIP_CALL( mod2MatrixAddOrigRow(scip, blkmem, mod2matrix, origcol2col, rows[i], rhsslack, ORIG_RHS, rhsmod2) );
1177 }
1178 }
1179 else if( rhsslack <= maxslack )
1180 {
1181 /* use rhs */
1182 /* coverity[var_deref_model] */
1183 SCIP_CALL( mod2MatrixAddOrigRow(scip, blkmem, mod2matrix, origcol2col, rows[i], rhsslack, ORIG_RHS, rhsmod2) );
1184 }
1185 else if( lhsslack <= maxslack )
1186 {
1187 /* use lhs */
1188 /* coverity[var_deref_model] */
1189 SCIP_CALL( mod2MatrixAddOrigRow(scip, blkmem, mod2matrix, origcol2col, rows[i], lhsslack, ORIG_LHS, lhsmod2) );
1190 }
1191 }
1192
1193 /* transform non-integral rows */
1194 SCIP_CALL( mod2MatrixTransformContRows(scip, sol, sepadata, mod2matrix, allowlocal, maxslack) );
1195
1196 /* add all transformed integral rows using the created columns */
1197 for( i = 0; i < mod2matrix->ntransintrows; ++i )
1198 {
1199 SCIP_CALL( mod2MatrixAddTransRow(scip, mod2matrix, origcol2col, i) );
1200 }
1201
1202 SCIPhashmapFree(&origcol2col);
1203
1204 return SCIP_OKAY;
1205}
1206
1207/* compare two mod 2 columns for equality */
1208static
1209SCIP_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
1220 if( SCIPhashsetGetNElements(col1->nonzrows) != SCIPhashsetGetNElements(col2->nonzrows) )
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 */
1235static
1236SCIP_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 */
1260static
1261SCIP_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 */
1288static
1289SCIP_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 */
1307static
1308SCIP_RETCODE mod2matrixRemoveRow(
1309 SCIP* scip, /**< scip data structure */
1310 MOD2_MATRIX* mod2matrix, /**< the mod 2 matrix */
1311 MOD2_ROW* row /**< mod 2 row */
1312 )
1313{
1314 int i;
1315 int position = row->pos;
1316
1317 checkRow(row);
1318
1319 /* update counter for zero slack rows */
1320 if( SCIPisZero(scip, row->slack) )
1321 --mod2matrix->nzeroslackrows;
1322
1323 /* remove the row from the array */
1324 --mod2matrix->nrows;
1325 mod2matrix->rows[position] = mod2matrix->rows[mod2matrix->nrows];
1326 mod2matrix->rows[position]->pos = position;
1327
1328 /* unlink columns from row */
1329 for( i = 0; i < row->nnonzcols; ++i )
1330 {
1331 SCIP_CALL( mod2colUnlinkRow(row->nonzcols[i], row) );
1332 }
1333
1334 /* free row */
1335 SCIPfreeBlockMemoryArrayNull(scip, &row->nonzcols, row->nonzcolssize);
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 */
1343static
1344void 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 position = col->pos;
1358
1359 /* remove column from arrays */
1360 --mod2matrix->ncols;
1361 mod2matrix->cols[position] = mod2matrix->cols[mod2matrix->ncols];
1362 mod2matrix->cols[position]->pos = position;
1363
1364 nslots = SCIPhashsetGetNSlots(col->nonzrows);
1365 rows = (MOD2_ROW**) SCIPhashsetGetSlots(col->nonzrows);
1366
1367 /* adjust rows of column */
1368 for( i = 0; i < nslots; ++i )
1369 {
1370 if( rows[i] != NULL )
1371 mod2rowUnlinkCol(rows[i], col);
1372 }
1373
1374 /* free column */
1375 SCIPhashsetFree(&col->nonzrows, SCIPblkmem(scip));
1376 SCIPfreeBlockMemory(scip, &col);
1377}
1378
1379/* remove columns that are (Prop3 iii) zero (Prop3 iv) identify indentical columns (Prop3 v) unit vector columns */
1380static
1381SCIP_RETCODE mod2matrixPreprocessColumns(
1382 SCIP* scip, /**< scip data structure */
1383 MOD2_MATRIX* mod2matrix, /**< mod 2 matrix */
1384 SCIP_SEPADATA* sepadata /**< zerohalf separator data */
1385 )
1386{
1387 int i;
1388 SCIP_HASHTABLE* columntable;
1389
1390 SCIP_CALL( SCIPhashtableCreate(&columntable, SCIPblkmem(scip), mod2matrix->ncols,
1391 SCIPhashGetKeyStandard, columnsEqual, columnGetSignature, NULL) );
1392
1393 for( i = 0; i < mod2matrix->ncols; )
1394 {
1395 MOD2_COL* col = mod2matrix->cols[i];
1396 int nnonzrows = SCIPhashsetGetNElements(col->nonzrows);
1397 if( nnonzrows == 0 )
1398 { /* Prop3 iii */
1399 mod2matrixRemoveCol(scip, mod2matrix, col);
1400 }
1401 else if( nnonzrows == 1 )
1402 { /* Prop3 v */
1403 MOD2_ROW* row;
1404
1405 {
1406 int j = 0;
1407 MOD2_ROW** rows;
1408 rows = (MOD2_ROW**) SCIPhashsetGetSlots(col->nonzrows);
1409 while( rows[j] == NULL )
1410 ++j;
1411
1412 row = rows[j];
1413 }
1414
1415 checkRow(row);
1416
1417 /* column is unit vector, so add its solution value to the rows slack and remove it */
1418 if( SCIPisZero(scip, row->slack) )
1419 --mod2matrix->nzeroslackrows;
1420
1421 row->slack += col->solval;
1422 assert(!SCIPisZero(scip, row->slack));
1423
1424 mod2matrixRemoveCol(scip, mod2matrix, col);
1425 ++sepadata->nreductions;
1426
1427 checkRow(row);
1428 }
1429 else
1430 {
1431 MOD2_COL* identicalcol;
1432 identicalcol = (MOD2_COL*)SCIPhashtableRetrieve(columntable, col);
1433 if( identicalcol != NULL )
1434 {
1435 assert(identicalcol != col);
1436
1437 /* column is identical to other column so add its solution value to the other one and then remove and free it */
1438 identicalcol->solval += col->solval;
1439
1440 /* also adjust the solval of the removed column so that the maxsolval of each row is properly updated */
1441 col->solval = identicalcol->solval;
1442
1443 mod2matrixRemoveCol(scip, mod2matrix, col);
1444 }
1445 else
1446 {
1447 SCIP_CALL( SCIPhashtableInsert(columntable, (void*)col) );
1448 ++i;
1449 }
1450 }
1451 }
1452
1453 SCIPhashtableFree(&columntable);
1454
1455 return SCIP_OKAY;
1456}
1457
1458#define NONZERO(x) (COPYSIGN(1e-100, (x)) + (x))
1459
1460/** add original row to aggregation with weight 0.5 */
1461static
1462void addOrigRow(
1463 SCIP* scip, /**< SCIP datastructure */
1464 SCIP_Real* tmpcoefs, /**< array to add coefficients to */
1465 SCIP_Real* cutrhs, /**< pointer to add right hand side */
1466 int* nonzeroinds, /**< array of non-zeros in the aggregation */
1467 int* nnz, /**< pointer to update number of non-zeros */
1468 int* cutrank, /**< pointer to update cut rank */
1469 SCIP_Bool* cutislocal, /**< pointer to update local flag */
1470 SCIP_ROW* row, /**< row to add */
1471 int sign /**< sign for weight, i.e. +1 to use right hand side or -1 to use left hand side */
1472 )
1473{
1474 int i;
1475 SCIP_Real weight = 0.5 * sign;
1476 SCIP_COL** rowcols;
1477 SCIP_Real* rowvals;
1478 int rowlen;
1479
1480 rowlen = SCIProwGetNNonz(row);
1481 rowcols = SCIProwGetCols(row);
1482 rowvals = SCIProwGetVals(row);
1483 for( i = 0; i < rowlen; ++i )
1484 {
1485 SCIP_Real val;
1486 int probindex;
1487
1488 probindex = SCIPcolGetVarProbindex(rowcols[i]);
1489 val = tmpcoefs[probindex];
1490 if( val == 0.0 )
1491 {
1492 nonzeroinds[(*nnz)++] = probindex;
1493 }
1494
1495 val += weight * rowvals[i];
1496 tmpcoefs[probindex] = NONZERO(val);
1497 }
1498
1499 if( sign == +1 )
1500 {
1501 *cutrhs += weight * SCIPfeasFloor(scip, SCIProwGetRhs(row) - SCIProwGetConstant(row));
1502 }
1503 else
1504 {
1505 assert(sign == -1);
1506 *cutrhs += weight * SCIPfeasCeil(scip, SCIProwGetLhs(row) - SCIProwGetConstant(row));
1507 }
1508
1509 if( SCIProwGetRank(row) > *cutrank )
1510 *cutrank = SCIProwGetRank(row);
1511 *cutislocal = *cutislocal || SCIProwIsLocal(row);
1512}
1513
1514/** add transformed integral row to aggregation with weight 0.5 */
1515static
1516void addTransRow(
1517 SCIP_Real* tmpcoefs, /**< array to add coefficients to */
1518 SCIP_Real* cutrhs, /**< pointer to add right hand side */
1519 int* nonzeroinds, /**< array of non-zeros in the aggregation */
1520 int* nnz, /**< pointer to update number of non-zeros */
1521 int* cutrank, /**< pointer to update cut rank */
1522 SCIP_Bool* cutislocal, /**< pointer to update local flag */
1523 TRANSINTROW* introw /**< transformed integral row to add to the aggregation */
1524 )
1525{
1526 int i;
1527
1528 for( i = 0; i < introw->len; ++i )
1529 {
1530 int probindex = introw->varinds[i];
1531 SCIP_Real val = tmpcoefs[probindex];
1532
1533 if( val == 0.0 )
1534 {
1535 nonzeroinds[(*nnz)++] = probindex;
1536 }
1537
1538 val += 0.5 * introw->vals[i];
1539 tmpcoefs[probindex] = NONZERO(val);
1540 }
1541
1542 *cutrhs += 0.5 * introw->rhs;
1543
1544 *cutrank = MAX(*cutrank, introw->rank);
1545 *cutislocal = *cutislocal || introw->local;
1546}
1547
1548/* calculates the cuts efficacy of cut */
1549static
1550SCIP_Real calcEfficacy(
1551 SCIP* scip, /**< SCIP data structure */
1552 SCIP_SOL* sol, /**< solution to separate, or NULL for LP solution */
1553 SCIP_Real* cutcoefs, /**< array of the non-zero coefficients in the cut */
1554 SCIP_Real cutrhs, /**< the right hand side of the cut */
1555 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
1556 int cutnnz /**< the number of non-zeros in the cut */
1557 )
1558{
1559 SCIP_VAR** vars;
1560 SCIP_Real norm;
1561 SCIP_Real activity;
1562 int i;
1563
1564 assert(scip != NULL);
1565 assert(cutcoefs != NULL);
1566 assert(cutinds != NULL);
1567
1568 norm = SCIPgetVectorEfficacyNorm(scip, cutcoefs, cutnnz);
1569 vars = SCIPgetVars(scip);
1570
1571 activity = 0.0;
1572 for( i = 0; i < cutnnz; ++i )
1573 activity += cutcoefs[i] * SCIPgetSolVal(scip, sol, vars[cutinds[i]]);
1574
1575 return (activity - cutrhs) / MAX(1e-6, norm);
1576}
1577
1578/** computes maximal violation that can be achieved for zerohalf cuts where this row particiaptes */
1579static
1580SCIP_Real computeMaxViolation(
1581 MOD2_ROW* row /**< mod 2 row */
1582 )
1583{
1584 SCIP_Real viol;
1585
1586 viol = 1.0 - row->slack;
1587 viol *= 0.5;
1588
1589 return viol;
1590}
1591
1592/** computes violation of zerohalf cut generated from given mod 2 row */
1593static
1594SCIP_Real computeViolation(
1595 MOD2_ROW* row /**< mod 2 row */
1596 )
1597{
1598 int i;
1599 SCIP_Real viol;
1600
1601 viol = 1.0 - row->slack;
1602
1603 for( i = 0; i < row->nnonzcols; ++i )
1604 {
1605 viol -= row->nonzcols[i]->solval;
1606 }
1607
1608 viol *= 0.5;
1609
1610 return viol;
1611}
1612
1613/** generate a zerohalf cut from a given mod 2 row, i.e., try if aggregations of rows of the
1614 * mod2 matrix give violated cuts
1615 */
1616static
1617SCIP_RETCODE generateZerohalfCut(
1618 SCIP* scip, /**< scip data structure */
1619 SCIP_SOL* sol, /**< solution to separate, or NULL for LP solution */
1620 MOD2_MATRIX* mod2matrix, /**< mod 2 matrix */
1621 SCIP_SEPA* sepa, /**< zerohalf separator */
1622 SCIP_SEPADATA* sepadata, /**< zerohalf separator data */
1623 SCIP_Bool allowlocal, /**< should local cuts be allowed */
1624 MOD2_ROW* row /**< mod 2 row */
1625 )
1626{
1627 SCIP_Bool cutislocal;
1628 int i;
1629 int cutnnz;
1630 int cutrank;
1631 int nvars;
1632 int maxaggrlen;
1633 int nchgcoefs;
1634 int* cutinds;
1635 SCIP_ROW** rows;
1636 SCIP_VAR** vars;
1637 SCIP_Real* tmpcoefs;
1638 SCIP_Real* cutcoefs;
1639 SCIP_Real cutrhs;
1640 SCIP_Real cutefficacy;
1641
1642 if( computeViolation(row) < sepadata->minviol )
1643 return SCIP_OKAY;
1644
1645 rows = SCIPgetLPRows(scip);
1646 nvars = SCIPgetNVars(scip);
1647 vars = SCIPgetVars(scip);
1648
1649 maxaggrlen = MAXAGGRLEN(SCIPgetNLPCols(scip));
1650
1651 /* right hand side must be odd, otherwise no cut can be generated */
1652 assert(row->rhs == 1);
1653
1654 /* perform the summation of the rows defined by the mod 2 row*/
1655 SCIP_CALL( SCIPallocCleanBufferArray(scip, &tmpcoefs, nvars) );
1656 SCIP_CALL( SCIPallocBufferArray(scip, &cutinds, nvars) );
1657 SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, nvars) );
1658
1659 /* the right hand side of the zerohalf cut will be rounded down by 0.5
1660 * thus we can instead subtract 0.5 directly
1661 */
1662 cutrhs = -0.5;
1663 cutnnz = 0;
1664 cutrank = 0;
1665 cutislocal = FALSE;
1666
1667 /* compute the aggregation of the rows with weight 0.5 */
1668 for( i = 0; i < row->nrowinds; ++i )
1669 {
1670 switch( row->rowinds[i].type )
1671 {
1672 case ORIG_RHS:
1673 addOrigRow(scip, tmpcoefs, &cutrhs, cutinds, &cutnnz, &cutrank, &cutislocal, rows[row->rowinds[i].index], 1);
1674 break;
1675 case ORIG_LHS:
1676 addOrigRow(scip, tmpcoefs, &cutrhs, cutinds, &cutnnz, &cutrank, &cutislocal, rows[row->rowinds[i].index], -1);
1677 break;
1678 case TRANSROW: {
1679 TRANSINTROW* introw = &mod2matrix->transintrows[row->rowinds[i].index];
1680 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);
1681 addTransRow(tmpcoefs, &cutrhs, cutinds, &cutnnz, &cutrank, &cutislocal, introw);
1682 break;
1683 }
1684 default:
1685 SCIPABORT();
1686 }
1687 }
1688
1689 /* abort if aggregation is too long */
1690 if( cutnnz > maxaggrlen )
1691 {
1692 /* clean buffer array must be set to zero before jumping to the terminate label */
1693 for( i = 0; i < cutnnz; ++i )
1694 {
1695 int k = cutinds[i];
1696 tmpcoefs[k] = 0.0;
1697 }
1698 goto TERMINATE;
1699 }
1700
1701 /* compute the cut coefficients and update right handside due to complementation if necessary */
1702 for( i = 0; i < cutnnz; )
1703 {
1704 int k = cutinds[i];
1705 SCIP_Real coef = tmpcoefs[k];
1706 SCIP_Real floorcoef = SCIPfeasFloor(scip, coef);
1707 tmpcoefs[k] = 0.0;
1708
1709 /* only check complementation if the coefficient was rounded down */
1710 if( REALABS(coef - floorcoef) > 0.1 )
1711 {
1712 SCIP_Real lb;
1713 SCIP_Real ub;
1714 SCIP_Bool loclb;
1715 SCIP_Bool locub;
1716 SCIP_Real primsol;
1717 SCIP_Bool useub;
1718
1719 /* complement with closest bound */
1720 primsol = SCIPgetSolVal(scip, sol, vars[k]);
1721 lb = SCIPvarGetLbGlobal(vars[k]);
1722 ub = SCIPvarGetUbGlobal(vars[k]);
1723 loclb = FALSE;
1724 locub = FALSE;
1725
1726 /* use local bounds if better */
1727 if( allowlocal )
1728 {
1729 if( SCIPisGT(scip, SCIPvarGetLbLocal(vars[k]), lb) )
1730 {
1731 loclb = TRUE;
1732 lb = SCIPvarGetLbLocal(vars[k]);
1733 }
1734
1735 if( SCIPisLT(scip, SCIPvarGetUbLocal(vars[k]), ub) )
1736 {
1737 locub = TRUE;
1738 ub = SCIPvarGetUbLocal(vars[k]);
1739 }
1740 }
1741
1742 if( SCIPisInfinity(scip, ub) ) /* if there is no ub, use lb */
1743 useub = FALSE;
1744 else if( SCIPisInfinity(scip, -lb) ) /* if there is no lb, use ub */
1745 useub = TRUE;
1746 else if( SCIPisLT(scip, primsol, (1.0 - BOUNDSWITCH) * lb + BOUNDSWITCH * ub) )
1747 useub = FALSE;
1748 else
1749 useub = TRUE;
1750
1751 if( useub )
1752 {
1753 /* set local flag if local bound was used */
1754 if( locub )
1755 cutislocal = TRUE;
1756
1757 /* upper bound was used so floor was the wrong direction to round, coefficient must be ceiled instead */
1758 floorcoef += 1.0;
1759
1760 assert(SCIPisFeasEQ(scip, floorcoef - coef, 0.5));
1761
1762 /* add delta of complementing then rounding by 0.5 and complementing back to the right hand side */
1763 cutrhs += 0.5 * ub;
1764 }
1765 else
1766 {
1767 /* set local flag if local bound was used */
1768 if( loclb )
1769 cutislocal = TRUE;
1770
1771 assert(SCIPisFeasEQ(scip, coef - floorcoef, 0.5));
1772
1773 /* add delta of complementing then rounding by 0.5 and complementing back to the right hand side */
1774 cutrhs -= 0.5 * lb;
1775 }
1776 }
1777
1778 /* make coefficient exactly integral */
1779 assert(SCIPisFeasIntegral(scip, floorcoef));
1780 floorcoef = SCIPfeasRound(scip, floorcoef);
1781
1782 /* if coefficient is zero remove entry, otherwise set to floorcoef */
1783 if( floorcoef == 0.0 )
1784 {
1785 --cutnnz;
1786 cutinds[i] = cutinds[cutnnz];
1787 }
1788 else
1789 {
1790 cutcoefs[i] = floorcoef;
1791 ++i;
1792 }
1793 }
1794
1795 /* make right hand side exactly integral */
1796 assert(SCIPisFeasIntegral(scip, cutrhs));
1797 cutrhs = SCIPfeasRound(scip, cutrhs);
1798
1799 if( ! SCIPcutsTightenCoefficients(scip, cutislocal, cutcoefs, &cutrhs, cutinds, &cutnnz, &nchgcoefs) )
1800 {
1801 /* calculate efficacy */
1802 cutefficacy = calcEfficacy(scip, sol, cutcoefs, cutrhs, cutinds, cutnnz);
1803
1804 if( SCIPisEfficacious(scip, cutefficacy) )
1805 {
1806 SCIP_ROW* cut;
1807 char cutname[SCIP_MAXSTRLEN];
1808 int v;
1809
1810 /* increase rank by 1 */
1811 cutrank += 1;
1812
1813 assert(allowlocal || !cutislocal);
1814
1815 /* create the cut */
1816 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "zerohalf%" SCIP_LONGINT_FORMAT "_x%d", SCIPgetNLPs(scip), row->index);
1817
1818 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), cutrhs, cutislocal, FALSE, sepadata->dynamiccuts) );
1819
1820 SCIProwChgRank(cut, cutrank);
1821
1822 /* cache the row extension and only flush them if the cut gets added */
1823 SCIP_CALL( SCIPcacheRowExtensions(scip, cut) );
1824
1825 /* collect all non-zero coefficients */
1826 for( v = 0; v < cutnnz; ++v )
1827 {
1828 SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cutinds[v]], cutcoefs[v]) );
1829 }
1830
1831 /* flush all changes before adding the cut */
1832 SCIP_CALL( SCIPflushRowExtensions(scip, cut) );
1833
1834 if( SCIPisCutNew(scip, cut) )
1835 {
1836 int pos = sepadata->ncuts++;
1837
1838 if( sepadata->ncuts > sepadata->cutssize )
1839 {
1840 int newsize = SCIPcalcMemGrowSize(scip, sepadata->ncuts);
1841 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &sepadata->cuts, sepadata->cutssize, newsize) );
1842 sepadata->cutssize = newsize;
1843 }
1844
1845 sepadata->cuts[pos] = cut;
1846 }
1847 else
1848 {
1849 /* release the row */
1850 SCIP_CALL( SCIPreleaseRow(scip, &cut) );
1851 }
1852 }
1853 }
1854
1855 TERMINATE:
1856 SCIPfreeBufferArray(scip, &cutcoefs);
1857 SCIPfreeBufferArray(scip, &cutinds);
1858 SCIPfreeCleanBufferArray(scip, &tmpcoefs);
1859
1860 return SCIP_OKAY;
1861}
1862
1863
1864/** remove rows that are (a) zero (b) identical to other rows (keep the one with smallest slack) (c) have slack greater
1865 * 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)
1866 */
1867static
1868SCIP_RETCODE mod2matrixPreprocessRows(
1869 SCIP* scip, /**< scip data structure */
1870 SCIP_SOL* sol, /**< solution to separate, or NULL for LP solution */
1871 MOD2_MATRIX* mod2matrix, /**< the mod 2 matrix */
1872 SCIP_SEPA* sepa, /**< the zerohalf separator */
1873 SCIP_SEPADATA* sepadata, /**< data of the zerohalf separator */
1874 SCIP_Bool allowlocal /**< should local cuts be allowed */
1875 )
1876{
1877 int i;
1878 SCIP_HASHTABLE* rowtable;
1879
1880 SCIP_CALL( SCIPhashtableCreate(&rowtable, SCIPblkmem(scip), mod2matrix->nrows,
1881 SCIPhashGetKeyStandard, rowsEqual, rowGetSignature, NULL) );
1882
1883 for( i = 0; i < mod2matrix->nrows; )
1884 {
1885 MOD2_ROW* row = mod2matrix->rows[i];
1886 row->pos = i;
1887
1888 checkRow(row);
1889
1890 assert(row->nnonzcols == 0 || row->nonzcols != NULL);
1891
1892 if( (row->nnonzcols == 0 && row->rhs == 0) || computeMaxViolation(row) < sepadata->minviol )
1893 { /* (a) and (c) */
1894 sepadata->nreductions += row->nnonzcols;
1895 SCIP_CALL( mod2matrixRemoveRow(scip, mod2matrix, row) );
1896 }
1897 else if( row->nnonzcols > 0 )
1898 { /* (b) */
1899 MOD2_ROW* identicalrow;
1900 identicalrow = (MOD2_ROW*)SCIPhashtableRetrieve(rowtable, (void*)row);
1901 if( identicalrow != NULL )
1902 {
1903 assert(identicalrow != row);
1904 assert(identicalrow->nnonzcols == 0 || identicalrow->nonzcols != NULL);
1905
1906 checkRow(identicalrow);
1907
1908 /* row is identical to other row; only keep the one with smaller slack */
1909 if( identicalrow->slack <= row->slack )
1910 {
1911 SCIP_CALL( mod2matrixRemoveRow(scip, mod2matrix, row) );
1912 }
1913 else
1914 {
1915 assert(SCIPhashtableExists(rowtable, (void*)identicalrow));
1916
1917 SCIP_CALL( SCIPhashtableRemove(rowtable, (void*)identicalrow) );
1918 assert(!SCIPhashtableExists(rowtable, (void*)identicalrow));
1919
1920 SCIP_CALL( SCIPhashtableInsert(rowtable, (void*)row) );
1921
1922 SCIPswapPointers((void**) &mod2matrix->rows[row->pos], (void**) &mod2matrix->rows[identicalrow->pos]);
1923 SCIPswapInts(&row->pos, &identicalrow->pos);
1924
1925 assert(mod2matrix->rows[row->pos] == row && mod2matrix->rows[identicalrow->pos] == identicalrow);
1926 assert(identicalrow->pos == i);
1927 assert(row->pos < i);
1928
1929 SCIP_CALL( mod2matrixRemoveRow(scip, mod2matrix, identicalrow) );
1930 }
1931 }
1932 else
1933 {
1934 SCIP_CALL( SCIPhashtableInsert(rowtable, (void*)row) );
1935 ++i;
1936 }
1937 }
1938 else
1939 {
1940 /* (d) */
1941 assert(row->nnonzcols == 0 && row->rhs == 1 && SCIPisLT(scip, row->slack, 1.0));
1942
1943 SCIP_CALL( generateZerohalfCut(scip, sol, mod2matrix, sepa, sepadata, allowlocal, row) );
1944
1945 if( sepadata->infeasible )
1946 goto TERMINATE;
1947
1948 SCIP_CALL( mod2matrixRemoveRow(scip, mod2matrix, row) );
1949 ++i;
1950 }
1951 }
1952TERMINATE:
1953 SCIPhashtableFree(&rowtable);
1954
1955 return SCIP_OKAY;
1956}
1957
1958/** add a mod2 row to another one */
1959static
1960SCIP_RETCODE mod2rowAddRow(
1961 SCIP* scip, /**< scip data structure */
1962 BMS_BLKMEM* blkmem, /**< block memory shell */
1963 MOD2_MATRIX* mod2matrix, /**< mod 2 matrix */
1964 MOD2_ROW* row, /**< mod 2 row */
1965 MOD2_ROW* rowtoadd /**< mod 2 row that is added to the other mod 2 row */
1966 )
1967{
1968 SCIP_Shortbool* contained;
1969 int i;
1970 int j;
1971 int k;
1972 int nnewentries;
1973 int nlprows;
1974 MOD2_COL** newnonzcols;
1975 SCIP_Real newslack;
1976
1977 checkRow(row);
1978 checkRow(rowtoadd);
1979
1980 assert(row->nnonzcols == 0 || row->nonzcols != NULL);
1981 assert(rowtoadd->nnonzcols == 0 || rowtoadd->nonzcols != NULL);
1982
1983 nlprows = SCIPgetNLPRows(scip);
1984 row->rhs ^= rowtoadd->rhs;
1985
1986 newslack = row->slack + rowtoadd->slack;
1987 blkmem = SCIPblkmem(scip);
1988
1989 if( SCIPisZero(scip, row->slack) && !SCIPisZero(scip, newslack) )
1990 --mod2matrix->nzeroslackrows;
1991
1992 row->slack = newslack;
1993
1994 {
1995 /* the maximum index return by the UNIQUE_INDEX macro is 3 times
1996 * the maximum index value in the ROWINDEX struct. The index value could
1997 * be the lp position of an original row or the index of a transformed row.
1998 * Hence we need to allocate 3 times the maximum of these two possible
1999 * index types.
2000 */
2001 int allocsize = 3 * MAX(nlprows, mod2matrix->ntransintrows);
2002 SCIP_CALL( SCIPallocCleanBufferArray(scip, &contained, allocsize) );
2003 }
2004
2005 /* remember entries that are in the row to add */
2006 for( i = 0; i < rowtoadd->nrowinds; ++i )
2007 {
2008 contained[UNIQUE_INDEX(rowtoadd->rowinds[i])] = 1;
2009 }
2010
2011 /* remove the entries that are in both rows from the row (1 + 1 = 0 (mod 2)) */
2012 nnewentries = rowtoadd->nrowinds;
2013 for( i = 0; i < row->nrowinds; )
2014 {
2015 if( contained[UNIQUE_INDEX(row->rowinds[i])] )
2016 {
2017 --nnewentries;
2018 contained[UNIQUE_INDEX(row->rowinds[i])] = 0;
2019 --row->nrowinds;
2020 row->rowinds[i] = row->rowinds[row->nrowinds];
2021 }
2022 else
2023 {
2024 ++i;
2025 }
2026 }
2027
2028 SCIP_CALL( SCIPensureBlockMemoryArray(scip, &row->rowinds, &row->rowindssize, row->nrowinds + nnewentries) );
2029
2030 /* add remaining entries of row to add */
2031 for ( i = 0; i < rowtoadd->nrowinds; ++i )
2032 {
2033 if( contained[UNIQUE_INDEX(rowtoadd->rowinds[i])] )
2034 {
2035 contained[UNIQUE_INDEX(rowtoadd->rowinds[i])] = 0;
2036 row->rowinds[row->nrowinds++] = rowtoadd->rowinds[i];
2037 }
2038 }
2039
2040 SCIPfreeCleanBufferArray(scip, &contained);
2041
2042 SCIP_CALL( SCIPallocBufferArray(scip, &newnonzcols, row->nnonzcols + rowtoadd->nnonzcols) );
2043
2044 i = 0;
2045 j = 0;
2046 k = 0;
2047 row->maxsolval = 0.0;
2048
2049 /* since columns are sorted we can merge them */
2050 while( i < row->nnonzcols && j < rowtoadd->nnonzcols )
2051 {
2052 if( row->nonzcols[i] == rowtoadd->nonzcols[j] )
2053 {
2054 SCIP_CALL( mod2colUnlinkRow(row->nonzcols[i], row) );
2055 ++i;
2056 ++j;
2057 }
2058 else if( row->nonzcols[i]->index < rowtoadd->nonzcols[j]->index )
2059 {
2060 row->maxsolval = MAX(row->maxsolval, row->nonzcols[i]->solval);
2061 newnonzcols[k++] = row->nonzcols[i++];
2062 }
2063 else
2064 {
2065 SCIP_CALL( mod2colLinkRow(blkmem, rowtoadd->nonzcols[j], row) );
2066 newnonzcols[k++] = rowtoadd->nonzcols[j++];
2067 }
2068 }
2069
2070 while( i < row->nnonzcols )
2071 {
2072 row->maxsolval = MAX(row->maxsolval, row->nonzcols[i]->solval);
2073 newnonzcols[k++] = row->nonzcols[i++];
2074 }
2075
2076 while( j < rowtoadd->nnonzcols )
2077 {
2078 SCIP_CALL( mod2colLinkRow(blkmem, rowtoadd->nonzcols[j], row) );
2079 newnonzcols[k++] = rowtoadd->nonzcols[j++];
2080 }
2081
2082 row->nnonzcols = k;
2083 SCIP_CALL( SCIPensureBlockMemoryArray(scip, &row->nonzcols, &row->nonzcolssize, row->nnonzcols) );
2084 BMScopyMemoryArray(row->nonzcols, newnonzcols, row->nnonzcols);
2085
2086 SCIPfreeBufferArray(scip, &newnonzcols);
2087
2088 assert(row->nnonzcols == 0 || row->nonzcols != NULL);
2089 checkRow(row);
2090 checkRow(rowtoadd);
2091
2092 return SCIP_OKAY;
2093}
2094
2095/* --------------------------------------------------------------------------------------------------------------------
2096 * callback methods of separator
2097 * -------------------------------------------------------------------------------------------------------------------- */
2098
2099/** copy method for separator plugins (called when SCIP copies plugins) */
2100static
2101SCIP_DECL_SEPACOPY(sepaCopyZerohalf)
2102{ /*lint --e{715}*/
2103 assert(scip != NULL);
2104 assert(sepa != NULL);
2105 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
2106
2107 /* call inclusion method of constraint handler */
2108 SCIP_CALL( SCIPincludeSepaZerohalf(scip) );
2109
2110 return SCIP_OKAY;
2111}
2112
2113/** destructor of separator to free user data (called when SCIP is exiting) */
2114static
2115SCIP_DECL_SEPAFREE(sepaFreeZerohalf)
2116{
2117 SCIP_SEPADATA* sepadata;
2118
2119 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
2120
2121 /* free separator data */
2122 sepadata = SCIPsepaGetData(sepa);
2123 assert(sepadata != NULL);
2124
2125 SCIPfreeBlockMemory(scip, &sepadata);
2126 SCIPsepaSetData(sepa, NULL);
2127
2128 return SCIP_OKAY;
2129}
2130
2131static
2132SCIP_DECL_SEPAINITSOL(sepaInitsolZerohalf)
2133{
2134 SCIP_SEPADATA* sepadata;
2135
2136 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
2137
2138 /* allocate random generator */
2139 sepadata = SCIPsepaGetData(sepa);
2140 assert(sepadata != NULL);
2141
2142 assert(sepadata->randnumgen == NULL);
2143 SCIP_CALL( SCIPcreateRandom(scip, &sepadata->randnumgen, (unsigned int)sepadata->initseed, TRUE) );
2144
2145 return SCIP_OKAY;
2146}
2147
2148static
2149SCIP_DECL_SEPAEXITSOL(sepaExitsolZerohalf)
2150{
2151 SCIP_SEPADATA* sepadata;
2152
2153 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
2154
2155 /* free random generator */
2156 sepadata = SCIPsepaGetData(sepa);
2157 assert(sepadata != NULL);
2158
2159 SCIPfreeRandom(scip, &sepadata->randnumgen);
2160
2161 return SCIP_OKAY;
2162}
2163
2164/** perform the zerohalf cut separation */
2165static
2166SCIP_RETCODE doSeparation(
2167 SCIP* scip,
2168 SCIP_SEPA* sepa,
2169 SCIP_SOL* sol,
2170 SCIP_RESULT* result,
2171 SCIP_Bool allowlocal,
2172 int depth /* current depth */
2173 )
2174{
2175 int i;
2176 int k;
2177 int maxsepacuts;
2178 SCIP_Real maxslack;
2179 SCIP_SEPADATA* sepadata;
2180 MOD2_MATRIX mod2matrix;
2181 MOD2_ROW** nonzrows;
2182
2183 assert(result != NULL);
2184 assert(sepa != NULL);
2185
2186 sepadata = SCIPsepaGetData(sepa);
2187 assert(sepadata != NULL);
2188
2189 {
2190 int ncalls = SCIPsepaGetNCallsAtNode(sepa);
2191
2192 /* only call the zerohalf cut separator a given number of times at each node */
2193 if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
2194 || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
2195 return SCIP_OKAY;
2196
2197 maxsepacuts = depth == 0 ? sepadata->maxsepacutsroot : sepadata->maxsepacuts;
2198 maxslack = depth == 0 ? sepadata->maxslackroot : sepadata->maxslack;
2199 maxslack += 2 * SCIPfeastol(scip);
2200 }
2201
2202 *result = SCIP_DIDNOTFIND;
2203
2204 SCIP_CALL( SCIPaggrRowCreate(scip, &sepadata->aggrrow) );
2205 sepadata->ncuts = 0;
2206 sepadata->cutssize = 0;
2207 sepadata->cuts = NULL;
2208 sepadata->infeasible = FALSE;
2209
2210 SCIP_CALL( buildMod2Matrix(scip, sol, sepadata, SCIPblkmem(scip), &mod2matrix, allowlocal, maxslack) );
2211
2212 SCIPdebugMsg(scip, "built mod2 matrix (%i rows, %i cols)\n", mod2matrix.nrows, mod2matrix.ncols);
2213
2214 SCIP_CALL( SCIPallocBufferArray(scip, &nonzrows, mod2matrix.nrows) );
2215
2216 for( k = 0; k < MAXREDUCTIONROUNDS; ++k )
2217 {
2218 int ncancel;
2219
2220 sepadata->nreductions = 0;
2221
2222 assert(mod2matrix.nzeroslackrows <= mod2matrix.nrows);
2223 SCIP_CALL( mod2matrixPreprocessRows(scip, sol, &mod2matrix, sepa, sepadata, allowlocal) );
2224 assert(mod2matrix.nzeroslackrows <= mod2matrix.nrows);
2225
2226 SCIPdebugMsg(scip, "preprocessed rows (%i rows, %i cols, %i cuts) \n", mod2matrix.nrows, mod2matrix.ncols,
2227 sepadata->ncuts);
2228
2229 if( mod2matrix.nrows == 0 )
2230 break;
2231
2232 if( sepadata->ncuts >= sepadata->maxcutcands )
2233 {
2234 SCIPdebugMsg(scip, "enough cuts, stopping (%i rows, %i cols)\n", mod2matrix.nrows, mod2matrix.ncols);
2235 break;
2236 }
2237
2238 SCIP_CALL( mod2matrixPreprocessColumns(scip, &mod2matrix, sepadata) );
2239
2240 SCIPdebugMsg(scip, "preprocessed columns (%i rows, %i cols)\n", mod2matrix.nrows, mod2matrix.ncols);
2241
2242 ncancel = mod2matrix.nrows;
2243 if( ncancel > 100 )
2244 {
2245 ncancel = 100;
2246 SCIPselectPtr((void**) mod2matrix.rows, compareRowSlack, ncancel, mod2matrix.nrows);
2247 }
2248
2249 SCIPsortPtr((void**) mod2matrix.rows, compareRowSlack, ncancel);
2250
2251 if( mod2matrix.ncols == 0 )
2252 break;
2253
2254 assert(mod2matrix.nzeroslackrows <= mod2matrix.nrows);
2255
2256 /* apply Prop5 */
2257 for( i = 0; i < ncancel; ++i )
2258 {
2259 int j;
2260 MOD2_COL* col = NULL;
2261 MOD2_ROW* row = mod2matrix.rows[i];
2262
2263 if( SCIPisPositive(scip, row->slack) || row->nnonzcols == 0 )
2264 continue;
2265
2266 SCIPdebugMsg(scip, "processing row %i/%i (%i/%i cuts)\n", i, mod2matrix.nrows, sepadata->ncuts, sepadata->maxcutcands);
2267
2268 for( j = 0; j < row->nnonzcols; ++j )
2269 {
2270 if( row->nonzcols[j]->solval == row->maxsolval ) /*lint !e777*/
2271 {
2272 col = row->nonzcols[j];
2273 break;
2274 }
2275 }
2276
2277 assert( col != NULL );
2278
2279 {
2280 int nslots;
2281 int nnonzrows;
2282 MOD2_ROW** rows;
2283
2284 ++sepadata->nreductions;
2285
2286 nnonzrows = 0;
2287 nslots = SCIPhashsetGetNSlots(col->nonzrows);
2288 rows = (MOD2_ROW**) SCIPhashsetGetSlots(col->nonzrows);
2289
2290 for( j = 0; j < nslots; ++j )
2291 {
2292 if( rows[j] != NULL && rows[j] != row )
2293 nonzrows[nnonzrows++] = rows[j];
2294 }
2295
2296 for( j = 0; j < nnonzrows; ++j )
2297 {
2298 SCIP_CALL( mod2rowAddRow(scip, SCIPblkmem(scip), &mod2matrix, nonzrows[j], row) );
2299 }
2300
2301 row->slack = col->solval;
2302 --mod2matrix.nzeroslackrows;
2303
2304 mod2matrixRemoveCol(scip, &mod2matrix, col);
2305 }
2306 }
2307
2308 SCIPdebugMsg(scip, "applied proposition five (%i rows, %i cols)\n", mod2matrix.nrows, mod2matrix.ncols);
2309
2310 if( sepadata->nreductions == 0 )
2311 {
2312 SCIPdebugMsg(scip, "no change, stopping (%i rows, %i cols)\n", mod2matrix.nrows, mod2matrix.ncols);
2313 break;
2314 }
2315 }
2316
2317 for( i = 0; i < mod2matrix.nrows && sepadata->ncuts < sepadata->maxcutcands; ++i )
2318 {
2319 MOD2_ROW* row = mod2matrix.rows[i];
2320
2321 if( computeMaxViolation(row) < sepadata->minviol )
2322 break;
2323
2324 if( row->rhs == 0 )
2325 continue;
2326
2327 SCIP_CALL( generateZerohalfCut(scip, sol, &mod2matrix, sepa, sepadata, allowlocal, row) );
2328 }
2329
2330 SCIPdebugMsg(scip, "total number of cuts found: %i\n", sepadata->ncuts);
2331
2332 /* If cuts where found we apply a filtering procedure using the scores and the orthogonalities,
2333 * similar to the sepastore. We only add the cuts that make it through this process and discard
2334 * the rest.
2335 */
2336 if( sepadata->ncuts > 0 )
2337 {
2338 int nselectedcuts;
2339
2340 SCIP_CALL( SCIPselectCutsHybrid(scip, sepadata->cuts, NULL, sepadata->randnumgen, sepadata->goodscore, sepadata->badscore,
2341 sepadata->goodmaxparall, sepadata->maxparall, sepadata->dircutoffdistweight, sepadata->efficacyweight, sepadata->objparalweight, 0.0,
2342 sepadata->ncuts, 0, maxsepacuts, &nselectedcuts) );
2343
2344 for( i = 0; i < sepadata->ncuts; ++i )
2345 {
2346 if( i < nselectedcuts )
2347 {
2348 /* if selected, add global cuts to the pool and local cuts to the sepastore */
2349 if( SCIProwIsLocal(sepadata->cuts[i]) )
2350 {
2351 SCIP_CALL( SCIPaddRow(scip, sepadata->cuts[i], FALSE, &sepadata->infeasible) );
2352 }
2353 else
2354 {
2355 SCIP_CALL( SCIPaddPoolCut(scip, sepadata->cuts[i]) );
2356 }
2357 }
2358
2359 /* release current cut */
2360 SCIP_CALL( SCIPreleaseRow(scip, &sepadata->cuts[i]) );
2361 }
2362
2363 SCIPfreeBlockMemoryArray(scip, &sepadata->cuts, sepadata->cutssize);
2364
2365 if( sepadata->infeasible )
2366 *result = SCIP_CUTOFF;
2367 else
2368 *result = SCIP_SEPARATED;
2369 }
2370
2371 SCIPfreeBufferArray(scip, &nonzrows);
2372 SCIPaggrRowFree(scip, &sepadata->aggrrow);
2373
2374 destroyMod2Matrix(scip, &mod2matrix);
2375
2376 return SCIP_OKAY;
2377}
2378
2379/** LP solution separation method of separator */
2380static
2381SCIP_DECL_SEPAEXECLP(sepaExeclpZerohalf)
2382{
2383 assert(result != NULL);
2384 assert(sepa != NULL);
2385 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
2386
2387 *result = SCIP_DIDNOTRUN;
2388
2389 /* only call separator, if we are not close to terminating */
2390 if( SCIPisStopped(scip) )
2391 return SCIP_OKAY;
2392
2393 /* only call separator, if an optimal LP solution is at hand */
2394 if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
2395 return SCIP_OKAY;
2396
2397 /* only call separator, if there are fractional variables */
2398 if( SCIPgetNLPBranchCands(scip) == 0 )
2399 return SCIP_OKAY;
2400
2401 SCIP_CALL( doSeparation(scip, sepa, NULL, result, allowlocal, depth) );
2402
2403 return SCIP_OKAY;
2404}
2405
2406/** custom solution separation method of separator */
2407static
2408SCIP_DECL_SEPAEXECSOL(sepaExecsolZerohalf)
2409{
2410 assert(result != NULL);
2411 assert(sepa != NULL);
2412 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
2413
2414 *result = SCIP_DIDNOTRUN;
2415
2416 /* only call separator, if we are not close to terminating */
2417 if( SCIPisStopped(scip) )
2418 return SCIP_OKAY;
2419
2420 SCIP_CALL( doSeparation(scip, sepa, sol, result, allowlocal, depth) );
2421
2422 return SCIP_OKAY;
2423}
2424
2425/** creates the zerohalf separator and includes it in SCIP */
2426SCIP_RETCODE SCIPincludeSepaZerohalf(
2427 SCIP* scip /**< SCIP data structure */
2428 )
2429{
2430 SCIP_SEPADATA* sepadata;
2431 SCIP_SEPA* sepa;
2432
2433 /* create zerohalf separator data */
2434 SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) );
2435 BMSclearMemory(sepadata);
2436
2437 /* include separator */
2438 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST,
2439 SEPA_USESSUBSCIP, SEPA_DELAY, sepaExeclpZerohalf, sepaExecsolZerohalf, sepadata) );
2440
2441 assert(sepa != NULL);
2442
2443 /* set non-NULL pointers to callback methods */
2444 SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyZerohalf) );
2445 SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeZerohalf) );
2446 SCIP_CALL( SCIPsetSepaInitsol(scip, sepa, sepaInitsolZerohalf) );
2447 SCIP_CALL( SCIPsetSepaExitsol(scip, sepa, sepaExitsolZerohalf) );
2448
2449 /* add zerohalf separator parameters */
2450 SCIP_CALL( SCIPaddIntParam(scip,
2451 "separating/" SEPA_NAME "/maxrounds",
2452 "maximal number of zerohalf separation rounds per node (-1: unlimited)",
2453 &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
2454 SCIP_CALL( SCIPaddIntParam(scip,
2455 "separating/" SEPA_NAME "/maxroundsroot",
2456 "maximal number of zerohalf separation rounds in the root node (-1: unlimited)",
2457 &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
2458 SCIP_CALL( SCIPaddIntParam(scip,
2459 "separating/" SEPA_NAME "/maxsepacuts",
2460 "maximal number of zerohalf cuts separated per separation round",
2461 &sepadata->maxsepacuts, FALSE, DEFAULT_MAXSEPACUTS, 0, INT_MAX, NULL, NULL) );
2462 SCIP_CALL( SCIPaddIntParam(scip,
2463 "separating/" SEPA_NAME "/initseed",
2464 "initial seed used for random tie-breaking in cut selection",
2465 &sepadata->initseed, FALSE, DEFAULT_INITSEED, 0, INT_MAX, NULL, NULL) );
2466 SCIP_CALL( SCIPaddIntParam(scip,
2467 "separating/" SEPA_NAME "/maxsepacutsroot",
2468 "maximal number of zerohalf cuts separated per separation round in the root node",
2469 &sepadata->maxsepacutsroot, FALSE, DEFAULT_MAXSEPACUTSROOT, 0, INT_MAX, NULL, NULL) );
2470 SCIP_CALL( SCIPaddIntParam(scip,
2471 "separating/" SEPA_NAME "/maxcutcands",
2472 "maximal number of zerohalf cuts considered per separation round",
2473 &sepadata->maxcutcands, FALSE, DEFAULT_MAXCUTCANDS, 0, INT_MAX, NULL, NULL) );
2474 SCIP_CALL( SCIPaddRealParam(scip,
2475 "separating/" SEPA_NAME "/maxslack",
2476 "maximal slack of rows to be used in aggregation",
2477 &sepadata->maxslack, TRUE, DEFAULT_MAXSLACK, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2478 SCIP_CALL( SCIPaddRealParam(scip,
2479 "separating/" SEPA_NAME "/maxslackroot",
2480 "maximal slack of rows to be used in aggregation in the root node",
2481 &sepadata->maxslackroot, TRUE, DEFAULT_MAXSLACKROOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2482 SCIP_CALL( SCIPaddRealParam(scip,
2483 "separating/" SEPA_NAME "/goodscore",
2484 "threshold for score of cut relative to best score to be considered good, so that less strict filtering is applied",
2485 &sepadata->goodscore, TRUE, DEFAULT_GOODSCORE, 0.0, 1.0, NULL, NULL) );
2486 SCIP_CALL( SCIPaddRealParam(scip,
2487 "separating/" SEPA_NAME "/badscore",
2488 "threshold for score of cut relative to best score to be discarded",
2489 &sepadata->badscore, TRUE, DEFAULT_BADSCORE, 0.0, 1.0, NULL, NULL) );
2490 SCIP_CALL( SCIPaddRealParam(scip,
2491 "separating/" SEPA_NAME "/objparalweight",
2492 "weight of objective parallelism in cut score calculation",
2493 &sepadata->objparalweight, TRUE, DEFAULT_OBJPARALWEIGHT, 0.0, 1.0, NULL, NULL) );
2494 SCIP_CALL( SCIPaddRealParam(scip,
2495 "separating/" SEPA_NAME "/efficacyweight",
2496 "weight of efficacy in cut score calculation",
2497 &sepadata->efficacyweight, TRUE, DEFAULT_EFFICACYWEIGHT, 0.0, 1.0, NULL, NULL) );
2498 SCIP_CALL( SCIPaddRealParam(scip,
2499 "separating/" SEPA_NAME "/dircutoffdistweight",
2500 "weight of directed cutoff distance in cut score calculation",
2501 &sepadata->dircutoffdistweight, TRUE, DEFAULT_DIRCUTOFFDISTWEIGHT, 0.0, 1.0, NULL, NULL) );
2502 SCIP_CALL( SCIPaddRealParam(scip,
2503 "separating/" SEPA_NAME "/goodmaxparall",
2504 "maximum parallelism for good cuts",
2505 &sepadata->goodmaxparall, TRUE, DEFAULT_GOODMAXPARALL, 0.0, 1.0, NULL, NULL) );
2506 SCIP_CALL( SCIPaddRealParam(scip,
2507 "separating/" SEPA_NAME "/maxparall",
2508 "maximum parallelism for non-good cuts",
2509 &sepadata->maxparall, TRUE, DEFAULT_MAXPARALL, 0.0, 1.0, NULL, NULL) );
2510 SCIP_CALL( SCIPaddRealParam(scip,
2511 "separating/" SEPA_NAME "/minviol",
2512 "minimal violation to generate zerohalfcut for",
2513 &sepadata->minviol, TRUE, DEFAULT_MINVIOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2514 SCIP_CALL( SCIPaddBoolParam(scip,
2515 "separating/" SEPA_NAME "/dynamiccuts",
2516 "should generated cuts be removed from the LP if they are no longer tight?",
2517 &sepadata->dynamiccuts, FALSE, DEFAULT_DYNAMICCUTS, NULL, NULL) );
2518 SCIP_CALL( SCIPaddRealParam(scip,
2519 "separating/" SEPA_NAME "/maxrowdensity",
2520 "maximal density of row to be used in aggregation",
2521 &sepadata->maxrowdensity, TRUE, DEFAULT_MAXROWDENSITY, 0.0, 1.0, NULL, NULL) );
2522 SCIP_CALL( SCIPaddIntParam(scip,
2523 "separating/" SEPA_NAME "/densityoffset",
2524 "additional number of variables allowed in row on top of density",
2525 &sepadata->densityoffset, TRUE, DEFAULT_DENSITYOFFSET, 0, INT_MAX, NULL, NULL) );
2526
2527 return SCIP_OKAY;
2528}
cutsel_hybrid.h
hybrid cut selector
NULL
#define NULL
Definition: def.h:262
SCIP_MAXSTRLEN
#define SCIP_MAXSTRLEN
Definition: def.h:283
SCIP_UNUSED
#define SCIP_UNUSED(x)
Definition: def.h:423
SCIP_Shortbool
#define SCIP_Shortbool
Definition: def.h:99
SCIP_REAL_MAX
#define SCIP_REAL_MAX
Definition: def.h:173
SCIP_Bool
#define SCIP_Bool
Definition: def.h:91
SCIP_DEFAULT_EPSILON
#define SCIP_DEFAULT_EPSILON
Definition: def.h:178
SCIP_ALLOC
#define SCIP_ALLOC(x)
Definition: def.h:380
SCIP_Real
#define SCIP_Real
Definition: def.h:172
TRUE
#define TRUE
Definition: def.h:93
FALSE
#define FALSE
Definition: def.h:94
MAX
#define MAX(x, y)
Definition: def.h:234
SCIP_LONGINT_FORMAT
#define SCIP_LONGINT_FORMAT
Definition: def.h:164
SCIPABORT
#define SCIPABORT()
Definition: def.h:341
REALABS
#define REALABS(x)
Definition: def.h:196
EPSZ
#define EPSZ(x, eps)
Definition: def.h:202
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:369
SCIPselectCutsHybrid
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)
Definition: cutsel_hybrid.c:438
SCIPisStopped
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:734
SCIPgetNContVars
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2172
SCIPgetNVars
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
SCIPgetVars
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1947
SCIPhashmapFree
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3110
SCIPhashmapGetImage
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3263
SCIPhashmapInsert
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3158
SCIPhashmapCreate
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3076
SCIPhashsetFree
void SCIPhashsetFree(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem)
Definition: misc.c:3792
SCIPhashsetExists
SCIP_Bool SCIPhashsetExists(SCIP_HASHSET *hashset, void *element)
Definition: misc.c:3819
SCIPhashsetGetSlots
void ** SCIPhashsetGetSlots(SCIP_HASHSET *hashset)
Definition: misc.c:4010
SCIPhashsetGetNElements
int SCIPhashsetGetNElements(SCIP_HASHSET *hashset)
Definition: misc.c:3994
SCIPhashsetGetNSlots
int SCIPhashsetGetNSlots(SCIP_HASHSET *hashset)
Definition: misc.c:4002
SCIPhashsetInsert
SCIP_RETCODE SCIPhashsetInsert(SCIP_HASHSET *hashset, BMS_BLKMEM *blkmem, void *element)
Definition: misc.c:3802
SCIPhashsetCreate
SCIP_RETCODE SCIPhashsetCreate(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem, int size)
Definition: misc.c:3761
SCIPhashsetRemove
SCIP_RETCODE SCIPhashsetRemove(SCIP_HASHSET *hashset, void *element)
Definition: misc.c:3860
SCIPhashtableFree
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2349
SCIPhashtableExists
SCIP_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2662
SCIPhashtableCreate
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:2299
SCIPhashtableRetrieve
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2611
SCIPhashtableRemove
SCIP_RETCODE SCIPhashtableRemove(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2680
SCIPhashtableInsert
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2550
SCIPhashSignature64
#define SCIPhashSignature64(a)
Definition: pub_misc.h:549
SCIPdebugMsg
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIPcalcIntegralScalar
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:9558
SCIPrelDiff
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
Definition: misc.c:11213
SCIPaddIntParam
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
SCIPaddRealParam
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
SCIPaddBoolParam
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
SCIPswapInts
void SCIPswapInts(int *value1, int *value2)
Definition: misc.c:10371
SCIPswapPointers
void SCIPswapPointers(void **pointer1, void **pointer2)
Definition: misc.c:10397
SCIPgetNLPBranchCands
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip_branch.c:435
SCIPcolGetVarProbindex
int SCIPcolGetVarProbindex(SCIP_COL *col)
Definition: lp.c:17091
SCIPcolGetVar
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:17071
SCIPcolIsIntegral
SCIP_Bool SCIPcolIsIntegral(SCIP_COL *col)
Definition: lp.c:17101
SCIPaddPoolCut
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip_cut.c:361
SCIPcutsTightenCoefficients
SCIP_Bool SCIPcutsTightenCoefficients(SCIP *scip, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, int *nchgcoefs)
Definition: cuts.c:1527
SCIPaggrRowCreate
SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition: cuts.c:1723
SCIPisCutNew
SCIP_Bool SCIPisCutNew(SCIP *scip, SCIP_ROW *row)
Definition: scip_cut.c:343
SCIPisEfficacious
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip_cut.c:135
SCIPaggrRowFree
void SCIPaggrRowFree(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition: cuts.c:1755
SCIPaddRow
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:250
SCIPgetVectorEfficacyNorm
SCIP_Real SCIPgetVectorEfficacyNorm(SCIP *scip, SCIP_Real *vals, int nvals)
Definition: scip_cut.c:149
SCIPgetLPColsData
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
Definition: scip_lp.c:472
SCIPgetLPRowsData
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip_lp.c:571
SCIPgetLPRows
SCIP_ROW ** SCIPgetLPRows(SCIP *scip)
Definition: scip_lp.c:606
SCIPgetNLPRows
int SCIPgetNLPRows(SCIP *scip)
Definition: scip_lp.c:627
SCIPgetLPSolstat
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:169
SCIPgetNLPCols
int SCIPgetNLPCols(SCIP *scip)
Definition: scip_lp.c:528
SCIPfreeCleanBufferArray
#define SCIPfreeCleanBufferArray(scip, ptr)
Definition: scip_mem.h:146
SCIPallocCleanBufferArray
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:142
SCIPfreeBlockMemoryArray
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
SCIPensureBlockMemoryArray
#define SCIPensureBlockMemoryArray(scip, ptr, arraysizeptr, minsize)
Definition: scip_mem.h:107
SCIPcalcMemGrowSize
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
SCIPallocBufferArray
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
SCIPfreeBufferArray
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
SCIPallocBlockMemoryArray
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
SCIPreallocBlockMemoryArray
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
SCIPfreeBlockMemory
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
SCIPfreeBlockMemoryArrayNull
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
SCIPallocBlockMemory
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIProwIsIntegral
SCIP_Bool SCIProwIsIntegral(SCIP_ROW *row)
Definition: lp.c:17420
SCIProwGetLhs
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17321
SCIProwIsModifiable
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
Definition: lp.c:17440
SCIPcacheRowExtensions
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1639
SCIProwGetNNonz
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:17242
SCIProwGetCols
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:17267
SCIProwGetRhs
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17331
SCIProwGetNLPNonz
int SCIProwGetNLPNonz(SCIP_ROW *row)
Definition: lp.c:17256
SCIProwGetLPPos
int SCIProwGetLPPos(SCIP_ROW *row)
Definition: lp.c:17530
SCIPflushRowExtensions
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1662
SCIProwIsLocal
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition: lp.c:17430
SCIPaddVarToRow
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1705
SCIPreleaseRow
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1566
SCIPcreateEmptyRowSepa
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:1457
SCIProwGetRank
int SCIProwGetRank(SCIP_ROW *row)
Definition: lp.c:17410
SCIProwChgRank
void SCIProwChgRank(SCIP_ROW *row, int rank)
Definition: lp.c:17563
SCIProwGetConstant
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:17287
SCIProwGetVals
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:17277
SCIPgetRowSolActivity
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition: scip_lp.c:2148
SCIPsetSepaInitsol
SCIP_RETCODE SCIPsetSepaInitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAINITSOL((*sepainitsol)))
Definition: scip_sepa.c:221
SCIPincludeSepaBasic
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:115
SCIPsepaGetName
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition: sepa.c:743
SCIPsepaGetNCallsAtNode
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
Definition: sepa.c:880
SCIPsetSepaFree
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip_sepa.c:173
SCIPsetSepaExitsol
SCIP_RETCODE SCIPsetSepaExitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAEXITSOL((*sepaexitsol)))
Definition: scip_sepa.c:237
SCIPsepaGetData
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
Definition: sepa.c:633
SCIPsepaSetData
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
Definition: sepa.c:643
SCIPsetSepaCopy
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip_sepa.c:157
SCIPgetSolVal
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1213
SCIPgetNLPs
SCIP_Longint SCIPgetNLPs(SCIP *scip)
Definition: scip_solvingstats.c:427
SCIPinfinity
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip_numerics.c:510
SCIPisFeasEQ
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:780
SCIPisPositive
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:570
SCIPfeasCeil
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:917
SCIPfeasFloor
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:905
SCIPisInfinity
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:521
SCIPisSumLT
SCIP_Bool SCIPisSumLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:692
SCIPround
SCIP_Real SCIPround(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:655
SCIPfeasRound
SCIP_Real SCIPfeasRound(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:929
SCIPisSumEQ
SCIP_Bool SCIPisSumEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:679
SCIPisFeasIntegral
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:881
SCIPfeastol
SCIP_Real SCIPfeastol(SCIP *scip)
Definition: scip_numerics.c:165
SCIPisGT
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:484
SCIPisEQ
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:445
SCIPisZero
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:558
SCIPepsilon
SCIP_Real SCIPepsilon(SCIP *scip)
Definition: scip_numerics.c:137
SCIPsumepsilon
SCIP_Real SCIPsumepsilon(SCIP *scip)
Definition: scip_numerics.c:151
SCIPisLT
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:458
SCIPisSumGT
SCIP_Bool SCIPisSumGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:718
SCIPvarGetVlbCoefs
SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
Definition: var.c:18310
SCIPvarGetUbLocal
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18162
SCIPvarGetUbGlobal
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18106
SCIPgetVarClosestVub
SCIP_RETCODE SCIPgetVarClosestVub(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Real *closestvub, int *closestvubidx)
Definition: scip_var.c:6737
SCIPvarGetProbindex
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17786
SCIPvarGetVlbConstants
SCIP_Real * SCIPvarGetVlbConstants(SCIP_VAR *var)
Definition: var.c:18320
SCIPgetVarClosestVlb
SCIP_RETCODE SCIPgetVarClosestVlb(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Real *closestvlb, int *closestvlbidx)
Definition: scip_var.c:6714
SCIPvarGetLbLocal
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18152
SCIPvarGetVlbVars
SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
Definition: var.c:18300
SCIPvarGetLbGlobal
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18096
SCIPvarGetVubConstants
SCIP_Real * SCIPvarGetVubConstants(SCIP_VAR *var)
Definition: var.c:18362
SCIPvarGetVubVars
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
Definition: var.c:18342
SCIPvarGetVubCoefs
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
Definition: var.c:18352
SCIPfreeRandom
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
Definition: scip_randnumgen.c:79
SCIPcreateRandom
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
Definition: scip_randnumgen.c:56
SCIPselectPtr
void SCIPselectPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int k, int len)
SCIPincludeSepaZerohalf
SCIP_RETCODE SCIPincludeSepaZerohalf(SCIP *scip)
Definition: sepa_zerohalf.c:2426
SCIPsortedvecFindPtr
SCIP_Bool SCIPsortedvecFindPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void *val, int len, int *pos)
SCIPsortPtr
void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
SCIPsnprintf
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10878
BMSallocBlockMemory
#define BMSallocBlockMemory(mem, ptr)
Definition: memory.h:451
BMSclearMemory
#define BMSclearMemory(ptr)
Definition: memory.h:129
BMScopyMemoryArray
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:134
BMSmoveMemoryArray
#define BMSmoveMemoryArray(ptr, source, num)
Definition: memory.h:138
BMS_BLKMEM
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:437
SCIPblkmem
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
scipdefplugins.h
default SCIP plugins
mod2matrixPreprocessColumns
static SCIP_RETCODE mod2matrixPreprocessColumns(SCIP *scip, MOD2_MATRIX *mod2matrix, SCIP_SEPADATA *sepadata)
Definition: sepa_zerohalf.c:1381
SEPA_PRIORITY
#define SEPA_PRIORITY
Definition: sepa_zerohalf.c:64
DEFAULT_BADSCORE
#define DEFAULT_BADSCORE
Definition: sepa_zerohalf.c:79
addOrigRow
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)
Definition: sepa_zerohalf.c:1462
DEFAULT_GOODSCORE
#define DEFAULT_GOODSCORE
Definition: sepa_zerohalf.c:77
MAXDNOM
#define MAXDNOM
Definition: sepa_zerohalf.c:92
SCIP_DECL_SEPAEXITSOL
static SCIP_DECL_SEPAEXITSOL(sepaExitsolZerohalf)
Definition: sepa_zerohalf.c:2149
BOUNDSWITCH
#define BOUNDSWITCH
Definition: sepa_zerohalf.c:97
SEPA_DELAY
#define SEPA_DELAY
Definition: sepa_zerohalf.c:68
DEFAULT_EFFICACYWEIGHT
#define DEFAULT_EFFICACYWEIGHT
Definition: sepa_zerohalf.c:86
ORIG_RHS
#define ORIG_RHS
Definition: sepa_zerohalf.c:109
DEFAULT_OBJPARALWEIGHT
#define DEFAULT_OBJPARALWEIGHT
Definition: sepa_zerohalf.c:85
SCIP_DECL_SEPAEXECLP
static SCIP_DECL_SEPAEXECLP(sepaExeclpZerohalf)
Definition: sepa_zerohalf.c:2381
COLINFO_GET_RHSOFFSET
#define COLINFO_GET_RHSOFFSET(x)
Definition: sepa_zerohalf.c:210
transformNonIntegralRow
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)
Definition: sepa_zerohalf.c:338
computeViolation
static SCIP_Real computeViolation(MOD2_ROW *row)
Definition: sepa_zerohalf.c:1594
DEFAULT_DYNAMICCUTS
#define DEFAULT_DYNAMICCUTS
Definition: sepa_zerohalf.c:81
SEPA_DESC
#define SEPA_DESC
Definition: sepa_zerohalf.c:63
SCIP_DECL_HASHKEYEQ
static SCIP_DECL_HASHKEYEQ(columnsEqual)
Definition: sepa_zerohalf.c:1209
ORIG_LHS
#define ORIG_LHS
Definition: sepa_zerohalf.c:110
SCIP_DECL_SEPAEXECSOL
static SCIP_DECL_SEPAEXECSOL(sepaExecsolZerohalf)
Definition: sepa_zerohalf.c:2408
mod2MatrixAddOrigRow
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)
Definition: sepa_zerohalf.c:824
generateZerohalfCut
static SCIP_RETCODE generateZerohalfCut(SCIP *scip, SCIP_SOL *sol, MOD2_MATRIX *mod2matrix, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_Bool allowlocal, MOD2_ROW *row)
Definition: sepa_zerohalf.c:1617
destroyMod2Matrix
static void destroyMod2Matrix(SCIP *scip, MOD2_MATRIX *mod2matrix)
Definition: sepa_zerohalf.c:990
DEFAULT_MAXSLACKROOT
#define DEFAULT_MAXSLACKROOT
Definition: sepa_zerohalf.c:76
MAXREDUCTIONROUNDS
#define MAXREDUCTIONROUNDS
Definition: sepa_zerohalf.c:96
getIntegralScalar
static void getIntegralScalar(SCIP_Real val, SCIP_Real scalar, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Real *sval, SCIP_Real *intval)
Definition: sepa_zerohalf.c:306
DEFAULT_MAXPARALL
#define DEFAULT_MAXPARALL
Definition: sepa_zerohalf.c:89
SCIP_DECL_SORTPTRCOMP
static SCIP_DECL_SORTPTRCOMP(compareColIndex)
Definition: sepa_zerohalf.c:238
addTransRow
static void addTransRow(SCIP_Real *tmpcoefs, SCIP_Real *cutrhs, int *nonzeroinds, int *nnz, int *cutrank, SCIP_Bool *cutislocal, TRANSINTROW *introw)
Definition: sepa_zerohalf.c:1516
mod2matrixRemoveRow
static SCIP_RETCODE mod2matrixRemoveRow(SCIP *scip, MOD2_MATRIX *mod2matrix, MOD2_ROW *row)
Definition: sepa_zerohalf.c:1308
DEFAULT_MAXROUNDSROOT
#define DEFAULT_MAXROUNDSROOT
Definition: sepa_zerohalf.c:71
MAXSCALE
#define MAXSCALE
Definition: sepa_zerohalf.c:93
mod2rowUnlinkCol
static void mod2rowUnlinkCol(MOD2_ROW *row, MOD2_COL *col)
Definition: sepa_zerohalf.c:797
SEPA_USESSUBSCIP
#define SEPA_USESSUBSCIP
Definition: sepa_zerohalf.c:67
UNIQUE_INDEX
#define UNIQUE_INDEX(rowind)
Definition: sepa_zerohalf.c:114
COLINFO_GET_MOD2COL
#define COLINFO_GET_MOD2COL(x)
Definition: sepa_zerohalf.c:209
DEFAULT_MAXSLACK
#define DEFAULT_MAXSLACK
Definition: sepa_zerohalf.c:75
buildMod2Matrix
static SCIP_RETCODE buildMod2Matrix(SCIP *scip, SCIP_SOL *sol, SCIP_SEPADATA *sepadata, BMS_BLKMEM *blkmem, MOD2_MATRIX *mod2matrix, SCIP_Bool allowlocal, SCIP_Real maxslack)
Definition: sepa_zerohalf.c:1026
mod2matrixPreprocessRows
static SCIP_RETCODE mod2matrixPreprocessRows(SCIP *scip, SCIP_SOL *sol, MOD2_MATRIX *mod2matrix, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_Bool allowlocal)
Definition: sepa_zerohalf.c:1868
mod2
static int mod2(SCIP *scip, SCIP_Real val)
Definition: sepa_zerohalf.c:294
DEFAULT_MAXSEPACUTSROOT
#define DEFAULT_MAXSEPACUTSROOT
Definition: sepa_zerohalf.c:73
DEFAULT_DENSITYOFFSET
#define DEFAULT_DENSITYOFFSET
Definition: sepa_zerohalf.c:83
DEFAULT_INITSEED
#define DEFAULT_INITSEED
Definition: sepa_zerohalf.c:84
SCIP_DECL_SEPAINITSOL
static SCIP_DECL_SEPAINITSOL(sepaInitsolZerohalf)
Definition: sepa_zerohalf.c:2132
NONZERO
#define NONZERO(x)
Definition: sepa_zerohalf.c:1458
computeMaxViolation
static SCIP_Real computeMaxViolation(MOD2_ROW *row)
Definition: sepa_zerohalf.c:1580
checkRow
static void checkRow(MOD2_ROW *row)
Definition: sepa_zerohalf.c:216
TRANSROW
#define TRANSROW
Definition: sepa_zerohalf.c:111
mod2MatrixAddTransRow
static SCIP_RETCODE mod2MatrixAddTransRow(SCIP *scip, MOD2_MATRIX *mod2matrix, SCIP_HASHMAP *origcol2col, int transrowind)
Definition: sepa_zerohalf.c:909
doSeparation
static SCIP_RETCODE doSeparation(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_RESULT *result, SCIP_Bool allowlocal, int depth)
Definition: sepa_zerohalf.c:2166
DEFAULT_GOODMAXPARALL
#define DEFAULT_GOODMAXPARALL
Definition: sepa_zerohalf.c:88
SEPA_MAXBOUNDDIST
#define SEPA_MAXBOUNDDIST
Definition: sepa_zerohalf.c:66
mod2matrixRemoveCol
static void mod2matrixRemoveCol(SCIP *scip, MOD2_MATRIX *mod2matrix, MOD2_COL *col)
Definition: sepa_zerohalf.c:1344
DEFAULT_MAXCUTCANDS
#define DEFAULT_MAXCUTCANDS
Definition: sepa_zerohalf.c:74
SCIP_DECL_HASHKEYVAL
static SCIP_DECL_HASHKEYVAL(columnGetSignature)
Definition: sepa_zerohalf.c:1236
DEFAULT_DIRCUTOFFDISTWEIGHT
#define DEFAULT_DIRCUTOFFDISTWEIGHT
Definition: sepa_zerohalf.c:87
SEPA_FREQ
#define SEPA_FREQ
Definition: sepa_zerohalf.c:65
MAXAGGRLEN
#define MAXAGGRLEN(nvars)
Definition: sepa_zerohalf.c:98
mod2rowAddRow
static SCIP_RETCODE mod2rowAddRow(SCIP *scip, BMS_BLKMEM *blkmem, MOD2_MATRIX *mod2matrix, MOD2_ROW *row, MOD2_ROW *rowtoadd)
Definition: sepa_zerohalf.c:1960
mod2MatrixAddCol
static SCIP_RETCODE mod2MatrixAddCol(SCIP *scip, MOD2_MATRIX *mod2matrix, SCIP_HASHMAP *origvar2col, SCIP_VAR *origvar, SCIP_Real solval, int rhsoffset)
Definition: sepa_zerohalf.c:721
calcEfficacy
static SCIP_Real calcEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_Real *cutcoefs, SCIP_Real cutrhs, int *cutinds, int cutnnz)
Definition: sepa_zerohalf.c:1550
DEFAULT_MAXSEPACUTS
#define DEFAULT_MAXSEPACUTS
Definition: sepa_zerohalf.c:72
SEPA_NAME
#define SEPA_NAME
Definition: sepa_zerohalf.c:62
mod2colLinkRow
static SCIP_RETCODE mod2colLinkRow(BMS_BLKMEM *blkmem, MOD2_COL *col, MOD2_ROW *row)
Definition: sepa_zerohalf.c:754
mod2MatrixTransformContRows
static SCIP_RETCODE mod2MatrixTransformContRows(SCIP *scip, SCIP_SOL *sol, SCIP_SEPADATA *sepadata, MOD2_MATRIX *mod2matrix, SCIP_Bool allowlocal, SCIP_Real maxslack)
Definition: sepa_zerohalf.c:628
SCIP_DECL_SEPACOPY
static SCIP_DECL_SEPACOPY(sepaCopyZerohalf)
Definition: sepa_zerohalf.c:2101
DEFAULT_MAXROUNDS
#define DEFAULT_MAXROUNDS
Definition: sepa_zerohalf.c:70
COLINFO_CREATE
#define COLINFO_CREATE(mod2col, rhsoffset)
Definition: sepa_zerohalf.c:211
ROWIND_TYPE
#define ROWIND_TYPE
Definition: sepa_zerohalf.c:108
mod2colUnlinkRow
static SCIP_RETCODE mod2colUnlinkRow(MOD2_COL *col, MOD2_ROW *row)
Definition: sepa_zerohalf.c:771
DEFAULT_MINVIOL
#define DEFAULT_MINVIOL
Definition: sepa_zerohalf.c:80
SCIP_DECL_SEPAFREE
static SCIP_DECL_SEPAFREE(sepaFreeZerohalf)
Definition: sepa_zerohalf.c:2115
DEFAULT_MAXROWDENSITY
#define DEFAULT_MAXROWDENSITY
Definition: sepa_zerohalf.c:82
sepa_zerohalf.h
{0,1/2}-cuts separator
Mod2Col::solval
SCIP_Real solval
Definition: sepa_zerohalf.c:157
Mod2Col::nonzrows
SCIP_HASHSET * nonzrows
Definition: sepa_zerohalf.c:156
Mod2Matrix::rows
MOD2_ROW ** rows
Definition: sepa_zerohalf.c:166
Mod2Matrix::transintrows
TRANSINTROW * transintrows
Definition: sepa_zerohalf.c:167
Mod2Matrix::cols
MOD2_COL ** cols
Definition: sepa_zerohalf.c:165
Mod2Matrix::nzeroslackrows
int nzeroslackrows
Definition: sepa_zerohalf.c:169
Mod2Row::rowinds
ROWINDEX * rowinds
Definition: sepa_zerohalf.c:140
Mod2Row::maxsolval
SCIP_Real maxsolval
Definition: sepa_zerohalf.c:143
Mod2Row::rowindssize
int rowindssize
Definition: sepa_zerohalf.c:148
Mod2Row::nrowinds
int nrowinds
Definition: sepa_zerohalf.c:147
Mod2Row::nonzcolssize
int nonzcolssize
Definition: sepa_zerohalf.c:150
Mod2Row::nonzcols
MOD2_COL ** nonzcols
Definition: sepa_zerohalf.c:141
Mod2Row::nnonzcols
int nnonzcols
Definition: sepa_zerohalf.c:149
Mod2Row::slack
SCIP_Real slack
Definition: sepa_zerohalf.c:142
RowIndex::index
unsigned int index
Definition: sepa_zerohalf.c:121
RowIndex::type
unsigned int type
Definition: sepa_zerohalf.c:118
SCIP_AggrRow
Definition: struct_cuts.h:41
SCIP_Col
Definition: struct_lp.h:136
SCIP_HashMap
Definition: struct_misc.h:138
SCIP_HashSet
Definition: struct_misc.h:150
SCIP_HashTable
Definition: struct_misc.h:90
SCIP_RandNumGen
Definition: struct_misc.h:269
SCIP_Row
Definition: struct_lp.h:202
SCIP_Sepa
Definition: struct_sepa.h:47
SCIP_Sol
Definition: struct_sol.h:74
SCIP_Var
Definition: struct_var.h:208
TransIntRow::slack
SCIP_Real slack
Definition: sepa_zerohalf.c:127
TransIntRow::vals
SCIP_Real * vals
Definition: sepa_zerohalf.c:129
TransIntRow::local
SCIP_Bool local
Definition: sepa_zerohalf.c:134
TransIntRow::rhs
SCIP_Real rhs
Definition: sepa_zerohalf.c:128
SCIP_LPSOLSTAT_OPTIMAL
@ SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:43
SCIP_DIDNOTRUN
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
SCIP_CUTOFF
@ SCIP_CUTOFF
Definition: type_result.h:48
SCIP_DIDNOTFIND
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
SCIP_SEPARATED
@ SCIP_SEPARATED
Definition: type_result.h:49
SCIP_RESULT
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
SCIP_OKAY
@ SCIP_OKAY
Definition: type_retcode.h:42
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_SEPADATA
struct SCIP_SepaData SCIP_SEPADATA
Definition: type_sepa.h:52