Scippy

SCIP

Solving Constraint Integer Programs

sepa_impliedbounds.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-2022 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 scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file sepa_impliedbounds.c
17  * @ingroup DEFPLUGINS_SEPA
18  * @brief implied bounds separator
19  * @author Kati Wolter
20  * @author Tobias Achterberg
21  */
22 
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24 
25 #include "blockmemshell/memory.h"
26 #include "scip/pub_implics.h"
27 #include "scip/pub_lp.h"
28 #include "scip/pub_message.h"
29 #include "scip/pub_misc.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_lp.h"
35 #include "scip/scip_mem.h"
36 #include "scip/scip_message.h"
37 #include "scip/scip_numerics.h"
38 #include "scip/scip_param.h"
39 #include "scip/scip_prob.h"
40 #include "scip/scip_sepa.h"
41 #include "scip/scip_sol.h"
42 #include "scip/scip_solvingstats.h"
43 #include "scip/scip_var.h"
45 #include <string.h>
46 
47 
48 #define SEPA_NAME "impliedbounds"
49 #define SEPA_DESC "implied bounds separator"
50 #define SEPA_PRIORITY -50
51 #define SEPA_FREQ 10
52 #define SEPA_MAXBOUNDDIST 1.0
53 #define SEPA_USESSUBSCIP FALSE /**< does the separator use a secondary SCIP instance? */
54 #define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */
55 
56 #define RELCUTCOEFMAXRANGE 1.0 /**< maximal allowed range of cut coefficients, relative to 1/feastol */
57 #define DEFAULT_USETWOSIZECLIQUES TRUE /**< should violated inequalities for cliques with 2 variables be separated? */
58 
59 /** separator-specific data for the implied bounds separator */
60 struct SCIP_SepaData
61 {
62  SCIP_Bool usetwosizecliques; /**< should violated inequalities for cliques with 2 variables be separated? */
63 };
64 
65 /*
66  * Local methods
67  */
68 
69 /** adds given cut with two variables, if it is violated */
70 static
72  SCIP* scip, /**< SCIP data structure */
73  SCIP_SEPA* sepa, /**< separator */
74  SCIP_Real val1, /**< given coefficient of first variable */
75  SCIP_VAR* var1, /**< given first variable */
76  SCIP_Real solval1, /**< current LP solution value of first variable */
77  SCIP_Real val2, /**< given coefficient of second variable */
78  SCIP_VAR* var2, /**< given second variable */
79  SCIP_Real solval2, /**< current LP solution value of second variable */
80  SCIP_Real rhs, /**< given right hand side of the cut to add */
81  SCIP_Bool* cutoff, /**< whether a cutoff has been detected */
82  int* ncuts /**< pointer to update number of cuts added */
83  )
84 {
85  SCIP_Real activity;
86 
87  assert(ncuts != NULL);
88  assert(cutoff != NULL);
89  *cutoff = FALSE;
90 
91  /* calculate activity of cut */
92  activity = val1 * solval1 + val2 * solval2;
93  /*SCIPdebugMsg(scip, " -> %g<%s>[%g] + %g<%s>[%g] <= %g (act: %g)\n",
94  val1, SCIPvarGetName(var1), solval1, val2, SCIPvarGetName(var2), solval2, rhs, activity);*/
95 
96  /* check, if cut is violated */
97  if( SCIPisEfficacious(scip, activity - rhs) )
98  {
99  SCIP_ROW* cut;
100  char cutname[SCIP_MAXSTRLEN];
101 
102  /* create cut */
103  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "implbd%" SCIP_LONGINT_FORMAT "_%d", SCIPgetNLPs(scip), *ncuts);
104  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), rhs, FALSE, FALSE, TRUE) );
105  SCIP_CALL( SCIPcacheRowExtensions(scip, cut) );
106  SCIP_CALL( SCIPaddVarToRow(scip, cut, var1, val1) );
107  SCIP_CALL( SCIPaddVarToRow(scip, cut, var2, val2) );
108  SCIP_CALL( SCIPflushRowExtensions(scip, cut) );
109  /* set cut rank: for implied bounds we always set to 1 */
110  SCIProwChgRank(cut, 1);
111 
112 #ifdef SCIP_DEBUG
113  SCIPdebugMsg(scip, " -> found cut (activity = %g): ", activity);
114  SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
115 #endif
116 
117  SCIP_CALL( SCIPaddPoolCut(scip, cut) );
118  (*ncuts)++;
119 
120  /* release cut */
121  SCIP_CALL( SCIPreleaseRow(scip, &cut) );
122  }
123 
124  return SCIP_OKAY;
125 }
126 
127 /** searches and adds implied bound cuts that are violated by the given solution value array */
128 static
130  SCIP* scip, /**< SCIP data structure */
131  SCIP_SEPA* sepa, /**< separator */
132  SCIP_SOL* sol, /**< the solution that should be separated, or NULL for LP solution */
133  SCIP_Real* solvals, /**< array with solution values of all problem variables */
134  SCIP_VAR** fracvars, /**< array of fractional variables */
135  SCIP_Real* fracvals, /**< solution values of fractional variables */
136  int nfracs, /**< number of fractional variables */
137  SCIP_Bool* cutoff, /**< whether a cutoff has been detected */
138  int* ncuts /**< pointer to store the number of generated cuts */
139  )
140 {
141  SCIP_CLIQUE** cliques;
142  SCIP_SEPADATA* sepadata;
143  int ncliques;
144  int i;
145 
146  assert(solvals != NULL);
147  assert(fracvars != NULL || nfracs == 0);
148  assert(fracvals != NULL || nfracs == 0);
149  assert(cutoff != NULL);
150  assert(ncuts != NULL);
151 
152  *cutoff = FALSE;
153  *ncuts = 0;
154  sepadata = SCIPsepaGetData(sepa);
155  assert(sepadata != NULL);
156 
157  SCIPdebugMsg(scip, "searching for implied bound cuts\n");
158 
159  /* search binary variables for violated implications */
160  for( i = 0; i < nfracs; i++ )
161  {
162  SCIP_BOUNDTYPE* impltypes;
163  SCIP_Real* implbounds;
164  SCIP_VAR** implvars;
165  int nimpl;
166  int j;
167 
168  assert(fracvars != NULL);
169  assert(fracvals != NULL);
170 
171  /* only process binary variables */
172  if( SCIPvarGetType(fracvars[i]) != SCIP_VARTYPE_BINARY )
173  continue;
174 
175  /* get implications of x == 1 */
176  nimpl = SCIPvarGetNImpls(fracvars[i], TRUE);
177  implvars = SCIPvarGetImplVars(fracvars[i], TRUE);
178  impltypes = SCIPvarGetImplTypes(fracvars[i], TRUE);
179  implbounds = SCIPvarGetImplBounds(fracvars[i], TRUE);
180 
181  /*SCIPdebugMsg(scip, "%d implications for <%s>[%g] == 1\n", nimpl, SCIPvarGetName(fracvars[i]), fracvals[i]);*/
182 
183  /* try to add cuts for implications of x == 1
184  * x == 1 -> y <= p: y <= ub + x * (p - ub) <==> y + (ub - p) * x <= ub
185  * x == 1 -> y >= p: y >= lb + x * (p - lb) <==> -y + (p - lb) * x <= -lb
186  * with lb (ub) global lower (upper) bound of y
187  */
188  for( j = 0; j < nimpl; j++ )
189  {
190  SCIP_Real solval;
191 
192  assert(implvars != NULL);
193  assert(impltypes != NULL);
194  assert(implbounds != NULL);
195 
196  /* consider only implications with active implvar */
197  if( SCIPvarGetProbindex(implvars[j]) < 0 )
198  continue;
199 
200  solval = solvals[SCIPvarGetProbindex(implvars[j])];
201  if( impltypes[j] == SCIP_BOUNDTYPE_UPPER )
202  {
203  SCIP_Real ub;
204 
205  /* implication x == 1 -> y <= p */
206  ub = SCIPvarGetUbGlobal(implvars[j]);
207 
208  /* consider only nonredundant and numerical harmless implications */
209  if( SCIPisLE(scip, implbounds[j], ub) && (ub - implbounds[j]) * SCIPfeastol(scip) <= RELCUTCOEFMAXRANGE )
210  {
211  /* add cut if violated */
212  SCIP_CALL( addCut(scip, sepa, 1.0, implvars[j], solval, (ub - implbounds[j]), fracvars[i], fracvals[i],
213  ub, cutoff, ncuts) );
214  if ( *cutoff )
215  return SCIP_OKAY;
216  }
217  }
218  else
219  {
220  SCIP_Real lb;
221 
222  /* implication x == 1 -> y >= p */
223  lb = SCIPvarGetLbGlobal(implvars[j]);
224  assert(impltypes[j] == SCIP_BOUNDTYPE_LOWER);
225 
226  /* consider only nonredundant and numerical harmless implications */
227  if( SCIPisGE(scip, implbounds[j], lb) && (implbounds[j] - lb) * SCIPfeastol(scip) <= RELCUTCOEFMAXRANGE )
228  {
229  /* add cut if violated */
230  SCIP_CALL( addCut(scip, sepa, -1.0, implvars[j], solval, (implbounds[j] - lb), fracvars[i], fracvals[i],
231  -lb, cutoff, ncuts) );
232  if ( *cutoff )
233  return SCIP_OKAY;
234  }
235  }
236  }
237 
238  /* get implications of x == 0 */
239  nimpl = SCIPvarGetNImpls(fracvars[i], FALSE);
240  implvars = SCIPvarGetImplVars(fracvars[i], FALSE);
241  impltypes = SCIPvarGetImplTypes(fracvars[i], FALSE);
242  implbounds = SCIPvarGetImplBounds(fracvars[i], FALSE);
243 
244  /*SCIPdebugMsg(scip, "%d implications for <%s>[%g] == 0\n", nimpl, SCIPvarGetName(fracvars[i]), fracvals[i]);*/
245 
246  /* try to add cuts for implications of x == 0
247  * x == 0 -> y <= p: y <= p + x * (ub - p) <==> y + (p - ub) * x <= p
248  * x == 0 -> y >= p: y >= p + x * (lb - p) <==> -y + (lb - p) * x <= -p
249  * with lb (ub) global lower (upper) bound of y
250  */
251  for( j = 0; j < nimpl; j++ )
252  {
253  SCIP_Real solval;
254 
255  /* consider only implications with active implvar */
256  if( SCIPvarGetProbindex(implvars[j]) < 0 )
257  continue;
258 
259  solval = solvals[SCIPvarGetProbindex(implvars[j])];
260  if( impltypes[j] == SCIP_BOUNDTYPE_UPPER )
261  {
262  SCIP_Real ub;
263 
264  /* implication x == 0 -> y <= p */
265  ub = SCIPvarGetUbGlobal(implvars[j]);
266 
267  /* consider only nonredundant and numerical harmless implications */
268  if( SCIPisLE(scip, implbounds[j], ub) && (ub - implbounds[j]) * SCIPfeastol(scip) < RELCUTCOEFMAXRANGE )
269  {
270  /* add cut if violated */
271  SCIP_CALL( addCut(scip, sepa, 1.0, implvars[j], solval, (implbounds[j] - ub), fracvars[i], fracvals[i],
272  implbounds[j], cutoff, ncuts) );
273  if ( *cutoff )
274  return SCIP_OKAY;
275  }
276  }
277  else
278  {
279  SCIP_Real lb;
280 
281  /* implication x == 0 -> y >= p */
282  lb = SCIPvarGetLbGlobal(implvars[j]);
283  assert(impltypes[j] == SCIP_BOUNDTYPE_LOWER);
284 
285  /* consider only nonredundant and numerical harmless implications */
286  if( SCIPisGE(scip, implbounds[j], lb) && (implbounds[j] - lb) * SCIPfeastol(scip) < RELCUTCOEFMAXRANGE )
287  {
288  /* add cut if violated */
289  SCIP_CALL( addCut(scip, sepa, -1.0, implvars[j], solval, (lb - implbounds[j]), fracvars[i], fracvals[i],
290  -implbounds[j], cutoff, ncuts) );
291  if ( *cutoff )
292  return SCIP_OKAY;
293  }
294  }
295  }
296  }
297 
298  /* stop separation here if cliques should not be separated */
299  if( ! sepadata->usetwosizecliques )
300  return SCIP_OKAY;
301 
302  /* prepare clean clique data */
303  SCIP_CALL( SCIPcleanupCliques(scip, cutoff) );
304 
305  if( *cutoff )
306  return SCIP_OKAY;
307 
308  cliques = SCIPgetCliques(scip);
309  ncliques = SCIPgetNCliques(scip);
310 
311  /* loop over cliques of size 2 which are essentially implications and add cuts if they are violated */
312  for( i = 0; i < ncliques; ++i )
313  {
314  SCIP_CLIQUE* clique;
315  SCIP_VAR** clqvars;
316  SCIP_Bool* clqvals;
317  SCIP_Real rhs;
318 
319  clique = cliques[i];
320  /* only consider inequality cliques of size 2 */
321  if( SCIPcliqueGetNVars(clique) != 2 || SCIPcliqueIsEquation(clique) )
322  continue;
323 
324  /* get variables and values of the clique */
325  clqvars = SCIPcliqueGetVars(clique);
326  clqvals = SCIPcliqueGetValues(clique);
327 
328  /* clique variables should never be equal after clean up */
329  assert(clqvars[0] != clqvars[1]);
330 
331  /* calculate right hand side of clique inequality, which is initially 1 and decreased by 1 for every occurence of
332  * a negated variable in the clique
333  */
334  rhs = 1.0;
335  if( ! clqvals[0] )
336  rhs -= 1.0;
337  if( ! clqvals[1] )
338  rhs -= 1.0;
339 
340  /* Basic clique inequality is
341  *
342  * cx * x + (1-cx) (1-x) + cy * y + (1-cy) * (1-y) <= 1,
343  *
344  * where x and y are the two binary variables in the clique and cx and cy are their clique values, where a
345  * clique value of 0 means that the negation of the variable should be part of the inequality.
346  * Hence, exactly one of the two possible terms for x and y has a nonzero coefficient
347  */
348  SCIP_CALL( addCut(scip, sepa,
349  clqvals[0] ? 1.0 : -1.0, clqvars[0], SCIPgetSolVal(scip, sol, clqvars[0]),
350  clqvals[1] ? 1.0 : -1.0, clqvars[1], SCIPgetSolVal(scip, sol, clqvars[1]),
351  rhs, cutoff, ncuts) );
352 
353  /* terminate if cutoff was found */
354  if( *cutoff )
355  return SCIP_OKAY;
356  }
357 
358  return SCIP_OKAY;
359 }
360 
361 
362 /*
363  * Callback methods of separator
364  */
365 
366 /** copy method for separator plugins (called when SCIP copies plugins) */
367 static
368 SCIP_DECL_SEPACOPY(sepaCopyImpliedbounds)
369 { /*lint --e{715}*/
370  assert(scip != NULL);
371  assert(sepa != NULL);
372  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
373 
374  /* call inclusion method of constraint handler */
376 
377  return SCIP_OKAY;
378 }
379 
380 /** destructor of separator to free user data (called when SCIP is exiting) */
381 static
382 SCIP_DECL_SEPAFREE(sepaFreeImpliedbounds)
383 { /*lint --e{715}*/
384  SCIP_SEPADATA* sepadata;
385 
386  assert(scip != NULL);
387  assert(sepa != NULL);
388  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
389 
390  /* get separation data and free it */
391  sepadata = SCIPsepaGetData(sepa);
392  assert(sepadata != NULL);
393  SCIPfreeBlockMemory(scip, &sepadata);
394 
395  /* reset data pointer to NULL */
396  SCIPsepaSetData(sepa, NULL);
397 
398  return SCIP_OKAY;
399 }
400 
401 
402 /** LP solution separation method of separator */
403 static
404 SCIP_DECL_SEPAEXECLP(sepaExeclpImpliedbounds)
405 { /*lint --e{715}*/
406  SCIP_VAR** vars;
407  SCIP_VAR** fracvars;
408  SCIP_Real* solvals;
409  SCIP_Real* fracvals;
410  SCIP_Bool cutoff;
411  int nvars;
412  int nbinvars;
413  int nfracs;
414  int ncuts;
415 
416  assert(sepa != NULL);
417  assert(scip != NULL);
418 
419  *result = SCIP_DIDNOTRUN;
420 
421  /* gets active problem variables */
422  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, NULL, NULL, NULL) );
423  if( nbinvars == 0 )
424  return SCIP_OKAY;
425 
426  /* get fractional problem variables */
427  /* todo try out also separating fractional implicit integer variables */
428  SCIP_CALL( SCIPgetLPBranchCands(scip, &fracvars, &fracvals, NULL, &nfracs, NULL, NULL) );
429  if( nfracs == 0 )
430  return SCIP_OKAY;
431 
432  /* get solution values for all variables */
433  SCIP_CALL( SCIPallocBufferArray(scip, &solvals, nvars) );
434  SCIP_CALL( SCIPgetVarSols(scip, nvars, vars, solvals) );
435 
436  /* call the cut separation */
437  SCIP_CALL( separateCuts(scip, sepa, NULL, solvals, fracvars, fracvals, nfracs, &cutoff, &ncuts) );
438 
439  /* adjust result code */
440  if ( cutoff )
441  *result = SCIP_CUTOFF;
442  else if ( ncuts > 0 )
443  *result = SCIP_SEPARATED;
444  else
445  *result = SCIP_DIDNOTFIND;
446 
447  /* free temporary memory */
448  SCIPfreeBufferArray(scip, &solvals);
449 
450  return SCIP_OKAY;
451 }
452 
453 
454 /** arbitrary primal solution separation method of separator */
455 static
456 SCIP_DECL_SEPAEXECSOL(sepaExecsolImpliedbounds)
457 { /*lint --e{715}*/
458  SCIP_VAR** vars;
459  SCIP_VAR** fracvars;
460  SCIP_Real* solvals;
461  SCIP_Real* fracvals;
462  SCIP_Bool cutoff;
463  int nvars;
464  int nbinvars;
465  int nfracs;
466  int ncuts;
467  int i;
468 
469  assert(sepa != NULL);
470  assert(scip != NULL);
471 
472  *result = SCIP_DIDNOTRUN;
473 
474  /* gets active problem variables */
475  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, NULL, NULL, NULL) );
476  if( nbinvars == 0 )
477  return SCIP_OKAY;
478 
479  /* get solution values for all variables */
480  SCIP_CALL( SCIPallocBufferArray(scip, &solvals, nvars) );
481  SCIP_CALL( SCIPgetSolVals(scip, sol, nvars, vars, solvals) );
482 
483  /* get binary problem variables that are fractional in given solution */
484  SCIP_CALL( SCIPallocBufferArray(scip, &fracvars, nbinvars) );
485  SCIP_CALL( SCIPallocBufferArray(scip, &fracvals, nbinvars) );
486  nfracs = 0;
487  for( i = 0; i < nbinvars; ++i )
488  {
489  if( !SCIPisFeasIntegral(scip, solvals[i]) )
490  {
491  fracvars[nfracs] = vars[i];
492  fracvals[nfracs] = solvals[i];
493  nfracs++;
494  }
495  }
496 
497  /* call the cut separation */
498  ncuts = 0;
499  cutoff = FALSE;
500 
501  if( nfracs > 0 )
502  {
503  SCIP_CALL( separateCuts(scip, sepa, sol, solvals, fracvars, fracvals, nfracs, &cutoff, &ncuts) );
504  }
505 
506  /* adjust result code */
507  if ( cutoff )
508  *result = SCIP_CUTOFF;
509  else if ( ncuts > 0 )
510  *result = SCIP_SEPARATED;
511  else
512  *result = SCIP_DIDNOTFIND;
513 
514  /* free temporary memory */
515  SCIPfreeBufferArray(scip, &fracvals);
516  SCIPfreeBufferArray(scip, &fracvars);
517  SCIPfreeBufferArray(scip, &solvals);
518 
519  return SCIP_OKAY;
520 }
521 
522 
523 /*
524  * separator specific interface methods
525  */
526 
527 /** creates the impliedbounds separator and includes it in SCIP */
529  SCIP* scip /**< SCIP data structure */
530  )
531 {
532  SCIP_SEPADATA* sepadata;
533  SCIP_SEPA* sepa;
534 
535  /* create impliedbounds separator data */
536  SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) );
537  assert(sepadata != NULL);
538 
539  /* include separator */
542  sepaExeclpImpliedbounds, sepaExecsolImpliedbounds,
543  sepadata) );
544  assert(sepa != NULL);
545 
546  /* set non-NULL pointers to callback methods */
547  SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyImpliedbounds) );
548  SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeImpliedbounds) );
549 
550  /* add separator parameters */
551  SCIP_CALL( SCIPaddBoolParam(scip, "separating/impliedbounds/usetwosizecliques",
552  "should violated inequalities for cliques with 2 variables be separated?",
553  &sepadata->usetwosizecliques, TRUE, DEFAULT_USETWOSIZECLIQUES, NULL, NULL) );
554 
555  return SCIP_OKAY;
556 }
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:386
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
static SCIP_DECL_SEPAEXECLP(sepaExeclpImpliedbounds)
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
Definition: implics.c:3368
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1626
public methods for SCIP parameter handling
public methods for memory management
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1649
static SCIP_DECL_SEPAFREE(sepaFreeImpliedbounds)
public methods for implications, variable bounds, and cliques
#define SEPA_MAXBOUNDDIST
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17910
#define SCIP_MAXSTRLEN
Definition: def.h:293
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1686
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SEPA_PRIORITY
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1865
#define FALSE
Definition: def.h:87
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
#define SEPA_DELAY
#define TRUE
Definition: def.h:86
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition: sepa.c:734
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_Bool SCIPcliqueIsEquation(SCIP_CLIQUE *clique)
Definition: implics.c:3424
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17600
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
static SCIP_RETCODE addCut(SCIP *scip, SCIP_SEPA *sepa, SCIP_Real val1, SCIP_VAR *var1, SCIP_Real solval1, SCIP_Real val2, SCIP_VAR *var2, SCIP_Real solval2, SCIP_Real rhs, SCIP_Bool *cutoff, int *ncuts)
#define SEPA_USESSUBSCIP
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
public methods for SCIP variables
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip_sepa.c:142
#define SCIPdebugMsg
Definition: scip_message.h:69
public methods for separator plugins
#define DEFAULT_USETWOSIZECLIQUES
public methods for numerical tolerances
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
Definition: sepa.c:624
public methods for querying solving statistics
#define SEPA_FREQ
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17920
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1389
SCIP_RETCODE SCIPincludeSepaImpliedbounds(SCIP *scip)
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip_cut.c:126
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
Definition: sepa.c:634
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_CALL(x)
Definition: def.h:384
#define RELCUTCOEFMAXRANGE
static SCIP_DECL_SEPAEXECSOL(sepaExecsolImpliedbounds)
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:100
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
public data structures and miscellaneous methods
SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18220
#define SCIP_Bool
Definition: def.h:84
#define SEPA_DESC
int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18188
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip_cut.c:352
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
Definition: implics.c:3380
public methods for LP management
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:1444
public methods for cuts and aggregation rows
SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18234
public methods for the LP relaxation, rows and columns
SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18205
SCIP_CLIQUE ** SCIPgetCliques(SCIP *scip)
Definition: scip_var.c:7626
implied bounds separator
public methods for branching rule plugins and branching
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1553
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip_sepa.c:158
public methods for solutions
SCIP_RETCODE SCIPgetVarSols(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_var.c:2324
void SCIProwChgRank(SCIP_ROW *row, int rank)
Definition: lp.c:17500
public methods for message output
static SCIP_DECL_SEPACOPY(sepaCopyImpliedbounds)
int SCIPgetNCliques(SCIP *scip)
Definition: scip_var.c:7572
#define SCIP_Real
Definition: def.h:177
public methods for message handling
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2197
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17416
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
Definition: implics.c:3358
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
#define SEPA_NAME
public methods for separators
SCIPallocBlockMemory(scip, subsol))
SCIP_RETCODE SCIPcleanupCliques(SCIP *scip, SCIP_Bool *infeasible)
Definition: scip_var.c:7529
SCIP_Longint SCIPgetNLPs(SCIP *scip)
public methods for global and local (sub)problems
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
struct SCIP_SepaData SCIP_SEPADATA
Definition: type_sepa.h:43
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:48
static SCIP_RETCODE separateCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_Real *solvals, SCIP_VAR **fracvars, SCIP_Real *fracvals, int nfracs, SCIP_Bool *cutoff, int *ncuts)
memory allocation routines