heur_localbranching.c
Go to the documentation of this file.
32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
74 #define DEFAULT_MINIMPROVE 0.01 /* factor by which localbranching should at least improve the incumbent */
76 #define DEFAULT_NODESQUOT 0.05 /* contingent of sub problem nodes in relation to original nodes */
77 #define DEFAULT_LPLIMFAC 1.5 /* factor by which the limit on the number of LP depends on the node limit */
78 #define DEFAULT_NWAITINGNODES 200 /* number of nodes without incumbent change that heuristic should wait */
81 #define DEFAULT_COPYCUTS TRUE /* if DEFAULT_USELPROWS is FALSE, then should all active cuts from the cutpool
108 SCIP_Real minimprove; /**< factor by which localbranching should at least improve the incumbent */
109 SCIP_Real nodelimit; /**< the nodelimit employed in the current sub-SCIP, for the event handler*/
110 SCIP_Real lplimfac; /**< factor by which the limit on the number of LP depends on the node limit */
217 cutoff = (1-heurdata->minimprove)*SCIPgetUpperbound(scip) + heurdata->minimprove*SCIPgetLowerbound(scip);
317 /* with a little abuse we initialize the heurdata as if localbranching would have finished its last step regularly */
364 SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapfw, "localbranching", NULL, NULL, 0, heurdata->uselprows,
378 SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecLocalbranching, NULL) );
396 SCIP_CALL( SCIPsetCommonSubscipParams(scip, subscip, nsubnodes, MAX(10, nsubnodes/10), heurdata->bestsollimit) );
407 SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) );
411 SCIPdebugMsg(scip, "solving local branching subproblem with neighborhoodsize %d and maxnodes %" SCIP_LONGINT_FORMAT "\n",
415 * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
424 SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) );
431 SCIPdebugMsg(scip, "local branching used %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT " nodes\n",
445 heurdata->callstatus = WAITFORNEWSOL; /* new solution will immediately be installed at next call */
453 heurdata->curneighborhoodsize = (heurdata->emptyneighborhoodsize + heurdata->curneighborhoodsize)/2;
455 SCIPdebugMsg(scip, " -> node limit reached: reduced neighborhood to %d, increased minnodes to %d\n",
460 SCIPdebugMsg(scip, " -> new neighborhood was already proven to be empty: wait for new solution\n");
468 heurdata->curneighborhoodsize = MAX(heurdata->curneighborhoodsize, heurdata->emptyneighborhoodsize + 2);
470 SCIPdebugMsg(scip, " -> neighborhood is empty: increased neighborhood to %d\n", heurdata->curneighborhoodsize);
484 SCIPdebugMsg(scip, " -> unexpected sub-MIP status <%d>: waiting for new solution\n", SCIPgetStatus(subscip));
543 if( SCIPsolGetHeur(bestsol) != NULL && strcmp(SCIPheurGetName(SCIPsolGetHeur(bestsol)), "trivial") == 0 )
566 maxnnodes = (SCIP_Longint)(maxnnodes * (1.0 + 2.0*(SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur)+1.0)));
567 maxnnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-MIP as 100 nodes */
667 "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
Definition: type_result.h:42
Definition: type_result.h:56
Definition: type_result.h:43
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:782
public methods for SCIP parameter handling
Definition: struct_scip.h:68
public methods for node selector plugins
public methods for memory management
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1596
public solving methods
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:104
Definition: struct_var.h:207
Definition: type_stat.h:64
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1874
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3023
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:324
Definition: type_var.h:62
methods commonly used by primal heuristics
static SCIP_DECL_HEURINIT(heurInitLocalbranching)
Definition: heur_localbranching.c:306
public methods for problem variables
SCIP_RETCODE SCIPincludeHeurLocalbranching(SCIP *scip)
Definition: heur_localbranching.c:607
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)
Definition: scip_heur.c:117
Definition: type_stat.h:52
SCIP_RETCODE SCIPtranslateSubSols(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_Bool *success, int *solindex)
Definition: scip_copy.c:1448
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3210
static SCIP_DECL_HEUREXEC(heurExecLocalbranching)
Definition: heur_localbranching.c:498
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1371
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)
Definition: scip_param.c:83
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
Definition: scip_solvingstats.c:4136
Definition: type_stat.h:43
public methods for numerical tolerances
Definition: type_stat.h:44
public methods for querying solving statistics
Definition: struct_sol.h:73
Definition: struct_misc.h:137
Definition: type_stat.h:45
Definition: type_result.h:44
Definition: struct_cons.h:46
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:178
public methods for event handler plugins and event handlers
Definition: type_stat.h:61
static SCIP_RETCODE setupAndSolveSubscipLocalbranching(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_Longint nsubnodes, SCIP_RESULT *result)
Definition: heur_localbranching.c:330
Local branching heuristic according to Fischetti and Lodi.
Definition: type_retcode.h:42
Definition: type_stat.h:42
public methods for problem copies
public methods for primal CIP solutions
Definition: struct_heur.h:97
public methods for primal heuristic plugins and divesets
public methods for constraint handler plugins and constraints
SCIP_RETCODE SCIPsetCommonSubscipParams(SCIP *sourcescip, SCIP *subscip, SCIP_Longint nsubnodes, SCIP_Longint nstallnodes, int bestsollimit)
Definition: scip_copy.c:3328
public data structures and miscellaneous methods
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:286
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip_prob.c:1430
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:320
Constraint handler for linear constraints in their most general form, .
static SCIP_DECL_HEURFREE(heurFreeLocalbranching)
Definition: heur_localbranching.c:285
Definition: type_stat.h:48
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_linear.c:17851
public methods for branching rule plugins and branching
public methods for managing events
general public methods
Definition: type_stat.h:65
static SCIP_DECL_EVENTEXEC(eventExecLocalbranching)
Definition: heur_localbranching.c:241
Definition: type_stat.h:53
Definition: type_stat.h:54
public methods for solutions
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1119
public methods for message output
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:194
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)
Definition: heuristics.c:925
public methods for message handling
Definition: type_retcode.h:54
static SCIP_RETCODE addLocalbranchingConstraintAndObjcutoff(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **subvars)
Definition: heur_localbranching.c:131
static SCIP_DECL_HEURCOPY(heurCopyLocalbranching)
Definition: heur_localbranching.c:271
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip_copy.c:3244
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:162
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:883
public methods for primal heuristics
Definition: objbenders.h:43
public methods for global and local (sub)problems
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1361
Definition: type_stat.h:62
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)
Definition: scip_param.c:139
Definition: type_stat.h:57
Definition: struct_event.h:204
Definition: type_stat.h:51
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)
Definition: scip_param.c:57
Definition: type_stat.h:60
SCIP_Longint SCIPgetSolNodenum(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1657
Definition: type_stat.h:63
memory allocation routines