Detailed Description

Altenative-based reduction tests for Steiner problems.

Author: Daniel Rehfeldt

This file implements alternative-based reduction techniques for several Steiner problems. Most tests can be found in "Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem" by Daniel Rehfeldt and Thorsten Koch, or in "Reduction Techniques for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem" by Daniel Rehfeldt et al. Note that special distance tests as well as extending (alternative) reduction techniques can be found in separate files.

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

Definition in file reduce_alt.c.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "graph.h"
#include "reduce.h"
#include "misc_stp.h"
#include "probdata_stp.h"
#include "scip/scip.h"
#include "portab.h"

Go to the source code of this file.

Data Structures
struct	nearest_special_distance_test_data

Macros
#define	VERTEX_CONNECT 0

#define	VERTEX_TEMPNEIGHBOR 1

#define	VERTEX_NEIGHBOR 2

#define	VERTEX_OTHER 3

#define	STP_RED_CNSNN 25

#define	STP_RED_ANSMAXCANDS 500

#define	STP_RED_ANSEXMAXCANDS 50

#define	STP_RED_ANSMAXNEIGHBORS 25

Typedefs
typedef struct nearest_special_distance_test_data	NSV

Functions
static void	ansDeleteVertex (SCIP scip, GRAPH g, int RESTRICT marked, int RESTRICT nelims, int vertex)

static void	ansUnmark (const GRAPH g, int basenode, const int neighbarr, int nNeigbors, int *RESTRICT marked)

static void	ansProcessCandidateWithBridge (SCIP scip, GRAPH g, int RESTRICT marked, int RESTRICT nelims, SCIP_Real maxprize, int candvertex, int bridgeedge)

static void	ansProcessCandidate (SCIP scip, GRAPH g, int RESTRICT marked, int RESTRICT nelims, SCIP_Real maxprize, int candvertex)

static SCIP_RETCODE	nsvInitData (SCIP scip, const SD sdistance, const GRAPH g, int solnode, SCIP_Real fixed, NSV nsv)

static void	nsvInitRecording (STP_Vectype(int) edgesrecord, NSV *nsv)

static void	nsvFreeData (SCIP scip, NSV nsv)

static SCIP_Bool	nsvEdgeIsValid (const GRAPH g, const NSV nsv, int edge)

static void	nsvEdgeGetTermDists (const GRAPH g, const NSV nsv, int edge, int candidate_id, SCIP_Real dist_tail, SCIP_Real dist_head)

static SCIP_RETCODE	nsvEdgeContract (SCIP scip, int edge, int end_remain, int end_killed, GRAPH g, NSV nsv, int nelims)

static SCIP_RETCODE	nsvExec (SCIP scip, NSV nsv, GRAPH g, int nelims)

SCIP_RETCODE	reduce_nsvImplied (SCIP scip, const SD sdistance, GRAPH g, int solnode, SCIP_Real fixed, int nelims)

SCIP_RETCODE	reduce_nsvImpliedRecord (SCIP scip, const SD sdistance, GRAPH g, STP_Vectype(int) edgerecord)

SCIP_RETCODE	reduce_sl (SCIP scip, const int edgestate, GRAPH g, PATH vnoi, SCIP_Real fixed, int vbase, int vrnodes, STP_Bool visited, int solnode, int nelims)

SCIP_RETCODE	reduce_nv (SCIP scip, GRAPH g, PATH vnoi, SCIP_Real fixed, int edgearrint, int vbase, int solnode, int nelims)

SCIP_RETCODE	reduce_nvAdv (SCIP scip, const int edgestate, GRAPH g, PATH vnoi, SCIP_Real distance, SCIP_Real fixed, int edgearrint, int vbase, int distnode, int solnode, int *nelims)

SCIP_RETCODE	reduce_ans (SCIP scip, GRAPH g, int *nelims)

SCIP_RETCODE	reduce_ansAdv (SCIP scip, GRAPH g, int *nelims, SCIP_Bool extneigbhood)

SCIP_RETCODE	reduce_ansAdv2 (SCIP scip, GRAPH g, int *nelims)

SCIP_RETCODE	reduce_cnsAdv (SCIP scip, GRAPH g, int marked, int count)

SCIP_RETCODE	reduce_npv (SCIP scip, GRAPH g, PATH pathtail, int heap, int statetail, int statehead, int *nelims, int limit)

SCIP_RETCODE	reduce_chain2 (SCIP scip, GRAPH g, PATH pathtail, int heap, int statetail, int statehead, int *nelims, int limit)

SCIP_RETCODE	reduce_nnp (SCIP scip, GRAPH g, int *nelims)

SCIP_RETCODE	reduce_impliedProfitBased (SCIP scip, int edgelimit, GRAPH g, int solnode, SCIP_Real fixed, int *nelims)

SCIP_RETCODE	reduce_impliedProfitBasedRpc (SCIP scip, GRAPH g, REDSOLLOCAL redsollocal, SCIP_Real fixed, int *nelims)

Macro Definition Documentation

◆ VERTEX_CONNECT

#define VERTEX_CONNECT 0

Definition at line 48 of file reduce_alt.c.

Referenced by reduce_cnsAdv().

◆ VERTEX_TEMPNEIGHBOR

#define VERTEX_TEMPNEIGHBOR 1

Definition at line 49 of file reduce_alt.c.

Referenced by reduce_cnsAdv().

◆ VERTEX_NEIGHBOR

#define VERTEX_NEIGHBOR 2

Definition at line 50 of file reduce_alt.c.

Referenced by reduce_ansAdv2(), and reduce_cnsAdv().

◆ VERTEX_OTHER

#define VERTEX_OTHER 3

Definition at line 51 of file reduce_alt.c.

Referenced by reduce_cnsAdv().

◆ STP_RED_CNSNN

#define STP_RED_CNSNN 25

Definition at line 52 of file reduce_alt.c.

Referenced by reduce_ansAdv(), reduce_ansAdv2(), and reduce_cnsAdv().

◆ STP_RED_ANSMAXCANDS

#define STP_RED_ANSMAXCANDS 500

Definition at line 53 of file reduce_alt.c.

Referenced by reduce_ansAdv().

◆ STP_RED_ANSEXMAXCANDS

#define STP_RED_ANSEXMAXCANDS 50

Definition at line 54 of file reduce_alt.c.

Referenced by reduce_ansAdv().

◆ STP_RED_ANSMAXNEIGHBORS

#define STP_RED_ANSMAXNEIGHBORS 25

Definition at line 55 of file reduce_alt.c.

Referenced by reduce_ans().

Typedef Documentation

◆ NSV

typedef struct nearest_special_distance_test_data NSV

NSV test data

Function Documentation

◆ ansDeleteVertex()

static void ansDeleteVertex	(	SCIP *	scip,
		GRAPH *	g,
		int *RESTRICT	marked,
		int *RESTRICT	nelims,
		int	vertex
	)

inlinestatic

ans subtest

Parameters

scip	SCIP data structure
g	graph data structure
marked	nodes array
nelims	pointer to number of reductions
vertex	vertex

Definition at line 85 of file reduce_alt.c.

References FALSE, GRAPH::grad, graph_knot_del(), graph_knot_printInfo(), graph_pc_knotIsDummyTerm(), Is_term, GRAPH::mark, GRAPH::term, and TRUE.

Referenced by ansProcessCandidate(), and ansProcessCandidateWithBridge().

◆ ansUnmark()

static void ansUnmark	(	const GRAPH *	g,
		int	basenode,
		const int *	neighbarr,
		int	nNeigbors,
		int *RESTRICT	marked
	)

inlinestatic

un-marks

Parameters

g	graph data structure
basenode	base node
neighbarr	array of neighbors
nNeigbors	nNeigbors
marked	nodes array

Definition at line 111 of file reduce_alt.c.

References FALSE, GRAPH::grad, GRAPH::head, GRAPH::knots, GRAPH::oeat, GRAPH::outbeg, and x.

Referenced by reduce_ans(), reduce_ansAdv(), and reduce_ansAdv2().

◆ ansProcessCandidateWithBridge()

static void ansProcessCandidateWithBridge	(	SCIP *	scip,
		GRAPH *	g,
		int *RESTRICT	marked,
		int *RESTRICT	nelims,
		SCIP_Real	maxprize,
		int	candvertex,
		int	bridgeedge
	)

inlinestatic

ANS submethod for the case that the candidate vertex has exactly one non-dominated neighbor and both vertices combined are dominated

Parameters

scip	SCIP data structure
g	graph data structure
marked	nodes array
nelims	pointer to number of reductions
maxprize	value to not surpass
candvertex	candidate
bridgeedge	edge to neighbor

Definition at line 158 of file reduce_alt.c.

References ansDeleteVertex(), EAT_LAST, graph_edge_del(), GRAPH::head, LE, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_Real, SCIPdebugMessage, SCIPisGT(), SCIPisLE(), and TRUE.

Referenced by ansProcessCandidate().

◆ ansProcessCandidate()

static void ansProcessCandidate	(	SCIP *	scip,
		GRAPH *	g,
		int *RESTRICT	marked,
		int *RESTRICT	nelims,
		SCIP_Real	maxprize,
		int	candvertex
	)

static

ANS subtest

Parameters

scip	SCIP data structure
g	graph data structure
marked	nodes array
nelims	pointer to number of reductions
maxprize	value to not surpass
candvertex	candidate

Definition at line 219 of file reduce_alt.c.

References ansDeleteVertex(), ansProcessCandidateWithBridge(), graph_pc_knotIsDummyTerm(), GRAPH::head, Is_term, LE, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIPdebugMessage, SCIPisLE(), and GRAPH::term.

Referenced by reduce_ans(), reduce_ansAdv(), and reduce_ansAdv2().

◆ nsvInitData()

static SCIP_RETCODE nsvInitData	(	SCIP *	scip,
		const SD *	sdistance,
		const GRAPH *	g,
		int *	solnode,
		SCIP_Real *	fixed,
		NSV *	nsv
	)

static

initializes NSV test data

Parameters

scip	SCIP data structure
sdistance	special distances storage
g	graph structure
solnode	node array to mark whether an node is part of a given solution (CONNECT)
fixed	offset pointer
nsv	NSV

Definition at line 264 of file reduce_alt.c.

Referenced by reduce_nsvImplied(), and reduce_nsvImpliedRecord().

◆ nsvInitRecording()

static void nsvInitRecording	(	STP_Vectype(int)	edgesrecord,
		NSV *	nsv
	)

static

initializes NSV recordings

Parameters

edgesrecord	edges record
nsv	NSV

Definition at line 337 of file reduce_alt.c.

References TRUE.

Referenced by reduce_nsvImpliedRecord().

◆ nsvFreeData()

static void nsvFreeData	(	SCIP *	scip,
		NSV *	nsv
	)

static

frees NSV test data

Parameters

scip	SCIP data structure
nsv	NSV

Definition at line 352 of file reduce_alt.c.

References nearest_special_distance_test_data::candidates_bottleneck, nearest_special_distance_test_data::candidates_edge, nearest_special_distance_test_data::candidates_head, nearest_special_distance_test_data::candidates_headdist, nearest_special_distance_test_data::candidates_isLink, nearest_special_distance_test_data::candidates_tail, nearest_special_distance_test_data::candidates_taildist, nearest_special_distance_test_data::nodes_isBlocked, and SCIPfreeBufferArray.

Referenced by reduce_nsvImplied(), and reduce_nsvImpliedRecord().

◆ nsvEdgeIsValid()

static SCIP_Bool nsvEdgeIsValid	(	const GRAPH *	g,
		const NSV *	nsv,
		int	edge
	)

inlinestatic

edge in NSV test can possibly still be contracted?

Parameters

g	graph structure
nsv	NSV data
edge	the edge

Definition at line 370 of file reduce_alt.c.

References FALSE, graph_edge_isDeleted(), graph_edge_isInRange(), GRAPH::head, nearest_special_distance_test_data::nodes_isBlocked, GRAPH::tail, and TRUE.

Referenced by nsvExec().

◆ nsvEdgeGetTermDists()

static void nsvEdgeGetTermDists	(	const GRAPH *	g,
		const NSV *	nsv,
		int	edge,
		int	candidate_id,
		SCIP_Real *	dist_tail,
		SCIP_Real *	dist_head
	)

inlinestatic

get special implied distances to terminals from both endpoints of given edge

Parameters

g	graph structure
nsv	NSV data
edge	the edge
candidate_id	id of candidate
dist_tail	distance from tail
dist_head	distance from head

Definition at line 400 of file reduce_alt.c.

References nearest_special_distance_test_data::candidates_bottleneck, nearest_special_distance_test_data::candidates_edge, nearest_special_distance_test_data::candidates_headdist, nearest_special_distance_test_data::candidates_taildist, GRAPH::cost, FARAWAY, GE, graph_tpathsGet4CloseTermsLE(), GT, GRAPH::head, Is_term, SCIP_Real, nearest_special_distance_test_data::sdistance, GRAPH::tail, GRAPH::term, and special_distance_storage::terminalpaths.

Referenced by nsvExec().

◆ nsvEdgeContract()

static SCIP_RETCODE nsvEdgeContract	(	SCIP *	scip,
		int	edge,
		int	end_remain,
		int	end_killed,
		GRAPH *	g,
		NSV *	nsv,
		int *	nelims
	)

inlinestatic

contract edge in NSV test

Parameters

scip	SCIP data structure
edge	the edge
end_remain	survivor end node of edge
end_killed	other end node
g	graph structure
nsv	NSV data
nelims	number of eliminations

Definition at line 497 of file reduce_alt.c.

References GRAPH::cost, graph_edge_printInfo(), graph_knot_chg(), graph_knot_contractFixed(), nearest_special_distance_test_data::nodes_isBlocked, SCIP_CALL, SCIP_OKAY, STP_TERM, StpVecPushBack, and TRUE.

Referenced by nsvExec().

◆ nsvExec()

static SCIP_RETCODE nsvExec	(	SCIP *	scip,
		NSV *	nsv,
		GRAPH *	g,
		int *	nelims
	)

static

executes actual NSV test

Parameters

scip	SCIP data structure
nsv	NSV
g	graph structure
nelims	number of eliminations

Definition at line 535 of file reduce_alt.c.

References nearest_special_distance_test_data::candidates_bottleneck, nearest_special_distance_test_data::candidates_edge, nearest_special_distance_test_data::candidates_isLink, GRAPH::cost, EQ, FARAWAY, flipedge, GE, graph_edge_isInRange(), graph_valid(), GRAPH::head, Is_term, LE, nsvEdgeContract(), nsvEdgeGetTermDists(), nsvEdgeIsValid(), reduce_cutEdgeTryPrune(), reduce_sdprofitGetProfit(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, nearest_special_distance_test_data::sdistance, special_distance_storage::sdprofit, GRAPH::tail, and GRAPH::term.

Referenced by reduce_nsvImplied(), and reduce_nsvImpliedRecord().

◆ reduce_nsvImplied()

SCIP_RETCODE reduce_nsvImplied	(	SCIP *	scip,
		const SD *	sdistance,
		GRAPH *	g,
		int *	solnode,
		SCIP_Real *	fixed,
		int *	nelims
	)

implied version of NSV test

Parameters

scip	SCIP data structure
sdistance	special distances storage
g	graph structure
solnode	node array to mark whether an node is part of a given solution (CONNECT)
fixed	offset pointer
nelims	number of eliminations

Definition at line 621 of file reduce_alt.c.

References nsvExec(), nsvFreeData(), nsvInitData(), SCIP_CALL, and SCIP_OKAY.

Referenced by reduce_impliedProfitBased(), testNsvImpliedContractsCutDistEdge(), testNsvImpliedContractsCutDistMiddleEdge(), testNsvImpliedContractsEdge(), testNsvImpliedContractsEdge2(), and testNsvImpliedContractsImpliedToTermEdge().

◆ reduce_nsvImpliedRecord()

SCIP_RETCODE reduce_nsvImpliedRecord	(	SCIP *	scip,
		const SD *	sdistance,
		GRAPH *	g,
		STP_Vectype(int) *	edgerecord
	)

implied version of NSV test. Does not perform the reductions, but rather records them

Parameters

scip	SCIP data structure
sdistance	special distances storage
g	graph structure
edgerecord	keeps number edges

Definition at line 643 of file reduce_alt.c.

References nsvExec(), nsvFreeData(), nsvInitData(), nsvInitRecording(), NULL, SCIP_CALL, and SCIP_OKAY.

Referenced by reduce_impliedProfitBasedRpc().

◆ reduce_sl()

SCIP_RETCODE reduce_sl	(	SCIP *	scip,
		const int *	edgestate,
		GRAPH *	g,
		PATH *	vnoi,
		SCIP_Real *	fixed,
		int *	vbase,
		int *	vrnodes,
		STP_Bool *	visited,
		int *	solnode,
		int *	nelims
	)

shortest link reduction

Parameters

scip	SCIP data structure
edgestate	for propagation or NULL
g	graph data structure
vnoi	Voronoi data structure
fixed	offset pointer
vbase	Voronoi/shortest path bases array
vrnodes	Voronoi/shortest path array
visited	Voronoi/shortest path array
solnode	node array to mark whether an node is part of a given solution (CONNECT), or NULL
nelims	pointer to store number of eliminations

Definition at line 665 of file reduce_alt.c.

References BMSclearMemoryArray, GRAPH::cost, shortest_path::dist, EAT_LAST, EDGE_BLOCKED, EQ, FALSE, FARAWAY, GE, GRAPH::grad, graph_edge_printInfo(), graph_getIsTermArray(), graph_knot_chg(), graph_knot_contractFixed(), graph_mark(), graph_pc_contractEdge(), graph_pc_isPc(), graph_pc_isUnrootedPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_knotIsNonLeafTerm(), graph_pc_knotToFixedTerm(), graph_voronoiTerms(), GRAPH::head, Is_anyTerm, Is_pseudoTerm, GRAPH::knots, LE, LT, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPfreeBufferArray, SCIPisGE(), SCIPisLE(), SCIPisLT(), GRAPH::source, STP_RPCSPG, STP_TERM, GRAPH::stp_type, STP_Vectype, StpVecFree, StpVecGetSize, StpVecPopBack, StpVecPushBack, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by execNvSl().

◆ reduce_nv()

SCIP_RETCODE reduce_nv	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	vnoi,
		SCIP_Real *	fixed,
		int *	edgearrint,
		int *	vbase,
		int *	solnode,
		int *	nelims
	)

Parameters

scip	SCIP data structure
g	graph data structure
vnoi	Voronoi data structure
fixed	offset pointer
edgearrint	edge int array for internal computations
vbase	array for internal computations
solnode	node array to mark whether an node is part of a given solution (CONNECT), or NULL
nelims	pointer to store number of eliminations

Definition at line 932 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, FARAWAY, GRAPH::grad, graph_knot_contractFixed(), graph_pc_contractEdge(), graph_voronoiWithDist(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPisGE(), SCIPisLE(), GRAPH::source, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, and UNKNOWN.

◆ reduce_nvAdv()

SCIP_RETCODE reduce_nvAdv	(	SCIP *	scip,
		const int *	edgestate,
		GRAPH *	g,
		PATH *	vnoi,
		SCIP_Real *	distance,
		SCIP_Real *	fixed,
		int *	edgearrint,
		int *	vbase,
		int *	distnode,
		int *	solnode,
		int *	nelims
	)

Parameters

scip	SCIP data structure
edgestate	for propagation or NULL
g	graph data structure
vnoi	Voronoi data structure
distance	nodes-sized distance array
fixed	offset pointer
edgearrint	edges-sized array
vbase	Voronoi base array
distnode	nodes-sized distance array
solnode	node array to mark whether an node is part of a given solution (CONNECT), or NULL
nelims	pointer to store number of eliminations

Definition at line 1121 of file reduce_alt.c.

References BMSclearMemoryArray, GRAPH::cost, shortest_path::dist, EAT_LAST, EDGE_BLOCKED, GRAPH::extended, FALSE, FARAWAY, flipedge, GE, GRAPH::grad, graph_edge_del(), graph_get_nNodes(), graph_get_nTerms(), graph_getIsTermArray(), graph_knot_contractFixed(), graph_mark(), graph_pc_contractEdge(), graph_pc_knotIsNonLeafTerm(), graph_voronoiWithDist(), GRAPH::head, Is_term, GRAPH::knots, LE, GRAPH::mark, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisGE(), SCIPisLE(), SCIPisLT(), GRAPH::source, STP_PCSPG, STP_RPCSPG, STP_SPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

Referenced by execNvSl().

◆ reduce_ans()

SCIP_RETCODE reduce_ans	(	SCIP *	scip,
		GRAPH *	g,
		int *	nelims
	)

adjacent neighbourhood reduction for the MWCSP

Parameters

scip	SCIP data structure
g	graph data structure
nelims	pointer to number of reductions

Definition at line 1470 of file reduce_alt.c.

References ansProcessCandidate(), ansUnmark(), EAT_LAST, FALSE, GRAPH::grad, graph_get_nNodes(), graph_mark(), graph_pc_isMw(), graph_pc_knotIsDummyTerm(), graph_valid(), GRAPH::head, Is_term, LT, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, STP_RED_ANSMAXNEIGHBORS, GRAPH::term, and TRUE.

Referenced by redLoopInnerMw(), testRmwAnsDeletesOneEdge(), testRmwAnsDeletesOneNode(), and testRmwAnsDeletesTwoNodes().

◆ reduce_ansAdv()

SCIP_RETCODE reduce_ansAdv	(	SCIP *	scip,
		GRAPH *	g,
		int *	nelims,
		SCIP_Bool	extneigbhood
	)

advanced adjacent neighbourhood reduction for the MWCSP

Parameters

scip	SCIP data structure
g	graph data structure
nelims	pointer to number of performed reductions
extneigbhood	use extended neighbour hood

Definition at line 1544 of file reduce_alt.c.

References ansProcessCandidate(), ansUnmark(), EAT_LAST, FALSE, GRAPH::grad, graph_get_nNodes(), graph_pc_isMw(), graph_pc_knotIsDummyTerm(), graph_valid(), GRAPH::head, Is_term, GRAPH::mark, MAX, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisGT(), SCIPisLE(), STP_RED_ANSEXMAXCANDS, STP_RED_ANSMAXCANDS, STP_RED_CNSNN, GRAPH::term, and TRUE.

Referenced by redLoopInnerMw().

◆ reduce_ansAdv2()

SCIP_RETCODE reduce_ansAdv2	(	SCIP *	scip,
		GRAPH *	g,
		int *	nelims
	)

alternative advanced adjacent neighbourhood reduction for the MWCSP

Parameters

scip	SCIP data structure
g	graph data structure
nelims	pointer to number of reductions

Definition at line 1656 of file reduce_alt.c.

References ansProcessCandidate(), ansUnmark(), EAT_LAST, FALSE, GRAPH::grad, graph_get_nNodes(), graph_pc_isMw(), graph_pc_knotIsDummyTerm(), graph_valid(), GT, GRAPH::head, Is_term, LT, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisGE(), SCIPisLE(), STP_RED_CNSNN, GRAPH::term, TRUE, UNKNOWN, and VERTEX_NEIGHBOR.

Referenced by redLoopInnerMw().

◆ reduce_cnsAdv()

SCIP_RETCODE reduce_cnsAdv	(	SCIP *	scip,
		GRAPH *	g,
		int *	marked,
		int *	count
	)

advanced connected neighborhood subset reduction test for the MWCSP

Parameters

scip	SCIP data structure
g	graph data structure
marked	nodes array for internal use
count	pointer to number of reductions

Definition at line 1793 of file reduce_alt.c.

References EAT_LAST, FALSE, GE, GRAPH::grad, graph_edge_del(), graph_get_nNodes(), GRAPH::head, Is_term, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_OKAY, SCIP_Real, SCIPisGE(), SCIPisGT(), SCIPisLE(), STP_MWCSP, STP_RED_CNSNN, GRAPH::stp_type, GRAPH::term, TRUE, UNKNOWN, VERTEX_CONNECT, VERTEX_NEIGHBOR, VERTEX_OTHER, and VERTEX_TEMPNEIGHBOR.

◆ reduce_npv()

SCIP_RETCODE reduce_npv	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	pathtail,
		int *	heap,
		int *	statetail,
		int *	statehead,
		int *	nelims,
		int	limit
	)

non-positive vertex reduction for the MWCSP

Definition at line 2067 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_edge_add(), graph_edge_del(), graph_free(), graph_get_nNodes(), graph_init(), graph_knot_add(), graph_knot_del(), graph_mark(), graph_path_exec(), graph_path_exit(), graph_path_init(), GRAPH::head, Is_term, GRAPH::mark, MST_MODE, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, reduce_getSdByPaths(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisGE(), SCIPisGT(), SCIPisLE(), GRAPH::term, TRUE, and UNKNOWN.

Referenced by redLoopInnerMw(), and testRmwNpv3DeletesNode().

◆ reduce_chain2()

SCIP_RETCODE reduce_chain2	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	pathtail,
		int *	heap,
		int *	statetail,
		int *	statehead,
		int *	nelims,
		int	limit
	)

chain reduction (NPV_2) for the MWCSP

Definition at line 2445 of file reduce_alt.c.

References shortest_path::dist, shortest_path::edge, FALSE, FARAWAY, GRAPH::grad, graph_edge_del(), graph_get_nNodes(), GRAPH::head, Is_term, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, reduce_getSdByPaths(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisGE(), GRAPH::term, TRUE, and UNKNOWN.

Referenced by redLoopInnerMw(), and testRmwChain2DeletesNode().

◆ reduce_nnp()

SCIP_RETCODE reduce_nnp	(	SCIP *	scip,
		GRAPH *	g,
		int *	nelims
	)

non-negative path reduction for the MWCSP

Parameters

scip	SCIP data structure
g	graph data structure
nelims	pointer to number of reductions

Definition at line 2534 of file reduce_alt.c.

References EAT_LAST, FALSE, graph_edge_del(), graph_get_nNodes(), graph_pc_isMw(), graph_valid(), GRAPH::head, LT, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, and TRUE.

Referenced by redLoopInnerMw().

◆ reduce_impliedProfitBased()

SCIP_RETCODE reduce_impliedProfitBased	(	SCIP *	scip,
		int	edgelimit,
		GRAPH *	g,
		int *	solnode,
		SCIP_Real *	fixed,
		int *	nelims
	)

Combined implied-profit based tests: First elimination tests are used, afterwards edge contraction test are applied. NOTE: The expensive part is to build the bottleneck distances, thus we always apply all other tests.

Parameters

scip	SCIP data structure
edgelimit	limit for star test
g	graph structure
solnode	node array to mark whether an node is part of a given solution (CONNECT)
fixed	offset pointer
nelims	number of eliminations

Definition at line 2609 of file reduce_alt.c.

References special_distance_storage::blctree, FALSE, graph_pc_isPcMw(), graph_tpathsRecomputeBiased(), reduce_nsvImplied(), reduce_sdBiased(), reduce_sdFree(), reduce_sdInitBiasedBottleneck(), reduce_sdprofitBuildFromBLC(), reduce_sdStarBiasedWithProfit(), reduce_unconnected(), reduce_unconnectedRpcRmw(), SCIP_CALL, SCIP_OKAY, nearest_special_distance_test_data::sdistance, special_distance_storage::sdprofit, special_distance_storage::terminalpaths, GRAPH::terms, and TRUE.

Referenced by redLoopInnerStp().

◆ reduce_impliedProfitBasedRpc()

SCIP_RETCODE reduce_impliedProfitBasedRpc	(	SCIP *	scip,
		GRAPH *	g,
		REDSOLLOCAL *	redsollocal,
		SCIP_Real *	fixed,
		int *	nelims
	)

similar to above, but for rooted-prize collecting Steiner tree problem

Parameters

scip	SCIP data structure
g	graph structure
redsollocal	primal bound info
fixed	offset pointer
nelims	number of eliminations

Definition at line 2664 of file reduce_alt.c.

References special_distance_storage::blctree, GRAPH::cost, EAT_FREE, GRAPH::edges, FALSE, FARAWAY, GE, graph_edge_del(), graph_edge_isInRange(), graph_edge_printInfo(), graph_free(), graph_mark(), graph_path_exit(), graph_path_init(), graph_pc_contractEdge(), graph_pc_knotIsFixedTerm(), graph_pc_knotIsPropPotTerm(), graph_tpathsRecomputeBiased(), graph_transRpcGetSpg(), graph_transRpcToSpgIsStable(), graph_valid(), GRAPH::head, Is_term, NULL, GRAPH::oeat, reduce_nsvImpliedRecord(), reduce_sdBiased(), reduce_sdFree(), reduce_sdInitBiasedBottleneck(), reduce_sdprofitBuildFromBLC(), reduce_sollocalGetSolnode(), reduce_sollocalGetUpperBound(), reduce_sollocalRebuildTry(), reduce_sollocalSetOffset(), reduce_unconnectedRpcRmw(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPfreeMemoryArray, nearest_special_distance_test_data::sdistance, special_distance_storage::sdprofit, GRAPH::source, STP_RPCSPG, GRAPH::stp_type, STP_Vectype, StpVecFree, StpVecGetSize, GRAPH::tail, GRAPH::term, special_distance_storage::terminalpaths, GRAPH::terms, and TRUE.

Referenced by reduce_redLoopPc().

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ VERTEX_CONNECT

◆ VERTEX_TEMPNEIGHBOR

◆ VERTEX_NEIGHBOR

◆ VERTEX_OTHER

◆ STP_RED_CNSNN

◆ STP_RED_ANSMAXCANDS

◆ STP_RED_ANSEXMAXCANDS

◆ STP_RED_ANSMAXNEIGHBORS

Typedef Documentation

◆ NSV

Function Documentation

◆ ansDeleteVertex()

◆ ansUnmark()

◆ ansProcessCandidateWithBridge()

◆ ansProcessCandidate()

◆ nsvInitData()

◆ nsvInitRecording()

◆ nsvFreeData()

◆ nsvEdgeIsValid()

◆ nsvEdgeGetTermDists()

◆ nsvEdgeContract()

◆ nsvExec()

◆ reduce_nsvImplied()

◆ reduce_nsvImpliedRecord()

◆ reduce_sl()

◆ reduce_nv()

◆ reduce_nvAdv()

◆ reduce_ans()

◆ reduce_ansAdv()

◆ reduce_ansAdv2()

◆ reduce_cnsAdv()

◆ reduce_npv()

◆ reduce_chain2()

◆ reduce_nnp()

◆ reduce_impliedProfitBased()

◆ reduce_impliedProfitBasedRpc()