Detailed Description

bound based reductions for Steiner tree problems

Author: Daniel Rehfeldt

This file implements bound-based reduction techniques for several Steiner problems. Most tests can be found in "A Generic Approach to Solving the Steiner Tree Problem and Variants" by Daniel Rehfeldt.

A list of all interface methods can be found in reduce.h.

Definition in file reduce_bnd.c.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <assert.h>
#include "graph.h"
#include "reduce.h"
#include "heur_tm.h"
#include "heur_ascendprune.h"
#include "misc_stp.h"
#include "solstp.h"
#include "probdata_stp.h"
#include "prop_stp.h"

Go to the source code of this file.

Macros
#define	BND_TMHEUR_NRUNS 20

Functions
static SCIP_RETCODE	computeSteinerTree (SCIP scip, GRAPH graph, SCIP_Real cost, SCIP_Real costrev, int result, STP_Bool stnode, SCIP_Real upperbound, SCIP_Bool success)

static SCIP_RETCODE	boundPruneHeur (SCIP scip, GRAPH graph, PATH vnoi, SCIP_Real cost, SCIP_Real radius, SCIP_Real costrev, SCIP_Real offset, int heap, int state, int vbase, const int solnode, const int soledge, int *nelims, int minelims)

static SCIP_RETCODE	boundPruneHeurMw (SCIP scip, GRAPH graph, PATH vnoi, SCIP_Real cost, SCIP_Real radius, SCIP_Real costrev, SCIP_Real offset, int heap, int state, int vbase, const int solnode, const int soledge, int *nelims, int minelims)

SCIP_RETCODE	reduce_bound (SCIP scip, GRAPH graph, PATH vnoi, SCIP_Real radius, SCIP_Real offset, SCIP_Real upperbound, int heap, int state, int vbase, int nelims)

SCIP_RETCODE	reduce_boundMw (SCIP scip, GRAPH graph, PATH vnoi, SCIP_Real offset, int heap, int state, int vbase, int result, int *nelims)

SCIP_RETCODE	reduce_boundPruneHeur (SCIP scip, GRAPH graph, PATH vnoi, SCIP_Real cost, SCIP_Real radius, SCIP_Real costrev, SCIP_Real offset, int heap, int state, int vbase, const int solnode, const int soledge, int *nelims, int minelims)

SCIP_RETCODE	reduce_boundHopDa (SCIP scip, GRAPH graph, int nelims, SCIP_RANDNUMGEN randnumgen)

SCIP_RETCODE	reduce_boundHop (SCIP scip, GRAPH graph, PATH vnoi, SCIP_Real cost, SCIP_Real radius, SCIP_Real costrev, int heap, int state, int vbase, int nelims)

SCIP_RETCODE	reduce_boundHopR (SCIP scip, GRAPH graph, PATH vnoi, SCIP_Real cost, SCIP_Real costrev, SCIP_Real pathdist, int heap, int state, int vbase, int nelims, int *pathedge)

SCIP_RETCODE	reduce_boundHopRc (SCIP scip, GRAPH graph, PATH vnoi, SCIP_Real cost, SCIP_Real costrev, SCIP_Real pathdist, SCIP_Real objval, int heap, int state, int vbase, int nelims, int *pathedge, SCIP_Bool fix)

Macro Definition Documentation

◆ BND_TMHEUR_NRUNS

#define BND_TMHEUR_NRUNS 20

number of runs of constructive heuristic

Definition at line 46 of file reduce_bnd.c.

Referenced by computeSteinerTree().

Function Documentation

◆ computeSteinerTree()

static SCIP_RETCODE computeSteinerTree	(	SCIP *	scip,
		GRAPH *	graph,
		SCIP_Real *	cost,
		SCIP_Real *	costrev,
		int *	result,
		STP_Bool *	stnode,
		SCIP_Real *	upperbound,
		SCIP_Bool *	success
	)

static

bound-based reductions for the (R)PCSTP, the MWCSP and the STP

Parameters

scip	SCIP data structure
graph	graph data structure
cost	edge cost array
costrev	reversed edge cost array
result	result edges
stnode	result nodes
upperbound	pointer to an upper bound
success	success?

Definition at line 51 of file reduce_bnd.c.

References BND_TMHEUR_NRUNS, CONNECT, GRAPH::extended, FALSE, FARAWAY, graph_get_nEdges(), graph_get_nNodes(), graph_getEdgeCosts(), graph_pc_2org(), graph_pc_2trans(), graph_pc_isMw(), graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_solGetObj(), GRAPH::head, GRAPH::mark, nnodes, NULL, pcmode_fromheurdata, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArrayNull, SCIPisEQ(), SCIPStpHeurTMCompStarts(), SCIPStpHeurTMRun(), solstp_getObjBounded(), GRAPH::source, GRAPH::tail, TRUE, and UNKNOWN.

Referenced by reduce_bound().

◆ boundPruneHeur()

static SCIP_RETCODE boundPruneHeur	(	SCIP *	scip,
		GRAPH *	graph,
		PATH *	vnoi,
		SCIP_Real *	cost,
		SCIP_Real *	radius,
		SCIP_Real *	costrev,
		SCIP_Real *	offset,
		int *	heap,
		int *	state,
		int *	vbase,
		const int *	solnode,
		const int *	soledge,
		int *	nelims,
		int	minelims
	)

static

heuristic bound-based reductions for non (R)MWCS

Parameters

scip	SCIP data structure
graph	graph data structure
vnoi	Voronoi data structure
cost	edge cost array
radius	radius array
costrev	reversed edge cost array
offset	pointer to the offset
heap	heap array
state	array to store state of a node during Voronoi computation
vbase	Voronoi base to each node
solnode	array of nodes of current solution that is not to be destroyed
soledge	array of edges of current solution that is not to be destroyed
nelims	pointer to store number of eliminated edges
minelims	minimum number of edges to be eliminated

Definition at line 149 of file reduce_bnd.c.

References bound, CONNECT, GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_add2ndTermPaths(), graph_add3rdTermPaths(), graph_edge_del(), graph_free(), graph_getEdgeCosts(), graph_init(), graph_knot_chg(), graph_knot_delPseudo(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_pc_isMw(), graph_valid(), graph_voronoiWithRadius(), GRAPH::head, Is_pseudoTerm, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_state, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPepsilon(), SCIPfreeBufferArray, SCIPisGE(), SCIPisGT(), SCIPisLT(), SCIPsortReal(), GRAPH::source, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by reduce_boundPruneHeur().

◆ boundPruneHeurMw()

static SCIP_RETCODE boundPruneHeurMw	(	SCIP *	scip,
		GRAPH *	graph,
		PATH *	vnoi,
		SCIP_Real *	cost,
		SCIP_Real *	radius,
		SCIP_Real *	costrev,
		SCIP_Real *	offset,
		int *	heap,
		int *	state,
		int *	vbase,
		const int *	solnode,
		const int *	soledge,
		int *	nelims,
		int	minelims
	)

static

heuristic bound-based reductions for (R)MWCS

Parameters

scip	SCIP data structure
graph	graph data structure
vnoi	Voronoi data structure
cost	edge cost array
radius	radius array
costrev	reversed edge cost array
offset	pointer to the offset
heap	heap array
state	array to store state of a node during Voronoi computation
vbase	Voronoi base to each node
solnode	array of nodes of current solution that is not to be destroyed
soledge	array of edges of current solution that is not to be destroyed
nelims	pointer to store number of eliminated edges
minelims	minimum number of edges to be eliminated

Definition at line 487 of file reduce_bnd.c.

References CONNECT, GRAPH::cost, shortest_path::dist, EAT_LAST, GRAPH::edges, GRAPH::extended, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_add2ndTermPaths(), graph_edge_del(), graph_getEdgeCosts(), graph_pc_isMw(), graph_valid(), graph_voronoiMw(), GRAPH::head, Is_anyTerm, Is_pseudoTerm, GRAPH::knots, GRAPH::mark, nnodes, nterms, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPepsilon(), SCIPisGT(), SCIPisLT(), SCIPsortReal(), GRAPH::source, STP_MWCSP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by reduce_boundPruneHeur().

◆ reduce_bound()

SCIP_RETCODE reduce_bound	(	SCIP *	scip,
		GRAPH *	graph,
		PATH *	vnoi,
		SCIP_Real *	radius,
		SCIP_Real *	offset,
		SCIP_Real *	upperbound,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	nelims
	)

bound-based reductions for the (R)PCSTP, the MWCSP and the STP

Parameters

scip	SCIP data structure
graph	graph data structure
vnoi	Voronoi data structure
radius	radius array
offset	pointer to the offset
upperbound	pointer to an upper bound
heap	heap array
state	array to store state of a node during Voronoi computation
vbase	Voronoi base to each node
nelims	pointer to store number of eliminated edges

Definition at line 655 of file reduce_bnd.c.

References bound, computeSteinerTree(), CONNECT, GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::extended, FARAWAY, flipedge, GRAPH::grad, graph_add2ndTermPaths(), graph_add3rdTermPaths(), graph_add4thTermPaths(), graph_edge_del(), graph_free(), graph_get4nextTTerms(), graph_get_nEdges(), graph_get_nNodes(), graph_getEdgeCosts(), graph_init(), graph_knot_chg(), graph_knot_delPseudo(), graph_knot_printInfo(), graph_mark(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_pc_deleteTerm(), graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), graph_printInfo(), graph_valid(), graph_voronoiWithRadius(), GT, GRAPH::head, Is_pseudoTerm, Is_term, LT, GRAPH::mark, MST_MODE, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_state, GRAPH::prize, r, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPisGE(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPsortReal(), SCIPsortRealInt(), GRAPH::source, STP_DHCSTP, STP_MWCSP, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by execPc_BND(), redLoopInnerStp(), and reduce_hc().

◆ reduce_boundMw()

SCIP_RETCODE reduce_boundMw	(	SCIP *	scip,
		GRAPH *	graph,
		PATH *	vnoi,
		SCIP_Real *	offset,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	result,
		int *	nelims
	)

Bound-based reduction method for the MWCSP . The reduction method tries to eliminate nodes and vertices by checking whether an upper bound for each solution that contains them is smaller than the best known solution value. The essence of the approach is a decomposition of the graph such that this upper bound is minimized.

Parameters

scip	SCIP data structure
graph	graph data structure
vnoi	Voronoi data structure (size 3 * nnodes)
offset	pointer to the offset
heap	heap array
state	array to store state of a node during Voronoi computation
vbase	Voronoi base to each node
result	solution array or NULL
nelims	pointer to store number of eliminated edges

Definition at line 1058 of file reduce_bnd.c.

References bound, CONNECT, GRAPH::cost, shortest_path::dist, EAT_LAST, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_add2ndTermPaths(), graph_edge_del(), graph_pc_isRootedPcMw(), graph_voronoiMw(), graph_voronoiWithRadiusMw(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPisGE(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPsortReal(), GRAPH::source, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by redLoopInnerMw().

◆ reduce_boundPruneHeur()

SCIP_RETCODE reduce_boundPruneHeur	(	SCIP *	scip,
		GRAPH *	graph,
		PATH *	vnoi,
		SCIP_Real *	cost,
		SCIP_Real *	radius,
		SCIP_Real *	costrev,
		SCIP_Real *	offset,
		int *	heap,
		int *	state,
		int *	vbase,
		const int *	solnode,
		const int *	soledge,
		int *	nelims,
		int	minelims
	)

heuristic bound-based reductions for the (R)PCSTP, the MWCSP and the STP; used by prune heuristic

Parameters

scip	SCIP data structure
graph	graph data structure
vnoi	Voronoi data structure
cost	edge cost array
radius	radius array
costrev	reversed edge cost array
offset	pointer to the offset
heap	heap array
state	array to store state of a node during Voronoi computation
vbase	Voronoi base to each node
solnode	array of nodes of current solution that is not to be destroyed
soledge	array of edges of current solution that is not to be destroyed
nelims	pointer to store number of eliminated edges
minelims	minimum number of edges to be eliminated

Definition at line 1237 of file reduce_bnd.c.

References boundPruneHeur(), boundPruneHeurMw(), GRAPH::extended, graph_pc_isMw(), graph_valid(), NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, and GRAPH::source.

Referenced by SCIPStpHeurPruneRun().

◆ reduce_boundHopDa()

SCIP_RETCODE reduce_boundHopDa	(	SCIP *	scip,
		GRAPH *	graph,
		int *	nelims,
		SCIP_RANDNUMGEN *	randnumgen
	)

dual ascent based hop reductions for HCDSTP

Parameters

scip	SCIP data structure
graph	graph data structure
nelims	pointer to store number of reduced edges
randnumgen	random number generator

Definition at line 1286 of file reduce_bnd.c.

References BMScopyMemoryArray, GRAPH::cost, reduce_costs_reduction_parameters::damode, EQ, extred_none, FALSE, FARAWAY, graph_get_nEdges(), graph_valid(), LT, NULL, reduce_da(), reduce_unconnectedForDirected(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, and STP_DAMODE_HOPS.

Referenced by reduce_hc().

◆ reduce_boundHop()

SCIP_RETCODE reduce_boundHop	(	SCIP *	scip,
		GRAPH *	graph,
		PATH *	vnoi,
		SCIP_Real *	cost,
		SCIP_Real *	radius,
		SCIP_Real *	costrev,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	nelims
	)

bound-based reduction test for the HCDSTP

Definition at line 1323 of file reduce_bnd.c.

References bound, CONNECT, GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_add2ndTermPaths(), graph_edge_del(), graph_free(), graph_init(), graph_knot_chg(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_valid(), graph_voronoiWithRadius(), GRAPH::head, GRAPH::hoplimit, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_state, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisGT(), SCIPisLT(), SCIPsortReal(), GRAPH::source, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by reduce_hc().

◆ reduce_boundHopR()

SCIP_RETCODE reduce_boundHopR	(	SCIP *	scip,
		GRAPH *	graph,
		PATH *	vnoi,
		SCIP_Real *	cost,
		SCIP_Real *	costrev,
		SCIP_Real *	pathdist,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	nelims,
		int *	pathedge
	)

hop bound-based reduction test for the HCDSTP

Definition at line 1518 of file reduce_bnd.c.

References bound, GRAPH::cost, shortest_path::dist, EAT_LAST, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_add1stTermPaths(), graph_edge_del(), graph_path_execX(), graph_valid(), GRAPH::head, GRAPH::hoplimit, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGT(), SCIPisLT(), GRAPH::source, GRAPH::term, and TRUE.

Referenced by reduce_hc().

◆ reduce_boundHopRc()

SCIP_RETCODE reduce_boundHopRc	(	SCIP *	scip,
		GRAPH *	graph,
		PATH *	vnoi,
		SCIP_Real *	cost,
		SCIP_Real *	costrev,
		SCIP_Real *	pathdist,
		SCIP_Real	objval,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	nelims,
		int *	pathedge,
		SCIP_Bool	fix
	)

Definition at line 1646 of file reduce_bnd.c.

References BLOCKED, bound, CONNECT, GRAPH::cost, DEFAULT_HOPFACTOR, shortest_path::dist, EAT_LAST, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_add1stTermPaths(), graph_edge_del(), graph_path_execX(), graph_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, pcmode_fromheurdata, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetCutoffbound(), SCIPisGT(), SCIPisLT(), SCIPprobdataGetVars(), SCIPStpFixEdgeVarTo0(), SCIPStpHeurTMRun(), SCIPvarGetUbLocal(), GRAPH::source, GRAPH::term, TRUE, and UNKNOWN.

Referenced by reduce_hc().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ BND_TMHEUR_NRUNS

Function Documentation

◆ computeSteinerTree()

◆ boundPruneHeur()

◆ boundPruneHeurMw()

◆ reduce_bound()

◆ reduce_boundMw()

◆ reduce_boundPruneHeur()

◆ reduce_boundHopDa()

◆ reduce_boundHop()

◆ reduce_boundHopR()

◆ reduce_boundHopRc()