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 SCIP_HEURDISPCHAR_LNS |
#define | HEUR_PRIORITY -1104010 |
#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 |
#define HEUR_NAME "lpface" |
Definition at line 66 of file heur_lpface.c.
#define HEUR_DESC "LNS heuristic that searches the optimal LP face inside a sub-MIP" |
Definition at line 67 of file heur_lpface.c.
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
Definition at line 68 of file heur_lpface.c.
#define HEUR_PRIORITY -1104010 |
Definition at line 69 of file heur_lpface.c.
#define HEUR_FREQ 15 |
Definition at line 70 of file heur_lpface.c.
#define HEUR_FREQOFS 0 |
Definition at line 71 of file heur_lpface.c.
#define HEUR_MAXDEPTH -1 |
Definition at line 72 of file heur_lpface.c.
#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE |
Definition at line 73 of file heur_lpface.c.
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 74 of file heur_lpface.c.
#define DEFAULT_MAXNODES 5000LL |
maximum number of nodes to regard in the subproblem
Definition at line 76 of file heur_lpface.c.
#define DEFAULT_MINNODES 50LL |
minimum number of nodes to regard in the subproblem
Definition at line 77 of file heur_lpface.c.
#define DEFAULT_MINFIXINGRATE 0.1 |
required percentage of fixed integer variables in sub-MIP to run
Definition at line 78 of file heur_lpface.c.
#define DEFAULT_NODESOFS 200LL |
number of nodes added to the contingent of the total nodes
Definition at line 79 of file heur_lpface.c.
#define DEFAULT_NODESQUOT 0.1 |
subproblem nodes in relation to nodes of the original problem
Definition at line 80 of file heur_lpface.c.
#define DEFAULT_LPLIMFAC 2.0 |
factor by which the limit on the number of LP depends on the node limit
Definition at line 81 of file heur_lpface.c.
#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 82 of file heur_lpface.c.
#define DEFAULT_COPYCUTS TRUE |
if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?
Definition at line 84 of file heur_lpface.c.
#define DEFAULT_DUALBASISEQUATIONS FALSE |
should the dually nonbasic rows be turned into equations?
Definition at line 86 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
#define DEFAULT_KEEPSUBSCIP FALSE |
should the heuristic continue solving the same sub-SCIP?
Definition at line 87 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 88 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
#define EVENTHDLR_NAME "Lpface" |
Definition at line 91 of file heur_lpface.c.
#define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" |
Definition at line 92 of file heur_lpface.c.
#define heurExitLpface NULL |
Definition at line 1068 of file heur_lpface.c.
Referenced by SCIPincludeHeurLpface().
typedef struct SubscipData SUBSCIPDATA |
Definition at line 106 of file heur_lpface.c.
|
static |
determine variable fixings for sub-SCIP based on reduced costs
scip | SCIP data structure |
heurdata | primal heuristic data |
fixvars | buffer to store variables that should be fixed |
fixvals | buffer to store corresponding fixing values |
nfixvars | pointer to store number of variables that should be fixed |
success | pointer to store whether enough integer variables were fixed |
Definition at line 146 of file heur_lpface.c.
References assert(), heurdata, i, MAX, nbinvars, nintvars, NULL, nvars, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPdebugMsg, SCIPgetColRedcost(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPisDualfeasZero(), SCIPisFeasEQ(), SCIPisInfinity(), SCIPvarGetCol(), SCIPvarGetLbGlobal(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPvarIsIntegral(), SCIPvarIsRelaxationOnly(), var, and vars.
Referenced by SCIP_DECL_HEUREXEC().
|
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 236 of file heur_lpface.c.
References assert(), FALSE, i, NULL, SCIP_Bool, 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(), and TRUE.
Referenced by setupSubproblem().
|
static |
create the LP face subproblem constraints
scip | original SCIP data structure |
subscip | SCIP data structure for the subproblem |
subvars | the variables of the subproblem |
heurdata | primal heuristic data |
Definition at line 331 of file heur_lpface.c.
References assert(), createRows(), FALSE, heurdata, i, NULL, nvars, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCoefLinear(), SCIPaddCons(), SCIPcreateConsLinear(), SCIPgetLowerbound(), SCIPgetNObjVars(), SCIPgetNVars(), SCIPgetVars(), SCIPisZero(), SCIPreleaseCons(), SCIPvarGetObj(), TRUE, and vars.
Referenced by setupSubscipLpface().
|
static |
updates heurdata after an unsuccessful run of lpface
scip | original SCIP data structure |
heurdata | primal heuristic data |
Definition at line 380 of file heur_lpface.c.
References heurdata, SCIP_LONGINT_MAX, and SCIPgetNNodes().
Referenced by 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 394 of file heur_lpface.c.
References heurdata, MIN, NULL, SCIP_Longint, SCIPgetNNodes(), and SCIPheurGetNCalls().
Referenced by SCIP_DECL_HEUREXEC(), and setSubscipLimits().
|
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 426 of file heur_lpface.c.
References assert(), calcNodeLimit(), FALSE, heurdata, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPgetBoolParam(), SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetNNodes(), SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPisInfinity(), SCIPsetLongintParam(), SCIPsetRealParam(), and TRUE.
Referenced by solveSubscipLpface().
|
static |
sets all one-time parameter settings like search strategy, but no limits
subscip | data structure of the sub-problem |
Definition at line 488 of file heur_lpface.c.
References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIPfindBranchrule(), SCIPfindNodesel(), SCIPisParamFixed(), SCIPsetBoolParam(), SCIPsetCharParam(), SCIPsetIntParam(), SCIPsetPresolving(), SCIPsetSeparating(), SCIPsetSubscipsOff(), and TRUE.
Referenced by setupSubscipLpface().
|
static |
reset the sub-SCIP data to its default values
subscipdata | data structure of the sub-problem |
Definition at line 544 of file heur_lpface.c.
References SubscipData::nsubvars, NULL, SubscipData::objbound, SCIP_INVALID, SubscipData::subscip, and SubscipData::subvars.
Referenced by SCIP_DECL_HEUREXEC(), SCIP_DECL_HEURINITSOL(), and subscipdataFreeSubscip().
|
static |
free the stored sub-SCIP information
scip | original SCIP data structure |
subscipdata | data structure of the sub-problem |
Definition at line 556 of file heur_lpface.c.
References assert(), SubscipData::nsubvars, NULL, SCIP_CALL, SCIP_OKAY, SCIPfree(), SCIPfreeBlockMemoryArray, SubscipData::subscip, subscipdataReset(), and SubscipData::subvars.
Referenced by SCIP_DECL_HEUREXEC(), and SCIP_DECL_HEUREXITSOL().
|
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 585 of file heur_lpface.c.
References assert(), SubscipData::nsubvars, NULL, nvars, SubscipData::objbound, SCIP_CALL, SCIP_OKAY, SCIPduplicateBlockMemoryArray, SCIPgetCurrentNode(), SCIPgetNodeLowerbound(), SCIPgetNVars(), SubscipData::subscip, and SubscipData::subvars.
Referenced by SCIP_DECL_HEUREXEC().
|
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 643 of file heur_lpface.c.
References heurdata, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHDIR_UPWARDS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPchgVarObj(), SCIPfrac(), SCIPgetVarAvgInferences(), SCIPvarGetLPSol(), SCIPvarGetObj(), SCIPvarGetRootSol(), and var.
Referenced by setupSubscipLpface().
|
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 708 of file heur_lpface.c.
References assert(), EVENTHDLR_NAME, heurdata, NULL, SCIP_CALL, SCIP_EVENTTYPE_LPSOLVED, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIPdebugMsg, SCIPeventGetType(), SCIPeventhdlrGetName(), SCIPgetNLPs(), and SCIPinterruptSolve().
|
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 |
fixvars | variables that should be fixed |
fixvals | corresponding fixing values |
nfixvars | number of variables that should be fixed |
nvars | number of original problem's variables |
Definition at line 733 of file heur_lpface.c.
References assert(), changeSubvariableObjective(), FALSE, heurdata, i, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPblkmem(), SCIPcopyConsCompression(), SCIPcopyCuts(), SCIPcopyParamSettings(), SCIPcopyPlugins(), SCIPcopyVars(), SCIPcreateProbBasic(), SCIPgetProbName(), SCIPgetSubscipDepth(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPsetIntParam(), SCIPsetSubscipDepth(), SCIPsnprintf(), setSubscipParameters(), setupSubproblem(), TRUE, valid, and vars.
Referenced by SCIP_DECL_HEUREXEC().
|
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 817 of file heur_lpface.c.
References assert(), EVENTHDLR_DESC, EVENTHDLR_NAME, FALSE, HEUR_NAME, heurdata, NULL, result, SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIP_EVENTTYPE_LPSOLVED, SCIP_FOUNDSOL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIP_Real, SCIP_STATUS_INFEASIBLE, SCIPcatchEvent(), SCIPdebug, SCIPdebugMsg, SCIPerrorMessage, SCIPgetBestSol(), SCIPgetNLPIterations(), SCIPgetNNodes(), SCIPgetNSols(), SCIPgetPresolvingTime(), SCIPgetStatus(), SCIPincludeEventhdlrBasic(), SCIPinfoMessage(), SCIPprintStatistics(), SCIPsolGetIndex(), SCIPsolve(), SCIPtransformProb(), SCIPtranslateSubSols(), SCIPwriteOrigProblem(), SCIPwriteParams(), setSubscipLimits(), TRUE, and updateFailureStatistic().
Referenced by SCIP_DECL_HEUREXEC().
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 937 of file heur_lpface.c.
References assert(), HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurLpface().
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 951 of file heur_lpface.c.
References assert(), heurdata, NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), and SCIPheurSetData().
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 971 of file heur_lpface.c.
References assert(), heurdata, NULL, SCIP_OKAY, SCIP_STATUS_UNKNOWN, and SCIPheurGetData().
|
static |
solving process initialization method of primal heuristic (called when branch and bound process is about to begin)
Definition at line 997 of file heur_lpface.c.
References assert(), heurdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPheurGetData(), SCIPinfinity(), and subscipdataReset().
|
static |
solving process deinitialization method of primal heuristic (called before branch and bound process is exiting)
Definition at line 1022 of file heur_lpface.c.
References assert(), heurdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), and subscipdataFreeSubscip().
|
static |
execution method of primal heuristic
Definition at line 1073 of file heur_lpface.c.
References assert(), calcNodeLimit(), determineVariableFixings(), heurdata, nbinvars, nintvars, NULL, nvars, result, SCIP_Bool, SCIP_CALL, SCIP_DELAYED, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPallColsInLP(), SCIPallocBufferArray, SCIPcreate(), SCIPdebug, SCIPdebugMsg, SCIPfree(), SCIPfreeBufferArray, SCIPgetCurrentNode(), SCIPgetDepth(), SCIPgetLowerbound(), SCIPgetLowerboundRoot(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetNNodes(), SCIPgetNodeLowerbound(), SCIPgetVarsData(), SCIPheurGetData(), SCIPisEQ(), SCIPisGE(), SCIPisGT(), SCIPisInfinity(), SCIPisIntegral(), SCIPisLE(), SCIPisLPRelax(), SCIPisLT(), SCIPisObjIntegral(), SCIPisStopped(), SCIPnodeGetLowerbound(), SCIPnodeGetParent(), SCIPretransformObj(), setupSubscipLpface(), solveSubscipLpface(), subscipdataCopySubscip(), subscipdataFreeSubscip(), subscipdataReset(), and vars.