Detailed Description
LNS heuristic that finds the optimal rounding to a given point.
Definition in file heur_rens.c.
#include "blockmemshell/memory.h"
#include "nlpi/type_nlpi.h"
#include "scip/heuristics.h"
#include "scip/heur_rens.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_nlp.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_timing.h"
#include "scip/scip_var.h"
#include <string.h>
Go to the source code of this file.
Macros | |
#define | HEUR_NAME "rens" |
#define | HEUR_DESC "LNS exploring fractional neighborhood of relaxation's optimum" |
#define | HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
#define | HEUR_PRIORITY -1100000 |
#define | HEUR_FREQ 0 |
#define | HEUR_FREQOFS 0 |
#define | HEUR_MAXDEPTH -1 |
#define | HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE |
#define | HEUR_USESSUBSCIP TRUE |
#define | DEFAULT_BINARYBOUNDS TRUE /* should general integers get binary bounds [floor(.),ceil(.)] ? */ |
#define | DEFAULT_MAXNODES 5000LL /* maximum number of nodes to regard in the subproblem */ |
#define | DEFAULT_MINFIXINGRATE 0.5 /* minimum percentage of integer variables that have to be fixed */ |
#define | DEFAULT_MINIMPROVE 0.01 /* factor by which RENS should at least improve the incumbent */ |
#define | DEFAULT_MINNODES 50LL /* minimum number of nodes to regard in the subproblem */ |
#define | DEFAULT_NODESOFS 500LL /* number of nodes added to the contingent of the total nodes */ |
#define | DEFAULT_NODESQUOT 0.1 /* 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_STARTSOL 'l' /* solution that is used for fixing values */ |
#define | STARTSOL_CHOICES "nl" /* possible values for startsol ('l'p relaxation, 'n'lp relaxation) */ |
#define | DEFAULT_USELPROWS |
#define | DEFAULT_COPYCUTS |
#define | DEFAULT_EXTRATIME |
#define | DEFAULT_ADDALLSOLS FALSE /* should all subproblem solutions be added to the original SCIP? */ |
#define | DEFAULT_FULLSCALE |
#define | DEFAULT_BESTSOLLIMIT -1 /* 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 "Rens" |
#define | EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" |
Functions | |
static SCIP_RETCODE | computeFixingrate (SCIP *scip, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int *nfixedvars, int fixedvarssize, SCIP_Real minfixingrate, char *startsol, SCIP_Real *fixingrate, SCIP_Bool *success) |
static SCIP_RETCODE | restrictToBinaryBounds (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, char startsol) |
static | SCIP_DECL_EVENTEXEC (eventExecRens) |
static SCIP_RETCODE | setupAndSolveSubscip (SCIP *scip, SCIP *subscip, SCIP_RESULT *result, SCIP_HEUR *heur, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Real intfixingrate, SCIP_Real minfixingrate, SCIP_Real minimprove, SCIP_Longint maxnodes, SCIP_Longint nstallnodes, char startsol, SCIP_Bool binarybounds, SCIP_Bool uselprows) |
SCIP_RETCODE | SCIPapplyRens (SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Real minfixingrate, SCIP_Real minimprove, SCIP_Longint maxnodes, SCIP_Longint nstallnodes, char startsol, SCIP_Bool binarybounds, SCIP_Bool uselprows) |
static | SCIP_DECL_HEURCOPY (heurCopyRens) |
static | SCIP_DECL_HEURFREE (heurFreeRens) |
static | SCIP_DECL_HEURINIT (heurInitRens) |
static | SCIP_DECL_HEUREXEC (heurExecRens) |
SCIP_RETCODE | SCIPincludeHeurRens (SCIP *scip) |
Macro Definition Documentation
◆ HEUR_NAME
#define HEUR_NAME "rens" |
Definition at line 56 of file heur_rens.c.
Referenced by SCIP_DECL_HEURCOPY(), SCIPincludeHeurRens(), and setupAndSolveSubscip().
◆ HEUR_DESC
#define HEUR_DESC "LNS exploring fractional neighborhood of relaxation's optimum" |
Definition at line 57 of file heur_rens.c.
Referenced by SCIPincludeHeurRens().
◆ HEUR_DISPCHAR
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
Definition at line 58 of file heur_rens.c.
Referenced by SCIPincludeHeurRens().
◆ HEUR_PRIORITY
#define HEUR_PRIORITY -1100000 |
Definition at line 59 of file heur_rens.c.
Referenced by SCIPincludeHeurRens().
◆ HEUR_FREQ
#define HEUR_FREQ 0 |
Definition at line 60 of file heur_rens.c.
Referenced by SCIPincludeHeurRens().
◆ HEUR_FREQOFS
#define HEUR_FREQOFS 0 |
Definition at line 61 of file heur_rens.c.
Referenced by SCIPincludeHeurRens().
◆ HEUR_MAXDEPTH
#define HEUR_MAXDEPTH -1 |
Definition at line 62 of file heur_rens.c.
Referenced by SCIPincludeHeurRens().
◆ HEUR_TIMING
#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE |
Definition at line 63 of file heur_rens.c.
Referenced by SCIPincludeHeurRens().
◆ HEUR_USESSUBSCIP
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 64 of file heur_rens.c.
Referenced by SCIPincludeHeurRens().
◆ DEFAULT_BINARYBOUNDS
#define DEFAULT_BINARYBOUNDS TRUE /* should general integers get binary bounds [floor(.),ceil(.)] ? */ |
Definition at line 67 of file heur_rens.c.
Referenced by SCIPincludeHeurRens().
◆ DEFAULT_MAXNODES
#define DEFAULT_MAXNODES 5000LL /* maximum number of nodes to regard in the subproblem */ |
Definition at line 68 of file heur_rens.c.
Referenced by SCIPincludeHeurRens().
◆ DEFAULT_MINFIXINGRATE
#define DEFAULT_MINFIXINGRATE 0.5 /* minimum percentage of integer variables that have to be fixed */ |
Definition at line 69 of file heur_rens.c.
Referenced by SCIPincludeHeurRens().
◆ DEFAULT_MINIMPROVE
#define DEFAULT_MINIMPROVE 0.01 /* factor by which RENS should at least improve the incumbent */ |
Definition at line 70 of file heur_rens.c.
Referenced by SCIPincludeHeurRens().
◆ DEFAULT_MINNODES
#define DEFAULT_MINNODES 50LL /* minimum number of nodes to regard in the subproblem */ |
Definition at line 71 of file heur_rens.c.
Referenced by SCIPincludeHeurRens().
◆ DEFAULT_NODESOFS
#define DEFAULT_NODESOFS 500LL /* number of nodes added to the contingent of the total nodes */ |
Definition at line 72 of file heur_rens.c.
Referenced by SCIPincludeHeurRens().
◆ DEFAULT_NODESQUOT
#define DEFAULT_NODESQUOT 0.1 /* subproblem nodes in relation to nodes of the original problem */ |
Definition at line 73 of file heur_rens.c.
Referenced by SCIPincludeHeurRens().
◆ 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 74 of file heur_rens.c.
Referenced by SCIPincludeHeurRens().
◆ DEFAULT_STARTSOL
#define DEFAULT_STARTSOL 'l' /* solution that is used for fixing values */ |
Definition at line 75 of file heur_rens.c.
Referenced by SCIPincludeHeurRens().
◆ STARTSOL_CHOICES
#define STARTSOL_CHOICES "nl" /* possible values for startsol ('l'p relaxation, 'n'lp relaxation) */ |
Definition at line 76 of file heur_rens.c.
Referenced by SCIPincludeHeurRens().
◆ DEFAULT_USELPROWS
#define DEFAULT_USELPROWS |
Definition at line 77 of file heur_rens.c.
Referenced by SCIPincludeHeurRens().
◆ DEFAULT_COPYCUTS
#define DEFAULT_COPYCUTS |
Definition at line 79 of file heur_rens.c.
Referenced by SCIPincludeHeurRens().
◆ DEFAULT_EXTRATIME
#define DEFAULT_EXTRATIME |
Definition at line 82 of file heur_rens.c.
Referenced by SCIPincludeHeurRens().
◆ DEFAULT_ADDALLSOLS
#define DEFAULT_ADDALLSOLS FALSE /* should all subproblem solutions be added to the original SCIP? */ |
Definition at line 85 of file heur_rens.c.
Referenced by SCIPincludeHeurRens().
◆ DEFAULT_FULLSCALE
#define DEFAULT_FULLSCALE |
Definition at line 87 of file heur_rens.c.
Referenced by SCIPincludeHeurRens().
◆ DEFAULT_BESTSOLLIMIT
#define DEFAULT_BESTSOLLIMIT -1 /* limit on number of improving incumbent solutions in sub-CIP */ |
Definition at line 91 of file heur_rens.c.
Referenced by SCIPincludeHeurRens().
◆ DEFAULT_USEUCT
#define DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */ |
Definition at line 92 of file heur_rens.c.
Referenced by SCIPincludeHeurRens().
◆ EVENTHDLR_NAME
#define EVENTHDLR_NAME "Rens" |
Definition at line 95 of file heur_rens.c.
Referenced by SCIP_DECL_EVENTEXEC(), and setupAndSolveSubscip().
◆ EVENTHDLR_DESC
#define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" |
Definition at line 96 of file heur_rens.c.
Referenced by setupAndSolveSubscip().
Function Documentation
◆ computeFixingrate()
|
static |
compute the number of initial fixings and check whether the fixing rate exceeds the minimum fixing rate
- Parameters
-
scip SCIP data structure fixedvars array to store source SCIP variables whose copies should be fixed in the sub-SCIP fixedvals array to store solution values for variable fixing nfixedvars pointer to store the number of fixed variables fixedvarssize size of the arrays to store fixing variables minfixingrate percentage of integer variables that have to be fixed startsol pointer to solution used for fixing values ('l'p relaxation, 'n'lp relaxation) fixingrate percentage of integers that get actually fixed success pointer to store whether minimum fixingrate is exceeded
Definition at line 136 of file heur_rens.c.
References FALSE, MAX, NULL, SCIP_CALL, SCIP_NLPPAR_VERBLEVEL, SCIP_NLPSOLSTAT_FEASIBLE, SCIP_NLPSOLSTAT_GLOBOPT, SCIP_NLPSOLSTAT_LOCOPT, SCIP_OKAY, SCIP_Real, SCIPdebug, SCIPdebugMsg, SCIPfloor(), SCIPgetNLPIntPar(), SCIPgetNLPSolstat(), SCIPgetVarsData(), SCIPisFeasIntegral(), SCIPisNLPConstructed(), SCIPsetNLPInitialGuessSol(), SCIPsetNLPIntPar(), SCIPsolveNLP(), SCIPvarGetLPSol(), SCIPvarGetNLPSol(), and TRUE.
Referenced by SCIPapplyRens().
◆ restrictToBinaryBounds()
|
static |
fixes bounds of unfixed integer variables to binary bounds
- Parameters
-
scip original SCIP data structure subscip SCIP data structure for the subproblem subvars the variables of the subproblem startsol solution used for fixing values ('l'p relaxation, 'n'lp relaxation)
Definition at line 249 of file heur_rens.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPchgVarLbGlobal(), SCIPchgVarUbGlobal(), SCIPfeasCeil(), SCIPfeasFloor(), SCIPfloor(), SCIPgetVarsData(), SCIPisFeasEQ(), SCIPisFeasIntegral(), SCIPvarGetLbGlobal(), SCIPvarGetLPSol(), SCIPvarGetNLPSol(), and SCIPvarGetUbGlobal().
Referenced by setupAndSolveSubscip().
◆ SCIP_DECL_EVENTEXEC()
|
static |
Definition at line 316 of file heur_rens.c.
References EVENTHDLR_NAME, NULL, SCIP_CALL, SCIP_EVENTTYPE_LPSOLVED, SCIP_OKAY, SCIPdebugMsg, SCIPeventGetType(), SCIPeventhdlrGetName(), SCIPgetNLPs(), and SCIPinterruptSolve().
◆ setupAndSolveSubscip()
|
static |
setup and solve the RENS sub-SCIP
- Parameters
-
scip SCIP data structure subscip sub SCIP data structure result result pointer heur heuristic data structure fixedvars array of variables that should be fixed fixedvals array of fixing values nfixedvars number of variables that should be fixed intfixingrate percentage of integer variables fixed minfixingrate minimum percentage of integer variables that have to be fixed minimprove factor by which RENS should at least improve the incumbent maxnodes maximum number of nodes for the subproblem nstallnodes number of stalling nodes for the subproblem startsol solution used for fixing values ('l'p relaxation, 'n'lp relaxation) binarybounds should general integers get binary bounds [floor(.),ceil(.)]? uselprows should subproblem be created out of the rows in the LP rows?
Definition at line 341 of file heur_rens.c.
References EVENTHDLR_DESC, EVENTHDLR_NAME, FALSE, HEUR_NAME, MAX, NULL, restrictToBinaryBounds(), SCIP_Bool, SCIP_CALL, SCIP_EVENTTYPE_LPSOLVED, SCIP_FOUNDSOL, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIP_PLUGINNOTFOUND, SCIP_Real, SCIPABORT, SCIPallocBufferArray, SCIPblkmem(), SCIPcatchEvent(), SCIPcopyLargeNeighborhoodSearch(), SCIPcopyLimits(), SCIPdebug, SCIPdebugMsg, SCIPdropEvent(), SCIPerrorMessage, SCIPfindBranchrule(), SCIPfindConshdlr(), SCIPfindNodesel(), SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetLowerbound(), SCIPgetNConss(), SCIPgetNNodes(), SCIPgetNOrigVars(), SCIPgetNSols(), SCIPgetNVars(), SCIPgetPrimalbound(), SCIPgetSols(), SCIPgetSolvingTime(), SCIPgetUpperbound(), SCIPgetVarsData(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPheurGetData(), SCIPincludeEventhdlrBasic(), SCIPinfinity(), SCIPisInfinity(), SCIPisParamFixed(), SCIPmergeVariableStatistics(), SCIPpresolve(), SCIPprintStatistics(), SCIPsetBoolParam(), SCIPsetCharParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetObjlimit(), SCIPsetPresolving(), SCIPsetSeparating(), SCIPsetSubscipsOff(), SCIPsolGetNodenum(), SCIPsolve(), SCIPstatisticPrintf, SCIPsumepsilon(), SCIPtransformProb(), SCIPtranslateSubSol(), SCIPtrySolFree(), SCIPwarningMessage(), and TRUE.
Referenced by SCIPapplyRens().
◆ SCIP_DECL_HEURCOPY()
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 701 of file heur_rens.c.
References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurRens().
◆ SCIP_DECL_HEURFREE()
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 715 of file heur_rens.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 735 of file heur_rens.c.
References NULL, SCIP_OKAY, and SCIPheurGetData().
◆ SCIP_DECL_HEUREXEC()
|
static |
execution method of primal heuristic
Definition at line 755 of file heur_rens.c.
References NULL, SCIP_CALL, SCIP_DELAYED, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIPapplyRens(), SCIPdebugMsg, SCIPgetCutoffbound(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetNLPBranchCands(), SCIPgetNNlpis(), SCIPgetNNodes(), SCIPhasCurrentNodeLP(), SCIPheurGetData(), SCIPheurGetNBestSolsFound(), SCIPheurGetNCalls(), SCIPisGE(), and SCIPisStopped().