SCIP Doxygen Documentation
Loading...
Searching...
No Matches
cutsel_ensemble.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-2025 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.h
26
* @ingroup CUTSELECTORS
27
* @brief ensemble cut selector
28
* @author Mark Turner
29
*
30
* This cut selector is based on the paper:
31
* M. Turner, T. Berthold, and M. Besançon. @n
32
* A Context-Aware Cutting Plane Selection Algorithm for Mixed-Integer Programming.@n
33
* arXiv preprint arXiv:2307.07322 (2023).
34
*
35
* The ensemble cut selector scores cuts by using a weighted sum of normalised efficacy,
36
* normalised directed cutoff distance (only at the root node), normalised expected objective improvement,
37
* objective parallelism, integer support, density, dynamism, normalised pseudo-costs, and normalised number of locks.
38
* It also has a variety of filtering methods. If density filtering is enabled, then it filters all cuts before
39
* scoring over some relative density threshold. After scoring, it selects the cuts with the highest score,
40
* where after each selection, the remaining cuts are either filtered or penalised via parallelism checks.
41
* Whether the cuts are filtered or penalised is a users choice.
42
* The algorithm terminates when some limit of selected cuts is reached, there are no cuts remaining to select,
43
* or the score of all remaining cuts is below minscore.
44
*
45
* If a cut is given by \f$ a^T x \leq b \f$, then
46
* - the efficacy is defined as the distance between the LP solution and the hyperplane \f$ a^T x = b \f$.
47
* It is normalised by the largest efficacy from the given array of cuts. ((log(eff(cut) + 1) / log(maxeff + 1))**2 ;
48
* - the directed cutoff distance is defined as the distance between the LP solution and the hyperplane \f$ a^T x = b \f$
49
* restricted to the line segment joining the LP solution to the currently best primal solution; therefore, it is only
50
* defined when a primal solution is available. It is normalised by the largest cutoff distance from the
51
* given array of cuts. ((log(dcd(cut) + 1) / log(maxdcd + 1))**2;
52
* - the objective parallelism is how parallel the vector \f$ a \f$ is w.r.t. the objective function \f$ c \f$. That
53
* is, the objective parallelism is given by \f$ \frac{a^T c}{\|a\| \|c\|} \f$. Notice that the vectors are parallel
54
* when this formula returns 1;
55
* - the expected objective improvement is defined by the difference of the objective evaluated at the LP solution
56
* and when evaluated at the orthogonal projection onto the cut. As we normalise the value, we remove the
57
* objective vector multiplication from its calculation. We calculate it as efficacy * objective parallelism.
58
* We also normalise it according to the equation ((log(expimprov(cut) + 1) / log(maxexpimprov + 1))**2;
59
* - the integer support of a cut is the ratio between the number of nonzero integer columns and the number of nonzero
60
* columns.
61
* - the density of a cut is the ratio of non-zero entries divided by the number of columns in the LP;
62
* - the dynamism of a cut is the ratio between the maximum absolute value over all coefficients and the
63
* minimum absolute value over all coefficients. If this ratio is below a threshold, we give the cut a flat reward
64
* for good numerics;
65
* - the pseudo-cost score of the cut is the pseudo-cost score of each variable with non-zero coefficient in the cut
66
* multiplied by the distance in that variable dimension to the orthogonal projection of the LP solution onto
67
* the cut. We normalise the result by the maximum over all cuts: pscost / maxpscost
68
* - the number of variable locks for a cut is the average amount of locks attached to variables with
69
* non-zero coefficients in the cut. We normalise the result by the maximum over all cuts: numlocks / maxnumlocks
70
*
71
* These features of a cut can be recovered and/or computed with the functions @ref SCIPgetCutEfficacy(), @ref
72
* SCIPgetCutLPSolCutoffDistance(), @ref SCIPgetRowObjParallelism(), and @ref SCIPgetRowNumIntCols(), @ref
73
* SCIProwGetNNonz(), @ref SCIProwGetVals(), @ref SCIProwGetCols(), @ref SCIPgetVarPseudocostScore(),
74
* @ref SCIPvarGetNLocksUp(), @ref SCIPvarGetNLocksDown().
75
*
76
* The filtering (density) works as follows:
77
* The non-forced cuts are scanned through, and any cut over a density threshold (0,1) is dropped from
78
* consideration.
79
*
80
* The filtering / penalise (parallelism) step works as follows:
81
* First, the forced cuts --- cuts that are going to enter the LP no matter what --- are used to filter / penalise
82
* the non-forced cuts. This means that for each forced cut, @p fcut, the parallelism between @p fcut and
83
* 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$
84
* is \f$ \frac{a^T d}{\|a\| \|d\|} \f$).
85
* If the parallelism with @p fcut is larger or equal than some maximum threshold then it is either removed from
86
* consideration (if filter by parallelism), or its score is decreased (if penalise by parallelism).
87
* If the score drops below some threshold @p minscore, then the cut is removed from consideration.
88
* Each time a cut is selected (which is always greedily w.r.t. the scores), the same filtering procedure for
89
* parallelism described above is run.
90
*
91
* @note The maximum parallelism is a parameter that can be set, as well as the weights for the score.
92
*
93
* @note In the case of no primal solution, the weight assigned to the directed cutoff distance is transferred to the
94
* efficacy.
95
*/
96
97
/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
98
99
#ifndef __SCIP_CUTSEL_ENSEMBLE_H__
100
#define __SCIP_CUTSEL_ENSEMBLE_H__
101
102
103
#include "
scip/scip.h
"
104
105
#ifdef __cplusplus
106
extern
"C"
{
107
#endif
108
109
/** creates the ensemble separator and includes it in SCIP
110
*
111
* @ingroup CutSelectorIncludes
112
*/
113
SCIP_EXPORT
114
SCIP_RETCODE
SCIPincludeCutselEnsemble
(
115
SCIP
*
scip
/**< SCIP data structure */
116
);
117
118
/**@addtogroup CUTSELECTORS
119
*
120
* @{
121
*/
122
123
/** perform a cut selection algorithm for the given array of cuts
124
*
125
* This is the selection method of the ensemble cut selector. It uses a weighted sum of normalised efficacy,
126
* normalised directed cutoff distance, normalised expected improvements, objective parallelism,
127
* integer support, sparsity, dynamism, pseudo-costs, and variable locks.
128
* In addition to the weighted sum score, there are optionally parallelism-based filtering and penalties,
129
* and density filtering.
130
* There are also additional budget constraints on the number of cuts that should be added.
131
* The input cuts array gets re-sorted such that the selected cuts come first and the remaining ones are the end.
132
*/
133
SCIP_EXPORT
134
SCIP_RETCODE
SCIPselectCutsEnsemble
(
135
SCIP
*
scip
,
/**< SCIP data structure */
136
SCIP_ROW
** cuts,
/**< array with cuts to perform selection algorithm */
137
SCIP_ROW
** forcedcuts,
/**< array with forced cuts */
138
SCIP_CUTSELDATA
* cutseldata,
/**< cut selector data */
139
SCIP_Bool
root,
/**< whether we are currently at the root node or not */
140
int
ncuts,
/**< number of cuts in cuts array */
141
int
nforcedcuts,
/**< number of forced cuts */
142
int
maxselectedcuts,
/**< maximal number of cuts from cuts array to select */
143
int
* nselectedcuts
/**< pointer to return number of selected cuts from cuts array */
144
);
145
146
/** @} */
147
148
#ifdef __cplusplus
149
}
150
#endif
151
152
#endif
SCIP_Bool
#define SCIP_Bool
Definition
def.h:91
SCIPselectCutsEnsemble
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)
Definition
cutsel_ensemble.c:681
SCIPincludeCutselEnsemble
SCIP_RETCODE SCIPincludeCutselEnsemble(SCIP *scip)
Definition
cutsel_ensemble.c:556
scip
Definition
objbenders.h:44
scip.h
SCIP callable library.
SCIP_CUTSELDATA
struct SCIP_CutselData SCIP_CUTSELDATA
Definition
type_cutsel.h:53
SCIP_ROW
struct SCIP_Row SCIP_ROW
Definition
type_lp.h:104
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition
type_retcode.h:63
SCIP
struct Scip SCIP
Definition
type_scip.h:39
cutsel_ensemble.h
© 2002-2025 by Zuse Institute Berlin (ZIB),
Imprint
Generated by
1.13.2