Detailed Description

reduction-based primal heuristic for Steiner problems

Author: Daniel Rehfeldt

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 "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"

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	PRUNE_TMRUNS 100

#define	PRUNE_TMRUNS_FAST 70

#define	PRUNE_MINREDELIMS 2

#define	PRUNE_MAXREDROUNDS 6

#define	MAXNTERMINALS 500

#define	MAXNEDGES 10000

Functions
static void	setNodeSolArray (const GRAPH g, SCIP_Real RESTRICT uborg, int RESTRICT solnode, const int soledge)

static SCIP_RETCODE	computeNewSols (SCIP scip, GRAPH g, GRAPH prunegraph, int nodearrint, int solnode, int soledge, int globalsoledge, SCIP_Real globalobj, SCIP_Bool incumbentgiven, SCIP_Bool beFast, 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, int solnode, int soledge, int globalsoledge, 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 46 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 47 of file heur_prune.c.

Referenced by SCIPStpIncludeHeurPrune().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR 'P'

Definition at line 48 of file heur_prune.c.

Referenced by SCIPStpIncludeHeurPrune().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY 2

Definition at line 49 of file heur_prune.c.

Referenced by SCIPStpIncludeHeurPrune().

◆ HEUR_FREQ

#define HEUR_FREQ -1

Definition at line 50 of file heur_prune.c.

Referenced by SCIPStpIncludeHeurPrune().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 0

Definition at line 51 of file heur_prune.c.

Referenced by SCIPStpIncludeHeurPrune().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH -1

Definition at line 52 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 53 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 54 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 56 of file heur_prune.c.

Referenced by SCIPStpIncludeHeurPrune().

◆ PRUNE_TMRUNS

#define PRUNE_TMRUNS 100

number of runs in TM heuristic when called by prune heuristic

Definition at line 57 of file heur_prune.c.

Referenced by computeNewSols(), and SCIP_DECL_HEURINITSOL().

◆ PRUNE_TMRUNS_FAST

#define PRUNE_TMRUNS_FAST 70

number of runs in TM heuristic when called by prune heuristic

Definition at line 58 of file heur_prune.c.

◆ PRUNE_MINREDELIMS

#define PRUNE_MINREDELIMS 2

maximum number of eliminations for reduction package when called by prune heuristic

Definition at line 59 of file heur_prune.c.

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

◆ PRUNE_MAXREDROUNDS

#define PRUNE_MAXREDROUNDS 6

maximum number of reduction rounds in prune heuristic

Definition at line 60 of file heur_prune.c.

Referenced by SCIPStpHeurPruneRun().

◆ MAXNTERMINALS

#define MAXNTERMINALS 500

Definition at line 61 of file heur_prune.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ MAXNEDGES

#define MAXNEDGES 10000

Definition at line 62 of file heur_prune.c.

Referenced by SCIP_DECL_HEUREXEC().

Function Documentation

◆ setNodeSolArray()

static void setNodeSolArray	(	const GRAPH *	g,
		SCIP_Real *RESTRICT	uborg,
		int *RESTRICT	solnode,
		const int *	soledge
	)

static

Definition at line 86 of file heur_prune.c.

References CONNECT, GRAPH::cost, graph_get_nEdges(), graph_get_nNodes(), GRAPH::head, nnodes, NULL, SCIP_Real, GRAPH::source, GRAPH::tail, and UNKNOWN.

Referenced by SCIPStpHeurPruneRun(), and SCIPStpHeurPruneUpdateSols().

◆ computeNewSols()

static SCIP_RETCODE computeNewSols	(	SCIP *	scip,
		GRAPH *	g,
		GRAPH *	prunegraph,
		int *	nodearrint,
		int *	solnode,
		int *	soledge,
		int *	globalsoledge,
		SCIP_Real *	globalobj,
		SCIP_Bool	incumbentgiven,
		SCIP_Bool	beFast,
		SCIP_Bool *	success
	)

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
nodearrint	array
solnode	array for best solution nodes wrt prunegraph
soledge	array for best solution edges wrt prunegraph
globalsoledge	array storing best solution wrt g
globalobj	pointer to objective value of best solution wrt g
incumbentgiven	incumbent solution for pruned graph given?
beFast	use fast mode?
success	pointer to store whether a solution could be found

Definition at line 131 of file heur_prune.c.

References GRAPH::cost, GRAPH::edges, GRAPH::grad, graph_valid(), GRAPH::knots, GRAPH::mark, nnodes, NULL, pcmode_fromheurdata, PRUNE_TMRUNS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPStpHeurLocalRun(), SCIPStpHeurPruneUpdateSols(), SCIPStpHeurTMCompStarts(), SCIPStpHeurTMRun(), GRAPH::source, and GRAPH::terms.

Referenced by SCIPStpHeurPruneRun().

◆ getRedBound()

static int getRedBound	(	int	nround,
		int	nedges
	)

static

Definition at line 191 of file heur_prune.c.

References MAX, and PRUNE_MINREDELIMS.

Referenced by SCIPStpHeurPruneRun().

◆ setMinMaxElims()

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

static

Definition at line 206 of file heur_prune.c.

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

Referenced by SCIPStpHeurPruneRun().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyPrune )

static

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

Definition at line 258 of file heur_prune.c.

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

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreePrune )

static

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

Definition at line 272 of file heur_prune.c.

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

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitPrune )

static

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

Definition at line 293 of file heur_prune.c.

References SCIP_OKAY.

◆ SCIP_DECL_HEURINITSOL()

static SCIP_DECL_HEURINITSOL ( heurInitsolPrune )

static

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

Definition at line 303 of file heur_prune.c.

References NULL, PRUNE_TMRUNS, SCIP_OKAY, and SCIPheurGetData().

◆ SCIP_DECL_HEUREXITSOL()

static SCIP_DECL_HEUREXITSOL ( heurExitsolPrune )

static

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

Definition at line 326 of file heur_prune.c.

References SCIP_OKAY.

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecPrune )

static

execution method of primal heuristic

Definition at line 335 of file heur_prune.c.

References CONNECT, GRAPH::cost, GRAPH::edges, FALSE, 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(), solstp_isValid(), 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,
		int *	solnode,
		int *	soledge,
		int *	globalsoledge,
		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
solnode	array for best solution nodes wrt prunegraph
soledge	array for best solution edges wrt prunegraph
globalsoledge	array storing best solution wrt g
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 489 of file heur_prune.c.

References BMScopyMemoryArray, CONNECT, GRAPH::cost, shortest_path::edge, GRAPH::edges, FALSE, FARAWAY, graph_mark(), GRAPH::knots, LT, nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisEQ(), SCIPisLE(), SCIPStpHeurLocalRun(), SCIPStpHeurTMBuildTree(), SCIPStpHeurTMBuildTreePcMw(), setNodeSolArray(), solstp_getObjBounded(), solstp_getOrg(), solstp_isValid(), STP_MWCSP, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, GRAPH::stp_type, TRUE, and UNKNOWN.

Referenced by computeNewSols(), SCIPStpHeurSlackPruneRun(), and updateSolution().

◆ 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 599 of file heur_prune.c.

References BMScopyMemoryArray, computeNewSols(), CONNECT, bidecomposition_reduction_parameters::depth, reduction_parameters::dualascent, GRAPH::edges, GRAPH::extended, FALSE, FARAWAY, getRedBound(), graph_copy(), graph_edge_del(), graph_free(), graph_get_nVET(), graph_initHistory(), graph_path_exit(), graph_path_init(), graph_pc_2org(), graph_pc_2trans(), graph_pc_isRootedPcMw(), graph_valid(), GRAPH::head, Is_term, GRAPH::knots, nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, NULL, PRUNE_MAXREDROUNDS, PRUNE_MINREDELIMS, reduction_base::redparameters, reduce_boundPruneHeur(), reduce_redLoopMw(), reduce_redLoopPc(), reduce_redLoopStp(), reduce_solAddNodesol(), reduce_solFree(), reduce_solGetNodesol(), reduce_solGetOffset(), reduce_solInit(), reduce_unconnected(), reduce_unconnectedRpcRmw(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPvarGetUbLocal(), setMinMaxElims(), setNodeSolArray(), solstp_getObjBounded(), solstp_isValid(), 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, UNKNOWN, and GRAPH::withInexactReductions.

Referenced by redcostGraphComputeSteinerTree(), and SCIP_DECL_HEUREXEC().

◆ SCIPStpIncludeHeurPrune()

SCIP_RETCODE SCIPStpIncludeHeurPrune ( SCIP * scip )

creates the prune primal heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 951 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(), 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_PRUNE_MAXFRQ

◆ PRUNE_TMRUNS

◆ PRUNE_TMRUNS_FAST

◆ PRUNE_MINREDELIMS

◆ PRUNE_MAXREDROUNDS

◆ MAXNTERMINALS

◆ MAXNEDGES

Function Documentation

◆ setNodeSolArray()

◆ computeNewSols()

◆ getRedBound()

◆ setMinMaxElims()

◆ SCIP_DECL_HEURCOPY()

◆ SCIP_DECL_HEURFREE()

◆ SCIP_DECL_HEURINIT()

◆ SCIP_DECL_HEURINITSOL()

◆ SCIP_DECL_HEUREXITSOL()

◆ SCIP_DECL_HEUREXEC()

◆ SCIPStpHeurPruneUpdateSols()

◆ SCIPStpHeurPruneRun()

◆ SCIPStpIncludeHeurPrune()