Scippy

SCIP

Solving Constraint Integer Programs

sepa_zerohalf.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file sepa_zerohalf.c
26 * @ingroup DEFPLUGINS_SEPA
27 * @brief {0,1/2}-cuts separator
28 * @author Leona Gottwald
29 * @author Manuel Kutschka
30 * @author Kati Wolter
31 *
32 * {0,1/2}-Chvátal-Gomory cuts separator. It solves the following separation problem:
33 * Consider an integer program
34 * \f[
35 * \min \{ c^T x : Ax \leq b, x \geq 0, x \mbox{ integer} \}
36 * \f]
37 * and a fractional solution \f$x^*\f$ of its LP relaxation. Find a weightvector \f$u\f$ whose entries \f$u_i\f$ are either 0 or
38 * \f$\frac{1}{2}\f$ such that the following inequality is valid for all integral solutions and violated by \f$x^*\f$:
39 * \f[
40 * \lfloor(u^T A) x \rfloor \leq \lfloor u^T b\rfloor
41 * \f]
42 *
43 * References:
44 * - Alberto Caprara, Matteo Fischetti. {0,1/2}-Chvatal-Gomory cuts. Math. Programming, Volume 74, p221--235, 1996.
45 * - Arie M. C. A. Koster, Adrian Zymolka and Manuel Kutschka. \n
46 * Algorithms to separate {0,1/2}-Chvatal-Gomory cuts.
47 * Algorithms - ESA 2007: 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, \n
48 * Proceedings. Lecture Notes in Computer Science, Volume 4698, p. 693--704, 2007.
49 * - Arie M. C. A. Koster, Adrian Zymolka and Manuel Kutschka. \n
50 * Algorithms to separate {0,1/2}-Chvatal-Gomory cuts (Extended Version). \n
51 * ZIB Report 07-10, Zuse Institute Berlin, 2007. http://www.zib.de/Publications/Reports/ZR-07-10.pdf
52 * - Manuel Kutschka. Algorithmen zur Separierung von {0,1/2}-Schnitten. Diplomarbeit. Technische Universitaet Berlin, 2007.
53 */
54
55/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
56
57#include "string.h"
58#include "scip/sepa_zerohalf.h"
59#include "scip/scipdefplugins.h"
60#include "scip/cutsel_hybrid.h"
61
62#define SEPA_NAME "zerohalf"
63#define SEPA_DESC "{0,1/2}-cuts separator"
64#define SEPA_PRIORITY -6000
65#define SEPA_FREQ 10
66#define SEPA_MAXBOUNDDIST 1.0
67#define SEPA_USESSUBSCIP FALSE
68#define SEPA_DELAY FALSE
69
70#define DEFAULT_MAXROUNDS 5 /**< maximal number of zerohalf separation rounds per node (-1: unlimited) */
71#define DEFAULT_MAXROUNDSROOT 20 /**< maximal number of zerohalf separation rounds in the root node (-1: unlimited) */
72#define DEFAULT_MAXSEPACUTS 20 /**< maximal number of zerohalf cuts separated per separation round */
73#define DEFAULT_MAXSEPACUTSROOT 100 /**< maximal number of zerohalf cuts separated per separation round in root node */
74#define DEFAULT_MAXCUTCANDS 2000 /**< maximal number of zerohalf cuts considered per separation round */
75#define DEFAULT_MAXSLACK 0.0 /**< maximal slack of rows to be used in aggregation */
76#define DEFAULT_MAXSLACKROOT 0.0 /**< maximal slack of rows to be used in aggregation in the root node */
77#define DEFAULT_GOODSCORE 1.0 /**< threshold for score of cut relative to best score to be considered good,
78 * so that less strict filtering is applied */
79#define DEFAULT_BADSCORE 0.5 /**< threshold for score of cut relative to best score to be discarded */
80#define DEFAULT_MINVIOL 0.1 /**< minimal violation to generate zerohalfcut for */
81#define DEFAULT_DYNAMICCUTS TRUE /**< should generated cuts be removed from the LP if they are no longer tight? */
82#define DEFAULT_MAXROWDENSITY 0.05 /**< maximal density of row to be used in aggregation */
83#define DEFAULT_DENSITYOFFSET 100 /**< additional number of variables allowed in row on top of density */
84#define DEFAULT_INITSEED 0x5EED /**< default initial seed used for random tie-breaking in cut selection */
85#define DEFAULT_OBJPARALWEIGHT 0.0 /**< weight of objective parallelism in cut score calculation */
86#define DEFAULT_EFFICACYWEIGHT 1.0 /**< weight of efficacy in cut score calculation */
87#define DEFAULT_DIRCUTOFFDISTWEIGHT 0.0 /**< weight of directed cutoff distance in cut score calculation */
88#define DEFAULT_GOODMAXPARALL 0.1 /**< maximum parallelism for good cuts */
89#define DEFAULT_MAXPARALL 0.1 /**< maximum parallelism for non-good cuts */
90
91/* SCIPcalcRowIntegralScalar parameters */
92#define MAXDNOM 1000LL
93#define MAXSCALE 1000.0
94
95/* other defines */
96#define MAXREDUCTIONROUNDS 100 /**< maximum number of rounds to perform reductions on the mod 2 system */
97#define BOUNDSWITCH 0.5 /**< threshold for bound switching */
98#define MAXAGGRLEN(nvars) ((int)(0.1*(nvars)+1000))
99
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 /* cppcheck-suppress nullPointer */
1358 position = col->pos;
1359
1360 /* remove column from arrays */
1361 --mod2matrix->ncols;
1362 mod2matrix->cols[position] = mod2matrix->cols[mod2matrix->ncols];
1363 mod2matrix->cols[position]->pos = position;
1364
1365 /* cppcheck-suppress nullPointer */
1366 nslots = SCIPhashsetGetNSlots(col->nonzrows);
1367 /* cppcheck-suppress nullPointer */
1368 rows = (MOD2_ROW**) SCIPhashsetGetSlots(col->nonzrows);
1369
1370 /* adjust rows of column */
1371 for( i = 0; i < nslots; ++i )
1372 {
1373 if( rows[i] != NULL )
1374 mod2rowUnlinkCol(rows[i], col);
1375 }
1376
1377 /* free column */
1378 SCIPhashsetFree(&col->nonzrows, SCIPblkmem(scip));
1379 SCIPfreeBlockMemory(scip, &col);
1380}
1381
1382/* remove columns that are (Prop3 iii) zero (Prop3 iv) identify indentical columns (Prop3 v) unit vector columns */
1383static
1384SCIP_RETCODE mod2matrixPreprocessColumns(
1385 SCIP* scip, /**< scip data structure */
1386 MOD2_MATRIX* mod2matrix, /**< mod 2 matrix */
1387 SCIP_SEPADATA* sepadata /**< zerohalf separator data */
1388 )
1389{
1390 int i;
1391 SCIP_HASHTABLE* columntable;
1392
1393 SCIP_CALL( SCIPhashtableCreate(&columntable, SCIPblkmem(scip), mod2matrix->ncols,
1394 SCIPhashGetKeyStandard, columnsEqual, columnGetSignature, NULL) );
1395
1396 for( i = 0; i < mod2matrix->ncols; )
1397 {
1398 MOD2_COL* col = mod2matrix->cols[i];
1399 int nnonzrows = SCIPhashsetGetNElements(col->nonzrows);
1400 if( nnonzrows == 0 )
1401 { /* Prop3 iii */
1402 mod2matrixRemoveCol(scip, mod2matrix, col);
1403 }
1404 else if( nnonzrows == 1 )
1405 { /* Prop3 v */
1406 MOD2_ROW* row;
1407
1408 {
1409 int j = 0;
1410 MOD2_ROW** rows;
1411 rows = (MOD2_ROW**) SCIPhashsetGetSlots(col->nonzrows);
1412 while( rows[j] == NULL )
1413 ++j;
1414
1415 row = rows[j];
1416 }
1417
1418 checkRow(row);
1419
1420 /* column is unit vector, so add its solution value to the rows slack and remove it */
1421 if( SCIPisZero(scip, row->slack) )
1422 --mod2matrix->nzeroslackrows;
1423
1424 row->slack += col->solval;
1425 assert(!SCIPisZero(scip, row->slack));
1426
1427 mod2matrixRemoveCol(scip, mod2matrix, col);
1428 ++sepadata->nreductions;
1429
1430 checkRow(row);
1431 }
1432 else
1433 {
1434 MOD2_COL* identicalcol;
1435 identicalcol = (MOD2_COL*)SCIPhashtableRetrieve(columntable, col);
1436 if( identicalcol != NULL )
1437 {
1438 assert(identicalcol != col);
1439
1440 /* column is identical to other column so add its solution value to the other one and then remove and free it */
1441 identicalcol->solval += col->solval;
1442
1443 /* also adjust the solval of the removed column so that the maxsolval of each row is properly updated */
1444 col->solval = identicalcol->solval;
1445
1446 mod2matrixRemoveCol(scip, mod2matrix, col);
1447 }
1448 else
1449 {
1450 SCIP_CALL( SCIPhashtableInsert(columntable, (void*)col) );
1451 ++i;
1452 }
1453 }
1454 }
1455
1456 SCIPhashtableFree(&columntable);
1457
1458 return SCIP_OKAY;
1459}
1460
1461#define NONZERO(x) (COPYSIGN(1e-100, (x)) + (x))
1462
1463/** add original row to aggregation with weight 0.5 */
1464static
1465void addOrigRow(
1466 SCIP* scip, /**< SCIP datastructure */
1467 SCIP_Real* tmpcoefs, /**< array to add coefficients to */
1468 SCIP_Real* cutrhs, /**< pointer to add right hand side */
1469 int* nonzeroinds, /**< array of non-zeros in the aggregation */
1470 int* nnz, /**< pointer to update number of non-zeros */
1471 int* cutrank, /**< pointer to update cut rank */
1472 SCIP_Bool* cutislocal, /**< pointer to update local flag */
1473 SCIP_ROW* row, /**< row to add */
1474 int sign /**< sign for weight, i.e. +1 to use right hand side or -1 to use left hand side */
1475 )
1476{
1477 int i;
1478 SCIP_Real weight = 0.5 * sign;
1479 SCIP_COL** rowcols;
1480 SCIP_Real* rowvals;
1481 int rowlen;
1482
1483 rowlen = SCIProwGetNNonz(row);
1484 rowcols = SCIProwGetCols(row);
1485 rowvals = SCIProwGetVals(row);
1486 for( i = 0; i < rowlen; ++i )
1487 {
1488 SCIP_Real val;
1489 int probindex;
1490
1491 probindex = SCIPcolGetVarProbindex(rowcols[i]);
1492 val = tmpcoefs[probindex];
1493 if( val == 0.0 )
1494 {
1495 nonzeroinds[(*nnz)++] = probindex;
1496 }
1497
1498 val += weight * rowvals[i];
1499 tmpcoefs[probindex] = NONZERO(val);
1500 }
1501
1502 if( sign == +1 )
1503 {
1504 *cutrhs += weight * SCIPfeasFloor(scip, SCIProwGetRhs(row) - SCIProwGetConstant(row));
1505 }
1506 else
1507 {
1508 assert(sign == -1);
1509 *cutrhs += weight * SCIPfeasCeil(scip, SCIProwGetLhs(row) - SCIProwGetConstant(row));
1510 }
1511
1512 if( SCIProwGetRank(row) > *cutrank )
1513 *cutrank = SCIProwGetRank(row);
1514 *cutislocal = *cutislocal || SCIProwIsLocal(row);
1515}
1516
1517/** add transformed integral row to aggregation with weight 0.5 */
1518static
1519void addTransRow(
1520 SCIP_Real* tmpcoefs, /**< array to add coefficients to */
1521 SCIP_Real* cutrhs, /**< pointer to add right hand side */
1522 int* nonzeroinds, /**< array of non-zeros in the aggregation */
1523 int* nnz, /**< pointer to update number of non-zeros */
1524 int* cutrank, /**< pointer to update cut rank */
1525 SCIP_Bool* cutislocal, /**< pointer to update local flag */
1526 TRANSINTROW* introw /**< transformed integral row to add to the aggregation */
1527 )
1528{
1529 int i;
1530
1531 for( i = 0; i < introw->len; ++i )
1532 {
1533 int probindex = introw->varinds[i];
1534 SCIP_Real val = tmpcoefs[probindex];
1535
1536 if( val == 0.0 )
1537 {
1538 nonzeroinds[(*nnz)++] = probindex;
1539 }
1540
1541 val += 0.5 * introw->vals[i];
1542 tmpcoefs[probindex] = NONZERO(val);
1543 }
1544
1545 *cutrhs += 0.5 * introw->rhs;
1546
1547 *cutrank = MAX(*cutrank, introw->rank);
1548 *cutislocal = *cutislocal || introw->local;
1549}
1550
1551/* calculates the cuts efficacy of cut */
1552static
1553SCIP_Real calcEfficacy(
1554 SCIP* scip, /**< SCIP data structure */
1555 SCIP_SOL* sol, /**< solution to separate, or NULL for LP solution */
1556 SCIP_Real* cutcoefs, /**< array of the non-zero coefficients in the cut */
1557 SCIP_Real cutrhs, /**< the right hand side of the cut */
1558 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
1559 int cutnnz /**< the number of non-zeros in the cut */
1560 )
1561{
1562 SCIP_VAR** vars;
1563 SCIP_Real norm;
1564 SCIP_Real activity;
1565 int i;
1566
1567 assert(scip != NULL);
1568 assert(cutcoefs != NULL);
1569 assert(cutinds != NULL);
1570
1571 norm = SCIPgetVectorEfficacyNorm(scip, cutcoefs, cutnnz);
1572 vars = SCIPgetVars(scip);
1573
1574 activity = 0.0;
1575 for( i = 0; i < cutnnz; ++i )
1576 activity += cutcoefs[i] * SCIPgetSolVal(scip, sol, vars[cutinds[i]]);
1577
1578 return (activity - cutrhs) / MAX(1e-6, norm);
1579}
1580
1581/** computes maximal violation that can be achieved for zerohalf cuts where this row particiaptes */
1582static
1583SCIP_Real computeMaxViolation(
1584 MOD2_ROW* row /**< mod 2 row */
1585 )
1586{
1587 SCIP_Real viol;
1588
1589 viol = 1.0 - row->slack;
1590 viol *= 0.5;
1591
1592 return viol;
1593}
1594
1595/** computes violation of zerohalf cut generated from given mod 2 row */
1596static
1597SCIP_Real computeViolation(
1598 MOD2_ROW* row /**< mod 2 row */
1599 )
1600{
1601 int i;
1602 SCIP_Real viol;
1603
1604 viol = 1.0 - row->slack;
1605
1606 for( i = 0; i < row->nnonzcols; ++i )
1607 {
1608 viol -= row->nonzcols[i]->solval;
1609 }
1610
1611 viol *= 0.5;
1612
1613 return viol;
1614}
1615
1616/** generate a zerohalf cut from a given mod 2 row, i.e., try if aggregations of rows of the
1617 * mod2 matrix give violated cuts
1618 */
1619static
1620SCIP_RETCODE generateZerohalfCut(
1621 SCIP* scip, /**< scip data structure */
1622 SCIP_SOL* sol, /**< solution to separate, or NULL for LP solution */
1623 MOD2_MATRIX* mod2matrix, /**< mod 2 matrix */
1624 SCIP_SEPA* sepa, /**< zerohalf separator */
1625 SCIP_SEPADATA* sepadata, /**< zerohalf separator data */
1626 SCIP_Bool allowlocal, /**< should local cuts be allowed */
1627 MOD2_ROW* row /**< mod 2 row */
1628 )
1629{
1630 SCIP_Bool cutislocal;
1631 int i;
1632 int cutnnz;
1633 int cutrank;
1634 int nvars;
1635 int maxaggrlen;
1636 int nchgcoefs;
1637 int* cutinds;
1638 SCIP_ROW** rows;
1639 SCIP_VAR** vars;
1640 SCIP_Real* tmpcoefs;
1641 SCIP_Real* cutcoefs;
1642 SCIP_Real cutrhs;
1643 SCIP_Real cutefficacy;
1644
1645 if( computeViolation(row) < sepadata->minviol )
1646 return SCIP_OKAY;
1647
1648 rows = SCIPgetLPRows(scip);
1649 nvars = SCIPgetNVars(scip);
1650 vars = SCIPgetVars(scip);
1651
1652 maxaggrlen = MAXAGGRLEN(SCIPgetNLPCols(scip));
1653
1654 /* right hand side must be odd, otherwise no cut can be generated */
1655 assert(row->rhs == 1);
1656
1657 /* perform the summation of the rows defined by the mod 2 row*/
1658 SCIP_CALL( SCIPallocCleanBufferArray(scip, &tmpcoefs, nvars) );
1659 SCIP_CALL( SCIPallocBufferArray(scip, &cutinds, nvars) );
1660 SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, nvars) );
1661
1662 /* the right hand side of the zerohalf cut will be rounded down by 0.5
1663 * thus we can instead subtract 0.5 directly
1664 */
1665 cutrhs = -0.5;
1666 cutnnz = 0;
1667 cutrank = 0;
1668 cutislocal = FALSE;
1669
1670 /* compute the aggregation of the rows with weight 0.5 */
1671 for( i = 0; i < row->nrowinds; ++i )
1672 {
1673 switch( row->rowinds[i].type )
1674 {
1675 case ORIG_RHS:
1676 addOrigRow(scip, tmpcoefs, &cutrhs, cutinds, &cutnnz, &cutrank, &cutislocal, rows[row->rowinds[i].index], 1);
1677 break;
1678 case ORIG_LHS:
1679 addOrigRow(scip, tmpcoefs, &cutrhs, cutinds, &cutnnz, &cutrank, &cutislocal, rows[row->rowinds[i].index], -1);
1680 break;
1681 case TRANSROW: {
1682 TRANSINTROW* introw = &mod2matrix->transintrows[row->rowinds[i].index];
1683 SCIPdebugMsg(scip, "using transformed row %i of length %i with slack %f and rhs %f for cut\n", row->rowinds[i].index, introw->len, introw->slack, introw->rhs);
1684 addTransRow(tmpcoefs, &cutrhs, cutinds, &cutnnz, &cutrank, &cutislocal, introw);
1685 break;
1686 }
1687 default:
1688 SCIPABORT();
1689 }
1690 }
1691
1692 /* abort if aggregation is too long */
1693 if( cutnnz > maxaggrlen )
1694 {
1695 /* clean buffer array must be set to zero before jumping to the terminate label */
1696 for( i = 0; i < cutnnz; ++i )
1697 {
1698 int k = cutinds[i];
1699 tmpcoefs[k] = 0.0;
1700 }
1701 goto TERMINATE;
1702 }
1703
1704 /* compute the cut coefficients and update right handside due to complementation if necessary */
1705 for( i = 0; i < cutnnz; )
1706 {
1707 int k = cutinds[i];
1708 SCIP_Real coef = tmpcoefs[k];
1709 SCIP_Real floorcoef = SCIPfeasFloor(scip, coef);
1710 tmpcoefs[k] = 0.0;
1711
1712 /* only check complementation if the coefficient was rounded down */
1713 if( REALABS(coef - floorcoef) > 0.1 )
1714 {
1715 SCIP_Real lb;
1716 SCIP_Real ub;
1717 SCIP_Bool loclb;
1718 SCIP_Bool locub;
1719 SCIP_Real primsol;
1720 SCIP_Bool useub;
1721
1722 /* complement with closest bound */
1723 primsol = SCIPgetSolVal(scip, sol, vars[k]);
1724 lb = SCIPvarGetLbGlobal(vars[k]);
1725 ub = SCIPvarGetUbGlobal(vars[k]);
1726 loclb = FALSE;
1727 locub = FALSE;
1728
1729 /* use local bounds if better */
1730 if( allowlocal )
1731 {
1732 if( SCIPisGT(scip, SCIPvarGetLbLocal(vars[k]), lb) )
1733 {
1734 loclb = TRUE;
1735 lb = SCIPvarGetLbLocal(vars[k]);
1736 }
1737
1738 if( SCIPisLT(scip, SCIPvarGetUbLocal(vars[k]), ub) )
1739 {
1740 locub = TRUE;
1741 ub = SCIPvarGetUbLocal(vars[k]);
1742 }
1743 }
1744
1745 if( SCIPisInfinity(scip, ub) ) /* if there is no ub, use lb */
1746 useub = FALSE;
1747 else if( SCIPisInfinity(scip, -lb) ) /* if there is no lb, use ub */
1748 useub = TRUE;
1749 else if( SCIPisLT(scip, primsol, (1.0 - BOUNDSWITCH) * lb + BOUNDSWITCH * ub) )
1750 useub = FALSE;
1751 else
1752 useub = TRUE;
1753
1754 if( useub )
1755 {
1756 /* set local flag if local bound was used */
1757 if( locub )
1758 cutislocal = TRUE;
1759
1760 /* upper bound was used so floor was the wrong direction to round, coefficient must be ceiled instead */
1761 floorcoef += 1.0;
1762
1763 assert(SCIPisFeasEQ(scip, floorcoef - coef, 0.5));
1764
1765 /* add delta of complementing then rounding by 0.5 and complementing back to the right hand side */
1766 cutrhs += 0.5 * ub;
1767 }
1768 else
1769 {
1770 /* set local flag if local bound was used */
1771 if( loclb )
1772 cutislocal = TRUE;
1773
1774 assert(SCIPisFeasEQ(scip, coef - floorcoef, 0.5));
1775
1776 /* add delta of complementing then rounding by 0.5 and complementing back to the right hand side */
1777 cutrhs -= 0.5 * lb;
1778 }
1779 }
1780
1781 /* make coefficient exactly integral */
1782 assert(SCIPisFeasIntegral(scip, floorcoef));
1783 floorcoef = SCIPfeasRound(scip, floorcoef);
1784
1785 /* if coefficient is zero remove entry, otherwise set to floorcoef */
1786 if( floorcoef == 0.0 )
1787 {
1788 --cutnnz;
1789 cutinds[i] = cutinds[cutnnz];
1790 }
1791 else
1792 {
1793 cutcoefs[i] = floorcoef;
1794 ++i;
1795 }
1796 }
1797
1798 /* make right hand side exactly integral */
1799 assert(SCIPisFeasIntegral(scip, cutrhs));
1800 cutrhs = SCIPfeasRound(scip, cutrhs);
1801
1802 if( ! SCIPcutsTightenCoefficients(scip, cutislocal, cutcoefs, &cutrhs, cutinds, &cutnnz, &nchgcoefs) )
1803 {
1804 /* calculate efficacy */
1805 cutefficacy = calcEfficacy(scip, sol, cutcoefs, cutrhs, cutinds, cutnnz);
1806
1807 if( SCIPisEfficacious(scip, cutefficacy) )
1808 {
1809 SCIP_ROW* cut;
1810 char cutname[SCIP_MAXSTRLEN];
1811 int v;
1812
1813 /* increase rank by 1 */
1814 cutrank += 1;
1815
1816 assert(allowlocal || !cutislocal);
1817
1818 /* create the cut */
1819 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "zerohalf%" SCIP_LONGINT_FORMAT "_x%d", SCIPgetNLPs(scip), row->index);
1820
1821 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), cutrhs, cutislocal, FALSE, sepadata->dynamiccuts) );
1822
1823 SCIProwChgRank(cut, cutrank);
1824
1825 /* cache the row extension and only flush them if the cut gets added */
1826 SCIP_CALL( SCIPcacheRowExtensions(scip, cut) );
1827
1828 /* collect all non-zero coefficients */
1829 for( v = 0; v < cutnnz; ++v )
1830 {
1831 SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cutinds[v]], cutcoefs[v]) );
1832 }
1833
1834 /* flush all changes before adding the cut */
1835 SCIP_CALL( SCIPflushRowExtensions(scip, cut) );
1836
1837 if( SCIPisCutNew(scip, cut) )
1838 {
1839 int pos = sepadata->ncuts++;
1840
1841 if( sepadata->ncuts > sepadata->cutssize )
1842 {
1843 int newsize = SCIPcalcMemGrowSize(scip, sepadata->ncuts);
1844 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &sepadata->cuts, sepadata->cutssize, newsize) );
1845 sepadata->cutssize = newsize;
1846 }
1847
1848 sepadata->cuts[pos] = cut;
1849 }
1850 else
1851 {
1852 /* release the row */
1853 SCIP_CALL( SCIPreleaseRow(scip, &cut) );
1854 }
1855 }
1856 }
1857
1858 TERMINATE:
1859 SCIPfreeBufferArray(scip, &cutcoefs);
1860 SCIPfreeBufferArray(scip, &cutinds);
1861 SCIPfreeCleanBufferArray(scip, &tmpcoefs);
1862
1863 return SCIP_OKAY;
1864}
1865
1866
1867/** remove rows that are (a) zero (b) identical to other rows (keep the one with smallest slack) (c) have slack greater
1868 * than 1 (d) for zero rows with 1 as rhs and slack less than 1, we can directly generate a cut and remove the row (Lemma 4)
1869 */
1870static
1871SCIP_RETCODE mod2matrixPreprocessRows(
1872 SCIP* scip, /**< scip data structure */
1873 SCIP_SOL* sol, /**< solution to separate, or NULL for LP solution */
1874 MOD2_MATRIX* mod2matrix, /**< the mod 2 matrix */
1875 SCIP_SEPA* sepa, /**< the zerohalf separator */
1876 SCIP_SEPADATA* sepadata, /**< data of the zerohalf separator */
1877 SCIP_Bool allowlocal /**< should local cuts be allowed */
1878 )
1879{
1880 int i;
1881 SCIP_HASHTABLE* rowtable;
1882
1883 SCIP_CALL( SCIPhashtableCreate(&rowtable, SCIPblkmem(scip), mod2matrix->nrows,
1884 SCIPhashGetKeyStandard, rowsEqual, rowGetSignature, NULL) );
1885
1886 for( i = 0; i < mod2matrix->nrows; )
1887 {
1888 MOD2_ROW* row = mod2matrix->rows[i];
1889 row->pos = i;
1890
1891 checkRow(row);
1892
1893 assert(row->nnonzcols == 0 || row->nonzcols != NULL);
1894
1895 if( (row->nnonzcols == 0 && row->rhs == 0) || computeMaxViolation(row) < sepadata->minviol )
1896 { /* (a) and (c) */
1897 sepadata->nreductions += row->nnonzcols;
1898 SCIP_CALL( mod2matrixRemoveRow(scip, mod2matrix, row) );
1899 }
1900 else if( row->nnonzcols > 0 )
1901 { /* (b) */
1902 MOD2_ROW* identicalrow;
1903 identicalrow = (MOD2_ROW*)SCIPhashtableRetrieve(rowtable, (void*)row);
1904 if( identicalrow != NULL )
1905 {
1906 assert(identicalrow != row);
1907 assert(identicalrow->nnonzcols == 0 || identicalrow->nonzcols != NULL);
1908
1909 checkRow(identicalrow);
1910
1911 /* row is identical to other row; only keep the one with smaller slack */
1912 if( identicalrow->slack <= row->slack )
1913 {
1914 SCIP_CALL( mod2matrixRemoveRow(scip, mod2matrix, row) );
1915 }
1916 else
1917 {
1918 assert(SCIPhashtableExists(rowtable, (void*)identicalrow));
1919
1920 SCIP_CALL( SCIPhashtableRemove(rowtable, (void*)identicalrow) );
1921 assert(!SCIPhashtableExists(rowtable, (void*)identicalrow));
1922
1923 SCIP_CALL( SCIPhashtableInsert(rowtable, (void*)row) );
1924
1925 SCIPswapPointers((void**) &mod2matrix->rows[row->pos], (void**) &mod2matrix->rows[identicalrow->pos]);
1926 SCIPswapInts(&row->pos, &identicalrow->pos);
1927
1928 assert(mod2matrix->rows[row->pos] == row && mod2matrix->rows[identicalrow->pos] == identicalrow);
1929 assert(identicalrow->pos == i);
1930 assert(row->pos < i);
1931
1932 SCIP_CALL( mod2matrixRemoveRow(scip, mod2matrix, identicalrow) );
1933 }
1934 }
1935 else
1936 {
1937 SCIP_CALL( SCIPhashtableInsert(rowtable, (void*)row) );
1938 ++i;
1939 }
1940 }
1941 else
1942 {
1943 /* (d) */
1944 assert(row->nnonzcols == 0 && row->rhs == 1 && SCIPisLT(scip, row->slack, 1.0));
1945
1946 SCIP_CALL( generateZerohalfCut(scip, sol, mod2matrix, sepa, sepadata, allowlocal, row) );
1947
1948 if( sepadata->infeasible )
1949 goto TERMINATE;
1950
1951 SCIP_CALL( mod2matrixRemoveRow(scip, mod2matrix, row) );
1952 ++i;
1953 }
1954 }
1955TERMINATE:
1956 SCIPhashtableFree(&rowtable);
1957
1958 return SCIP_OKAY;
1959}
1960
1961/** add a mod2 row to another one */
1962static
1963SCIP_RETCODE mod2rowAddRow(
1964 SCIP* scip, /**< scip data structure */
1965 BMS_BLKMEM* blkmem, /**< block memory shell */
1966 MOD2_MATRIX* mod2matrix, /**< mod 2 matrix */
1967 MOD2_ROW* row, /**< mod 2 row */
1968 MOD2_ROW* rowtoadd /**< mod 2 row that is added to the other mod 2 row */
1969 )
1970{
1971 SCIP_Shortbool* contained;
1972 int i;
1973 int j;
1974 int k;
1975 int nnewentries;
1976 int nlprows;
1977 MOD2_COL** newnonzcols;
1978 SCIP_Real newslack;
1979
1980 checkRow(row);
1981 checkRow(rowtoadd);
1982
1983 assert(row->nnonzcols == 0 || row->nonzcols != NULL);
1984 assert(rowtoadd->nnonzcols == 0 || rowtoadd->nonzcols != NULL);
1985
1986 nlprows = SCIPgetNLPRows(scip);
1987 row->rhs ^= rowtoadd->rhs;
1988
1989 newslack = row->slack + rowtoadd->slack;
1990 blkmem = SCIPblkmem(scip);
1991
1992 if( SCIPisZero(scip, row->slack) && !SCIPisZero(scip, newslack) )
1993 --mod2matrix->nzeroslackrows;
1994
1995 row->slack = newslack;
1996
1997 {
1998 /* the maximum index return by the UNIQUE_INDEX macro is 3 times
1999 * the maximum index value in the ROWINDEX struct. The index value could
2000 * be the lp position of an original row or the index of a transformed row.
2001 * Hence we need to allocate 3 times the maximum of these two possible
2002 * index types.
2003 */
2004 int allocsize = 3 * MAX(nlprows, mod2matrix->ntransintrows);
2005 SCIP_CALL( SCIPallocCleanBufferArray(scip, &contained, allocsize) );
2006 }
2007
2008 /* remember entries that are in the row to add */
2009 for( i = 0; i < rowtoadd->nrowinds; ++i )
2010 {
2011 contained[UNIQUE_INDEX(rowtoadd->rowinds[i])] = 1;
2012 }
2013
2014 /* remove the entries that are in both rows from the row (1 + 1 = 0 (mod 2)) */
2015 nnewentries = rowtoadd->nrowinds;
2016 for( i = 0; i < row->nrowinds; )
2017 {
2018 if( contained[UNIQUE_INDEX(row->rowinds[i])] )
2019 {
2020 --nnewentries;
2021 contained[UNIQUE_INDEX(row->rowinds[i])] = 0;
2022 --row->nrowinds;
2023 row->rowinds[i] = row->rowinds[row->nrowinds];
2024 }
2025 else
2026 {
2027 ++i;
2028 }
2029 }
2030
2031 SCIP_CALL( SCIPensureBlockMemoryArray(scip, &row->rowinds, &row->rowindssize, row->nrowinds + nnewentries) );
2032
2033 /* add remaining entries of row to add */
2034 for ( i = 0; i < rowtoadd->nrowinds; ++i )
2035 {
2036 if( contained[UNIQUE_INDEX(rowtoadd->rowinds[i])] )
2037 {
2038 contained[UNIQUE_INDEX(rowtoadd->rowinds[i])] = 0;
2039 row->rowinds[row->nrowinds++] = rowtoadd->rowinds[i];
2040 }
2041 }
2042
2043 SCIPfreeCleanBufferArray(scip, &contained);
2044
2045 SCIP_CALL( SCIPallocBufferArray(scip, &newnonzcols, row->nnonzcols + rowtoadd->nnonzcols) );
2046
2047 i = 0;
2048 j = 0;
2049 k = 0;
2050 row->maxsolval = 0.0;
2051
2052 /* since columns are sorted we can merge them */
2053 while( i < row->nnonzcols && j < rowtoadd->nnonzcols )
2054 {
2055 if( row->nonzcols[i] == rowtoadd->nonzcols[j] )
2056 {
2057 SCIP_CALL( mod2colUnlinkRow(row->nonzcols[i], row) );
2058 ++i;
2059 ++j;
2060 }
2061 else if( row->nonzcols[i]->index < rowtoadd->nonzcols[j]->index )
2062 {
2063 row->maxsolval = MAX(row->maxsolval, row->nonzcols[i]->solval);
2064 newnonzcols[k++] = row->nonzcols[i++];
2065 }
2066 else
2067 {
2068 SCIP_CALL( mod2colLinkRow(blkmem, rowtoadd->nonzcols[j], row) );
2069 newnonzcols[k++] = rowtoadd->nonzcols[j++];
2070 }
2071 }
2072
2073 while( i < row->nnonzcols )
2074 {
2075 row->maxsolval = MAX(row->maxsolval, row->nonzcols[i]->solval);
2076 newnonzcols[k++] = row->nonzcols[i++];
2077 }
2078
2079 while( j < rowtoadd->nnonzcols )
2080 {
2081 SCIP_CALL( mod2colLinkRow(blkmem, rowtoadd->nonzcols[j], row) );
2082 newnonzcols[k++] = rowtoadd->nonzcols[j++];
2083 }
2084
2085 row->nnonzcols = k;
2086 SCIP_CALL( SCIPensureBlockMemoryArray(scip, &row->nonzcols, &row->nonzcolssize, row->nnonzcols) );
2087 BMScopyMemoryArray(row->nonzcols, newnonzcols, row->nnonzcols);
2088
2089 SCIPfreeBufferArray(scip, &newnonzcols);
2090
2091 assert(row->nnonzcols == 0 || row->nonzcols != NULL);
2092 checkRow(row);
2093 checkRow(rowtoadd);
2094
2095 return SCIP_OKAY;
2096}
2097
2098/* --------------------------------------------------------------------------------------------------------------------
2099 * callback methods of separator
2100 * -------------------------------------------------------------------------------------------------------------------- */
2101
2102/** copy method for separator plugins (called when SCIP copies plugins) */
2103static
2104SCIP_DECL_SEPACOPY(sepaCopyZerohalf)
2105{ /*lint --e{715}*/
2106 assert(scip != NULL);
2107 assert(sepa != NULL);
2108 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
2109
2110 /* call inclusion method of constraint handler */
2111 SCIP_CALL( SCIPincludeSepaZerohalf(scip) );
2112
2113 return SCIP_OKAY;
2114}
2115
2116/** destructor of separator to free user data (called when SCIP is exiting) */
2117static
2118SCIP_DECL_SEPAFREE(sepaFreeZerohalf)
2119{
2120 SCIP_SEPADATA* sepadata;
2121
2122 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
2123
2124 /* free separator data */
2125 sepadata = SCIPsepaGetData(sepa);
2126 assert(sepadata != NULL);
2127
2128 SCIPfreeBlockMemory(scip, &sepadata);
2129 SCIPsepaSetData(sepa, NULL);
2130
2131 return SCIP_OKAY;
2132}
2133
2134static
2135SCIP_DECL_SEPAINITSOL(sepaInitsolZerohalf)
2136{
2137 SCIP_SEPADATA* sepadata;
2138
2139 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
2140
2141 /* allocate random generator */
2142 sepadata = SCIPsepaGetData(sepa);
2143 assert(sepadata != NULL);
2144
2145 assert(sepadata->randnumgen == NULL);
2146 SCIP_CALL( SCIPcreateRandom(scip, &sepadata->randnumgen, (unsigned int)sepadata->initseed, TRUE) );
2147
2148 return SCIP_OKAY;
2149}
2150
2151static
2152SCIP_DECL_SEPAEXITSOL(sepaExitsolZerohalf)
2153{
2154 SCIP_SEPADATA* sepadata;
2155
2156 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
2157
2158 /* free random generator */
2159 sepadata = SCIPsepaGetData(sepa);
2160 assert(sepadata != NULL);
2161
2162 SCIPfreeRandom(scip, &sepadata->randnumgen);
2163
2164 return SCIP_OKAY;
2165}
2166
2167/** perform the zerohalf cut separation */
2168static
2169SCIP_RETCODE doSeparation(
2170 SCIP* scip,
2171 SCIP_SEPA* sepa,
2172 SCIP_SOL* sol,
2173 SCIP_RESULT* result,
2174 SCIP_Bool allowlocal,
2175 int depth /* current depth */
2176 )
2177{
2178 int i;
2179 int k;
2180 int maxsepacuts;
2181 SCIP_Real maxslack;
2182 SCIP_SEPADATA* sepadata;
2183 MOD2_MATRIX mod2matrix;
2184 MOD2_ROW** nonzrows;
2185
2186 assert(result != NULL);
2187 assert(sepa != NULL);
2188
2189 sepadata = SCIPsepaGetData(sepa);
2190 assert(sepadata != NULL);
2191
2192 {
2193 int ncalls = SCIPsepaGetNCallsAtNode(sepa);
2194
2195 /* only call the zerohalf cut separator a given number of times at each node */
2196 if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
2197 || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
2198 return SCIP_OKAY;
2199
2200 maxsepacuts = depth == 0 ? sepadata->maxsepacutsroot : sepadata->maxsepacuts;
2201 maxslack = depth == 0 ? sepadata->maxslackroot : sepadata->maxslack;
2202 maxslack += 2 * SCIPfeastol(scip);
2203 }
2204
2205 *result = SCIP_DIDNOTFIND;
2206
2207 SCIP_CALL( SCIPaggrRowCreate(scip, &sepadata->aggrrow) );
2208 sepadata->ncuts = 0;
2209 sepadata->cutssize = 0;
2210 sepadata->cuts = NULL;
2211 sepadata->infeasible = FALSE;
2212
2213 SCIP_CALL( buildMod2Matrix(scip, sol, sepadata, SCIPblkmem(scip), &mod2matrix, allowlocal, maxslack) );
2214
2215 SCIPdebugMsg(scip, "built mod2 matrix (%i rows, %i cols)\n", mod2matrix.nrows, mod2matrix.ncols);
2216
2217 SCIP_CALL( SCIPallocBufferArray(scip, &nonzrows, mod2matrix.nrows) );
2218
2219 for( k = 0; k < MAXREDUCTIONROUNDS; ++k )
2220 {
2221 int ncancel;
2222
2223 sepadata->nreductions = 0;
2224
2225 assert(mod2matrix.nzeroslackrows <= mod2matrix.nrows);
2226 SCIP_CALL( mod2matrixPreprocessRows(scip, sol, &mod2matrix, sepa, sepadata, allowlocal) );
2227 assert(mod2matrix.nzeroslackrows <= mod2matrix.nrows);
2228
2229 SCIPdebugMsg(scip, "preprocessed rows (%i rows, %i cols, %i cuts) \n", mod2matrix.nrows, mod2matrix.ncols,
2230 sepadata->ncuts);
2231
2232 if( mod2matrix.nrows == 0 )
2233 break;
2234
2235 if( sepadata->ncuts >= sepadata->maxcutcands )
2236 {
2237 SCIPdebugMsg(scip, "enough cuts, stopping (%i rows, %i cols)\n", mod2matrix.nrows, mod2matrix.ncols);
2238 break;
2239 }
2240
2241 SCIP_CALL( mod2matrixPreprocessColumns(scip, &mod2matrix, sepadata) );
2242
2243 SCIPdebugMsg(scip, "preprocessed columns (%i rows, %i cols)\n", mod2matrix.nrows, mod2matrix.ncols);
2244
2245 ncancel = mod2matrix.nrows;
2246 if( ncancel > 100 )
2247 {
2248 ncancel = 100;
2249 SCIPselectPtr((void**) mod2matrix.rows, compareRowSlack, ncancel, mod2matrix.nrows);
2250 }
2251
2252 SCIPsortPtr((void**) mod2matrix.rows, compareRowSlack, ncancel);
2253
2254 if( mod2matrix.ncols == 0 )
2255 break;
2256
2257 assert(mod2matrix.nzeroslackrows <= mod2matrix.nrows);
2258
2259 /* apply Prop5 */
2260 for( i = 0; i < ncancel; ++i )
2261 {
2262 int j;
2263 MOD2_COL* col = NULL;
2264 MOD2_ROW* row = mod2matrix.rows[i];
2265
2266 if( SCIPisPositive(scip, row->slack) || row->nnonzcols == 0 )
2267 continue;
2268
2269 SCIPdebugMsg(scip, "processing row %i/%i (%i/%i cuts)\n", i, mod2matrix.nrows, sepadata->ncuts, sepadata->maxcutcands);
2270
2271 for( j = 0; j < row->nnonzcols; ++j )
2272 {
2273 if( row->nonzcols[j]->solval == row->maxsolval ) /*lint !e777*/
2274 {
2275 col = row->nonzcols[j];
2276 break;
2277 }
2278 }
2279
2280 assert( col != NULL );
2281
2282 {
2283 int nslots;
2284 int nnonzrows;
2285 MOD2_ROW** rows;
2286
2287 ++sepadata->nreductions;
2288
2289 nnonzrows = 0;
2290 /* cppcheck-suppress nullPointer */
2291 nslots = SCIPhashsetGetNSlots(col->nonzrows);
2292 /* cppcheck-suppress nullPointer */
2293 rows = (MOD2_ROW**) SCIPhashsetGetSlots(col->nonzrows);
2294
2295 for( j = 0; j < nslots; ++j )
2296 {
2297 if( rows[j] != NULL && rows[j] != row )
2298 nonzrows[nnonzrows++] = rows[j];
2299 }
2300
2301 for( j = 0; j < nnonzrows; ++j )
2302 {
2303 SCIP_CALL( mod2rowAddRow(scip, SCIPblkmem(scip), &mod2matrix, nonzrows[j], row) );
2304 }
2305
2306 /* cppcheck-suppress nullPointer */
2307 row->slack = col->solval;
2308 --mod2matrix.nzeroslackrows;
2309
2310 mod2matrixRemoveCol(scip, &mod2matrix, col);
2311 }
2312 }
2313
2314 SCIPdebugMsg(scip, "applied proposition five (%i rows, %i cols)\n", mod2matrix.nrows, mod2matrix.ncols);
2315
2316 if( sepadata->nreductions == 0 )
2317 {
2318 SCIPdebugMsg(scip, "no change, stopping (%i rows, %i cols)\n", mod2matrix.nrows, mod2matrix.ncols);
2319 break;
2320 }
2321 }
2322
2323 for( i = 0; i < mod2matrix.nrows && sepadata->ncuts < sepadata->maxcutcands; ++i )
2324 {
2325 MOD2_ROW* row = mod2matrix.rows[i];
2326
2327 if( computeMaxViolation(row) < sepadata->minviol )
2328 break;
2329
2330 if( row->rhs == 0 )
2331 continue;
2332
2333 SCIP_CALL( generateZerohalfCut(scip, sol, &mod2matrix, sepa, sepadata, allowlocal, row) );
2334 }
2335
2336 SCIPdebugMsg(scip, "total number of cuts found: %i\n", sepadata->ncuts);
2337
2338 /* If cuts where found we apply a filtering procedure using the scores and the orthogonalities,
2339 * similar to the sepastore. We only add the cuts that make it through this process and discard
2340 * the rest.
2341 */
2342 if( sepadata->ncuts > 0 )
2343 {
2344 int nselectedcuts;
2345
2346 SCIP_CALL( SCIPselectCutsHybrid(scip, sepadata->cuts, NULL, sepadata->randnumgen, sepadata->goodscore, sepadata->badscore,
2347 sepadata->goodmaxparall, sepadata->maxparall, sepadata->dircutoffdistweight, sepadata->efficacyweight, sepadata->objparalweight, 0.0,
2348 sepadata->ncuts, 0, maxsepacuts, &nselectedcuts) );
2349
2350 for( i = 0; i < sepadata->ncuts; ++i )
2351 {
2352 if( i < nselectedcuts )
2353 {
2354 /* if selected, add global cuts to the pool and local cuts to the sepastore */
2355 if( SCIProwIsLocal(sepadata->cuts[i]) )
2356 {
2357 SCIP_CALL( SCIPaddRow(scip, sepadata->cuts[i], FALSE, &sepadata->infeasible) );
2358 }
2359 else
2360 {
2361 SCIP_CALL( SCIPaddPoolCut(scip, sepadata->cuts[i]) );
2362 }
2363 }
2364
2365 /* release current cut */
2366 SCIP_CALL( SCIPreleaseRow(scip, &sepadata->cuts[i]) );
2367 }
2368
2369 SCIPfreeBlockMemoryArray(scip, &sepadata->cuts, sepadata->cutssize);
2370
2371 if( sepadata->infeasible )
2372 *result = SCIP_CUTOFF;
2373 else
2374 *result = SCIP_SEPARATED;
2375 }
2376
2377 SCIPfreeBufferArray(scip, &nonzrows);
2378 SCIPaggrRowFree(scip, &sepadata->aggrrow);
2379
2380 destroyMod2Matrix(scip, &mod2matrix);
2381
2382 return SCIP_OKAY;
2383}
2384
2385/** LP solution separation method of separator */
2386static
2387SCIP_DECL_SEPAEXECLP(sepaExeclpZerohalf)
2388{
2389 assert(result != NULL);
2390 assert(sepa != NULL);
2391 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
2392
2393 *result = SCIP_DIDNOTRUN;
2394
2395 /* only call separator, if we are not close to terminating */
2396 if( SCIPisStopped(scip) )
2397 return SCIP_OKAY;
2398
2399 /* only call separator, if an optimal LP solution is at hand */
2400 if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
2401 return SCIP_OKAY;
2402
2403 /* only call separator, if there are fractional variables */
2404 if( SCIPgetNLPBranchCands(scip) == 0 )
2405 return SCIP_OKAY;
2406
2407 SCIP_CALL( doSeparation(scip, sepa, NULL, result, allowlocal, depth) );
2408
2409 return SCIP_OKAY;
2410}
2411
2412/** custom solution separation method of separator */
2413static
2414SCIP_DECL_SEPAEXECSOL(sepaExecsolZerohalf)
2415{
2416 assert(result != NULL);
2417 assert(sepa != NULL);
2418 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
2419
2420 *result = SCIP_DIDNOTRUN;
2421
2422 /* only call separator, if we are not close to terminating */
2423 if( SCIPisStopped(scip) )
2424 return SCIP_OKAY;
2425
2426 SCIP_CALL( doSeparation(scip, sepa, sol, result, allowlocal, depth) );
2427
2428 return SCIP_OKAY;
2429}
2430
2431/** creates the zerohalf separator and includes it in SCIP */
2432SCIP_RETCODE SCIPincludeSepaZerohalf(
2433 SCIP* scip /**< SCIP data structure */
2434 )
2435{
2436 SCIP_SEPADATA* sepadata;
2437 SCIP_SEPA* sepa;
2438
2439 /* create zerohalf separator data */
2440 SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) );
2441 BMSclearMemory(sepadata);
2442
2443 /* include separator */
2444 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST,
2445 SEPA_USESSUBSCIP, SEPA_DELAY, sepaExeclpZerohalf, sepaExecsolZerohalf, sepadata) );
2446
2447 assert(sepa != NULL);
2448
2449 /* set non-NULL pointers to callback methods */
2450 SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyZerohalf) );
2451 SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeZerohalf) );
2452 SCIP_CALL( SCIPsetSepaInitsol(scip, sepa, sepaInitsolZerohalf) );
2453 SCIP_CALL( SCIPsetSepaExitsol(scip, sepa, sepaExitsolZerohalf) );
2454
2455 /* add zerohalf separator parameters */
2456 SCIP_CALL( SCIPaddIntParam(scip,
2457 "separating/" SEPA_NAME "/maxrounds",
2458 "maximal number of zerohalf separation rounds per node (-1: unlimited)",
2459 &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
2460 SCIP_CALL( SCIPaddIntParam(scip,
2461 "separating/" SEPA_NAME "/maxroundsroot",
2462 "maximal number of zerohalf separation rounds in the root node (-1: unlimited)",
2463 &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
2464 SCIP_CALL( SCIPaddIntParam(scip,
2465 "separating/" SEPA_NAME "/maxsepacuts",
2466 "maximal number of zerohalf cuts separated per separation round",
2467 &sepadata->maxsepacuts, FALSE, DEFAULT_MAXSEPACUTS, 0, INT_MAX, NULL, NULL) );
2468 SCIP_CALL( SCIPaddIntParam(scip,
2469 "separating/" SEPA_NAME "/initseed",
2470 "initial seed used for random tie-breaking in cut selection",
2471 &sepadata->initseed, FALSE, DEFAULT_INITSEED, 0, INT_MAX, NULL, NULL) );
2472 SCIP_CALL( SCIPaddIntParam(scip,
2473 "separating/" SEPA_NAME "/maxsepacutsroot",
2474 "maximal number of zerohalf cuts separated per separation round in the root node",
2475 &sepadata->maxsepacutsroot, FALSE, DEFAULT_MAXSEPACUTSROOT, 0, INT_MAX, NULL, NULL) );
2476 SCIP_CALL( SCIPaddIntParam(scip,
2477 "separating/" SEPA_NAME "/maxcutcands",
2478 "maximal number of zerohalf cuts considered per separation round",
2479 &sepadata->maxcutcands, FALSE, DEFAULT_MAXCUTCANDS, 0, INT_MAX, NULL, NULL) );
2480 SCIP_CALL( SCIPaddRealParam(scip,
2481 "separating/" SEPA_NAME "/maxslack",
2482 "maximal slack of rows to be used in aggregation",
2483 &sepadata->maxslack, TRUE, DEFAULT_MAXSLACK, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2484 SCIP_CALL( SCIPaddRealParam(scip,
2485 "separating/" SEPA_NAME "/maxslackroot",
2486 "maximal slack of rows to be used in aggregation in the root node",
2487 &sepadata->maxslackroot, TRUE, DEFAULT_MAXSLACKROOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2488 SCIP_CALL( SCIPaddRealParam(scip,
2489 "separating/" SEPA_NAME "/goodscore",
2490 "threshold for score of cut relative to best score to be considered good, so that less strict filtering is applied",
2491 &sepadata->goodscore, TRUE, DEFAULT_GOODSCORE, 0.0, 1.0, NULL, NULL) );
2492 SCIP_CALL( SCIPaddRealParam(scip,
2493 "separating/" SEPA_NAME "/badscore",
2494 "threshold for score of cut relative to best score to be discarded",
2495 &sepadata->badscore, TRUE, DEFAULT_BADSCORE, 0.0, 1.0, NULL, NULL) );
2496 SCIP_CALL( SCIPaddRealParam(scip,
2497 "separating/" SEPA_NAME "/objparalweight",
2498 "weight of objective parallelism in cut score calculation",
2499 &sepadata->objparalweight, TRUE, DEFAULT_OBJPARALWEIGHT, 0.0, 1.0, NULL, NULL) );
2500 SCIP_CALL( SCIPaddRealParam(scip,
2501 "separating/" SEPA_NAME "/efficacyweight",
2502 "weight of efficacy in cut score calculation",
2503 &sepadata->efficacyweight, TRUE, DEFAULT_EFFICACYWEIGHT, 0.0, 1.0, NULL, NULL) );
2504 SCIP_CALL( SCIPaddRealParam(scip,
2505 "separating/" SEPA_NAME "/dircutoffdistweight",
2506 "weight of directed cutoff distance in cut score calculation",
2507 &sepadata->dircutoffdistweight, TRUE, DEFAULT_DIRCUTOFFDISTWEIGHT, 0.0, 1.0, NULL, NULL) );
2508 SCIP_CALL( SCIPaddRealParam(scip,
2509 "separating/" SEPA_NAME "/goodmaxparall",
2510 "maximum parallelism for good cuts",
2511 &sepadata->goodmaxparall, TRUE, DEFAULT_GOODMAXPARALL, 0.0, 1.0, NULL, NULL) );
2512 SCIP_CALL( SCIPaddRealParam(scip,
2513 "separating/" SEPA_NAME "/maxparall",
2514 "maximum parallelism for non-good cuts",
2515 &sepadata->maxparall, TRUE, DEFAULT_MAXPARALL, 0.0, 1.0, NULL, NULL) );
2516 SCIP_CALL( SCIPaddRealParam(scip,
2517 "separating/" SEPA_NAME "/minviol",
2518 "minimal violation to generate zerohalfcut for",
2519 &sepadata->minviol, TRUE, DEFAULT_MINVIOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2520 SCIP_CALL( SCIPaddBoolParam(scip,
2521 "separating/" SEPA_NAME "/dynamiccuts",
2522 "should generated cuts be removed from the LP if they are no longer tight?",
2523 &sepadata->dynamiccuts, FALSE, DEFAULT_DYNAMICCUTS, NULL, NULL) );
2524 SCIP_CALL( SCIPaddRealParam(scip,
2525 "separating/" SEPA_NAME "/maxrowdensity",
2526 "maximal density of row to be used in aggregation",
2527 &sepadata->maxrowdensity, TRUE, DEFAULT_MAXROWDENSITY, 0.0, 1.0, NULL, NULL) );
2528 SCIP_CALL( SCIPaddIntParam(scip,
2529 "separating/" SEPA_NAME "/densityoffset",
2530 "additional number of variables allowed in row on top of density",
2531 &sepadata->densityoffset, TRUE, DEFAULT_DENSITYOFFSET, 0, INT_MAX, NULL, NULL) );
2532
2533 return SCIP_OKAY;
2534}
cutsel_hybrid.h
hybrid cut selector
NULL
#define NULL
Definition: def.h:267
SCIP_MAXSTRLEN
#define SCIP_MAXSTRLEN
Definition: def.h:288
SCIP_UNUSED
#define SCIP_UNUSED(x)
Definition: def.h:428
SCIP_Shortbool
#define SCIP_Shortbool
Definition: def.h:99
SCIP_REAL_MAX
#define SCIP_REAL_MAX
Definition: def.h:174
SCIP_Bool
#define SCIP_Bool
Definition: def.h:91
SCIP_DEFAULT_EPSILON
#define SCIP_DEFAULT_EPSILON
Definition: def.h:179
SCIP_ALLOC
#define SCIP_ALLOC(x)
Definition: def.h:385
SCIP_Real
#define SCIP_Real
Definition: def.h:173
TRUE
#define TRUE
Definition: def.h:93
FALSE
#define FALSE
Definition: def.h:94
MAX
#define MAX(x, y)
Definition: def.h:239
SCIP_LONGINT_FORMAT
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
SCIPABORT
#define SCIPABORT()
Definition: def.h:346
REALABS
#define REALABS(x)
Definition: def.h:197
EPSZ
#define EPSZ(x, eps)
Definition: def.h:203
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:374
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:724
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:3108
SCIPhashmapGetImage
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3261
SCIPhashmapInsert
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3156
SCIPhashmapCreate
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
SCIPhashsetFree
void SCIPhashsetFree(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem)
Definition: misc.c:3790
SCIPhashsetExists
SCIP_Bool SCIPhashsetExists(SCIP_HASHSET *hashset, void *element)
Definition: misc.c:3817
SCIPhashsetGetSlots
void ** SCIPhashsetGetSlots(SCIP_HASHSET *hashset)
Definition: misc.c:4008
SCIPhashsetGetNElements
int SCIPhashsetGetNElements(SCIP_HASHSET *hashset)
Definition: misc.c:3992
SCIPhashsetGetNSlots
int SCIPhashsetGetNSlots(SCIP_HASHSET *hashset)
Definition: misc.c:4000
SCIPhashsetInsert
SCIP_RETCODE SCIPhashsetInsert(SCIP_HASHSET *hashset, BMS_BLKMEM *blkmem, void *element)
Definition: misc.c:3800
SCIPhashsetCreate
SCIP_RETCODE SCIPhashsetCreate(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem, int size)
Definition: misc.c:3759
SCIPhashsetRemove
SCIP_RETCODE SCIPhashsetRemove(SCIP_HASHSET *hashset, void *element)
Definition: misc.c:3858
SCIPhashtableFree
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2346
SCIPhashtableExists
SCIP_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2659
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:2296
SCIPhashtableRetrieve
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2608
SCIPhashtableRemove
SCIP_RETCODE SCIPhashtableRemove(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2677
SCIPhashtableInsert
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2547
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:9557
SCIPrelDiff
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
Definition: misc.c:11184
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:10370
SCIPswapPointers
void SCIPswapPointers(void **pointer1, void **pointer2)
Definition: misc.c:10396
SCIPgetNLPBranchCands
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip_branch.c:428
SCIPcolGetVarProbindex
int SCIPcolGetVarProbindex(SCIP_COL *col)
Definition: lp.c:17062
SCIPcolGetVar
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:17042
SCIPcolIsIntegral
SCIP_Bool SCIPcolIsIntegral(SCIP_COL *col)
Definition: lp.c:17072
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:471
SCIPgetLPRowsData
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip_lp.c:570
SCIPgetLPRows
SCIP_ROW ** SCIPgetLPRows(SCIP *scip)
Definition: scip_lp.c:605
SCIPgetNLPRows
int SCIPgetNLPRows(SCIP *scip)
Definition: scip_lp.c:626
SCIPgetLPSolstat
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:168
SCIPgetNLPCols
int SCIPgetNLPCols(SCIP *scip)
Definition: scip_lp.c:527
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:17391
SCIProwGetLhs
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17292
SCIProwIsModifiable
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
Definition: lp.c:17411
SCIPcacheRowExtensions
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1635
SCIProwGetNNonz
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:17213
SCIProwGetCols
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:17238
SCIProwGetRhs
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17302
SCIProwGetNLPNonz
int SCIProwGetNLPNonz(SCIP_ROW *row)
Definition: lp.c:17227
SCIProwGetLPPos
int SCIProwGetLPPos(SCIP_ROW *row)
Definition: lp.c:17501
SCIPflushRowExtensions
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1658
SCIProwIsLocal
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition: lp.c:17401
SCIPaddVarToRow
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1701
SCIPreleaseRow
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1562
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:1453
SCIProwGetRank
int SCIProwGetRank(SCIP_ROW *row)
Definition: lp.c:17381
SCIProwChgRank
void SCIProwChgRank(SCIP_ROW *row, int rank)
Definition: lp.c:17534
SCIProwGetConstant
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:17258
SCIProwGetVals
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:17248
SCIPgetRowSolActivity
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition: scip_lp.c:2144
SCIPsetSepaInitsol
SCIP_RETCODE SCIPsetSepaInitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAINITSOL((*sepainitsol)))
Definition: scip_sepa.c:215
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:109
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:167
SCIPsetSepaExitsol
SCIP_RETCODE SCIPsetSepaExitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAEXITSOL((*sepaexitsol)))
Definition: scip_sepa.c:231
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:151
SCIPgetSolVal
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
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:18292
SCIPvarGetUbLocal
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
SCIPvarGetUbGlobal
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
SCIPgetVarClosestVub
SCIP_RETCODE SCIPgetVarClosestVub(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Real *closestvub, int *closestvubidx)
Definition: scip_var.c:6632
SCIPvarGetProbindex
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17768
SCIPvarGetVlbConstants
SCIP_Real * SCIPvarGetVlbConstants(SCIP_VAR *var)
Definition: var.c:18302
SCIPgetVarClosestVlb
SCIP_RETCODE SCIPgetVarClosestVlb(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Real *closestvlb, int *closestvlbidx)
Definition: scip_var.c:6609
SCIPvarGetLbLocal
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
SCIPvarGetVlbVars
SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
Definition: var.c:18282
SCIPvarGetLbGlobal
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
SCIPvarGetVubConstants
SCIP_Real * SCIPvarGetVubConstants(SCIP_VAR *var)
Definition: var.c:18344
SCIPvarGetVubVars
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
Definition: var.c:18324
SCIPvarGetVubCoefs
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
Definition: var.c:18334
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:2432
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:10877
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:1384
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:1465
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:2152
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:2387
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:1597
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:2414
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:1620
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:1519
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:1871
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:2135
NONZERO
#define NONZERO(x)
Definition: sepa_zerohalf.c:1461
computeMaxViolation
static SCIP_Real computeMaxViolation(MOD2_ROW *row)
Definition: sepa_zerohalf.c:1583
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:2169
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:1963
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:1553
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:2104
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:2118
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