Detailed Description
Local branching heuristic according to Fischetti and Lodi.
Definition in file heur_localbranching.c.
#include "blockmemshell/memory.h"
#include "scip/cons_linear.h"
#include "scip/heuristics.h"
#include "scip/heur_localbranching.h"
#include "scip/pub_event.h"
#include "scip/pub_heur.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_sol.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_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 <string.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 SCIP_HEURDISPCHAR_LNS |
#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 | EVENTHDLR_NAME "Localbranching" |
#define | EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" |
#define | EXECUTE 0 |
#define | WAITFORNEWSOL 1 |
Functions | |
static SCIP_RETCODE | addLocalbranchingConstraintAndObjcutoff (SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **subvars) |
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) |
Macro Definition Documentation
◆ HEUR_NAME
#define HEUR_NAME "localbranching" |
Definition at line 52 of file heur_localbranching.c.
Referenced by SCIP_DECL_HEURCOPY(), SCIPincludeHeurLocalbranching(), and setupAndSolveSubscipLocalbranching().
◆ HEUR_DESC
#define HEUR_DESC "local branching heuristic by Fischetti and Lodi" |
Definition at line 53 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
◆ HEUR_DISPCHAR
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
Definition at line 54 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
◆ HEUR_PRIORITY
#define HEUR_PRIORITY -1102000 |
Definition at line 55 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
◆ HEUR_FREQ
#define HEUR_FREQ -1 |
Definition at line 56 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
◆ HEUR_FREQOFS
#define HEUR_FREQOFS 0 |
Definition at line 57 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
◆ HEUR_MAXDEPTH
#define HEUR_MAXDEPTH -1 |
Definition at line 58 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
◆ HEUR_TIMING
#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE |
Definition at line 59 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
◆ HEUR_USESSUBSCIP
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 60 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
◆ DEFAULT_NEIGHBORHOODSIZE
#define DEFAULT_NEIGHBORHOODSIZE 18 /* radius of the incumbents neighborhood to be searched */ |
Definition at line 62 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
◆ DEFAULT_NODESOFS
#define DEFAULT_NODESOFS 1000 /* number of nodes added to the contingent of the total nodes */ |
Definition at line 63 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
◆ DEFAULT_MAXNODES
#define DEFAULT_MAXNODES 10000 /* maximum number of nodes to regard in the subproblem */ |
Definition at line 64 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
◆ DEFAULT_MINIMPROVE
#define DEFAULT_MINIMPROVE 0.01 /* factor by which localbranching should at least improve the incumbent */ |
Definition at line 65 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
◆ DEFAULT_MINNODES
#define DEFAULT_MINNODES 1000 /* minimum number of nodes required to start the subproblem */ |
Definition at line 66 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
◆ DEFAULT_NODESQUOT
#define DEFAULT_NODESQUOT 0.05 /* contingent of sub problem nodes in relation to original nodes */ |
Definition at line 67 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
◆ DEFAULT_LPLIMFAC
#define DEFAULT_LPLIMFAC 1.5 /* factor by which the limit on the number of LP depends on the node limit */ |
Definition at line 68 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
◆ DEFAULT_NWAITINGNODES
#define DEFAULT_NWAITINGNODES 200 /* number of nodes without incumbent change that heuristic should wait */ |
Definition at line 69 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
◆ DEFAULT_USELPROWS
#define DEFAULT_USELPROWS |
Definition at line 70 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
◆ DEFAULT_COPYCUTS
#define DEFAULT_COPYCUTS |
Definition at line 72 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
◆ DEFAULT_BESTSOLLIMIT
#define DEFAULT_BESTSOLLIMIT 3 /* limit on number of improving incumbent solutions in sub-CIP */ |
Definition at line 75 of file heur_localbranching.c.
Referenced by SCIPincludeHeurLocalbranching().
◆ EVENTHDLR_NAME
#define EVENTHDLR_NAME "Localbranching" |
Definition at line 78 of file heur_localbranching.c.
Referenced by SCIP_DECL_EVENTEXEC(), and setupAndSolveSubscipLocalbranching().
◆ EVENTHDLR_DESC
#define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" |
Definition at line 79 of file heur_localbranching.c.
Referenced by setupAndSolveSubscipLocalbranching().
◆ EXECUTE
#define EXECUTE 0 |
Definition at line 82 of file heur_localbranching.c.
Referenced by SCIP_DECL_HEUREXEC(), and setupAndSolveSubscipLocalbranching().
◆ WAITFORNEWSOL
#define WAITFORNEWSOL 1 |
Definition at line 83 of file heur_localbranching.c.
Referenced by SCIP_DECL_HEUREXEC(), SCIP_DECL_HEURINIT(), and setupAndSolveSubscipLocalbranching().
Function Documentation
◆ addLocalbranchingConstraintAndObjcutoff()
|
static |
create the extra constraint of local branching and add it to subscip
- Parameters
-
scip SCIP data structure subscip the subproblem created by localbranching heur the local branching heuristic subvars the subproblem variables
Definition at line 122 of file heur_localbranching.c.
References FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPaddCons(), SCIPallocBufferArray, SCIPcreateConsLinear(), SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetLowerbound(), SCIPgetProbName(), SCIPgetSolVal(), SCIPgetUpperbound(), SCIPgetVarsData(), SCIPheurGetData(), SCIPisFeasEQ(), SCIPisFeasIntegral(), SCIPisInfinity(), SCIPreleaseCons(), SCIPsetObjlimit(), SCIPsnprintf(), SCIPsumepsilon(), SCIPvarGetType(), and TRUE.
Referenced by setupAndSolveSubscipLocalbranching().
◆ SCIP_DECL_EVENTEXEC()
|
static |
event handler execution callback to interrupt the solution process
Definition at line 232 of file heur_localbranching.c.
References EVENTHDLR_NAME, NULL, SCIP_CALL, SCIP_EVENTTYPE_LPSOLVED, SCIP_OKAY, SCIPdebugMsg, SCIPeventGetType(), SCIPeventhdlrGetName(), SCIPgetNLPs(), and SCIPinterruptSolve().
◆ SCIP_DECL_HEURCOPY()
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 262 of file heur_localbranching.c.
References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurLocalbranching().
◆ SCIP_DECL_HEURFREE()
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 276 of file heur_localbranching.c.
References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), and SCIPheurSetData().
◆ SCIP_DECL_HEURINIT()
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 297 of file heur_localbranching.c.
References NULL, SCIP_OKAY, SCIPheurGetData(), and WAITFORNEWSOL.
◆ setupAndSolveSubscipLocalbranching()
|
static |
setup And solve local branching subscip
- Parameters
-
scip SCIP data structure subscip the subproblem created by localbranching heur localbranching heuristic nsubnodes nodelimit for subscip result result pointer
Definition at line 321 of file heur_localbranching.c.
References addLocalbranchingConstraintAndObjcutoff(), EVENTHDLR_DESC, EVENTHDLR_NAME, EXECUTE, FALSE, HEUR_NAME, MAX, NULL, SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIP_DIDNOTRUN, SCIP_EVENTTYPE_LPSOLVED, SCIP_FOUNDSOL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, 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_TERMINATE, SCIP_STATUS_TIMELIMIT, SCIP_STATUS_TOTALNODELIMIT, SCIP_STATUS_UNBOUNDED, SCIP_STATUS_UNKNOWN, SCIP_STATUS_USERINTERRUPT, SCIPallocBufferArray, SCIPblkmem(), SCIPcatchEvent(), SCIPcopyLargeNeighborhoodSearch(), SCIPdebug, SCIPdebugMsg, SCIPdropEvent(), SCIPerrorMessage, SCIPfreeBufferArray, SCIPgetNNodes(), SCIPgetStatus(), SCIPgetVarsData(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPheurGetData(), SCIPincludeEventhdlrBasic(), SCIPprintStatistics(), SCIPsetCommonSubscipParams(), SCIPsolve(), SCIPtransformProb(), SCIPtranslateSubSols(), and WAITFORNEWSOL.
Referenced by SCIP_DECL_HEUREXEC().
◆ SCIP_DECL_HEUREXEC()
|
static |
execution method of primal heuristic
Definition at line 489 of file heur_localbranching.c.
References EXECUTE, NULL, 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.