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