Detailed Description
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) |
Macro Definition Documentation
◆ HEUR_NAME
#define HEUR_NAME "rins" |
Definition at line 51 of file heur_rins.c.
Referenced by SCIP_DECL_HEURCOPY(), SCIPincludeHeurRins(), and wrapperRins().
◆ HEUR_DESC
#define HEUR_DESC "relaxation induced neighborhood search by Danna, Rothberg, and Le Pape" |
Definition at line 52 of file heur_rins.c.
Referenced by SCIPincludeHeurRins().
◆ HEUR_DISPCHAR
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
Definition at line 53 of file heur_rins.c.
Referenced by SCIPincludeHeurRins().
◆ HEUR_PRIORITY
#define HEUR_PRIORITY -1101000 |
Definition at line 54 of file heur_rins.c.
Referenced by SCIPincludeHeurRins().
◆ HEUR_FREQ
#define HEUR_FREQ 25 |
Definition at line 55 of file heur_rins.c.
Referenced by SCIPincludeHeurRins().
◆ HEUR_FREQOFS
#define HEUR_FREQOFS 0 |
Definition at line 56 of file heur_rins.c.
Referenced by SCIPincludeHeurRins().
◆ HEUR_MAXDEPTH
#define HEUR_MAXDEPTH -1 |
Definition at line 57 of file heur_rins.c.
Referenced by SCIPincludeHeurRins().
◆ HEUR_TIMING
#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE |
Definition at line 58 of file heur_rins.c.
Referenced by SCIPincludeHeurRins().
◆ HEUR_USESSUBSCIP
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 59 of file heur_rins.c.
Referenced by SCIPincludeHeurRins().
◆ DEFAULT_NODESOFS
#define DEFAULT_NODESOFS 500 /* number of nodes added to the contingent of the total nodes */ |
Definition at line 61 of file heur_rins.c.
Referenced by SCIPincludeHeurRins().
◆ DEFAULT_MAXNODES
#define DEFAULT_MAXNODES 5000 /* maximum number of nodes to regard in the subproblem */ |
Definition at line 62 of file heur_rins.c.
Referenced by SCIPincludeHeurRins().
◆ DEFAULT_MINNODES
#define DEFAULT_MINNODES 50 /* minimum number of nodes to regard in the subproblem */ |
Definition at line 63 of file heur_rins.c.
Referenced by SCIPincludeHeurRins().
◆ DEFAULT_MINIMPROVE
#define DEFAULT_MINIMPROVE 0.01 /* factor by which RINS should at least improve the incumbent */ |
Definition at line 64 of file heur_rins.c.
Referenced by SCIPincludeHeurRins().
◆ DEFAULT_MINFIXINGRATE
#define DEFAULT_MINFIXINGRATE 0.3 /* minimum percentage of integer variables that have to be fixed */ |
Definition at line 65 of file heur_rins.c.
Referenced by SCIPincludeHeurRins().
◆ DEFAULT_NODESQUOT
#define DEFAULT_NODESQUOT 0.3 /* subproblem nodes in relation to nodes of the original problem */ |
Definition at line 66 of file heur_rins.c.
Referenced by SCIPincludeHeurRins().
◆ DEFAULT_LPLIMFAC
#define DEFAULT_LPLIMFAC 2.0 /* factor by which the limit on the number of LP depends on the node limit */ |
Definition at line 67 of file heur_rins.c.
Referenced by SCIPincludeHeurRins().
◆ DEFAULT_NWAITINGNODES
#define DEFAULT_NWAITINGNODES 200 /* number of nodes without incumbent change that heuristic should wait */ |
Definition at line 68 of file heur_rins.c.
Referenced by SCIPincludeHeurRins().
◆ DEFAULT_USELPROWS
#define DEFAULT_USELPROWS |
Definition at line 69 of file heur_rins.c.
Referenced by SCIPincludeHeurRins().
◆ DEFAULT_COPYCUTS
#define DEFAULT_COPYCUTS |
Definition at line 71 of file heur_rins.c.
Referenced by SCIPincludeHeurRins().
◆ DEFAULT_USEUCT
#define DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */ |
Definition at line 74 of file heur_rins.c.
Referenced by SCIPincludeHeurRins().
◆ EVENTHDLR_NAME
#define EVENTHDLR_NAME "Rins" |
Definition at line 77 of file heur_rins.c.
Referenced by SCIP_DECL_EVENTEXEC(), and wrapperRins().
◆ EVENTHDLR_DESC
#define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" |
Definition at line 78 of file heur_rins.c.
Referenced by wrapperRins().
Function Documentation
◆ determineFixings()
|
static |
determines variable fixings for RINS
RINS fixes variables with matching solution values in the current LP and the incumbent solution
- Parameters
-
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 117 of file heur_rins.c.
References FALSE, MAX, NULL, SCIP_CALL, SCIP_DECL_EVENTEXEC(), SCIP_OKAY, SCIP_Real, SCIPgetBestSol(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPisFeasEQ(), SCIPvarGetLPSol(), and TRUE.
Referenced by SCIP_DECL_HEUREXEC().
◆ SCIP_DECL_EVENTEXEC()
|
static |
Definition at line 376 of file heur_rins.c.
References EVENTHDLR_NAME, NULL, SCIP_CALL, SCIP_EVENTTYPE_LPSOLVED, SCIP_OKAY, SCIPdebugMsg, SCIPeventGetType(), SCIPeventhdlrGetName(), SCIPgetNLPs(), and SCIPinterruptSolve().
Referenced by determineFixings().
◆ wrapperRins()
|
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 nfixedvars Number of fixed variables nnodes Number of nodes in the b&b tree
Definition at line 197 of file heur_rins.c.
References EVENTHDLR_DESC, EVENTHDLR_NAME, FALSE, HEUR_NAME, MAX, nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIP_EVENTTYPE_LPSOLVED, SCIP_FOUNDSOL, 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(), SCIPfindConshdlr(), 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(), 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 406 of file heur_rins.c.
References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurRins().
◆ SCIP_DECL_HEURFREE()
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 420 of file heur_rins.c.
References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), and SCIPheurSetData().
◆ SCIP_DECL_HEURINIT()
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 441 of file heur_rins.c.
References NULL, SCIP_OKAY, and SCIPheurGetData().
◆ SCIP_DECL_HEUREXEC()
|
static |
execution method of primal heuristic
Definition at line 461 of file heur_rins.c.
References determineFixings(), FALSE, nnodes, NULL, 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(), and wrapperRins().