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 "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 int getRedBound	(	int	nrounds,
		int	nedges
	)

static

Definition at line 88 of file heur_slackprune.c.

References MAX, and SLACKPRUNE_MINREDELIMS.

Referenced by SCIPStpHeurSlackPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().

◆ setMinMaxElims()

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

static

Definition at line 102 of file heur_slackprune.c.

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

Referenced by SCIPStpHeurSlackPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().

◆ updateSolNodeArray()

static void updateSolNodeArray	(	GRAPH *	graph,
		int *	soledge,
		int *	solnode,
		int	nnodes,
		int	nnedges
	)

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 SCIP_DECL_HEURCOPY ( heurCopySlackPrune )

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 SCIP_DECL_HEURFREE ( heurFreeSlackPrune )

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 SCIP_DECL_HEURINIT ( heurInitSlackPrune )

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 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 313 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 336 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 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().

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

◆ BREAKONERROR

◆ MAXNTERMINALS

◆ MAXNEDGES

◆ SLACK_MAXTOTNEDGES

Function Documentation

◆ getRedBound()

◆ setMinMaxElims()

◆ updateSolNodeArray()

◆ SCIP_DECL_HEURCOPY()

◆ SCIP_DECL_HEURFREE()

◆ SCIP_DECL_HEURINIT()

◆ SCIP_DECL_HEURINITSOL()

◆ SCIP_DECL_HEUREXITSOL()

◆ SCIP_DECL_HEUREXEC()

◆ SCIPStpHeurSlackPruneRun()

◆ SCIPStpHeurSlackPruneRunPcMw()

◆ SCIPStpIncludeHeurSlackPrune()