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