cutsel_dynamic.h File Reference

Detailed Description

dynamic cut selector

Author

Christoph Graczyk

The dynamic cut selector is an extension of the hybrid cut selector to employ a dynamic range for the orthogonality filtering, dependent on the efficacy ratio between cuts. It allows the user to specify a minimum efficacy gain in percentage to filter cuts, which corresponds geometrically to the idealized shift from the LP solution adding only the first cut to the intersection with the second cut. In this way we can enforce a minimum orthogonality between cuts through the efficacy ratio. This should, in theory, avoid the selection of cutting plane pairs that do not improve the lp solution, but only increase the number of cuts in the lp.

The selector allows the user to specify a filtering strategy during cut selection ('d'ynamic- and 'f'ull dynamic), which determines how the orthogonality filtering is applied. In both cases, after a cut is selected, the remaining cuts are resorted by computing their relative efficacy to the selected cut. The efficacy ratio is then used to filter the cuts based on the filtering strategy:

• 'd'ynamic-parallelism: The dynamic parallelism strategy filters cuts based on the efficacy ratio between cut pairs. It only filters cuts that are not theoretically improving the efficacy of the pair given the first cut, i.e., the efficacy ratio is below the minimum efficacy gain in percentage, without calculating or resorting the cut array.
• 'f'ull dynamic parallelism: The full dynamic parallelism strategy filters cuts based on the efficacy ratio between cut pairs by iteratively recomputing the score given the previously selected cut. This results in a set of cuts that is a sequence of theoretically most effective almost orthogonal cuts, whereby almost orthogonal means that the efficacy ratio is above the minimum efficacy gain in percentage.

Definition in file cutsel_dynamic.h.

#include "scip/scip.h"

Go to the source code of this file.

Functions
SCIP_RETCODE	SCIPincludeCutselDynamic (SCIP *scip)
SCIP_RETCODE	SCIPselectCutsDynamic (SCIP *scip, SCIP_ROW **cuts, SCIP_ROW **forcedcuts, SCIP_RANDNUMGEN *randnumgen, char filtermode, SCIP_Real mingain, SCIP_Real maxparall, SCIP_Real dircutoffdistweight, SCIP_Real efficacyweight, SCIP_Real objparalweight, SCIP_Real intsupportweight, int ncuts, int nforcedcuts, int maxselectedcuts, int *nselectedcuts)