78#define VBOUNDVARIANT_NOOBJ 0x001u
79#define VBOUNDVARIANT_BESTBOUND 0x002u
80#define VBOUNDVARIANT_WORSTBOUND 0x004u
82#define HEUR_NAME "vbounds"
83#define HEUR_DESC "LNS heuristic uses the variable lower and upper bounds to determine the search neighborhood"
84#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_PROP
85#define HEUR_PRIORITY 2500
88#define HEUR_MAXDEPTH -1
89#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE
90#define HEUR_USESSUBSCIP TRUE
92#define DEFAULT_MAXNODES 5000LL
93#define DEFAULT_MININTFIXINGRATE 0.65
94#define DEFAULT_MINMIPFIXINGRATE 0.65
96#define DEFAULT_MINIMPROVE 0.01
98#define DEFAULT_MINNODES 500LL
99#define DEFAULT_NODESOFS 500LL
100#define DEFAULT_NODESQUOT 0.1
101#define DEFAULT_MAXPROPROUNDS 2
102#define DEFAULT_MAXBACKTRACKS 10
103#define DEFAULT_COPYCUTS TRUE
105#define DEFAULT_USELOCKFIXINGS FALSE
110#define DEFAULT_FEASVARIANT (VBOUNDVARIANT_BESTBOUND | VBOUNDVARIANT_WORSTBOUND)
113#define DEFAULT_TIGHTENVARIANT (VBOUNDVARIANT_NOOBJ | VBOUNDVARIANT_BESTBOUND | VBOUNDVARIANT_WORSTBOUND)
126 SCIP_Longint maxnodes;
127 SCIP_Longint minnodes;
128 SCIP_Longint nodesofs;
130 SCIP_Real minintfixingrate;
131 SCIP_Real minmipfixingrate;
133 SCIP_Real minimprove;
135 SCIP_Real cutoffbound;
141 SCIP_Bool initialized;
142 SCIP_Bool applicable;
145 SCIP_Bool uselockfixings;
160#define getLbIndex(idx) (2*(idx))
161#define getUbIndex(idx) (2*(idx)+1)
162#define getVarIndex(idx) ((idx)/2)
163#define getBoundtype(idx) (((idx) % 2 == 0) ? SCIP_BOUNDTYPE_LOWER : SCIP_BOUNDTYPE_UPPER)
164#define isIndexLowerbound(idx) ((idx) % 2 == 0)
165#define getOtherBoundIndex(idx) (((idx) % 2 == 0) ? (idx) + 1 : (idx) - 1)
238 while( stacksize > 0 )
360 if( idx >= 0 && !
visited[idx] )
396 maxstacksize =
MAX(maxstacksize, stacksize);
445 for(
i = 0;
i < nbounds; ++
i )
452 assert(*nvbvars <= nbounds);
502 for( v = 0; v <
nvbs; ++v )
524 SCIP_Real upperbound;
525 SCIP_Real minimprove;
526 SCIP_Real cutoffbound;
544 heurdata->cutoffbound =
MIN(upperbound, cutoffbound);
563 SCIP_Bool* infeasible
576 for( v = 0; v < nvbvars && !(*infeasible); ++v )
643 SCIPdebugMsg(
scip,
"fixing %d: variable <%s> (obj=%g) to lower bound <%g> (%d pseudo cands)\n",
662 SCIPdebugMsg(
scip,
"fixing %d: variable <%s> (obj=%g) to upper bound <%g> (%d pseudo cands)\n",
710 SCIPdebugMessage(
"backtrack %d was %sfeasible\n", nbacktracks, (*infeasible ?
"in" :
""));
715 SCIPdebugMsg(
scip,
"probing was infeasible after %d backtracks\n", nbacktracks);
719 else if( nbacktracks >
heurdata->maxbacktracks )
741 SCIP_Real lowerbound,
762 SCIP_CALL(
SCIPcopyConsCompression(
scip, subscip, varmap,
NULL,
"_vbounds",
NULL,
NULL, 0,
FALSE,
FALSE,
FALSE,
818 SCIP_Real upperbound;
819 SCIP_Real minimprove;
820 SCIP_Real cutoffbound;
838 heurdata->cutoffbound =
MIN(upperbound, cutoffbound);
855 SCIPdebugMsg(
scip,
"vbounds heuristic presolved subproblem at time %g : %d vars, %d cons; fixing value = %g\n",
912 SCIP_Real lowerbound;
959 SCIPdebugMsg(
scip,
"apply variable bounds heuristic at node %lld on %d variable bounds, tighten: %u obj: %d\n",
1002#ifdef COLLECTSTATISTICS
1040 SCIPdebugMsg(
scip,
"after lockfixings: npscands=%d, oldnpscands=%d, allrowsfulfilled=%u, heurdata->minintfixingrate=%g\n",
1079 "Heuristic " HEUR_NAME " solving LP from scratch with %.1f %% unfixed columns (%d of %d) ...\n",
1097 SCIPwarningMessage(
scip,
"Error while solving LP in vbound heuristic; LP solve terminated with code <%d>\n",
1129 SCIPdebugMsg(
scip,
"vbound heuristic found roundable primal solution: obj=%g\n",
1189#ifdef SCIP_STATISTIC
1191 SCIPstatisticMessage(
"vbound: tighten=%u obj=%d nvars=%d presolnvars=%d ratio=%.2f infeas=%u found=%d time=%.4f\n",
1253 for( v = 0; v <
heurdata->nvbvars; ++v )
1383 "minimum percentage of integer variables that have to be fixed",
1387 "minimum percentage of variables that have to be fixed within sub-SCIP (integer and continuous)",
1391 "maximum number of nodes to regard in the subproblem",
1395 "number of nodes added to the contingent of the total nodes",
1399 "minimum number of nodes required to start the subproblem",
1403 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1407 "factor by which " HEUR_NAME " heuristic should at least improve the incumbent",
1411 "maximum number of propagation rounds during probing (-1 infinity)",
1415 "should all active cuts from cutpool be copied to constraints in subproblem?",
1419 "should more variables be fixed based on variable locks if the fixing rate was not reached?",
1423 "maximum number of backtracks during the fixing process",
1427 "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",
1431 "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_Real SCIPclockGetTime(SCIP_CLOCK *clck)
internal methods for clocks and timing issues
#define SCIP_MAXTREEDEPTH
#define SCIP_CALL_ABORT(x)
#define SCIP_LONGINT_FORMAT
SCIP_RETCODE SCIPtranslateSubSols(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_Bool *success, int *solindex)
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)
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
SCIP_RETCODE SCIPcopyCuts(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, int *ncutsadded)
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreate(SCIP **scip)
SCIP_STATUS SCIPgetStatus(SCIP *scip)
int SCIPgetNIntVars(SCIP *scip)
int SCIPgetNImplVars(SCIP *scip)
const char * SCIPgetProbName(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)
SCIP_VAR ** SCIPgetVars(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 SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
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 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 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 SCIPincludeHeurVbounds(SCIP *scip)
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
int SCIPgetNPseudoBranchCands(SCIP *scip)
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 SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur,)
const char * SCIPheurGetName(SCIP_HEUR *heur)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
SCIP_RETCODE SCIPflushLP(SCIP *scip)
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
SCIP_RETCODE SCIPconstructLP(SCIP *scip, SCIP_Bool *cutoff)
SCIP_Bool SCIPisLPConstructed(SCIP *scip)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
SCIP_Real SCIPgetLPObjval(SCIP *scip)
int SCIPgetNUnfixedLPCols(SCIP *scip)
int SCIPgetNLPCols(SCIP *scip)
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
#define SCIPallocClearBufferArray(scip, ptr, num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
int SCIPgetProbingDepth(SCIP *scip)
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
char * SCIPsnprintfProbingStats(SCIP *scip, char *strbuf, int len)
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
SCIP_Bool SCIPinProbing(SCIP *scip)
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
int SCIPgetNSols(SCIP *scip)
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
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_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)
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
SCIP_RETCODE SCIPpresolve(SCIP *scip)
SCIP_RETCODE SCIPsolve(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 SCIPgetNLPIterations(SCIP *scip)
SCIP_RETCODE SCIPcreateClock(SCIP *scip, SCIP_CLOCK **clck)
SCIP_RETCODE SCIPstopClock(SCIP *scip, SCIP_CLOCK *clck)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_RETCODE SCIPfreeClock(SCIP *scip, SCIP_CLOCK **clck)
SCIP_RETCODE SCIPstartClock(SCIP *scip, SCIP_CLOCK *clck)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPsumepsilon(SCIP *scip)
int SCIPgetDepth(SCIP *scip)
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
int SCIPvarGetNVlbs(SCIP_VAR *var)
SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
int SCIPvarGetProbindex(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
int SCIPvarGetNVubs(SCIP_VAR *var)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
int SCIPgetNCliques(SCIP *scip)
SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
void SCIPenableVarHistory(SCIP *scip)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
SCIPfreeSol(scip, &heurdata->sol))
SCIPcreateSol(scip, &heurdata->sol, heur))
assert(minobj< SCIPgetCutoffbound(scip))
SCIPlinkLPSol(scip, sol))
SCIP_RETCODE SCIPapplyLockFixings(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Bool *cutoff, SCIP_Bool *allrowsfulfilled)
#define getOtherBoundIndex(idx)
#define DEFAULT_MININTFIXINGRATE
#define DEFAULT_NODESQUOT
#define isIndexLowerbound(idx)
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)
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)
#define VBOUNDVARIANT_WORSTBOUND
#define DEFAULT_TIGHTENVARIANT
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)
static SCIP_RETCODE dfs(SCIP *scip, int startnode, SCIP_Shortbool *visited, int *dfsstack, int *stacknextedge, int *stacknextcliquevar, int *cliqueexit, int *dfsnodes, int *ndfsnodes)
#define DEFAULT_FEASVARIANT
static SCIP_RETCODE initializeCandsLists(SCIP *scip, SCIP_HEURDATA *heurdata)
#define DEFAULT_MINIMPROVE
#define DEFAULT_MINMIPFIXINGRATE
static SCIP_RETCODE topologicalSort(SCIP *scip, int *vbvars, int *nvbvars)
#define DEFAULT_MAXBACKTRACKS
static void heurdataReset(SCIP_HEURDATA *heurdata)
#define getBoundtype(idx)
#define VBOUNDVARIANT_BESTBOUND
#define DEFAULT_USELOCKFIXINGS
#define DEFAULT_MAXPROPROUNDS
#define VBOUNDVARIANT_NOOBJ
LNS heuristic uses the variable lower and upper bounds to determine the search neighborhood.
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
int SCIPcliqueGetIndex(SCIP_CLIQUE *clique)
memory allocation routines
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
public methods for primal heuristics
public methods for implications, variable bounds, and cliques
public methods for message output
#define SCIPstatisticMessage
public data structures and miscellaneous methods
public methods for branch and bound tree
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 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 numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for the probing mode
public methods for solutions
public methods for querying solving statistics
public methods for timing
public methods for the branch-and-bound tree
public methods for SCIP variables
#define SCIP_DECL_HEURCOPY(x)
struct SCIP_HeurData SCIP_HEURDATA
#define SCIP_DECL_HEURFREE(x)
#define SCIP_DECL_HEUREXITSOL(x)
#define SCIP_DECL_HEUREXEC(x)
enum SCIP_LPSolStat SCIP_LPSOLSTAT
enum SCIP_BoundType SCIP_BOUNDTYPE
@ SCIP_LPSOLSTAT_INFEASIBLE
@ SCIP_LPSOLSTAT_OBJLIMIT
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARTYPE_CONTINUOUS