66#define HEUR_NAME "lpface"
67#define HEUR_DESC "LNS heuristic that searches the optimal LP face inside a sub-MIP"
68#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
69#define HEUR_PRIORITY -1104010
72#define HEUR_MAXDEPTH -1
73#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE
74#define HEUR_USESSUBSCIP TRUE
76#define DEFAULT_MAXNODES 5000LL
77#define DEFAULT_MINNODES 50LL
78#define DEFAULT_MINFIXINGRATE 0.1
79#define DEFAULT_NODESOFS 200LL
80#define DEFAULT_NODESQUOT 0.1
81#define DEFAULT_LPLIMFAC 2.0
82#define DEFAULT_USELPROWS TRUE
84#define DEFAULT_COPYCUTS TRUE
86#define DEFAULT_DUALBASISEQUATIONS FALSE
87#define DEFAULT_KEEPSUBSCIP FALSE
88#define DEFAULT_MINPATHLEN 5
91#define EVENTHDLR_NAME "Lpface"
92#define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic"
111 SCIP_Longint maxnodes;
112 SCIP_Longint minnodes;
113 SCIP_Longint nodesofs;
117 unsigned int nfailures;
118 SCIP_Longint nextnodenumber;
119 SCIP_Real lastlpobjinfeas;
120 SCIP_Real minfixingrate;
126 SCIP_Bool dualbasisequations;
127 SCIP_Bool keepsubscip;
128 char subscipobjective;
132 SCIP_Longint submipnlpiters;
133 SCIP_Real submippresoltime;
156 SCIP_Real fixingrate;
228 SCIPdebugMsg(
scip,
" LP face heuristic fixed %senough variables (%d out of %d)\n",
240 SCIP_Bool dualbasisequations
252 for(
i = 0;
i < nrows;
i++ )
291 for(
j = 0;
j < nnonz;
j++ )
294 if( consvars[
j] ==
NULL )
340 SCIP_Real lowerbound;
400 SCIP_Longint nodelimit;
435 SCIP_Real memorylimit;
436 SCIP_Longint nodelimit;
600 subscipdata->
subscip = subscip;
618 SCIP_Real memorylimit;
619 SCIP_Longint nodelimit;
633 time, timelimit, nodes, nodelimit, status);
656 switch(
heurdata->subscipobjective )
761 SCIP_CALL(
SCIPcopyPlugins(
scip, subscip,
TRUE,
FALSE,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
778 SCIP_CALL(
SCIPcopyConsCompression(
scip, subscip, varmapfw,
NULL,
"lpface",
fixvars,
fixvals,
nfixvars,
TRUE,
FALSE,
FALSE,
TRUE, &
success) );
792 if( subvars[
i] !=
NULL )
837 if( eventhdlr ==
NULL )
860#ifdef WRITELPFACEPROB
1045#ifdef SCIP_STATISTIC
1060 "LP Face heuristic stats: Status: %d Nodes: %d LP iters: %d Fixed: %d Presolving time: %.2f\n",
1066#define heurExitLpface NULL
1081 SCIP_Longint nodelimit;
1203 SCIPdebugMsg(
scip,
"Free subscip of LP face heuristic because variable number %d changed since last call (was %d)\n",
1210 SCIPdebugMsg(
scip,
"Free subscip of LP face heuristic because of different dual bound: %16.9g > %16.9g\n",
1219 subscip =
heurdata->subscipdata->subscip;
1220 subvars =
heurdata->subscipdata->subvars;
1337 "number of nodes added to the contingent of the total nodes",
1341 "maximum number of nodes to regard in the subproblem",
1345 "minimum number of nodes required to start the subproblem",
1349 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1353 "required percentage of fixed integer variables in sub-MIP to run",
1357 "factor by which the limit on the number of LP depends on the node limit",
1361 "should subproblem be created out of the rows in the LP rows?",
1365 "should dually nonbasic rows be turned into equations?",
1369 "should the heuristic continue solving the same sub-SCIP?",
1373 "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
1377 "objective function in the sub-SCIP: (z)ero, (r)oot-LP-difference, (i)nference, LP (f)ractionality, (o)riginal",
1381 "the minimum active search tree path length along which lower bound hasn't changed before heuristic becomes active",
Constraint handler for linear constraints in their most general form, .
#define SCIP_CALL_ABORT(x)
#define SCIP_LONGINT_FORMAT
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
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)
void SCIPsetSubscipDepth(SCIP *scip, int newdepth)
SCIP_RETCODE SCIPtranslateSubSols(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_Bool *success, int *solindex)
SCIP_RETCODE SCIPcopyVars(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool global)
SCIP_RETCODE SCIPcopyPlugins(SCIP *sourcescip, SCIP *targetscip, SCIP_Bool copyreaders, SCIP_Bool copypricers, SCIP_Bool copyconshdlrs, SCIP_Bool copyconflicthdlrs, SCIP_Bool copypresolvers, SCIP_Bool copyrelaxators, SCIP_Bool copyseparators, SCIP_Bool copycutselectors, SCIP_Bool copypropagators, SCIP_Bool copyheuristics, SCIP_Bool copyeventhdlrs, SCIP_Bool copynodeselectors, SCIP_Bool copybranchrules, SCIP_Bool copydisplays, SCIP_Bool copydialogs, SCIP_Bool copytables, SCIP_Bool copyexprhdlrs, SCIP_Bool copynlpis, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
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)
int SCIPgetSubscipDepth(SCIP *scip)
SCIP_RETCODE SCIPcopyCuts(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, int *ncutsadded)
SCIP_RETCODE SCIPcopyParamSettings(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 SCIPgetNObjVars(SCIP *scip)
const char * SCIPgetProbName(SCIP *scip)
SCIP_RETCODE SCIPwriteOrigProblem(SCIP *scip, const char *filename, const char *extension, SCIP_Bool genericnames)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
int SCIPgetNVars(SCIP *scip)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
SCIP_Bool SCIPisObjIntegral(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)
SCIP_Real SCIPgetNodeLowerbound(SCIP *scip, SCIP_NODE *node)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, 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 SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
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 SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
SCIP_RETCODE SCIPwriteParams(SCIP *scip, const char *filename, SCIP_Bool comments, SCIP_Bool onlychanged)
SCIP_RETCODE SCIPresetParam(SCIP *scip, const char *name)
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
SCIP_RETCODE SCIPsetCharParam(SCIP *scip, const char *name, char value)
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 SCIPgetLongintParam(SCIP *scip, const char *name, SCIP_Longint *value)
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
SCIP_RETCODE SCIPincludeHeurLpface(SCIP *scip)
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
SCIP_Real SCIPgetColRedcost(SCIP *scip, SCIP_COL *col)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
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 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_RETCODE SCIPsetHeurInitsol(SCIP *scip, 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,)
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur,)
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur,)
const char * SCIPheurGetName(SCIP_HEUR *heur)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
SCIP_Bool SCIPisLPRelax(SCIP *scip)
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
SCIP_Bool SCIPallColsInLP(SCIP *scip)
SCIP_Real SCIPgetLPObjval(SCIP *scip)
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
SCIP_NODE * SCIPnodeGetParent(SCIP_NODE *node)
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
int SCIProwGetNNonz(SCIP_ROW *row)
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
const char * SCIProwGetName(SCIP_ROW *row)
SCIP_Real SCIPgetRowActivity(SCIP *scip, SCIP_ROW *row)
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
int SCIPgetNSols(SCIP *scip)
int SCIPsolGetIndex(SCIP_SOL *sol)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
SCIP_RETCODE SCIPsolve(SCIP *scip)
SCIP_Real SCIPgetLowerboundRoot(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_Real SCIPgetPresolvingTime(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_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfrac(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisDualfeasZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetDepth(SCIP *scip)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
int SCIPvarGetProbindex(SCIP_VAR *var)
SCIP_Real SCIPvarGetRootSol(SCIP_VAR *var)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
SCIP_Bool SCIPvarIsRelaxationOnly(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
SCIP_Real SCIPgetVarAvgInferences(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR dir)
int SCIPsnprintf(char *t, int len, const char *s,...)
assert(minobj< SCIPgetCutoffbound(scip))
static SCIP_RETCODE setSubscipLimits(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_Bool *success)
static SCIP_RETCODE createRows(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_Bool dualbasisequations)
#define DEFAULT_NODESQUOT
static SCIP_RETCODE subscipdataCopySubscip(SCIP *scip, SUBSCIPDATA *subscipdata, SCIP *subscip, SCIP_VAR **subvars, int nvars)
static SCIP_RETCODE setSubscipParameters(SCIP *subscip)
static SCIP_RETCODE setupSubscipLpface(SCIP *scip, SCIP *subscip, SCIP_HEURDATA *heurdata, SCIP_VAR **subvars, SCIP_VAR **vars, SCIP_VAR **fixvars, SCIP_Real *fixvals, int nfixvars, int nvars)
static SCIP_RETCODE subscipdataFreeSubscip(SCIP *scip, SUBSCIPDATA *subscipdata)
static SCIP_RETCODE changeSubvariableObjective(SCIP *scip, SCIP *subscip, SCIP_VAR *var, SCIP_VAR *subvar, SCIP_HEURDATA *heurdata)
static SCIP_RETCODE solveSubscipLpface(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_VAR **subvars, SCIP_RESULT *result, SCIP_Real focusnodelb, SCIP_Bool *keepthisscip)
static SCIP_Longint calcNodeLimit(SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
#define DEFAULT_KEEPSUBSCIP
#define DEFAULT_DUALBASISEQUATIONS
#define DEFAULT_MINFIXINGRATE
static SCIP_RETCODE determineVariableFixings(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **fixvars, SCIP_Real *fixvals, int *nfixvars, SCIP_Bool *success)
#define DEFAULT_USELPROWS
#define DEFAULT_MINPATHLEN
static void updateFailureStatistic(SCIP *scip, SCIP_HEURDATA *heurdata)
static void subscipdataReset(SUBSCIPDATA *subscipdata)
static SCIP_RETCODE setupSubproblem(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEURDATA *heurdata)
LNS heuristic that tries to compute integral solution on optimal LP face.
memory allocation routines
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
public methods for managing events
public methods for primal heuristics
public methods for LP management
public methods for message output
public data structures and miscellaneous methods
public methods for primal CIP solutions
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 event handler plugins and event handlers
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 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 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_HEURINITSOL(x)
#define SCIP_DECL_HEURCOPY(x)
struct SCIP_HeurData SCIP_HEURDATA
#define SCIP_DECL_HEURINIT(x)
#define SCIP_DECL_HEUREXIT(x)
#define SCIP_DECL_HEURFREE(x)
#define SCIP_DECL_HEUREXITSOL(x)
#define SCIP_DECL_HEUREXEC(x)
@ SCIP_BRANCHDIR_DOWNWARDS
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE
enum SCIP_Status SCIP_STATUS