Detailed Description
DINS primal heuristic (according to Ghosh)
Definition in file heur_dins.c.
#include "blockmemshell/memory.h"
#include "scip/cons_linear.h"
#include "scip/heur_dins.h"
#include "scip/heuristics.h"
#include "scip/pub_event.h"
#include "scip/pub_heur.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_cons.h"
#include "scip/scip_copy.h"
#include "scip/scip_event.h"
#include "scip/scip_general.h"
#include "scip/scip_heur.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_nodesel.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_sol.h"
#include "scip/scip_solve.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_var.h"
#include <string.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 SCIP_HEURDISPCHAR_LNS |
#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_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) |
Macro Definition Documentation
◆ HEUR_NAME
#define HEUR_NAME "dins" |
Definition at line 53 of file heur_dins.c.
Referenced by SCIP_DECL_HEURCOPY(), SCIPincludeHeurDins(), and wrapperDins().
◆ HEUR_DESC
#define HEUR_DESC "distance induced neighborhood search by Ghosh" |
Definition at line 54 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
◆ HEUR_DISPCHAR
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
Definition at line 55 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
◆ HEUR_PRIORITY
#define HEUR_PRIORITY -1105000 |
Definition at line 56 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
◆ HEUR_FREQ
#define HEUR_FREQ -1 |
Definition at line 57 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
◆ HEUR_FREQOFS
#define HEUR_FREQOFS 0 |
Definition at line 58 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
◆ HEUR_MAXDEPTH
#define HEUR_MAXDEPTH -1 |
Definition at line 59 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
◆ HEUR_TIMING
#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE |
Definition at line 60 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
◆ HEUR_USESSUBSCIP
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 61 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
◆ DEFAULT_NODESOFS
#define DEFAULT_NODESOFS 5000LL /* number of nodes added to the contingent of the total nodes */ |
Definition at line 63 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
◆ DEFAULT_MAXNODES
#define DEFAULT_MAXNODES 5000LL /* maximum number of nodes to regard in the subproblem */ |
Definition at line 64 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
◆ DEFAULT_MINNODES
#define DEFAULT_MINNODES 50LL /* minimum number of nodes to regard in the subproblem */ |
Definition at line 65 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
◆ DEFAULT_MINIMPROVE
#define DEFAULT_MINIMPROVE 0.01 /* factor by which DINS should at least improve the incumbent */ |
Definition at line 66 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
◆ DEFAULT_NODESQUOT
#define DEFAULT_NODESQUOT 0.05 /* subproblem nodes in relation to nodes of the original problem */ |
Definition at line 67 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
◆ DEFAULT_LPLIMFAC
#define DEFAULT_LPLIMFAC 1.5 /* factor by which the limit on the number of LP depends on the node limit */ |
Definition at line 68 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
◆ DEFAULT_MINFIXINGRATE
#define DEFAULT_MINFIXINGRATE 0.3 /* minimum percentage of integer variables that have to be fixed */ |
Definition at line 69 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
◆ DEFAULT_NWAITINGNODES
#define DEFAULT_NWAITINGNODES 200LL /* number of nodes without incumbent change that heuristic should wait */ |
Definition at line 70 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
◆ DEFAULT_NEIGHBORHOODSIZE
#define DEFAULT_NEIGHBORHOODSIZE 18 /* radius of the incumbents neighborhood to be searched */ |
Definition at line 71 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
◆ DEFAULT_SOLNUM
#define DEFAULT_SOLNUM 5 /* number of pool-solutions to be checked for flag array update */ |
Definition at line 72 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
◆ DEFAULT_USELPROWS
#define DEFAULT_USELPROWS |
Definition at line 73 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
◆ DEFAULT_COPYCUTS
#define DEFAULT_COPYCUTS |
Definition at line 75 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
◆ DEFAULT_BESTSOLLIMIT
#define DEFAULT_BESTSOLLIMIT 3 /* limit on number of improving incumbent solutions in sub-CIP */ |
Definition at line 78 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
◆ DEFAULT_USEUCT
#define DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */ |
Definition at line 79 of file heur_dins.c.
Referenced by SCIPincludeHeurDins().
◆ EVENTHDLR_NAME
#define EVENTHDLR_NAME "Dins" |
Definition at line 83 of file heur_dins.c.
Referenced by SCIP_DECL_EVENTEXEC(), and wrapperDins().
◆ EVENTHDLR_DESC
#define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" |
Definition at line 84 of file heur_dins.c.
Referenced by wrapperDins().
Function Documentation
◆ computeIntegerVariableBounds()
|
static |
compute tightened bounds for integer variables depending on how much the LP and the incumbent solution values differ
- Parameters
-
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 123 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().
◆ determineVariableFixings()
|
static |
creates a subproblem for subscip by fixing a number of variables
- Parameters
-
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 197 of file heur_dins.c.
References computeIntegerVariableBounds(), NULL, 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().
◆ reboundIntegerVariables()
|
static |
creates a subproblem for subscip by fixing a number of variables
- Parameters
-
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 327 of file heur_dins.c.
References computeIntegerVariableBounds(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPchgVarLbGlobal(), SCIPchgVarUbGlobal(), SCIPisFeasEQ(), SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().
Referenced by wrapperDins().
◆ addLocalBranchingConstraint()
|
static |
create the extra constraint of local branching and add it to subscip
- Parameters
-
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 365 of file heur_dins.c.
References FALSE, NULL, SCIP_CALL, SCIP_DECL_EVENTEXEC(), 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().
◆ SCIP_DECL_EVENTEXEC()
|
static |
Definition at line 672 of file heur_dins.c.
References EVENTHDLR_NAME, NULL, SCIP_CALL, SCIP_EVENTTYPE_LPSOLVED, SCIP_OKAY, SCIPdebugMsg, SCIPeventGetType(), SCIPeventhdlrGetName(), SCIPgetNLPs(), and SCIPinterruptSolve().
Referenced by addLocalBranchingConstraint().
◆ wrapperDins()
|
static |
wrapper for the part of heuristic that runs a subscip. Wrapper is needed to avoid possible ressource leaks
- Parameters
-
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 447 of file heur_dins.c.
References addLocalBranchingConstraint(), EVENTHDLR_DESC, EVENTHDLR_NAME, FALSE, HEUR_NAME, MAX, NULL, 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(), SCIPgetUpperbound(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPincludeEventhdlrBasic(), SCIPisInfinity(), SCIPisParamFixed(), SCIPprintStatistics(), SCIPsetBoolParam(), SCIPsetCharParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetObjlimit(), SCIPsetPresolving(), SCIPsetSeparating(), SCIPsetSubscipsOff(), SCIPsolve(), SCIPsumepsilon(), SCIPtransformProb(), SCIPtranslateSubSols(), and TRUE.
Referenced by SCIP_DECL_HEUREXEC().
◆ SCIP_DECL_HEURCOPY()
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 702 of file heur_dins.c.
References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurDins().
◆ SCIP_DECL_HEURFREE()
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 716 of file heur_dins.c.
References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), and SCIPheurSetData().
◆ SCIP_DECL_HEURINITSOL()
|
static |
solving process initialization method of primal heuristic (called when branch and bound process is about to begin)
Definition at line 737 of file heur_dins.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPgetNBinVars(), SCIPheurGetData(), and TRUE.
◆ SCIP_DECL_HEUREXITSOL()
|
static |
solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)
Definition at line 768 of file heur_dins.c.
References NULL, SCIP_OKAY, SCIPfreeBlockMemoryArray, and SCIPheurGetData().
◆ SCIP_DECL_HEUREXEC()
|
static |
execution method of primal heuristic
Definition at line 789 of file heur_dins.c.
References determineVariableFixings(), MAX, NULL, 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().