lpface primal heuristic that searches the optimal LP face inside a sub-MIP
Definition in file heur_lpface.c.
#include <assert.h>
#include <string.h>
#include <stdio.h>
#include "scip/scip.h"
#include "scip/scipdefplugins.h"
#include "scip/cons_linear.h"
#include "scip/heur_lpface.h"
#include "scip/pub_misc.h"
Go to the source code of this file.
Macros | |
#define | HEUR_NAME "lpface" |
#define | HEUR_DESC "LNS heuristic that searches the optimal LP face inside a sub-MIP" |
#define | HEUR_DISPCHAR '_' |
#define | HEUR_PRIORITY -1104000 |
#define | HEUR_FREQ 15 |
#define | HEUR_FREQOFS 0 |
#define | HEUR_MAXDEPTH -1 |
#define | HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE |
#define | HEUR_USESSUBSCIP TRUE |
#define | DEFAULT_MAXNODES 5000LL |
#define | DEFAULT_MINNODES 50LL |
#define | DEFAULT_MINFIXINGRATE 0.1 |
#define | DEFAULT_NODESOFS 200LL |
#define | DEFAULT_NODESQUOT 0.1 |
#define | DEFAULT_LPLIMFAC 2.0 |
#define | DEFAULT_USELPROWS TRUE |
#define | DEFAULT_COPYCUTS TRUE |
#define | DEFAULT_DUALBASISEQUATIONS FALSE |
#define | DEFAULT_KEEPSUBSCIP FALSE |
#define | DEFAULT_MINPATHLEN 5 |
#define | EVENTHDLR_NAME "Lpface" |
#define | EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" |
#define | heurExitLpface NULL |
Typedefs | |
typedef struct SubscipData | SUBSCIPDATA |
Functions | |
static SCIP_RETCODE | fixVariables (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEURDATA *heurdata, SCIP_Bool *success) |
static SCIP_RETCODE | createRows (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_Bool dualbasisequations) |
static SCIP_RETCODE | setupSubproblem (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEURDATA *heurdata, SCIP_Bool *success) |
static SCIP_RETCODE | createNewSol (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, int *solindex, SCIP_Bool *success) |
static void | updateFailureStatistic (SCIP *scip, SCIP_HEURDATA *heurdata) |
static SCIP_Longint | calcNodeLimit (SCIP *scip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata) |
static SCIP_RETCODE | setSubscipLimits (SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, SCIP_Bool *success) |
static SCIP_RETCODE | setSubscipParameters (SCIP *scip, SCIP *subscip) |
static void | subscipdataReset (SUBSCIPDATA *subscipdata) |
static SCIP_RETCODE | subscipdataFreeSubscip (SCIP *scip, SUBSCIPDATA *subscipdata) |
static SCIP_RETCODE | subscipdataCopySubscip (SCIP *scip, SUBSCIPDATA *subscipdata, SCIP *subscip, SCIP_VAR **subvars, int nvars) |
static SCIP_RETCODE | changeSubvariableObjective (SCIP *scip, SCIP *subscip, SCIP_VAR *var, SCIP_VAR *subvar, SCIP_HEURDATA *heurdata) |
static | SCIP_DECL_EVENTEXEC (eventExecLpface) |
static SCIP_RETCODE | setupSubscipLpface (SCIP *scip, SCIP *subscip, SCIP_HEURDATA *heurdata, SCIP_VAR **subvars, SCIP_VAR **vars, SCIP_RESULT *result, SCIP_Bool *keepthisscip, int nvars) |
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_DECL_HEURCOPY (heurCopyLpface) |
static | SCIP_DECL_HEURFREE (heurFreeLpface) |
static | SCIP_DECL_HEURINIT (heurInitLpface) |
static | SCIP_DECL_HEURINITSOL (heurInitsolLpface) |
static | SCIP_DECL_HEUREXITSOL (heurExitsolLpface) |
static | SCIP_DECL_HEUREXEC (heurExecLpface) |
SCIP_RETCODE | SCIPincludeHeurLpface (SCIP *scip) |
#define HEUR_NAME "lpface" |
Definition at line 32 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface(), and solveSubscipLpface().
#define HEUR_DESC "LNS heuristic that searches the optimal LP face inside a sub-MIP" |
Definition at line 33 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
#define HEUR_DISPCHAR '_' |
Definition at line 34 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
#define HEUR_PRIORITY -1104000 |
Definition at line 35 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
#define HEUR_FREQ 15 |
Definition at line 36 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
#define HEUR_FREQOFS 0 |
Definition at line 37 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
#define HEUR_MAXDEPTH -1 |
Definition at line 38 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE |
Definition at line 39 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 40 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
#define DEFAULT_MAXNODES 5000LL |
maximum number of nodes to regard in the subproblem
Definition at line 42 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
#define DEFAULT_MINNODES 50LL |
minimum number of nodes to regard in the subproblem
Definition at line 43 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
#define DEFAULT_MINFIXINGRATE 0.1 |
required percentage of fixed integer variables in sub-MIP to run
Definition at line 44 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
#define DEFAULT_NODESOFS 200LL |
number of nodes added to the contingent of the total nodes
Definition at line 45 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
#define DEFAULT_NODESQUOT 0.1 |
subproblem nodes in relation to nodes of the original problem
Definition at line 46 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
#define DEFAULT_LPLIMFAC 2.0 |
factor by which the limit on the number of LP depends on the node limit
Definition at line 47 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
#define DEFAULT_USELPROWS TRUE |
should subproblem be created out of the rows in the LP rows, otherwise, the copy constructors of the constraints handlers are used
Definition at line 48 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
#define DEFAULT_COPYCUTS TRUE |
if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?
Definition at line 51 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
#define DEFAULT_DUALBASISEQUATIONS FALSE |
should the dually nonbasic rows be turned into equations?
Definition at line 54 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
#define DEFAULT_KEEPSUBSCIP FALSE |
should the heuristic continue solving the same sub-SCIP?
Definition at line 55 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
#define DEFAULT_MINPATHLEN 5 |
the minimum active search tree path length along which the lower bound hasn't changed before heuristic becomes active
Definition at line 56 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
#define EVENTHDLR_NAME "Lpface" |
Definition at line 60 of file heur_lpface.c.
Referenced by solveSubscipLpface().
#define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" |
Definition at line 61 of file heur_lpface.c.
Referenced by solveSubscipLpface().
#define heurExitLpface NULL |
Definition at line 1116 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
typedef struct SubscipData SUBSCIPDATA |
Definition at line 75 of file heur_lpface.c.
|
static |
fixes variables of the subproblem considering their reduced costs
scip | original SCIP data structure |
subscip | SCIP data structure for the subproblem |
subvars | the variables of the subproblem |
heurdata | primal heuristic data |
success | pointer to store whether enough integer variables were fixed |
Definition at line 115 of file heur_lpface.c.
References createRows(), MAX, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPchgVarLbGlobal(), SCIPchgVarUbGlobal(), SCIPdebugMsg, SCIPgetColRedcost(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPisDualfeasZero(), SCIPisFeasEQ(), SCIPisInfinity(), SCIPvarGetCol(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and SCIPvarIsIntegral().
Referenced by setupSubproblem().
|
static |
creates the rows of the subproblem
scip | original SCIP data structure |
subscip | SCIP data structure for the subproblem |
subvars | the variables of the subproblem |
dualbasisequations | should the dually nonbasic rows be turned into equations? |
Definition at line 199 of file heur_lpface.c.
References FALSE, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPallocBufferArray, SCIPcolGetVar(), SCIPcreateConsLinear(), SCIPfreeBufferArray, SCIPgetLPRowsData(), SCIPgetRowActivity(), SCIPisDualfeasZero(), SCIPisFeasEQ(), SCIPisInfinity(), SCIPreleaseCons(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetDualsol(), SCIProwGetLhs(), SCIProwGetName(), SCIProwGetNNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIProwIsLocal(), SCIPvarGetProbindex(), setupSubproblem(), and TRUE.
Referenced by fixVariables(), and setupSubproblem().
|
static |
creates the LP face subproblem by fixing nonbasic variables with nonzero reduced costs
scip | original SCIP data structure |
subscip | SCIP data structure for the subproblem |
subvars | the variables of the subproblem |
heurdata | primal heuristic data |
success | pointer to store whether the problem was created successfully |
Definition at line 284 of file heur_lpface.c.
References createNewSol(), createRows(), FALSE, fixVariables(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCoefLinear(), SCIPaddCons(), SCIPcreateConsLinear(), SCIPgetLowerbound(), SCIPgetNObjVars(), SCIPgetNVars(), SCIPgetVars(), SCIPisZero(), SCIPreleaseCons(), SCIPvarGetObj(), and TRUE.
Referenced by createRows(), and setupSubscipLpface().
|
static |
creates a new solution for the original problem by copying the solution of the subproblem
scip | original SCIP data structure |
subscip | SCIP structure of the subproblem |
subvars | the variables of the subproblem |
heur | lpface heuristic structure |
subsol | solution of the subproblem |
solindex | pointer to store index of the solution |
success | pointer to store whether new solution was found or not |
Definition at line 339 of file heur_lpface.c.
References FALSE, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcreateSol(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetNOrigVars(), SCIPgetSolTransObj(), SCIPgetSolVals(), SCIPgetVarsData(), SCIPretransformObj(), SCIPsetSolVals(), SCIPsolGetIndex(), SCIPtrySolFree(), TRUE, and updateFailureStatistic().
Referenced by setupSubproblem(), and solveSubscipLpface().
|
static |
updates heurdata after an unsuccessful run of lpface
scip | original SCIP data structure |
heurdata | primal heuristic data |
Definition at line 402 of file heur_lpface.c.
References calcNodeLimit(), SCIP_Longint, SCIP_LONGINT_MAX, and SCIPgetNNodes().
Referenced by createNewSol(), setupSubscipLpface(), and solveSubscipLpface().
|
static |
calculate a node limit based on node limiting parameters of the heuristic
scip | (original) SCIP data structure |
heur | LP face heuristic |
heurdata | primal heuristic data |
Definition at line 416 of file heur_lpface.c.
References SCIP_Longint, SCIPgetNNodes(), SCIPheurGetNCalls(), and setSubscipLimits().
Referenced by setSubscipLimits(), and updateFailureStatistic().
|
static |
sets node, time, and memory limit according to the parameter settings of the heuristic
scip | original SCIP data structure |
subscip | data structure of the sub-problem |
heur | LP face heuristic |
heurdata | heuristic data structure |
success | did we successfully set all parameters up? |
Definition at line 448 of file heur_lpface.c.
References calcNodeLimit(), FALSE, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetNNodes(), SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPisInfinity(), SCIPsetLongintParam(), SCIPsetRealParam(), setSubscipParameters(), and TRUE.
Referenced by calcNodeLimit(), and solveSubscipLpface().
|
static |
sets all one-time parameter settings like search strategy, but no limits
scip | original SCIP data structure |
subscip | data structure of the sub-problem |
Definition at line 503 of file heur_lpface.c.
References FALSE, SCIP_CALL, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIPfindBranchrule(), SCIPfindConshdlr(), SCIPfindNodesel(), SCIPisParamFixed(), SCIPsetBoolParam(), SCIPsetCharParam(), SCIPsetIntParam(), SCIPsetPresolving(), SCIPsetSeparating(), SCIPsetSubscipsOff(), subscipdataReset(), and TRUE.
Referenced by setSubscipLimits(), and setupSubscipLpface().
|
static |
reset the sub-SCIP data to its default values
subscipdata | data structure of the sub-problem |
Definition at line 572 of file heur_lpface.c.
References SubscipData::nsubvars, SubscipData::objbound, SCIP_INVALID, SubscipData::subscip, subscipdataFreeSubscip(), and SubscipData::subvars.
Referenced by setSubscipParameters(), and subscipdataFreeSubscip().
|
static |
free the stored sub-SCIP information
scip | original SCIP data structure |
subscipdata | data structure of the sub-problem |
Definition at line 584 of file heur_lpface.c.
References SubscipData::nsubvars, SCIP_CALL, SCIP_OKAY, SCIPfree(), SCIPfreeBlockMemoryArray, SubscipData::subscip, subscipdataCopySubscip(), subscipdataReset(), and SubscipData::subvars.
Referenced by subscipdataReset().
|
static |
store the sub-SCIP to the data structure
scip | original SCIP data structure |
subscipdata | data structure of the sub-problem |
subscip | sub scip data structure to keep |
subvars | sub scip variable array in the order of the main SCIP variables |
nvars | number of sub SCIP variables |
Definition at line 613 of file heur_lpface.c.
References changeSubvariableObjective(), SubscipData::nsubvars, SubscipData::objbound, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPduplicateBlockMemoryArray, SCIPgetCurrentNode(), SCIPgetLongintParam(), SCIPgetNNodes(), SCIPgetNodeLowerbound(), SCIPgetNVars(), SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPgetStatus(), SubscipData::subscip, and SubscipData::subvars.
Referenced by subscipdataFreeSubscip().
|
static |
create the objective function based on the user selection
scip | SCIP data structure |
subscip | sub-SCIP data structure |
var | SCIP variable |
subvar | sub-SCIP variable whose objective coefficient is changed |
heurdata | heuristic data structure to control how the objective is changed |
Definition at line 671 of file heur_lpface.c.
References SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHDIR_UPWARDS, SCIP_CALL, SCIP_DECL_EVENTEXEC(), SCIP_OKAY, SCIP_Real, SCIPchgVarObj(), SCIPfrac(), SCIPgetVarAvgInferences(), SCIPvarGetLPSol(), SCIPvarGetObj(), and SCIPvarGetRootSol().
Referenced by setupSubscipLpface(), and subscipdataCopySubscip().
|
static |
execution callback of the event handler for Lpface sub-SCIP
we interrupt the solution process if we hit the LP iteration limit per node
Definition at line 736 of file heur_lpface.c.
Referenced by changeSubvariableObjective().
|
static |
setup and solve the subproblem and catch the return code
scip | SCIP data structure |
subscip | sub-SCIP data structure |
heurdata | heuristics data |
subvars | subproblem's variables |
vars | original problem's variables |
result | pointer to store the result |
keepthisscip | should the subscip be kept or deleted? |
nvars | number of original problem's variables |
Definition at line 761 of file heur_lpface.c.
References changeSubvariableObjective(), FALSE, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPblkmem(), SCIPcopy(), SCIPcopyCuts(), SCIPcopyParamSettings(), SCIPcopyVars(), SCIPcreateProbBasic(), SCIPgetProbName(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPincludeDefaultPlugins(), SCIPsetIntParam(), SCIPsnprintf(), setSubscipParameters(), setupSubproblem(), solveSubscipLpface(), TRUE, and updateFailureStatistic().
|
static |
setup and solve the subproblem and catch the return code
scip | SCIP data structure |
subscip | sub-SCIP data structure |
heur | mutation heuristic |
heurdata | heuristics data |
subvars | subproblem's variables |
result | pointer to store the result |
focusnodelb | lower bound of the focus node |
keepthisscip | should the subscip be kept or deleted? |
Definition at line 855 of file heur_lpface.c.
References createNewSol(), EVENTHDLR_DESC, EVENTHDLR_NAME, FALSE, HEUR_NAME, SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIP_DECL_HEURCOPY(), SCIP_EVENTTYPE_LPSOLVED, SCIP_FOUNDSOL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIP_STATUS_INFEASIBLE, SCIPcatchEvent(), SCIPdebug, SCIPdebugMsg, SCIPerrorMessage, SCIPgetBestSol(), SCIPgetNLPIterations(), SCIPgetNNodes(), SCIPgetNSols(), SCIPgetPresolvingTime(), SCIPgetSols(), SCIPgetStatus(), SCIPincludeEventhdlrBasic(), SCIPinfoMessage(), SCIPprintStatistics(), SCIPsolGetIndex(), SCIPsolve(), SCIPtransformProb(), SCIPwriteOrigProblem(), SCIPwriteParams(), setSubscipLimits(), TRUE, and updateFailureStatistic().
Referenced by setupSubscipLpface().
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 984 of file heur_lpface.c.
Referenced by solveSubscipLpface().
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 998 of file heur_lpface.c.
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 1018 of file heur_lpface.c.
|
static |
solving process initialization method of primal heuristic (called when branch and bound process is about to begin)
Definition at line 1044 of file heur_lpface.c.
|
static |
solving process deinitialization method of primal heuristic (called before branch and bound process is exiting)
Definition at line 1069 of file heur_lpface.c.
|
static |
execution method of primal heuristic
Definition at line 1121 of file heur_lpface.c.