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"
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 */
65struct 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 */
86static
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. **/
222static
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 */
256static
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 */
289static
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) */
365static
366SCIP_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] */
380static
381SCIP_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) */
396static
397SCIP_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) */
410static
411SCIP_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 */
425static
426SCIP_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,
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,
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}
#define DEFAULT_MINGAIN
#define DEFAULT_EFFICACYWEIGHT
#define DEFAULT_OBJPARALWEIGHT
#define RANDSEED
static int filterWithDynamicParallelism(SCIP *scip, SCIP_ROW *bestcut, SCIP_ROW **cuts, SCIP_Real *scores, SCIP_Real mingain, SCIP_Real maxparall, int ncuts)
static SCIP_DECL_CUTSELSELECT(cutselSelectDynamic)
#define DEFAULT_MAXDEPTH
static SCIP_DECL_CUTSELFREE(cutselFreeDynamic)
static void selectBestCut(SCIP_ROW **cuts, SCIP_Real *scores, int ncuts)
#define CUTSEL_DESC
static SCIP_DECL_CUTSELCOPY(cutselCopyDynamic)
#define DEFAULT_FILTERMODE
#define CUTSEL_PRIORITY
static SCIP_RETCODE computeProjectionScore(SCIP *scip, SCIP_ROW *bestcut, SCIP_ROW *cut, SCIP_Real *score)
#define DEFAULT_MINORTHO
#define DEFAULT_DIRCUTOFFDISTWEIGHT
static SCIP_DECL_CUTSELINIT(cutselInitDynamic)
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 CUTSEL_NAME
static SCIP_DECL_CUTSELEXIT(cutselExitDynamic)
#define DEFAULT_INTSUPPORTWEIGHT
dynamic cut selector
#define NULL
Definition: def.h:267
#define SCIP_MAXTREEDEPTH
Definition: def.h:316
#define SCIP_INVALID
Definition: def.h:193
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define SCIP_CALL(x)
Definition: def.h:374
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)
SCIP_RETCODE SCIPincludeCutselDynamic(SCIP *scip)
#define SCIPdebugMsg
Definition: scip_message.h:78
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
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
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
void SCIPswapPointers(void **pointer1, void **pointer2)
Definition: misc.c:10396
void SCIPswapReals(SCIP_Real *value1, SCIP_Real *value2)
Definition: misc.c:10383
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:94
SCIP_Real SCIPgetCutLPSolCutoffDistance(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:72
SCIP_RETCODE SCIPsetCutselInit(SCIP *scip, SCIP_CUTSEL *cutsel, SCIP_DECL_CUTSELINIT((*cutselinit)))
Definition: scip_cutsel.c:157
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
SCIP_RETCODE SCIPsetCutselCopy(SCIP *scip, SCIP_CUTSEL *cutsel, SCIP_DECL_CUTSELCOPY((*cutselcopy)))
Definition: scip_cutsel.c:125
SCIP_CUTSELDATA * SCIPcutselGetData(SCIP_CUTSEL *cutsel)
Definition: cutsel.c:419
SCIP_RETCODE SCIPsetCutselFree(SCIP *scip, SCIP_CUTSEL *cutsel, SCIP_DECL_CUTSELFREE((*cutselfree)))
Definition: scip_cutsel.c:141
void SCIPcutselSetData(SCIP_CUTSEL *cutsel, SCIP_CUTSELDATA *cutseldata)
Definition: cutsel.c:429
const char * SCIPcutselGetName(SCIP_CUTSEL *cutsel)
Definition: cutsel.c:159
SCIP_RETCODE SCIPsetCutselExit(SCIP *scip, SCIP_CUTSEL *cutsel, SCIP_DECL_CUTSELEXIT((*cutselexit)))
Definition: scip_cutsel.c:173
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_Real SCIProwGetParallelism(SCIP_ROW *row1, SCIP_ROW *row2, char orthofunc)
Definition: lp.c:7724
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:17213
SCIP_Bool SCIProwIsInGlobalCutpool(SCIP_ROW *row)
Definition: lp.c:17491
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition: lp.c:17401
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:17351
SCIP_Real SCIPgetRowObjParallelism(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:2190
int SCIPgetRowNumIntCols(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1886
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2169
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10130
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
#define BMSclearMemory(ptr)
Definition: memory.h:129
public methods for cuts and aggregation rows
public methods for cut selector plugins
public methods for the LP relaxation, rows and columns
public methods for random numbers
struct SCIP_CutselData SCIP_CUTSELDATA
Definition: type_cutsel.h:53
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_SUCCESS
Definition: type_result.h:58
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63