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