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   cutsel_dynamic.c
17   	 * @ingroup DEFPLUGINS_CUTSEL
18   	 * @brief  dynamic cut selector
19   	 * @author Christoph Graczyk
20   	 */
21   	
22   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23   	
24   	#include <assert.h>
25   	
26   	
27   	#include "scip/scip_cutsel.h"
28   	#include "scip/scip_cut.h"
29   	#include "scip/scip_lp.h"
30   	#include "scip/scip_randnumgen.h"
31   	#include "scip/cutsel_dynamic.h"
32   	
33   	
34   	#define CUTSEL_NAME               "dynamic"
35   	#define CUTSEL_DESC               "dynamic orthogonality for hybrid cutsel"
36   	#define CUTSEL_PRIORITY           7000
37   	
38   	#define RANDSEED                  0x5EED
39   	
40   	#define DEFAULT_EFFICACYWEIGHT          1.0  /**< weight of efficacy in score calculation */
41   	#define DEFAULT_DIRCUTOFFDISTWEIGHT     0.0  /**< weight of directed cutoff distance in score calculation */
42   	#define DEFAULT_OBJPARALWEIGHT          0.0  /**< weight of objective parallelism in score calculation */
43   	#define DEFAULT_INTSUPPORTWEIGHT        0.0  /**< weight of integral support in cut score calculation */
44   	#define DEFAULT_MINORTHO                0.9  /**< minimal orthogonality in percent for a cut to enter the LP */
45   	#define DEFAULT_MINGAIN                 0.01 /**< minimal efficacy gain for a cut to enter the LP */
46   	#define DEFAULT_MAXDEPTH                (-1) /**< maximum depth at which this cutselector is used (-1 : all nodes) */
47   	#define DEFAULT_FILTERMODE              'd'  /**< filtering strategy during cut selection (
48   	                                               *  'd'ynamic-  and 'f'ull dynamic parallelism) */
49   	
50   	
51   	/*
52   	 * Data structures
53   	 */
54   	
55   	/** cut selector data */
56   	struct SCIP_CutselData
57   	{
58   	   SCIP_RANDNUMGEN*      randnumgen;         /**< random generator for tiebreaking */
59   	   SCIP_Real             objparalweight;     /**< weight of objective parallelism in cut score calculation */
60   	   SCIP_Real             efficacyweight;     /**< weight of efficacy in cut score calculation */
61   	   SCIP_Real             dircutoffdistweight;/**< weight of directed cutoff distance in cut score calculation */
62   	   SCIP_Real             intsupportweight;   /**< weight of integral support in cut score calculation */
63   	   SCIP_Real             mingain;            /**< minimal projection efficacy gain for a cut to enter the LP in percent */
64   	   SCIP_Real             minortho;           /**< minimal orthogonality for a cut to enter the LP */
65   	   int                   maxdepth;           /**< maximum depth at which this cutselector is used (-1 : all nodes) */
66   	   char                  filtermode;         /**< filtering strategy during cut selection (
67   	                                              *  'd'ynamic- and 'f'ull dynamic parallelism) */
68   	};
69   	
70   	/*
71   	 * Local methods
72   	 */
73   	
74   	/* put your local methods here, and declare them static */
75   	
76   	/** returns the maximum score of cuts; if scores is not NULL, then stores the individual score of each cut in scores */
77   	static
78   	void scoring(
79   	   SCIP*                 scip,               /**< SCIP data structure */
80   	   SCIP_ROW**            cuts,               /**< array with cuts to score */
81   	   SCIP_RANDNUMGEN*      randnumgen,         /**< random number generator for tie-breaking, or NULL */
82   	   SCIP_Real             dircutoffdistweight,/**< weight of directed cutoff distance in cut score calculation */
83   	   SCIP_Real             efficacyweight,     /**< weight of efficacy in cut score calculation */
84   	   SCIP_Real             objparalweight,     /**< weight of objective parallelism in cut score calculation */
85   	   SCIP_Real             intsupportweight,   /**< weight of integral support in cut score calculation */
86   	   int*                  currentncuts,       /**< current number of cuts in cuts array */
87   	   SCIP_Real*            scores              /**< array to store the score of cuts or NULL */
88   	   )
89   	{
90   	   SCIP_Real maxscore = 0.0;
91   	   SCIP_SOL* sol;
92   	   int i;
93   	   int ncuts = *currentncuts;
94   	
95   	   sol = SCIPgetBestSol(scip);
96   	
97   	   /* if there is an incumbent and the factor is not 0.0, compute directed cutoff distances for the incumbent */
98   	   if( sol != NULL && dircutoffdistweight > 0.0 )
99   	   {
100  	      for( i = ncuts-1; i >= 0; --i )
101  	      {
102  	         SCIP_Real score;
103  	         SCIP_Real objparallelism;
104  	         SCIP_Real intsupport;
105  	         SCIP_Real efficacy;
106  	
107  	         if( intsupportweight > 0.0 )
108  	            intsupport = intsupportweight * SCIPgetRowNumIntCols(scip, cuts[i]) / (SCIP_Real) SCIProwGetNNonz(cuts[i]);
109  	         else
110  	            intsupport = 0.0;
111  	
112  	         if( objparalweight > 0.0 )
113  	            objparallelism = objparalweight * SCIPgetRowObjParallelism(scip, cuts[i]);
114  	         else
115  	            objparallelism = 0.0;
116  	
117  	         efficacy = SCIPgetCutEfficacy(scip, NULL, cuts[i]);
118  	
119  	         if( SCIProwIsLocal(cuts[i]) )
120  	         {
121  	            score = dircutoffdistweight * efficacy;
122  	         }
123  	         else
124  	         {
125  	            score = SCIPgetCutLPSolCutoffDistance(scip, sol, cuts[i]);
126  	            score = dircutoffdistweight * MAX(score, efficacy);
127  	         }
128  	
129  	         efficacy *= efficacyweight;
130  	         score += objparallelism + intsupport + efficacy;
131  	
132  	         /* add small term to prefer global pool cuts */
133  	         if( SCIProwIsInGlobalCutpool(cuts[i]) )
134  	            score += 1e-4;
135  	
136  	         if( randnumgen != NULL)
137  	         {
138  	            score += SCIPrandomGetReal(randnumgen, 0.0, 1e-6);
139  	         }
140  	
141  	         maxscore = MAX(maxscore, score);
142  	
143  	         if( scores != NULL)
144  	         {
145  	            if( SCIPisLE(scip, score, 0.0) )
146  	            {
147  	               --ncuts;
148  	               SCIPswapPointers((void**) &cuts[i], (void**) &cuts[ncuts]);
149  	               SCIPswapReals(&scores[i], &scores[ncuts]);
150  	            }
151  	            else
152  	               scores[i] = score;
153  	         }
154  	      }
155  	   }
156  	   else
157  	   {
158  	      /* in case there is no solution add the directed cutoff distance weight to the efficacy weight
159  	         * since the efficacy underestimates the directed cuttoff distance
160  	       */
161  	      efficacyweight += dircutoffdistweight;
162  	
163  	      /*lint -e{850} i is modified in the body of the for loop */
164  	      for( i = ncuts-1; i >= 0; --i )
165  	      {
166  	         SCIP_Real score;
167  	         SCIP_Real objparallelism;
168  	         SCIP_Real intsupport;
169  	         SCIP_Real efficacy;
170  	
171  	         if( intsupportweight > 0.0 )
172  	            intsupport = intsupportweight * SCIPgetRowNumIntCols(scip, cuts[i]) / (SCIP_Real) SCIProwGetNNonz(cuts[i]);
173  	         else
174  	            intsupport = 0.0;
175  	
176  	         if( objparalweight > 0.0 )
177  	            objparallelism = objparalweight * SCIPgetRowObjParallelism(scip, cuts[i]);
178  	         else
179  	            objparallelism = 0.0;
180  	
181  	         efficacy = efficacyweight > 0.0 ? efficacyweight * SCIPgetCutEfficacy(scip, NULL, cuts[i]) : 0.0;
182  	
183  	         score = objparallelism + intsupport + efficacy;
184  	
185  	         /* add small term to prefer global pool cuts */
186  	         if( SCIProwIsInGlobalCutpool(cuts[i]) )
187  	            score += 1e-4;
188  	
189  	         if( randnumgen != NULL)
190  	         {
191  	            score += SCIPrandomGetReal(randnumgen, 0.0, 1e-6);
192  	         }
193  	
194  	         maxscore = MAX(maxscore, score);
195  	
196  	         if( scores != NULL)
197  	         {
198  	            if( SCIPisLE(scip, score, 0.0) )
199  	            {
200  	               --ncuts;
201  	               SCIPswapPointers((void**) &cuts[i], (void**) &cuts[ncuts]);
202  	               SCIPswapReals(&scores[i], &scores[ncuts]);
203  	            }
204  	            else
205  	               scores[i] = score;
206  	         }
207  	      }
208  	   }
209  	   *currentncuts = ncuts;
210  	}
211  	
212  	/** compute projectioncut score for cuts from a given bestcut. **/
213  	static
214  	SCIP_RETCODE computeProjectionScore(
215  	   SCIP*                 scip,               /**< SCIP data structure */
216  	   SCIP_ROW*             bestcut,            /**< cut to filter orthogonality with */
217  	   SCIP_ROW*             cut,                /**< cut to perform scoring on */
218  	   SCIP_Real*            score              /**< score for cut */
219  	   )
220  	{
221  	   SCIP_Real efficacy;
222  	   SCIP_Real currentbestefficacy;
223  	   SCIP_Real cosineangle;
224  	
225  	   SCIPdebugMsg(scip, "\ncomputeProjectionScore.\n\n");
226  	   currentbestefficacy = SCIPgetCutEfficacy(scip, NULL, bestcut);
227  	   SCIPdebugMsg(scip, "currentbestefficacy = %g\n", currentbestefficacy);
228  	
229  	   efficacy = SCIPgetCutEfficacy(scip, NULL, cut);
230  	   SCIPdebugMsg(scip, "efficacy[%s] = %g\n", SCIProwGetName(cut), efficacy);
231  	
232  	   cosineangle = SCIProwGetParallelism(bestcut, cut, 'e');
233  	   if( SCIPisEQ(scip, cosineangle, 1.0))
234  	      *score = -SCIPinfinity(scip);
235  	   else
236  	   {
237  	      *score = SQRT(currentbestefficacy * currentbestefficacy + efficacy * efficacy
238  	                       - 2 * fabs(currentbestefficacy) * fabs(efficacy) * cosineangle)
239  	         / SQRT((1 - (cosineangle * cosineangle)));
240  	      *score -= currentbestefficacy;
241  	   }
242  	   SCIPdebugMsg(scip, "Projectionscore[%s] = %g\n", SCIProwGetName(cut), *score);
243  	   return SCIP_OKAY;
244  	}
245  	
246  	/** move the cut with the highest score to the first position in the array; there must be at least one cut */
247  	static
248  	void selectBestCut(
249  	    SCIP_ROW**           cuts,               /**< array with cuts to perform selection algorithm */
250  	    SCIP_Real*           scores,             /**< array with scores of cuts to perform selection algorithm */
251  	    int                  ncuts               /**< number of cuts in given array */
252  	   )
253  	{
254  	   int i;
255  	   int bestpos;
256  	   SCIP_Real bestscore;
257  	
258  	   assert(ncuts > 0);
259  	   assert(cuts != NULL);
260  	   assert(scores != NULL);
261  	
262  	   bestscore = scores[0];
263  	   bestpos = 0;
264  	
265  	   for( i = 1; i < ncuts; ++i )
266  	   {
267  	      if( scores[i] > bestscore )
268  	      {
269  	         bestpos = i;
270  	         bestscore = scores[i];
271  	      }
272  	   }
273  	
274  	   SCIPswapPointers((void**) &cuts[bestpos], (void**) &cuts[0]);
275  	   SCIPswapReals(&scores[bestpos], &scores[0]);
276  	}
277  	
278  	/** filters the given array of cuts to enforce a maximum parallelism constraint
279  	 *  w.r.t the given cut; moves filtered cuts to the end of the array and returns number of selected cuts */
280  	static
281  	int filterWithDynamicParallelism(
282  	   SCIP*                 scip,               /**< SCIP data structure */
283  	   SCIP_ROW*             bestcut,            /**< cut to filter orthogonality with */
284  	   SCIP_ROW**            cuts,               /**< array with cuts to perform selection algorithm */
285  	   SCIP_Real*            scores,             /**< array with scores of cuts to perform selection algorithm */
286  	   SCIP_Real             mingain,            /**< minimum gain enforced on the two-cut efficacy */
287  	   SCIP_Real             maxparall,          /**< maximal parallelism for all cuts that are not good */
288  	   int                   ncuts               /**< number of cuts in given array */
289  	   )
290  	{
291  	   int i;
292  	   SCIP_Bool filter;
293  	   SCIP_Real bestcutefficacy;
294  	
295  	   SCIPdebugMsg(scip, "\nfilterWithDynamicParallelism.\n\n");
296  	
297  	   assert(bestcut != NULL);
298  	   assert(ncuts == 0 || cuts != NULL);
299  	   assert(ncuts == 0 || scores != NULL);
300  	
301  	   bestcutefficacy = SCIPgetCutEfficacy(scip, NULL, bestcut);
302  	
303  	   /*lint -e{850} i is modified in the body of the for loop */
304  	   for( i = ncuts-1; i >= 0; --i )
305  	   {
306  	      SCIP_Real thisparall;
307  	      SCIP_Real cosine;
308  	      SCIP_Real currentcutefficacy;
309  	      SCIP_Real minmaxparall;
310  	
311  	      currentcutefficacy = SCIPgetCutEfficacy(scip, NULL, cuts[i]);
312  	
313  	      if( SCIPisGE(scip, bestcutefficacy, currentcutefficacy))
314  	      {
315  	         cosine = SCIProwGetParallelism(bestcut, cuts[i], 's');
316  	         thisparall = cosine * bestcutefficacy / currentcutefficacy;
317  	         SCIPdebugMsg(scip, "Thisparall(%g) = cosine(%g) * (bestcutefficacy(%g)/ currentcutefficacy(%g))\n\n", thisparall,
318  	                      cosine, bestcutefficacy, currentcutefficacy);
319  	      }
320  	      else
321  	      {
322  	         cosine = SCIProwGetParallelism(cuts[i], bestcut, 's');
323  	         thisparall = cosine * currentcutefficacy / bestcutefficacy;
324  	         SCIPdebugMsg(scip, "Thisparall(%g) = cosine(%g) * (currentcutefficacy(%g) / bestcutefficacy(%g))\n\n", thisparall,
325  	                      cosine, currentcutefficacy, bestcutefficacy);
326  	      }
327  	
328  	      /* compute the max-minimum angle for given the given cuts to enforce
329  	       * norm(d) >= (1+mingain)*eff1 for non-negative cosine angle */
330  	      minmaxparall = MAX( (bestcutefficacy * bestcutefficacy
331  	                        + currentcutefficacy * currentcutefficacy
332  	                        - (1 + mingain) * bestcutefficacy * (1 + mingain) * bestcutefficacy * (1 - cosine * cosine))
333  	                        / (2 * bestcutefficacy * currentcutefficacy),
334  	                        maxparall );
335  	      filter = ( SCIPisGE(scip, thisparall, 1.0) || SCIPisGT(scip, cosine, minmaxparall) );
336  	
337  	      SCIPdebugMsg(scip, "Filter = %u\n", filter);
338  	
339  	      if( filter )
340  	      {
341  	         --ncuts;
342  	         SCIPswapPointers((void**) &cuts[i], (void**) &cuts[ncuts]);
343  	         SCIPswapReals(&scores[i], &scores[ncuts]);
344  	      }
345  	   }
346  	
347  	   return ncuts;
348  	}
349  	
350  	
351  	/*
352  	 * Callback methods of cut selector
353  	 */
354  	
355  	/** copy method for cut selector plugin (called when SCIP copies plugins) */
356  	static
357  	SCIP_DECL_CUTSELCOPY(cutselCopyDynamic)
358  	{  /*lint --e{715}*/
359  	  assert(scip != NULL);
360  	  assert(cutsel != NULL);
361  	  assert(strcmp(SCIPcutselGetName(cutsel), CUTSEL_NAME) == 0);
362  	
363  	  /* call inclusion method of cut selector */
364  	  SCIP_CALL( SCIPincludeCutselDynamic(scip) );
365  	
366  	  return SCIP_OKAY;
367  	}
368  	
369  	/** destructor of cut selector to free user data (called when SCIP is exiting) */
370  	/**! [SnippetCutselFreeDynamic] */
371  	static
372  	SCIP_DECL_CUTSELFREE(cutselFreeDynamic)
373  	{  /*lint --e{715}*/
374  	  SCIP_CUTSELDATA* cutseldata;
375  	
376  	  cutseldata = SCIPcutselGetData(cutsel);
377  	
378  	  SCIPfreeBlockMemory(scip, &cutseldata);
379  	
380  	  SCIPcutselSetData(cutsel, NULL);
381  	
382  	  return SCIP_OKAY;
383  	}
384  	/**! [SnippetCutselFreeDynamic] */
385  	
386  	/** initialization method of cut selector (called after problem was transformed) */
387  	static
388  	SCIP_DECL_CUTSELINIT(cutselInitDynamic)
389  	{  /*lint --e{715}*/
390  	  SCIP_CUTSELDATA* cutseldata;
391  	
392  	  cutseldata = SCIPcutselGetData(cutsel);
393  	  assert(cutseldata != NULL);
394  	
395  	  SCIP_CALL( SCIPcreateRandom(scip, &(cutseldata)->randnumgen, RANDSEED, TRUE) );
396  	
397  	  return SCIP_OKAY;
398  	}
399  	
400  	/** deinitialization method of cut selector (called before transformed problem is freed) */
401  	static
402  	SCIP_DECL_CUTSELEXIT(cutselExitDynamic)
403  	{  /*lint --e{715}*/
404  	  SCIP_CUTSELDATA* cutseldata;
405  	
406  	  cutseldata = SCIPcutselGetData(cutsel);
407  	  assert(cutseldata != NULL);
408  	  assert(cutseldata->randnumgen != NULL);
409  	
410  	  SCIPfreeRandom(scip, &cutseldata->randnumgen);
411  	
412  	  return SCIP_OKAY;
413  	}
414  	
415  	/** cut selection method of cut selector */
416  	static
417  	SCIP_DECL_CUTSELSELECT(cutselSelectDynamic) { /*lint --e{715}*/
418  	   SCIP_CUTSELDATA *cutseldata;
419  	
420  	   assert(cutsel != NULL);
421  	   assert(result != NULL);
422  	
423  	   *result = SCIP_SUCCESS;
424  	
425  	   cutseldata = SCIPcutselGetData(cutsel);
426  	   assert(cutseldata != NULL);
427  	   if (cutseldata->maxdepth != -1 && cutseldata->maxdepth < SCIPgetDepth(scip))
428  	   {
429  	      *result = SCIP_DIDNOTFIND;
430  	      return SCIP_OKAY;
431  	   }
432  	
433  	   SCIP_CALL( SCIPselectCutsDynamic( scip, cuts, forcedcuts, cutseldata->randnumgen, cutseldata->filtermode,
434  	                                      cutseldata->mingain, 1-cutseldata->minortho, cutseldata->dircutoffdistweight, cutseldata->efficacyweight,
435  	                                      cutseldata->objparalweight, cutseldata->intsupportweight, ncuts, nforcedcuts,
436  	                                      maxnselectedcuts, nselectedcuts) );
437  	
438  	   return SCIP_OKAY;
439  	}
440  	
441  	
442  	/*
443  	 * cut selector specific interface methods
444  	 */
445  	
446  	/** creates the dynamic cut selector and includes it in SCIP */
447  	SCIP_RETCODE SCIPincludeCutselDynamic(
448  	   SCIP*                 scip                /**< SCIP data structure */
449  	   )
450  	{
451  	   SCIP_CUTSELDATA* cutseldata;
452  	   SCIP_CUTSEL* cutsel;
453  	
454  	   /* create dynamic cut selector data */
455  	   SCIP_CALL( SCIPallocBlockMemory(scip, &cutseldata) );
456  	   BMSclearMemory(cutseldata);
457  	
458  	   SCIP_CALL( SCIPincludeCutselBasic(scip, &cutsel, CUTSEL_NAME, CUTSEL_DESC, CUTSEL_PRIORITY, cutselSelectDynamic,
459  	                                    cutseldata) );
460  	
461  	   assert(cutsel != NULL);
462  	
463  	   /* set non fundamental callbacks via setter functions */
464  	   SCIP_CALL( SCIPsetCutselCopy(scip, cutsel, cutselCopyDynamic) );
465  	
466  	   SCIP_CALL( SCIPsetCutselFree(scip, cutsel, cutselFreeDynamic) );
467  	   SCIP_CALL( SCIPsetCutselInit(scip, cutsel, cutselInitDynamic) );
468  	   SCIP_CALL( SCIPsetCutselExit(scip, cutsel, cutselExitDynamic) );
469  	
470  	   /* add dynamic cut selector parameters */
471  	   SCIP_CALL( SCIPaddRealParam(scip,
472  	               "cutselection/" CUTSEL_NAME "/efficacyweight",
473  	               "weight of efficacy in cut score calculation",
474  	               &cutseldata->efficacyweight, FALSE,
475  	               DEFAULT_EFFICACYWEIGHT, 0.0, SCIP_INVALID / 10.0, NULL, NULL) );
476  	
477  	   SCIP_CALL( SCIPaddRealParam(scip,
478  	               "cutselection/" CUTSEL_NAME "/dircutoffdistweight",
479  	               "weight of directed cutoff distance in cut score calculation",
480  	               &cutseldata->dircutoffdistweight, FALSE,
481  	               DEFAULT_DIRCUTOFFDISTWEIGHT, 0.0, SCIP_INVALID / 10.0, NULL, NULL) );
482  	
483  	   SCIP_CALL( SCIPaddRealParam(scip,
484  	               "cutselection/" CUTSEL_NAME "/objparalweight",
485  	               "weight of objective parallelism in cut score calculation",
486  	               &cutseldata->objparalweight, FALSE,
487  	               DEFAULT_OBJPARALWEIGHT, 0.0, SCIP_INVALID / 10.0, NULL, NULL) );
488  	
489  	   SCIP_CALL( SCIPaddRealParam(scip,
490  	               "cutselection/" CUTSEL_NAME "/intsupportweight",
491  	               "weight of integral support in cut score calculation",
492  	               &cutseldata->intsupportweight, FALSE,
493  	               DEFAULT_INTSUPPORTWEIGHT, 0.0, SCIP_INVALID / 10.0, NULL, NULL) );
494  	
495  	   SCIP_CALL( SCIPaddRealParam(scip,
496  	               "cutselection/" CUTSEL_NAME "/mingain",
497  	               "minimal efficacy gain for a cut to enter the LP",
498  	               &cutseldata->mingain, FALSE,
499  	               DEFAULT_MINGAIN, 0.0, 1.0, NULL, NULL) );
500  	
501  	   SCIP_CALL( SCIPaddCharParam(scip,
502  	               "cutselection/" CUTSEL_NAME "/filtermode",
503  	               "filtering strategy during cut selection",
504  	               &cutseldata->filtermode, FALSE,
505  	               DEFAULT_FILTERMODE, "df", NULL, NULL) );
506  	
507  	   SCIP_CALL( SCIPaddRealParam(scip,
508  	               "cutselection/" CUTSEL_NAME "/minortho",
509  	               "minimal orthogonality for a cut to enter the LP",
510  	               &cutseldata->minortho, FALSE,
511  	               DEFAULT_MINORTHO, 0.0, 1.0, NULL, NULL) );
512  	
513  	   SCIP_CALL( SCIPaddIntParam(scip,
514  	               "cutselection/" CUTSEL_NAME "/maxdepth",
515  	               "maximum depth at which this cutselector is employed",
516  	               &cutseldata->maxdepth, FALSE,
517  	               DEFAULT_MAXDEPTH, -1, SCIP_MAXTREEDEPTH, NULL, NULL) );
518  	
519  	   return SCIP_OKAY;
520  	}
521  	
522  	
523  	/** perform a cut selection algorithm for the given array of cuts
524  	 *
525  	 *  This is the selection method of the dynamic cut selector which implements
526  	 *  the dynamic orthognality filtering based on the ratio of efficacies.
527  	 *  The input cuts array gets resorted s.t the selected cuts come first and the remaining
528  	 *  ones are the end.
529  	 */
530  	SCIP_RETCODE SCIPselectCutsDynamic(
531  	   SCIP*                 scip,               /**< SCIP data structure */
532  	   SCIP_ROW**            cuts,               /**< array with cuts to perform selection algorithm */
533  	   SCIP_ROW**            forcedcuts,         /**< array with forced cuts */
534  	   SCIP_RANDNUMGEN*      randnumgen,         /**< random number generator for tie-breaking, or NULL */
535  	   char                  filtermode,         /**< filtering strategy during cut selection (
536  	                                             *  'd'ynamic- and 'f'ull dynamic parallelism) */
537  	   SCIP_Real             mingain,            /**< minimum efficacy gain in percentage to filter cuts */
538  	   SCIP_Real             maxparall,          /**< maximal parallelism for all cuts that are not good */
539  	   SCIP_Real             dircutoffdistweight,/**< weight of directed cutoff distance in cut score calculation */
540  	   SCIP_Real             efficacyweight,     /**< weight of efficacy in cut score calculation */
541  	   SCIP_Real             objparalweight,     /**< weight of objective parallelism in cut score calculation */
542  	   SCIP_Real             intsupportweight,   /**< weight of integral support in cut score calculation */
543  	   int                   ncuts,              /**< number of cuts in cuts array */
544  	   int                   nforcedcuts,        /**< number of forced cuts */
545  	   int                   maxselectedcuts,    /**< maximal number of cuts from cuts array to select */
546  	   int*                  nselectedcuts      /**< pointer to return number of selected cuts from cuts array */
547  	   )
548  	{
549  	   SCIP_ROW* selectedcut;
550  	   SCIP_Real* scores;
551  	   SCIP_Real* forcedscores;
552  	   SCIP_Real* scoresptr;
553  	   int ngoodforcedcuts;
554  	   int i;
555  	
556  	   assert(cuts != NULL && ncuts > 0);
557  	   assert(forcedcuts != NULL || nforcedcuts == 0);
558  	   assert(nselectedcuts != NULL);
559  	
560  	   *nselectedcuts = 0;
561  	   ngoodforcedcuts = 0;
562  	
563  	   SCIP_CALL( SCIPallocBufferArray(scip, &scores, ncuts) );
564  	
565  	   /* compute scores of cuts and max score of cuts and forced cuts (used to define goodscore) */
566  	   scoring(scip, cuts, randnumgen, dircutoffdistweight, efficacyweight, objparalweight, intsupportweight, &ncuts,
567  	           scores);
568  	   scoresptr = scores;
569  	
570  	   SCIPdebugMsg(scip, "nforcedcuts = %i.\n", nforcedcuts);
571  	
572  	   /* perform cut selection algorithm for the cuts */
573  	
574  	   /* forced cuts are going to be selected so use them to filter cuts */
575  	   for( i = 0; i < nforcedcuts && ncuts > 0; ++i )
576  	      ncuts = filterWithDynamicParallelism(scip, forcedcuts[i], cuts, scores, mingain, maxparall, ncuts);
577  	
578  	   /* if all cuts are already filtered, we can stop */
579  	   if( ncuts <= 0 )
580  	      goto TERMINATE;
581  	
582  	   /* if the maximal number of cuts was selected, we can stop here */
583  	   if( *nselectedcuts == maxselectedcuts )
584  	      goto TERMINATE;
585  	
586  	   if( filtermode == 'f' && nforcedcuts > 0 )
587  	   {
588  	      SCIP_CALL( SCIPallocBufferArray(scip, &forcedscores, nforcedcuts) );
589  	      ngoodforcedcuts = nforcedcuts;
590  	      scoring(scip, forcedcuts, randnumgen, dircutoffdistweight, efficacyweight, objparalweight, intsupportweight,
591  	              &ngoodforcedcuts, forcedscores);
592  	
593  	      if( ngoodforcedcuts != 0 )
594  	      {
595  	        selectBestCut(forcedcuts, forcedscores, ngoodforcedcuts);
596  	        SCIPfreeBufferArray(scip, &forcedscores);
597  	        SCIPdebugMsg(scip, "best forced cut: %s.\n", SCIProwGetName(forcedcuts[0]));
598  	
599  	        for( i = 0; i < ncuts; i++ )
600  	        {
601  	           SCIP_CALL( computeProjectionScore(scip, forcedcuts[0], cuts[i], &scores[i]) );
602  	           SCIPdebugMsg(scip, "scores[%i] = %g\n", i, scores[i]);
603  	        }
604  	      }
605  	   }
606  	
607  	   if( ngoodforcedcuts == 0 )
608  	   {
609  	      assert(filtermode == 'd' || ngoodforcedcuts == 0);
610  	      selectBestCut(cuts, scores, ncuts);
611  	
612  	      selectedcut = cuts[0];
613  	      SCIPdebugMsg(scip, "selectedcut = %s.\n", SCIProwGetName(selectedcut));
614  	
615  	      ++(*nselectedcuts);
616  	
617  	      /* if the maximal number of cuts was selected, we can stop here */
618  	      if( *nselectedcuts == maxselectedcuts )
619  	         goto TERMINATE;
620  	
621  	      /* move the pointers to the next position and filter the remaining cuts to enforce the dynamic parallelism constraint */
622  	      ++cuts;
623  	      ++scores;
624  	      --ncuts;
625  	
626  	      ncuts = filterWithDynamicParallelism(scip, selectedcut, cuts, scores, mingain, maxparall, ncuts);
627  	
628  	      if( filtermode == 'f' )
629  	      {
630  	         for( i = 0; i < ncuts; i++ )
631  	         {
632  	            SCIP_CALL( computeProjectionScore(scip, selectedcut, cuts[i], &scores[i]) );
633  	         }
634  	      }
635  	   }
636  	
637  	   SCIPdebugMsg(scip, "ncuts after forced cut filter = %i.\n", ncuts);
638  	
639  	   /* now greedily select the remaining cuts */
640  	   while( ncuts > 0 )
641  	   {
642  	      selectBestCut(cuts, scores, ncuts);
643  	      selectedcut = cuts[0];
644  	      SCIPdebugMsg(scip, "selectedcut = %s.\n", SCIProwGetName(selectedcut));
645  	
646  	      ++(*nselectedcuts);
647  	
648  	      /* if the maximal number of cuts was selected, we can stop here */
649  	      if( *nselectedcuts == maxselectedcuts )
650  	         goto TERMINATE;
651  	
652  	      /* move the pointers to the next position and filter the remaining cuts to enforce the dynamic parallelism constraint */
653  	      ++cuts;
654  	      ++scores;
655  	      --ncuts;
656  	
657  	      ncuts = filterWithDynamicParallelism(scip, selectedcut, cuts, scores, mingain, maxparall, ncuts);
658  	
659  	      if( filtermode == 'f' )
660  	      {
661  	         for( i = 0; i < ncuts; i++ )
662  	         {
663  	            SCIP_CALL( computeProjectionScore(scip, selectedcut, cuts[i], &scores[i]) );
664  	            SCIPdebugMsg(scip, "nonforcedscores[%i] = %g\n", i, scores[i]);
665  	         }
666  	      }
667  	   }
668  	
669  	   TERMINATE:
670  	   SCIPfreeBufferArray(scip, &scoresptr);
671  	   return SCIP_OKAY;
672  	}
673