closecuts meta separator
This separator generates a convex combination of the current LP solution and either the best primal feasible solution or an interior point of the LP relaxation. If the convex combination is proper, the new point is closer to the convex hull of the feasible points. The separator then calls all other separators to separate this point. The idea is that in this way possibly "deeper" cuts are generated. Note, however, that the new point is not a basic solution, i.e., separators relying basis information, e.g., Gomory cuts, will not work.
The other cuts are generated via the sepasol() callbacks in constraints handlers or separators.
This separator stops after a certain number (parameter maxunsuccessful
) of unsuccessful calls. It also inhibits the separation of the ordinary LP solution if it already generated enough (parameter sepathreshold
) cuts. The convex combination is determined via the parameter sepacombvalue
.
In general, this separator makes sense if it is expected that there will be many separation rounds and many cuts will be again deleted, because they are not active after a certain number of rounds. In particular, branch-and-cut algorithms for combinatorial optimization problems form good candidates.
The idea seems to be first proposed in the context of the travelling salesman problem, see
Definition in file sepa_closecuts.c.
Go to the source code of this file.
Macros | |
#define | SEPA_NAME "closecuts" |
#define | SEPA_DESC "closecuts meta separator" |
#define | SEPA_PRIORITY 1000000 |
#define | SEPA_FREQ -1 |
#define | SEPA_MAXBOUNDDIST 1.0 |
#define | SEPA_USESSUBSCIP FALSE |
#define | SEPA_DELAY FALSE |
#define | SCIP_DEFAULT_SEPARELINT TRUE |
#define | SCIP_DEFAULT_SEPACOMBVALUE 0.30 |
#define | SCIP_DEFAULT_SEPATHRESHOLD 50 |
#define | SCIP_DEFAULT_INCLOBJCUTOFF FALSE |
#define | SCIP_DEFAULT_RECOMPUTERELINT FALSE |
#define | SCIP_DEFAULT_MAXUNSUCCESSFUL 0 |
#define | SCIP_DEFAULT_MAXLPITERFACTOR 10.0 |
#define | SCIP_MIN_LPITERS 100 |
Functions | |
static SCIP_RETCODE | generateCloseCutPoint (SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_SOL **point) |
static | SCIP_DECL_SEPACOPY (sepaCopyClosecuts) |
static | SCIP_DECL_SEPAFREE (sepaFreeClosecuts) |
static | SCIP_DECL_SEPAEXITSOL (sepaExitsolClosecuts) |
static | SCIP_DECL_SEPAEXECLP (sepaExeclpClosecuts) |
SCIP_RETCODE | SCIPincludeSepaClosecuts (SCIP *scip) |
SCIP_RETCODE | SCIPsetBasePointClosecuts (SCIP *scip, SCIP_SOL *sol) |
#define SEPA_NAME "closecuts" |
Definition at line 58 of file sepa_closecuts.c.
Referenced by SCIP_DECL_SEPACOPY(), SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAEXITSOL(), SCIP_DECL_SEPAFREE(), SCIPincludeSepaClosecuts(), and SCIPsetBasePointClosecuts().
#define SEPA_DESC "closecuts meta separator" |
Definition at line 59 of file sepa_closecuts.c.
Referenced by SCIPincludeSepaClosecuts().
#define SEPA_PRIORITY 1000000 |
Definition at line 60 of file sepa_closecuts.c.
Referenced by SCIPincludeSepaClosecuts().
#define SEPA_FREQ -1 |
Definition at line 61 of file sepa_closecuts.c.
Referenced by SCIPincludeSepaClosecuts().
#define SEPA_MAXBOUNDDIST 1.0 |
Definition at line 62 of file sepa_closecuts.c.
Referenced by SCIPincludeSepaClosecuts().
#define SEPA_USESSUBSCIP FALSE |
does the separator use a secondary SCIP instance?
Definition at line 63 of file sepa_closecuts.c.
Referenced by SCIPincludeSepaClosecuts().
#define SEPA_DELAY FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 64 of file sepa_closecuts.c.
Referenced by SCIPincludeSepaClosecuts().
#define SCIP_DEFAULT_SEPARELINT TRUE |
generate close cuts w.r.t. relative interior point (best solution otherwise)?
Definition at line 68 of file sepa_closecuts.c.
Referenced by SCIPincludeSepaClosecuts().
#define SCIP_DEFAULT_SEPACOMBVALUE 0.30 |
convex combination value for close cuts
Definition at line 69 of file sepa_closecuts.c.
Referenced by SCIPincludeSepaClosecuts().
#define SCIP_DEFAULT_SEPATHRESHOLD 50 |
threshold on number of generated cuts below which the ordinary separation is started
Definition at line 70 of file sepa_closecuts.c.
Referenced by SCIPincludeSepaClosecuts().
#define SCIP_DEFAULT_INCLOBJCUTOFF FALSE |
include the objective cutoff when computing the relative interior?
Definition at line 71 of file sepa_closecuts.c.
Referenced by SCIPincludeSepaClosecuts().
#define SCIP_DEFAULT_RECOMPUTERELINT FALSE |
recompute relative interior in each separation call?
Definition at line 72 of file sepa_closecuts.c.
Referenced by SCIPincludeSepaClosecuts().
#define SCIP_DEFAULT_MAXUNSUCCESSFUL 0 |
turn off separation in current node after unsuccessful calls (-1 never turn off)
Definition at line 73 of file sepa_closecuts.c.
Referenced by SCIPincludeSepaClosecuts().
#define SCIP_DEFAULT_MAXLPITERFACTOR 10.0 |
factor for maximal LP iterations in relative interior computation compared to node LP iterations
Definition at line 74 of file sepa_closecuts.c.
Referenced by SCIPincludeSepaClosecuts().
#define SCIP_MIN_LPITERS 100 |
minimum number of allowed LP iterations in relative interior computation
Definition at line 76 of file sepa_closecuts.c.
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
generate point for close cut separation
The constructed point is the convex combination of the point stored in set->closesol and the current LP solution. The convexity parameter is set->sepa_closecombvalue. If this parameter is 0, the point coincides with the LP solution.
scip | SCIP data structure |
sepadata | separator data |
point | point to be generated (or NULL if unsuccessful) |
Definition at line 103 of file sepa_closecuts.c.
References MAX, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcreateSol(), SCIPgetNVars(), SCIPgetSolVal(), SCIPgetVars(), SCIPisZero(), SCIPsetSolVal(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), and SCIPvarGetUbLocal().
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 167 of file sepa_closecuts.c.
References SCIP_CALL, SCIP_OKAY, SCIPincludeSepaClosecuts(), SCIPsepaGetName(), and SEPA_NAME.
|
static |
destructor of separator to free user data (called when SCIP is exiting)
Definition at line 181 of file sepa_closecuts.c.
References SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaSetData(), and SEPA_NAME.
|
static |
solving process deinitialization method of separator (called before branch and bound process data is freed)
Definition at line 202 of file sepa_closecuts.c.
References FALSE, SCIP_CALL, SCIP_OKAY, SCIPfreeSol(), SCIPsepaGetData(), SCIPsepaGetName(), and SEPA_NAME.
|
static |
LP solution separation method of separator
Definition at line 224 of file sepa_closecuts.c.
References FALSE, generateCloseCutPoint(), MAX, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_MIN_LPITERS, SCIP_NEWROUND, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIP_VERBLEVEL_MINIMAL, SCIPcomputeLPRelIntPoint(), SCIPdebugMsg, SCIPfreeSol(), SCIPgetBestSol(), SCIPgetCurrentNode(), SCIPgetDepth(), SCIPgetLPSolstat(), SCIPgetNCuts(), SCIPgetNLPBranchCands(), SCIPgetNLPIterations(), SCIPgetNRootLPIterations(), SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPisInfinity(), SCIPisStopped(), SCIPnodeGetNumber(), SCIPremoveInefficaciousCuts(), SCIPsepaGetData(), SCIPsepaGetName(), SCIPseparateSol(), SCIPverbMessage(), SEPA_NAME, and TRUE.