1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (C) 2002-2022 Konrad-Zuse-Zentrum */ 7 /* fuer Informationstechnik Berlin */ 8 /* */ 9 /* SCIP is distributed under the terms of the ZIB Academic License. */ 10 /* */ 11 /* You should have received a copy of the ZIB Academic License */ 12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */ 13 /* */ 14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 15 16 /**@file cutsel_dynamic.h 17 * @ingroup CUTSELECTORS 18 * @brief dynamic cut selector 19 * @author Christoph Graczyk 20 * 21 * The dynamic cut selector is an extension of the hybrid cut selector to employ a dynamic range for the orthogonality 22 * filtering, dependent on the efficacy ratio between cuts. It allows the user to specify a minimum efficacy gain in 23 * percentage to filter cuts, which corresponds geometrically to the idealized shift from the LP solution adding only 24 * the first cut to the intersection with the second cut. 25 * In this way we can enforce a minimum orthogonality between cuts through the efficacy ratio. This should, in theory, 26 * avoid the selection of cutting plane pairs that do not improve the lp solution, but only increase the number of cuts 27 * in the lp. 28 * 29 * The selector allows the user to specify a filtering strategy during cut selection ('d'ynamic- and 'f'ull dynamic), 30 * which determines how the orthogonality filtering is applied. 31 * In both cases, after a cut is selected, the remaining cuts are resorted by computing their relative efficacy to the 32 * selected cut. The efficacy ratio is then used to filter the cuts based on the filtering strategy: 33 * - 'd'ynamic-parallelism: The dynamic parallelism strategy filters cuts based on the efficacy ratio between cut 34 * pairs. It only filters cuts that are not theoretically improving the efficacy of the pair given the first cut, i.e., 35 * the efficacy ratio is below the minimum efficacy gain in percentage, without calculating or resorting the cut array. 36 * 37 * - 'f'ull dynamic parallelism: The full dynamic parallelism strategy filters cuts based on the efficacy ratio between 38 * cut pairs by iteratively recomputing the score given the previously selected cut. This results in a set of cuts 39 * that is a sequence of theoretically most effective almost orthogonal cuts, whereby almost orthogonal means that 40 * the efficacy ratio is above the minimum efficacy gain in percentage. 41 */ 42 43 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 44 45 #ifndef __SCIP_CUTSEL_DYNAMIC_H__ 46 #define __SCIP_CUTSEL_DYNAMIC_H__ 47 48 49 #include "scip/scip.h" 50 51 #ifdef __cplusplus 52 extern "C" { 53 #endif 54 55 /** creates the dynamic hybrid separator and includes it in SCIP 56 * 57 * @ingroup CutSelectorIncludes 58 */ 59 SCIP_EXPORT 60 SCIP_RETCODE SCIPincludeCutselDynamic( 61 SCIP* scip /**< SCIP data structure */ 62 ); 63 64 /**@addtogroup CUTSELECTORS 65 * 66 * @{ 67 */ 68 69 /** perform a cut selection algorithm for the given array of cuts 70 * 71 * This is an extension of the hybrid cutselector to employ a dynamic range 72 * when applying orthogonality filtering, dependent on the efficacy ratio between cuts. 73 * 74 * The input cuts array should be resorted such that the selected cuts come first. 75 */ 76 SCIP_EXPORT 77 SCIP_RETCODE SCIPselectCutsDynamic( 78 SCIP* scip, /**< SCIP data structure */ 79 SCIP_ROW** cuts, /**< array with cuts to perform selection algorithm */ 80 SCIP_ROW** forcedcuts, /**< array with forced cuts */ 81 SCIP_RANDNUMGEN* randnumgen, /**< random number generator for tie-breaking, or NULL */ 82 char filtermode, /**< filtering strategy during cut selection ( 83 * 'd'ynamic- and 'f'ull dynamic parallelism) */ 84 SCIP_Real mingain, /**< minimum efficacy gain in percentage to filter cuts */ 85 SCIP_Real maxparall, /**< maximal parallelism for all cuts that are not good */ 86 SCIP_Real dircutoffdistweight,/**< weight of directed cutoff distance in cut score calculation */ 87 SCIP_Real efficacyweight, /**< weight of efficacy in cut score calculation */ 88 SCIP_Real objparalweight, /**< weight of objective parallelism in cut score calculation */ 89 SCIP_Real intsupportweight, /**< weight of integral support in cut score calculation */ 90 int ncuts, /**< number of cuts in cuts array */ 91 int nforcedcuts, /**< number of forced cuts */ 92 int maxselectedcuts, /**< maximal number of cuts from cuts array to select */ 93 int* nselectedcuts /**< pointer to return number of selected cuts from cuts array */ 94 ); 95 96 /** @} */ 97 98 #ifdef __cplusplus 99 } 100 #endif 101 102 #endif 103