ensemble cut selector
This cut selector is based on the paper: M. Turner, T. Berthold, and M. Besançon.
A Context-Aware Cutting Plane Selection Algorithm for Mixed-Integer Programming.
arXiv preprint arXiv:2307.07322 (2023).
The ensemble cut selector scores cuts by using a weighted sum of normalised efficacy, normalised directed cutoff distance (only at the root node), normalised expected objective improvement, objective parallelism, integer support, density, dynamism, normalised pseudo-costs, and normalised number of locks. It also has a variety of filtering methods. If density filtering is enabled, then it filters all cuts before scoring over some relative density threshold. After scoring, it selects the cuts with the highest score, where after each selection, the remaining cuts are either filtered or penalised via parallelism checks. Whether the cuts are filtered or penalised is a users choice. The algorithm terminates when some limit of selected cuts is reached, there are no cuts remaining to select, or the score of all remaining cuts is below minscore.
If a cut is given by \( a^T x \leq b \), then
These features of a cut can be recovered and/or computed with the functions SCIPgetCutEfficacy(), SCIPgetCutLPSolCutoffDistance(), SCIPgetRowObjParallelism(), and SCIPgetRowNumIntCols(), SCIProwGetNNonz(), SCIProwGetVals(), SCIProwGetCols(), SCIPgetVarPseudocostScore(), SCIPvarGetNLocksUp(), SCIPvarGetNLocksDown().
The filtering (density) works as follows: The non-forced cuts are scanned through, and any cut over a density threshold (0,1) is dropped from consideration.
The filtering / penalise (parallelism) step works as follows: First, the forced cuts — cuts that are going to enter the LP no matter what — are used to filter / penalise the non-forced cuts. This means that for each forced cut, fcut
, the parallelism between fcut
and every non-forced cut, cut
, is computed (the parallelism between two cuts \( a^T x \leq b \) and \( d^T x \leq e\) is \( \frac{a^T d}{\|a\| \|d\|} \)). If the parallelism with fcut
is larger or equal than some maximum threshold then it is either removed from consideration (if filter by parallelism), or its score is decreased (if penalise by parallelism). If the score drops below some threshold minscore
, then the cut is removed from consideration. Each time a cut is selected (which is always greedily w.r.t. the scores), the same filtering procedure for parallelism described above is run.
Definition in file cutsel_ensemble.h.
#include "scip/scip.h"
Go to the source code of this file.
Functions | |
SCIP_RETCODE | SCIPincludeCutselEnsemble (SCIP *scip) |
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) |