66#define HEUR_NAME "proximity"
67#define HEUR_DESC "heuristic trying to improve the incumbent by an auxiliary proximity objective function"
68#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
69#define HEUR_PRIORITY -2000000
72#define HEUR_MAXDEPTH -1
73#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
74#define HEUR_USESSUBSCIP TRUE
77#define EVENTHDLR_NAME "Proximity"
78#define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic"
82#define DEFAULT_MAXNODES 10000LL
83#define DEFAULT_MINIMPROVE 0.02
84#define DEFAULT_MINGAP 0.01
85#define DEFAULT_MINNODES 1LL
86#define DEFAULT_MINLPITERS 200LL
87#define DEFAULT_MAXLPITERS 100000LL
88#define DEFAULT_NODESOFS 50LL
89#define DEFAULT_WAITINGNODES 100LL
90#define DEFAULT_NODESQUOT 0.1
91#define DEFAULT_USELPROWS FALSE
92#define DEFAULT_BINVARQUOT 0.1
93#define DEFAULT_RESTART TRUE
94#define DEFAULT_USEFINALLP FALSE
95#define DEFAULT_LPITERSQUOT 0.2
96#define DEFAULT_USEUCT FALSE
105 SCIP_Longint maxnodes;
106 SCIP_Longint minnodes;
107 SCIP_Longint maxlpiters;
108 SCIP_Longint nusedlpiters;
109 SCIP_Longint minlpiters;
110 SCIP_Longint nodesofs;
112 SCIP_Longint waitingnodes;
113 SCIP_Real lpitersquot;
114 SCIP_Real minimprove;
117 SCIP_Real binvarquot;
130 SCIP_Bool usefinallp;
173 for( v = 0; v <
nvars; ++v )
233 SCIP_Bool usefinallp,
258 if( subvars[
i] ==
NULL )
278 for( v =
nvars - 1; v >=
nvars - ncontvars; --v )
302 for( v =
nvars - 1; v >=
nvars - ncontvars; --v )
585 SCIPdebugMsg(
scip,
"skipping proximity: pure feasibility problem anyway\n");
595 SCIP_Longint nusednodes = 0
LL;
596 SCIP_Longint nusedlpiters = 0
LL;
609 heurdata->nusedlpiters += nusedlpiters;
671 SCIP_Real minimprove,
674 SCIP_Longint* nusednodes,
675 SCIP_Longint* nusedlpiters,
695 SCIP_Real lowerbound;
711 assert(0.0 <= minimprove && minimprove <= 1.0);
736 if(
heurdata->lastsolidx == solidx )
823 if( eventhdlr ==
NULL )
850 if( subvars[
i] ==
NULL )
908 if( subvars[
i] ==
NULL )
968 "Presolving Time: %.2f\n",
heurdata->subprobidx,
977 if( nusednodes !=
NULL )
979 if( nusedlpiters !=
NULL )
1044 "should subproblem be constructed based on LP row information?",
1048 "should the heuristic immediately run again on its newly found solution?",
1052 "should the heuristic solve a final LP in case of continuous objective variables?",
1056 "maximum number of nodes to regard in the subproblem",
1060 "number of nodes added to the contingent of the total nodes",
1064 "minimum number of nodes required to start the subproblem",
1068 "maximum number of LP iterations to be performed in the subproblem",
1072 "minimum number of LP iterations performed in subproblem",
1076 "waiting nodes since last incumbent before heuristic is executed",
1080 "factor by which proximity should at least improve the incumbent",
1084 "sub-MIP node limit w.r.t number of original nodes",
1088 "threshold for percentage of binary variables required to start",
1092 "quotient of sub-MIP LP iterations with respect to LP iterations so far",
1096 "minimum primal-dual gap for which the heuristic is executed",
1100 "should uct node selection be used at the beginning of the search?",
Constraint handler for linear constraints in their most general form, .
#define SCIP_CALL_ABORT(x)
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPchgRhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreate(SCIP **scip)
int SCIPgetNObjVars(SCIP *scip)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
int SCIPgetNVars(SCIP *scip)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetObjNorm(SCIP *scip)
int SCIPgetNFixedVars(SCIP *scip)
int SCIPgetNBinVars(SCIP *scip)
SCIP_Bool SCIPisObjIntegral(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 SCIPdeleteSubproblemProximity(SCIP *scip)
SCIP_RETCODE SCIPapplyProximity(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Real minimprove, SCIP_Longint nnodes, SCIP_Longint nlpiters, SCIP_Longint *nusednodes, SCIP_Longint *nusedlpiters, SCIP_Bool freesubscip)
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 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 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 SCIPincludeHeurProximity(SCIP *scip)
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
SCIP_EVENTHDLR * SCIPfindEventhdlr(SCIP *scip, const char *name)
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_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur,)
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur,)
const char * SCIPheurGetName(SCIP_HEUR *heur)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
SCIP_RETCODE SCIPchgVarLbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_RETCODE SCIPchgVarUbDive(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_RETCODE SCIPstartDive(SCIP *scip)
SCIP_RETCODE SCIPsolveDiveLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
SCIP_Bool SCIPisLPConstructed(SCIP *scip)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
SCIP_Longint SCIPsolGetNodenum(SCIP_SOL *sol)
int SCIPgetNSols(SCIP *scip)
SCIP_HEUR * SCIPsolGetHeur(SCIP_SOL *sol)
SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
int SCIPsolGetIndex(SCIP_SOL *sol)
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
SCIP_RETCODE SCIPtrySol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
SCIP_RETCODE SCIPpresolve(SCIP *scip)
SCIP_RETCODE SCIPfreeTransform(SCIP *scip)
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
SCIP_RETCODE SCIPsolve(SCIP *scip)
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
SCIP_Real SCIPgetPrimalbound(SCIP *scip)
SCIP_Real SCIPgetGap(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Longint SCIPgetNRootLPIterations(SCIP *scip)
SCIP_Longint SCIPgetNRootFirstLPIterations(SCIP *scip)
SCIP_Longint SCIPgetNLPIterations(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 SCIPgetPresolvingTime(SCIP *scip)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPchgVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_RETCODE SCIPchgVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
SCIPfreeSol(scip, &heurdata->sol))
SCIPcreateSol(scip, &heurdata->sol, heur))
assert(minobj< SCIPgetCutoffbound(scip))
SCIPlinkLPSol(scip, sol))
static SCIP_RETCODE solveLp(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
#define DEFAULT_NODESQUOT
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_Bool usefinallp, SCIP_Bool *success)
#define DEFAULT_BINVARQUOT
#define DEFAULT_USEFINALLP
static SCIP_RETCODE setupSubproblem(SCIP_HEURDATA *heurdata, SCIP *subscip)
#define DEFAULT_WAITINGNODES
static SCIP_RETCODE deleteSubproblem(SCIP *scip, SCIP_HEURDATA *heurdata)
#define DEFAULT_MINIMPROVE
#define DEFAULT_USELPROWS
#define DEFAULT_LPITERSQUOT
#define DEFAULT_MAXLPITERS
#define DEFAULT_MINLPITERS
improvement heuristic which uses an auxiliary objective instead of the original objective function wh...
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 SCIPstatisticMessage
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 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_EventData SCIP_EVENTDATA
#define SCIP_DECL_EVENTEXEC(x)
#define SCIP_EVENTTYPE_NODESOLVED
#define SCIP_DECL_HEURCOPY(x)
struct SCIP_HeurData SCIP_HEURDATA
#define SCIP_DECL_HEURINIT(x)
#define SCIP_DECL_HEURFREE(x)
#define SCIP_DECL_HEUREXITSOL(x)
#define SCIP_DECL_HEUREXEC(x)
@ SCIP_LPSOLSTAT_ITERLIMIT
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE