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 |
#define HEUR_NAME "proximity" |
Definition at line 66 of file heur_proximity.c.
#define HEUR_DESC "heuristic trying to improve the incumbent by an auxiliary proximity objective function" |
Definition at line 67 of file heur_proximity.c.
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
Definition at line 68 of file heur_proximity.c.
#define HEUR_PRIORITY -2000000 |
Definition at line 69 of file heur_proximity.c.
#define HEUR_FREQ -1 |
Definition at line 70 of file heur_proximity.c.
#define HEUR_FREQOFS 0 |
Definition at line 71 of file heur_proximity.c.
#define HEUR_MAXDEPTH -1 |
Definition at line 72 of file heur_proximity.c.
#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE |
Definition at line 73 of file heur_proximity.c.
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 74 of file heur_proximity.c.
#define EVENTHDLR_NAME "Proximity" |
Definition at line 77 of file heur_proximity.c.
#define EVENTHDLR_DESC "LP event handler for " HEUR_NAME " heuristic" |
Definition at line 78 of file heur_proximity.c.
#define DEFAULT_MAXNODES 10000LL |
maximum number of nodes to regard in the subproblem
Definition at line 82 of file heur_proximity.c.
#define DEFAULT_MINIMPROVE 0.02 |
factor by which proximity should at least improve the incumbent
Definition at line 83 of file heur_proximity.c.
#define DEFAULT_MINGAP 0.01 |
minimum primal-dual gap for which the heuristic is executed
Definition at line 84 of file heur_proximity.c.
#define DEFAULT_MINNODES 1LL |
minimum number of nodes to regard in the subproblem
Definition at line 85 of file heur_proximity.c.
#define DEFAULT_MINLPITERS 200LL |
minimum number of LP iterations to perform in one sub-mip
Definition at line 86 of file heur_proximity.c.
Referenced by SCIPincludeHeurProximity().
#define DEFAULT_MAXLPITERS 100000LL |
maximum number of LP iterations to be performed in the subproblem
Definition at line 87 of file heur_proximity.c.
Referenced by SCIPincludeHeurProximity(), and SCIPincludeHeurZeroobj().
#define DEFAULT_NODESOFS 50LL |
number of nodes added to the contingent of the total nodes
Definition at line 88 of file heur_proximity.c.
#define DEFAULT_WAITINGNODES 100LL |
default waiting nodes since last incumbent before heuristic is executed
Definition at line 89 of file heur_proximity.c.
#define DEFAULT_NODESQUOT 0.1 |
default quotient of sub-MIP nodes with respect to number of processed nodes
Definition at line 90 of file heur_proximity.c.
#define DEFAULT_USELPROWS FALSE |
should subproblem be constructed based on LP row information?
Definition at line 91 of file heur_proximity.c.
#define DEFAULT_BINVARQUOT 0.1 |
default threshold for percentage of binary variables required to start
Definition at line 92 of file heur_proximity.c.
Referenced by SCIPincludeHeurProximity().
#define DEFAULT_RESTART TRUE |
should the heuristic immediately run again on its newly found solution?
Definition at line 93 of file heur_proximity.c.
Referenced by SCIPincludeHeurProximity().
#define DEFAULT_USEFINALLP FALSE |
should the heuristic solve a final LP in case of continuous objective variables?
Definition at line 94 of file heur_proximity.c.
Referenced by SCIPincludeHeurProximity().
#define DEFAULT_LPITERSQUOT 0.2 |
default quotient of sub-MIP LP iterations with respect to LP iterations so far
Definition at line 95 of file heur_proximity.c.
Referenced by SCIPincludeHeurProximity().
#define DEFAULT_USEUCT FALSE |
should uct node selection be used at the beginning of the search?
Definition at line 96 of file heur_proximity.c.
|
static |
optimizes the continuous variables in an LP diving by fixing all integer variables to the given solution values
scip | SCIP data structure |
sol | candidate solution for which continuous variables should be optimized |
success | was the dive successful? |
Definition at line 141 of file heur_proximity.c.
References assert(), FALSE, lperror, nintvars, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_LONGINT_FORMAT, 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(), sol, TRUE, and vars.
Referenced by createNewSol().
|
static |
creates a new solution for the original problem by copying the solution of the subproblem
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 227 of file heur_proximity.c.
References assert(), FALSE, i, MAX, MIN, NULL, nvars, SCIP_Bool, 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(), TRUE, var, and vars.
Referenced by SCIPapplyProximity().
|
static |
sets solving parameters for the subproblem created by the heuristic
heurdata | heuristic data structure |
subscip | copied SCIP data structure |
Definition at line 323 of file heur_proximity.c.
References assert(), FALSE, heurdata, NULL, SCIP_CALL, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIPfindBranchrule(), SCIPfindNodesel(), SCIPisParamFixed(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetPresolving(), SCIPsetSeparating(), SCIPsetSubscipsOff(), and TRUE.
Referenced by SCIPapplyProximity().
|
static |
frees the subproblem
scip | SCIP data structure |
heurdata | heuristic data |
Definition at line 397 of file heur_proximity.c.
References assert(), heurdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPfree(), SCIPfreeBlockMemoryArray, SCIPhashmapFree(), and SCIPreleaseCons().
Referenced by SCIP_DECL_HEUREXEC(), SCIP_DECL_HEUREXITSOL(), SCIPapplyProximity(), and SCIPdeleteSubproblemProximity().
|
static |
exec the event handler
We interrupt the solution process.
Definition at line 430 of file heur_proximity.c.
References assert(), EVENTHDLR_NAME, heurdata, NULL, SCIP_CALL, SCIP_EVENTTYPE_NODESOLVED, SCIP_LPSOLSTAT_ITERLIMIT, SCIP_OKAY, SCIPeventGetType(), SCIPeventhdlrGetName(), SCIPgetLPSolstat(), SCIPgetNLPIterations(), and SCIPinterruptSolve().
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 458 of file heur_proximity.c.
References assert(), HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurProximity().
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 472 of file heur_proximity.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 493 of file heur_proximity.c.
References assert(), heurdata, NULL, SCIP_OKAY, and SCIPheurGetData().
|
static |
solution process exiting method of proximity heuristic
Definition at line 522 of file heur_proximity.c.
References assert(), deleteSubproblem(), heurdata, NULL, SCIP_CALL, SCIP_OKAY, and SCIPheurGetData().
|
static |
execution method of primal heuristic
Definition at line 542 of file heur_proximity.c.
References assert(), deleteSubproblem(), FALSE, heurdata, MAX, MIN, nnodes, NULL, result, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIPapplyProximity(), SCIPdebugMsg, SCIPdeleteSubproblemProximity(), SCIPgetNBinVars(), SCIPgetNNodes(), SCIPgetNObjVars(), SCIPgetNRootFirstLPIterations(), SCIPgetNVars(), SCIPheurGetData(), SCIPisStopped(), and TRUE.