cutsel_hybrid.h File Reference

Detailed Description

hybrid cut selector

Author

Leona Gottwald

Felipe Serrano

Mark Turner

The hybrid cut selector scores cuts by using a weighted sum of the efficacy, directed cutoff distance, objective parallelism, and integer support of the cuts. Afterwards, it selects the cuts using the score and filtering for parallelism after selecting each cut.

If a cut is given by \( a^T x \leq b \), then

• the efficacy is defined as the distance between the LP solution and the hyperplane \( a^T x = b \);
• the directed cutoff distance is defined as the distance between the LP solution and the hyperplane \( a^T x = b \) restricted to the line segment joining the LP solution to the currently best primal solution; therefore, it is only defined when a primal solution is available;
• the objective parallelism is how parallel the vector \( a \) is w.r.t. the objective function \( c \). That is, the objective parallelism is given by \( \frac{a^T c}{\|a\| \|c\|} \). Notice that the vectors are parallel when this formula returns 1;
• the integer support of a cut is the ratio between the number of nonzero integer columns and the number of nonzero columns.

These features of a cut can be recovered and/or computed with the functions SCIPgetCutEfficacy(), SCIPgetCutLPSolCutoffDistance(), SCIPgetRowObjParallelism(), and SCIPgetRowNumIntCols(), SCIProwGetNNonz().

The filtering step works as follows. After computing the scores, these are divided in two groups: good scores and bad scores. Any score larger or equal to 90% of the largest score is considered a good score.

First, the forced cuts — cuts that are going to enter the LP no matter what — are used to filter 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 score of cut is good, then cut is dropped if its parallelism with fcut is larger or equal than the maximum between \( \frac{1}{2} \) and 1 - minimum orthogonality. If the score of cut is not good, then cut is dropped if its parallelism with fcut is larger or equal than 1 - minimum orthogonality.

Note

The minimum orthogonality is a parameter that can be set, as well as the weights for the score.

In the case of no primal solution, the weight assigned to the directed cutoff distance is transfered to the efficacy.

Definition in file cutsel_hybrid.h.

#include "scip/scip.h"

Go to the source code of this file.

Functions
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)