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 0
35 #define SEPA_MAXBOUNDDIST 0.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 50 /**< 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_MAXWEIGHTRANGE 1e+04 /**< maximal valid range max(|weights|)/min(|weights|) of row weights */
45 
46 #define MAKECUTINTEGRAL /* try to scale all cuts to integral coefficients */
47 /*#define MAKEINTCUTINTEGRAL*/ /* try to scale cuts without continuous variables to integral coefficients */
48 #define FORCECUTINTEGRAL /* discard cut if conversion to integral coefficients failed */
49 #define SEPARATEROWS /* separate rows with integral slack */
50 
51 #define BOUNDSWITCH 0.9999
52 #define USEVBDS TRUE
53 #define ALLOWLOCAL TRUE
54 #define MAKECONTINTEGRAL FALSE
55 #define MINFRAC 0.05
56 #define MAXFRAC 0.95
57 
58 #define MAXAGGRLEN(nvars) (0.1*(nvars)+1000) /**< maximal length of base inequality */
59 
60 
61 /** separator data */
62 struct SCIP_SepaData
63 {
64  SCIP_Real maxweightrange; /**< maximal valid range max(|weights|)/min(|weights|) of row weights */
65  int maxrounds; /**< maximal number of strong CG separation rounds per node (-1: unlimited) */
66  int maxroundsroot; /**< maximal number of strong CG separation rounds in the root node (-1: unlimited) */
67  int maxsepacuts; /**< maximal number of strong CG cuts separated per separation round */
68  int maxsepacutsroot; /**< maximal number of strong CG cuts separated per separation round in root node */
69  int lastncutsfound; /**< total number of cuts found after last call of separator */
70  SCIP_Bool dynamiccuts; /**< should generated cuts be removed from the LP if they are no longer tight? */
71 };
72 
73 
74 /*
75  * local methods
76  */
77 
78 /** stores nonzero elements of dense coefficient vector as sparse vector, and calculates activity and norm */
79 static
81  SCIP* scip, /**< SCIP data structure */
82  int nvars, /**< number of problem variables */
83  SCIP_VAR** vars, /**< problem variables */
84  SCIP_Real* cutcoefs, /**< dense coefficient vector */
85  SCIP_Real* varsolvals, /**< dense variable LP solution vector */
86  char normtype, /**< type of norm to use for efficacy norm calculation */
87  SCIP_VAR** cutvars, /**< array to store variables of sparse cut vector */
88  SCIP_Real* cutvals, /**< array to store coefficients of sparse cut vector */
89  int* cutlen, /**< pointer to store number of nonzero entries in cut */
90  SCIP_Real* cutact, /**< pointer to store activity of cut */
91  SCIP_Real* cutnorm /**< pointer to store norm of cut vector */
92  )
93 {
94  SCIP_Real val;
95  SCIP_Real absval;
96  SCIP_Real cutsqrnorm;
97  SCIP_Real act;
98  SCIP_Real norm;
99  int len;
100  int v;
101 
102  assert(nvars == 0 || cutcoefs != NULL);
103  assert(nvars == 0 || varsolvals != NULL);
104  assert(cutvars != NULL);
105  assert(cutvals != NULL);
106  assert(cutlen != NULL);
107  assert(cutact != NULL);
108  assert(cutnorm != NULL);
109 
110  len = 0;
111  act = 0.0;
112  norm = 0.0;
113  switch( normtype )
114  {
115  case 'e':
116  cutsqrnorm = 0.0;
117  for( v = 0; v < nvars; ++v )
118  {
119  val = cutcoefs[v];
120  if( !SCIPisZero(scip, val) )
121  {
122  act += val * varsolvals[v];
123  cutsqrnorm += SQR(val);
124  cutvars[len] = vars[v];
125  cutvals[len] = val;
126  len++;
127  }
128  }
129  norm = SQRT(cutsqrnorm);
130  break;
131  case 'm':
132  for( v = 0; v < nvars; ++v )
133  {
134  val = cutcoefs[v];
135  if( !SCIPisZero(scip, val) )
136  {
137  act += val * varsolvals[v];
138  absval = ABS(val);
139  norm = MAX(norm, absval);
140  cutvars[len] = vars[v];
141  cutvals[len] = val;
142  len++;
143  }
144  }
145  break;
146  case 's':
147  for( v = 0; v < nvars; ++v )
148  {
149  val = cutcoefs[v];
150  if( !SCIPisZero(scip, val) )
151  {
152  act += val * varsolvals[v];
153  norm += ABS(val);
154  cutvars[len] = vars[v];
155  cutvals[len] = val;
156  len++;
157  }
158  }
159  break;
160  case 'd':
161  for( v = 0; v < nvars; ++v )
162  {
163  val = cutcoefs[v];
164  if( !SCIPisZero(scip, val) )
165  {
166  act += val * varsolvals[v];
167  norm = 1.0;
168  cutvars[len] = vars[v];
169  cutvals[len] = val;
170  len++;
171  }
172  }
173  break;
174  default:
175  SCIPerrorMessage("invalid efficacy norm parameter '%c'\n", normtype);
176  return SCIP_INVALIDDATA;
177  }
178 
179  *cutlen = len;
180  *cutact = act;
181  *cutnorm = norm;
182 
183  return SCIP_OKAY;
184 }
185 
186 
187 /*
188  * Callback methods
189  */
190 
191 /** copy method for separator plugins (called when SCIP copies plugins) */
192 static
193 SCIP_DECL_SEPACOPY(sepaCopyStrongcg)
194 { /*lint --e{715}*/
195  assert(scip != NULL);
196  assert(sepa != NULL);
197  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
198 
199  /* call inclusion method of constraint handler */
201 
202  return SCIP_OKAY;
203 }
204 
205 /** destructor of separator to free user data (called when SCIP is exiting) */
206 static
207 SCIP_DECL_SEPAFREE(sepaFreeStrongcg)
208 { /*lint --e{715}*/
209  SCIP_SEPADATA* sepadata;
210 
211  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
212 
213  /* free separator data */
214  sepadata = SCIPsepaGetData(sepa);
215  assert(sepadata != NULL);
216 
217  SCIPfreeBlockMemory(scip, &sepadata);
218 
219  SCIPsepaSetData(sepa, NULL);
220 
221  return SCIP_OKAY;
222 }
223 
224 
225 /** LP solution separation method of separator */
226 static
227 SCIP_DECL_SEPAEXECLP(sepaExeclpStrongcg)
228 { /*lint --e{715}*/
229  SCIP_SEPADATA* sepadata;
230  SCIP_VAR** vars;
231  SCIP_COL** cols;
232  SCIP_ROW** rows;
233  SCIP_Real* varsolvals;
234  SCIP_Real* binvrow;
235  SCIP_Real* cutcoefs;
236  SCIP_Real cutrhs;
237  SCIP_Real cutact;
238  SCIP_Real maxscale;
239  SCIP_Longint maxdnom;
240  int* basisind;
241  int* inds;
242  int ninds;
243  int nvars;
244  int ncols;
245  int nrows;
246  int ncalls;
247  int depth;
248  int maxdepth;
249  int maxsepacuts;
250  int ncuts;
251  int c;
252  int i;
253  int cutrank;
254  SCIP_Bool success;
255  SCIP_Bool cutislocal;
256  char normtype;
257 
258  assert(sepa != NULL);
259  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
260  assert(scip != NULL);
261  assert(result != NULL);
262 
263  *result = SCIP_DIDNOTRUN;
264 
265  sepadata = SCIPsepaGetData(sepa);
266  assert(sepadata != NULL);
267 
268  depth = SCIPgetDepth(scip);
269  ncalls = SCIPsepaGetNCallsAtNode(sepa);
270 
271  /* only call separator, if we are not close to terminating */
272  if( SCIPisStopped(scip) )
273  return SCIP_OKAY;
274 
275  /* only call the strong CG cut separator a given number of times at each node */
276  if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
277  || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
278  return SCIP_OKAY;
279 
280  /* only call separator, if an optimal LP solution is at hand */
282  return SCIP_OKAY;
283 
284  /* only call separator, if the LP solution is basic */
285  if( !SCIPisLPSolBasic(scip) )
286  return SCIP_OKAY;
287 
288  /* only call separator, if there are fractional variables */
289  if( SCIPgetNLPBranchCands(scip) == 0 )
290  return SCIP_OKAY;
291 
292  /* get variables data */
293  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
294 
295  /* get LP data */
296  SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
297  SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
298  if( ncols == 0 || nrows == 0 )
299  return SCIP_OKAY;
300 
301 #if 0 /* if too many columns, separator is usually very slow: delay it until no other cuts have been found */
302  if( ncols >= 50*nrows )
303  return SCIP_OKAY;
304  if( ncols >= 5*nrows )
305  {
306  int ncutsfound;
307 
308  ncutsfound = SCIPgetNCutsFound(scip);
309  if( ncutsfound > sepadata->lastncutsfound || !SCIPsepaWasLPDelayed(sepa) )
310  {
311  sepadata->lastncutsfound = ncutsfound;
312  *result = SCIP_DELAYED;
313  return SCIP_OKAY;
314  }
315  }
316 #endif
317 
318  /* get the type of norm to use for efficacy calculations */
319  SCIP_CALL( SCIPgetCharParam(scip, "separating/efficacynorm", &normtype) );
320 
321  /* set the maximal denominator in rational representation of strong CG cut and the maximal scale factor to
322  * scale resulting cut to integral values to avoid numerical instabilities
323  */
324  /**@todo find better but still stable strong CG cut settings: look at dcmulti, gesa3, khb0525, misc06, p2756 */
325  maxdepth = SCIPgetMaxDepth(scip);
326  if( depth == 0 )
327  {
328  maxdnom = 1000;
329  maxscale = 1000.0;
330  }
331  else if( depth <= maxdepth/4 )
332  {
333  maxdnom = 1000;
334  maxscale = 1000.0;
335  }
336  else if( depth <= maxdepth/2 )
337  {
338  maxdnom = 100;
339  maxscale = 100.0;
340  }
341  else
342  {
343  maxdnom = 10;
344  maxscale = 10.0;
345  }
346 
347  *result = SCIP_DIDNOTFIND;
348 
349  /* allocate temporary memory */
350  SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, nvars) );
351  SCIP_CALL( SCIPallocBufferArray(scip, &basisind, nrows) );
352  SCIP_CALL( SCIPallocBufferArray(scip, &binvrow, nrows) );
353  SCIP_CALL( SCIPallocBufferArray(scip, &inds, nrows) );
354  varsolvals = NULL; /* allocate this later, if needed */
355 
356  /* get basis indices */
357  SCIP_CALL( SCIPgetLPBasisInd(scip, basisind) );
358 
359  /* get the maximal number of cuts allowed in a separation round */
360  if( depth == 0 )
361  maxsepacuts = sepadata->maxsepacutsroot;
362  else
363  maxsepacuts = sepadata->maxsepacuts;
364 
365  SCIPdebugMsg(scip, "searching strong CG cuts: %d cols, %d rows, maxdnom=%" SCIP_LONGINT_FORMAT ", maxscale=%g, maxcuts=%d\n",
366  ncols, nrows, maxdnom, maxscale, maxsepacuts);
367 
368  /* for all basic columns belonging to integer variables, try to generate a strong CG cut */
369  ncuts = 0;
370  for( i = 0; i < nrows && ncuts < maxsepacuts && !SCIPisStopped(scip) && *result != SCIP_CUTOFF; ++i )
371  {
372  SCIP_Bool tryrow;
373 
374  tryrow = FALSE;
375  c = basisind[i];
376  if( c >= 0 )
377  {
378  SCIP_VAR* var;
379 
380  assert(c < ncols);
381  var = SCIPcolGetVar(cols[c]);
383  {
384  SCIP_Real primsol;
385 
386  primsol = SCIPcolGetPrimsol(cols[c]);
387  assert(SCIPgetVarSol(scip, var) == primsol); /*lint !e777*/
388 
389  if( SCIPfeasFrac(scip, primsol) >= MINFRAC )
390  {
391  SCIPdebugMsg(scip, "trying strong CG cut for col <%s> [%g]\n", SCIPvarGetName(var), primsol);
392  tryrow = TRUE;
393  }
394  }
395  }
396 #ifdef SEPARATEROWS
397  else
398  {
399  SCIP_ROW* row;
400 
401  assert(0 <= -c-1 && -c-1 < nrows);
402  row = rows[-c-1];
403  if( SCIProwIsIntegral(row) && !SCIProwIsModifiable(row) )
404  {
405  SCIP_Real primsol;
406 
407  primsol = SCIPgetRowActivity(scip, row);
408  if( SCIPfeasFrac(scip, primsol) >= MINFRAC )
409  {
410  SCIPdebugMsg(scip, "trying strong CG cut for row <%s> [%g]\n", SCIProwGetName(row), primsol);
411  tryrow = TRUE;
412  }
413  }
414  }
415 #endif
416 
417  if( tryrow )
418  {
419  /* get the row of B^-1 for this basic integer variable with fractional solution value */
420  SCIP_CALL( SCIPgetLPBInvRow(scip, i, binvrow, inds, &ninds) );
421 
422 #ifdef SCIP_DEBUG
423  /* initialize variables, that might not have been initialized in SCIPcalcMIR if success == FALSE */
424  cutact = 0.0;
425  cutrhs = SCIPinfinity(scip);
426 #endif
427  /* create a strong CG cut out of the weighted LP rows using the B^-1 row as weights */
428  SCIP_CALL( SCIPcalcStrongCG(scip, BOUNDSWITCH, USEVBDS, ALLOWLOCAL, (int) MAXAGGRLEN(nvars), sepadata->maxweightrange, MINFRAC, MAXFRAC,
429  binvrow, inds, ninds, 1.0, cutcoefs, &cutrhs, &cutact, &success, &cutislocal, &cutrank) );
430  assert(ALLOWLOCAL || !cutislocal);
431  SCIPdebugMsg(scip, " -> success=%u: %g <= %g\n", success, cutact, cutrhs);
432 
433  /* if successful, convert dense cut into sparse row, and add the row as a cut */
434  if( success && SCIPisFeasGT(scip, cutact, cutrhs) )
435  {
436  SCIP_VAR** cutvars;
437  SCIP_Real* cutvals;
438  SCIP_Real cutnorm;
439  int cutlen;
440 
441  /* if this is the first successful cut, get the LP solution for all COLUMN variables */
442  if( varsolvals == NULL )
443  {
444  int v;
445 
446  SCIP_CALL( SCIPallocBufferArray(scip, &varsolvals, nvars) );
447  for( v = 0; v < nvars; ++v )
448  {
449  if( SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_COLUMN )
450  varsolvals[v] = SCIPvarGetLPSol(vars[v]);
451  }
452  }
453  assert(varsolvals != NULL);
454 
455  /* get temporary memory for storing the cut as sparse row */
456  SCIP_CALL( SCIPallocBufferArray(scip, &cutvars, nvars) );
457  SCIP_CALL( SCIPallocBufferArray(scip, &cutvals, nvars) );
458 
459  /* store the cut as sparse row, calculate activity and norm of cut */
460  SCIP_CALL( storeCutInArrays(scip, nvars, vars, cutcoefs, varsolvals, normtype,
461  cutvars, cutvals, &cutlen, &cutact, &cutnorm) );
462 
463  SCIPdebugMsg(scip, " -> strong CG cut for <%s>: act=%f, rhs=%f, norm=%f, eff=%f, rank=%d\n",
464  c >= 0 ? SCIPvarGetName(SCIPcolGetVar(cols[c])) : SCIProwGetName(rows[-c-1]),
465  cutact, cutrhs, cutnorm, (cutact - cutrhs)/cutnorm, cutrank);
466 
467  if( SCIPisPositive(scip, cutnorm) && SCIPisEfficacious(scip, (cutact - cutrhs)/cutnorm) )
468  {
469  SCIP_ROW* cut;
470  char cutname[SCIP_MAXSTRLEN];
471 
472  /* create the cut */
473  if( c >= 0 )
474  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "scg%d_x%d", SCIPgetNLPs(scip), c);
475  else
476  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "scg%d_s%d", SCIPgetNLPs(scip), -c-1);
477  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), cutrhs, cutislocal, FALSE, sepadata->dynamiccuts) );
478  SCIP_CALL( SCIPaddVarsToRow(scip, cut, cutlen, cutvars, cutvals) );
479  /*SCIPdebug( SCIP_CALL(SCIPprintRow(scip, cut, NULL)) );*/
480  SCIProwChgRank(cut, cutrank);
481 
482  assert(success);
483 #ifdef MAKECUTINTEGRAL
484  /* try to scale the cut to integral values */
486  maxdnom, maxscale, MAKECONTINTEGRAL, &success) );
487 #else
488 #ifdef MAKEINTCUTINTEGRAL
489  /* try to scale the cut to integral values if there are no continuous variables
490  * -> leads to an integral slack variable that can later be used for other cuts
491  */
492  {
493  int k = 0;
494  while ( k < cutlen && SCIPvarIsIntegral(cutvars[k]) )
495  ++k;
496  if( k == cutlen )
497  {
499  maxdnom, maxscale, MAKECONTINTEGRAL, &success) );
500  }
501  }
502 #endif
503 #endif
504 
505 #ifndef FORCECUTINTEGRAL
506  success = TRUE;
507 #endif
508 
509  if( success )
510  {
511  if( !SCIPisCutEfficacious(scip, NULL, cut) )
512  {
513  SCIPdebugMsg(scip, " -> strong CG cut <%s> no longer efficacious: act=%f, rhs=%f, norm=%f, eff=%f\n",
514  cutname, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
515  SCIPgetCutEfficacy(scip, NULL, cut));
516  /*SCIPdebug( SCIP_CALL(SCIPprintRow(scip, cut, NULL)) );*/
517  success = FALSE;
518  }
519  else
520  {
521  SCIP_Bool infeasible;
522 
523  SCIPdebugMsg(scip, " -> found strong CG cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, min=%f, max=%f (range=%f)\n",
524  cutname, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
528  /*SCIPdebug( SCIP_CALL(SCIPprintRow(scip, cut, NULL)) );*/
529  SCIP_CALL( SCIPaddCut(scip, NULL, cut, FALSE, &infeasible) );
530  if ( infeasible )
531  *result = SCIP_CUTOFF;
532  else
533  {
534  if( !cutislocal )
535  {
536  SCIP_CALL( SCIPaddPoolCut(scip, cut) );
537  }
538  *result = SCIP_SEPARATED;
539  }
540  ncuts++;
541  }
542  }
543  else
544  {
545  SCIPdebugMsg(scip, " -> strong CG cut <%s> couldn't be scaled to integral coefficients: act=%f, rhs=%f, norm=%f, eff=%f\n",
546  cutname, cutact, cutrhs, cutnorm, SCIPgetCutEfficacy(scip, NULL, cut));
547  }
548 
549  /* release the row */
550  SCIP_CALL( SCIPreleaseRow(scip, &cut) );
551  }
552 
553  /* free temporary memory */
554  SCIPfreeBufferArray(scip, &cutvals);
555  SCIPfreeBufferArray(scip, &cutvars);
556  }
557  }
558  }
559 
560  /* free temporary memory */
561  SCIPfreeBufferArrayNull(scip, &varsolvals);
562  SCIPfreeBufferArray(scip, &inds);
563  SCIPfreeBufferArray(scip, &binvrow);
564  SCIPfreeBufferArray(scip, &basisind);
565  SCIPfreeBufferArray(scip, &cutcoefs);
566 
567  SCIPdebugMsg(scip, "end searching strong CG cuts: found %d cuts\n", ncuts);
568 
569  sepadata->lastncutsfound = SCIPgetNCutsFound(scip);
570 
571  return SCIP_OKAY;
572 }
573 
574 
575 /*
576  * separator specific interface methods
577  */
578 
579 /** creates the Strong CG cut separator and includes it in SCIP */
581  SCIP* scip /**< SCIP data structure */
582  )
583 {
584  SCIP_SEPADATA* sepadata;
585  SCIP_SEPA* sepa;
586 
587  /* create separator data */
588  SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) );
589  sepadata->lastncutsfound = 0;
590 
591  /* include separator */
594  sepaExeclpStrongcg, NULL,
595  sepadata) );
596 
597  assert(sepa != NULL);
598 
599  /* set non-NULL pointers to callback methods */
600  SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyStrongcg) );
601  SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeStrongcg) );
602 
603  /* add separator parameters */
605  "separating/strongcg/maxrounds",
606  "maximal number of strong CG separation rounds per node (-1: unlimited)",
607  &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
609  "separating/strongcg/maxroundsroot",
610  "maximal number of strong CG separation rounds in the root node (-1: unlimited)",
611  &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
613  "separating/strongcg/maxsepacuts",
614  "maximal number of strong CG cuts separated per separation round",
615  &sepadata->maxsepacuts, FALSE, DEFAULT_MAXSEPACUTS, 0, INT_MAX, NULL, NULL) );
617  "separating/strongcg/maxsepacutsroot",
618  "maximal number of strong CG cuts separated per separation round in the root node",
619  &sepadata->maxsepacutsroot, FALSE, DEFAULT_MAXSEPACUTSROOT, 0, INT_MAX, NULL, NULL) );
621  "separating/strongcg/maxweightrange",
622  "maximal valid range max(|weights|)/min(|weights|) of row weights",
623  &sepadata->maxweightrange, TRUE, DEFAULT_MAXWEIGHTRANGE, 1.0, SCIP_REAL_MAX, NULL, NULL) );
625  "separating/strongcg/dynamiccuts",
626  "should generated cuts be removed from the LP if they are no longer tight?",
627  &sepadata->dynamiccuts, FALSE, DEFAULT_DYNAMICCUTS, NULL, NULL) );
628 
629  return SCIP_OKAY;
630 }
631 
static SCIP_DECL_SEPAFREE(sepaFreeStrongcg)
#define DEFAULT_MAXROUNDS
Definition: sepa_strongcg.c:39
SCIP_RETCODE SCIPgetCharParam(SCIP *scip, const char *name, char *value)
Definition: scip.c:4445
SCIP_RETCODE SCIPgetLPBInvRow(SCIP *scip, int r, SCIP_Real *coefs, int *inds, int *ninds)
Definition: scip.c:29309
#define USEVBDS
Definition: sepa_strongcg.c:52
static SCIP_DECL_SEPACOPY(sepaCopyStrongcg)
#define SEPA_DESC
Definition: sepa_strongcg.c:32
SCIP_RETCODE SCIPcalcStrongCG(SCIP *scip, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, int maxmksetcoefs, SCIP_Real maxweightrange, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real *weights, int *inds, int ninds, SCIP_Real scale, SCIP_Real *mircoef, SCIP_Real *mirrhs, SCIP_Real *cutactivity, SCIP_Bool *success, SCIP_Bool *cutislocal, int *cutrank)
Definition: scip.c:29529
#define BOUNDSWITCH
Definition: sepa_strongcg.c:51
#define SEPA_PRIORITY
Definition: sepa_strongcg.c:33
#define SCIP_MAXSTRLEN
Definition: def.h:215
#define DEFAULT_MAXROUNDSROOT
Definition: sepa_strongcg.c:40
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
Definition: scip.c:45876
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:16370
int SCIPgetMaxDepth(SCIP *scip)
Definition: scip.c:42144
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:11505
#define FALSE
Definition: def.h:64
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:45816
#define DEFAULT_MAXSEPACUTSROOT
Definition: sepa_strongcg.c:42
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:9340
#define TRUE
Definition: def.h:63
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition: sepa.c:632
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21907
#define SEPA_NAME
Definition: sepa_strongcg.c:31
#define ALLOWLOCAL
Definition: sepa_strongcg.c:53
SCIP_Real SCIPfeasFrac(SCIP *scip, SCIP_Real val)
Definition: scip.c:46247
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:21937
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21890
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
Definition: scip.c:29087
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip.c:36161
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip.c:7367
#define SCIPdebugMsg
Definition: scip.h:451
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4202
SCIP_Real SCIPepsilon(SCIP *scip)
Definition: scip.c:45246
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30491
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
Definition: sepa.c:543
#define MINFRAC
Definition: sepa_strongcg.c:55
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip.c:29262
#define MAXFRAC
Definition: sepa_strongcg.c:56
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip.c:33761
#define SEPA_USESSUBSCIP
Definition: sepa_strongcg.c:36
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
Definition: lp.c:16035
SCIP_RETCODE SCIPincludeSepaStrongcg(SCIP *scip)
SCIP_Real SCIPgetRowMinCoef(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30473
#define SCIPerrorMessage
Definition: pub_message.h:45
#define SEPA_FREQ
Definition: sepa_strongcg.c:34
int SCIPgetNCutsFound(SCIP *scip)
Definition: scip.c:41951
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip.h:21938
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
Definition: sepa.c:759
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip.c:33779
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16552
SCIP_Bool SCIProwIsIntegral(SCIP_ROW *row)
Definition: lp.c:16410
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
Definition: sepa.c:553
#define NULL
Definition: lpi_spx1.cpp:137
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:17540
#define SCIP_CALL(x)
Definition: def.h:306
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46125
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:16321
SCIP_Real SCIPgetRowLPActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30562
SCIP_RETCODE SCIPaddCut(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip.c:33869
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
Definition: lp.c:16430
#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:7325
SCIP_Bool SCIPsepaWasLPDelayed(SCIP_SEPA *sepa)
Definition: sepa.c:869
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21925
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:61
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:28854
#define SEPA_MAXBOUNDDIST
Definition: sepa_strongcg.c:35
#define DEFAULT_MAXSEPACUTS
Definition: sepa_strongcg.c:41
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:42094
#define MAX(x, y)
Definition: tclique_def.h:75
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:33964
SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip.c:30051
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip.c:33738
SCIP_RETCODE SCIPgetLPBasisInd(SCIP *scip, int *basisind)
Definition: scip.c:29281
#define SCIP_REAL_MAX
Definition: def.h:136
#define DEFAULT_MAXWEIGHTRANGE
Definition: sepa_strongcg.c:44
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip.c:30160
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip.c:7383
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition: lp.c:16081
void SCIProwChgRank(SCIP_ROW *row, int rank)
Definition: lp.c:16533
#define DEFAULT_DYNAMICCUTS
Definition: sepa_strongcg.c:43
#define MAKECONTINTEGRAL
Definition: sepa_strongcg.c:54
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16671
#define SCIP_Real
Definition: def.h:135
SCIP_RETCODE SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:30314
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1138
static SCIP_RETCODE storeCutInArrays(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_Real *cutcoefs, SCIP_Real *varsolvals, char normtype, SCIP_VAR **cutvars, SCIP_Real *cutvals, int *cutlen, SCIP_Real *cutact, SCIP_Real *cutnorm)
Definition: sepa_strongcg.c:80
#define SCIP_Longint
Definition: def.h:120
Strong CG Cuts (Letchford & Lodi)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16717
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:45864
SCIP_Real SCIPgetVarSol(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:19446
SCIP_Real SCIPsumepsilon(SCIP *scip)
Definition: scip.c:45260
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip.c:29165
SCIP_Longint SCIPgetNLPs(SCIP *scip)
Definition: scip.c:41363
#define MAXAGGRLEN(nvars)
Definition: sepa_strongcg.c:58
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:16743
SCIP_RETCODE SCIPmakeRowIntegral(SCIP *scip, SCIP_ROW *row, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Longint maxdnom, SCIP_Real maxscale, SCIP_Bool usecontvars, SCIP_Bool *success)
Definition: scip.c:30431
SCIP_Real SCIProwGetNorm(SCIP_ROW *row)
Definition: lp.c:16287
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4258
struct SCIP_SepaData SCIP_SEPADATA
Definition: type_sepa.h:38
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4176
SCIP_Real SCIPgetRowActivity(SCIP *scip, SCIP_ROW *row)
Definition: scip.c:30673