65#define HEUR_NAME "rens"
66#define HEUR_DESC "LNS exploring fractional neighborhood of relaxation's optimum"
67#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
68#define HEUR_PRIORITY -1100000
71#define HEUR_MAXDEPTH -1
72#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE
73#define HEUR_USESSUBSCIP TRUE
76#define DEFAULT_BINARYBOUNDS TRUE
77#define DEFAULT_MAXNODES 5000LL
78#define DEFAULT_MINFIXINGRATE 0.5
79#define DEFAULT_MINIMPROVE 0.01
80#define DEFAULT_MINNODES 50LL
81#define DEFAULT_NODESOFS 500LL
82#define DEFAULT_NODESQUOT 0.1
83#define DEFAULT_LPLIMFAC 2.0
84#define DEFAULT_STARTSOL 'l'
85#define STARTSOL_CHOICES "nl"
86#define DEFAULT_USELPROWS FALSE
88#define DEFAULT_COPYCUTS TRUE
91#define DEFAULT_EXTRATIME FALSE
94#define DEFAULT_ADDALLSOLS FALSE
96#define DEFAULT_FULLSCALE FALSE
100#define DEFAULT_BESTSOLLIMIT -1
101#define DEFAULT_USEUCT FALSE
104#define EVENTHDLR_NAME "Rens"
105#define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic"
182 if( (*startsol) ==
'n' )
189 SCIPdebugMsg(
scip,
"try to solve NLP relaxation to obtain fixing values\n");
202 SCIPdebugMsg(
scip,
"solving NLP relaxation was %s successful (stat=%d)\n", *success ?
"" :
"not", stat);
228 fixedvars[(*nfixedvars)] =
vars[
i];
229 fixedvals[(*nfixedvars)] = solval;
243 if( *fixingrate < minfixingrate )
269 assert(startsol ==
'l' || startsol ==
'n');
281 if( subvars[
i] ==
NULL )
395 if( eventhdlr ==
NULL )
517 SCIPwarningMessage(
scip,
"Error while presolving subproblem in RENS heuristic; sub-SCIP terminated with code <%d>\n", retcode);
527 allfixingrate =
MAX(allfixingrate, 0.0);
532 if( allfixingrate >= minfixingrate / 2.0 )
554 SCIPwarningMessage(
scip,
"Error while solving subproblem in RENS heuristic; sub-SCIP terminated with code <%d>\n", retcode);
573 for(
i = 0;
i < nsubsols && (!success ||
heurdata->addallsols); ++
i )
590 SCIPstatisticPrintf(
"RENS statistic: fixed only %6.3f integer variables, %6.3f all variables --> abort \n", intfixingrate, allfixingrate);
637 assert(0.0 <= minfixingrate && minfixingrate <= 1.0);
638 assert(0.0 <= minimprove && minimprove <= 1.0);
639 assert(startsol ==
'l' || startsol ==
'n');
657 SCIPstatisticPrintf(
"RENS statistic: fixed only %5.2f integer variables --> abort \n", intfixingrate);
672 retcode =
setupAndSolveSubscip(
scip, subscip,
result, heur, fixedvars, fixedvals, nfixedvars, intfixingrate, minfixingrate, minimprove, maxnodes, nstallnodes, startsol, binarybounds, uselprows);
795 nstallnodes =
MIN(nstallnodes,
heurdata->maxnodes);
798 if( nstallnodes < heurdata->minnodes )
844 "minimum percentage of integer variables that have to be fixable",
848 "maximum number of nodes to regard in the subproblem",
852 "number of nodes added to the contingent of the total nodes",
856 "minimum number of nodes required to start the subproblem",
860 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
864 "factor by which RENS should at least improve the incumbent",
868 "factor by which the limit on the number of LP depends on the node limit",
872 "solution that is used for fixing values ('l'p relaxation, 'n'lp relaxation)",
876 "should general integers get binary bounds [floor(.),ceil(.)] ?",
880 "should subproblem be created out of the rows in the LP rows?",
884 "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
888 "should the RENS sub-CIP get its own full time limit? This is only for testing and not recommended!",
892 "should all subproblem solutions be added to the original SCIP?",
896 "should the RENS sub-CIP be solved with cuts, conflicts, strong branching,... This is only for testing and not recommended!",
900 "limit on number of improving incumbent solutions in sub-CIP",
904 "should uct node selection be used at the beginning of the search?",
#define SCIP_LONGINT_FORMAT
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
SCIP_RETCODE SCIPmergeVariableStatistics(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR **sourcevars, SCIP_VAR **targetvars, int nvars)
SCIP_RETCODE SCIPtranslateSubSol(SCIP *scip, SCIP *subscip, SCIP_SOL *subsol, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_SOL **newsol)
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreate(SCIP **scip)
int SCIPgetNIntVars(SCIP *scip)
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
int SCIPgetNVars(SCIP *scip)
int SCIPgetNConss(SCIP *scip)
int SCIPgetNOrigVars(SCIP *scip)
int SCIPgetNBinVars(SCIP *scip)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
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)
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
SCIP_RETCODE SCIPsetCharParam(SCIP *scip, const char *name, char value)
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
SCIP_RETCODE SCIPincludeHeurRens(SCIP *scip)
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
int SCIPgetNLPBranchCands(SCIP *scip)
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur,)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur,)
const char * SCIPheurGetName(SCIP_HEUR *heur)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
SCIP_Real SCIPgetLPObjval(SCIP *scip)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
int SCIPgetNNlpis(SCIP *scip)
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
SCIP_NLPSOLSTAT SCIPgetNLPSolstat(SCIP *scip)
#define SCIPsolveNLP(...)
SCIP_RETCODE SCIPsetNLPInitialGuessSol(SCIP *scip, SCIP_SOL *sol)
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
SCIP_Longint SCIPsolGetNodenum(SCIP_SOL *sol)
int SCIPgetNSols(SCIP *scip)
SCIP_SOL ** SCIPgetSols(SCIP *scip)
SCIP_RETCODE SCIPtrySolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
SCIP_RETCODE SCIPpresolve(SCIP *scip)
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
SCIP_RETCODE SCIPsolve(SCIP *scip)
SCIP_Real SCIPgetPrimalbound(SCIP *scip)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_RETCODE SCIPcopyLargeNeighborhoodSearch(SCIP *sourcescip, SCIP *subscip, SCIP_HASHMAP *varmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool uselprows, SCIP_Bool copycuts, SCIP_Bool *success, SCIP_Bool *valid)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPchgVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
SCIP_RETCODE SCIPchgVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_Real SCIPvarGetNLPSol(SCIP_VAR *var)
#define DEFAULT_NODESQUOT
#define DEFAULT_MINIMPROVE
#define DEFAULT_ADDALLSOLS
#define DEFAULT_MINFIXINGRATE
#define DEFAULT_USELPROWS
#define DEFAULT_BESTSOLLIMIT
assert(minobj< SCIPgetCutoffbound(scip))
#define DEFAULT_FULLSCALE
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)
#define DEFAULT_BINARYBOUNDS
#define DEFAULT_EXTRATIME
static SCIP_RETCODE restrictToBinaryBounds(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, char startsol)
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)
LNS heuristic that finds the optimal rounding to a given point.
methods commonly used by primal heuristics
memory allocation routines
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
public methods for managing events
public methods for primal heuristics
public methods for message output
#define SCIPstatisticPrintf
public data structures and miscellaneous methods
public methods for primal CIP solutions
public methods for problem variables
public methods for branching rule plugins and branching
public methods for constraint handler plugins and constraints
public methods for problem copies
public methods for event handler plugins and event handlers
public methods for primal heuristic plugins and divesets
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for nonlinear relaxation
public methods for NLPI solver interfaces
public methods for node selector plugins
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for solutions
public methods for querying solving statistics
public methods for timing
public methods for SCIP variables
struct SCIP_Eventhdlr SCIP_EVENTHDLR
struct SCIP_EventData SCIP_EVENTDATA
#define SCIP_DECL_EVENTEXEC(x)
#define SCIP_EVENTTYPE_LPSOLVED
#define SCIP_DECL_HEURCOPY(x)
struct SCIP_HeurData SCIP_HEURDATA
struct SCIP_Heur SCIP_HEUR
#define SCIP_DECL_HEURINIT(x)
#define SCIP_DECL_HEURFREE(x)
#define SCIP_DECL_HEUREXEC(x)
struct SCIP_HashMap SCIP_HASHMAP
enum SCIP_NlpSolStat SCIP_NLPSOLSTAT
@ SCIP_NLPSOLSTAT_FEASIBLE
@ SCIP_NLPSOLSTAT_GLOBOPT
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE