1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright 2002-2022 Zuse Institute Berlin */ 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 153