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