Scippy

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