Scippy

SCIP

Solving Constraint Integer Programs

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