LNS heuristic that combines the incumbent with the LP optimum.
Definition in file heur_rins.c.
#include "blockmemshell/memory.h"
#include "scip/heuristics.h"
#include "scip/heur_rins.h"
#include "scip/pub_event.h"
#include "scip/pub_heur.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_sol.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 <string.h>
Go to the source code of this file.
Macros | |
#define | HEUR_NAME "rins" |
#define | HEUR_DESC "relaxation induced neighborhood search by Danna, Rothberg, and Le Pape" |
#define | HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
#define | HEUR_PRIORITY -1101000 |
#define | HEUR_FREQ 25 |
#define | HEUR_FREQOFS 0 |
#define | HEUR_MAXDEPTH -1 |
#define | HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE |
#define | HEUR_USESSUBSCIP TRUE |
#define | DEFAULT_NODESOFS 500 /* number of nodes added to the contingent of the total nodes */ |
#define | DEFAULT_MAXNODES 5000 /* maximum number of nodes to regard in the subproblem */ |
#define | DEFAULT_MINNODES 50 /* minimum number of nodes to regard in the subproblem */ |
#define | DEFAULT_MINIMPROVE 0.01 /* factor by which RINS should at least improve the incumbent */ |
#define | DEFAULT_MINFIXINGRATE 0.3 /* minimum percentage of integer variables that have to be fixed */ |
#define | DEFAULT_NODESQUOT 0.3 /* subproblem nodes in relation to nodes of the original problem */ |
#define | DEFAULT_LPLIMFAC 2.0 /* factor by which the limit on the number of LP depends on the node limit */ |
#define | DEFAULT_NWAITINGNODES 200 /* number of nodes without incumbent change that heuristic should wait */ |
#define | DEFAULT_USELPROWS |
#define | DEFAULT_COPYCUTS |
#define | DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */ |
#define | EVENTHDLR_NAME "Rins" |
#define | EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" |
Functions | |
static SCIP_RETCODE | determineFixings (SCIP *scip, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int *nfixedvars, int fixedvarssize, SCIP_Real minfixingrate, SCIP_Bool *success) |
static | SCIP_DECL_EVENTEXEC (eventExecRins) |
static SCIP_RETCODE | wrapperRins (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 nfixedvars, SCIP_Longint nnodes) |
static | SCIP_DECL_HEURCOPY (heurCopyRins) |
static | SCIP_DECL_HEURFREE (heurFreeRins) |
static | SCIP_DECL_HEURINIT (heurInitRins) |
static | SCIP_DECL_HEUREXEC (heurExecRins) |
SCIP_RETCODE | SCIPincludeHeurRins (SCIP *scip) |
#define HEUR_NAME "rins" |
Definition at line 60 of file heur_rins.c.
#define HEUR_DESC "relaxation induced neighborhood search by Danna, Rothberg, and Le Pape" |
Definition at line 61 of file heur_rins.c.
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
Definition at line 62 of file heur_rins.c.
#define HEUR_PRIORITY -1101000 |
Definition at line 63 of file heur_rins.c.
#define HEUR_FREQ 25 |
Definition at line 64 of file heur_rins.c.
#define HEUR_FREQOFS 0 |
Definition at line 65 of file heur_rins.c.
#define HEUR_MAXDEPTH -1 |
Definition at line 66 of file heur_rins.c.
#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE |
Definition at line 67 of file heur_rins.c.
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 68 of file heur_rins.c.
#define DEFAULT_NODESOFS 500 /* number of nodes added to the contingent of the total nodes */ |
Definition at line 70 of file heur_rins.c.
#define DEFAULT_MAXNODES 5000 /* maximum number of nodes to regard in the subproblem */ |
Definition at line 71 of file heur_rins.c.
#define DEFAULT_MINNODES 50 /* minimum number of nodes to regard in the subproblem */ |
Definition at line 72 of file heur_rins.c.
#define DEFAULT_MINIMPROVE 0.01 /* factor by which RINS should at least improve the incumbent */ |
Definition at line 73 of file heur_rins.c.
#define DEFAULT_MINFIXINGRATE 0.3 /* minimum percentage of integer variables that have to be fixed */ |
Definition at line 74 of file heur_rins.c.
#define DEFAULT_NODESQUOT 0.3 /* subproblem nodes in relation to nodes of the original problem */ |
Definition at line 75 of file heur_rins.c.
#define DEFAULT_LPLIMFAC 2.0 /* factor by which the limit on the number of LP depends on the node limit */ |
Definition at line 76 of file heur_rins.c.
#define DEFAULT_NWAITINGNODES 200 /* number of nodes without incumbent change that heuristic should wait */ |
Definition at line 77 of file heur_rins.c.
#define DEFAULT_USELPROWS |
Definition at line 78 of file heur_rins.c.
#define DEFAULT_COPYCUTS |
Definition at line 79 of file heur_rins.c.
#define DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */ |
Definition at line 80 of file heur_rins.c.
#define EVENTHDLR_NAME "Rins" |
Definition at line 83 of file heur_rins.c.
#define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" |
Definition at line 84 of file heur_rins.c.
|
static |
determines variable fixings for RINS
RINS fixes variables with matching solution values in the current LP and the incumbent solution
scip | original SCIP data structure |
fixedvars | array to store source SCIP variables that should be fixed in the copy |
fixedvals | array to store fixing values for variables that should be fixed in the copy |
nfixedvars | pointer to store the number of variables that RINS can fix |
fixedvarssize | size of the buffer arrays to store potential fixings |
minfixingrate | percentage of integer variables that have to be fixed |
success | pointer to store whether sufficiently many variable fixings were found |
Definition at line 123 of file heur_rins.c.
References assert(), FALSE, i, MAX, nbinvars, nintvars, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetBestSol(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPisFeasEQ(), SCIPvarGetLPSol(), TRUE, and vars.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
Definition at line 371 of file heur_rins.c.
References assert(), EVENTHDLR_NAME, heurdata, NULL, SCIP_CALL, SCIP_EVENTTYPE_LPSOLVED, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIPdebugMsg, SCIPeventGetType(), SCIPeventhdlrGetName(), SCIPgetNLPs(), and SCIPinterruptSolve().
|
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 |
nfixedvars | Number of fixed variables |
nnodes | Number of nodes in the b&b tree |
Definition at line 203 of file heur_rins.c.
References assert(), cutoff, EVENTHDLR_DESC, EVENTHDLR_NAME, FALSE, HEUR_NAME, heurdata, i, MAX, MIN, nnodes, NULL, nvars, result, SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIP_EVENTTYPE_LPSOLVED, SCIP_FOUNDSOL, SCIP_Longint, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIP_PLUGINNOTFOUND, SCIP_Real, SCIP_VERBLEVEL_FULL, SCIP_VERBLEVEL_NONE, SCIPallocBufferArray, SCIPblkmem(), SCIPcatchEvent(), SCIPcopyLargeNeighborhoodSearch(), SCIPcopyLimits(), SCIPdebug, SCIPdropEvent(), SCIPerrorMessage, SCIPfindBranchrule(), SCIPfindNodesel(), SCIPfreeBufferArray, SCIPgetLowerbound(), SCIPgetNNodes(), SCIPgetUpperbound(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPincludeEventhdlrBasic(), SCIPisInfinity(), SCIPisParamFixed(), SCIPmergeVariableStatistics(), SCIPprintStatistics(), SCIPsetBoolParam(), SCIPsetCharParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetObjlimit(), SCIPsetPresolving(), SCIPsetSeparating(), SCIPsetSubscipsOff(), SCIPsolve(), SCIPsumepsilon(), SCIPtransformProb(), SCIPtranslateSubSols(), TRUE, and vars.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 401 of file heur_rins.c.
References assert(), HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurRins().
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 415 of file heur_rins.c.
References assert(), heurdata, NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), and SCIPheurSetData().
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 436 of file heur_rins.c.
References assert(), heurdata, NULL, SCIP_OKAY, and SCIPheurGetData().
|
static |
execution method of primal heuristic
Definition at line 456 of file heur_rins.c.
References assert(), determineFixings(), FALSE, heurdata, MIN, nbinvars, nintvars, nnodes, NULL, nvars, result, SCIP_Bool, SCIP_CALL, SCIP_DELAYED, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcheckCopyLimits(), SCIPcreate(), SCIPdebugMsg, SCIPfree(), SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetCutoffbound(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetNNodes(), SCIPgetNSols(), SCIPgetSolNodenum(), SCIPgetVarsData(), SCIPhasCurrentNodeLP(), SCIPheurGetData(), SCIPheurGetNBestSolsFound(), SCIPheurGetNCalls(), SCIPisGE(), SCIPisStopped(), SCIPsolIsOriginal(), vars, and wrapperRins().