SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
cutsel_ensemble.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_ensemble.c
26 * @ingroup DEFPLUGINS_CUTSEL
27 * @brief ensemble cut selector
28 * @author Mark Turner
29 *
30 * @todo separator hard limit on density is inappropriate for MINLP. Need to relax hard limit in case of all cuts dense
31 * @todo penalising via parallelism is overly costly if many cuts. Hash cuts before and find appropriate groups?
32 */
33
34/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35
36#include <assert.h>
37
38#include "scip/scip_cutsel.h"
39#include "scip/scip_cut.h"
40#include "scip/scip_lp.h"
43
44
45#define CUTSEL_NAME "ensemble"
46#define CUTSEL_DESC "weighted sum of many terms with optional filtering and penalties"
47#define CUTSEL_PRIORITY 7000
48
49#define RANDSEED 0x5EED
50
51#define DEFAULT_MINSCORE 0.0 /**< minimum score s.t. a cut can be selected */
52#define DEFAULT_EFFICACYWEIGHT 0.75 /**< weight of normed-efficacy in score calculation */
53#define DEFAULT_DIRCUTOFFDISTWEIGHT 0.0 /**< weight of normed-directed cutoff distance in score calculation */
54#define DEFAULT_OBJPARALWEIGHT 0.25 /**< weight of objective parallelism in score calculation */
55#define DEFAULT_INTSUPPORTWEIGHT 0.45 /**< weight of integral support in cut score calculation */
56#define DEFAULT_EXPIMPROVWEIGHT 0.1 /**< weight of normed-expected improvement in cut score calculation */
57#define DEFAULT_PSCOSTWEIGHT 0.75 /**< weight of normalised pseudo-costs in cut score calculation */
58#define DEFAULT_NLOCKSWEIGHT 0.25 /**< weight of normalised number of locks in cut score calculation */
59#define DEFAULT_MAXSPARSITYBONUS 0.5 /**< score given to a cut with complete sparsity */
60#define DEFAULT_SPARSITYENDBONUS 0.2 /**< the density at which a cut no longer receives additional score */
61#define DEFAULT_GOODNUMERICBONUS 0.0 /**< bonus provided for good numerics */
62#define DEFAULT_MAXCOEFRATIOBONUS 10000 /**< maximum coefficient ratio of cut for which numeric bonus is given */
63#define DEFAULT_PENALISELOCKS TRUE /**< whether having less locks should be rewarded instead of more */
64#define DEFAULT_PENALISEOBJPARAL TRUE /**< whether objective parallelism should be penalised not rewarded */
65#define DEFAULT_FILTERPARALCUTS FALSE /**< should cuts be filtered so no two parallel cuts are added */
66#define DEFAULT_MAXPARAL 0.95 /**< threshold for when two cuts are considered parallel to each other */
67#define DEFAULT_PENALISEPARALCUTS TRUE /**< should two parallel cuts be penalised instead of outright filtered */
68#define DEFAULT_PARALPENALTY 0.25 /**< penalty for weaker of two parallel cuts if penalising parallel cuts */
69#define DEFAULT_FILTERDENSECUTS TRUE /**< should cuts over a given density threshold be filtered */
70#define DEFAULT_MAXCUTDENSITY 0.425 /**< max allowed cut density if filtering dense cuts */
71#define DEFAULT_MAXNONZEROROOTROUND 4.5 /**< max nonzeros per round (root). Gets multiplied by num LP cols */
72#define DEFAULT_MAXNONZEROTREEROUND 9.5 /**< max nonzeros per round (tree). Gets multiplied by num LP cols */
73#define DEFAULT_MAXCUTS 200 /**< maximum number of cuts that can be considered by this cut selector */
74#define DEFAULT_MAXNUMVARS 50000 /**< maximum number of variables that a problem can have while calling this cut selector */
75
76/*
77 * Data structures
78 */
79
80/** cut selector data */
81struct SCIP_CutselData
82{
83 SCIP_RANDNUMGEN* randnumgen; /**< random generator for tie-breaking */
84 SCIP_Real minscore; /**< minimum score for a cut to be added to the LP */
85 SCIP_Real objparalweight; /**< weight of objective parallelism in cut score calculation */
86 SCIP_Real efficacyweight; /**< weight of normed-efficacy in cut score calculation */
87 SCIP_Real dircutoffdistweight;/**< weight of normed-directed cutoff distance in cut score calculation */
88 SCIP_Real expimprovweight; /**< weight of normed-expected improvement in cut score calculation */
89 SCIP_Real intsupportweight; /**< weight of integral support in cut score calculation */
90 SCIP_Real pscostweight; /**< weight of normalised pseudo-costs in cut score calculation */
91 SCIP_Real locksweight; /**< weight of normed-number of active locks in cut score calculation */
92 SCIP_Real maxsparsitybonus; /**< weight of maximum sparsity reward in cut score calculation */
93 SCIP_Real goodnumericsbonus; /**< weight of good numeric bonus in cut score calculation */
94 SCIP_Real endsparsitybonus; /**< max sparsity value for which a bonus is applied */
95 SCIP_Real maxparal; /**< threshold for when two cuts are considered parallel to each other */
96 SCIP_Real paralpenalty; /**< penalty for weaker of two parallel cuts if penalising parallel cuts */
97 SCIP_Real maxcutdensity; /**< max allowed cut density if filtering dense cuts */
98 SCIP_Real maxnonzerorootround;/**< max nonzeros per round (root). Gets multiplied by num LP cols */
99 SCIP_Real maxnonzerotreeround;/**< max nonzeros per round (tree). Gets multiplied by num LP cols */
100 SCIP_Bool filterparalcuts; /**< should cuts be filtered so no two parallel cuts are added */
101 SCIP_Bool penaliseparalcuts; /**< should two parallel cuts be penalised instead of outright filtered */
102 SCIP_Bool filterdensecuts; /**< should cuts over a given density threshold be filtered */
103 SCIP_Bool penaliselocks; /**< whether the number of locks should be penalised instead of rewarded */
104 SCIP_Bool penaliseobjparal; /**< whether objective parallelism should be penalised */
105 int maxcoefratiobonus; /**< maximum coefficient ratio for which numeric bonus is applied */
106 int maxcuts; /**< maximum number of cuts that can be considered by this cut selector */
107 int maxnumvars; /**< maximum number of variables that a problem can have while calling this cut selector */
108};
109
110
111/*
112 * Local methods
113 */
114
115/** returns the maximum score of cuts; if scores is not NULL, then stores the individual score of each cut in scores */
116static
118 SCIP* scip, /**< SCIP data structure */
119 SCIP_ROW** cuts, /**< array with cuts to score */
120 SCIP_CUTSELDATA* cutseldata, /**< cut selector data */
121 SCIP_Real* scores, /**< array to store the score of cuts or NULL */
122 SCIP_Bool root, /**< whether we are at the root node or not */
123 int ncuts /**< number of cuts in cuts array */
124)
125{
126 SCIP_Real* effs;
127 SCIP_Real* dcds;
128 SCIP_Real* exps;
129 SCIP_Real* cutdensities;
130 SCIP_Real* cutlocks;
131 SCIP_Real* pscosts;
132 SCIP_SOL* sol;
133 SCIP_Real maxdcd = 0.0;
134 SCIP_Real maxeff = 0.0;
135 SCIP_Real maxexp = 0.0;
136 SCIP_Real maxpscost = 0.0;
137 SCIP_Real maxlocks = 0.0;
138 SCIP_Real ncols;
139
140 /* Get the solution that we use for directed cutoff distance calculations. Get the number of columns too */
142 ncols = SCIPgetNLPCols(scip);
143
144 /* Initialise all array information that we're going to use for scoring */
151
152
153 /* Populate the number of cut locks, the pseudo-cost scores, and the cut densities */
154 for (int i = 0; i < ncuts; ++i )
155 {
156 SCIP_COL** cols;
157 SCIP_Real* cutvals;
158 SCIP_Real sqrcutnorm;
159 SCIP_Real ncutcols;
160 SCIP_Real cutalpha;
161
162 cols = SCIProwGetCols(cuts[i]);
163 cutvals = SCIProwGetVals(cuts[i]);
164 sqrcutnorm = MAX(SCIPsumepsilon(scip), SQR(SCIProwGetNorm(cuts[i]))); /*lint !e666*/
166 ncutcols = SCIProwGetNNonz(cuts[i]);
167 cutdensities[i] = ncutcols / ncols;
168 cutlocks[i] = 0;
169 pscosts[i] = 0;
170
171
172 for ( int j = 0; j < (int) ncutcols; ++j )
173 {
175 SCIP_Real colval;
176 SCIP_Real l1dist;
177
178 colval = SCIPcolGetPrimsol(cols[j]);
179 colvar = SCIPcolGetVar(cols[j]);
180 /* Get the number of active locks feature in the cut */
181 if( ! SCIPisInfinity(scip, SCIProwGetRhs(cuts[i])) && cutvals[j] > 0.0 )
183 if( ! SCIPisInfinity(scip, -SCIProwGetLhs(cuts[i])) && cutvals[j] < 0.0 )
185 if( ! SCIPisInfinity(scip, SCIProwGetRhs(cuts[i])) && cutvals[j] < 0.0 )
187 if( ! SCIPisInfinity(scip, -SCIProwGetLhs(cuts[i])) && cutvals[j] > 0.0 )
189
190 /* Get the L1 distance from the projection onto the cut and the LP solution in the variable direction */
191 l1dist = ABS(colval - (cutalpha * cutvals[j]));
193 }
194 cutlocks[i] = cutlocks[i] / ncutcols; /*lint !e414*/
195
196 if( cutlocks[i] > maxlocks )
198
199 if( pscosts[i] > maxpscost )
201 }
202
203 /* account for the case where maxlocks or maxpscost is 0 */
204 maxpscost = MAX(maxpscost, SCIPepsilon(scip)); /*lint !e666*/
205 maxlocks = MAX(maxlocks, 1);
206
207 for ( int i = 0; i < ncuts; i++ )
208 {
209 cutlocks[i] = cutlocks[i] / maxlocks; /*lint !e414*/
210 /* if locks are penalized, we complement the corresponding score */
211 if( cutseldata->penaliselocks )
212 cutlocks[i] = 1 - cutlocks[i];
213 pscosts[i] = pscosts[i] / maxpscost; /*lint !e414*/
214 }
215
216
217 /* Get the arrays / maximums of directed cutoff distance, efficacy, and expected improvement values. */
218 if ( sol != NULL && root )
219 {
220 for ( int i = 0; i < ncuts; i++ )
221 {
223 maxdcd = MAX(maxdcd, dcds[i]);
224 }
225 }
226
227 for ( int i = 0; i < ncuts; ++i )
228 {
229 effs[i] = SCIPgetCutEfficacy(scip, NULL, cuts[i]);
230 exps[i] = effs[i] * SCIPgetRowObjParallelism(scip, cuts[i]);
231 maxeff = MAX(maxeff, effs[i]);
232 maxexp = MAX(maxexp, exps[i]);
233 }
234
235 /* Now score the cuts */
236 for ( int i = 0; i < ncuts; ++i )
237 {
238 SCIP_Real score;
239 SCIP_Real scaleddcd;
240 SCIP_Real scaledeff;
241 SCIP_Real scaledexp;
242 SCIP_Real objparallelism;
243 SCIP_Real intsupport;
244 SCIP_Real density;
245 SCIP_Real dynamism;
246 SCIP_Real mincutval;
247 SCIP_Real maxcutval;
248 SCIP_Real pscost;
249 SCIP_Real cutlock;
250
251 /* Get the integer support */
253 intsupport *= cutseldata->intsupportweight;
254
255 /* Get the objective parallelism and orthogonality */
256 if( ! cutseldata->penaliseobjparal )
257 objparallelism = cutseldata->objparalweight * SCIPgetRowObjParallelism(scip, cuts[i]);
258 else
259 objparallelism = cutseldata->objparalweight * (1 - SCIPgetRowObjParallelism(scip, cuts[i]));
260
261 /* Get the density score */
262 density = (cutseldata->maxsparsitybonus / cutseldata->endsparsitybonus) * -1 * cutdensities[i];
263 density += cutseldata->maxsparsitybonus;
264 density = MAX(density, 0.0);
265
266 /* Get the normalised pseudo-cost and number of locks score */
267 if( root )
268 pscost = 0.0;
269 else
270 pscost = cutseldata->pscostweight * pscosts[i];
271 cutlock = cutseldata->locksweight * cutlocks[i];
272
273 /* Get the dynamism (good numerics) score */
276 mincutval = mincutval > 0.0 ? mincutval : 1.0;
277 dynamism = cutseldata->maxcoefratiobonus >= maxcutval / mincutval ? cutseldata->goodnumericsbonus : 0.0;
278
279 /* Get the dcd / eff / exp score */
280 if ( sol != NULL && root )
281 {
282 if ( SCIPisSumLE(scip, dcds[i], 0.0))
283 scaleddcd = 0.0;
284 else
285 scaleddcd = cutseldata->dircutoffdistweight * SQR(LOG1P(dcds[i]) / LOG1P(maxdcd)); /*lint !e666*/
286 }
287 else
288 {
289 scaleddcd = 0.0;
290 }
291
292 if ( SCIPisSumLE(scip, exps[i], 0.0))
293 scaledexp = 0.0;
294 else
295 scaledexp = cutseldata->expimprovweight * SQR(LOG1P(exps[i]) / LOG1P(maxexp)); /*lint !e666*/
296
297 if ( SCIPisSumLE(scip, effs[i], 0.0))
298 {
299 scaledeff = 0.0;
300 }
301 else
302 {
303 if ( sol != NULL && root )
304 scaledeff = cutseldata->efficacyweight * SQR(LOG1P(effs[i]) / LOG1P(maxeff)); /*lint !e666*/
305 else
306 scaledeff = (cutseldata->efficacyweight + cutseldata->dircutoffdistweight) * SQR(LOG1P(effs[i]) / LOG1P(maxeff)); /*lint !e666*/
307 }
308
309 /* Combine all scores and introduce some minor randomness */
311
312 score += SCIPrandomGetReal(cutseldata->randnumgen, 0.0, 1e-6);
313
314 scores[i] = score;
315 }
316
323
324 return SCIP_OKAY;
325
326}
327
328
329/** move the cut with the highest score to the first position in the array; there must be at least one cut */
330static
332 SCIP_ROW** cuts, /**< array with cuts to perform selection algorithm */
333 SCIP_Real* scores, /**< array with scores of cuts to perform selection algorithm */
334 int ncuts /**< number of cuts in given array */
335)
336{
337 int bestpos;
338 SCIP_Real bestscore;
339
340 assert(ncuts > 0);
341 assert(cuts != NULL);
342 assert(scores != NULL);
343
344 bestscore = scores[0];
345 bestpos = 0;
346
347 for( int i = 1; i < ncuts; ++i )
348 {
349 if( scores[i] > bestscore )
350 {
351 bestpos = i;
352 bestscore = scores[i];
353 }
354 }
355
356 SCIPswapPointers((void**) &cuts[bestpos], (void**) &cuts[0]);
357 SCIPswapReals(&scores[bestpos], &scores[0]);
358}
359
360/** filters the given array of cuts to enforce a maximum parallelism constraint
361 * w.r.t the given cut; moves filtered cuts to the end of the array and returns number of selected cuts */
362static
364 SCIP_ROW* cut, /**< cut to filter orthogonality with */
365 SCIP_ROW** cuts, /**< array with cuts to perform selection algorithm */
366 SCIP_Real* scores, /**< array with scores of cuts to perform selection algorithm */
367 int ncuts, /**< number of cuts in given array */
368 SCIP_Real maxparallel /**< maximal parallelism for all cuts that are not good */
369)
370{
371
372 assert( cut != NULL );
373 assert( ncuts == 0 || cuts != NULL );
374 assert( ncuts == 0 || scores != NULL );
375
376 for( int i = ncuts - 1; i >= 0; --i )
377 {
378 SCIP_Real thisparallel;
379
381
383 {
384 --ncuts;
385 SCIPswapPointers((void**) &cuts[i], (void**) &cuts[ncuts]);
386 SCIPswapReals(&scores[i], &scores[ncuts]);
387 }
388 }
389
390 return ncuts;
391}
392
393/** penalises any cut too parallel to cut by reducing the parallel cut's score. */
394static
396 SCIP* scip, /**< SCIP data structure */
397 SCIP_ROW* cut, /**< cut to filter orthogonality with */
398 SCIP_ROW** cuts, /**< array with cuts to perform selection algorithm */
399 SCIP_Real* scores, /**< array with scores of cuts to perform selection algorithm */
400 int ncuts, /**< number of cuts in given array */
401 SCIP_Real maxparallel, /**< maximal parallelism for all cuts that are not good */
402 SCIP_Real paralpenalty /**< penalty for weaker of two parallel cuts if penalising parallel cuts */
403)
404{
405
406 assert( cut != NULL );
407 assert( ncuts == 0 || cuts != NULL );
408 assert( ncuts == 0 || scores != NULL );
409
410 for( int i = ncuts - 1; i >= 0; --i )
411 {
412 SCIP_Real thisparallel;
413
415
416 /* Filter cuts that are absolutely parallel still. Otherwise penalise if closely parallel */
417 if( thisparallel > 1 - SCIPsumepsilon(scip) )
418 {
419 --ncuts;
420 SCIPswapPointers((void**) &cuts[i], (void**) &cuts[ncuts]);
421 SCIPswapReals(&scores[i], &scores[ncuts]);
422 }
423 else if( thisparallel > maxparallel )
424 {
425 scores[i] -= paralpenalty;
426 }
427 }
428
429 return ncuts;
430}
431
432/** filters the given array of cuts to enforce a maximum density constraint,
433 * Moves filtered cuts to the end of the array and returns number of selected cuts */
434static
436 SCIP* scip, /**< SCIP data structure */
437 SCIP_ROW** cuts, /**< array with cuts to perform selection algorithm */
438 SCIP_Real maxdensity, /**< maximum density s.t. a cut is not filtered */
439 int ncuts /**< number of cuts in given array */
440)
441{
442 SCIP_Real ncols;
443
444 assert( ncuts == 0 || cuts != NULL );
445
446 ncols = SCIPgetNLPCols(scip);
447
448 for( int i = ncuts - 1; i >= 0; --i )
449 {
450 SCIP_Real nvals;
451
452 nvals = SCIProwGetNNonz(cuts[i]);
453
454 if( maxdensity < nvals / ncols )
455 {
456 --ncuts;
457 SCIPswapPointers((void**) &cuts[i], (void**) &cuts[ncuts]);
458 }
459 }
460
461 return ncuts;
462}
463
464
465/*
466 * Callback methods of cut selector
467 */
468
469
470/** copy method for cut selector plugin (called when SCIP copies plugins) */
471static
473{ /*lint --e{715}*/
474 assert(scip != NULL);
475 assert(cutsel != NULL);
477
478 /* call inclusion method of cut selector */
480
481 return SCIP_OKAY;
482}
483
484/** destructor of cut selector to free user data (called when SCIP is exiting) */
485/**! [SnippetCutselFreeEnsemble] */
486static
488{ /*lint --e{715}*/
489 SCIP_CUTSELDATA* cutseldata;
490
491 cutseldata = SCIPcutselGetData(cutsel);
492
493 SCIPfreeBlockMemory(scip, &cutseldata);
494
496
497 return SCIP_OKAY;
498}
499/**! [SnippetCutselFreeEnsemble] */
500
501/** initialization method of cut selector (called after problem was transformed) */
502static
504{ /*lint --e{715}*/
505 SCIP_CUTSELDATA* cutseldata;
506
507 cutseldata = SCIPcutselGetData(cutsel);
508 assert(cutseldata != NULL);
509
510 SCIP_CALL( SCIPcreateRandom(scip, &(cutseldata)->randnumgen, RANDSEED, TRUE) );
511
512 return SCIP_OKAY;
513}
514
515/** deinitialization method of cut selector (called before transformed problem is freed) */
516static
518{ /*lint --e{715}*/
519 SCIP_CUTSELDATA* cutseldata;
520
521 cutseldata = SCIPcutselGetData(cutsel);
522 assert(cutseldata != NULL);
523 assert(cutseldata->randnumgen != NULL);
524
525 SCIPfreeRandom(scip, &cutseldata->randnumgen);
526
527 return SCIP_OKAY;
528}
529
530/** cut selection method of cut selector */
531static
533{ /*lint --e{715}*/
534 SCIP_CUTSELDATA* cutseldata;
535
536 assert(cutsel != NULL);
537 assert(result != NULL);
538
539 cutseldata = SCIPcutselGetData(cutsel);
540 assert(cutseldata != NULL);
541
542 if( ncuts > cutseldata->maxcuts || SCIPgetNVars(scip) > cutseldata->maxnumvars )
543 {
545 return SCIP_OKAY;
546 }
547
549
550 SCIP_CALL( SCIPselectCutsEnsemble(scip, cuts, forcedcuts, cutseldata, root, ncuts, nforcedcuts,
552
553 return SCIP_OKAY;
554}
555
556
557/*
558 * cut selector specific interface methods
559 */
560
561/** creates the ensemble cut selector and includes it in SCIP */
563 SCIP* scip /**< SCIP data structure */
564)
565{
566 SCIP_CUTSELDATA* cutseldata;
568
569 /* create ensemble cut selector data */
570 SCIP_CALL( SCIPallocBlockMemory(scip, &cutseldata) );
571 BMSclearMemory(cutseldata);
572
574 cutseldata) );
575
576 assert(cutsel != NULL);
577
578 /* set non fundamental callbacks via setter functions */
580
584
585 /* add ensemble cut selector parameters */
587 "cutselection/" CUTSEL_NAME "/efficacyweight",
588 "weight of normed-efficacy in cut score calculation",
589 &cutseldata->efficacyweight, FALSE, DEFAULT_EFFICACYWEIGHT, 0.0, SCIP_INVALID/10.0, NULL, NULL) );
590
592 "cutselection/" CUTSEL_NAME "/dircutoffdistweight",
593 "weight of normed-directed cutoff distance in cut score calculation",
594 &cutseldata->dircutoffdistweight, FALSE, DEFAULT_DIRCUTOFFDISTWEIGHT, 0.0, SCIP_INVALID/10.0, NULL, NULL) );
595
597 "cutselection/" CUTSEL_NAME "/objparalweight",
598 "weight of objective parallelism in cut score calculation",
599 &cutseldata->objparalweight, FALSE, DEFAULT_OBJPARALWEIGHT, 0.0, SCIP_INVALID/10.0, NULL, NULL) );
600
602 "cutselection/" CUTSEL_NAME "/intsupportweight",
603 "weight of integral support in cut score calculation",
604 &cutseldata->intsupportweight, FALSE, DEFAULT_INTSUPPORTWEIGHT, 0.0, SCIP_INVALID/10.0, NULL, NULL) );
605
607 "cutselection/" CUTSEL_NAME "/expimprovweight",
608 "weight of normed-expected obj improvement in cut score calculation",
609 &cutseldata->expimprovweight, FALSE, DEFAULT_EXPIMPROVWEIGHT, 0.0, SCIP_INVALID/10.0, NULL, NULL) );
610
612 "cutselection/" CUTSEL_NAME "/minscore",
613 "minimum score s.t. a cut can be added",
614 &cutseldata->minscore, FALSE, DEFAULT_MINSCORE, -SCIP_INVALID/10.0, SCIP_INVALID/10.0, NULL, NULL) );
615
617 "cutselection/" CUTSEL_NAME "/pscostweight",
618 "weight of normed-pseudo-costs in cut score calculation",
619 &cutseldata->pscostweight, FALSE, DEFAULT_PSCOSTWEIGHT, 0.0, SCIP_INVALID/10.0, NULL, NULL) );
620
622 "cutselection/" CUTSEL_NAME "/locksweight",
623 "weight of normed-num-locks in cut score calculation",
624 &cutseldata->locksweight, FALSE, DEFAULT_NLOCKSWEIGHT, 0.0, SCIP_INVALID/10.0, NULL, NULL) );
625
627 "cutselection/" CUTSEL_NAME "/maxsparsitybonus",
628 "weight of maximum sparsity reward in cut score calculation",
629 &cutseldata->maxsparsitybonus, FALSE, DEFAULT_MAXSPARSITYBONUS, 0.0, SCIP_INVALID/10.0, NULL, NULL) );
630
632 "cutselection/" CUTSEL_NAME "/goodnumericsbonus",
633 "weight of good numerics bonus (ratio of coefficients) in cut score calculation",
634 &cutseldata->goodnumericsbonus, FALSE, DEFAULT_GOODNUMERICBONUS, 0.0, SCIP_INVALID/10.0, NULL, NULL) );
635
637 "cutselection/" CUTSEL_NAME "/endsparsitybonus",
638 "max sparsity value for which a bonus is applied in cut score calculation",
639 &cutseldata->endsparsitybonus, FALSE, DEFAULT_SPARSITYENDBONUS, 0.0, SCIP_INVALID/10.0, NULL, NULL) );
640
642 "cutselection/" CUTSEL_NAME "/maxparal",
643 "threshold for when two cuts are considered parallel to each other",
644 &cutseldata->maxparal, FALSE, DEFAULT_MAXPARAL, 0.0, 1.0, NULL, NULL) );
645
647 "cutselection/" CUTSEL_NAME "/paralpenalty",
648 "penalty for weaker of two parallel cuts if penalising parallel cuts",
649 &cutseldata->paralpenalty, TRUE, DEFAULT_PARALPENALTY, 0.0, SCIP_INVALID/10.0, NULL, NULL) );
650
652 "cutselection/" CUTSEL_NAME "/maxcutdensity",
653 "max allowed cut density if filtering dense cuts",
654 &cutseldata->maxcutdensity, TRUE, DEFAULT_MAXCUTDENSITY, 0.0, 1.0, NULL, NULL) );
655
657 "cutselection/" CUTSEL_NAME "/maxnonzerorootround",
658 "max non-zeros per round applied cuts (root). multiple num LP cols.",
659 &cutseldata->maxnonzerorootround, FALSE, DEFAULT_MAXNONZEROROOTROUND, 0.0, SCIP_INVALID/10.0, NULL, NULL) );
660
662 "cutselection/" CUTSEL_NAME "/maxnonzerotreeround",
663 "max non-zeros per round applied cuts (tree). multiple num LP cols.",
664 &cutseldata->maxnonzerotreeround, FALSE, DEFAULT_MAXNONZEROTREEROUND, 0.0, SCIP_INVALID/10.0, NULL, NULL) );
665
667 "cutselection/" CUTSEL_NAME "/filterparalcuts",
668 "should cuts be filtered so no two parallel cuts are added",
669 &cutseldata->filterparalcuts, FALSE, DEFAULT_FILTERPARALCUTS, NULL, NULL) );
670
672 "cutselection/" CUTSEL_NAME "/penaliseparalcuts",
673 "should two parallel cuts be penalised instead of outright filtered",
674 &cutseldata->penaliseparalcuts, TRUE, DEFAULT_PENALISEPARALCUTS, NULL, NULL) );
675
677 "cutselection/" CUTSEL_NAME "/filterdensecuts",
678 "should cuts over a given density threshold be filtered",
679 &cutseldata->filterdensecuts, TRUE, DEFAULT_FILTERDENSECUTS, NULL, NULL) );
680
682 "cutselection/" CUTSEL_NAME "/penaliselocks",
683 "should the number of locks be penalised instead of rewarded",
684 &cutseldata->penaliselocks, TRUE, DEFAULT_PENALISELOCKS, NULL, NULL) );
685
687 "cutselection/" CUTSEL_NAME "/penaliseobjparal",
688 "should objective parallelism be penalised instead of rewarded",
689 &cutseldata->penaliseobjparal, TRUE, DEFAULT_PENALISEOBJPARAL, NULL, NULL) );
690
692 "cutselection/" CUTSEL_NAME "/maxcoefratiobonus",
693 "max coefficient ratio for which numeric bonus is applied.",
694 &cutseldata->maxcoefratiobonus, TRUE, DEFAULT_MAXCOEFRATIOBONUS, 1, 1000000, NULL, NULL) );
695
697 "cutselection/" CUTSEL_NAME "/maxcuts",
698 "max number of cuts such that cut selector is applied.",
699 &cutseldata->maxcuts, TRUE, DEFAULT_MAXCUTS, 1, 1000000, NULL, NULL) );
700
702 "cutselection/" CUTSEL_NAME "/maxnumvars",
703 "max number of variables such that cut selector is applied.",
704 &cutseldata->maxnumvars, TRUE, DEFAULT_MAXNUMVARS, 1, 1000000, NULL, NULL) );
705
706 return SCIP_OKAY;
707
708}
709
710/** perform a cut selection algorithm for the given array of cuts
711 *
712 * This is the selection method of the ensemble cut selector. It uses a weighted sum of normalised efficacy,
713 * normalised directed cutoff distance, normalised expected improvements, objective parallelism,
714 * integer support, sparsity, dynamism, pseudo-costs, and variable locks.
715 * In addition to the weighted sum score, there are optionally parallelism-based filtering and penalties,
716 * and density filtering.
717 * There are also additional budget constraints on the number of cuts that should be added.
718 * The input cuts array gets re-sorted such that the selected cuts come first and the remaining ones are the end.
719 */
721 SCIP* scip, /**< SCIP data structure */
722 SCIP_ROW** cuts, /**< array with cuts to perform selection algorithm */
723 SCIP_ROW** forcedcuts, /**< array with forced cuts */
724 SCIP_CUTSELDATA* cutseldata, /**< cut selector data */
725 SCIP_Bool root, /**< whether we are at the root node or not */
726 int ncuts, /**< number of cuts in cuts array */
727 int nforcedcuts, /**< number of forced cuts */
728 int maxselectedcuts, /**< maximal number of cuts from cuts array to select */
729 int* nselectedcuts /**< pointer to return number of selected cuts from cuts array */
730)
731{
732 SCIP_Real* scores;
733 SCIP_Real* origscoresptr;
734 SCIP_Real nonzerobudget;
735 SCIP_Real budgettaken = 0.0;
736 SCIP_Real ncols;
737
738 assert(cuts != NULL && ncuts > 0);
739 assert(forcedcuts != NULL || nforcedcuts == 0);
741
742 *nselectedcuts = 0;
743 ncols = SCIPgetNLPCols(scip);
744
745 /* filter dense cuts */
746 if( cutseldata->filterdensecuts )
747 {
748 ncuts = filterWithDensity(scip, cuts, cutseldata->maxcutdensity, ncuts);
749 if( ncuts == 0 )
750 return SCIP_OKAY;
751 }
752
753 /* Initialise the score array */
754 SCIP_CALL( SCIPallocBufferArray(scip, &scores, ncuts) );
755 origscoresptr = scores;
756
757 /* compute scores of cuts */
758 SCIP_CALL( scoring(scip, cuts, cutseldata, scores, root, ncuts) );
759
760 /* perform cut selection algorithm for the cuts */
761
762 /* forced cuts are going to be selected so use them to filter cuts */
763 for( int i = 0; i < nforcedcuts && ncuts > 0; ++i )
764 {
765 if( cutseldata->filterparalcuts )
766 ncuts = filterWithParallelism(forcedcuts[i], cuts, scores, ncuts, cutseldata->maxparal);
767 else if( cutseldata->penaliseparalcuts )
768 ncuts = penaliseWithParallelism(scip, forcedcuts[i], cuts, scores, ncuts, cutseldata->maxparal, cutseldata->paralpenalty);
769 }
770
771 /* Get the budget depending on if we are the root or not */
772 nonzerobudget = root ? cutseldata->maxnonzerorootround : cutseldata->maxnonzerotreeround;
773
774 /* now greedily select the remaining cuts */
775 while( ncuts > 0 )
776 {
778
779 selectBestCut(cuts, scores, ncuts);
780 selectedcut = cuts[0];
781
782 /* if the best cut of the remaining cuts is considered bad, we discard it and all remaining cuts */
783 if( scores[0] < cutseldata->minscore )
784 break;
785
786 ++(*nselectedcuts);
787
788 /* if the maximal number of cuts was selected, we can stop here */
790 break;
791
792 /* increase the non-zero budget counter of added cuts */
793 budgettaken += SCIProwGetNNonz(cuts[0]) / ncols;
794
795 /* move the pointers to the next position and filter the remaining cuts to enforce the maximum parallelism constraint */
796 ++cuts;
797 ++scores;
798 --ncuts;
799
800 if( cutseldata->filterparalcuts && ncuts > 0)
801 ncuts = filterWithParallelism(selectedcut, cuts, scores, ncuts, cutseldata->maxparal);
802 else if( cutseldata->penaliseparalcuts && ncuts > 0 )
803 ncuts = penaliseWithParallelism(scip, selectedcut, cuts, scores, ncuts, cutseldata->maxparal, cutseldata->paralpenalty);
804
805 /* Filter out all remaining cuts that would go over the non-zero budget threshold */
807 ncuts = filterWithDensity(scip, cuts, nonzerobudget - budgettaken, ncuts);
808
809 }
810
812
813 return SCIP_OKAY;
814}
#define DEFAULT_MAXCUTS
#define DEFAULT_SPARSITYENDBONUS
#define DEFAULT_EFFICACYWEIGHT
#define DEFAULT_MAXNONZEROTREEROUND
#define DEFAULT_OBJPARALWEIGHT
#define RANDSEED
#define DEFAULT_FILTERDENSECUTS
#define DEFAULT_MAXSPARSITYBONUS
#define DEFAULT_MINSCORE
#define DEFAULT_PARALPENALTY
#define DEFAULT_PENALISEPARALCUTS
#define DEFAULT_GOODNUMERICBONUS
#define DEFAULT_PENALISELOCKS
#define DEFAULT_NLOCKSWEIGHT
static SCIP_RETCODE scoring(SCIP *scip, SCIP_ROW **cuts, SCIP_CUTSELDATA *cutseldata, SCIP_Real *scores, SCIP_Bool root, int ncuts)
static void selectBestCut(SCIP_ROW **cuts, SCIP_Real *scores, int ncuts)
static int filterWithDensity(SCIP *scip, SCIP_ROW **cuts, SCIP_Real maxdensity, int ncuts)
static int penaliseWithParallelism(SCIP *scip, SCIP_ROW *cut, SCIP_ROW **cuts, SCIP_Real *scores, int ncuts, SCIP_Real maxparallel, SCIP_Real paralpenalty)
#define CUTSEL_DESC
#define CUTSEL_PRIORITY
static int filterWithParallelism(SCIP_ROW *cut, SCIP_ROW **cuts, SCIP_Real *scores, int ncuts, SCIP_Real maxparallel)
#define DEFAULT_EXPIMPROVWEIGHT
#define DEFAULT_MAXCOEFRATIOBONUS
#define DEFAULT_DIRCUTOFFDISTWEIGHT
#define DEFAULT_MAXCUTDENSITY
#define DEFAULT_MAXNONZEROROOTROUND
#define CUTSEL_NAME
#define DEFAULT_PENALISEOBJPARAL
#define DEFAULT_MAXNUMVARS
#define DEFAULT_PSCOSTWEIGHT
#define DEFAULT_FILTERPARALCUTS
#define DEFAULT_MAXPARAL
#define DEFAULT_INTSUPPORTWEIGHT
ensemble cut selector
#define NULL
Definition def.h:267
#define LOG1P(x)
Definition def.h:222
#define SCIP_INVALID
Definition def.h:193
#define SCIP_Real
Definition def.h:173
#define ABS(x)
Definition def.h:235
#define SQR(x)
Definition def.h:214
#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
static const SCIP_Real density
Definition gastrans.c:145
SCIP_RETCODE SCIPselectCutsEnsemble(SCIP *scip, SCIP_ROW **cuts, SCIP_ROW **forcedcuts, SCIP_CUTSELDATA *cutseldata, SCIP_Bool root, int ncuts, int nforcedcuts, int maxselectedcuts, int *nselectedcuts)
SCIP_RETCODE SCIPincludeCutselEnsemble(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
Definition scip_prob.c:1992
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
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:57
void SCIPswapPointers(void **pointer1, void **pointer2)
Definition misc.c:10396
void SCIPswapReals(SCIP_Real *value1, SCIP_Real *value2)
Definition misc.c:10383
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition lp.c:17042
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
Definition lp.c:16996
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_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_RETCODE SCIPsetCutselExit(SCIP *scip, SCIP_CUTSEL *cutsel,)
SCIP_CUTSELDATA * SCIPcutselGetData(SCIP_CUTSEL *cutsel)
Definition cutsel.c:419
void SCIPcutselSetData(SCIP_CUTSEL *cutsel, SCIP_CUTSELDATA *cutseldata)
Definition cutsel.c:429
const char * SCIPcutselGetName(SCIP_CUTSEL *cutsel)
Definition cutsel.c:159
SCIP_RETCODE SCIPsetCutselFree(SCIP *scip, SCIP_CUTSEL *cutsel,)
int SCIPgetNLPCols(SCIP *scip)
Definition scip_lp.c:527
#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 SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:1922
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition lp.c:17292
SCIP_Real SCIPgetRowMinCoef(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:1904
SCIP_Real SCIPgetRowFeasibility(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:2124
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_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition lp.c:17238
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition lp.c:17302
SCIP_Real SCIProwGetNorm(SCIP_ROW *row)
Definition lp.c:17268
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_Real * SCIProwGetVals(SCIP_ROW *row)
Definition lp.c:17248
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition scip_sol.c:2169
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_Bool SCIPisSumLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPvarGetNLocksDown(SCIP_VAR *var)
Definition var.c:3416
int SCIPvarGetNLocksUp(SCIP_VAR *var)
Definition var.c:3429
SCIP_Real SCIPgetVarPseudocostScore(SCIP *scip, SCIP_VAR *var, SCIP_Real solval)
Definition scip_var.c:9105
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition misc.c:10130
return SCIP_OKAY
SCIPfreeRandom(scip, &heurdata->randnumgen)
SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE))
static SCIP_SOL * sol
assert(minobj< SCIPgetCutoffbound(scip))
#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
#define SCIP_DECL_CUTSELEXIT(x)
Definition type_cutsel.h:86
#define SCIP_DECL_CUTSELSELECT(x)
#define SCIP_DECL_CUTSELFREE(x)
Definition type_cutsel.h:70
struct SCIP_CutselData SCIP_CUTSELDATA
Definition type_cutsel.h:53
#define SCIP_DECL_CUTSELINIT(x)
Definition type_cutsel.h:78
#define SCIP_DECL_CUTSELCOPY(x)
Definition type_cutsel.h:62
@ SCIP_DIDNOTFIND
Definition type_result.h:44
@ SCIP_SUCCESS
Definition type_result.h:58
enum SCIP_Retcode SCIP_RETCODE