DINS primal heuristic (according to Ghosh)
Definition in file heur_dins.c.
#include <assert.h>
#include <string.h>
#include "scip/scip.h"
#include "scip/cons_linear.h"
#include "scip/heur_dins.h"
Go to the source code of this file.
Macros | |
#define | HEUR_NAME "dins" |
#define | HEUR_DESC "distance induced neighborhood search by Ghosh" |
#define | HEUR_DISPCHAR 'D' |
#define | HEUR_PRIORITY -1105000 |
#define | HEUR_FREQ -1 |
#define | HEUR_FREQOFS 0 |
#define | HEUR_MAXDEPTH -1 |
#define | HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE |
#define | HEUR_USESSUBSCIP TRUE |
#define | DEFAULT_NODESOFS 5000LL /* number of nodes added to the contingent of the total nodes */ |
#define | DEFAULT_MAXNODES 5000LL /* maximum number of nodes to regard in the subproblem */ |
#define | DEFAULT_MINNODES 50LL /* minimum number of nodes to regard in the subproblem */ |
#define | DEFAULT_MINIMPROVE 0.01 /* factor by which DINS should at least improve the incumbent */ |
#define | DEFAULT_NODESQUOT 0.05 /* subproblem nodes in relation to nodes of the original problem */ |
#define | DEFAULT_LPLIMFAC 1.5 /* factor by which the limit on the number of LP depends on the node limit */ |
#define | DEFAULT_MINFIXINGRATE 0.3 /* minimum percentage of integer variables that have to be fixed */ |
#define | DEFAULT_NWAITINGNODES 200LL /* number of nodes without incumbent change that heuristic should wait */ |
#define | DEFAULT_NEIGHBORHOODSIZE 18 /* radius of the incumbents neighborhood to be searched */ |
#define | DEFAULT_SOLNUM 5 /* number of pool-solutions to be checked for flag array update */ |
#define | DEFAULT_USELPROWS |
#define | DEFAULT_COPYCUTS |
#define | DEFAULT_BESTSOLLIMIT 3 /* limit on number of improving incumbent solutions in sub-CIP */ |
#define | DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */ |
#define | EVENTHDLR_NAME "Dins" |
#define | EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" |
Functions | |
static void | computeIntegerVariableBounds (SCIP *scip, SCIP_VAR *var, SCIP_Real *lbptr, SCIP_Real *ubptr) |
static SCIP_RETCODE | determineVariableFixings (SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_VAR **vars, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nbinvars, int nintvars, int *binfixings, int *intfixings) |
static SCIP_RETCODE | reboundIntegerVariables (SCIP *scip, SCIP *subscip, SCIP_VAR **vars, SCIP_VAR **subvars, int nbinvars, int nintvars) |
static SCIP_RETCODE | addLocalBranchingConstraint (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEURDATA *heurdata) |
static SCIP_RETCODE | createNewSol (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_Bool *success) |
static | SCIP_DECL_EVENTEXEC (eventExecDins) |
static SCIP_RETCODE | wrapperDins (SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_VAR **vars, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, SCIP_RESULT *result, int nvars, int nbinvars, int nintvars, int binfixings, int intfixings, SCIP_Longint nsubnodes) |
static | SCIP_DECL_HEURCOPY (heurCopyDins) |
static | SCIP_DECL_HEURFREE (heurFreeDins) |
static | SCIP_DECL_HEURINITSOL (heurInitsolDins) |
static | SCIP_DECL_HEUREXITSOL (heurExitsolDins) |
static | SCIP_DECL_HEUREXEC (heurExecDins) |
SCIP_RETCODE | SCIPincludeHeurDins (SCIP *scip) |
#define HEUR_NAME "dins" |
Definition at line 30 of file heur_dins.c.
Referenced by SCIP_DECL_HEURCOPY(), SCIPincludeHeurDins(), and wrapperDins().
#define HEUR_DESC "distance induced neighborhood search by Ghosh" |
Definition at line 31 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
#define HEUR_DISPCHAR 'D' |
Definition at line 32 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
#define HEUR_PRIORITY -1105000 |
Definition at line 33 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
#define HEUR_FREQ -1 |
Definition at line 34 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
#define HEUR_FREQOFS 0 |
Definition at line 35 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
#define HEUR_MAXDEPTH -1 |
Definition at line 36 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE |
Definition at line 37 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 38 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
#define DEFAULT_NODESOFS 5000LL /* number of nodes added to the contingent of the total nodes */ |
Definition at line 40 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
#define DEFAULT_MAXNODES 5000LL /* maximum number of nodes to regard in the subproblem */ |
Definition at line 41 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
#define DEFAULT_MINNODES 50LL /* minimum number of nodes to regard in the subproblem */ |
Definition at line 42 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
#define DEFAULT_MINIMPROVE 0.01 /* factor by which DINS should at least improve the incumbent */ |
Definition at line 43 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
#define DEFAULT_NODESQUOT 0.05 /* subproblem nodes in relation to nodes of the original problem */ |
Definition at line 44 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
#define DEFAULT_LPLIMFAC 1.5 /* factor by which the limit on the number of LP depends on the node limit */ |
Definition at line 45 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
#define DEFAULT_MINFIXINGRATE 0.3 /* minimum percentage of integer variables that have to be fixed */ |
Definition at line 46 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
#define DEFAULT_NWAITINGNODES 200LL /* number of nodes without incumbent change that heuristic should wait */ |
Definition at line 47 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
#define DEFAULT_NEIGHBORHOODSIZE 18 /* radius of the incumbents neighborhood to be searched */ |
Definition at line 48 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
#define DEFAULT_SOLNUM 5 /* number of pool-solutions to be checked for flag array update */ |
Definition at line 49 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
#define DEFAULT_USELPROWS |
Definition at line 50 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
#define DEFAULT_COPYCUTS |
Definition at line 52 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
#define DEFAULT_BESTSOLLIMIT 3 /* limit on number of improving incumbent solutions in sub-CIP */ |
Definition at line 55 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
#define DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */ |
Definition at line 56 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
#define EVENTHDLR_NAME "Dins" |
Definition at line 60 of file heur_dins.c.
Referenced by SCIP_DECL_EVENTEXEC(), and wrapperDins().
#define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" |
Definition at line 61 of file heur_dins.c.
Referenced by wrapperDins().
|
static |
compute tightened bounds for integer variables depending on how much the LP and the incumbent solution values differ
scip | SCIP data structure of the original problem |
var | the variable for which bounds should be computed |
lbptr | pointer to store the lower bound in the DINS sub-SCIP |
ubptr | pointer to store the upper bound in the DINS sub-SCIP |
Definition at line 100 of file heur_dins.c.
References MAX, REALABS, SCIP_Real, SCIP_VARTYPE_INTEGER, SCIPfeasCeil(), SCIPfeasFloor(), SCIPgetBestSol(), SCIPgetSolVal(), SCIPisFeasEQ(), SCIPvarGetLbGlobal(), SCIPvarGetLPSol(), SCIPvarGetType(), and SCIPvarGetUbGlobal().
Referenced by determineVariableFixings(), and reboundIntegerVariables().
|
static |
creates a subproblem for subscip by fixing a number of variables
scip | SCIP data structure of the original problem |
heur | DINS heuristic structure |
heurdata | heuristic data structure |
vars | variables of the original problem |
fixedvars | array to store variables that should be fixed in the sub-SCIP |
fixedvals | array to store fixing values for fixed variables |
nbinvars | number of binary variables of problem and subproblem |
nintvars | number of general integer variables of problem and subproblem |
binfixings | pointer to store number of binary variables that should be fixed |
intfixings | pointer to store number of integer variables that should be fixed |
Definition at line 175 of file heur_dins.c.
References computeIntegerVariableBounds(), SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPcalcMemGrowSize(), SCIPgetBestSol(), SCIPgetNSols(), SCIPgetNSolsFound(), SCIPgetSolHeur(), SCIPgetSols(), SCIPgetSolVal(), SCIPisFeasEQ(), SCIPreallocBlockMemoryArray, SCIPvarGetLPSol(), SCIPvarGetRootSol(), and TRUE.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
creates a subproblem for subscip by fixing a number of variables
scip | SCIP data structure of the original problem |
subscip | SCIP data structure of the subproblem |
vars | variables of the original problem |
subvars | variables of the DINS sub-SCIP |
nbinvars | number of binary variables of problem and subproblem |
nintvars | number of general integer variables of problem and subproblem |
Definition at line 305 of file heur_dins.c.
References computeIntegerVariableBounds(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPchgVarLbGlobal(), SCIPchgVarUbGlobal(), SCIPisFeasEQ(), SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().
Referenced by wrapperDins().
|
static |
create the extra constraint of local branching and add it to subscip
scip | SCIP data structure of the original problem |
subscip | SCIP data structure of the subproblem |
subvars | variables of the subproblem |
heurdata | heuristic's data structure |
Definition at line 339 of file heur_dins.c.
References FALSE, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPaddCons(), SCIPallocBufferArray, SCIPcreateConsLinear(), SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetProbName(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPisFeasEQ(), SCIPisFeasIntegral(), SCIPreleaseCons(), SCIPsnprintf(), SCIPvarGetLbGlobal(), SCIPvarGetType(), SCIPvarGetUbGlobal(), and TRUE.
Referenced by wrapperDins().
|
static |
creates a new solution for the original problem by copying the solution of the subproblem
scip | original SCIP data structure |
subscip | SCIP structure of the subproblem |
subvars | the variables of the subproblem |
heur | DINS heuristic structure |
subsol | solution of the subproblem |
success | used to store whether new solution was found or not |
Definition at line 412 of file heur_dins.c.
References FALSE, SCIP_CALL, SCIP_DECL_EVENTEXEC(), SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcreateSol(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetNOrigVars(), SCIPgetSolVals(), SCIPgetVarsData(), SCIPsetSolVals(), SCIPtrySolFree(), and TRUE.
Referenced by wrapperDins().
|
static |
Definition at line 693 of file heur_dins.c.
References EVENTHDLR_NAME, SCIP_CALL, SCIP_EVENTTYPE_LPSOLVED, SCIP_OKAY, SCIPdebugMsg, SCIPeventGetType(), SCIPeventhdlrGetName(), SCIPgetNLPs(), and SCIPinterruptSolve().
Referenced by createNewSol().
|
static |
wrapper for the part of heuristic that runs a subscip. Wrapper is needed to avoid possible ressource leaks
scip | original SCIP data structure |
subscip | SCIP structure of the subproblem |
heur | Heuristic pointer |
heurdata | Heuristic's data |
vars | original problem's variables |
fixedvars | Fixed variables of original SCIP |
fixedvals | Fixed values of original SCIP |
result | Result pointer |
nvars | Number of variables |
nbinvars | Number of binary variables in original SCIP |
nintvars | Number of integer variables in original SCIP |
binfixings | Number of binary fixing in original SCIP |
intfixings | Number of integer fixings in original SCIP |
nsubnodes | Number of nodes in the subscip |
Definition at line 464 of file heur_dins.c.
References addLocalBranchingConstraint(), createNewSol(), EVENTHDLR_DESC, EVENTHDLR_NAME, FALSE, HEUR_NAME, MAX, reboundIntegerVariables(), SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIP_EVENTTYPE_LPSOLVED, SCIP_FOUNDSOL, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIP_PLUGINNOTFOUND, SCIP_Real, SCIPallocBufferArray, SCIPblkmem(), SCIPcatchEvent(), SCIPcopyLargeNeighborhoodSearch(), SCIPcopyLimits(), SCIPdebug, SCIPdebugMsg, SCIPdropEvent(), SCIPerrorMessage, SCIPfindBranchrule(), SCIPfindConshdlr(), SCIPfindNodesel(), SCIPfreeBufferArray, SCIPgetLowerbound(), SCIPgetNBinVars(), SCIPgetNConss(), SCIPgetNIntVars(), SCIPgetNNodes(), SCIPgetNSols(), SCIPgetNVars(), SCIPgetSols(), SCIPgetUpperbound(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPincludeEventhdlrBasic(), SCIPisInfinity(), SCIPisParamFixed(), SCIPprintStatistics(), SCIPsetBoolParam(), SCIPsetCharParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetObjlimit(), SCIPsetPresolving(), SCIPsetSeparating(), SCIPsetSubscipsOff(), SCIPsolve(), SCIPsumepsilon(), SCIPtransformProb(), and TRUE.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 723 of file heur_dins.c.
References HEUR_NAME, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurDins().
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 737 of file heur_dins.c.
References SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), and SCIPheurSetData().
|
static |
solving process initialization method of primal heuristic (called when branch and bound process is about to begin)
Definition at line 758 of file heur_dins.c.
References SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPgetNBinVars(), SCIPheurGetData(), and TRUE.
|
static |
solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)
Definition at line 789 of file heur_dins.c.
References SCIP_OKAY, SCIPfreeBlockMemoryArray, and SCIPheurGetData().
|
static |
execution method of primal heuristic
Definition at line 810 of file heur_dins.c.
References determineVariableFixings(), MAX, SCIP_Bool, SCIP_CALL, SCIP_DELAYED, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcheckCopyLimits(), SCIPcreate(), SCIPfree(), SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetCutoffbound(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetNNodes(), SCIPgetNSols(), SCIPgetSolNodenum(), SCIPgetVarsData(), SCIPhasCurrentNodeLP(), SCIPheurGetData(), SCIPheurGetNBestSolsFound(), SCIPheurGetNCalls(), SCIPisGE(), SCIPisStopped(), and wrapperDins().