heur_trustregion.c
Go to the documentation of this file.
18 * @brief Large neighborhood search heuristic for Benders' decomposition based on trust region methods
21 * The Trust Region heuristic draws upon trust region methods for solving optimization problems, especially in the
22 * context of Benders' decomposition. This heuristic has been developed to improve the heuristic performance of the
25 * The Trust Region heuristic copies the original SCIP instance and adds a constraint to penalize changes from the
26 * incumbent solution. Consider a problem that includes a set of binary variables \f$\mathcal{B}\f$. Given a feasible
27 * solution \f$\hat{x}\f$ to the original problem, we define the set \f$\mathcal{B}^{+}\f$ as the index set for the
28 * binary variables that are 1 in the input solution and \f$\mathcal{B}^{-}\f$ as the index set for binary variables
35 * The variable \f$\theta\f$ measure the distance, in terms of the binary variables, of candidate solutions to the input
38 * In addition, an upper bounding constraint is explicitly added to enforce a minimum improvement from the heuristic,
39 * given by \f$f(x) \le f(\hat{x}) - \epsilon\f$. The parameter \f$\epsilon \ge 0\f$ denotes the minimum improvement
42 * The objective function is then modified to \f$f(x) + M\theta\f$, where \f$M\f$ is a parameter for penalizing the
45 * If a new incumbent solution is found by this heuristic, then the Trust Region heuristic is immediately
49 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
89 #define DEFAULT_MINBINVARS 10 /**< the minimum number of binary variables necessary to run the heuristic */
93 #define DEFAULT_NODESQUOT 0.05 /**< contingent of sub problem nodes in relation to original nodes */
94 #define DEFAULT_LPLIMFAC 1.5 /**< factor by which the limit on the number of LP depends on the node limit */
95 #define DEFAULT_NWAITINGNODES 1 /**< number of nodes without incumbent change that heuristic should wait */
96 #define DEFAULT_USELPROWS FALSE /**< should subproblem be created out of the rows in the LP rows,
98 #define DEFAULT_COPYCUTS TRUE /**< if DEFAULT_USELPROWS is FALSE, then should all active cuts from the cutpool
100 #define DEFAULT_BESTSOLLIMIT 3 /**< limit on number of improving incumbent solutions in sub-CIP */
103 #define DEFAULT_OBJMINIMPROVE 1e-2 /**< the minimum absolute improvement in the objective function value */
124 SCIP_Real nodelimit; /**< the nodelimit employed in the current sub-SCIP, for the event handler*/
125 SCIP_Real lplimfac; /**< factor by which the limit on the number of LP depends on the node limit */
127 SCIP_Real objminimprove; /**< the minimum absolute improvement in the objective function value */
170 SCIP_CALL( SCIPaddTrustregionNeighborhoodConstraint(scip, subscip, subvars, heurdata->violpenalty) );
182 /* create the upper bounding constraint. An absolute minimum improvement is used for this heuristic. This is
183 * different to other LNS heuristics, where a relative improvement is used. The absolute improvement tries to take
184 * into account problem specific information that is available to the user, such as a minimum step in the objective
300 /* with a little abuse we initialize the heurdata as if trustregion would have finished its last step regularly */
345 SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapfw, "trustregion", NULL, NULL, 0, heurdata->uselprows,
359 SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecTrustregion, NULL) );
377 SCIP_CALL( SCIPsetCommonSubscipParams(scip, subscip, nsubnodes, MAX(10, nsubnodes/10), heurdata->bestsollimit) );
387 SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) );
391 SCIPdebugMsg(scip, "solving trust region subproblem with maxnodes %" SCIP_LONGINT_FORMAT "\n", nsubnodes);
396 * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
405 SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) );
412 SCIPdebugMsg(scip, "trust region used %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT " nodes\n",
423 if( SCIPgetStatus(subscip) == SCIP_STATUS_NODELIMIT || SCIPgetStatus(subscip) == SCIP_STATUS_STALLNODELIMIT
485 if( SCIPsolGetHeur(bestsol) != NULL && strcmp(SCIPheurGetName(SCIPsolGetHeur(bestsol)), "trivial") == 0 )
492 * In this case, the trust region heuristic is designed for Benders' decomposition and solutions found may not be
493 * added by this heuristic but by trysol. So we don't reward finding best solutions, but finding any solution. */
494 maxnnodes = (SCIP_Longint)(maxnnodes * (1.0 + 2.0*(SCIPheurGetNSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur)+1.0)));
495 maxnnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-MIP as 100 nodes */
548 /* if the result is FOUNDSOL, this means that a solution was found during a previous execution of the heuristic.
567 )
621 "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
Definition: type_result.h:33
Definition: type_result.h:47
Large neighborhood search heuristic for Benders' decomposition based on trust region methods...
Definition: type_result.h:34
public methods for SCIP parameter handling
Definition: struct_scip.h:59
public methods for node selector plugins
public methods for memory management
static SCIP_DECL_EVENTEXEC(eventExecTrustregion)
Definition: heur_trustregion.c:226
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:95
Definition: struct_var.h:198
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1865
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:315
methods commonly used by primal heuristics
public methods for problem variables
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:108
SCIP_RETCODE SCIPtranslateSubSols(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_Bool *success, int *solindex)
Definition: scip_copy.c:1439
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3201
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1362
public methods for SCIP variables
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:74
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
Definition: scip_solvingstats.c:4127
public methods for numerical tolerances
Definition: type_stat.h:35
public methods for querying solving statistics
Definition: struct_sol.h:64
Definition: struct_misc.h:128
Definition: type_stat.h:36
Definition: type_result.h:35
Definition: struct_cons.h:37
SCIP_RETCODE SCIPaddTrustregionNeighborhoodConstraint(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR **subvars, SCIP_Real violpenalty)
Definition: heuristics.c:990
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
public methods for event handler plugins and event handlers
SCIP_Real SCIPgetSolTransObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1482
Definition: type_retcode.h:33
public methods for problem copies
public methods for primal CIP solutions
SCIP_RETCODE SCIPincludeHeurTrustregion(SCIP *scip)
Definition: heur_trustregion.c:567
Definition: struct_heur.h:88
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:3319
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:277
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:478
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:311
Constraint handler for linear constraints in their most general form, .
Definition: type_stat.h:39
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:17840
public methods for branching rule plugins and branching
public methods for managing events
general public methods
public methods for solutions
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
public methods for message output
static SCIP_RETCODE setupAndSolveSubscipTrustregion(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_Longint nsubnodes, SCIP_RESULT *result)
Definition: heur_trustregion.c:313
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:185
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:916
static SCIP_RETCODE addTrustRegionConstraints(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEURDATA *heurdata)
Definition: heur_trustregion.c:150
public methods for message handling
Definition: type_retcode.h:45
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip_copy.c:3235
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
public methods for primal heuristics
SCIPallocBlockMemory(scip, subsol))
Definition: objbenders.h:33
public methods for global and local (sub)problems
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:130
Definition: struct_event.h:195
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:48
SCIP_Longint SCIPgetSolNodenum(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1648
memory allocation routines