Detailed Description
reduction-based primal heuristic for Steiner problems
This file implements a reduction based heuristic for Steiner problems. See "SCIP-Jack - A solver for STP and variants with parallelization extensions" (2016) by Gamrath, Koch, Maher, Rehfeldt and Shinano
A list of all interface methods can be found in heur_prune.h
Definition in file heur_prune.c.
#include <assert.h>
#include <string.h>
#include <stdio.h>
#include "scip/scip.h"
#include "scip/scipdefplugins.h"
#include "scip/cons_linear.h"
#include "heur_prune.h"
#include "heur_local.h"
#include "grph.h"
#include "heur_tm.h"
#include "cons_stp.h"
#include "scip/pub_misc.h"
#include "probdata_stp.h"
Go to the source code of this file.
Macros | |
#define | HEUR_NAME "prune" |
#define | HEUR_DESC "Reduction based heuristic for Steiner problems" |
#define | HEUR_DISPCHAR 'P' |
#define | HEUR_PRIORITY 2 |
#define | HEUR_FREQ -1 |
#define | HEUR_FREQOFS 0 |
#define | HEUR_MAXDEPTH -1 |
#define | HEUR_TIMING (SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE) |
#define | HEUR_USESSUBSCIP FALSE |
#define | DEFAULT_PRUNE_MAXFRQ FALSE |
#define | DEFAULT_PRUNE_TMRUNS 100 |
#define | PRUNE_MINREDELIMS 2 |
#define | PRUNE_MAXREDROUNDS 6 |
#define | BREAKONERROR FALSE |
#define | MAXNTERMINALS 500 |
#define | MAXNEDGES 10000 |
Functions | |
static void | setNodeSolArray (const GRAPH *g, SCIP_Real *uborg, int *solnode, const int *soledge) |
static SCIP_RETCODE | computeNewSols (SCIP *scip, GRAPH *g, GRAPH *prunegraph, PATH *path, int *nodearrint, int *edgearrint, int *solnode, int *soledge, int *globalsoledge, STP_Bool *nodearrchar, SCIP_Real *globalobj, SCIP_Bool incumbentgiven, SCIP_Bool *success) |
static int | getRedBound (int nround, int nedges) |
static void | setMinMaxElims (SCIP *scip, int *minnelims, int *lminnelims, int annodes, int anedges, int anterms, int nround, int maxrounds) |
static | SCIP_DECL_HEURCOPY (heurCopyPrune) |
static | SCIP_DECL_HEURFREE (heurFreePrune) |
static | SCIP_DECL_HEURINIT (heurInitPrune) |
static | SCIP_DECL_HEURINITSOL (heurInitsolPrune) |
static | SCIP_DECL_HEUREXITSOL (heurExitsolPrune) |
static | SCIP_DECL_HEUREXEC (heurExecPrune) |
SCIP_RETCODE | SCIPStpHeurPruneUpdateSols (SCIP *scip, GRAPH *g, GRAPH *prunegraph, PATH *path, int *nodearrint, int *edgearrint, int *solnode, int *soledge, int *globalsoledge, STP_Bool *nodearrchar, SCIP_Real *globalobj, SCIP_Bool incumbentgiven, SCIP_Bool *success) |
SCIP_RETCODE | SCIPStpHeurPruneRun (SCIP *scip, SCIP_VAR **vars, GRAPH *g, int *soledge, SCIP_Bool *success, const SCIP_Bool withinitialsol, const SCIP_Bool reducegraph) |
SCIP_RETCODE | SCIPStpIncludeHeurPrune (SCIP *scip) |
Macro Definition Documentation
◆ HEUR_NAME
#define HEUR_NAME "prune" |
Definition at line 44 of file heur_prune.c.
Referenced by SCIP_DECL_HEURCOPY(), SCIP_DECL_HEUREXEC(), and SCIPStpIncludeHeurPrune().
◆ HEUR_DESC
#define HEUR_DESC "Reduction based heuristic for Steiner problems" |
Definition at line 45 of file heur_prune.c.
Referenced by SCIPStpIncludeHeurPrune().
◆ HEUR_DISPCHAR
#define HEUR_DISPCHAR 'P' |
Definition at line 46 of file heur_prune.c.
Referenced by SCIPStpIncludeHeurPrune().
◆ HEUR_PRIORITY
#define HEUR_PRIORITY 2 |
Definition at line 47 of file heur_prune.c.
Referenced by SCIPStpIncludeHeurPrune().
◆ HEUR_FREQ
#define HEUR_FREQ -1 |
Definition at line 48 of file heur_prune.c.
Referenced by SCIPStpIncludeHeurPrune().
◆ HEUR_FREQOFS
#define HEUR_FREQOFS 0 |
Definition at line 49 of file heur_prune.c.
Referenced by SCIPStpIncludeHeurPrune().
◆ HEUR_MAXDEPTH
#define HEUR_MAXDEPTH -1 |
Definition at line 50 of file heur_prune.c.
Referenced by SCIPStpIncludeHeurPrune().
◆ HEUR_TIMING
#define HEUR_TIMING (SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE) |
Definition at line 51 of file heur_prune.c.
Referenced by SCIPStpIncludeHeurPrune().
◆ HEUR_USESSUBSCIP
#define HEUR_USESSUBSCIP FALSE |
does the heuristic use a secondary SCIP instance?
Definition at line 52 of file heur_prune.c.
Referenced by SCIPStpIncludeHeurPrune().
◆ DEFAULT_PRUNE_MAXFRQ
#define DEFAULT_PRUNE_MAXFRQ FALSE |
executions of the heuristic at maximum frequency?
Definition at line 54 of file heur_prune.c.
Referenced by SCIPStpIncludeHeurPrune().
◆ DEFAULT_PRUNE_TMRUNS
#define DEFAULT_PRUNE_TMRUNS 100 |
number of runs in TM heuristic when called by prune heuristic
Definition at line 55 of file heur_prune.c.
Referenced by computeNewSols(), and SCIP_DECL_HEURINITSOL().
◆ PRUNE_MINREDELIMS
#define PRUNE_MINREDELIMS 2 |
maximum number of eliminations for reduction package when called by prune heuristic
Definition at line 56 of file heur_prune.c.
Referenced by getRedBound(), and setMinMaxElims().
◆ PRUNE_MAXREDROUNDS
#define PRUNE_MAXREDROUNDS 6 |
maximum number of reduction rounds in prune heuristic
Definition at line 57 of file heur_prune.c.
Referenced by SCIPStpHeurPruneRun().
◆ BREAKONERROR
#define BREAKONERROR FALSE |
Definition at line 58 of file heur_prune.c.
◆ MAXNTERMINALS
#define MAXNTERMINALS 500 |
Definition at line 59 of file heur_prune.c.
Referenced by SCIP_DECL_HEUREXEC().
◆ MAXNEDGES
#define MAXNEDGES 10000 |
Definition at line 60 of file heur_prune.c.
Referenced by SCIP_DECL_HEUREXEC().
Function Documentation
◆ setNodeSolArray()
|
static |
Definition at line 87 of file heur_prune.c.
References CONNECT, GRAPH::cost, GRAPH::edges, GRAPH::head, GRAPH::knots, nnodes, NULL, SCIP_Real, GRAPH::tail, and UNKNOWN.
Referenced by SCIPStpHeurPruneRun(), and SCIPStpHeurPruneUpdateSols().
◆ computeNewSols()
|
static |
computes new solution during execution of prune and updates best global one if possible
- Parameters
-
scip SCIP data structure g graph data structure prunegraph pruned graph data structure path shortest path struct nodearrint array edgearrint array solnode array for best solution nodes wrt prunegraph soledge array for best solution edges wrt prunegraph globalsoledge array storing best solution wrt g nodearrchar array globalobj pointer to objective value of best solution wrt g incumbentgiven incumbent solution for pruned graph given? success pointer to store whether a solution could be found
Definition at line 127 of file heur_prune.c.
References GRAPH::cost, DEFAULT_PRUNE_TMRUNS, GRAPH::edges, FALSE, GRAPH::grad, graph_valid(), GRAPH::knots, GRAPH::mark, nnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPStpHeurLocalRun(), SCIPStpHeurPruneUpdateSols(), SCIPStpHeurTMCompStarts(), SCIPStpHeurTMRun(), and GRAPH::source.
Referenced by SCIPStpHeurPruneRun().
◆ getRedBound()
|
static |
Definition at line 181 of file heur_prune.c.
References MAX, and PRUNE_MINREDELIMS.
Referenced by SCIPStpHeurPruneRun().
◆ setMinMaxElims()
|
static |
Definition at line 195 of file heur_prune.c.
References MAX, NULL, PRUNE_MINREDELIMS, SCIP_Real, and SCIPisGT().
Referenced by SCIPStpHeurPruneRun().
◆ SCIP_DECL_HEURCOPY()
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 248 of file heur_prune.c.
References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPStpIncludeHeurPrune().
◆ SCIP_DECL_HEURFREE()
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 262 of file heur_prune.c.
References NULL, SCIP_OKAY, SCIPfreeMemory, SCIPheurGetData(), and SCIPheurSetData().
◆ SCIP_DECL_HEURINIT()
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 283 of file heur_prune.c.
References SCIP_OKAY.
◆ SCIP_DECL_HEURINITSOL()
|
static |
solving process initialization method of primal heuristic (called when branch and bound process is about to begin)
Definition at line 293 of file heur_prune.c.
References DEFAULT_PRUNE_TMRUNS, NULL, SCIP_OKAY, and SCIPheurGetData().
◆ SCIP_DECL_HEUREXITSOL()
|
static |
solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)
Definition at line 316 of file heur_prune.c.
References SCIP_OKAY.
◆ SCIP_DECL_HEUREXEC()
|
static |
execution method of primal heuristic
Definition at line 325 of file heur_prune.c.
References CONNECT, GRAPH::cost, GRAPH::edges, FALSE, graph_sol_valid(), HEUR_NAME, MAXNEDGES, MAXNTERMINALS, NULL, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetProbData(), SCIPgetSolOrigObj(), SCIPheurGetData(), SCIPheurGetName(), SCIPisEQ(), SCIPisGT(), SCIPprobdataAddNewSol(), SCIPprobdataGetGraph(), SCIPprobdataGetNVars(), SCIPprobdataGetOffset(), SCIPprobdataGetVars(), SCIPprobdataGetXval(), SCIPsolGetHeur(), SCIPsolGetIndex(), SCIPStpHeurPruneRun(), STP_GSTP, STP_OARSMT, STP_RSMT, STP_SPG, GRAPH::stp_type, GRAPH::terms, TRUE, and UNKNOWN.
◆ SCIPStpHeurPruneUpdateSols()
SCIP_RETCODE SCIPStpHeurPruneUpdateSols | ( | SCIP * | scip, |
GRAPH * | g, | ||
GRAPH * | prunegraph, | ||
PATH * | path, | ||
int * | nodearrint, | ||
int * | edgearrint, | ||
int * | solnode, | ||
int * | soledge, | ||
int * | globalsoledge, | ||
STP_Bool * | nodearrchar, | ||
SCIP_Real * | globalobj, | ||
SCIP_Bool | incumbentgiven, | ||
SCIP_Bool * | success | ||
) |
updates solutions for pruned graph
- Parameters
-
scip SCIP data structure g graph data structure prunegraph pruned graph data structure path shortest path struct nodearrint array edgearrint array solnode array for best solution nodes wrt prunegraph soledge array for best solution edges wrt prunegraph globalsoledge array storing best solution wrt g nodearrchar array globalobj pointer to objective value of best solution wrt g incumbentgiven incumbent solution for pruned graph given? success pointer to store whether a solution could be found
Definition at line 481 of file heur_prune.c.
References BMScopyMemoryArray, CONNECT, GRAPH::cost, shortest_path::edge, GRAPH::edges, FARAWAY, GRAPH::grad, graph_sol_getObj(), graph_sol_getOrg(), graph_sol_valid(), GRAPH::knots, GRAPH::mark, nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisLE(), SCIPStpHeurLocalRun(), SCIPStpHeurTMBuildTree(), SCIPStpHeurTMBuildTreePcMw(), setNodeSolArray(), STP_MWCSP, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, GRAPH::stp_type, TRUE, and UNKNOWN.
Referenced by computeNewSols(), and SCIPStpHeurSlackPruneRun().
◆ SCIPStpHeurPruneRun()
SCIP_RETCODE SCIPStpHeurPruneRun | ( | SCIP * | scip, |
SCIP_VAR ** | vars, | ||
GRAPH * | g, | ||
int * | soledge, | ||
SCIP_Bool * | success, | ||
const SCIP_Bool | withinitialsol, | ||
const SCIP_Bool | reducegraph | ||
) |
execute prune heuristic on given graph
- Parameters
-
scip SCIP data structure vars problem variables or NULL (need to be provided whenever available) g the graph soledge array to store primal solution (if no solution is provided, withinitialsol must be set to FALSE) success feasible solution found? withinitialsol solution given? reducegraph try to reduce graph initially?
Definition at line 597 of file heur_prune.c.
References BMScopyMemoryArray, computeNewSols(), CONNECT, GRAPH::cost, GRAPH::edges, GRAPH::extended, FALSE, FARAWAY, getRedBound(), graph_copy(), graph_edge_del(), graph_free(), graph_get_NVET(), graph_init_history(), graph_path_exit(), graph_path_init(), graph_pc_2org(), graph_pc_2trans(), graph_sol_getObj(), graph_sol_valid(), graph_valid(), GRAPH::head, Is_term, GRAPH::knots, level0(), nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, NULL, PRUNE_MAXREDROUNDS, redLoopMw(), redLoopPc(), redLoopStp(), reduce_boundPrune(), SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPvarGetUbLocal(), setMinMaxElims(), setNodeSolArray(), STP_DHCSTP, STP_GSTP, STP_MWCSP, STP_OARSMT, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, STP_RSMT, STP_SPG, GRAPH::stp_type, GRAPH::tail, GRAPH::terms, TRUE, and UNKNOWN.
Referenced by SCIP_DECL_HEUREXEC(), SCIPStpHeurAscendPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().
◆ SCIPStpIncludeHeurPrune()
SCIP_RETCODE SCIPStpIncludeHeurPrune | ( | SCIP * | scip | ) |
creates the prune primal heuristic and includes it in SCIP
- Parameters
-
scip SCIP data structure
Definition at line 907 of file heur_prune.c.
References DEFAULT_PRUNE_MAXFRQ, FALSE, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, HEUR_USESSUBSCIP, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPallocMemory, SCIPincludeHeurBasic(), SCIPsetHeurCopy(), SCIPsetHeurExitsol(), SCIPsetHeurFree(), SCIPsetHeurInit(), and SCIPsetHeurInitsol().
Referenced by runShell(), and SCIP_DECL_HEURCOPY().