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