# SCIP

Solving Constraint Integer Programs

cutsel_hybrid.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 /* */
7 /* fuer Informationstechnik Berlin */
8 /* */
10 /* */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file cutsel_hybrid.h
17  * @ingroup CUTSELECTORS
18  * @brief hybrid cut selector
19  * @author Leona Gottwald
20  * @author Felipe Serrano
21  * @author Mark Turner
22  *
23  * The hybrid cut selector scores cuts by using a weighted sum of the efficacy, directed cutoff distance, objective
24  * parallelism, and integer support of the cuts. Afterwards, it selects the cuts using the score and filtering for
25  * parallelism after selecting each cut.
26  *
27  * If a cut is given by \f$a^T x \leq b \f$, then
28  * - the efficacy is defined as the distance between the LP solution and the hyperplane \f$a^T x = b \f$;
29  * - the directed cutoff distance is defined as the distance between the LP solution and the hyperplane \f$a^T x = b \f$
30  * restricted to the line segment joining the LP solution to the currently best primal solution; therefore, it is only
31  * defined when a primal solution is available;
32  * - the objective parallelism is how parallel the vector \f$a \f$ is w.r.t. the objective function \f$c \f$. That
33  * is, the objective parallelism is given by \f$\frac{a^T c}{\|a\| \|c\|} \f$. Notice that the vectors are parallel
34  * when this formula returns 1;
35  * - the integer support of a cut is the ratio between the number of nonzero integer columns and the number of nonzero
36  * columns.
37  *
38  * These features of a cut can be recovered and/or computed with the functions @ref SCIPgetCutEfficacy(), @ref
39  * SCIPgetCutLPSolCutoffDistance(), @ref SCIPgetRowObjParallelism(), and @ref SCIPgetRowNumIntCols(), @ref
40  * SCIProwGetNNonz().
41  *
42  * The filtering step works as follows.
43  * After computing the scores, these are divided in two groups: good scores and bad scores. Any score larger or equal
44  * to 90% of the largest score is considered a good score.
45  *
46  * First, the forced cuts --- cuts that are going to enter the LP no matter what --- are used to filter the non-forced
47  * cuts. This means that for each forced cut, @p fcut, the parallelism between @p fcut and
48  * every non-forced cut, @p cut, is computed (the parallelism between two cuts \f$a^T x \leq b \f$ and \f$d^T x \leq e\f$
49  * is \f$\frac{a^T d}{\|a\| \|d\|} \f$).
50  * If the score of cut is good, then cut is dropped if its parallelism with @p fcut is larger or equal than the maximum
51  * between \f$\frac{1}{2} \f$ and 1 - minimum orthogonality.
52  * If the score of cut is not good, then cut is dropped if its parallelism with @p fcut is larger or equal than 1 - minimum
53  * orthogonality.
54  *
55  * @note The minimum orthogonality is a parameter that can be set, as well as the weights for the score.
56  *
57  * @note In the case of no primal solution, the weight assigned to the directed cutoff distance is transfered to the
58  * efficacy.
59  */
60
61 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
62
63 #ifndef __SCIP_CUTSEL_HYBRID_H__
64 #define __SCIP_CUTSEL_HYBRID_H__
65
66
67 #include "scip/scip.h"
68
69 #ifdef __cplusplus
70 extern "C" {
71 #endif
72
73 /** creates the hybrid separator and includes it in SCIP
74  *
75  * @ingroup CutSelectorIncludes
76  */
77 SCIP_EXPORT
79  SCIP* scip /**< SCIP data structure */
80  );
81
83  *
84  * @{
85  */
86
87 /** perform a cut selection algorithm for the given array of cuts
88  *
89  * This is the selection method of the hybrid cut selector which uses a weighted sum of the
90  * efficacy, parallelism, directed cutoff distance, and the integral support.
91  * The input cuts array gets resorted s.t the selected cuts come first and the remaining
92  * ones are the end.
93  */
94 SCIP_EXPORT
96  SCIP* scip, /**< SCIP data structure */
97  SCIP_ROW** cuts, /**< array with cuts to perform selection algorithm */
98  SCIP_ROW** forcedcuts, /**< array with forced cuts */
99  SCIP_RANDNUMGEN* randnumgen, /**< random number generator for tie-breaking, or NULL */
100  SCIP_Real goodscorefac, /**< factor of best score among the given cuts to consider a cut good
101  * and filter with less strict settings of the maximum parallelism */
102  SCIP_Real badscorefac, /**< factor of best score among the given cuts to consider a cut bad
103  * and discard it regardless of its parallelism to other cuts */
104  SCIP_Real goodmaxparall, /**< maximum parallelism for good cuts */
105  SCIP_Real maxparall, /**< maximum parallelism for non-good cuts */
106  SCIP_Real dircutoffdistweight,/**< weight of directed cutoff distance in cut score calculation */
107  SCIP_Real efficacyweight, /**< weight of efficacy in cut score calculation */
108  SCIP_Real objparalweight, /**< weight of objective parallelism in cut score calculation */
109  SCIP_Real intsupportweight, /**< weight of integral support in cut score calculation */
110  int ncuts, /**< number of cuts in cuts array */
111  int nforcedcuts, /**< number of forced cuts */
112  int maxselectedcuts, /**< maximal number of cuts from cuts array to select */
113  int* nselectedcuts /**< pointer to return number of selected cuts from cuts array */
114  );
115
116 /** @} */
117
118 #ifdef __cplusplus
119 }
120 #endif
121
122 #endif
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPincludeCutselHybrid(SCIP *scip)
SCIP_RETCODE SCIPselectCutsHybrid(SCIP *scip, SCIP_ROW **cuts, SCIP_ROW **forcedcuts, SCIP_RANDNUMGEN *randnumgen, SCIP_Real goodscorefac, SCIP_Real badscorefac, SCIP_Real goodmaxparall, 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:177
SCIP callable library.