heur_vbounds.c
Go to the documentation of this file.
18 * @brief LNS heuristic uses the variable lower and upper bounds to determine the search neighborhood
25 * @todo allow smaller fixing rate after presolve if total number of variables is small (<= 1000)?
31 * Preliminary version available as <a href="https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/5551">ZIB-Report 15-26</a>.
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
74 #define HEUR_DESC "LNS heuristic uses the variable lower and upper bounds to determine the search neighborhood"
84 #define DEFAULT_MININTFIXINGRATE 0.65 /**< minimum percentage of integer variables that have to be fixed */
85 #define DEFAULT_MINMIPFIXINGRATE 0.65 /**< minimuskipobjm percentage of variables that have to be fixed within sub-SCIP
87 #define DEFAULT_MINIMPROVE 0.01 /**< factor by which vbounds heuristic should at least improve the
90 #define DEFAULT_NODESOFS 500LL /**< number of nodes added to the contingent of the total nodes */
91 #define DEFAULT_NODESQUOT 0.1 /**< subproblem nodes in relation to nodes of the original problem */
94 #define DEFAULT_COPYCUTS TRUE /**< should all active cuts from the cutpool of the original scip be copied to
96 #define DEFAULT_USELOCKFIXINGS FALSE /**< should more variables be fixed based on variable locks if
104 #define DEFAULT_TIGHTENVARIANT (VBOUNDVARIANT_NOOBJ | VBOUNDVARIANT_BESTBOUND | VBOUNDVARIANT_WORSTBOUND)
115 SCIP_BOUNDTYPE* vbbounds; /**< topological sorted variables with respect to the variable bounds */
121 SCIP_Real minintfixingrate; /**< minimum percentage of integer variables that have to be fixed */
122 SCIP_Real minmipfixingrate; /**< minimum percentage of variables that have to be fixed within sub-SCIP
124 SCIP_Real minimprove; /**< factor by which vbounds heuristic should at least improve the incumbent */
131 int tightenvariant; /**< which tightening variants of the vbounds heuristic should be called? */
144 * The heuristic works on indices representing a bound of a variable. This index will be called bound index in the
145 * following. For a given active variable with problem index i (note that active variables have problem indices
146 * between 0 and nactivevariable - 1), the bound index of its lower bound is 2*i, the bound index of its upper
147 * bound is 2*i + 1. The other way around, a given bound index i corresponds to the variable with problem index
149 * The following macros can be used to convert bound index into variable problem index and boundtype and vice versa.
177 /** performs depth-first-search in the implicitly given directed graph from the given start index */
264 idx = (SCIPisPositive(scip, coefs[i]) == lower) ? getLbIndex(SCIPvarGetProbindex(vbvars[i])) : getUbIndex(SCIPvarGetProbindex(vbvars[i]));
272 /* we stopped because we found an unhandled node and not because we reached the end of the list */
414 {
433 /* while there are unvisited nodes, run dfs on the inverse graph starting from one of these nodes; the dfs orders are
434 * stored in the topoorder array, later dfs calls are just appended after the stacks of previous dfs calls, which
441 SCIP_CALL( dfs(scip, i, visited, dfsstack, stacknextedge, stacknextcliquevar, cliqueexit, vbvars, nvbvars) );
552 SCIP_Bool* allobj1, /**< pointer to store whether all variables were fixed according to obj=1 scheme */
553 SCIP_Bool* allobj2, /**< pointer to store whether all variables were fixed according to obj=2 scheme */
587 * 1) tighten == TRUE: we go through the list of variables and fix variables to force propagation;
591 * 2) tighten == FALSE: we fix variables to avoid too much propagation in order to avoid reaching
598 /* if we want to take into account the objective function coefficients, we only perform a fixing if the variable
608 /* if we want to take into account the objective function coefficients but reverted, we only perform a fixing if the variable
636 v, SCIPvarGetName(var), SCIPvarGetObj(var), SCIPvarGetLbLocal(var), SCIPgetNPseudoBranchCands(scip));
655 v, SCIPvarGetName(var), SCIPvarGetObj(var), SCIPvarGetUbLocal(var), SCIPgetNPseudoBranchCands(scip));
687 /* because of the limited number of propagation rounds, it may happen that conflict analysis finds a valid
688 * global bound for the last fixed variable that conflicts with applying the reverse bound change after backtracking;
754 SCIP_CALL( SCIPcopyConsCompression(scip, subscip, varmap, NULL, "_vbounds", NULL, NULL, 0, FALSE, FALSE, FALSE,
802 if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
842 /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
843 * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
847 SCIPdebugMsg(scip, "vbounds heuristic presolved subproblem at time %g : %d vars, %d cons; fixing value = %g\n",
853 /* after presolving, we should have at least reached a certain fixing rate over ALL variables (including continuous)
858 SCIPdebugMsg(scip, "solving subproblem: nstallnodes=%" SCIP_LONGINT_FORMAT ", maxnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->maxnodes);
862 SCIPdebugMsg(scip, "ending solving vbounds-submip at time %g, status = %d\n", SCIPgetSolvingTime(scip), SCIPgetStatus(subscip));
864 /* check, whether a solution was found; due to numerics, it might happen that not all solutions are feasible ->
895 SCIP_Bool* skipobj1, /**< pointer to store whether the run with obj=1 can be skipped, or NULL */
896 SCIP_Bool* skipobj2, /**< pointer to store whether the run with obj=2 can be skipped, or NULL */
943 nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
944 nstallnodes -= 100 * SCIPheurGetNCalls(heur); /* count the setup costs for the sub-MIP as 100 nodes */
951 SCIPdebugMsg(scip, "apply variable bounds heuristic at node %lld on %d variable bounds, tighten: %u obj: %d\n",
957 SCIPdebugMsg(scip, "skipping " HEUR_NAME ": nstallnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->minnodes);
967 /* check whether the LP should be solved at the current node in the tree to determine whether the heuristic
976 /* manually cut off the node if the LP construction detected infeasibility (heuristics cannot return such a result) */
999 SCIP_CALL( applyVboundsFixings(scip, heurdata, vbvars, nvbvars, tighten, obj, &allobj1, &allobj2, &backtracked, &cutoff) );
1013 SCIPdebugMsg(scip, "npscands=%d, oldnpscands=%d, heurdata->minintfixingrate=%g\n", npscands, oldnpscands, heurdata->minintfixingrate);
1018 if( heurdata->uselockfixings && npscands <= 2.0 * oldnpscands * (1.0 - heurdata->minintfixingrate) )
1032 SCIPdebugMsg(scip, "after lockfixings: npscands=%d, oldnpscands=%d, allrowsfulfilled=%u, heurdata->minintfixingrate=%g\n",
1061 /* print message if relatively large LP is solved from scratch, since this could lead to a longer period during
1071 "Heuristic " HEUR_NAME " solving LP from scratch with %.1f %% unfixed columns (%d of %d) ...\n",
1078 /* solve LP; errors in the LP solver should not kill the overall solving process, if the LP is just needed for a
1079 * heuristic. hence in optimized mode, the return code is caught and a warning is printed, only in debug mode,
1089 SCIPwarningMessage(scip, "Error while solving LP in vbound heuristic; LP solve terminated with code <%d>\n",
1100 SCIPdebugMsg(scip, " -> new LP iterations: %" SCIP_LONGINT_FORMAT "\n", SCIPgetNLPIterations(scip));
1137 SCIPdebugMsg(scip, "found feasible solution by LP rounding: %16.9g\n", SCIPgetSolOrigObj(scip, sol));
1183 SCIPstatisticMessage("vbound: tighten=%u obj=%d nvars=%d presolnvars=%d ratio=%.2f infeas=%u found=%d time=%.4f\n",
1234 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
1311 SCIP_CALL( applyVbounds(scip, heur, heurdata, heurdata->vbvars, heurdata->nvbvars, FALSE, 1, NULL, NULL, result) );
1315 SCIP_CALL( applyVbounds(scip, heur, heurdata, heurdata->vbvars, heurdata->nvbvars, FALSE, 2, NULL, NULL, result) );
1327 SCIP_CALL( applyVbounds(scip, heur, heurdata, heurdata->vbvars, heurdata->nvbvars, TRUE, 1, NULL, NULL, result) );
1331 SCIP_CALL( applyVbounds(scip, heur, heurdata, heurdata->vbvars, heurdata->nvbvars, TRUE, 2, NULL, NULL, result) );
1379 "minimum percentage of variables that have to be fixed within sub-SCIP (integer and continuous)",
1419 "which variants of the vbounds heuristic that try to stay feasible should be called? (0: off, 1: w/o looking at obj, 2: only fix to best bound, 4: only fix to worst bound",
1423 "which tightening variants of the vbounds heuristic should be called? (0: off, 1: w/o looking at obj, 2: only fix to best bound, 4: only fix to worst bound",
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip_heur.c:233
Definition: type_result.h:33
Definition: type_result.h:47
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:949
public methods for SCIP parameter handling
public methods for branch and bound tree
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
Definition: scip_probing.c:216
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
Definition: scip_solvingstats.c:438
SCIP_RETCODE SCIPincludeHeurVbounds(SCIP *scip)
Definition: heur_vbounds.c:1355
Definition: struct_scip.h:59
public methods for memory management
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:117
public methods for implications, variable bounds, and cliques
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1587
internal methods for clocks and timing issues
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18273
public solving methods
public methods for timing
Definition: struct_var.h:198
static SCIP_RETCODE initializeCandsLists(SCIP *scip, SCIP_HEURDATA *heurdata)
Definition: heur_vbounds.c:462
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
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)
Definition: scip_param.c:102
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:3278
SCIP_RETCODE SCIPapplyLockFixings(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Bool *cutoff, SCIP_Bool *allrowsfulfilled)
Definition: heur_locks.c:187
static SCIP_RETCODE applyVboundsFixings(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **vars, int nvbvars, SCIP_Bool tighten, int obj, SCIP_Bool *allobj1, SCIP_Bool *allobj2, SCIP_Bool *backtracked, SCIP_Bool *infeasible)
Definition: heur_vbounds.c:550
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:923
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:288
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
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:292
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3201
Definition: type_message.h:46
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1362
Definition: type_lp.h:37
public methods for SCIP variables
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:111
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
public methods for querying solving statistics
Definition: struct_sol.h:64
public methods for the branch-and-bound tree
Definition: struct_misc.h:128
Definition: type_lp.h:40
SCIP_RETCODE SCIPcreateClock(SCIP *scip, SCIP_CLOCK **clck)
Definition: scip_timing.c:67
Definition: type_result.h:35
static SCIP_RETCODE topologicalSort(SCIP *scip, int *vbvars, int *nvbvars)
Definition: heur_vbounds.c:414
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:210
Definition: type_paramset.h:54
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:571
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
Definition: scip_probing.c:409
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:420
SCIP_RETCODE SCIPcopyCuts(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, int *ncutsadded)
Definition: scip_copy.c:2116
char * SCIPsnprintfProbingStats(SCIP *scip, char *strbuf, int len)
Definition: scip_probing.c:1035
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:241
Definition: type_retcode.h:33
public methods for problem copies
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:810
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:216
static SCIP_RETCODE setupAndSolveSubscip(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **vars, int nvars, SCIP_Longint nstallnodes, SCIP_Real lowerbound, int *nprevars, SCIP_Bool *wasfeas, SCIP_RESULT *result)
Definition: heur_vbounds.c:731
static SCIP_RETCODE dfs(SCIP *scip, int startnode, SCIP_Shortbool *visited, int *dfsstack, int *stacknextedge, int *stacknextcliquevar, int *cliqueexit, int *dfsnodes, int *ndfsnodes)
Definition: heur_vbounds.c:184
Definition: struct_heur.h:88
Definition: type_lp.h:34
public methods for primal heuristic plugins and divesets
public methods for constraint handler plugins and constraints
SCIP_RETCODE SCIPcopyConsCompression(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool global, SCIP_Bool enablepricing, SCIP_Bool threadsafe, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition: scip_copy.c:2951
public data structures and miscellaneous methods
SCIP_RETCODE SCIPcheckSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *feasible)
Definition: scip_sol.c:3440
static SCIP_DECL_HEUREXITSOL(heurExitsolVbounds)
Definition: heur_vbounds.c:1241
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
Definition: scip_sol.c:2446
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip_prob.c:1421
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:478
LNS heuristic uses the variable lower and upper bounds to determine the search neighborhood.
locks primal heuristic
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)
Definition: scip_sol.c:3125
public methods for the LP relaxation, rows and columns
public methods for branching rule plugins and branching
general public methods
public methods for solutions
Definition: type_lp.h:48
public methods for the probing mode
public methods for message output
Definition: struct_implics.h:66
public methods for message handling
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip_copy.c:3235
Definition: type_lp.h:35
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:102
public methods for primal heuristics
SCIPallocBlockMemory(scip, subsol))
Definition: type_paramset.h:53
Definition: objbenders.h:33
public methods for global and local (sub)problems
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:336
Definition: struct_clock.h:55
SCIP_RETCODE SCIPstartClock(SCIP *scip, SCIP_CLOCK *clck)
Definition: scip_timing.c:152
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
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:874
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:536
static SCIP_RETCODE applyVbounds(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_VAR **vbvars, int nvbvars, SCIP_Bool tighten, int obj, SCIP_Bool *skipobj1, SCIP_Bool *skipobj2, SCIP_RESULT *result)
Definition: heur_vbounds.c:892
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_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:319
memory allocation routines
Definition: type_var.h:58