Scippy

SCIP

Solving Constraint Integer Programs

sepa_strongcg.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_strongcg.c
17  * @brief Strong CG Cuts (Letchford & Lodi)
18  * @author Kati Wolter
19  * @author Tobias Achterberg
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include <assert.h>
25 #include <string.h>
26 
27 #include "scip/sepa_strongcg.h"
28 #include "scip/pub_misc.h"
29 
30 
31 #define SEPA_NAME "strongcg"
32 #define SEPA_DESC "Strong CG cuts separator (Letchford and Lodi)"
33 #define SEPA_PRIORITY -2000
34 #define SEPA_FREQ 10
35 #define SEPA_MAXBOUNDDIST 1.0
36 #define SEPA_USESSUBSCIP FALSE /**< does the separator use a secondary SCIP instance? */
37 #define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */
38 
39 #define DEFAULT_MAXROUNDS 5 /**< maximal number of strong CG separation rounds per node (-1: unlimited) */
40 #define DEFAULT_MAXROUNDSROOT 20 /**< maximal number of strong CG separation rounds in the root node (-1: unlimited) */
41 #define DEFAULT_MAXSEPACUTS 20 /**< maximal number of strong CG cuts separated per separation round */
42 #define DEFAULT_MAXSEPACUTSROOT 500 /**< maximal number of strong CG cuts separated per separation round in root node */
43 #define DEFAULT_DYNAMICCUTS TRUE /**< should generated cuts be removed from the LP if they are no longer tight? */
44 #define DEFAULT_RANDSEED 54 /**< initial random seed */
45 
46 #define SEPARATEROWS /* separate rows with integral slack */
47 
48 #define BOUNDSWITCH 0.9999
49 #define POSTPROCESS TRUE
50 #define USEVBDS TRUE
51 #define MINFRAC 0.05
52 #define MAXFRAC 0.95
53 
54 #define MAXAGGRLEN(nvars) (0.1*(nvars)+1000) /**< maximal length of base inequality */
55 
56 
57 /** separator data */
58 struct SCIP_SepaData
59 {
60  SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
61  int maxrounds; /**< maximal number of strong CG separation rounds per node (-1: unlimited) */
62  int maxroundsroot; /**< maximal number of strong CG separation rounds in the root node (-1: unlimited) */
63  int maxsepacuts; /**< maximal number of strong CG cuts separated per separation round */
64  int maxsepacutsroot; /**< maximal number of strong CG cuts separated per separation round in root node */
65  int lastncutsfound; /**< total number of cuts found after last call of separator */
66  SCIP_Bool dynamiccuts; /**< should generated cuts be removed from the LP if they are no longer tight? */
67 };
68 
69 /*
70  * Callback methods
71  */
72 
73 /** copy method for separator plugins (called when SCIP copies plugins) */
74 static
75 SCIP_DECL_SEPACOPY(sepaCopyStrongcg)
76 { /*lint --e{715}*/
77  assert(scip != NULL);
78  assert(sepa != NULL);
79  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
80 
81  /* call inclusion method of constraint handler */
83 
84  return SCIP_OKAY;
85 }
86 
87 /** destructor of separator to free user data (called when SCIP is exiting) */
88 static
89 SCIP_DECL_SEPAFREE(sepaFreeStrongcg)
90 { /*lint --e{715}*/
91  SCIP_SEPADATA* sepadata;
92 
93  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
94 
95  /* free separator data */
96  sepadata = SCIPsepaGetData(sepa);
97  assert(sepadata != NULL);
98 
99  SCIPfreeBlockMemory(scip, &sepadata);
100 
101  SCIPsepaSetData(sepa, NULL);
102 
103  return SCIP_OKAY;
104 }
105 
106 /** initialization method of separator (called after problem was transformed) */
107 static
108 SCIP_DECL_SEPAINIT(sepaInitStrongcg)
109 {
110  SCIP_SEPADATA* sepadata;
111 
112  sepadata = SCIPsepaGetData(sepa);
113  assert(sepadata != NULL);
114 
115  /* create and initialize random number generator */
116  SCIP_CALL( SCIPcreateRandom(scip, &sepadata->randnumgen, DEFAULT_RANDSEED) );
117 
118  return SCIP_OKAY;
119 }
120 
121 /** deinitialization method of separator (called before transformed problem is freed) */
122 static
123 SCIP_DECL_SEPAEXIT(sepaExitStrongcg)
124 { /*lint --e{715}*/
125  SCIP_SEPADATA* sepadata;
126 
127  sepadata = SCIPsepaGetData(sepa);
128  assert(sepadata != NULL);
129 
130  SCIPfreeRandom(scip, &sepadata->randnumgen);
131 
132  return SCIP_OKAY;
133 }
134 
135 /** LP solution separation method of separator */
136 static
137 SCIP_DECL_SEPAEXECLP(sepaExeclpStrongcg)
138 { /*lint --e{715}*/
139  SCIP_SEPADATA* sepadata;
140  SCIP_VAR** vars;
141  SCIP_COL** cols;
142  SCIP_ROW** rows;
143  SCIP_AGGRROW* aggrrow;
144  SCIP_Real* varsolvals;
145  SCIP_Real* binvrow;
146  SCIP_Real* cutcoefs;
147  SCIP_Real* basisfrac;
148  SCIP_Real cutrhs;
149  int* basisind;
150  int* basisperm;
151  int* inds;
152  int* cutinds;
153  int cutnnz;
154  int ninds;
155  int nvars;
156  int ncols;
157  int nrows;
158  int ncalls;
159  int depth;
160  int maxsepacuts;
161  int ncuts;
162  int c;
163  int i;
164  int cutrank;
165  SCIP_Bool success;
166  SCIP_Bool cutislocal;
167 
168  assert(sepa != NULL);
169  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
170  assert(scip != NULL);
171  assert(result != NULL);
172 
173  *result = SCIP_DIDNOTRUN;
174 
175  sepadata = SCIPsepaGetData(sepa);
176  assert(sepadata != NULL);
177 
178  depth = SCIPgetDepth(scip);
179  ncalls = SCIPsepaGetNCallsAtNode(sepa);
180 
181  /* only call separator, if we are not close to terminating */
182  if( SCIPisStopped(scip) || !allowlocal )
183  return SCIP_OKAY;
184 
185  /* only call the strong CG cut separator a given number of times at each node */
186  if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
187  || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
188  return SCIP_OKAY;
189 
190  /* only call separator, if an optimal LP solution is at hand */
192  return SCIP_OKAY;
193 
194  /* only call separator, if the LP solution is basic */
195  if( !SCIPisLPSolBasic(scip) )
196  return SCIP_OKAY;
197 
198  /* only call separator, if there are fractional variables */
199  if( SCIPgetNLPBranchCands(scip) == 0 )
200  return SCIP_OKAY;
201 
202  /* get variables data */
203  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
204 
205  /* get LP data */
206  SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
207  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
208  if( ncols == 0 || nrows == 0 )
209  return SCIP_OKAY;
210 
211 #if 0 /* if too many columns, separator is usually very slow: delay it until no other cuts have been found */
212  if( ncols >= 50*nrows )
213  return SCIP_OKAY;
214  if( ncols >= 5*nrows )
215  {
216  int ncutsfound;
217 
218  ncutsfound = SCIPgetNCutsFound(scip);
219  if( ncutsfound > sepadata->lastncutsfound || !SCIPsepaWasLPDelayed(sepa) )
220  {
221  sepadata->lastncutsfound = ncutsfound;
222  *result = SCIP_DELAYED;
223  return SCIP_OKAY;
224  }
225  }
226 #endif
227 
228  *result = SCIP_DIDNOTFIND;
229 
230  /* allocate temporary memory */
231  SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, nvars) );
232  SCIP_CALL( SCIPallocBufferArray(scip, &cutinds, nvars) );
233  SCIP_CALL( SCIPallocBufferArray(scip, &basisind, nrows) );
234  SCIP_CALL( SCIPallocBufferArray(scip, &basisperm, nrows) );
235  SCIP_CALL( SCIPallocBufferArray(scip, &basisfrac, nrows) );
236  SCIP_CALL( SCIPallocBufferArray(scip, &binvrow, nrows) );
237  SCIP_CALL( SCIPallocBufferArray(scip, &inds, nrows) );
238  SCIP_CALL( SCIPaggrRowCreate(scip, &aggrrow) );
239 
240  varsolvals = NULL; /* allocate this later, if needed */
241 
242  /* get basis indices */
243  SCIP_CALL( SCIPgetLPBasisInd(scip, basisind) );
244 
245  for( i = 0; i < nrows; ++i )
246  {
247  SCIP_Real frac = 0.0;
248 
249  c = basisind[i];
250 
251  basisperm[i] = i;
252 
253  if( c >= 0 )
254  {
255  SCIP_VAR* var;
256 
257  assert(c < ncols);
258  var = SCIPcolGetVar(cols[c]);
260  {
261  frac = SCIPfeasFrac(scip, SCIPcolGetPrimsol(cols[c]));
262  frac = MIN(frac, 1.0 - frac);
263  }
264  }
265 #ifdef SEPARATEROWS
266  else
267  {
268  SCIP_ROW* row;
269 
270  assert(0 <= -c-1 && -c-1 < nrows);
271  row = rows[-c-1];
272  if( SCIProwIsIntegral(row) && !SCIProwIsModifiable(row) )
273  {
274  frac = SCIPfeasFrac(scip, SCIPgetRowActivity(scip, row));
275  frac = MIN(frac, 1.0 - frac);
276  }
277  }
278 #endif
279 
280  if( frac >= MINFRAC )
281  {
282  /* slightly change fractionality to have random order for equal fractions */
283  basisfrac[i] = frac + SCIPrandomGetReal(sepadata->randnumgen, -1e-6, 1e-6);
284  }
285  else
286  {
287  basisfrac[i] = 0.0;
288  }
289  }
290 
291  /* sort basis indices by fractionality */
292  SCIPsortDownRealInt(basisfrac, basisperm, nrows);
293 
294  /* get the maximal number of cuts allowed in a separation round */
295  if( depth == 0 )
296  maxsepacuts = sepadata->maxsepacutsroot;
297  else
298  maxsepacuts = sepadata->maxsepacuts;
299 
300  SCIPdebugMsg(scip, "searching strong CG cuts: %d cols, %d rows, maxcuts=%d\n",
301  ncols, nrows, maxsepacuts);
302 
303  /* for all basic columns belonging to integer variables, try to generate a strong CG cut */
304  ncuts = 0;
305  for( i = 0; i < nrows && ncuts < maxsepacuts && !SCIPisStopped(scip) && *result != SCIP_CUTOFF; ++i )
306  {
307  int j;
308  SCIP_Real cutefficacy;
309 
310  if( basisfrac[i] == 0.0 )
311  break;
312 
313  j = basisperm[i];
314  c = basisind[j];
315 
316  /* get the row of B^-1 for this basic integer variable with fractional solution value */
317  SCIP_CALL( SCIPgetLPBInvRow(scip, j, binvrow, inds, &ninds) );
318 
319 #ifdef SCIP_DEBUG
320  /* initialize variables, that might not have been initialized in SCIPcalcMIR if success == FALSE */
321  cutefficacy = 0.0;
322  cutrhs = SCIPinfinity(scip);
323 #endif
324 
325  /* create the aggregation row using the B^-1 row as weights */
326  SCIP_CALL( SCIPaggrRowSumRows(scip, aggrrow, binvrow, inds, ninds,
327  FALSE, allowlocal, 1, (int) MAXAGGRLEN(nvars), &success) );
328 
329  if( !success )
330  continue;
331 
332  /* create a strong CG cut out of the aggregation row */
334  1.0, aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy, &cutrank, &cutislocal, &success) );
335 
336  assert(allowlocal || !cutislocal);
337  SCIPdebugMsg(scip, " -> success=%u: rhs: %g, efficacy: %g\n", success, cutrhs, cutefficacy);
338 
339  if( !success )
340  continue;
341 
342  /* if successful, convert dense cut into sparse row, and add the row as a cut */
343  if( SCIPisEfficacious(scip, cutefficacy) )
344  {
345  SCIP_ROW* cut;
346  char cutname[SCIP_MAXSTRLEN];
347  int v;
348 
349  SCIPdebugMsg(scip, " -> strong CG cut for <%s>: act=%f, rhs=%f, norm=%f, eff=%f, rank=%d\n",
350  c >= 0 ? SCIPvarGetName(SCIPcolGetVar(cols[c])) : SCIProwGetName(rows[-c-1]),
351  cutefficacy * SCIPgetVectorEfficacyNorm(scip, cutcoefs, cutnnz) + cutrhs, cutrhs, SCIPgetVectorEfficacyNorm(scip, cutcoefs, cutnnz), cutefficacy, cutrank);
352 
353  /* create the cut */
354  if( c >= 0 )
355  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "scg%d_x%d", SCIPgetNLPs(scip), c);
356  else
357  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "scg%d_s%d", SCIPgetNLPs(scip), -c-1);
358 
359  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), cutrhs, cutislocal, FALSE, sepadata->dynamiccuts) );
360 
361  /*SCIPdebug( SCIP_CALL(SCIPprintRow(scip, cut, NULL)) );*/
362  SCIProwChgRank(cut, cutrank);
363 
364  /* cache the row extension and only flush them if the cut gets added */
366 
367  /* collect all non-zero coefficients */
368  for( v = 0; v < cutnnz; ++v )
369  {
370  SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cutinds[v]], cutcoefs[v]) );
371  }
372 
373  assert(success);
374 
375  if( !SCIPisCutEfficacious(scip, NULL, cut) )
376  {
377  SCIPdebugMsg(scip, " -> strong CG cut <%s> no longer efficacious: act=%f, rhs=%f, norm=%f, eff=%f\n",
378  cutname, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
379  SCIPgetCutEfficacy(scip, NULL, cut));
380  /*SCIPdebug( SCIP_CALL(SCIPprintRow(scip, cut, NULL)) );*/
381  success = FALSE;
382  }
383  else
384  {
385  SCIP_Bool infeasible = FALSE;
386 
387  /* flush all changes before adding the cut */
389 
390  SCIPdebugMsg(scip, " -> found strong CG cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, min=%f, max=%f (range=%f)\n",
391  cutname, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
392  SCIPgetCutEfficacy(scip, NULL, cut),
395  /*SCIPdebug( SCIP_CALL(SCIPprintRow(scip, cut, NULL)) );*/
396 
397  if( SCIPisCutNew(scip, cut) )
398  {
399  if( !cutislocal )
400  {
401  SCIP_CALL( SCIPaddPoolCut(scip, cut) );
402  }
403  else
404  {
405  SCIP_CALL( SCIPaddRow(scip, cut, FALSE, &infeasible) );
406  }
407 
408  ncuts++;
409 
410  if( infeasible )
411  {
412  *result = SCIP_CUTOFF;
413  }
414  else
415  {
416  *result = SCIP_SEPARATED;
417  }
418  }
419  }
420 
421  /* release the row */
422  SCIP_CALL( SCIPreleaseRow(scip, &cut) );
423  }
424  }
425 
426  /* free temporary memory */
427  SCIPaggrRowFree(scip, &aggrrow);
428  SCIPfreeBufferArrayNull(scip, &varsolvals);
429  SCIPfreeBufferArray(scip, &inds);
430  SCIPfreeBufferArray(scip, &binvrow);
431  SCIPfreeBufferArray(scip, &basisfrac);
432  SCIPfreeBufferArray(scip, &basisperm);
433  SCIPfreeBufferArray(scip, &basisind);
434  SCIPfreeBufferArray(scip, &cutinds);
435  SCIPfreeBufferArray(scip, &cutcoefs);
436 
437  SCIPdebugMsg(scip, "end searching strong CG cuts: found %d cuts\n", ncuts);
438 
439  sepadata->lastncutsfound = SCIPgetNCutsFound(scip);
440 
441  return SCIP_OKAY;
442 }
443 
444 
445 /*
446  * separator specific interface methods
447  */
448 
449 /** creates the Strong CG cut separator and includes it in SCIP */
451  SCIP* scip /**< SCIP data structure */
452  )
453 {
454  SCIP_SEPADATA* sepadata;
455  SCIP_SEPA* sepa;
456 
457  /* create separator data */
458  SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) );
459  sepadata->lastncutsfound = 0;
460 
461  /* include separator */
464  sepaExeclpStrongcg, NULL,
465  sepadata) );
466 
467  assert(sepa != NULL);
468 
469  /* set non-NULL pointers to callback methods */
470  SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyStrongcg) );
471  SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeStrongcg) );
472  SCIP_CALL( SCIPsetSepaInit(scip, sepa, sepaInitStrongcg) );
473  SCIP_CALL( SCIPsetSepaExit(scip, sepa, sepaExitStrongcg) );
474 
475  /* add separator parameters */
477  "separating/strongcg/maxrounds",
478  "maximal number of strong CG separation rounds per node (-1: unlimited)",
479  &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
481  "separating/strongcg/maxroundsroot",
482  "maximal number of strong CG separation rounds in the root node (-1: unlimited)",
483  &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
485  "separating/strongcg/maxsepacuts",
486  "maximal number of strong CG cuts separated per separation round",
487  &sepadata->maxsepacuts, FALSE, DEFAULT_MAXSEPACUTS, 0, INT_MAX, NULL, NULL) );
489  "separating/strongcg/maxsepacutsroot",
490  "maximal number of strong CG cuts separated per separation round in the root node",
491  &sepadata->maxsepacutsroot, FALSE, DEFAULT_MAXSEPACUTSROOT, 0, INT_MAX, NULL, NULL) );
493  "separating/strongcg/dynamiccuts",
494  "should generated cuts be removed from the LP if they are no longer tight?",
495  &sepadata->dynamiccuts, FALSE, DEFAULT_DYNAMICCUTS, NULL, NULL) );
496 
497  return SCIP_OKAY;
498 }
499 
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
Definition: scip.c:48620
static SCIP_DECL_SEPAFREE(sepaFreeStrongcg)
Definition: sepa_strongcg.c:89
#define DEFAULT_MAXROUNDS
Definition: sepa_strongcg.c:39
SCIP_RETCODE SCIPcalcStrongCG(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real scale, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
Definition: cuts.c:7891
void SCIPaggrRowFree(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition: cuts.c:1567
SCIP_RETCODE SCIPgetLPBInvRow(SCIP *scip, int r, SCIP_Real *coefs, int *inds, int *ninds)
Definition: scip.c:29778
#define USEVBDS
Definition: sepa_strongcg.c:50
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30607
static SCIP_DECL_SEPACOPY(sepaCopyStrongcg)
Definition: sepa_strongcg.c:75
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30630
#define SEPA_DESC
Definition: sepa_strongcg.c:32
#define BOUNDSWITCH
Definition: sepa_strongcg.c:48
#define SEPA_PRIORITY
Definition: sepa_strongcg.c:33
#define SCIP_MAXSTRLEN
Definition: def.h:259
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed)
Definition: scip.c:48602
#define DEFAULT_MAXROUNDSROOT
Definition: sepa_strongcg.c:40
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:30662
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:16540
static SCIP_DECL_SEPAEXECLP(sepaExeclpStrongcg)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:11680
#define FALSE
Definition: def.h:64
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:47022
#define DEFAULT_MAXSEPACUTSROOT
Definition: sepa_strongcg.c:42
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10011
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition: sepa.c:646
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_Real SCIPgetVectorEfficacyNorm(SCIP *scip, SCIP_Real *vals, int nvals)
Definition: scip.c:34554
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:22602
#define SEPA_NAME
Definition: sepa_strongcg.c:31
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIP_Real SCIPfeasFrac(SCIP *scip, SCIP_Real val)
Definition: scip.c:47453
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:22585
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
Definition: scip.c:29556
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip.c:37028
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 SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30883
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
Definition: sepa.c:557
#define MINFRAC
Definition: sepa_strongcg.c:51
static SCIP_DECL_SEPAINIT(sepaInitStrongcg)
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip.c:29731
#define MAXFRAC
Definition: sepa_strongcg.c:52
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip.c:34522
#define SEPA_USESSUBSCIP
Definition: sepa_strongcg.c:36
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
Definition: lp.c:16205
SCIP_RETCODE SCIPincludeSepaStrongcg(SCIP *scip)
SCIP_Real SCIPgetRowMinCoef(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30865
#define DEFAULT_RANDSEED
Definition: sepa_strongcg.c:44
#define SEPA_FREQ
Definition: sepa_strongcg.c:34
int SCIPgetNCutsFound(SCIP *scip)
Definition: scip.c:42896
SCIP_RETCODE SCIPsetSepaExit(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAEXIT((*sepaexit)))
Definition: scip.c:7475
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip.h:22633
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
Definition: sepa.c:773
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip.c:34540
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16662
SCIP_Bool SCIProwIsIntegral(SCIP_ROW *row)
Definition: lp.c:16580
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
Definition: sepa.c:567
static SCIP_DECL_SEPAEXIT(sepaExitStrongcg)
#define SCIP_CALL(x)
Definition: def.h:350
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_Bool SCIProwIsModifiable(SCIP_ROW *row)
Definition: lp.c:16600
#define SEPA_DELAY
Definition: sepa_strongcg.c:37
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
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:61
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:29287
#define SEPA_MAXBOUNDDIST
Definition: sepa_strongcg.c:35
#define DEFAULT_MAXSEPACUTS
Definition: sepa_strongcg.c:41
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:43039
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:34766
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
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip.c:34499
SCIP_RETCODE SCIPgetLPBasisInd(SCIP *scip, int *basisind)
Definition: scip.c:29750
SCIP_Bool SCIPisCutNew(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:34748
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:9388
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_RETCODE SCIPsetSepaInit(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAINIT((*sepainit)))
Definition: scip.c:7459
SCIP_RETCODE SCIPaggrRowSumRows(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Real *weights, int *rowinds, int nrowinds, SCIP_Bool sidetypebasis, SCIP_Bool allowlocal, int negslack, int maxaggrlen, SCIP_Bool *valid)
Definition: cuts.c:2087
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:16251
void SCIProwChgRank(SCIP_ROW *row, int rank)
Definition: lp.c:16703
#define DEFAULT_DYNAMICCUTS
Definition: sepa_strongcg.c:43
#define SCIP_Real
Definition: def.h:149
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1145
#define POSTPROCESS
Definition: sepa_strongcg.c:49
SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition: cuts.c:1535
Strong CG Cuts (Letchford & Lodi)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16827
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip.c:29634
SCIP_Longint SCIPgetNLPs(SCIP *scip)
Definition: scip.c:42308
#define MAXAGGRLEN(nvars)
Definition: sepa_strongcg.c:54
SCIP_Real SCIProwGetNorm(SCIP_ROW *row)
Definition: lp.c:16457
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
SCIP_Real SCIPgetRowActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:31065