Detailed Description
dual-ascent and reduction based primal heuristic for Steiner problems
This file implements a dual-ascent and reduction based heuristic for Steiner problems. It is based on an approach described in T. Polzin's "Algorithms for the Steiner problem in networks".
A list of all interface methods can be found in heur_slackprune.h
Definition in file heur_slackprune.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_slackprune.h"
#include "heur_ascendprune.h"
#include "heur_local.h"
#include "heur_prune.h"
#include "grph.h"
#include "heur_tm.h"
#include "cons_stp.h"
#include "scip/pub_misc.h"
#include "probdata_stp.h"
#include "prop_stp.h"
Go to the source code of this file.
Macros | |
#define | HEUR_NAME "slackprune" |
#define | HEUR_DESC "Reduction based heuristic for Steiner problems" |
#define | HEUR_DISPCHAR 'S' |
#define | HEUR_PRIORITY 1 |
#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_SLACKPRUNE_MAXFREQ FALSE |
#define | SLACKPRUNE_MINREDELIMS 2 |
#define | SLACKPRUNE_MAXREDROUNDS 10 |
#define | SLACKPRUNE_MINSTALLPROPORTION 0.25 |
#define | SLACKPRUNE_MAXSTALLPROPORTION 0.5 |
#define | BREAKONERROR FALSE |
#define | MAXNTERMINALS 500 |
#define | MAXNEDGES 10000 |
#define | SLACK_MAXTOTNEDGES 5000 |
Functions | |
static int | getRedBound (int nrounds, int nedges) |
static void | setMinMaxElims (SCIP *scip, int *minnelims, int *lminnelims, int annodes, int anedges, int anterms, int nround, int maxnrounds) |
static void | updateSolNodeArray (GRAPH *graph, int *soledge, int *solnode, int nnodes, int nnedges) |
static | SCIP_DECL_HEURCOPY (heurCopySlackPrune) |
static | SCIP_DECL_HEURFREE (heurFreeSlackPrune) |
static | SCIP_DECL_HEURINIT (heurInitSlackPrune) |
static | SCIP_DECL_HEURINITSOL (heurInitsolSlackPrune) |
static | SCIP_DECL_HEUREXITSOL (heurExitsolSlackPrune) |
static | SCIP_DECL_HEUREXEC (heurExecSlackPrune) |
SCIP_RETCODE | SCIPStpHeurSlackPruneRun (SCIP *scip, SCIP_VAR **vars, GRAPH *g, int *soledge, SCIP_Bool *success, SCIP_Bool reducegraph, SCIP_Bool fullreduce) |
SCIP_RETCODE | SCIPStpHeurSlackPruneRunPcMw (SCIP *scip, SCIP_VAR **vars, GRAPH *g, int *soledge, SCIP_Bool *success) |
SCIP_RETCODE | SCIPStpIncludeHeurSlackPrune (SCIP *scip) |
Macro Definition Documentation
◆ HEUR_NAME
#define HEUR_NAME "slackprune" |
Definition at line 45 of file heur_slackprune.c.
Referenced by SCIP_DECL_HEURCOPY(), SCIP_DECL_HEUREXEC(), and SCIPStpIncludeHeurSlackPrune().
◆ HEUR_DESC
#define HEUR_DESC "Reduction based heuristic for Steiner problems" |
Definition at line 46 of file heur_slackprune.c.
Referenced by SCIPStpIncludeHeurSlackPrune().
◆ HEUR_DISPCHAR
#define HEUR_DISPCHAR 'S' |
Definition at line 47 of file heur_slackprune.c.
Referenced by SCIPStpIncludeHeurSlackPrune().
◆ HEUR_PRIORITY
#define HEUR_PRIORITY 1 |
Definition at line 48 of file heur_slackprune.c.
Referenced by SCIPStpIncludeHeurSlackPrune().
◆ HEUR_FREQ
#define HEUR_FREQ 1 |
Definition at line 49 of file heur_slackprune.c.
Referenced by SCIPStpIncludeHeurSlackPrune().
◆ HEUR_FREQOFS
#define HEUR_FREQOFS 0 |
Definition at line 50 of file heur_slackprune.c.
Referenced by SCIPStpIncludeHeurSlackPrune().
◆ HEUR_MAXDEPTH
#define HEUR_MAXDEPTH -1 |
Definition at line 51 of file heur_slackprune.c.
Referenced by SCIPStpIncludeHeurSlackPrune().
◆ HEUR_TIMING
#define HEUR_TIMING (SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE) |
Definition at line 52 of file heur_slackprune.c.
Referenced by SCIPStpIncludeHeurSlackPrune().
◆ HEUR_USESSUBSCIP
#define HEUR_USESSUBSCIP FALSE |
does the heuristic use a secondary SCIP instance?
Definition at line 53 of file heur_slackprune.c.
Referenced by SCIPStpIncludeHeurSlackPrune().
◆ DEFAULT_SLACKPRUNE_MAXFREQ
#define DEFAULT_SLACKPRUNE_MAXFREQ FALSE |
executions of the heuristic at maximum frequency?
Definition at line 55 of file heur_slackprune.c.
Referenced by SCIPStpIncludeHeurSlackPrune().
◆ SLACKPRUNE_MINREDELIMS
#define SLACKPRUNE_MINREDELIMS 2 |
minimum number of eliminations for reduction package when called by slack-and-prune heuristic
Definition at line 56 of file heur_slackprune.c.
Referenced by getRedBound(), and setMinMaxElims().
◆ SLACKPRUNE_MAXREDROUNDS
#define SLACKPRUNE_MAXREDROUNDS 10 |
maximum number of reduction rounds in slack-prune heuristic
Definition at line 57 of file heur_slackprune.c.
Referenced by SCIPStpHeurSlackPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().
◆ SLACKPRUNE_MINSTALLPROPORTION
#define SLACKPRUNE_MINSTALLPROPORTION 0.25 |
minimum proportion of arcs to be fixed before restarting slack-prune heuristic
Definition at line 58 of file heur_slackprune.c.
Referenced by SCIP_DECL_HEUREXEC().
◆ SLACKPRUNE_MAXSTALLPROPORTION
#define SLACKPRUNE_MAXSTALLPROPORTION 0.5 |
maximum proportion of arcs to be fixed before restarting slack-prune heuristic
Definition at line 59 of file heur_slackprune.c.
Referenced by SCIP_DECL_HEUREXEC().
◆ BREAKONERROR
#define BREAKONERROR FALSE |
Definition at line 60 of file heur_slackprune.c.
◆ MAXNTERMINALS
#define MAXNTERMINALS 500 |
Definition at line 61 of file heur_slackprune.c.
Referenced by SCIP_DECL_HEUREXEC().
◆ MAXNEDGES
#define MAXNEDGES 10000 |
Definition at line 62 of file heur_slackprune.c.
Referenced by SCIP_DECL_HEUREXEC().
◆ SLACK_MAXTOTNEDGES
#define SLACK_MAXTOTNEDGES 5000 |
Definition at line 63 of file heur_slackprune.c.
Referenced by SCIP_DECL_HEUREXEC().
Function Documentation
◆ getRedBound()
|
static |
Definition at line 88 of file heur_slackprune.c.
References MAX, and SLACKPRUNE_MINREDELIMS.
Referenced by SCIPStpHeurSlackPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().
◆ setMinMaxElims()
|
static |
Definition at line 102 of file heur_slackprune.c.
References MAX, NULL, SCIP_Real, SCIPisGT(), and SLACKPRUNE_MINREDELIMS.
Referenced by SCIPStpHeurSlackPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().
◆ updateSolNodeArray()
|
static |
Definition at line 154 of file heur_slackprune.c.
References CONNECT, GRAPH::cost, GRAPH::edges, FALSE, GRAPH::head, GRAPH::knots, nnodes, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgmlWriteClosing(), SCIPgmlWriteEdge(), SCIPgmlWriteNode(), SCIPgmlWriteOpening(), SCIPsnprintf(), GRAPH::source, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.
Referenced by SCIPStpHeurSlackPruneRunPcMw().
◆ SCIP_DECL_HEURCOPY()
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 267 of file heur_slackprune.c.
References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPStpIncludeHeurSlackPrune().
◆ SCIP_DECL_HEURFREE()
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 281 of file heur_slackprune.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 303 of file heur_slackprune.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 313 of file heur_slackprune.c.
References 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 336 of file heur_slackprune.c.
References SCIP_OKAY.
◆ SCIP_DECL_HEUREXEC()
|
static |
execution method of primal heuristic
Definition at line 346 of file heur_slackprune.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(), SCIPStpHeurSlackPruneRun(), SCIPStpNfixedEdges(), SLACK_MAXTOTNEDGES, SLACKPRUNE_MAXSTALLPROPORTION, SLACKPRUNE_MINSTALLPROPORTION, STP_GSTP, STP_OARSMT, STP_RSMT, STP_SPG, GRAPH::stp_type, GRAPH::terms, and UNKNOWN.
◆ SCIPStpHeurSlackPruneRun()
SCIP_RETCODE SCIPStpHeurSlackPruneRun | ( | SCIP * | scip, |
SCIP_VAR ** | vars, | ||
GRAPH * | g, | ||
int * | soledge, | ||
SCIP_Bool * | success, | ||
SCIP_Bool | reducegraph, | ||
SCIP_Bool | fullreduce | ||
) |
execute slack-and-prune heuristic on given graph
- Parameters
-
scip SCIP data structure vars problem variables or NULL g graph data structure soledge array to 1. provide and 2. return primal solution success feasible solution found? reducegraph try to reduce graph initially? fullreduce use full reduction techniques?
Definition at line 524 of file heur_slackprune.c.
References BMScopyMemoryArray, CONNECT, GRAPH::cost, GRAPH::edges, FALSE, getRedBound(), GRAPH::grad, graph_copy(), graph_edge_del(), graph_free(), graph_get_NVET(), graph_init_history(), graph_path_exit(), graph_path_init(), graph_sol_getObj(), graph_sol_valid(), graph_valid(), GRAPH::head, GRAPH::knots, level0(), nnodes, nterms, NULL, redLoopStp(), reduce_daSlackPrune(), SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemory, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBlockMemory, SCIPfreeBufferArray, SCIPisLE(), SCIPprobdataGetOffset(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneUpdateSols(), SCIPvarGetUbLocal(), setMinMaxElims(), SLACKPRUNE_MAXREDROUNDS, GRAPH::source, STP_GSTP, STP_OARSMT, STP_RSMT, STP_SPG, GRAPH::stp_type, GRAPH::tail, GRAPH::terms, TRUE, and UNKNOWN.
Referenced by SCIP_DECL_HEUREXEC().
◆ SCIPStpHeurSlackPruneRunPcMw()
SCIP_RETCODE SCIPStpHeurSlackPruneRunPcMw | ( | SCIP * | scip, |
SCIP_VAR ** | vars, | ||
GRAPH * | g, | ||
int * | soledge, | ||
SCIP_Bool * | success | ||
) |
execute slack-and-prune heuristic on given graph
- Parameters
-
scip SCIP data structure vars problem variables or NULL g graph data structure soledge array to 1. provide and 2. return primal solution success feasible solution found?
Definition at line 802 of file heur_slackprune.c.
References GRAPH::ancestors, CONNECT, GRAPH::cost, GRAPH::edges, FALSE, GRAPH::fixedges, getRedBound(), GRAPH::grad, graph_copy(), graph_edge_del(), graph_free(), graph_get_NVET(), graph_init_history(), graph_path_exit(), graph_path_init(), graph_sol_getObj(), graph_sol_markPcancestors(), graph_sol_setNodeList(), graph_sol_valid(), graph_valid(), GRAPH::head, Is_term, GRAPH::knots, level0(), nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, nterms, NULL, GRAPH::orghead, GRAPH::orgtail, GRAPH::pcancestors, redLoopMw(), reduce_daSlackPruneMw(), SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPallocBuffer, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBuffer, SCIPfreeBufferArray, SCIPisLT(), SCIPprobdataGetOffset(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurPruneRun(), SCIPStpHeurTMPrunePc(), SCIPvarGetUbLocal(), setMinMaxElims(), SLACKPRUNE_MAXREDROUNDS, GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, UNKNOWN, and updateSolNodeArray().
◆ SCIPStpIncludeHeurSlackPrune()
SCIP_RETCODE SCIPStpIncludeHeurSlackPrune | ( | SCIP * | scip | ) |
creates the slackprune primal heuristic and includes it in SCIP
- Parameters
-
scip SCIP data structure
Definition at line 1129 of file heur_slackprune.c.
References DEFAULT_SLACKPRUNE_MAXFREQ, 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().