Detailed Description
lpface primal heuristic that searches the optimal LP face inside a sub-MIP
Definition in file heur_lpface.c.
#include "blockmemshell/memory.h"
#include "scip/cons_linear.h"
#include "scip/scipdefplugins.h"
#include "scip/heur_lpface.h"
#include "scip/pub_event.h"
#include "scip/pub_heur.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_sol.h"
#include "scip/pub_tree.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_cons.h"
#include "scip/scip_copy.h"
#include "scip/scip_event.h"
#include "scip/scip_general.h"
#include "scip/scip_heur.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_nodesel.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_sol.h"
#include "scip/scip_solve.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_timing.h"
#include "scip/scip_tree.h"
#include "scip/scip_var.h"
#include <string.h>
Go to the source code of this file.
Data Structures | |
struct | SubscipData |
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) |
Macro Definition Documentation
◆ HEUR_NAME
#define HEUR_NAME "lpface" |
Definition at line 56 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface(), and solveSubscipLpface().
◆ HEUR_DESC
#define HEUR_DESC "LNS heuristic that searches the optimal LP face inside a sub-MIP" |
Definition at line 57 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
◆ HEUR_DISPCHAR
#define HEUR_DISPCHAR '_' |
Definition at line 58 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
◆ HEUR_PRIORITY
#define HEUR_PRIORITY -1104000 |
Definition at line 59 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
◆ HEUR_FREQ
#define HEUR_FREQ 15 |
Definition at line 60 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
◆ HEUR_FREQOFS
#define HEUR_FREQOFS 0 |
Definition at line 61 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
◆ HEUR_MAXDEPTH
#define HEUR_MAXDEPTH -1 |
Definition at line 62 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
◆ HEUR_TIMING
#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE |
Definition at line 63 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
◆ HEUR_USESSUBSCIP
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 64 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
◆ DEFAULT_MAXNODES
#define DEFAULT_MAXNODES 5000LL |
maximum number of nodes to regard in the subproblem
Definition at line 66 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
◆ DEFAULT_MINNODES
#define DEFAULT_MINNODES 50LL |
minimum number of nodes to regard in the subproblem
Definition at line 67 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
◆ DEFAULT_MINFIXINGRATE
#define DEFAULT_MINFIXINGRATE 0.1 |
required percentage of fixed integer variables in sub-MIP to run
Definition at line 68 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
◆ DEFAULT_NODESOFS
#define DEFAULT_NODESOFS 200LL |
number of nodes added to the contingent of the total nodes
Definition at line 69 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
◆ DEFAULT_NODESQUOT
#define DEFAULT_NODESQUOT 0.1 |
subproblem nodes in relation to nodes of the original problem
Definition at line 70 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
◆ DEFAULT_LPLIMFAC
#define DEFAULT_LPLIMFAC 2.0 |
factor by which the limit on the number of LP depends on the node limit
Definition at line 71 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
◆ DEFAULT_USELPROWS
#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 72 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
◆ DEFAULT_COPYCUTS
#define DEFAULT_COPYCUTS TRUE |
if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?
Definition at line 75 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
◆ DEFAULT_DUALBASISEQUATIONS
#define DEFAULT_DUALBASISEQUATIONS FALSE |
should the dually nonbasic rows be turned into equations?
Definition at line 78 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
◆ DEFAULT_KEEPSUBSCIP
#define DEFAULT_KEEPSUBSCIP FALSE |
should the heuristic continue solving the same sub-SCIP?
Definition at line 79 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
◆ DEFAULT_MINPATHLEN
#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 80 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
◆ EVENTHDLR_NAME
#define EVENTHDLR_NAME "Lpface" |
Definition at line 84 of file heur_lpface.c.
Referenced by solveSubscipLpface().
◆ EVENTHDLR_DESC
#define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" |
Definition at line 85 of file heur_lpface.c.
Referenced by solveSubscipLpface().
◆ heurExitLpface
#define heurExitLpface NULL |
Definition at line 1138 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
Typedef Documentation
◆ SUBSCIPDATA
typedef struct SubscipData SUBSCIPDATA |
Definition at line 99 of file heur_lpface.c.
Function Documentation
◆ fixVariables()
|
static |
fixes variables of the subproblem considering their reduced costs
- Parameters
-
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 139 of file heur_lpface.c.
References createRows(), MAX, NULL, 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().
◆ createRows()
|
static |
creates the rows of the subproblem
- Parameters
-
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 222 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().
◆ setupSubproblem()
|
static |
creates the LP face subproblem by fixing nonbasic variables with nonzero reduced costs
- Parameters
-
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 307 of file heur_lpface.c.
References createNewSol(), createRows(), FALSE, fixVariables(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCoefLinear(), SCIPaddCons(), SCIPcreateConsLinear(), SCIPgetLowerbound(), SCIPgetNObjVars(), SCIPgetNVars(), SCIPgetVars(), SCIPisZero(), SCIPreleaseCons(), SCIPvarGetObj(), and TRUE.
Referenced by createRows(), and setupSubscipLpface().
◆ createNewSol()
|
static |
creates a new solution for the original problem by copying the solution of the subproblem
- Parameters
-
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 362 of file heur_lpface.c.
References FALSE, NULL, 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().
◆ updateFailureStatistic()
|
static |
updates heurdata after an unsuccessful run of lpface
- Parameters
-
scip original SCIP data structure heurdata primal heuristic data
Definition at line 425 of file heur_lpface.c.
References calcNodeLimit(), SCIP_Longint, SCIP_LONGINT_MAX, and SCIPgetNNodes().
Referenced by createNewSol(), setupSubscipLpface(), and solveSubscipLpface().
◆ calcNodeLimit()
|
static |
calculate a node limit based on node limiting parameters of the heuristic
- Parameters
-
scip (original) SCIP data structure heur LP face heuristic heurdata primal heuristic data
Definition at line 439 of file heur_lpface.c.
References MIN, NULL, SCIP_Longint, SCIPgetNNodes(), SCIPheurGetNCalls(), and setSubscipLimits().
Referenced by setSubscipLimits(), and updateFailureStatistic().
◆ setSubscipLimits()
|
static |
sets node, time, and memory limit according to the parameter settings of the heuristic
- Parameters
-
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 471 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().
◆ setSubscipParameters()
|
static |
sets all one-time parameter settings like search strategy, but no limits
- Parameters
-
scip original SCIP data structure subscip data structure of the sub-problem
Definition at line 526 of file heur_lpface.c.
References FALSE, NULL, 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().
◆ subscipdataReset()
|
static |
reset the sub-SCIP data to its default values
- Parameters
-
subscipdata data structure of the sub-problem
Definition at line 594 of file heur_lpface.c.
References SubscipData::nsubvars, NULL, SubscipData::objbound, SCIP_INVALID, SubscipData::subscip, subscipdataFreeSubscip(), and SubscipData::subvars.
Referenced by setSubscipParameters(), and subscipdataFreeSubscip().
◆ subscipdataFreeSubscip()
|
static |
free the stored sub-SCIP information
- Parameters
-
scip original SCIP data structure subscipdata data structure of the sub-problem
Definition at line 606 of file heur_lpface.c.
References SubscipData::nsubvars, NULL, SCIP_CALL, SCIP_OKAY, SCIPfree(), SCIPfreeBlockMemoryArray, SubscipData::subscip, subscipdataCopySubscip(), subscipdataReset(), and SubscipData::subvars.
Referenced by subscipdataReset().
◆ subscipdataCopySubscip()
|
static |
store the sub-SCIP to the data structure
- Parameters
-
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 635 of file heur_lpface.c.
References changeSubvariableObjective(), SubscipData::nsubvars, NULL, SubscipData::objbound, SCIP_CALL, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPduplicateBlockMemoryArray, SCIPgetCurrentNode(), SCIPgetLongintParam(), SCIPgetNNodes(), SCIPgetNodeLowerbound(), SCIPgetNVars(), SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPgetStatus(), SubscipData::subscip, and SubscipData::subvars.
Referenced by subscipdataFreeSubscip().
◆ changeSubvariableObjective()
|
static |
create the objective function based on the user selection
- Parameters
-
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 693 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().
◆ SCIP_DECL_EVENTEXEC()
|
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 758 of file heur_lpface.c.
Referenced by changeSubvariableObjective().
◆ setupSubscipLpface()
|
static |
setup and solve the subproblem and catch the return code
- Parameters
-
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 783 of file heur_lpface.c.
References changeSubvariableObjective(), FALSE, NULL, 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().
◆ solveSubscipLpface()
|
static |
setup and solve the subproblem and catch the return code
- Parameters
-
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 878 of file heur_lpface.c.
References createNewSol(), EVENTHDLR_DESC, EVENTHDLR_NAME, FALSE, HEUR_NAME, NULL, 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().
◆ SCIP_DECL_HEURCOPY()
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 1007 of file heur_lpface.c.
Referenced by solveSubscipLpface().
◆ SCIP_DECL_HEURFREE()
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 1021 of file heur_lpface.c.
◆ SCIP_DECL_HEURINIT()
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 1041 of file heur_lpface.c.
◆ SCIP_DECL_HEURINITSOL()
|
static |
solving process initialization method of primal heuristic (called when branch and bound process is about to begin)
Definition at line 1067 of file heur_lpface.c.
◆ SCIP_DECL_HEUREXITSOL()
|
static |
solving process deinitialization method of primal heuristic (called before branch and bound process is exiting)
Definition at line 1092 of file heur_lpface.c.
◆ SCIP_DECL_HEUREXEC()
|
static |
execution method of primal heuristic
Definition at line 1143 of file heur_lpface.c.