Local branching heuristic according to Fischetti and Lodi.
Definition in file heur_localbranching.c.
#include <assert.h>
#include <string.h>
#include "scip/scip.h"
#include "scip/cons_linear.h"
#include "scip/scipdefplugins.h"
#include "scip/heur_localbranching.h"
#include "scip/pub_misc.h"
Go to the source code of this file.
Macros | |
#define | HEUR_NAME "localbranching" |
#define | HEUR_DESC "local branching heuristic by Fischetti and Lodi" |
#define | HEUR_DISPCHAR 'L' |
#define | HEUR_PRIORITY -1102000 |
#define | HEUR_FREQ -1 |
#define | HEUR_FREQOFS 0 |
#define | HEUR_MAXDEPTH -1 |
#define | HEUR_TIMING SCIP_HEURTIMING_AFTERNODE |
#define | HEUR_USESSUBSCIP TRUE |
#define | DEFAULT_NEIGHBORHOODSIZE 18 /* radius of the incumbents neighborhood to be searched */ |
#define | DEFAULT_NODESOFS 1000 /* number of nodes added to the contingent of the total nodes */ |
#define | DEFAULT_MAXNODES 10000 /* maximum number of nodes to regard in the subproblem */ |
#define | DEFAULT_MINIMPROVE 0.01 /* factor by which localbranching should at least improve the incumbent */ |
#define | DEFAULT_MINNODES 1000 /* minimum number of nodes required to start the subproblem */ |
#define | DEFAULT_NODESQUOT 0.05 /* contingent of sub problem nodes in relation to original nodes */ |
#define | DEFAULT_LPLIMFAC 1.5 /* factor by which the limit on the number of LP depends on the node limit */ |
#define | DEFAULT_NWAITINGNODES 200 /* number of nodes without incumbent change that heuristic should wait */ |
#define | DEFAULT_USELPROWS |
#define | DEFAULT_COPYCUTS |
#define | DEFAULT_BESTSOLLIMIT 3 /* limit on number of improving incumbent solutions in sub-CIP */ |
#define | DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */ |
#define | EVENTHDLR_NAME "Localbranching" |
#define | EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" |
#define | EXECUTE 0 |
#define | WAITFORNEWSOL 1 |
Functions | |
static SCIP_RETCODE | addLocalBranchingConstraint (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEURDATA *heurdata) |
static SCIP_RETCODE | createNewSol (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_Bool *success) |
static | SCIP_DECL_EVENTEXEC (eventExecLocalbranching) |
static | SCIP_DECL_HEURCOPY (heurCopyLocalbranching) |
static | SCIP_DECL_HEURFREE (heurFreeLocalbranching) |
static | SCIP_DECL_HEURINIT (heurInitLocalbranching) |
static SCIP_RETCODE | setupAndSolveSubscipLocalbranching (SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_Longint nsubnodes, SCIP_RESULT *result) |
static | SCIP_DECL_HEUREXEC (heurExecLocalbranching) |
SCIP_RETCODE | SCIPincludeHeurLocalbranching (SCIP *scip) |
#define HEUR_NAME "localbranching" |
Definition at line 32 of file heur_localbranching.c.
Referenced by SCIP_DECL_HEURCOPY(), SCIPincludeHeurLocalbranching(), and setupAndSolveSubscipLocalbranching().
#define HEUR_DESC "local branching heuristic by Fischetti and Lodi" |
Definition at line 33 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
#define HEUR_DISPCHAR 'L' |
Definition at line 34 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
#define HEUR_PRIORITY -1102000 |
Definition at line 35 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
#define HEUR_FREQ -1 |
Definition at line 36 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
#define HEUR_FREQOFS 0 |
Definition at line 37 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
#define HEUR_MAXDEPTH -1 |
Definition at line 38 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE |
Definition at line 39 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 40 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
#define DEFAULT_NEIGHBORHOODSIZE 18 /* radius of the incumbents neighborhood to be searched */ |
Definition at line 42 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
#define DEFAULT_NODESOFS 1000 /* number of nodes added to the contingent of the total nodes */ |
Definition at line 43 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
#define DEFAULT_MAXNODES 10000 /* maximum number of nodes to regard in the subproblem */ |
Definition at line 44 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
#define DEFAULT_MINIMPROVE 0.01 /* factor by which localbranching should at least improve the incumbent */ |
Definition at line 45 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
#define DEFAULT_MINNODES 1000 /* minimum number of nodes required to start the subproblem */ |
Definition at line 46 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
#define DEFAULT_NODESQUOT 0.05 /* contingent of sub problem nodes in relation to original nodes */ |
Definition at line 47 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
#define DEFAULT_LPLIMFAC 1.5 /* factor by which the limit on the number of LP depends on the node limit */ |
Definition at line 48 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
#define DEFAULT_NWAITINGNODES 200 /* number of nodes without incumbent change that heuristic should wait */ |
Definition at line 49 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
#define DEFAULT_USELPROWS |
Definition at line 50 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
#define DEFAULT_COPYCUTS |
Definition at line 52 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
#define DEFAULT_BESTSOLLIMIT 3 /* limit on number of improving incumbent solutions in sub-CIP */ |
Definition at line 55 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
#define DEFAULT_USEUCT FALSE /* should uct node selection be used at the beginning of the search? */ |
Definition at line 56 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
#define EVENTHDLR_NAME "Localbranching" |
Definition at line 59 of file heur_localbranching.c.
Referenced by SCIP_DECL_EVENTEXEC(), and setupAndSolveSubscipLocalbranching().
#define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" |
Definition at line 60 of file heur_localbranching.c.
Referenced by setupAndSolveSubscipLocalbranching().
#define EXECUTE 0 |
Definition at line 63 of file heur_localbranching.c.
Referenced by SCIP_DECL_HEUREXEC(), and setupAndSolveSubscipLocalbranching().
#define WAITFORNEWSOL 1 |
Definition at line 64 of file heur_localbranching.c.
Referenced by SCIP_DECL_HEUREXEC(), SCIP_DECL_HEURINIT(), and setupAndSolveSubscipLocalbranching().
|
static |
create the extra constraint of local branching and add it to subscip
scip | SCIP data structure of the original problem |
subscip | SCIP data structure of the subproblem |
subvars | variables of the subproblem |
heurdata | heuristic's data structure |
Definition at line 104 of file heur_localbranching.c.
References FALSE, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPaddCons(), SCIPallocBufferArray, SCIPcreateConsLinear(), SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetProbName(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPisFeasEQ(), SCIPisFeasIntegral(), SCIPreleaseCons(), SCIPsnprintf(), SCIPvarGetType(), and TRUE.
Referenced by setupAndSolveSubscipLocalbranching().
|
static |
creates a new solution for the original problem by copying the solution of the subproblem
scip | SCIP data structure of the original problem |
subscip | SCIP data structure of the subproblem |
subvars | the variables of the subproblem |
heur | the Localbranching heuristic |
subsol | solution of the subproblem |
success | pointer to store, whether new solution was found |
Definition at line 175 of file heur_localbranching.c.
References FALSE, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcreateSol(), SCIPfreeBufferArray, SCIPgetNOrigVars(), SCIPgetSolVals(), SCIPgetVarsData(), SCIPsetSolVals(), SCIPtrySolFree(), and TRUE.
Referenced by setupAndSolveSubscipLocalbranching().
|
static |
Definition at line 225 of file heur_localbranching.c.
References EVENTHDLR_NAME, SCIP_CALL, SCIP_EVENTTYPE_LPSOLVED, SCIP_OKAY, SCIPdebugMsg, SCIPeventGetType(), SCIPeventhdlrGetName(), SCIPgetNLPs(), and SCIPinterruptSolve().
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 255 of file heur_localbranching.c.
References HEUR_NAME, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurLocalbranching().
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 269 of file heur_localbranching.c.
References SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), and SCIPheurSetData().
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 290 of file heur_localbranching.c.
References SCIP_OKAY, SCIPheurGetData(), and WAITFORNEWSOL.
|
static |
todo setup And Solve Subscip
scip | SCIP data structure |
subscip | the subproblem created by localbranching |
heur | localbranching heuristic |
nsubnodes | nodelimit for subscip |
result | result pointer |
Definition at line 314 of file heur_localbranching.c.
References addLocalBranchingConstraint(), createNewSol(), EVENTHDLR_DESC, EVENTHDLR_NAME, EXECUTE, FALSE, HEUR_NAME, MAX, SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIP_DIDNOTRUN, SCIP_EVENTTYPE_LPSOLVED, SCIP_FOUNDSOL, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIP_PLUGINNOTFOUND, SCIP_Real, SCIP_STATUS_BESTSOLLIMIT, SCIP_STATUS_GAPLIMIT, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_INFORUNBD, SCIP_STATUS_MEMLIMIT, SCIP_STATUS_NODELIMIT, SCIP_STATUS_OPTIMAL, SCIP_STATUS_RESTARTLIMIT, SCIP_STATUS_SOLLIMIT, SCIP_STATUS_STALLNODELIMIT, SCIP_STATUS_TIMELIMIT, SCIP_STATUS_TOTALNODELIMIT, SCIP_STATUS_UNBOUNDED, SCIP_STATUS_UNKNOWN, SCIP_STATUS_USERINTERRUPT, SCIPallocBufferArray, SCIPblkmem(), SCIPcatchEvent(), SCIPcopyLargeNeighborhoodSearch(), SCIPcopyLimits(), SCIPdebug, SCIPdebugMsg, SCIPdropEvent(), SCIPerrorMessage, SCIPfindBranchrule(), SCIPfindConshdlr(), SCIPfindNodesel(), SCIPfreeBufferArray, SCIPgetLowerbound(), SCIPgetNNodes(), SCIPgetNSols(), SCIPgetSolOrigObj(), SCIPgetSols(), SCIPgetStatus(), SCIPgetUpperbound(), SCIPgetVarsData(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPheurGetData(), SCIPincludeEventhdlrBasic(), SCIPisInfinity(), SCIPisParamFixed(), SCIPprintStatistics(), SCIPsetBoolParam(), SCIPsetCharParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetObjlimit(), SCIPsetPresolving(), SCIPsetSeparating(), SCIPsetSubscipsOff(), SCIPsolve(), SCIPsumepsilon(), SCIPtransformProb(), TRUE, and WAITFORNEWSOL.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
execution method of primal heuristic
Definition at line 591 of file heur_localbranching.c.
References EXECUTE, SCIP_Bool, SCIP_CALL, SCIP_DELAYED, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_OKAY, SCIPcheckCopyLimits(), SCIPcreate(), SCIPdebugMsg, SCIPfree(), SCIPgetBestSol(), SCIPgetNBinVars(), SCIPgetNNodes(), SCIPgetNSols(), SCIPgetSolNodenum(), SCIPheurGetData(), SCIPheurGetName(), SCIPheurGetNBestSolsFound(), SCIPheurGetNCalls(), SCIPisStopped(), SCIPsolGetHeur(), SCIPsolIsOriginal(), setupAndSolveSubscipLocalbranching(), and WAITFORNEWSOL.