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