Scippy

SCIP

Solving Constraint Integer Programs

sepa_disjunctive.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-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file sepa_disjunctive.c
17  * @brief disjunctive cut separator
18  * @author Tobias Fischer
19  * @author Marc Pfetsch
20  *
21  * We separate disjunctive cuts for two term disjunctions of the form \f$x_1 = 0 \vee x_2 = 0\f$. They can be generated
22  * directly from the simplex tableau. For further information, we refer to@n
23  * "A complementarity-based partitioning and disjunctive cut algorithm for mathematical programming problems with
24  * equilibrium constraints"@n
25  * Júdice, J.J., Sherali, H.D., Ribeiro, I.M., Faustino, A.M., Journal of Global Optimization 36(1), 89–114 (2006)
26  *
27  * Cut coefficients belonging to integer variables can be strengthened by the 'monoidal cut strengthening' procedure, see@n
28  * "Strengthening cuts for mixed integer programs"@n
29  * Egon Balas, Robert G. Jeroslow, European Journal of Operational Research, Volume 4, Issue 4, 1980, Pages 224-234
30  */
31 
32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33 
34 #include <assert.h>
35 #include <string.h>
36 #include <ctype.h>
37 #include "scip/sepa_disjunctive.h"
38 #include "scip/cons_sos1.h"
39 
40 
41 #define SEPA_NAME "disjunctive"
42 #define SEPA_DESC "disjunctive cut separator"
43 #define SEPA_PRIORITY 10 /**< priority for separation */
44 #define SEPA_FREQ 0 /**< frequency for separating cuts; zero means to separate only in the root node */
45 #define SEPA_MAXBOUNDDIST 0.0 /**< maximal relative distance from the current node's dual bound to primal bound
46  * compared to best node's dual bound for applying separation.*/
47 #define SEPA_USESSUBSCIP FALSE /**< does the separator use a secondary SCIP instance? */
48 #define SEPA_DELAY TRUE /**< should separation method be delayed, if other separators found cuts? */
49 
50 #define DEFAULT_MAXRANK 20 /**< maximal rank of a cut that could not be scaled to integral coefficients (-1: unlimited) */
51 #define DEFAULT_MAXRANKINTEGRAL -1 /**< maximal rank of a cut that could be scaled to integral coefficients (-1: unlimited) */
52 #define DEFAULT_MAXWEIGHTRANGE 1e+03 /**< maximal valid range max(|weights|)/min(|weights|) of row weights */
53 #define DEFAULT_STRENGTHEN TRUE /**< strengthen cut if integer variables are present */
54 
55 #define DEFAULT_MAXDEPTH -1 /**< node depth of separating cuts (-1: no limit) */
56 #define DEFAULT_MAXROUNDS 25 /**< maximal number of separation rounds in a branching node (-1: no limit) */
57 #define DEFAULT_MAXROUNDSROOT 100 /**< maximal number of separation rounds in the root node (-1: no limit) */
58 #define DEFAULT_MAXINVCUTS 50 /**< maximal number of cuts investigated per iteration in a branching node */
59 #define DEFAULT_MAXINVCUTSROOT 250 /**< maximal number of cuts investigated per iteration in the root node */
60 #define DEFAULT_MAXCONFSDELAY 100000 /**< delay separation if number of conflict graph edges is larger than predefined value (-1: no limit) */
61 
62 #define MAKECONTINTEGRAL FALSE /**< convert continuous variable to integral variables in SCIPmakeRowIntegral() */
63 
64 
65 /** separator data */
66 struct SCIP_SepaData
67 {
68  SCIP_Bool strengthen; /**< strengthen cut if integer variables are present */
69  SCIP_CONSHDLR* conshdlr; /**< SOS1 constraint handler */
70  SCIP_Real maxweightrange; /**< maximal valid range max(|weights|)/min(|weights|) of row weights */
71  int maxrank; /**< maximal rank of a cut that could not be scaled to integral coefficients (-1: unlimited) */
72  int maxrankintegral; /**< maximal rank of a cut that could be scaled to integral coefficients (-1: unlimited) */
73  int maxdepth; /**< node depth of separating cuts (-1: no limit) */
74  int maxrounds; /**< maximal number of separation rounds in a branching node (-1: no limit) */
75  int maxroundsroot; /**< maximal number of separation rounds in the root node (-1: no limit) */
76  int maxinvcuts; /**< maximal number of cuts separated per iteration in a branching node */
77  int maxinvcutsroot; /**< maximal number of cuts separated per iteration in the root node */
78  int maxconfsdelay; /**< delay separation if number of conflict graph edges is larger than predefined value (-1: no limit) */
79  int lastncutsfound; /**< total number of cuts found after last call of separator */
80 };
81 
82 
83 /** gets rank of variable corresponding to row of \f$B^{-1}\f$ */
84 static
85 int getVarRank(
86  SCIP* scip, /**< SCIP pointer */
87  SCIP_Real* binvrow, /**< row of \f$B^{-1}\f$ */
88  SCIP_Real* rowsmaxval, /**< maximal row multiplicator from nonbasic matrix A_N */
89  SCIP_Real maxweightrange, /**< maximal valid range max(|weights|)/min(|weights|) of row weights */
90  SCIP_ROW** rows, /**< rows of LP relaxation of scip */
91  int nrows /**< number of rows */
92  )
93 {
94  SCIP_Real maxweight = 0.0;
95  int maxrank = 0;
96  int r;
97 
98  assert( scip != NULL );
99  assert( binvrow != NULL || nrows == 0 );
100  assert( rowsmaxval != NULL || nrows == 0 );
101  assert( rows != NULL || nrows == 0 );
102 
103  /* compute maximum row weights resulting from multiplication */
104  for (r = 0; r < nrows; ++r)
105  {
106  SCIP_Real val;
107 
108  val = REALABS(binvrow[r] * rowsmaxval[r]);/*lint !e613*/
109  if ( SCIPisGT(scip, val, maxweight) )
110  maxweight = val;
111  }
112 
113  /* compute rank */
114  for (r = 0; r < nrows; ++r)
115  {
116  SCIP_Real val;
117  int rank;
118 
119  val = REALABS(binvrow[r] * rowsmaxval[r]);/*lint !e613*/
120  rank = SCIProwGetRank(rows[r]);/*lint !e613*/
121  if ( rank > maxrank && SCIPisGT(scip, val * maxweightrange, maxweight) )
122  maxrank = rank;
123  }
124 
125  return maxrank;
126 }
127 
128 
129 /** gets the nonbasic coefficients of a simplex row */
130 static
132  SCIP* scip, /**< SCIP pointer */
133  SCIP_ROW** rows, /**< LP rows */
134  int nrows, /**< number LP rows */
135  SCIP_COL** cols, /**< LP columns */
136  int ncols, /**< number of LP columns */
137  SCIP_Real* coef, /**< row of \f$B^{-1} \cdot A\f$ */
138  SCIP_Real* binvrow, /**< row of \f$B^{-1}\f$ */
139  SCIP_Real* simplexcoefs, /**< pointer to store the nonbasic simplex-coefficients */
140  int* nonbasicnumber /**< pointer to store the number of nonbasic simplex-coefficients */
141  )
142 {
143  int r;
144  int c;
145 
146  assert( scip != NULL );
147  assert( rows != NULL );
148  assert( nonbasicnumber != NULL );
149  assert( simplexcoefs != NULL );
150  assert( cols != NULL );
151 
152  *nonbasicnumber = 0;
153 
154  /* note: the non-slack variables have to be added first (see the function generateDisjCutSOS1()) */
155 
156  /* get simplex-coefficients of the non-basic non-slack variables */
157  for (c = 0; c < ncols; ++c)
158  {
159  SCIP_COL* col;
160 
161  col = cols[c];
162  assert( col != NULL );
164  simplexcoefs[(*nonbasicnumber)++] = coef[c];
165  }
166 
167  /* get simplex-coefficients of the non-basic slack variables */
168  for (r = 0; r < nrows; ++r)
169  {
170  SCIP_ROW* row;
171  row = rows[r];
172  assert( row != NULL );
173 
175  {
176  assert( SCIPisFeasZero(scip, SCIPgetRowLPActivity(scip, row) - SCIProwGetRhs(row)) || SCIPisFeasZero(scip, SCIPgetRowLPActivity(scip, row) - SCIProwGetLhs(row)) );
177 
178  simplexcoefs[(*nonbasicnumber)++] = binvrow[r];
179  }
180  }
181 
182  return SCIP_OKAY;
183 }
184 
185 
186 /** computes a disjunctive cut inequality based on two simplex taubleau rows */
187 static
189  SCIP* scip, /**< SCIP pointer */
190  SCIP_SEPA* sepa, /**< separator */
191  SCIP_ROW** rows, /**< LP rows */
192  int nrows, /**< number of LP rows */
193  SCIP_COL** cols, /**< LP columns */
194  int ncols, /**< number of LP columns */
195  int ndisjcuts, /**< number of disjunctive cuts found so far */
196  SCIP_Bool scale, /**< should cut be scaled */
197  SCIP_Bool strengthen, /**< should cut be strengthened if integer variables are present */
198  SCIP_Real cutlhs1, /**< left hand side of the first simplex row */
199  SCIP_Real cutlhs2, /**< left hand side of the second simplex row */
200  SCIP_Real bound1, /**< bound of first simplex row */
201  SCIP_Real bound2, /**< bound of second simplex row */
202  SCIP_Real* simplexcoefs1, /**< simplex coefficients of first row */
203  SCIP_Real* simplexcoefs2, /**< simplex coefficients of second row */
204  SCIP_Real* cutcoefs, /**< pointer to store cut coefficients (length: nscipvars) */
205  SCIP_ROW** row, /**< pointer to store disjunctive cut inequality */
206  SCIP_Bool* madeintegral /**< pointer to store whether cut has been scaled to integral values */
207  )
208 {
209  char cutname[SCIP_MAXSTRLEN];
210  SCIP_COL** rowcols;
211  SCIP_COL* col;
212  SCIP_Real* rowvals;
213  SCIP_Real lhsrow;
214  SCIP_Real rhsrow;
215  SCIP_Real cutlhs;
216  SCIP_Real sgn;
217  SCIP_Real lb;
218  SCIP_Real ub;
219  int nonbasicnumber = 0;
220  int rownnonz;
221  int ind;
222  int r;
223  int c;
224 
225  assert( scip != NULL );
226  assert( row != NULL );
227  assert( rows != NULL );
228  assert( cols != NULL );
229  assert( simplexcoefs1 != NULL );
230  assert( simplexcoefs2 != NULL );
231  assert( cutcoefs != NULL );
232  assert( sepa != NULL );
233  assert( madeintegral != NULL );
234 
235  *madeintegral = FALSE;
236 
237  /* check signs */
238  if ( SCIPisFeasPositive(scip, cutlhs1) == SCIPisFeasPositive(scip, cutlhs2) )
239  sgn = 1.0;
240  else
241  sgn = -1.0;
242 
243  /* check bounds */
244  if ( SCIPisInfinity(scip, REALABS(bound1)) || SCIPisInfinity(scip, REALABS(bound2)) )
245  strengthen = FALSE;
246 
247  /* compute left hand side of row (a later update is possible, see below) */
248  cutlhs = sgn * cutlhs1 * cutlhs2;
249 
250  /* add cut-coefficients of the non-basic non-slack variables */
251  for (c = 0; c < ncols; ++c)
252  {
253  col = cols[c];
254  assert( col != NULL );
255  ind = SCIPcolGetLPPos(col);
256  assert( ind >= 0 );
257 
259  {
260  lb = SCIPcolGetLb(col);
261 
262  /* for integer variables we may obtain stronger coefficients */
263  if ( strengthen && SCIPcolIsIntegral(col) )
264  {
265  SCIP_Real mval;
266  SCIP_Real mvalfloor;
267  SCIP_Real mvalceil;
268 
269  mval = (cutlhs2 * simplexcoefs1[nonbasicnumber] - cutlhs1 * simplexcoefs2[nonbasicnumber]) / (cutlhs2 * bound1 + cutlhs1 * bound2);
270  mvalfloor = SCIPfloor(scip, mval);
271  mvalceil = SCIPceil(scip, mval);
272 
273  cutcoefs[ind] = MIN(sgn * cutlhs2 * (simplexcoefs1[nonbasicnumber] - mvalfloor * bound1), sgn * cutlhs1 * (simplexcoefs2[nonbasicnumber] + mvalceil * bound2));
274  assert( SCIPisFeasLE(scip, cutcoefs[ind], MAX(sgn * cutlhs2 * simplexcoefs1[nonbasicnumber], sgn * cutlhs1 * simplexcoefs2[nonbasicnumber])) );
275  }
276  else
277  cutcoefs[ind] = MAX(sgn * cutlhs2 * simplexcoefs1[nonbasicnumber], sgn * cutlhs1 * simplexcoefs2[nonbasicnumber]);
278 
279  cutlhs += cutcoefs[ind] * lb;
280  ++nonbasicnumber;
281  }
282  else if ( SCIPcolGetBasisStatus(col) == SCIP_BASESTAT_UPPER )
283  {
284  ub = SCIPcolGetUb(col);
285 
286  /* for integer variables we may obtain stronger coefficients */
287  if ( strengthen && SCIPcolIsIntegral(col) )
288  {
289  SCIP_Real mval;
290  SCIP_Real mvalfloor;
291  SCIP_Real mvalceil;
292 
293  mval = (cutlhs2 * simplexcoefs1[nonbasicnumber] - cutlhs1 * simplexcoefs2[nonbasicnumber]) / (cutlhs2 * bound1 + cutlhs1 * bound2);
294  mvalfloor = SCIPfloor(scip, -mval);
295  mvalceil = SCIPceil(scip, -mval);
296 
297  cutcoefs[ind] = MAX(sgn * cutlhs2 * (simplexcoefs1[nonbasicnumber] + mvalfloor * bound1), sgn * cutlhs1 * (simplexcoefs2[nonbasicnumber] - mvalceil * bound2));
298  assert( SCIPisFeasLE(scip, -cutcoefs[ind], -MIN(sgn * cutlhs2 * simplexcoefs1[nonbasicnumber], sgn * cutlhs1 * simplexcoefs2[nonbasicnumber])) );
299  }
300  else
301  cutcoefs[ind] = MIN(sgn * cutlhs2 * simplexcoefs1[nonbasicnumber], sgn * cutlhs1 * simplexcoefs2[nonbasicnumber]);
302 
303  cutlhs += cutcoefs[ind] * ub;
304  ++nonbasicnumber;
305  }
306  else
307  {
308  assert( SCIPcolGetBasisStatus(col) != SCIP_BASESTAT_ZERO );
309  cutcoefs[ind] = 0.0;
310  }
311  }
312 
313  /* add cut-coefficients of the non-basic slack variables */
314  for (r = 0; r < nrows; ++r)
315  {
316  rhsrow = SCIProwGetRhs(rows[r]) - SCIProwGetConstant(rows[r]);
317  lhsrow = SCIProwGetLhs(rows[r]) - SCIProwGetConstant(rows[r]);
318 
319  assert( SCIProwGetBasisStatus(rows[r]) != SCIP_BASESTAT_ZERO );
320  assert( SCIPisFeasZero(scip, lhsrow - rhsrow) || SCIPisNegative(scip, lhsrow - rhsrow) );
321  assert( SCIProwIsInLP(rows[r]) );
322 
323  if ( SCIProwGetBasisStatus(rows[r]) != SCIP_BASESTAT_BASIC )
324  {
325  SCIP_Real cutcoef;
326 
327  if ( SCIProwGetBasisStatus(rows[r]) == SCIP_BASESTAT_UPPER )
328  {
329  assert( SCIPisFeasZero(scip, SCIPgetRowLPActivity(scip, rows[r]) - SCIProwGetRhs(rows[r])) );
330 
331  cutcoef = MAX(sgn * cutlhs2 * simplexcoefs1[nonbasicnumber], sgn * cutlhs1 * simplexcoefs2[nonbasicnumber]);
332  cutlhs -= cutcoef * rhsrow;
333  ++nonbasicnumber;
334  }
335  else /* SCIProwGetBasisStatus(rows[r]) == SCIP_BASESTAT_LOWER */
336  {
337  assert( SCIProwGetBasisStatus(rows[r]) == SCIP_BASESTAT_LOWER );
338  assert( SCIPisFeasZero(scip, SCIPgetRowLPActivity(scip, rows[r]) - SCIProwGetLhs(rows[r])) );
339 
340  cutcoef = MIN(sgn * cutlhs2 * simplexcoefs1[nonbasicnumber], sgn * cutlhs1 * simplexcoefs2[nonbasicnumber]);
341  cutlhs -= cutcoef * lhsrow;
342  ++nonbasicnumber;
343  }
344 
345  rownnonz = SCIProwGetNNonz(rows[r]);
346  rowvals = SCIProwGetVals(rows[r]);
347  rowcols = SCIProwGetCols(rows[r]);
348 
349  for (c = 0; c < rownnonz; ++c)
350  {
351  ind = SCIPcolGetLPPos(rowcols[c]);
352 
353  /* if column is not in LP, then return without generating cut */
354  if ( ind < 0 )
355  {
356  *row = NULL;
357  return SCIP_OKAY;
358  }
359 
360  cutcoefs[ind] -= cutcoef * rowvals[c];
361  }
362  }
363  }
364 
365  /* create cut */
366  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "%s_%d_%d", SCIPsepaGetName(sepa), SCIPgetNLPs(scip), ndisjcuts);
367  if ( SCIPgetDepth(scip) == 0 )
368  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, row, sepa, cutname, cutlhs, SCIPinfinity(scip), FALSE, FALSE, TRUE) );
369  else
370  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, row, sepa, cutname, cutlhs, SCIPinfinity(scip), TRUE, FALSE, TRUE) );
371 
372  SCIP_CALL( SCIPcacheRowExtensions(scip, *row) );
373  for (c = 0; c < ncols; ++c)
374  {
375  ind = SCIPcolGetLPPos(cols[c]);
376  assert( ind >= 0 );
377  if ( ! SCIPisFeasZero(scip, cutcoefs[ind]) )
378  {
379  SCIP_CALL( SCIPaddVarToRow(scip, *row, SCIPcolGetVar(cols[c]), cutcoefs[ind] ) );
380  }
381  }
382  SCIP_CALL( SCIPflushRowExtensions(scip, *row) );
383 
384  /* try to scale the cut to integral values
385  * @todo find better but still stable disjunctive cut settings
386  */
387  if ( scale )
388  {
389  SCIP_Longint maxdnom;
390  SCIP_Real maxscale;
391 
392  assert( SCIPgetDepth(scip) >= 0 );
393  if( SCIPgetDepth(scip) == 0 )
394  {
395  maxdnom = 100;
396  maxscale = 100.0;
397  }
398  else
399  {
400  maxdnom = 10;
401  maxscale = 10.0;
402  }
403 
404  SCIP_CALL( SCIPmakeRowIntegral(scip, *row, -SCIPepsilon(scip), SCIPsumepsilon(scip), maxdnom, maxscale, TRUE, madeintegral) );
405  }
406 
407  return SCIP_OKAY;
408 }
409 
410 
411 /*
412  * Callback methods
413  */
414 
415 /** copy method for separator plugins (called when SCIP copies plugins) */
416 static
417 SCIP_DECL_SEPACOPY(sepaCopyDisjunctive)
418 {
419  assert( scip != NULL );
420  assert( sepa != NULL );
421  assert( strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0 );
422 
423  /* call inclusion method of constraint handler */
425 
426  return SCIP_OKAY;
427 }
428 
429 
430 /** destructor of separator to free user data (called when SCIP is exiting) */
431 static
432 SCIP_DECL_SEPAFREE(sepaFreeDisjunctive)/*lint --e{715}*/
433 {
434  SCIP_SEPADATA* sepadata;
435 
436  assert( strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0 );
437 
438  /* free separator data */
439  sepadata = SCIPsepaGetData(sepa);
440  assert( sepadata != NULL );
441 
442  SCIPfreeBlockMemory(scip, &sepadata);
443 
444  SCIPsepaSetData(sepa, NULL);
445 
446  return SCIP_OKAY;
447 }
448 
449 
450 /** solving process initialization method of separator */
451 static
452 SCIP_DECL_SEPAEXITSOL(sepaInitsolDisjunctive)
453 { /*lint --e{715}*/
454  SCIP_SEPADATA* sepadata;
455 
456  sepadata = SCIPsepaGetData(sepa);
457  assert(sepadata != NULL);
458 
459  sepadata->conshdlr = SCIPfindConshdlr(scip, "SOS1");
460 
461  return SCIP_OKAY;
462 }
463 
464 
465 /** LP solution separation method for disjunctive cuts */
466 static
467 SCIP_DECL_SEPAEXECLP(sepaExeclpDisjunctive)
468 {
469  SCIP_SEPADATA* sepadata;
470  SCIP_CONSHDLR* conshdlr;
471  SCIP_DIGRAPH* conflictgraph;
472  SCIP_ROW** rows;
473  SCIP_COL** cols;
474  SCIP_Real* cutcoefs = NULL;
475  SCIP_Real* simplexcoefs1 = NULL;
476  SCIP_Real* simplexcoefs2 = NULL;
477  SCIP_Real* coef = NULL;
478  SCIP_Real* binvrow = NULL;
479  SCIP_Real* rowsmaxval = NULL;
480  SCIP_Real* violationarray = NULL;
481  int* fixings1 = NULL;
482  int* fixings2 = NULL;
483  int* basisind = NULL;
484  int* basisrow = NULL;
485  int* varrank = NULL;
486  int* edgearray = NULL;
487  int nedges;
488  int ndisjcuts;
489  int nrelevantedges;
490  int nsos1vars;
491  int nconss;
492  int maxcuts;
493  int ncalls;
494  int depth;
495  int ncols;
496  int nrows;
497  int ind;
498  int j;
499  int i;
500 
501  assert( sepa != NULL );
502  assert( strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0 );
503  assert( scip != NULL );
504  assert( result != NULL );
505 
506  *result = SCIP_DIDNOTRUN;
507 
508  if( !allowlocal )
509  return SCIP_OKAY;
510 
511  /* only generate disjunctive cuts if we are not close to terminating */
512  if ( SCIPisStopped(scip) )
513  return SCIP_OKAY;
514 
515  /* only generate disjunctive cuts if an optimal LP solution is at hand */
517  return SCIP_OKAY;
518 
519  /* only generate disjunctive cuts if the LP solution is basic */
520  if ( ! SCIPisLPSolBasic(scip) )
521  return SCIP_OKAY;
522 
523  /* get LP data */
524  SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
525  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
526 
527  /* return if LP has no columns or no rows */
528  if ( ncols == 0 || nrows == 0 )
529  return SCIP_OKAY;
530 
531  assert( cols != NULL );
532  assert( rows != NULL );
533 
534  /* get sepa data */
535  sepadata = SCIPsepaGetData(sepa);
536  assert( sepadata != NULL );
537 
538  /* get constraint handler */
539  conshdlr = sepadata->conshdlr;
540  if ( conshdlr == NULL )
541  return SCIP_OKAY;
542 
543  /* get number of constraints */
544  nconss = SCIPconshdlrGetNConss(conshdlr);
545  if ( nconss == 0 )
546  return SCIP_OKAY;
547 
548  /* check for maxdepth < depth, maxinvcutsroot = 0 and maxinvcuts = 0 */
549  depth = SCIPgetDepth(scip);
550  if ( ( sepadata->maxdepth >= 0 && sepadata->maxdepth < depth )
551  || ( depth == 0 && sepadata->maxinvcutsroot == 0 )
552  || ( depth > 0 && sepadata->maxinvcuts == 0 ) )
553  return SCIP_OKAY;
554 
555  /* only call the cut separator a given number of times at each node */
556  ncalls = SCIPsepaGetNCallsAtNode(sepa);
557  if ( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
558  || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
559  return SCIP_OKAY;
560 
561  /* get conflict graph and number of conflict graph edges (note that the digraph arcs were added in both directions) */
562  conflictgraph = SCIPgetConflictgraphSOS1(conshdlr);
563  nedges = (int)SCIPceil(scip, (SCIP_Real)SCIPdigraphGetNArcs(conflictgraph)/2);
564 
565  /* if too many conflict graph edges, the separator can be slow: delay it until no other cuts have been found */
566  if ( sepadata->maxconfsdelay >= 0 && nedges >= sepadata->maxconfsdelay )
567  {
568  int ncutsfound;
569 
570  ncutsfound = SCIPgetNCutsFound(scip);
571  if ( ncutsfound > sepadata->lastncutsfound || ! SCIPsepaWasLPDelayed(sepa) )
572  {
573  sepadata->lastncutsfound = ncutsfound;
574  *result = SCIP_DELAYED;
575  return SCIP_OKAY;
576  }
577  }
578 
579  /* check basis status */
580  for (j = 0; j < ncols; ++j)
581  {
582  if ( SCIPcolGetBasisStatus(cols[j]) == SCIP_BASESTAT_ZERO )
583  return SCIP_OKAY;
584  }
585 
586  /* check accuracy of rows */
587  for (j = 0; j < nrows; ++j)
588  {
589  SCIP_ROW* row;
590 
591  row = rows[j];
592 
593  if ( ( SCIProwGetBasisStatus(row) == SCIP_BASESTAT_UPPER && ! SCIPisEQ(scip, SCIPgetRowLPActivity(scip, row), SCIProwGetRhs(row)) )
594  || ( SCIProwGetBasisStatus(row) == SCIP_BASESTAT_LOWER && ! SCIPisEQ(scip, SCIPgetRowLPActivity(scip, row), SCIProwGetLhs(row)) ) )
595  return SCIP_OKAY;
596  }
597 
598  /* get number of SOS1 variables */
599  nsos1vars = SCIPgetNSOS1Vars(conshdlr);
600 
601  /* allocate buffer arrays */
602  SCIP_CALL( SCIPallocBufferArray(scip, &edgearray, nedges) );
603  SCIP_CALL( SCIPallocBufferArray(scip, &fixings1, nedges) );
604  SCIP_CALL( SCIPallocBufferArray(scip, &fixings2, nedges) );
605  SCIP_CALL( SCIPallocBufferArray(scip, &violationarray, nedges) );
606 
607  /* get all violated conflicts {i, j} in the conflict graph and sort them based on the degree of a violation value */
608  nrelevantedges = 0;
609  for (j = 0; j < nsos1vars; ++j)
610  {
611  SCIP_VAR* var;
612 
613  var = SCIPnodeGetVarSOS1(conflictgraph, j);
614 
616  {
617  int* succ;
618  int nsucc;
619 
620  /* get successors and number of successors */
621  nsucc = SCIPdigraphGetNSuccessors(conflictgraph, j);
622  succ = SCIPdigraphGetSuccessors(conflictgraph, j);
623 
624  for (i = 0; i < nsucc; ++i)
625  {
626  SCIP_VAR* varsucc;
627  int succind;
628 
629  succind = succ[i];
630  varsucc = SCIPnodeGetVarSOS1(conflictgraph, succind);
631  if ( SCIPvarIsActive(varsucc) && succind < j && ! SCIPisFeasZero(scip, SCIPgetSolVal(scip, NULL, varsucc) ) &&
633  {
634  fixings1[nrelevantedges] = j;
635  fixings2[nrelevantedges] = succind;
636  edgearray[nrelevantedges] = nrelevantedges;
637  violationarray[nrelevantedges++] = SCIPgetSolVal(scip, NULL, var) * SCIPgetSolVal(scip, NULL, varsucc);
638  }
639  }
640  }
641  }
642 
643  /* sort violation score values */
644  if ( nrelevantedges > 0)
645  SCIPsortDownRealInt(violationarray, edgearray, nrelevantedges);
646  else
647  {
648  SCIPfreeBufferArrayNull(scip, &violationarray);
649  SCIPfreeBufferArrayNull(scip, &fixings2);
650  SCIPfreeBufferArrayNull(scip, &fixings1);
651  SCIPfreeBufferArrayNull(scip, &edgearray);
652 
653  return SCIP_OKAY;
654  }
655  SCIPfreeBufferArrayNull(scip, &violationarray);
656 
657  /* compute maximal number of cuts */
658  if ( SCIPgetDepth(scip) == 0 )
659  maxcuts = MIN(sepadata->maxinvcutsroot, nrelevantedges);
660  else
661  maxcuts = MIN(sepadata->maxinvcuts, nrelevantedges);
662  assert( maxcuts > 0 );
663 
664  /* allocate buffer arrays */
665  SCIP_CALL( SCIPallocBufferArray(scip, &varrank, ncols) );
666  SCIP_CALL( SCIPallocBufferArray(scip, &rowsmaxval, nrows) );
667  SCIP_CALL( SCIPallocBufferArray(scip, &basisrow, ncols) );
668  SCIP_CALL( SCIPallocBufferArray(scip, &binvrow, nrows) );
669  SCIP_CALL( SCIPallocBufferArray(scip, &coef, ncols) );
670  SCIP_CALL( SCIPallocBufferArray(scip, &simplexcoefs1, ncols) );
671  SCIP_CALL( SCIPallocBufferArray(scip, &simplexcoefs2, ncols) );
672  SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, ncols) );
673  SCIP_CALL( SCIPallocBufferArray(scip, &basisind, nrows) );
674 
675  /* get basis indices */
676  SCIP_CALL( SCIPgetLPBasisInd(scip, basisind) );
677 
678  /* create vector "basisrow" with basisrow[column of non-slack basis variable] = corresponding row of B^-1;
679  * compute maximum absolute value of nonbasic row coefficients */
680  for (j = 0; j < nrows; ++j)
681  {
682  SCIP_COL** rowcols;
683  SCIP_Real* rowvals;
684  SCIP_ROW* row;
685  SCIP_Real val;
686  SCIP_Real max = 0.0;
687  int nnonz;
688 
689  /* fill basisrow vector */
690  ind = basisind[j];
691  if ( ind >= 0 )
692  basisrow[ind] = j;
693 
694  /* compute maximum absolute value of nonbasic row coefficients */
695  row = rows[j];
696  assert( row != NULL );
697  rowvals = SCIProwGetVals(row);
698  nnonz = SCIProwGetNNonz(row);
699  rowcols = SCIProwGetCols(row);
700 
701  for (i = 0; i < nnonz; ++i)
702  {
704  {
705  val = REALABS(rowvals[i]);
706  if ( SCIPisFeasGT(scip, val, max) )
707  max = REALABS(val);
708  }
709  }
710 
711  /* handle slack variable coefficient and save maximum value */
712  rowsmaxval[j] = MAX(max, 1.0);
713  }
714 
715  /* initialize variable ranks with -1 */
716  for (j = 0; j < ncols; ++j)
717  varrank[j] = -1;
718 
719  /* free buffer array */
720  SCIPfreeBufferArrayNull(scip, &basisind);
721 
722  /* for the most promising disjunctions: try to generate disjunctive cuts */
723  ndisjcuts = 0;
724  for (i = 0; i < maxcuts; ++i)
725  {
726  SCIP_Bool madeintegral;
727  SCIP_Real cutlhs1;
728  SCIP_Real cutlhs2;
729  SCIP_Real bound1;
730  SCIP_Real bound2;
731  SCIP_ROW* row = NULL;
732  SCIP_VAR* var;
733  SCIP_COL* col;
734 
735  int nonbasicnumber;
736  int cutrank = 0;
737  int edgenumber;
738  int rownnonz;
739 
740  edgenumber = edgearray[i];
741 
742  /* determine first simplex row */
743  var = SCIPnodeGetVarSOS1(conflictgraph, fixings1[edgenumber]);
744  col = SCIPvarGetCol(var);
745  ind = SCIPcolGetLPPos(col);
746  assert( ind >= 0 );
747  assert( SCIPcolGetBasisStatus(col) == SCIP_BASESTAT_BASIC );
748 
749  /* get the 'ind'th row of B^-1 and B^-1 \cdot A */
750  SCIP_CALL( SCIPgetLPBInvRow(scip, basisrow[ind], binvrow, NULL, NULL) );
751  SCIP_CALL( SCIPgetLPBInvARow(scip, basisrow[ind], binvrow, coef, NULL, NULL) );
752 
753  /* get the simplex-coefficients of the non-basic variables */
754  SCIP_CALL( getSimplexCoefficients(scip, rows, nrows, cols, ncols, coef, binvrow, simplexcoefs1, &nonbasicnumber) );
755 
756  /* get rank of variable if not known already */
757  if ( varrank[ind] < 0 )
758  varrank[ind] = getVarRank(scip, binvrow, rowsmaxval, sepadata->maxweightrange, rows, nrows);
759  cutrank = MAX(cutrank, varrank[ind]);
760 
761  /* get right hand side and bound of simplex talbeau row */
762  cutlhs1 = SCIPcolGetPrimsol(col);
763  if ( SCIPisFeasPositive(scip, cutlhs1) )
764  bound1 = SCIPcolGetUb(col);
765  else
766  bound1 = SCIPcolGetLb(col);
767 
768 
769  /* determine second simplex row */
770  var = SCIPnodeGetVarSOS1(conflictgraph, fixings2[edgenumber]);
771  col = SCIPvarGetCol(var);
772  ind = SCIPcolGetLPPos(col);
773  assert( ind >= 0 );
774  assert( SCIPcolGetBasisStatus(col) == SCIP_BASESTAT_BASIC );
775 
776  /* get the 'ind'th row of B^-1 and B^-1 \cdot A */
777  SCIP_CALL( SCIPgetLPBInvRow(scip, basisrow[ind], binvrow, NULL, NULL) );
778  SCIP_CALL( SCIPgetLPBInvARow(scip, basisrow[ind], binvrow, coef, NULL, NULL) );
779 
780  /* get the simplex-coefficients of the non-basic variables */
781  SCIP_CALL( getSimplexCoefficients(scip, rows, nrows, cols, ncols, coef, binvrow, simplexcoefs2, &nonbasicnumber) );
782 
783  /* get rank of variable if not known already */
784  if ( varrank[ind] < 0 )
785  varrank[ind] = getVarRank(scip, binvrow, rowsmaxval, sepadata->maxweightrange, rows, nrows);
786  cutrank = MAX(cutrank, varrank[ind]);
787 
788  /* get right hand side and bound of simplex talbeau row */
789  cutlhs2 = SCIPcolGetPrimsol(col);
790  if ( SCIPisFeasPositive(scip, cutlhs2) )
791  bound2 = SCIPcolGetUb(col);
792  else
793  bound2 = SCIPcolGetLb(col);
794 
795  /* add coefficients to cut */
796  SCIP_CALL( generateDisjCutSOS1(scip, sepa, rows, nrows, cols, ncols, ndisjcuts, MAKECONTINTEGRAL, sepadata->strengthen, cutlhs1, cutlhs2, bound1, bound2, simplexcoefs1, simplexcoefs2, cutcoefs, &row, &madeintegral) );
797  if ( row == NULL )
798  continue;
799 
800  /* raise cutrank for present cut */
801  ++cutrank;
802 
803  /* check if there are numerical evidences */
804  if ( ( madeintegral && ( sepadata->maxrankintegral == -1 || cutrank <= sepadata->maxrankintegral ) )
805  || ( ! madeintegral && ( sepadata->maxrank == -1 || cutrank <= sepadata->maxrank ) ) )
806  {
807  /* possibly add cut to LP if it is useful; in case the lhs of the cut is minus infinity (due to scaling) the cut is useless */
808  rownnonz = SCIProwGetNNonz(row);
809  if ( rownnonz > 0 && ! SCIPisInfinity(scip, -SCIProwGetLhs(row)) && ! SCIProwIsInLP(row) && SCIPisCutEfficacious(scip, NULL, row) )
810  {
811  SCIP_Bool infeasible;
812 
813  /* set cut rank */
814  SCIProwChgRank(row, cutrank);
815 
816  /* add cut */
817  SCIP_CALL( SCIPaddRow(scip, row, FALSE, &infeasible) );
818  SCIPdebug( SCIP_CALL( SCIPprintRow(scip, row, NULL) ) );
819  if ( infeasible )
820  {
821  *result = SCIP_CUTOFF;
822  break;
823  }
824  ++ndisjcuts;
825  }
826  }
827 
828  /* release row */
829  SCIP_CALL( SCIPreleaseRow(scip, &row) );
830  }
831 
832  /* save total number of cuts found so far */
833  sepadata->lastncutsfound = SCIPgetNCutsFound(scip);
834 
835  /* evaluate the result of the separation */
836  if ( *result != SCIP_CUTOFF )
837  {
838  if ( ndisjcuts > 0 )
839  *result = SCIP_SEPARATED;
840  else
841  *result = SCIP_DIDNOTFIND;
842  }
843 
844  SCIPdebugMsg(scip, "Number of found disjunctive cuts: %d.\n", ndisjcuts);
845 
846  /* free buffer arrays */
847  SCIPfreeBufferArrayNull(scip, &cutcoefs);
848  SCIPfreeBufferArrayNull(scip, &simplexcoefs2);
849  SCIPfreeBufferArrayNull(scip, &simplexcoefs1);
850  SCIPfreeBufferArrayNull(scip, &coef);
851  SCIPfreeBufferArrayNull(scip, &binvrow);
852  SCIPfreeBufferArrayNull(scip, &basisrow);
853  SCIPfreeBufferArrayNull(scip, &fixings2);
854  SCIPfreeBufferArrayNull(scip, &fixings1);
855  SCIPfreeBufferArrayNull(scip, &edgearray);
856  SCIPfreeBufferArrayNull(scip, &rowsmaxval);
857  SCIPfreeBufferArrayNull(scip, &varrank);
858 
859  return SCIP_OKAY;
860 }
861 
862 
863 /** creates the disjunctive cut separator and includes it in SCIP */
865  SCIP* scip /**< SCIP data structure */
866  )
867 {
868  SCIP_SEPADATA* sepadata = NULL;
869  SCIP_SEPA* sepa = NULL;
870 
871  /* create separator data */
872  SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) );
873  sepadata->conshdlr = NULL;
874  sepadata->lastncutsfound = 0;
875 
876  /* include separator */
878  SEPA_USESSUBSCIP, SEPA_DELAY, sepaExeclpDisjunctive, NULL, sepadata) );
879 
880  assert( sepa != NULL );
881 
882  /* set non fundamental callbacks via setter functions */
883  SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyDisjunctive) );
884  SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeDisjunctive) );
885  SCIP_CALL( SCIPsetSepaInitsol(scip, sepa, sepaInitsolDisjunctive) );
886 
887  /* add separator parameters */
888  SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/strengthen",
889  "strengthen cut if integer variables are present.",
890  &sepadata->strengthen, TRUE, DEFAULT_STRENGTHEN, NULL, NULL) );
891 
892  SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxdepth",
893  "node depth of separating bipartite disjunctive cuts (-1: no limit)",
894  &sepadata->maxdepth, TRUE, DEFAULT_MAXDEPTH, -1, INT_MAX, NULL, NULL) );
895 
896  SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxrounds",
897  "maximal number of separation rounds per iteration in a branching node (-1: no limit)",
898  &sepadata->maxrounds, TRUE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
899 
900  SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxroundsroot",
901  "maximal number of separation rounds in the root node (-1: no limit)",
902  &sepadata->maxroundsroot, TRUE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
903 
904  SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxinvcuts",
905  "maximal number of cuts investigated per iteration in a branching node",
906  &sepadata->maxinvcuts, TRUE, DEFAULT_MAXINVCUTS, 0, INT_MAX, NULL, NULL) );
907 
908  SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxinvcutsroot",
909  "maximal number of cuts investigated per iteration in the root node",
910  &sepadata->maxinvcutsroot, TRUE, DEFAULT_MAXINVCUTSROOT, 0, INT_MAX, NULL, NULL) );
911 
912  SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxconfsdelay",
913  "delay separation if number of conflict graph edges is larger than predefined value (-1: no limit)",
914  &sepadata->maxconfsdelay, TRUE, DEFAULT_MAXCONFSDELAY, -1, INT_MAX, NULL, NULL) );
915 
916  SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxrank",
917  "maximal rank of a disj. cut that could not be scaled to integral coefficients (-1: unlimited)",
918  &sepadata->maxrank, FALSE, DEFAULT_MAXRANK, -1, INT_MAX, NULL, NULL) );
919 
920  SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxrankintegral",
921  "maximal rank of a disj. cut that could be scaled to integral coefficients (-1: unlimited)",
922  &sepadata->maxrankintegral, FALSE, DEFAULT_MAXRANKINTEGRAL, -1, INT_MAX, NULL, NULL) );
923 
924  SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/maxweightrange",
925  "maximal valid range max(|weights|)/min(|weights|) of row weights",
926  &sepadata->maxweightrange, TRUE, DEFAULT_MAXWEIGHTRANGE, 1.0, SCIP_REAL_MAX, NULL, NULL) );
927 
928  return SCIP_OKAY;
929 }
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:47357
SCIP_RETCODE SCIPgetLPBInvRow(SCIP *scip, int r, SCIP_Real *coefs, int *inds, int *ninds)
Definition: scip.c:29778
#define DEFAULT_MAXINVCUTS
static SCIP_DECL_SEPAEXECLP(sepaExeclpDisjunctive)
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30607
static SCIP_DECL_SEPAEXITSOL(sepaInitsolDisjunctive)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:6604
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30630
#define DEFAULT_MAXINVCUTSROOT
#define SCIP_MAXSTRLEN
Definition: def.h:259
SCIP_BASESTAT SCIPcolGetBasisStatus(SCIP_COL *col)
Definition: lp.c:16240
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:30662
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:16402
int * SCIPdigraphGetSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7305
#define SEPA_PRIORITY
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:16481
#define FALSE
Definition: def.h:64
SCIP_Bool SCIPcolIsIntegral(SCIP_COL *col)
Definition: lp.c:16271
SCIP_Real SCIPcolGetUb(SCIP_COL *col)
Definition: lp.c:16182
SCIP_BASESTAT SCIProwGetBasisStatus(SCIP_ROW *row)
Definition: lp.c:16529
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:47022
int SCIPgetNSOS1Vars(SCIP_CONSHDLR *conshdlr)
Definition: cons_sos1.c:10644
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10011
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:47094
#define TRUE
Definition: def.h:63
#define SCIPdebug(x)
Definition: pub_message.h:74
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition: sepa.c:646
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define DEFAULT_MAXWEIGHTRANGE
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:22602
disjunctive cut separator
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46957
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:22585
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
Definition: scip.c:29556
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip.c:7427
#define SCIPdebugMsg
Definition: scip.h:455
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.c:4265
SCIP_Real SCIPepsilon(SCIP *scip)
Definition: scip.c:46409
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
Definition: sepa.c:557
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition: lp.c:16692
#define SEPA_MAXBOUNDDIST
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip.c:29731
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip.c:34522
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
Definition: lp.c:16205
#define MAKECONTINTEGRAL
int SCIPgetNCutsFound(SCIP *scip)
Definition: scip.c:42896
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip.h:22633
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
Definition: sepa.c:773
SCIP_Real SCIPcolGetLb(SCIP_COL *col)
Definition: lp.c:16172
static SCIP_DECL_SEPAFREE(sepaFreeDisjunctive)
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
Definition: sepa.c:567
SCIP_RETCODE SCIPincludeSepaDisjunctive(SCIP *scip)
#define REALABS(x)
Definition: def.h:173
SCIP_RETCODE SCIPsetSepaInitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAINITSOL((*sepainitsol)))
Definition: scip.c:7491
#define DEFAULT_MAXCONFSDELAY
#define SCIP_CALL(x)
Definition: def.h:350
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47331
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47318
#define SEPA_DESC
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:16491
SCIP_Real SCIPgetRowLPActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30954
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip.c:34655
SCIP_DIGRAPH * SCIPgetConflictgraphSOS1(SCIP_CONSHDLR *conshdlr)
Definition: cons_sos1.c:10622
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:16427
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4515
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.c:7385
SCIP_Bool SCIPsepaWasLPDelayed(SCIP_SEPA *sepa)
Definition: sepa.c:883
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:22620
SCIP_RETCODE SCIPgetLPBInvARow(SCIP *scip, int r, SCIP_Real *binvrow, SCIP_Real *coefs, int *inds, int *ninds)
Definition: scip.c:29849
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:16437
static SCIP_DECL_SEPACOPY(sepaCopyDisjunctive)
int SCIPdigraphGetNSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7290
#define SCIP_Bool
Definition: def.h:61
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:29287
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:43039
#define SEPA_FREQ
#define MAX(x, y)
Definition: tclique_def.h:75
int SCIPdigraphGetNArcs(SCIP_DIGRAPH *digraph)
Definition: misc.c:7272
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.c:30425
static int getVarRank(SCIP *scip, SCIP_Real *binvrow, SCIP_Real *rowsmaxval, SCIP_Real maxweightrange, SCIP_ROW **rows, int nrows)
SCIP_VAR * SCIPnodeGetVarSOS1(SCIP_DIGRAPH *conflictgraph, int node)
Definition: cons_sos1.c:10721
#define DEFAULT_MAXROUNDS
#define DEFAULT_STRENGTHEN
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:16990
SCIP_RETCODE SCIPgetLPBasisInd(SCIP *scip, int *basisind)
Definition: scip.c:29750
static SCIP_RETCODE getSimplexCoefficients(SCIP *scip, SCIP_ROW **rows, int nrows, SCIP_COL **cols, int ncols, SCIP_Real *coef, SCIP_Real *binvrow, SCIP_Real *simplexcoefs, int *nonbasicnumber)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:47033
#define SEPA_NAME
int SCIProwGetRank(SCIP_ROW *row)
Definition: lp.c:16570
#define SCIP_REAL_MAX
Definition: def.h:150
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:16447
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip.c:30534
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip.c:7443
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46996
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:16251
#define DEFAULT_MAXROUNDSROOT
void SCIProwChgRank(SCIP_ROW *row, int rank)
Definition: lp.c:16703
static SCIP_RETCODE generateDisjCutSOS1(SCIP *scip, SCIP_SEPA *sepa, SCIP_ROW **rows, int nrows, SCIP_COL **cols, int ncols, int ndisjcuts, SCIP_Bool scale, SCIP_Bool strengthen, SCIP_Real cutlhs1, SCIP_Real cutlhs2, SCIP_Real bound1, SCIP_Real bound2, SCIP_Real *simplexcoefs1, SCIP_Real *simplexcoefs2, SCIP_Real *cutcoefs, SCIP_ROW **row, SCIP_Bool *madeintegral)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip.c:47369
#define SCIP_Real
Definition: def.h:149
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1145
constraint handler for SOS type 1 constraints
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip.c:31154
#define DEFAULT_MAXRANKINTEGRAL
#define SCIP_Longint
Definition: def.h:134
#define SEPA_DELAY
SCIP_Real SCIPsumepsilon(SCIP *scip)
Definition: scip.c:46423
#define DEFAULT_MAXRANK
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip.c:29634
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
Definition: scip.c:47155
SCIP_Longint SCIPgetNLPs(SCIP *scip)
Definition: scip.c:42308
int SCIPcolGetLPPos(SCIP_COL *col)
Definition: lp.c:16292
SCIP_RETCODE SCIPmakeRowIntegral(SCIP *scip, SCIP_ROW *row, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Longint maxdnom, SCIP_Real maxscale, SCIP_Bool usecontvars, SCIP_Bool *success)
Definition: scip.c:30805
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38905
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.c:4321
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:47143
struct SCIP_SepaData SCIP_SEPADATA
Definition: type_sepa.h:38
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.c:4239
#define DEFAULT_MAXDEPTH
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:16949
#define SEPA_USESSUBSCIP