Detailed Description
improvement heuristic which uses an auxiliary objective instead of the original objective function which is itself added as a constraint to a sub-SCIP instance. The heuristic was presented by Matteo Fischetti and Michele Monaci.
Definition in file heur_proximity.c.
#include "blockmemshell/memory.h"
#include "scip/cons_linear.h"
#include "scip/heuristics.h"
#include "scip/heur_proximity.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_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_nlp.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_var.h"
#include <string.h>
Go to the source code of this file.
Macros | |
#define | HEUR_NAME "proximity" |
#define | HEUR_DESC "heuristic trying to improve the incumbent by an auxiliary proximity objective function" |
#define | HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
#define | HEUR_PRIORITY -2000000 |
#define | HEUR_FREQ -1 |
#define | HEUR_FREQOFS 0 |
#define | HEUR_MAXDEPTH -1 |
#define | HEUR_TIMING SCIP_HEURTIMING_AFTERNODE |
#define | HEUR_USESSUBSCIP TRUE |
#define | EVENTHDLR_NAME "Proximity" |
#define | EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" |
#define | DEFAULT_MAXNODES 10000LL |
#define | DEFAULT_MINIMPROVE 0.02 |
#define | DEFAULT_MINGAP 0.01 |
#define | DEFAULT_MINNODES 1LL |
#define | DEFAULT_MINLPITERS 200LL |
#define | DEFAULT_MAXLPITERS 100000LL |
#define | DEFAULT_NODESOFS 50LL |
#define | DEFAULT_WAITINGNODES 100LL |
#define | DEFAULT_NODESQUOT 0.1 |
#define | DEFAULT_USELPROWS FALSE |
#define | DEFAULT_BINVARQUOT 0.1 |
#define | DEFAULT_RESTART TRUE |
#define | DEFAULT_USEFINALLP FALSE |
#define | DEFAULT_LPITERSQUOT 0.2 |
#define | DEFAULT_USEUCT FALSE |
Macro Definition Documentation
◆ HEUR_NAME
#define HEUR_NAME "proximity" |
Definition at line 57 of file heur_proximity.c.
Referenced by SCIP_DECL_HEURCOPY(), SCIPapplyProximity(), SCIPdeleteSubproblemProximity(), and SCIPincludeHeurProximity().
◆ HEUR_DESC
#define HEUR_DESC "heuristic trying to improve the incumbent by an auxiliary proximity objective function" |
Definition at line 58 of file heur_proximity.c.
Referenced by SCIPincludeHeurProximity().
◆ HEUR_DISPCHAR
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
Definition at line 59 of file heur_proximity.c.
Referenced by SCIPincludeHeurProximity().
◆ HEUR_PRIORITY
#define HEUR_PRIORITY -2000000 |
Definition at line 60 of file heur_proximity.c.
Referenced by SCIPincludeHeurProximity().
◆ HEUR_FREQ
#define HEUR_FREQ -1 |
Definition at line 61 of file heur_proximity.c.
Referenced by SCIPincludeHeurProximity().
◆ HEUR_FREQOFS
#define HEUR_FREQOFS 0 |
Definition at line 62 of file heur_proximity.c.
Referenced by SCIPincludeHeurProximity().
◆ HEUR_MAXDEPTH
#define HEUR_MAXDEPTH -1 |
Definition at line 63 of file heur_proximity.c.
Referenced by SCIPincludeHeurProximity().
◆ HEUR_TIMING
#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE |
Definition at line 64 of file heur_proximity.c.
Referenced by SCIPincludeHeurProximity().
◆ HEUR_USESSUBSCIP
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 65 of file heur_proximity.c.
Referenced by SCIPincludeHeurProximity().
◆ EVENTHDLR_NAME
#define EVENTHDLR_NAME "Proximity" |
Definition at line 68 of file heur_proximity.c.
Referenced by SCIP_DECL_EVENTEXEC(), and SCIPapplyProximity().
◆ EVENTHDLR_DESC
#define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" |
Definition at line 69 of file heur_proximity.c.
Referenced by SCIPapplyProximity().
◆ DEFAULT_MAXNODES
#define DEFAULT_MAXNODES 10000LL |
maximum number of nodes to regard in the subproblem
Definition at line 73 of file heur_proximity.c.
Referenced by SCIPincludeHeurProximity().
◆ DEFAULT_MINIMPROVE
#define DEFAULT_MINIMPROVE 0.02 |
factor by which proximity should at least improve the incumbent
Definition at line 74 of file heur_proximity.c.
Referenced by SCIPincludeHeurProximity().
◆ DEFAULT_MINGAP
#define DEFAULT_MINGAP 0.01 |
minimum primal-dual gap for which the heuristic is executed
Definition at line 75 of file heur_proximity.c.
Referenced by SCIPincludeHeurProximity().
◆ DEFAULT_MINNODES
#define DEFAULT_MINNODES 1LL |
minimum number of nodes to regard in the subproblem
Definition at line 76 of file heur_proximity.c.
Referenced by SCIPincludeHeurProximity().
◆ DEFAULT_MINLPITERS
#define DEFAULT_MINLPITERS 200LL |
minimum number of LP iterations to perform in one sub-mip
Definition at line 77 of file heur_proximity.c.
Referenced by SCIPincludeHeurProximity().
◆ DEFAULT_MAXLPITERS
#define DEFAULT_MAXLPITERS 100000LL |
maximum number of LP iterations to be performed in the subproblem
Definition at line 78 of file heur_proximity.c.
Referenced by SCIPincludeHeurProximity().
◆ DEFAULT_NODESOFS
#define DEFAULT_NODESOFS 50LL |
number of nodes added to the contingent of the total nodes
Definition at line 79 of file heur_proximity.c.
Referenced by SCIPincludeHeurProximity().
◆ DEFAULT_WAITINGNODES
#define DEFAULT_WAITINGNODES 100LL |
default waiting nodes since last incumbent before heuristic is executed
Definition at line 80 of file heur_proximity.c.
Referenced by SCIPincludeHeurProximity().
◆ DEFAULT_NODESQUOT
#define DEFAULT_NODESQUOT 0.1 |
default quotient of sub-MIP nodes with respect to number of processed nodes
Definition at line 81 of file heur_proximity.c.
Referenced by SCIPincludeHeurProximity().
◆ DEFAULT_USELPROWS
#define DEFAULT_USELPROWS FALSE |
should subproblem be constructed based on LP row information?
Definition at line 82 of file heur_proximity.c.
Referenced by SCIPincludeHeurProximity().
◆ DEFAULT_BINVARQUOT
#define DEFAULT_BINVARQUOT 0.1 |
default threshold for percentage of binary variables required to start
Definition at line 83 of file heur_proximity.c.
Referenced by SCIPincludeHeurProximity().
◆ DEFAULT_RESTART
#define DEFAULT_RESTART TRUE |
should the heuristic immediately run again on its newly found solution?
Definition at line 84 of file heur_proximity.c.
Referenced by SCIPincludeHeurProximity().
◆ DEFAULT_USEFINALLP
#define DEFAULT_USEFINALLP FALSE |
should the heuristic solve a final LP in case of continuous objective variables?
Definition at line 85 of file heur_proximity.c.
Referenced by SCIPincludeHeurProximity().
◆ DEFAULT_LPITERSQUOT
#define DEFAULT_LPITERSQUOT 0.2 |
default quotient of sub-MIP LP iterations with respect to LP iterations so far
Definition at line 86 of file heur_proximity.c.
Referenced by SCIPincludeHeurProximity().
◆ DEFAULT_USEUCT
#define DEFAULT_USEUCT FALSE |
should uct node selection be used at the beginning of the search?
Definition at line 87 of file heur_proximity.c.
Referenced by SCIPincludeHeurProximity().
Function Documentation
◆ solveLp()
|
static |
optimizes the continuous variables in an LP diving by fixing all integer variables to the given solution values
- Parameters
-
scip SCIP data structure sol candidate solution for which continuous variables should be optimized success was the dive successful?
Definition at line 132 of file heur_proximity.c.
References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPchgVarLbDive(), SCIPchgVarUbDive(), SCIPdebugMsg, SCIPendDive(), SCIPgetLPSolstat(), SCIPgetNLPIterations(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPisNLPConstructed(), SCIPlinkLPSol(), SCIPsolveDiveLP(), SCIPstartDive(), SCIPtrySol(), SCIPvarGetLbGlobal(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPwarningMessage(), and TRUE.
Referenced by createNewSol().
◆ 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 proximity heuristic structure subsol solution of the subproblem usefinallp should continuous variables be optimized by a final LP success used to store whether new solution was found or not
Definition at line 218 of file heur_proximity.c.
References FALSE, MAX, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPallocBufferArray, SCIPcreateSol(), SCIPfreeBufferArray, SCIPfreeSol(), SCIPgetObjNorm(), SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPisLPConstructed(), SCIPisZero(), SCIPsetSolVal(), SCIPsetSolVals(), SCIPstatisticMessage, SCIPtrySol(), SCIPvarGetLbLocal(), SCIPvarGetObj(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), solveLp(), and TRUE.
Referenced by SCIPapplyProximity().
◆ setupSubproblem()
|
static |
sets solving parameters for the subproblem created by the heuristic
- Parameters
-
heurdata heuristic data structure subscip copied SCIP data structure
Definition at line 314 of file heur_proximity.c.
References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIPfindBranchrule(), SCIPfindConshdlr(), SCIPfindNodesel(), SCIPisParamFixed(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetPresolving(), SCIPsetSeparating(), SCIPsetSubscipsOff(), and TRUE.
Referenced by SCIPapplyProximity().
◆ deleteSubproblem()
|
static |
frees the subproblem
- Parameters
-
scip SCIP data structure heurdata heuristic data
Definition at line 399 of file heur_proximity.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPfree(), SCIPfreeBlockMemoryArray, SCIPhashmapFree(), and SCIPreleaseCons().
Referenced by SCIP_DECL_HEUREXEC(), SCIP_DECL_HEUREXITSOL(), SCIPapplyProximity(), and SCIPdeleteSubproblemProximity().
◆ SCIP_DECL_EVENTEXEC()
|
static |
exec the event handler
We interrupt the solution process.
Definition at line 432 of file heur_proximity.c.
References EVENTHDLR_NAME, NULL, SCIP_CALL, SCIP_EVENTTYPE_NODESOLVED, SCIP_LPSOLSTAT_ITERLIMIT, SCIP_OKAY, SCIPeventGetType(), SCIPeventhdlrGetName(), SCIPgetLPSolstat(), SCIPgetNLPIterations(), and SCIPinterruptSolve().
◆ SCIP_DECL_HEURCOPY()
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 460 of file heur_proximity.c.
References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurProximity().
◆ SCIP_DECL_HEURFREE()
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 474 of file heur_proximity.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 495 of file heur_proximity.c.
References NULL, SCIP_OKAY, and SCIPheurGetData().
◆ SCIP_DECL_HEUREXITSOL()
|
static |
solution process exiting method of proximity heuristic
Definition at line 524 of file heur_proximity.c.
References deleteSubproblem(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPheurGetData().
◆ SCIP_DECL_HEUREXEC()
|
static |
execution method of primal heuristic
Definition at line 544 of file heur_proximity.c.
References deleteSubproblem(), FALSE, MAX, nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_Longint, SCIP_OKAY, SCIPapplyProximity(), SCIPdebugMsg, SCIPdeleteSubproblemProximity(), SCIPgetNBinVars(), SCIPgetNNodes(), SCIPgetNObjVars(), SCIPgetNRootFirstLPIterations(), SCIPgetNVars(), SCIPheurGetData(), SCIPisStopped(), and TRUE.