Detailed Description

Path deletion reduction test for Steiner problems.

Author: Daniel Rehfeldt

This file implements an improved version of the so called "path substitution test" by Polzin and Vahdati Daneshmand.

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

Definition in file reduce_path.c.

#include <assert.h>
#include "reduce.h"
#include "extreduce.h"

Data Structures
struct	path_replacement

Macros
#define	SP_MAXNDISTS 10000

#define	SP_MAXLENGTH 11

#define	SP_MAXDEGREE 8

#define	SP_MAXDEGREE_FAST 5

#define	SP_MAXDEGREE_PC 10

#define	SP_MAXNSTARTS 10000

#define	VNODES_UNSET -1

#define	SP_MAXNPULLS 4

Typedefs
typedef struct path_replacement	PR

Functions
static SCIP_Real	getSdProfit (const SDPROFIT sdprofit, const int nodes_index, int node, int nonsource)

static int	pathGetHead (const GRAPH g, const PR pr)

static void	deleteEdge (SCIP scip, int edge, GRAPH g, PR *pr)

static void	deletenodesDeg1 (SCIP scip, EXTPERMA extperma, GRAPH *g)

static void	ruleOutFromHead (SCIP scip, const GRAPH g, PR pr, SCIP_Bool needFullRuleOut)

static void	ruleOutFromTailSingle (SCIP scip, const GRAPH g, PR pr, SCIP_Bool isRuledOut)

static void	ruleOutFromTailCombs (SCIP scip, const GRAPH g, PR pr, SCIP_Bool isRuledOut)

static void	addPathNode (SCIP scip, int node, PR pr)

static void	addNonPathNode (SCIP scip, int node, PR pr)

static void	addPathHeadEdge (SCIP scip, const GRAPH g, PR *pr)

static void	addInitialPathNodes (SCIP scip, const GRAPH g, int startedge_tail, int startdege_head, PR *pr)

static void	pathneighborsCollect (SCIP scip, const GRAPH g, PR *pr)

static void	pathneighborsUpdateDistances (SCIP scip, const GRAPH g, PR *pr)

static void	pathExendPrepare (SCIP scip, const GRAPH g, int startedge, PR *pr)

static void	pathExend (SCIP scip, const GRAPH g, PR pr, SCIP_Bool isExendible, SCIP_Bool *isRedundant)

static SCIP_RETCODE	prInit (SCIP scip, const GRAPH g, EXTPERMA extperma, PR *pathreplace)

static void	prClean (PR *pr)

static void	prFree (SCIP scip, PR *pathreplace)

static SCIP_Bool	prIsPromising (const GRAPH *g)

static SCIP_RETCODE	processPath (SCIP scip, int startedge, PR pr, GRAPH g, int nelims)

static SCIP_RETCODE	pathreplaceExec (SCIP scip, PR pr, GRAPH g, int nelims)

SCIP_RETCODE	reduce_pathreplaceExt (SCIP scip, GRAPH g, EXTPERMA extperma, int nelims)

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

Macro Definition Documentation

◆ SP_MAXNDISTS

#define SP_MAXNDISTS 10000

Definition at line 34 of file reduce_path.c.

Referenced by prInit().

◆ SP_MAXLENGTH

#define SP_MAXLENGTH 11

Definition at line 35 of file reduce_path.c.

Referenced by pathExend(), and prInit().

◆ SP_MAXDEGREE

#define SP_MAXDEGREE 8

Definition at line 36 of file reduce_path.c.

Referenced by prInit().

◆ SP_MAXDEGREE_FAST

#define SP_MAXDEGREE_FAST 5

Definition at line 37 of file reduce_path.c.

Referenced by prInit().

◆ SP_MAXDEGREE_PC

#define SP_MAXDEGREE_PC 10

Definition at line 38 of file reduce_path.c.

Referenced by prInit().

◆ SP_MAXNSTARTS

#define SP_MAXNSTARTS 10000

Definition at line 39 of file reduce_path.c.

Referenced by pathneighborsCollect(), prClean(), and prInit().

◆ VNODES_UNSET

#define VNODES_UNSET -1

Definition at line 40 of file reduce_path.c.

Referenced by addNonPathNode(), addPathNode(), pathExend(), pathExendPrepare(), pathneighborsCollect(), pathneighborsUpdateDistances(), prClean(), prInit(), and ruleOutFromHead().

◆ SP_MAXNPULLS

#define SP_MAXNPULLS 4

Definition at line 41 of file reduce_path.c.

Referenced by pathneighborsUpdateDistances().

Typedef Documentation

◆ PR

typedef struct path_replacement PR

path replacement

Function Documentation

◆ getSdProfit()

static SCIP_Real getSdProfit	(	const SDPROFIT *	sdprofit,
		const int *	nodes_index,
		int	node,
		int	nonsource
	)

inlinestatic

gets profit for given node

Parameters

sdprofit	the SD profit
nodes_index	index array
node	node to get profit for
nonsource	node that should not be a source

Definition at line 77 of file reduce_path.c.

References FARAWAY, GE, LE, special_distance_implied_profit::nodes_bias, special_distance_implied_profit::nodes_bias2, special_distance_implied_profit::nodes_biassource, and special_distance_implied_profit::nodes_biassource2.

Referenced by pathneighborsUpdateDistances().

◆ pathGetHead()

static int pathGetHead	(	const GRAPH *	g,
		const PR *	pr
	)

inlinestatic

gets head of path

Parameters

g	graph data structure
pr	path replacement data structure

Definition at line 115 of file reduce_path.c.

References GRAPH::head, and StpVecGetSize.

Referenced by addPathHeadEdge(), pathExend(), pathneighborsCollect(), pathneighborsUpdateDistances(), ruleOutFromTailCombs(), and ruleOutFromTailSingle().

◆ deleteEdge()

static void deleteEdge	(	SCIP *	scip,
		int	edge,
		GRAPH *	g,
		PR *	pr
	)

inlinestatic

deletes given edge

Parameters

scip	SCIP
edge	edge to delete
g	graph data structure
pr	path replacement data structure

Definition at line 127 of file reduce_path.c.

References CONNECT, extension_data_permanent::distdata_default, path_replacement::extperma, extreduce_edgeRemove(), FALSE, flipedge, graph_edge_delFull(), extension_data_permanent::result, extension_data_permanent::solIsValid, and TRUE.

Referenced by processPath(), reduce_sdBiased(), reduce_sdBiasedNeighbor(), reduce_sdImpLongEdge(), and reduceWithEdgeFixingBounds().

◆ deletenodesDeg1()

static void deletenodesDeg1	(	SCIP *	scip,
		EXTPERMA *	extperma,
		GRAPH *	g
	)

static

removes nodes of degree one and unmarks

Parameters

scip	SCIP
extperma	extension data
g	graph data structure (in/out)

Definition at line 157 of file reduce_path.c.

References extension_data_permanent::distdata_default, extreduce_edgeRemove(), FALSE, GRAPH::grad, graph_get_nNodes(), GRAPH::head, Is_term, GRAPH::mark, nnodes, GRAPH::outbeg, SCIP_Bool, GRAPH::term, and TRUE.

Referenced by reduce_pathreplaceExt().

◆ ruleOutFromHead()

static void ruleOutFromHead	(	SCIP *	scip,
		const GRAPH *	g,
		PR *	pr,
		SCIP_Bool *	needFullRuleOut
	)

inlinestatic

tries to rule out neighbors of path head

Parameters

scip	SCIP
g	graph data structure
pr	path replacement data structure
needFullRuleOut	pointer to store whether full rule-out is needed

Definition at line 194 of file reduce_path.c.

References extension_data_permanent::distdata_default, EQ, path_replacement::extperma, extreduce_distDataGetSdDoubleEq(), extreduce_distDataGetSdDoubleForbiddenSingle(), FALSE, GT, LE, LT, NULL, SCIP_Bool, SCIP_Real, SCIPdebugMessage, StpVecGetSize, TRUE, and VNODES_UNSET.

Referenced by pathExend().

◆ ruleOutFromTailSingle()

static void ruleOutFromTailSingle	(	SCIP *	scip,
		const GRAPH *	g,
		PR *	pr,
		SCIP_Bool *	isRuledOut
	)

inlinestatic

tries to rule out neighbors of path tail

Parameters

scip	SCIP
g	graph data structure
pr	path replacement data structure
isRuledOut	ruled-out?

Definition at line 275 of file reduce_path.c.

References extension_data_permanent::distdata_default, EQ, path_replacement::extperma, extreduce_distDataGetSdDoubleEq(), extreduce_distDataGetSdDoubleForbiddenSingle(), GT, LE, LT, NULL, pathGetHead(), SCIP_Bool, SCIP_Real, SCIPdebugMessage, and TRUE.

Referenced by pathExend().

◆ ruleOutFromTailCombs()

static void ruleOutFromTailCombs	(	SCIP *	scip,
		const GRAPH *	g,
		PR *	pr,
		SCIP_Bool *	isRuledOut
	)

inlinestatic

tries to rule out neighbors of path tail

Parameters

scip	SCIP
g	graph data structure
pr	path replacement data structure
isRuledOut	ruled-out?

Definition at line 334 of file reduce_path.c.

References extension_data_permanent::distdata_default, EQ, path_replacement::extperma, extreduce_distDataGetSdDoubleEq(), extreduce_distDataGetSdDoubleForbiddenSingle(), GT, LE, LT, NULL, pathGetHead(), SCIP_Bool, SCIP_Real, SCIPdebugMessage, and TRUE.

Referenced by pathExend().

◆ addPathNode()

static void addPathNode	(	SCIP *	scip,
		int	node,
		PR *	pr
	)

inlinestatic

adds new path node

Parameters

scip	SCIP
node	node to add
pr	path replacement data structure

Definition at line 405 of file reduce_path.c.

References StpVecGetSize, StpVecPushBack, TRUE, and VNODES_UNSET.

Referenced by addInitialPathNodes().

◆ addNonPathNode()

static void addNonPathNode	(	SCIP *	scip,
		int	node,
		PR *	pr
	)

inlinestatic

adds new NON-path node

Parameters

scip	SCIP
node	node to add
pr	path replacement data structure

Definition at line 420 of file reduce_path.c.

References FALSE, StpVecGetSize, StpVecPushBack, and VNODES_UNSET.

Referenced by pathExendPrepare().

◆ addPathHeadEdge()

static void addPathHeadEdge	(	SCIP *	scip,
		const GRAPH *	g,
		PR *	pr
	)

inlinestatic

adds new path head edge to failed node

Parameters

scip	SCIP
g	graph
pr	path replacement data structure

Definition at line 436 of file reduce_path.c.

References dynamic_csr_storage::cost, GRAPH::cost, GRAPH::dcsr_storage, dynamic_csr_storage::edgeid, csr_range::end, EQ, dynamic_csr_storage::head, LE, pathGetHead(), GRAPH::prize, dynamic_csr_storage::range, SCIPdebugMessage, StpVecPushBack, and TRUE.

Referenced by pathExend().

◆ addInitialPathNodes()

static void addInitialPathNodes	(	SCIP *	scip,
		const GRAPH *	g,
		int	startedge_tail,
		int	startdege_head,
		PR *	pr
	)

inlinestatic

adds first two path nodes

Parameters

scip	SCIP
g	graph
startedge_tail	tail of start edge
startdege_head	head of start edge
pr	path replacement data structure

Definition at line 479 of file reduce_path.c.

References addPathNode(), dynamic_csr_storage::cost, GRAPH::dcsr_storage, csr_range::end, EQ, FARAWAY, dynamic_csr_storage::head, dynamic_csr_storage::range, SCIP_Real, and SCIPdebugMessage.

Referenced by pathExendPrepare().

◆ pathneighborsCollect()

static void pathneighborsCollect	(	SCIP *	scip,
		const GRAPH *	g,
		PR *	pr
	)

inlinestatic

collects neighbors

Parameters

scip	SCIP
g	graph data structure
pr	path replacement data structure

Definition at line 528 of file reduce_path.c.

References GRAPH::dcsr_storage, csr_range::end, FALSE, FARAWAY, dynamic_csr_storage::head, pathGetHead(), dynamic_csr_storage::range, SCIP_Real, SCIPdebugMessage, SP_MAXNSTARTS, StpVecClear, StpVecGetSize, StpVecPushBack, and VNODES_UNSET.

Referenced by pathExend().

◆ pathneighborsUpdateDistances()

static void pathneighborsUpdateDistances	(	SCIP *	scip,
		const GRAPH *	g,
		PR *	pr
	)

inlinestatic

updates distances from neighbors

Parameters

scip	SCIP
g	graph data structure
pr	path replacement data structure

Definition at line 580 of file reduce_path.c.

References dynamic_csr_storage::cost, GRAPH::dcsr_storage, csr_range::end, FALSE, getSdProfit(), dynamic_csr_storage::head, LT, pathGetHead(), dynamic_csr_storage::range, SCIP_Bool, SCIP_Real, SCIPdebugMessage, path_replacement::sdprofit, SP_MAXNPULLS, STP_Vectype, StpVecGetSize, StpVecPopBack, StpVecPushBack, TRUE, and VNODES_UNSET.

Referenced by pathExend().

◆ pathExendPrepare()

static void pathExendPrepare	(	SCIP *	scip,
		const GRAPH *	g,
		int	startedge,
		PR *	pr
	)

inlinestatic

preprocess for doing path extension later on

Parameters

scip	SCIP
g	graph data structure
startedge	first edge
pr	path replacement data structure

Definition at line 666 of file reduce_path.c.

References addInitialPathNodes(), addNonPathNode(), dynamic_csr_storage::cost, GRAPH::cost, GRAPH::dcsr_storage, csr_range::end, EQ, FALSE, GE, graph_pc_knotIsDummyTerm(), dynamic_csr_storage::head, GRAPH::head, LE, LT, GRAPH::prize, dynamic_csr_storage::range, SCIP_Bool, SCIP_Real, SCIPdebugMessage, StpVecGetSize, StpVecPushBack, GRAPH::tail, and VNODES_UNSET.

Referenced by processPath().

◆ pathExend()

static void pathExend	(	SCIP *	scip,
		const GRAPH *	g,
		PR *	pr,
		SCIP_Bool *	isExendible,
		SCIP_Bool *	isRedundant
	)

inlinestatic

tries to eliminate edges of path starting from edge

Parameters

scip	SCIP
g	graph data structure
pr	path replacement data structure
isExendible	extendible?
isRedundant	redundant?

Definition at line 791 of file reduce_path.c.

References addPathHeadEdge(), FALSE, GRAPH::grad, pathGetHead(), pathneighborsCollect(), pathneighborsUpdateDistances(), ruleOutFromHead(), ruleOutFromTailCombs(), ruleOutFromTailSingle(), SCIP_Bool, SP_MAXLENGTH, StpVecGetSize, TRUE, and VNODES_UNSET.

Referenced by processPath().

◆ prInit()

static SCIP_RETCODE prInit	(	SCIP *	scip,
		const GRAPH *	g,
		EXTPERMA *	extperma,
		PR **	pathreplace
	)

static

initializes

Parameters

scip	SCIP data structure
g	graph data structure
extperma	extension data or NULL
pathreplace	to initialize

Definition at line 869 of file reduce_path.c.

References path_replacement::extperma, extred_fast, graph_get_nNodes(), graph_getIsTermArray(), graph_pc_isPc(), extension_data_permanent::mode, nnodes, NULL, reduce_sdprofitInit(), SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, path_replacement::sdprofit, SP_MAXDEGREE, SP_MAXDEGREE_FAST, SP_MAXDEGREE_PC, SP_MAXLENGTH, SP_MAXNDISTS, SP_MAXNSTARTS, StpVecReserve, and VNODES_UNSET.

Referenced by reduce_pathreplace(), and reduce_pathreplaceExt().

◆ prClean()

static void prClean ( PR * pr )

static

cleans temporary data

Parameters

pr	to be cleaned

Definition at line 922 of file reduce_path.c.

References nnodes, SP_MAXNSTARTS, StpVecClear, StpVecGetSize, and VNODES_UNSET.

Referenced by processPath().

◆ prFree()

static void prFree	(	SCIP *	scip,
		PR **	pathreplace
	)

static

frees

Parameters

scip	SCIP data structure
pathreplace	to be freed

Definition at line 953 of file reduce_path.c.

References reduce_sdprofitFree(), SCIPfreeMemory, SCIPfreeMemoryArray, path_replacement::sdprofit, and StpVecFree.

Referenced by reduce_pathreplace(), and reduce_pathreplaceExt().

◆ prIsPromising()

static SCIP_Bool prIsPromising ( const GRAPH * g )

static

is execution of path replacement reduction method promising?

Parameters

g	graph structure

Definition at line 980 of file reduce_path.c.

References TRUE.

Referenced by reduce_pathreplace(), and reduce_pathreplaceExt().

◆ processPath()

static SCIP_RETCODE processPath	(	SCIP *	scip,
		int	startedge,
		PR *	pr,
		GRAPH *	g,
		int *	nelims
	)

inlinestatic

tries to eliminate edges of path starting from edge

Parameters

scip	SCIP data structure
startedge	edge to start from (head)
pr	path replacement data structure
g	graph data structure
nelims	pointer to number of reductions

Definition at line 991 of file reduce_path.c.

References deleteEdge(), FALSE, GRAPH::grad, GRAPH::head, pathExend(), pathExendPrepare(), prClean(), SCIP_Bool, SCIP_OKAY, SCIPdebugMessage, StpVecGetSize, GRAPH::tail, and TRUE.

Referenced by pathreplaceExec().

◆ pathreplaceExec()

static SCIP_RETCODE pathreplaceExec	(	SCIP *	scip,
		PR *	pr,
		GRAPH *	g,
		int *	nelims
	)

static

executes reduction method

Parameters

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

Definition at line 1038 of file reduce_path.c.

References extension_data_permanent::distdata_default, EAT_FREE, path_replacement::extperma, graph_get_nEdges(), graph_pc_edgeIsExtended(), NULL, GRAPH::oeat, processPath(), reduce_sdgraphEdgeIsInMst(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, special_distance_storage::sdgraph, and distance_data::sdistdata.

Referenced by reduce_pathreplace(), and reduce_pathreplaceExt().

◆ reduce_pathreplaceExt()

SCIP_RETCODE reduce_pathreplaceExt	(	SCIP *	scip,
		GRAPH *	g,
		EXTPERMA *	extperma,
		int *	nelims
	)

paths elimination while using special distances NOTE: SD-repair needs to be set-up!

Parameters

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

Definition at line 1080 of file reduce_path.c.

References GRAPH::dcsr_storage, deletenodesDeg1(), graph_free_dcsr(), graph_init_dcsr(), graph_valid(), NULL, pathreplaceExec(), prFree(), prInit(), prIsPromising(), SCIP_Bool, SCIP_CALL, and SCIP_OKAY.

Referenced by extreduce_deleteEdges().

◆ reduce_pathreplace()

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

paths elimination

Parameters

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

Definition at line 1119 of file reduce_path.c.

References graph_free_dcsr(), graph_init_dcsr(), graph_valid(), NULL, pathreplaceExec(), prFree(), prInit(), prIsPromising(), reduce_nodesDeg1(), SCIP_CALL, and SCIP_OKAY.

Referenced by redLoopInnerPc(), redLoopInnerStp(), testPathReplaceDeletesEdge(), and testPathReplaceDeletesEdge2().

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ SP_MAXNDISTS

◆ SP_MAXLENGTH

◆ SP_MAXDEGREE

◆ SP_MAXDEGREE_FAST

◆ SP_MAXDEGREE_PC

◆ SP_MAXNSTARTS

◆ VNODES_UNSET

◆ SP_MAXNPULLS

Typedef Documentation

◆ PR

Function Documentation

◆ getSdProfit()

◆ pathGetHead()

◆ deleteEdge()

◆ deletenodesDeg1()

◆ ruleOutFromHead()

◆ ruleOutFromTailSingle()

◆ ruleOutFromTailCombs()

◆ addPathNode()

◆ addNonPathNode()

◆ addPathHeadEdge()

◆ addInitialPathNodes()

◆ pathneighborsCollect()

◆ pathneighborsUpdateDistances()

◆ pathExendPrepare()

◆ pathExend()

◆ prInit()

◆ prClean()

◆ prFree()

◆ prIsPromising()

◆ processPath()

◆ pathreplaceExec()

◆ reduce_pathreplaceExt()

◆ reduce_pathreplace()