Detailed Description

Utility methods for dynamic programming solver for Steiner tree (sub-) problems.

Author: Daniel Rehfeldt

Implements two implementations for finding valid intersections of sub-trees during DP. One naive one, and one based on a search tree (DPS tree). Performance is slightly better for the latter one. NOTE: DPS tree design is mostly taken from "Separator-Based Pruned Dynamic Programming for Steiner Tree" by Iwata and Shigemura.

Definition in file dpterms_util.c.

#include "scip/scipdefplugins.h"
#include "dpterms.h"
#include "dptermsinterns.h"

Go to the source code of this file.

Data Structures
struct	dynamic_programming_search_tree_node

struct	dynamic_programming_search_tree

Macros
#define	CHILD_NONE -1

#define	CHILD_LEFT 0

#define	CHILD_RIGHT 1

Typedefs
typedef struct dynamic_programming_search_tree_node	DPSNODE

Functions
static SCIP_Bool	bitsetsizesAreValid (STP_Bitset termsmark, STP_Bitset rootsmark, const DPSTREE *dpstree)

static SCIP_Bool	treenodeIsInRange (int node_pos, const DPSTREE *dpstree)

static void	printNodeDebugInfo (int node_pos, const DPSTREE *dpstree)

static void	addLeaf (SCIP scip, STP_Bitset termsmark, STP_Bitset rootsmark, int64_t nsubsets, int leafpos, DPSTREE *dpstree)

static void	insertData (SCIP scip, STP_Bitset termsmark, STP_Bitset rootsmark, int64_t nsubsets, int node_pos, int split_pos, int subrootpos, DPSTREE *dpstree)

static void	streeCollectIntersects (SCIP scip, STP_Bitset termsmark, STP_Bitset rootsmark, int node_pos, DPSTREE dpstree)

SCIP_Bool	dpterms_intersectsEqualNaive (SCIP scip, STP_Bitset termsmark, STP_Bitset rootsmark, STP_Vectype(int) intersects, DPMISC dpmisc)

	STP_Vectype (int)

SCIP_RETCODE	dpterms_streeInsert (SCIP scip, STP_Bitset termsmark, STP_Bitset rootsmark, int64_t nsubsets, DPSTREE dpstree)

SCIP_RETCODE	dpterms_streeInit (SCIP scip, int nterms, int nnodes, DPSTREE *dpstree)

void	dpterms_streeFree (SCIP scip, DPSTREE *dpstree)

Macro Definition Documentation

◆ CHILD_NONE

#define CHILD_NONE -1

Definition at line 32 of file dpterms_util.c.

Referenced by addLeaf().

◆ CHILD_LEFT

#define CHILD_LEFT 0

Definition at line 33 of file dpterms_util.c.

Referenced by insertData(), printNodeDebugInfo(), and streeCollectIntersects().

◆ CHILD_RIGHT

#define CHILD_RIGHT 1

Definition at line 34 of file dpterms_util.c.

Referenced by insertData(), printNodeDebugInfo(), and streeCollectIntersects().

Typedef Documentation

◆ DPSNODE

typedef struct dynamic_programming_search_tree_node DPSNODE

sub tree

Function Documentation

◆ bitsetsizesAreValid()

static SCIP_Bool bitsetsizesAreValid	(	STP_Bitset	termsmark,
		STP_Bitset	rootsmark,
		const DPSTREE *	dpstree
	)

static

valid sizes? for debug checks

Parameters

termsmark	terminal mark
rootsmark	marks roots of extension trees
dpstree	to check for

Definition at line 70 of file dpterms_util.c.

References FALSE, stpbitset_getCapacity(), and TRUE.

Referenced by addLeaf(), dpterms_streeInsert(), insertData(), and streeCollectIntersects().

◆ treenodeIsInRange()

static SCIP_Bool treenodeIsInRange	(	int	node_pos,
		const DPSTREE *	dpstree
	)

static

valid node? for debug checks

Parameters

node_pos	position of node
dpstree	to check for

Definition at line 98 of file dpterms_util.c.

References FALSE, StpVecGetSize, and TRUE.

Referenced by insertData(), printNodeDebugInfo(), and streeCollectIntersects().

◆ printNodeDebugInfo()

static void printNodeDebugInfo	(	int	node_pos,
		const DPSTREE *	dpstree
	)

static

NOTE: only debug prints

Parameters

node_pos	position of node
dpstree	to check for

Definition at line 123 of file dpterms_util.c.

References CHILD_LEFT, CHILD_RIGHT, SCIPdebugMessage, stpbitset_print(), and treenodeIsInRange().

Referenced by insertData(), and streeCollectIntersects().

◆ addLeaf()

static void addLeaf	(	SCIP *	scip,
		STP_Bitset	termsmark,
		STP_Bitset	rootsmark,
		int64_t	nsubsets,
		int *	leafpos,
		DPSTREE *	dpstree
	)

static

adds leaf NOTE: takes ownership of termsmark and rootsmark

Parameters

scip	SCIP data structure
termsmark	terminal mark
rootsmark	marks roots of extension trees
nsubsets	number of subsets
leafpos	position of new leaf
dpstree	to insert to

Definition at line 147 of file dpterms_util.c.

References bitsetsizesAreValid(), CHILD_NONE, dynamic_programming_search_tree_node::children_id, dynamic_programming_search_tree_node::nsubsets, StpVecGetSize, and StpVecPushBack.

Referenced by dpterms_streeInsert(), and insertData().

◆ insertData()

static void insertData	(	SCIP *	scip,
		STP_Bitset	termsmark,
		STP_Bitset	rootsmark,
		int64_t	nsubsets,
		int	node_pos,
		int	split_pos,
		int *	subrootpos,
		DPSTREE *	dpstree
	)

static

inserts (recursively)

Parameters

scip	SCIP data structure
termsmark	terminal mark
rootsmark	marks roots of extension trees
nsubsets	number of subsets
node_pos	node position
split_pos	current split position
subrootpos	position of new sub-root
dpstree	to insert to

Definition at line 172 of file dpterms_util.c.

References addLeaf(), bitsetsizesAreValid(), CHILD_LEFT, CHILD_RIGHT, dynamic_programming_search_tree_node::children_id, nterms, printNodeDebugInfo(), dynamic_programming_search_tree_node::roots_union, SCIP_Bool, SCIPdebugMessage, STP_Bitset, STP_Vectype(), stpbitset_and(), stpbitset_bitIsTrue(), stpbitset_getPopcount(), stpbitset_newCopy(), stpbitset_or(), StpVecGetSize, StpVecPushBack, dynamic_programming_search_tree_node::terms_intersection, and treenodeIsInRange().

Referenced by dpterms_streeInsert(), and localVertexInsertion().

◆ streeCollectIntersects()

static void streeCollectIntersects	(	SCIP *	scip,
		STP_Bitset	termsmark,
		STP_Bitset	rootsmark,
		int	node_pos,
		DPSTREE *	dpstree
	)

static

gets indices of intersections

Parameters

scip	SCIP data structure
termsmark	terminal mark
rootsmark	marks roots of extension trees
node_pos	node position
dpstree	to insert to

Definition at line 278 of file dpterms_util.c.

References bitsetsizesAreValid(), CHILD_LEFT, CHILD_RIGHT, dynamic_programming_search_tree_node::children_id, dynamic_programming_search_tree_node::nsubsets, printNodeDebugInfo(), dynamic_programming_search_tree_node::roots_union, SCIPdebugMessage, dynamic_programming_search_tree_node::split_pos, STP_Bitset, STP_Vectype(), stpbitset_bitIsTrue(), stpbitset_haveIntersection(), StpVecPushBack, dynamic_programming_search_tree_node::terms_intersection, and treenodeIsInRange().

Referenced by dpterms_streeInsert().

◆ dpterms_intersectsEqualNaive()

SCIP_Bool dpterms_intersectsEqualNaive	(	SCIP *	scip,
		STP_Bitset	termsmark,
		STP_Bitset	rootsmark,
		STP_Vectype(int)	intersects,
		DPMISC *	dpmisc
	)

for debugging: checks whether given intersection is equal to naively computed one

Parameters

scip	SCIP data structure
termsmark	terminal mark
rootsmark	marks roots of extension trees
intersects	intersection indices
dpmisc	MISC DP data

Definition at line 340 of file dpterms_util.c.

References BMScopyMemoryArray, FALSE, SCIP_Bool, SCIP_CALL_ABORT, SCIPallocMemoryArray, SCIPdebugMessage, SCIPfreeMemoryArray, SCIPsortDownInt(), STP_Vectype(), StpVecFree, StpVecGetSize, and TRUE.

Referenced by dpterms_dpsubsolFree().

◆ STP_Vectype()

STP_Vectype ( int )

gets indices of intersections by using naive computation MISC DP data

gets indices of intersections to insert to

Definition at line 399 of file dpterms_util.c.

References FALSE, NULL, solution_trace::root, SCIP_Bool, STP_Bitset, stpbitset_bitIsTrue(), stpbitset_haveIntersection(), stpbitset_setsAreCompatible(), StpVecGetSize, StpVecPushBack, and TRUE.

Referenced by dpterms_intersectsEqualNaive(), dpterms_streeInsert(), insertData(), and streeCollectIntersects().

◆ dpterms_streeInsert()

SCIP_RETCODE dpterms_streeInsert	(	SCIP *	scip,
		STP_Bitset	termsmark,
		STP_Bitset	rootsmark,
		int64_t	nsubsets,
		DPSTREE *	dpstree
	)

inserts NOTE: dps-tree takes ownership of bitsets!

Parameters

scip	SCIP data structure
termsmark	terminal mark; will become OWNED
rootsmark	marks roots of extension trees; will become OWNED
nsubsets	number of subsets
dpstree	to insert to

Definition at line 449 of file dpterms_util.c.

References addLeaf(), bitsetsizesAreValid(), insertData(), NULL, SCIP_ERROR, SCIP_OKAY, SCIPdebugMessage, SCIPerrorMessage, dynamic_programming_search_tree_node::split_pos, STP_Bitset, STP_Vectype(), stpbitset_getPopcount(), stpbitset_print(), and streeCollectIntersects().

Referenced by subtreesAddNewFinalize().

◆ dpterms_streeInit()

SCIP_RETCODE dpterms_streeInit	(	SCIP *	scip,
		int	nterms,
		int	nnodes,
		DPSTREE **	dpstree
	)

initializes

Parameters

scip	SCIP data structure
nterms	number of terminals
nnodes	number of nodes
dpstree	initialize

Definition at line 533 of file dpterms_util.c.

References nnodes, nterms, NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocMemory.

Referenced by dpsolverInitData().

◆ dpterms_streeFree()

void dpterms_streeFree	(	SCIP *	scip,
		DPSTREE **	dpstree
	)

frees

Parameters

scip	SCIP data structure
dpstree	initialize

Definition at line 560 of file dpterms_util.c.

References SCIPfreeMemory, stpbitset_free(), StpVecFree, and StpVecGetSize.

Referenced by dpsolverFreeData().

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ CHILD_NONE

◆ CHILD_LEFT

◆ CHILD_RIGHT

Typedef Documentation

◆ DPSNODE

Function Documentation

◆ bitsetsizesAreValid()

◆ treenodeIsInRange()

◆ printNodeDebugInfo()

◆ addLeaf()

◆ insertData()

◆ streeCollectIntersects()

◆ dpterms_intersectsEqualNaive()

◆ STP_Vectype()

◆ dpterms_streeInsert()

◆ dpterms_streeInit()

◆ dpterms_streeFree()