Detailed Description

dual-ascent and reduction based primal heuristic for Steiner problems

Author: Daniel Rehfeldt

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 "graph.h"
#include "reduce.h"
#include "heur_tm.h"
#include "solstp.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.2

#define	SLACKPRUNE_MAXSTALLPROPORTION 0.5

#define	SLACKPRUNE_HARDREDRATIO 0.97

#define	MAXNTERMINALS 1000

#define	MAXNEDGES 20000

#define	MAXNEDGES_SPG 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 SCIP_Bool	probtypeIsValidForSlackPrune (const GRAPH *graph)

static SCIP_Bool	abortSlackPruneEarly (SCIP scip, const GRAPH graph, SCIP_HEURDATA *heurdata)

static SCIP_RETCODE	reduceExact (SCIP scip, GRAPH prunegraph, int reductbound, SCIP_Bool fullreduce, int soledge, int solnode, SCIP_Real *offset)

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 initialreduce, SCIP_Bool fullreduce)

SCIP_RETCODE	SCIPStpIncludeHeurSlackPrune (SCIP *scip)

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME "slackprune"

Definition at line 48 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 49 of file heur_slackprune.c.

Referenced by SCIPStpIncludeHeurSlackPrune().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR 'S'

Definition at line 50 of file heur_slackprune.c.

Referenced by SCIPStpIncludeHeurSlackPrune().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY 1

Definition at line 51 of file heur_slackprune.c.

Referenced by SCIPStpIncludeHeurSlackPrune().

◆ HEUR_FREQ

#define HEUR_FREQ 1

Definition at line 52 of file heur_slackprune.c.

Referenced by SCIPStpIncludeHeurSlackPrune().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 0

Definition at line 53 of file heur_slackprune.c.

Referenced by SCIPStpIncludeHeurSlackPrune().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH -1

Definition at line 54 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 55 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 56 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 58 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 59 of file heur_slackprune.c.

Referenced by getRedBound(), reduceExact(), and setMinMaxElims().

◆ SLACKPRUNE_MAXREDROUNDS

#define SLACKPRUNE_MAXREDROUNDS 10

maximum number of reduction rounds in slack-prune heuristic

Definition at line 60 of file heur_slackprune.c.

Referenced by SCIPStpHeurSlackPruneRun().

◆ SLACKPRUNE_MINSTALLPROPORTION

#define SLACKPRUNE_MINSTALLPROPORTION 0.2

minimum proportion of arcs to be fixed before restarting slack-prune heuristic

Definition at line 61 of file heur_slackprune.c.

Referenced by abortSlackPruneEarly().

◆ SLACKPRUNE_MAXSTALLPROPORTION

#define SLACKPRUNE_MAXSTALLPROPORTION 0.5

maximum proportion of arcs to be fixed before restarting slack-prune heuristic

Definition at line 62 of file heur_slackprune.c.

◆ SLACKPRUNE_HARDREDRATIO

#define SLACKPRUNE_HARDREDRATIO 0.97

Definition at line 63 of file heur_slackprune.c.

Referenced by abortSlackPruneEarly().

◆ MAXNTERMINALS

#define MAXNTERMINALS 1000

Definition at line 65 of file heur_slackprune.c.

Referenced by abortSlackPruneEarly().

◆ MAXNEDGES

#define MAXNEDGES 20000

Definition at line 66 of file heur_slackprune.c.

Referenced by abortSlackPruneEarly().

◆ MAXNEDGES_SPG

#define MAXNEDGES_SPG 10000

Definition at line 67 of file heur_slackprune.c.

Referenced by abortSlackPruneEarly().

◆ SLACK_MAXTOTNEDGES

#define SLACK_MAXTOTNEDGES 5000

Definition at line 69 of file heur_slackprune.c.

Function Documentation

◆ getRedBound()

static int getRedBound	(	int	nrounds,
		int	nedges
	)

static

Definition at line 91 of file heur_slackprune.c.

References MAX, and SLACKPRUNE_MINREDELIMS.

Referenced by SCIPStpHeurSlackPruneRun().

◆ setMinMaxElims()

static void setMinMaxElims	(	SCIP *	scip,
		int *	minnelims,
		int *	lminnelims,
		int	annodes,
		int	anedges,
		int	anterms,
		int	nround,
		int	maxnrounds
	)

static

Definition at line 105 of file heur_slackprune.c.

References MAX, NULL, SCIP_Real, SCIPisGT(), and SLACKPRUNE_MINREDELIMS.

Referenced by SCIPStpHeurSlackPruneRun().

◆ probtypeIsValidForSlackPrune()

static SCIP_Bool probtypeIsValidForSlackPrune ( const GRAPH * graph )

inlinestatic

can the problem class be used?

Parameters

graph graph data structure

Definition at line 159 of file heur_slackprune.c.

References graph_typeIsSpgLike(), STP_RMWCSP, STP_RPCSPG, and GRAPH::stp_type.

Referenced by abortSlackPruneEarly().

◆ abortSlackPruneEarly()

static SCIP_Bool abortSlackPruneEarly	(	SCIP *	scip,
		const GRAPH *	graph,
		SCIP_HEURDATA *	heurdata
	)

inlinestatic

should we abort early?

Parameters

scip	SCIP data structure
graph	graph data structure
heurdata	heuristic's data

Definition at line 170 of file heur_slackprune.c.

References GRAPH::edges, FALSE, graph_typeIsSpgLike(), MAXNEDGES, MAXNEDGES_SPG, MAXNTERMINALS, probtypeIsValidForSlackPrune(), SCIP_Bool, SCIP_Real, SCIPgetBestSol(), SCIPgetNSols(), SCIPprobdataGetNorgEdges(), SCIPsolGetIndex(), SCIPStpNfixedEdges(), SLACKPRUNE_HARDREDRATIO, SLACKPRUNE_MINSTALLPROPORTION, GRAPH::terms, and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

◆ reduceExact()

static SCIP_RETCODE reduceExact	(	SCIP *	scip,
		GRAPH *	prunegraph,
		int	reductbound,
		SCIP_Bool	fullreduce,
		int *	soledge,
		int *	solnode,
		SCIP_Real *	offset
	)

static

does exact reductions

Parameters

scip	SCIP data structure
prunegraph	graph data structure
reductbound	reduction bound
fullreduce	use full reduction techniques?
soledge	solution edges (in/out)
solnode	array of nodes of current solution that is not to be destroyed (in/out)
offset	objective offset

Definition at line 223 of file heur_slackprune.c.

References bidecomposition_reduction_parameters::depth, reduction_parameters::dualascent, FALSE, graph_get_nEdges(), graph_get_nNodes(), graph_pc_isMw(), graph_pc_isPc(), nnodes, NULL, reduction_base::redparameters, reduce_redLoopMw(), reduce_redLoopPc(), reduce_redLoopStp(), reduce_solAddNodesol(), reduce_solFree(), reduce_solGetNodesol(), reduce_solGetOffset(), reduce_solInit(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SLACKPRUNE_MINREDELIMS, and TRUE.

Referenced by SCIPStpHeurSlackPruneRun().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopySlackPrune )

static

copy method for primal heuristic plugins (called when SCIP copies plugins)

Definition at line 313 of file heur_slackprune.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPStpIncludeHeurSlackPrune().

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeSlackPrune )

static

destructor of primal heuristic to free user data (called when SCIP is exiting)

Definition at line 327 of file heur_slackprune.c.

References NULL, SCIP_OKAY, SCIPfreeMemory, SCIPheurGetData(), and SCIPheurSetData().

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitSlackPrune )

static

initialization method of primal heuristic (called after problem was transformed)

Definition at line 349 of file heur_slackprune.c.

References SCIP_OKAY.

◆ SCIP_DECL_HEURINITSOL()

static SCIP_DECL_HEURINITSOL ( heurInitsolSlackPrune )

static

solving process initialization method of primal heuristic (called when branch and bound process is about to begin)

Definition at line 359 of file heur_slackprune.c.

References NULL, SCIP_OKAY, and SCIPheurGetData().

◆ SCIP_DECL_HEUREXITSOL()

static SCIP_DECL_HEUREXITSOL ( heurExitsolSlackPrune )

static

solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)

Definition at line 385 of file heur_slackprune.c.

References SCIP_OKAY.

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecSlackPrune )

static

execution method of primal heuristic

Definition at line 395 of file heur_slackprune.c.

References abortSlackPruneEarly(), CONNECT, GRAPH::cost, GRAPH::edges, FALSE, HEUR_NAME, NULL, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetProbData(), SCIPgetSolOrigObj(), SCIPheurGetData(), SCIPheurGetName(), SCIPisEQ(), SCIPisLE(), SCIPprobdataAddNewSol(), SCIPprobdataGetGraph(), SCIPprobdataGetNVars(), SCIPprobdataGetOffset(), SCIPprobdataGetVars(), SCIPprobdataGetXval(), SCIPsolGetIndex(), SCIPStpHeurSlackPruneRun(), SCIPStpNfixedEdges(), solstp_isValid(), and UNKNOWN.

◆ SCIPStpHeurSlackPruneRun()

SCIP_RETCODE SCIPStpHeurSlackPruneRun	(	SCIP *	scip,
		SCIP_VAR **	vars,
		GRAPH *	g,
		int *	soledge,
		SCIP_Bool *	success,
		SCIP_Bool	initialreduce,
		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?
initialreduce	try to reduce graph initially?
fullreduce	use full reduction techniques?

Definition at line 532 of file heur_slackprune.c.

References BMScopyMemoryArray, CONNECT, FALSE, getRedBound(), graph_copy(), graph_edge_del(), graph_free(), graph_get_nEdges(), graph_get_nNodes(), graph_get_nVET(), graph_initHistory(), graph_path_exit(), graph_path_init(), graph_pc_edgeIsExtended(), graph_pc_isPcMw(), graph_valid(), GRAPH::head, GRAPH::knots, nnodes, GRAPH::norgmodelknots, NULL, reduce_daSlackPrune(), reduce_unconnected(), reduceExact(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisLE(), SCIPprobdataGetOffset(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneUpdateSols(), SCIPvarGetUbLocal(), setMinMaxElims(), SLACKPRUNE_MAXREDROUNDS, solstp_getObj(), solstp_getObjBounded(), solstp_isValid(), STP_GSTP, STP_OARSMT, STP_RSMT, STP_SPG, GRAPH::stp_type, GRAPH::tail, TRUE, and UNKNOWN.

Referenced by computeSteinerTreeRedCosts(), createInitialCuts(), and SCIP_DECL_HEUREXEC().

◆ SCIPStpIncludeHeurSlackPrune()

SCIP_RETCODE SCIPStpIncludeHeurSlackPrune ( SCIP * scip )

creates the slackprune primal heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 730 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(), SCIP_DECL_HEURCOPY(), and subscipSetupCallbacks().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ HEUR_NAME

◆ HEUR_DESC

◆ HEUR_DISPCHAR

◆ HEUR_PRIORITY

◆ HEUR_FREQ

◆ HEUR_FREQOFS

◆ HEUR_MAXDEPTH

◆ HEUR_TIMING

◆ HEUR_USESSUBSCIP

◆ DEFAULT_SLACKPRUNE_MAXFREQ

◆ SLACKPRUNE_MINREDELIMS

◆ SLACKPRUNE_MAXREDROUNDS

◆ SLACKPRUNE_MINSTALLPROPORTION

◆ SLACKPRUNE_MAXSTALLPROPORTION

◆ SLACKPRUNE_HARDREDRATIO

◆ MAXNTERMINALS

◆ MAXNEDGES

◆ MAXNEDGES_SPG

◆ SLACK_MAXTOTNEDGES

Function Documentation

◆ getRedBound()

◆ setMinMaxElims()

◆ probtypeIsValidForSlackPrune()

◆ abortSlackPruneEarly()

◆ reduceExact()

◆ SCIP_DECL_HEURCOPY()

◆ SCIP_DECL_HEURFREE()

◆ SCIP_DECL_HEURINIT()

◆ SCIP_DECL_HEURINITSOL()

◆ SCIP_DECL_HEUREXITSOL()

◆ SCIP_DECL_HEUREXEC()

◆ SCIPStpHeurSlackPruneRun()

◆ SCIPStpIncludeHeurSlackPrune()