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  /* only generate disjunctive cuts if we are not close to terminating */
509  if ( SCIPisStopped(scip) )
510  return SCIP_OKAY;
511 
512  /* only generate disjunctive cuts if an optimal LP solution is at hand */
514  return SCIP_OKAY;
515 
516  /* only generate disjunctive cuts if the LP solution is basic */
517  if ( ! SCIPisLPSolBasic(scip) )
518  return SCIP_OKAY;
519 
520  /* get LP data */
521  SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
522  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
523 
524  /* return if LP has no columns or no rows */
525  if ( ncols == 0 || nrows == 0 )
526  return SCIP_OKAY;
527 
528  assert( cols != NULL );
529  assert( rows != NULL );
530 
531  /* get sepa data */
532  sepadata = SCIPsepaGetData(sepa);
533  assert( sepadata != NULL );
534 
535  /* get constraint handler */
536  conshdlr = sepadata->conshdlr;
537  if ( conshdlr == NULL )
538  return SCIP_OKAY;
539 
540  /* get number of constraints */
541  nconss = SCIPconshdlrGetNConss(conshdlr);
542  if ( nconss == 0 )
543  return SCIP_OKAY;
544 
545  /* check for maxdepth < depth, maxinvcutsroot = 0 and maxinvcuts = 0 */
546  depth = SCIPgetDepth(scip);
547  if ( ( sepadata->maxdepth >= 0 && sepadata->maxdepth < depth )
548  || ( depth == 0 && sepadata->maxinvcutsroot == 0 )
549  || ( depth > 0 && sepadata->maxinvcuts == 0 ) )
550  return SCIP_OKAY;
551 
552  /* only call the cut separator a given number of times at each node */
553  ncalls = SCIPsepaGetNCallsAtNode(sepa);
554  if ( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
555  || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
556  return SCIP_OKAY;
557 
558  /* get conflict graph and number of conflict graph edges (note that the digraph arcs were added in both directions) */
559  conflictgraph = SCIPgetConflictgraphSOS1(conshdlr);
560  nedges = (int)SCIPceil(scip, (SCIP_Real)SCIPdigraphGetNArcs(conflictgraph)/2);
561 
562  /* if too many conflict graph edges, the separator can be slow: delay it until no other cuts have been found */
563  if ( sepadata->maxconfsdelay >= 0 && nedges >= sepadata->maxconfsdelay )
564  {
565  int ncutsfound;
566 
567  ncutsfound = SCIPgetNCutsFound(scip);
568  if ( ncutsfound > sepadata->lastncutsfound || ! SCIPsepaWasLPDelayed(sepa) )
569  {
570  sepadata->lastncutsfound = ncutsfound;
571  *result = SCIP_DELAYED;
572  return SCIP_OKAY;
573  }
574  }
575 
576  /* check basis status */
577  for (j = 0; j < ncols; ++j)
578  {
579  if ( SCIPcolGetBasisStatus(cols[j]) == SCIP_BASESTAT_ZERO )
580  return SCIP_OKAY;
581  }
582 
583  /* check accuracy of rows */
584  for (j = 0; j < nrows; ++j)
585  {
586  SCIP_ROW* row;
587 
588  row = rows[j];
589 
590  if ( ( SCIProwGetBasisStatus(row) == SCIP_BASESTAT_UPPER && ! SCIPisEQ(scip, SCIPgetRowLPActivity(scip, row), SCIProwGetRhs(row)) )
591  || ( SCIProwGetBasisStatus(row) == SCIP_BASESTAT_LOWER && ! SCIPisEQ(scip, SCIPgetRowLPActivity(scip, row), SCIProwGetLhs(row)) ) )
592  return SCIP_OKAY;
593  }
594 
595  /* get number of SOS1 variables */
596  nsos1vars = SCIPgetNSOS1Vars(conshdlr);
597 
598  /* allocate buffer arrays */
599  SCIP_CALL( SCIPallocBufferArray(scip, &edgearray, nedges) );
600  SCIP_CALL( SCIPallocBufferArray(scip, &fixings1, nedges) );
601  SCIP_CALL( SCIPallocBufferArray(scip, &fixings2, nedges) );
602  SCIP_CALL( SCIPallocBufferArray(scip, &violationarray, nedges) );
603 
604  /* get all violated conflicts {i, j} in the conflict graph and sort them based on the degree of a violation value */
605  nrelevantedges = 0;
606  for (j = 0; j < nsos1vars; ++j)
607  {
608  SCIP_VAR* var;
609 
610  var = SCIPnodeGetVarSOS1(conflictgraph, j);
611 
613  {
614  int* succ;
615  int nsucc;
616 
617  /* get successors and number of successors */
618  nsucc = SCIPdigraphGetNSuccessors(conflictgraph, j);
619  succ = SCIPdigraphGetSuccessors(conflictgraph, j);
620 
621  for (i = 0; i < nsucc; ++i)
622  {
623  SCIP_VAR* varsucc;
624  int succind;
625 
626  succind = succ[i];
627  varsucc = SCIPnodeGetVarSOS1(conflictgraph, succind);
628  if ( SCIPvarIsActive(varsucc) && succind < j && ! SCIPisFeasZero(scip, SCIPgetSolVal(scip, NULL, varsucc) ) &&
630  {
631  fixings1[nrelevantedges] = j;
632  fixings2[nrelevantedges] = succind;
633  edgearray[nrelevantedges] = nrelevantedges;
634  violationarray[nrelevantedges++] = SCIPgetSolVal(scip, NULL, var) * SCIPgetSolVal(scip, NULL, varsucc);
635  }
636  }
637  }
638  }
639 
640  /* sort violation score values */
641  if ( nrelevantedges > 0)
642  SCIPsortDownRealInt(violationarray, edgearray, nrelevantedges);
643  else
644  {
645  SCIPfreeBufferArrayNull(scip, &violationarray);
646  SCIPfreeBufferArrayNull(scip, &fixings2);
647  SCIPfreeBufferArrayNull(scip, &fixings1);
648  SCIPfreeBufferArrayNull(scip, &edgearray);
649 
650  return SCIP_OKAY;
651  }
652  SCIPfreeBufferArrayNull(scip, &violationarray);
653 
654  /* compute maximal number of cuts */
655  if ( SCIPgetDepth(scip) == 0 )
656  maxcuts = MIN(sepadata->maxinvcutsroot, nrelevantedges);
657  else
658  maxcuts = MIN(sepadata->maxinvcuts, nrelevantedges);
659  assert( maxcuts > 0 );
660 
661  /* allocate buffer arrays */
662  SCIP_CALL( SCIPallocBufferArray(scip, &varrank, ncols) );
663  SCIP_CALL( SCIPallocBufferArray(scip, &rowsmaxval, nrows) );
664  SCIP_CALL( SCIPallocBufferArray(scip, &basisrow, ncols) );
665  SCIP_CALL( SCIPallocBufferArray(scip, &binvrow, nrows) );
666  SCIP_CALL( SCIPallocBufferArray(scip, &coef, ncols) );
667  SCIP_CALL( SCIPallocBufferArray(scip, &simplexcoefs1, ncols) );
668  SCIP_CALL( SCIPallocBufferArray(scip, &simplexcoefs2, ncols) );
669  SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, ncols) );
670  SCIP_CALL( SCIPallocBufferArray(scip, &basisind, nrows) );
671 
672  /* get basis indices */
673  SCIP_CALL( SCIPgetLPBasisInd(scip, basisind) );
674 
675  /* create vector "basisrow" with basisrow[column of non-slack basis variable] = corresponding row of B^-1;
676  * compute maximum absolute value of nonbasic row coefficients */
677  for (j = 0; j < nrows; ++j)
678  {
679  SCIP_COL** rowcols;
680  SCIP_Real* rowvals;
681  SCIP_ROW* row;
682  SCIP_Real val;
683  SCIP_Real max = 0.0;
684  int nnonz;
685 
686  /* fill basisrow vector */
687  ind = basisind[j];
688  if ( ind >= 0 )
689  basisrow[ind] = j;
690 
691  /* compute maximum absolute value of nonbasic row coefficients */
692  row = rows[j];
693  assert( row != NULL );
694  rowvals = SCIProwGetVals(row);
695  nnonz = SCIProwGetNNonz(row);
696  rowcols = SCIProwGetCols(row);
697 
698  for (i = 0; i < nnonz; ++i)
699  {
701  {
702  val = REALABS(rowvals[i]);
703  if ( SCIPisFeasGT(scip, val, max) )
704  max = REALABS(val);
705  }
706  }
707 
708  /* handle slack variable coefficient and save maximum value */
709  rowsmaxval[j] = MAX(max, 1.0);
710  }
711 
712  /* initialize variable ranks with -1 */
713  for (j = 0; j < ncols; ++j)
714  varrank[j] = -1;
715 
716  /* free buffer array */
717  SCIPfreeBufferArrayNull(scip, &basisind);
718 
719  /* for the most promising disjunctions: try to generate disjunctive cuts */
720  ndisjcuts = 0;
721  for (i = 0; i < maxcuts; ++i)
722  {
723  SCIP_Bool madeintegral;
724  SCIP_Real cutlhs1;
725  SCIP_Real cutlhs2;
726  SCIP_Real bound1;
727  SCIP_Real bound2;
728  SCIP_ROW* row = NULL;
729  SCIP_VAR* var;
730  SCIP_COL* col;
731 
732  int nonbasicnumber;
733  int cutrank = 0;
734  int edgenumber;
735  int rownnonz;
736 
737  edgenumber = edgearray[i];
738 
739  /* determine first simplex row */
740  var = SCIPnodeGetVarSOS1(conflictgraph, fixings1[edgenumber]);
741  col = SCIPvarGetCol(var);
742  ind = SCIPcolGetLPPos(col);
743  assert( ind >= 0 );
744  assert( SCIPcolGetBasisStatus(col) == SCIP_BASESTAT_BASIC );
745 
746  /* get the 'ind'th row of B^-1 and B^-1 \cdot A */
747  SCIP_CALL( SCIPgetLPBInvRow(scip, basisrow[ind], binvrow, NULL, NULL) );
748  SCIP_CALL( SCIPgetLPBInvARow(scip, basisrow[ind], binvrow, coef, NULL, NULL) );
749 
750  /* get the simplex-coefficients of the non-basic variables */
751  SCIP_CALL( getSimplexCoefficients(scip, rows, nrows, cols, ncols, coef, binvrow, simplexcoefs1, &nonbasicnumber) );
752 
753  /* get rank of variable if not known already */
754  if ( varrank[ind] < 0 )
755  varrank[ind] = getVarRank(scip, binvrow, rowsmaxval, sepadata->maxweightrange, rows, nrows);
756  cutrank = MAX(cutrank, varrank[ind]);
757 
758  /* get right hand side and bound of simplex talbeau row */
759  cutlhs1 = SCIPcolGetPrimsol(col);
760  if ( SCIPisFeasPositive(scip, cutlhs1) )
761  bound1 = SCIPcolGetUb(col);
762  else
763  bound1 = SCIPcolGetLb(col);
764 
765 
766  /* determine second simplex row */
767  var = SCIPnodeGetVarSOS1(conflictgraph, fixings2[edgenumber]);
768  col = SCIPvarGetCol(var);
769  ind = SCIPcolGetLPPos(col);
770  assert( ind >= 0 );
771  assert( SCIPcolGetBasisStatus(col) == SCIP_BASESTAT_BASIC );
772 
773  /* get the 'ind'th row of B^-1 and B^-1 \cdot A */
774  SCIP_CALL( SCIPgetLPBInvRow(scip, basisrow[ind], binvrow, NULL, NULL) );
775  SCIP_CALL( SCIPgetLPBInvARow(scip, basisrow[ind], binvrow, coef, NULL, NULL) );
776 
777  /* get the simplex-coefficients of the non-basic variables */
778  SCIP_CALL( getSimplexCoefficients(scip, rows, nrows, cols, ncols, coef, binvrow, simplexcoefs2, &nonbasicnumber) );
779 
780  /* get rank of variable if not known already */
781  if ( varrank[ind] < 0 )
782  varrank[ind] = getVarRank(scip, binvrow, rowsmaxval, sepadata->maxweightrange, rows, nrows);
783  cutrank = MAX(cutrank, varrank[ind]);
784 
785  /* get right hand side and bound of simplex talbeau row */
786  cutlhs2 = SCIPcolGetPrimsol(col);
787  if ( SCIPisFeasPositive(scip, cutlhs2) )
788  bound2 = SCIPcolGetUb(col);
789  else
790  bound2 = SCIPcolGetLb(col);
791 
792  /* add coefficients to cut */
793  SCIP_CALL( generateDisjCutSOS1(scip, sepa, rows, nrows, cols, ncols, ndisjcuts, MAKECONTINTEGRAL, sepadata->strengthen, cutlhs1, cutlhs2, bound1, bound2, simplexcoefs1, simplexcoefs2, cutcoefs, &row, &madeintegral) );
794  if ( row == NULL )
795  continue;
796 
797  /* raise cutrank for present cut */
798  ++cutrank;
799 
800  /* check if there are numerical evidences */
801  if ( ( madeintegral && ( sepadata->maxrankintegral == -1 || cutrank <= sepadata->maxrankintegral ) )
802  || ( ! madeintegral && ( sepadata->maxrank == -1 || cutrank <= sepadata->maxrank ) ) )
803  {
804  /* 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 */
805  rownnonz = SCIProwGetNNonz(row);
806  if ( rownnonz > 0 && ! SCIPisInfinity(scip, -SCIProwGetLhs(row)) && ! SCIProwIsInLP(row) && SCIPisCutEfficacious(scip, NULL, row) )
807  {
808  SCIP_Bool infeasible;
809 
810  /* set cut rank */
811  SCIProwChgRank(row, cutrank);
812 
813  /* add cut */
814  SCIP_CALL( SCIPaddCut(scip, NULL, row, FALSE, &infeasible) );
815  SCIPdebug( SCIP_CALL( SCIPprintRow(scip, row, NULL) ) );
816  if ( infeasible )
817  {
818  *result = SCIP_CUTOFF;
819  break;
820  }
821  ++ndisjcuts;
822  }
823  }
824 
825  /* release row */
826  SCIP_CALL( SCIPreleaseRow(scip, &row) );
827  }
828 
829  /* save total number of cuts found so far */
830  sepadata->lastncutsfound = SCIPgetNCutsFound(scip);
831 
832  /* evaluate the result of the separation */
833  if ( *result != SCIP_CUTOFF )
834  {
835  if ( ndisjcuts > 0 )
836  *result = SCIP_SEPARATED;
837  else
838  *result = SCIP_DIDNOTFIND;
839  }
840 
841  SCIPdebugMsg(scip, "Number of found disjunctive cuts: %d.\n", ndisjcuts);
842 
843  /* free buffer arrays */
844  SCIPfreeBufferArrayNull(scip, &cutcoefs);
845  SCIPfreeBufferArrayNull(scip, &simplexcoefs2);
846  SCIPfreeBufferArrayNull(scip, &simplexcoefs1);
847  SCIPfreeBufferArrayNull(scip, &coef);
848  SCIPfreeBufferArrayNull(scip, &binvrow);
849  SCIPfreeBufferArrayNull(scip, &basisrow);
850  SCIPfreeBufferArrayNull(scip, &fixings2);
851  SCIPfreeBufferArrayNull(scip, &fixings1);
852  SCIPfreeBufferArrayNull(scip, &edgearray);
853  SCIPfreeBufferArrayNull(scip, &rowsmaxval);
854  SCIPfreeBufferArrayNull(scip, &varrank);
855 
856  return SCIP_OKAY;
857 }
858 
859 
860 /** creates the disjunctive cut separator and includes it in SCIP */
862  SCIP* scip /**< SCIP data structure */
863  )
864 {
865  SCIP_SEPADATA* sepadata = NULL;
866  SCIP_SEPA* sepa = NULL;
867 
868  /* create separator data */
869  SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) );
870  sepadata->conshdlr = NULL;
871  sepadata->lastncutsfound = 0;
872 
873  /* include separator */
875  SEPA_USESSUBSCIP, SEPA_DELAY, sepaExeclpDisjunctive, NULL, sepadata) );
876 
877  assert( sepa != NULL );
878 
879  /* set non fundamental callbacks via setter functions */
880  SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyDisjunctive) );
881  SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeDisjunctive) );
882  SCIP_CALL( SCIPsetSepaInitsol(scip, sepa, sepaInitsolDisjunctive) );
883 
884  /* add separator parameters */
885  SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/strengthen",
886  "strengthen cut if integer variables are present.",
887  &sepadata->strengthen, TRUE, DEFAULT_STRENGTHEN, NULL, NULL) );
888 
889  SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxdepth",
890  "node depth of separating bipartite disjunctive cuts (-1: no limit)",
891  &sepadata->maxdepth, TRUE, DEFAULT_MAXDEPTH, -1, INT_MAX, NULL, NULL) );
892 
893  SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxrounds",
894  "maximal number of separation rounds per iteration in a branching node (-1: no limit)",
895  &sepadata->maxrounds, TRUE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
896 
897  SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxroundsroot",
898  "maximal number of separation rounds in the root node (-1: no limit)",
899  &sepadata->maxroundsroot, TRUE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
900 
901  SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxinvcuts",
902  "maximal number of cuts investigated per iteration in a branching node",
903  &sepadata->maxinvcuts, TRUE, DEFAULT_MAXINVCUTS, 0, INT_MAX, NULL, NULL) );
904 
905  SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxinvcutsroot",
906  "maximal number of cuts investigated per iteration in the root node",
907  &sepadata->maxinvcutsroot, TRUE, DEFAULT_MAXINVCUTSROOT, 0, INT_MAX, NULL, NULL) );
908 
909  SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxconfsdelay",
910  "delay separation if number of conflict graph edges is larger than predefined value (-1: no limit)",
911  &sepadata->maxconfsdelay, TRUE, DEFAULT_MAXCONFSDELAY, -1, INT_MAX, NULL, NULL) );
912 
913  SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxrank",
914  "maximal rank of a disj. cut that could not be scaled to integral coefficients (-1: unlimited)",
915  &sepadata->maxrank, FALSE, DEFAULT_MAXRANK, -1, INT_MAX, NULL, NULL) );
916 
917  SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxrankintegral",
918  "maximal rank of a disj. cut that could be scaled to integral coefficients (-1: unlimited)",
919  &sepadata->maxrankintegral, FALSE, DEFAULT_MAXRANKINTEGRAL, -1, INT_MAX, NULL, NULL) );
920 
921  SCIP_CALL( SCIPaddRealParam(scip, "separating/" SEPA_NAME "/maxweightrange",
922  "maximal valid range max(|weights|)/min(|weights|) of row weights",
923  &sepadata->maxweightrange, TRUE, DEFAULT_MAXWEIGHTRANGE, 1.0, SCIP_REAL_MAX, NULL, NULL) );
924 
925  return SCIP_OKAY;
926 }
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:46151
SCIP_RETCODE SCIPgetLPBInvRow(SCIP *scip, int r, SCIP_Real *coefs, int *inds, int *ninds)
Definition: scip.c:29309
#define DEFAULT_MAXINVCUTS
static SCIP_DECL_SEPAEXECLP(sepaExeclpDisjunctive)
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30233
static SCIP_DECL_SEPAEXITSOL(sepaInitsolDisjunctive)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:6541
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30256
#define DEFAULT_MAXINVCUTSROOT
#define SCIP_MAXSTRLEN
Definition: def.h:215
SCIP_BASESTAT SCIPcolGetBasisStatus(SCIP_COL *col)
Definition: lp.c:16070
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:30288
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:16232
int * SCIPdigraphGetSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:6817
#define SEPA_PRIORITY
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:16311
#define FALSE
Definition: def.h:64
SCIP_Bool SCIPcolIsIntegral(SCIP_COL *col)
Definition: lp.c:16101
SCIP_Real SCIPcolGetUb(SCIP_COL *col)
Definition: lp.c:16012
SCIP_BASESTAT SCIProwGetBasisStatus(SCIP_ROW *row)
Definition: lp.c:16359
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:45816
int SCIPgetNSOS1Vars(SCIP_CONSHDLR *conshdlr)
Definition: cons_sos1.c:10626
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:9340
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:45888
#define TRUE
Definition: def.h:63
#define SCIPdebug(x)
Definition: pub_message.h:74
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition: sepa.c:632
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define DEFAULT_MAXWEIGHTRANGE
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21907
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:45751
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21890
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
Definition: scip.c:29087
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip.c:7367
#define SCIPdebugMsg
Definition: scip.h:451
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:4202
SCIP_Real SCIPepsilon(SCIP *scip)
Definition: scip.c:45246
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
Definition: sepa.c:543
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition: lp.c:16522
#define SEPA_MAXBOUNDDIST
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip.c:29262
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip.c:33761
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
Definition: lp.c:16035
#define MAKECONTINTEGRAL
int SCIPgetNCutsFound(SCIP *scip)
Definition: scip.c:41951
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip.h:21938
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
Definition: sepa.c:759
SCIP_Real SCIPcolGetLb(SCIP_COL *col)
Definition: lp.c:16002
static SCIP_DECL_SEPAFREE(sepaFreeDisjunctive)
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
Definition: sepa.c:553
SCIP_RETCODE SCIPincludeSepaDisjunctive(SCIP *scip)
#define NULL
Definition: lpi_spx1.cpp:137
#define REALABS(x)
Definition: def.h:159
SCIP_RETCODE SCIPsetSepaInitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAINITSOL((*sepainitsol)))
Definition: scip.c:7431
#define DEFAULT_MAXCONFSDELAY
#define SCIP_CALL(x)
Definition: def.h:306
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46125
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46112
#define SEPA_DESC
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:16321
SCIP_Real SCIPgetRowLPActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30562
SCIP_DIGRAPH * SCIPgetConflictgraphSOS1(SCIP_CONSHDLR *conshdlr)
Definition: cons_sos1.c:10604
SCIP_RETCODE SCIPaddCut(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip.c:33869
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition: lp.c:16257
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:7325
SCIP_Bool SCIPsepaWasLPDelayed(SCIP_SEPA *sepa)
Definition: sepa.c:869
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21925
SCIP_RETCODE SCIPgetLPBInvARow(SCIP *scip, int r, SCIP_Real *binvrow, SCIP_Real *coefs, int *inds, int *ninds)
Definition: scip.c:29380
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition: lp.c:16267
static SCIP_DECL_SEPACOPY(sepaCopyDisjunctive)
int SCIPdigraphGetNSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:6802
#define SCIP_Bool
Definition: def.h:61
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:28854
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:42094
#define SEPA_FREQ
#define MAX(x, y)
Definition: tclique_def.h:75
int SCIPdigraphGetNArcs(SCIP_DIGRAPH *digraph)
Definition: misc.c:6784
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:30051
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:10703
#define DEFAULT_MAXROUNDS
#define DEFAULT_STRENGTHEN
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:16880
SCIP_RETCODE SCIPgetLPBasisInd(SCIP *scip, int *basisind)
Definition: scip.c:29281
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:45827
#define SEPA_NAME
int SCIProwGetRank(SCIP_ROW *row)
Definition: lp.c:16400
#define SCIP_REAL_MAX
Definition: def.h:136
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition: lp.c:16277
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip.c:30160
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip.c:7383
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45790
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:16081
#define DEFAULT_MAXROUNDSROOT
void SCIProwChgRank(SCIP_ROW *row, int rank)
Definition: lp.c:16533
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:46163
#define SCIP_Real
Definition: def.h:135
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1138
#define MIN(x, y)
Definition: memory.c:75
constraint handler for SOS type 1 constraints
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip.c:30762
#define DEFAULT_MAXRANKINTEGRAL
#define SCIP_Longint
Definition: def.h:120
#define SEPA_DELAY
SCIP_Real SCIPsumepsilon(SCIP *scip)
Definition: scip.c:45260
#define DEFAULT_MAXRANK
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip.c:29165
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
Definition: scip.c:45949
SCIP_Longint SCIPgetNLPs(SCIP *scip)
Definition: scip.c:41363
int SCIPcolGetLPPos(SCIP_COL *col)
Definition: lp.c:16122
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:30431
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38007
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:4258
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:45937
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:4176
#define DEFAULT_MAXDEPTH
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:16839
#define SEPA_USESSUBSCIP