Scippy

SCIP

Solving Constraint Integer Programs

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