64#define HEUR_NAME "completesol"
65#define HEUR_DESC "primal heuristic trying to complete given partial solutions"
66#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
67#define HEUR_PRIORITY 0
70#define HEUR_MAXDEPTH 0
71#define HEUR_TIMING SCIP_HEURTIMING_BEFOREPRESOL | SCIP_HEURTIMING_BEFORENODE
72#define HEUR_USESSUBSCIP TRUE
75#define DEFAULT_MAXNODES 5000LL
76#define DEFAULT_MAXUNKRATE 0.85
77#define DEFAULT_ADDALLSOLS FALSE
78#define DEFAULT_MINNODES 50LL
79#define DEFAULT_NODESOFS 500LL
80#define DEFAULT_NODESQUOT 0.1
81#define DEFAULT_LPLIMFAC 2.0
82#define DEFAULT_OBJWEIGHT 1.0
83#define DEFAULT_BOUNDWIDENING 0.1
86#define DEFAULT_MINIMPROVE 0.01
87#define DEFAULT_MINOBJWEIGHT 1e-3
88#define DEFAULT_IGNORECONT FALSE
89#define DEFAULT_BESTSOLS 5
90#define DEFAULT_MAXPROPROUNDS 10
91#define DEFAULT_MAXLPITER -1LL
92#define DEFAULT_MAXCONTVARS -1
93#define DEFAULT_BEFOREPRESOL TRUE
96#define EVENTHDLR_NAME "Completesol"
97#define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic"
103 SCIP_Longint maxnodes;
104 SCIP_Longint minnodes;
105 SCIP_Longint nodesofs;
106 SCIP_Longint maxlpiter;
107 SCIP_Real maxunknownrate;
112 SCIP_Real boundwidening;
115 SCIP_Real minimprove;
116 SCIP_Bool addallsols;
117 SCIP_Bool ignorecont;
118 SCIP_Bool beforepresol;
169 SCIP_Real upperbound;
230 if( subvars[
i] ==
NULL )
237 if( objcons ==
NULL )
274 if( tightened[idx] ==
FALSE )
338 if( objcons !=
NULL )
405 SCIP_Bool* tightened,
406 SCIP_Bool* infeasible
410 SCIP_Bool incontsection;
412 SCIP_Bool abortearly;
414 SCIP_Bool probingsuccess;
415 SCIP_Longint ndomreds;
416 SCIP_Longint ndomredssum;
436 incontsection =
FALSE;
445 for( v = 0; v <
nvars && !abortearly; v++ )
460 if( ndomredssum > 0.3*
nvars )
480#ifdef SCIP_MORE_DEBUG
497#ifdef SCIP_MORE_DEBUG
510#ifdef SCIP_MORE_DEBUG
548#ifdef SCIP_MORE_DEBUG
619#ifdef SCIP_MORE_DEBUG
629#ifdef SCIP_MORE_DEBUG
630 SCIPdebugMsg(
scip,
"> tighten upper bound of variable <%s>: %g to %g (ndomreds=%lld)\n",
677#ifdef SCIP_MORE_DEBUG
687#ifdef SCIP_MORE_DEBUG
688 SCIPdebugMsg(
scip,
"> tighten lower bound of variable <%s>: %g to %g (ndomreds=%lld)\n",
700 ndomredssum += ndomreds;
703 SCIPdebugMsg(
scip,
"> found %d bound tightenings and %lld induced domain reductions (abort=%u).\n", nbndtightenings,
704 ndomredssum, abortearly);
717 SCIP_Longint nstallnodes,
753 SCIP_CALL(
SCIPcopyConsCompression(
scip, subscip, varmapf,
NULL,
"completesol",
NULL,
NULL, 0,
FALSE,
FALSE,
FALSE,
759 if( eventhdlr ==
NULL )
859 SCIPdebugMsg(
scip,
"presolved instance has bin=%d, int=%d, cont=%d variables\n",
865 SCIPdebugMsg(
scip,
"presolved instance has too many continuous variables (maxcontvars: %d)\n",
heurdata->maxcontvars);
903 for(
i = 0;
i < nsubsols && (!success ||
heurdata->addallsols);
i++ )
954 SCIP_Longint nstallnodes,
960 SCIP_Bool* tightened;
961 SCIP_Bool infeasible;
1064 SCIP_Longint nstallnodes;
1079 if( nodeinfeasible )
1120 nstallnodes =
MIN(nstallnodes,
heurdata->maxnodes);
1123 if( nstallnodes < heurdata->minnodes )
1138 for( s = 0; s < npartialsols; s++ )
1142 SCIP_Real unknownrate;
1144 sol = partialsols[s];
1150 for( v = 0; v <
nvars; v++ )
1171 SCIPdebugMsg(
scip,
"%d (rate %.4f) unknown solution values\n", nunknown, unknownrate);
1174 if( unknownrate >
heurdata->maxunknownrate )
1176 SCIPwarningMessage(
scip,
"ignore partial solution (%d) because unknown rate is too large (%g > %g)\n", s,
1177 unknownrate,
heurdata->maxunknownrate);
1195 for( v = 0; v <
nvars; v++ )
1248 "maximum number of nodes to regard in the subproblem",
1252 "minimum number of nodes required to start the subproblem",
1256 "maximal rate of unknown solution values",
1260 "should all subproblem solutions be added to the original SCIP?",
1264 "number of nodes added to the contingent of the total nodes",
1268 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1272 "factor by which the limit on the number of LP depends on the node limit",
1276 "weight of the original objective function (1: only original objective)",
1280 "bound widening factor applied to continuous variables (0: fix variables to given solution values, 1: relax to global bounds)",
1284 "factor by which the incumbent should be improved at least",
1288 "should number of continuous variables be ignored?",
1292 "heuristic stops, if the given number of improving solutions were found (-1: no limit)",
1296 "maximal number of iterations in propagation (-1: no limit)",
1300 "should the heuristic run before presolving?",
1304 "maximal number of LP iterations (-1: no limit)",
1308 "maximal number of continuous variables after presolving",
Constraint handler for linear constraints in their most general form, .
#define SCIP_MAXTREEDEPTH
#define SCIP_LONGINT_FORMAT
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 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 SCIPtranslateSubSol(SCIP *scip, SCIP *subscip, SCIP_SOL *subsol, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_SOL **newsol)
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)
SCIP_STAGE SCIPgetStage(SCIP *scip)
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
int SCIPgetNIntVars(SCIP *scip)
int SCIPgetNImplVars(SCIP *scip)
int SCIPgetNContVars(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNConss(SCIP *scip)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
SCIP_OBJSENSE SCIPgetObjsense(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 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 SCIPincludeHeurCompletesol(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)
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_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
const char * SCIPheurGetName(SCIP_HEUR *heur)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
#define SCIPallocClearBufferArray(scip, ptr, num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_Bool SCIPisNLPEnabled(SCIP *scip)
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
int SCIPgetProbingDepth(SCIP *scip)
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
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_RETCODE SCIPstartProbing(SCIP *scip)
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
SCIP_RETCODE SCIPfixVarProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
SCIP_SOLORIGIN SCIPsolGetOrigin(SCIP_SOL *sol)
SCIP_SOL ** SCIPgetPartialSols(SCIP *scip)
SCIP_Longint SCIPsolGetNodenum(SCIP_SOL *sol)
int SCIPgetNPartialSols(SCIP *scip)
int SCIPgetNSols(SCIP *scip)
SCIP_Bool SCIPsolIsPartial(SCIP_SOL *sol)
SCIP_SOL ** SCIPgetSols(SCIP *scip)
SCIP_RETCODE SCIPtrySolFree(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 SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
SCIP_RETCODE SCIPpresolve(SCIP *scip)
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
SCIP_RETCODE SCIPsolve(SCIP *scip)
SCIP_Real SCIPgetPrimalbound(SCIP *scip)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
int SCIPgetNRuns(SCIP *scip)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFrac(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
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_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
int SCIPvarGetProbindex(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
int SCIPsnprintf(char *t, int len, const char *s,...)
SCIPcreateSol(scip, &heurdata->sol, heur))
static SCIP_RETCODE createSubproblem(SCIP *scip, SCIP *subscip, SCIP_HEURDATA *heurdata, SCIP_VAR **subvars, SCIP_SOL *partialsol, SCIP_Bool *tightened)
#define DEFAULT_NODESQUOT
#define DEFAULT_MAXCONTVARS
static SCIP_RETCODE chgProbingBound(SCIP *scip, SCIP_VAR *var, SCIP_Real newval, SCIP_BRANCHDIR branchdir, SCIP_Bool *success)
#define DEFAULT_OBJWEIGHT
static SCIP_RETCODE tightenVariables(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **vars, int nvars, SCIP_SOL *sol, SCIP_Bool *tightened, SCIP_Bool *infeasible)
#define DEFAULT_MAXUNKRATE
#define DEFAULT_IGNORECONT
#define DEFAULT_ADDALLSOLS
static SCIP_RETCODE setupAndSolve(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_RESULT *result, SCIP_Longint nstallnodes, SCIP_SOL *partialsol, SCIP_Bool *tightened)
static SCIP_RETCODE applyCompletesol(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_RESULT *result, SCIP_Longint nstallnodes, SCIP_SOL *partialsol)
#define DEFAULT_MINOBJWEIGHT
#define DEFAULT_MINIMPROVE
#define DEFAULT_MAXLPITER
#define DEFAULT_BEFOREPRESOL
#define DEFAULT_MAXPROPROUNDS
#define DEFAULT_BOUNDWIDENING
primal heuristic trying to complete given partial solutions
assert(minobj< SCIPgetCutoffbound(scip))
memory allocation routines
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
public methods for managing events
public methods for primal heuristics
public methods for message output
#define SCIPstatisticPrintf
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 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 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
struct SCIP_EventData SCIP_EVENTDATA
#define SCIP_DECL_EVENTEXEC(x)
#define SCIP_EVENTTYPE_LPSOLVED
#define SCIP_DECL_HEURCOPY(x)
struct SCIP_HeurData SCIP_HEURDATA
#define SCIP_DECL_HEURFREE(x)
#define SCIP_DECL_HEUREXEC(x)
@ SCIP_BRANCHDIR_DOWNWARDS
enum SCIP_BranchDir SCIP_BRANCHDIR
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE
#define SCIP_HEURTIMING_BEFOREPRESOL
#define SCIP_HEURTIMING_BEFORENODE
@ SCIP_VARTYPE_CONTINUOUS