solstp.c File Reference

Detailed Description

includes methods working on solutions (i.e. trees) to Steiner tree problems

Author

Daniel Rehfeldt

Methods for manipulating solutions (i.e. trees) to Steiner tree problems, such as pruning. Also includes methods for obtaining information about solutions.

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

Definition in file solstp.c.

#include "probdata_stp.h"
#include "portab.h"
#include "solstp.h"
#include "mst.h"
#include "shortestpath.h"

Go to the source code of this file.

Functions
static SCIP_RETCODE	reroot (SCIP *scip, const GRAPH *g, int *result, int newroot, SCIP_Bool *isInfeasible)
static void	pcsubtreeDelete (const GRAPH *g, int subtree_root, int dfspos[], int result[], STP_Bool connected[])
static void	pcsubtreeDelete_csr (const CSR *csr_orgcosts, int subtree_root, int *RESTRICT dfspos, int *RESTRICT result, STP_Bool *RESTRICT connected)
static SCIP_Real	pcsubtreePruneForProfit (const GRAPH *g, const SCIP_Real *cost, int subtree_root, int *RESTRICT dfspos, int *RESTRICT result, STP_Bool *RESTRICT connected, int *RESTRICT dfscount)
static SCIP_Real	pcsubtreePruneForProfit_csr (const CSR *csr_orgcosts, const SCIP_Real *prize, SCIP_Bool isPc, int subtree_root, int *RESTRICT dfspos, int *RESTRICT result, STP_Bool *RESTRICT connected, int *RESTRICT dfscount)
static void	pcsolGetTrivialEdges (const GRAPH *g, const STP_Bool *connected, int *RESTRICT result)
static SCIP_RETCODE	pcsolGetMstEdges (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int root, int *result)
static void	pcsolMarkGraphNodes (const STP_Bool *connected, const GRAPH *g)
static void	pcsolMarkGraphNodes_csr (const GRAPH *g, STP_Bool *RESTRICT connected)
static void	pcsolPrune (const GRAPH *g, int *result, STP_Bool *connected)
static void	stpsolPrune_csr (const GRAPH *g, const MST *mst, int *RESTRICT result, STP_Bool *RESTRICT connected)
static void	solGetMstEdges_csr (const GRAPH *g, const STP_Bool *connected, int root, MST *mst, int *RESTRICT result)
static SCIP_RETCODE	strongPruneSteinerTreePc (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int solroot, int *result, STP_Bool *connected)
static SCIP_RETCODE	strongPruneSteinerTreePc_csr (SCIP *scip, const GRAPH *g, const CSR *csr_orgcosts, int solroot, int *result, STP_Bool *connected)
static SCIP_RETCODE	pruneSteinerTreeStp (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int *result, STP_Bool *connected)
static SCIP_RETCODE	pruneSteinerTreeStp_csr (const GRAPH *g, MST *mst, int *RESTRICT result, STP_Bool *RESTRICT connected)
static SCIP_RETCODE	pruneSteinerTreePc (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int *result, STP_Bool *connected)
static SCIP_RETCODE	pruneSteinerTreePc_csr (SCIP *scip, const GRAPH *g, MST *mst, int *RESTRICT result, STP_Bool *RESTRICT connected)
static void	setNodeList (const GRAPH *g, STP_Bool *RESTRICT solnode, IDX *listnode)
int	solstp_pcGetSolRoot (SCIP *scip, const GRAPH *g, const STP_Bool *connected)
void	solstp_pcConnectDummies (const GRAPH *g, int solroot, int *RESTRICT result, STP_Bool *RESTRICT connected)
SCIP_RETCODE	solstp_addSolToProb (SCIP *scip, const GRAPH *g, const int *soledge, SCIP_HEUR *heur, SCIP_Bool *success)
SCIP_Bool	stpsol_pruningIsPossible (const GRAPH *g, const int *result, const STP_Bool *connected)
SCIP_RETCODE	solstp_prune (SCIP *scip, const GRAPH *g, int *result, STP_Bool *connected)
SCIP_RETCODE	solstp_pruneFromNodes (SCIP *scip, const GRAPH *g, int *result, STP_Bool *connected)
SCIP_RETCODE	solstp_pruneFromEdges (SCIP *scip, const GRAPH *g, int *result)
SCIP_RETCODE	solstp_pruneFromTmHeur (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int *RESTRICT result, STP_Bool *RESTRICT connected)
SCIP_RETCODE	solstp_pruneFromTmHeur_csr (SCIP *scip, const GRAPH *g, SPATHS *spaths, int *RESTRICT result)
SCIP_RETCODE	solstp_reroot (SCIP *scip, const GRAPH *g, int *result, int newroot)
SCIP_RETCODE	solstp_rerootInfeas (SCIP *scip, GRAPH *g, int *result, int newroot, SCIP_Bool *isInfeasible)
SCIP_Bool	solstp_isUnreduced (SCIP *scip, const GRAPH *graph, const int *result)
SCIP_Bool	solstp_containsNode (const GRAPH *g, const int *result, int node)
SCIP_Bool	solstp_isValid (SCIP *scip, const GRAPH *graph, const int *result)
void	solstp_print (const GRAPH *graph, const int *result)
SCIP_Real	solstp_getObjBounded (const GRAPH *g, const int *soledge, SCIP_Real offset, int nedges)
SCIP_Real	solstp_getObj (const GRAPH *g, const int *soledge, SCIP_Real offset)
SCIP_Real	solstp_pcGetObjCsr (const GRAPH *g, const CSR *csr, const int *soledge_csr, const STP_Bool *solnode)
SCIP_Real	solstp_getObjCsr (const GRAPH *g, const CSR *csr, const int *soledge_csr, const STP_Bool *solnode)
void	solstp_getStpFromSCIPsol (SCIP *scip, SCIP_SOL *scipsol, const GRAPH *g, int *soledges)
void	solstp_convertCsrToGraph (SCIP *scip, const GRAPH *g, const CSR *csr, const int *soledge_csr, STP_Bool *RESTRICT solnode, int *RESTRICT soledge_g)
void	solstp_getTrivialSol (const GRAPH *g, int *soledge)
int	solstp_getNedges (const GRAPH *g, const int *soledge)
int	solstp_getNedgesBounded (const GRAPH *g, const int *soledge, int nedges)
void	solstp_setVertexFromEdge (const GRAPH *g, const int *result, STP_Bool *solnode)
void	solstp_setVertexFromEdgeConn (const GRAPH *g, const int *soledge, int *solnode)
SCIP_RETCODE	solstp_getOrg (SCIP *scip, const GRAPH *transgraph, const GRAPH *orggraph, const int *transsoledge, int *orgsoledge)
SCIP_RETCODE	solstp_markPcancestors (SCIP *scip, IDX **pcancestors, const int *tails, const int *heads, int orgnnodes, STP_Bool *solnodemark, STP_Bool *soledgemark, int *solnodequeue, int *nsolnodes, int *nsoledges)

Function Documentation

reroot()

static SCIP_RETCODE reroot ( SCIP *  scip, const GRAPH *  g, int *  result, int  newroot, SCIP_Bool *  isInfeasible  )

static

changes solution according to given root

Parameters

scip	SCIP data structure
g	the graph
result	solution array (CONNECT/UNKNOWN)
newroot	the new root
isInfeasible	infeasible?

Definition at line 43 of file solstp.c.

References a, CONNECT, EAT_LAST, FALSE, flipedge, GRAPH::grad, graph_get_nNodes(), graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, nnodes, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, solstp_isValid(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by solstp_reroot(), and solstp_rerootInfeas().

pcsubtreeDelete()

static void pcsubtreeDelete ( const GRAPH *  g, int  subtree_root, int  dfspos[], int  result[], STP_Bool  connected[]  )

static

Deletes subtree from given node, marked by dfspos. NOTE: recursive method.

Parameters

g	graph structure
subtree_root	root of the subtree
dfspos	array to mark DFS positions of nodes
result	ST edges
connected	ST nodes

Definition at line 200 of file solstp.c.

References CONNECT, EAT_LAST, FALSE, graph_edge_printInfo(), graph_pc_knotIsDummyTerm(), GRAPH::head, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, SCIPdebugMessage, and UNKNOWN.

Referenced by pcsubtreePruneForProfit().

pcsubtreeDelete_csr()

static void pcsubtreeDelete_csr ( const CSR *  csr_orgcosts, int  subtree_root, int *RESTRICT  dfspos, int *RESTRICT  result, STP_Bool *RESTRICT  connected  )

static

Deletes subtree from given node, marked by dfspos. NOTE: recursive method.

Parameters

csr_orgcosts	CSR
subtree_root	root of the subtree
dfspos	array to mark DFS positions of nodes
result	ST edges
connected	ST nodes

Definition at line 247 of file solstp.c.

References CONNECT, FALSE, csr_storage::head, SCIPdebugMessage, csr_storage::start, and UNKNOWN.

Referenced by pcsubtreePruneForProfit_csr().

pcsubtreePruneForProfit()

static SCIP_Real pcsubtreePruneForProfit ( const GRAPH *  g, const SCIP_Real *  cost, int  subtree_root, int *RESTRICT  dfspos, int *RESTRICT  result, STP_Bool *RESTRICT  connected, int *RESTRICT  dfscount  )

static

Prunes subtree from given node such that it becomes most profitable and returns the profit. NOTE: recursive method.

Parameters

g	graph structure
cost	edge costs
subtree_root	root of the subtree
dfspos	array to mark DFS positions of nodes
result	ST edges
connected	ST nodes
dfscount	counter

Definition at line 289 of file solstp.c.

References CONNECT, graph_edge_printInfo(), graph_pc_isMw(), graph_pc_isPc(), graph_pc_knotIsDummyTerm(), GRAPH::head, LT, GRAPH::oeat, GRAPH::outbeg, pcsubtreeDelete(), GRAPH::prize, SCIP_Real, SCIPdebugMessage, and UNKNOWN.

Referenced by strongPruneSteinerTreePc().

pcsubtreePruneForProfit_csr()

static SCIP_Real pcsubtreePruneForProfit_csr ( const CSR *  csr_orgcosts, const SCIP_Real *  prize, SCIP_Bool  isPc, int  subtree_root, int *RESTRICT  dfspos, int *RESTRICT  result, STP_Bool *RESTRICT  connected, int *RESTRICT  dfscount  )

static

Prunes subtree from given node such that it becomes most profitable and returns the profit. NOTE: recursive method.

Parameters

csr_orgcosts	CSR
prize	the prize
isPc	is PC?
subtree_root	root of the subtree
dfspos	array to mark DFS positions of nodes
result	ST edges
connected	ST nodes
dfscount	counter

Definition at line 355 of file solstp.c.

References CONNECT, csr_storage::cost, csr_storage::head, LE, LT, nnodes, pcsubtreeDelete_csr(), SCIP_Real, SCIPdebugMessage, csr_storage::start, and UNKNOWN.

Referenced by strongPruneSteinerTreePc_csr().

pcsolGetTrivialEdges()

static void pcsolGetTrivialEdges ( const GRAPH *  g, const STP_Bool *  connected, int *RESTRICT  result  )

inlinestatic

computes trivial solution and sets result edges

Parameters

g	graph structure
connected	ST nodes
result	MST solution, which does not include artificial terminals

Definition at line 420 of file solstp.c.

References a, CONNECT, GRAPH::edges, graph_pc_knotIsDummyTerm(), GRAPH::head, GRAPH::oeat, GRAPH::outbeg, GRAPH::source, and UNKNOWN.

Referenced by pruneSteinerTreePc(), and solstp_getTrivialSol().

pcsolGetMstEdges()

static SCIP_RETCODE pcsolGetMstEdges ( SCIP *  scip, const GRAPH *  g, const SCIP_Real *  cost, int  root, int *  result  )

inlinestatic

computes MST on marked graph and sets result edges

Parameters

scip	SCIP data structure
g	graph structure
cost	edge costs
root	root of solution
result	MST solution, which does not include artificial terminals

Definition at line 449 of file solstp.c.

References CONNECT, shortest_path::edge, graph_get_nNodes(), graph_path_exec(), GRAPH::head, GRAPH::mark, MST_MODE, nnodes, GRAPH::path_state, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, and UNKNOWN.

Referenced by pruneSteinerTreePc().

pcsolMarkGraphNodes()

static void pcsolMarkGraphNodes ( const STP_Bool *  connected, const GRAPH *  g  )

inlinestatic

mark nodes of the solution in the graph

Parameters

connected	ST nodes
g	graph structure

Definition at line 484 of file solstp.c.

References GRAPH::extended, FALSE, graph_get_nNodes(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsFixedTerm(), Is_term, GRAPH::mark, nnodes, SCIP_Bool, GRAPH::source, GRAPH::term, and TRUE.

Referenced by pruneSteinerTreePc().

pcsolMarkGraphNodes_csr()

static void pcsolMarkGraphNodes_csr ( const GRAPH *  g, STP_Bool *RESTRICT  connected  )

inlinestatic

mark nodes of the solution in the graph

Parameters

g	graph structure
connected	ST nodes

Definition at line 526 of file solstp.c.

References GRAPH::extended, FALSE, GRAPH::grad, graph_get_nNodes(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsFixedTerm(), Is_term, nnodes, SCIP_Bool, GRAPH::source, and GRAPH::term.

Referenced by pruneSteinerTreePc_csr().

pcsolPrune()

static void pcsolPrune ( const GRAPH *  g, int *  result, STP_Bool *  connected  )

inlinestatic

prune a Steiner tree in such a way that all leaves are terminals

Parameters

g	graph structure
result	MST solution, which does not include artificial terminals
connected	ST nodes

Definition at line 572 of file solstp.c.

References CONNECT, EAT_LAST, FALSE, graph_edge_printInfo(), graph_get_nNodes(), GRAPH::ieat, GRAPH::inpbeg, Is_pseudoTerm, Is_term, GRAPH::mark, nnodes, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_state, SCIPdebugMessage, GRAPH::source, GRAPH::term, and UNKNOWN.

Referenced by pruneSteinerTreePc().

stpsolPrune_csr()

static void stpsolPrune_csr ( const GRAPH *  g, const MST *  mst, int *RESTRICT  result, STP_Bool *RESTRICT  connected  )

static

prunes the Steiner tree in such a way that all leaves are terminals

Parameters

g	graph structure
mst	the MST
result	ST edges (need to be set to UNKNOWN)
connected	ST nodes

Definition at line 648 of file solstp.c.

References CONNECT, minimum_spanning_tree::csr, FALSE, graph_get_nNodes(), Is_term, nnodes, minimum_spanning_tree::nodes_predEdge, SCIPdebugMessage, csr_storage::start, GRAPH::term, and UNKNOWN.

Referenced by pruneSteinerTreeStp_csr().

solGetMstEdges_csr()

static void solGetMstEdges_csr ( const GRAPH *  g, const STP_Bool *  connected, int  root, MST *  mst, int *RESTRICT  result  )

inlinestatic

computes MST on marked graph and sets result edges

Parameters

g	graph structure
connected	ST nodes
root	root of solution
mst	the MST
result	MST solution, which does not include artificial terminals

Definition at line 702 of file solstp.c.

References CONNECT, minimum_spanning_tree::csr, graph_get_nNodes(), csr_storage::head, mst_computeOnMarked(), nnodes, minimum_spanning_tree::nodes_predEdge, and UNKNOWN.

Referenced by pruneSteinerTreePc_csr(), and pruneSteinerTreeStp_csr().

strongPruneSteinerTreePc()

static SCIP_RETCODE strongPruneSteinerTreePc ( SCIP *  scip, const GRAPH *  g, const SCIP_Real *  cost, int  solroot, int *  result, STP_Bool *  connected  )

static

Finds optimal prize-collecting Steiner tree on given tree.

Parameters

scip	SCIP data structure
g	graph structure
cost	edge costs
solroot	root of the solution
result	ST edges
connected	ST nodes

Definition at line 730 of file solstp.c.

References BMSclearMemoryArray, EQ, GRAPH::extended, graph_get_nNodes(), graph_pc_costsEqualOrgCosts(), graph_pc_isMw(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), Is_anyTerm, LT, nnodes, pcsubtreePruneForProfit(), GRAPH::prize, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, solstp_getNedges(), and GRAPH::term.

Referenced by pruneSteinerTreePc().

strongPruneSteinerTreePc_csr()

static SCIP_RETCODE strongPruneSteinerTreePc_csr ( SCIP *  scip, const GRAPH *  g, const CSR *  csr_orgcosts, int  solroot, int *  result, STP_Bool *  connected  )

static

Finds optimal prize-collecting Steiner tree on given tree.

Parameters

scip	SCIP data structure
g	graph structure
csr_orgcosts	CSR
solroot	root of the solution
result	ST edges
connected	ST nodes

Definition at line 787 of file solstp.c.

References BMSclearMemoryArray, GRAPH::extended, graph_csr_getNedges(), graph_get_nNodes(), graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_knotIsDummyTerm(), LT, nnodes, csr_storage::nnodes, pcsubtreePruneForProfit_csr(), GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, and solstp_getNedgesBounded().

Referenced by pruneSteinerTreePc_csr().

pruneSteinerTreeStp()

static SCIP_RETCODE pruneSteinerTreeStp ( SCIP *  scip, const GRAPH *  g, const SCIP_Real *  cost, int *  result, STP_Bool *  connected  )

static

prune a Steiner tree in such a way that all leaves are terminals

Parameters

scip	SCIP data structure
g	graph structure
cost	edge costs
result	ST edges, which need to be set to UNKNOWN
connected	ST nodes

Definition at line 837 of file solstp.c.

References EAT_LAST, shortest_path::edge, GRAPH::edges, FALSE, graph_get_nNodes(), graph_path_exec(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, GRAPH::mark, MST_MODE, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebug, SCIPfreeBufferArray, GRAPH::source, GRAPH::term, GRAPH::terms, and UNKNOWN.

Referenced by solstp_prune(), and solstp_pruneFromTmHeur().

pruneSteinerTreeStp_csr()

static SCIP_RETCODE pruneSteinerTreeStp_csr ( const GRAPH *  g, MST *  mst, int *RESTRICT  result, STP_Bool *RESTRICT  connected  )

static

Prunes the Steiner tree in such a way that all leaves are terminals:

1. Builds MST
2. Removes non-terminal leaves repeatedly

Parameters

g	graph structure
mst	the MST
result	ST edges (need to be set to UNKNOWN)
connected	ST nodes

Definition at line 940 of file solstp.c.

References minimum_spanning_tree::csr, graph_csr_getNedges(), SCIP_OKAY, solGetMstEdges_csr(), GRAPH::source, stpsolPrune_csr(), and UNKNOWN.

Referenced by solstp_pruneFromTmHeur_csr().

pruneSteinerTreePc()

static SCIP_RETCODE pruneSteinerTreePc ( SCIP *  scip, const GRAPH *  g, const SCIP_Real *  cost, int *  result, STP_Bool *  connected  )

static

Parameters

scip	SCIP data structure
g	graph structure
cost	edge costs
result	ST edges (need to be set to UNKNOWN)
connected	ST nodes

Definition at line 970 of file solstp.c.

References BMScopyMemoryArray, CONNECT, GRAPH::extended, graph_get_nEdges(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), GRAPH::knots, LE, GRAPH::mark, GRAPH::path_state, pcsolGetMstEdges(), pcsolGetTrivialEdges(), pcsolMarkGraphNodes(), pcsolPrune(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, solstp_getObjBounded(), solstp_isValid(), solstp_pcConnectDummies(), solstp_pcGetSolRoot(), GRAPH::source, stpsol_pruningIsPossible(), strongPruneSteinerTreePc(), and UNKNOWN.

Referenced by solstp_prune(), and solstp_pruneFromTmHeur().

pruneSteinerTreePc_csr()

static SCIP_RETCODE pruneSteinerTreePc_csr ( SCIP *  scip, const GRAPH *  g, MST *  mst, int *RESTRICT  result, STP_Bool *RESTRICT  connected  )

static

Parameters

scip	SCIP data structure
g	graph structure
mst	the MST
result	ST edges (need to be set to UNKNOWN)
connected	ST nodes

Definition at line 1055 of file solstp.c.

References minimum_spanning_tree::csr, GRAPH::extended, graph_csr_getNedges(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), pcsolMarkGraphNodes_csr(), SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIPdebugMessage, solGetMstEdges_csr(), solstp_pcGetSolRoot(), GRAPH::source, strongPruneSteinerTreePc_csr(), and UNKNOWN.

Referenced by solstp_pruneFromTmHeur_csr().

setNodeList()

static void setNodeList ( const GRAPH *  g, STP_Bool *RESTRICT  solnode, IDX *  listnode  )

inlinestatic

mark endpoints of edges in given list

Parameters

g	graph data structure
solnode	solution nodes array (TRUE/FALSE)
listnode	edge list

Definition at line 1109 of file solstp.c.

References GRAPH::head, Int_List_Node::index, NULL, Int_List_Node::parent, GRAPH::tail, and TRUE.

Referenced by solstp_getOrg().

solstp_pcGetSolRoot()

int solstp_pcGetSolRoot	(	SCIP *	scip,
		const GRAPH *	g,
		const STP_Bool *	connected
	)

Gets root of solution for unrooted PC/MW. Returns -1 if the solution is empty.

Parameters

scip	SCIP data structure
g	graph structure
connected	ST nodes

Definition at line 1140 of file solstp.c.

References a, graph_get_nNodes(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), GRAPH::head, Is_pseudoTerm, Is_term, nnodes, GRAPH::oeat, GRAPH::outbeg, SCIPprobdataGetNNodes(), SCIPprobdataGetNTerms(), SCIPprobdataGetPctermsorder(), GRAPH::source, GRAPH::term, and GRAPH::terms.

Referenced by pruneSteinerTreePc(), pruneSteinerTreePc_csr(), and solstp_convertCsrToGraph().

solstp_pcConnectDummies()

void solstp_pcConnectDummies	(	const GRAPH *	g,
		int	solroot,
		int *RESTRICT	result,
		STP_Bool *RESTRICT	connected
	)

connects dummy terminals to given (pre-) PC solution

Parameters

g	graph structure
solroot	root of solution
result	MST solution, which does not include artificial terminals
connected	ST nodes

Definition at line 1200 of file solstp.c.

References CONNECT, EAT_LAST, GRAPH::grad, graph_get_nNodes(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsFixedTerm(), GRAPH::ieat, GRAPH::inpbeg, Is_term, nnodes, SCIP_Bool, GRAPH::source, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by pruneSteinerTreePc(), and solstp_convertCsrToGraph().

solstp_addSolToProb()

SCIP_RETCODE solstp_addSolToProb	(	SCIP *	scip,
		const GRAPH *	g,
		const int *	soledge,
		SCIP_HEUR *	heur,
		SCIP_Bool *	success
	)

add new solution to SCIP

Parameters

scip	SCIP data structure
g	graph structure
soledge	solution
heur	heuristic data or NULL
success	denotes whether the new solution has been successfully added

Definition at line 1279 of file solstp.c.

References CONNECT, graph_get_nEdges(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPprobdataAddNewSol(), and solstp_isValid().

Referenced by createInitialCuts(), SCIP_DECL_HEUREXEC(), SCIP_DECL_RELAXEXEC(), SCIPStpHeurTMRunLP(), solveWithDpBorder(), and solveWithDpTerms().

stpsol_pruningIsPossible()

SCIP_Bool stpsol_pruningIsPossible	(	const GRAPH *	g,
		const int *	result,
		const STP_Bool *	connected
	)

(simple) pruning of given solution possible?

Parameters

g	graph structure
result	ST edges
connected	ST nodes

Definition at line 1307 of file solstp.c.

References CONNECT, GRAPH::cost, GRAPH::cost_org_pc, EAT_LAST, EQ, FALSE, GE, graph_get_nNodes(), graph_pc_isPc(), graph_pc_knotIsNonLeafTerm(), GRAPH::ieat, GRAPH::inpbeg, Is_pseudoTerm, Is_term, nnodes, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, GRAPH::term, and TRUE.

Referenced by pcmwUpdateBestSol_csrInSync(), and pruneSteinerTreePc().

solstp_prune()

SCIP_RETCODE solstp_prune	(	SCIP *	scip,
		const GRAPH *	g,
		int *	result,
		STP_Bool *	connected
	)

Prune solution given by included nodes. NOTE: For PC/RPC this method will get the original edge costs before pruning!

Parameters

scip	SCIP data structure
g	graph structure
result	ST edges (out)
connected	ST nodes (in/out)

Definition at line 1366 of file solstp.c.

References GRAPH::cost, GRAPH::extended, graph_get_nEdges(), graph_pc_getOrgCosts(), graph_pc_isPc(), graph_pc_isPcMw(), NULL, pruneSteinerTreePc(), pruneSteinerTreeStp(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, solstp_isValid(), STP_DCSTP, GRAPH::stp_type, and UNKNOWN.

Referenced by localExtendPc(), localInsertion2pc(), localKeyPathExchangeMw(), localKeyPathExchangePc(), localKeyPathExchangePc2(), localKeyVertex(), localKeyVertexPc(), localKeyVertexPc2(), localVertexInsertion(), redcostGraphSolRetransform(), SCIPStpHeurLocalExtendPcMw(), SCIPStpHeurLocalExtendPcMwOut(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), solPrune(), solstp_getOrg(), solstp_pruneFromNodes(), testPrunedSolIsImprovedPc1(), and testPrunedSolIsImprovedPc2().

solstp_pruneFromNodes()

SCIP_RETCODE solstp_pruneFromNodes	(	SCIP *	scip,
		const GRAPH *	g,
		int *	result,
		STP_Bool *	connected
	)

prune solution given by included nodes

Parameters

scip	SCIP data structure
g	graph structure
result	ST edges
connected	ST nodes

Definition at line 1415 of file solstp.c.

References SCIP_CALL, SCIP_OKAY, solstp_prune(), STP_DHCSTP, and GRAPH::stp_type.

Referenced by dpborder_solve(), dpsolverGetSolution(), findSolPcMw2Term(), findSolRPcMw(), and solstp_pruneFromEdges().

solstp_pruneFromEdges()

SCIP_RETCODE solstp_pruneFromEdges	(	SCIP *	scip,
		const GRAPH *	g,
		int *	result
	)

prune solution given by included edges

Parameters

scip	SCIP data structure
g	graph structure
result	ST edges

Definition at line 1432 of file solstp.c.

References CONNECT, FALSE, graph_get_nEdges(), graph_get_nNodes(), GRAPH::head, nnodes, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, solstp_isValid(), solstp_print(), solstp_pruneFromNodes(), GRAPH::tail, and TRUE.

Referenced by localKeyVertexHeuristics(), and SCIPStpHeurTMRunLP().

solstp_pruneFromTmHeur()

SCIP_RETCODE solstp_pruneFromTmHeur	(	SCIP *	scip,
		const GRAPH *	g,
		const SCIP_Real *	cost,
		int *RESTRICT	result,
		STP_Bool *RESTRICT	connected
	)

Prunes solution with respect to the provided edges costs. NOTE: method exists purely for optimization, so that unbiased costs for PC do not have to computed again!

Parameters

scip	SCIP data structure
g	graph structure
cost	edge costs (original edge costs for PC!)
result	ST edges
connected	ST nodes

Definition at line 1474 of file solstp.c.

References GRAPH::cost, graph_get_nEdges(), graph_pc_costsEqualOrgCosts(), graph_pc_isPc(), graph_pc_isPcMw(), pruneSteinerTreePc(), pruneSteinerTreeStp(), SCIP_CALL, SCIP_OKAY, STP_DHCSTP, GRAPH::stp_type, and UNKNOWN.

Referenced by computeSteinerTree(), computeSteinerTreeDijk(), computeSteinerTreeDijkBMw(), computeSteinerTreeDijkPcMw(), computeSteinerTreeDijkPcMwFull(), and computeSteinerTreeVnoi().

solstp_pruneFromTmHeur_csr()

SCIP_RETCODE solstp_pruneFromTmHeur_csr	(	SCIP *	scip,
		const GRAPH *	g,
		SPATHS *	spaths,
		int *RESTRICT	result
	)

Prunes solution with respect to the provided edges costs. CSR version!

Parameters

scip	SCIP data structure
g	graph structure
spaths	shortest paths; NOTE: distances and preds not valid afterwards! hacky, but improves cache-efficiency
result	ST edges

Definition at line 1515 of file solstp.c.

References GRAPH::cost, minimum_spanning_tree::csr, stortest_paths::csr, stortest_paths::csr_orgcosts, stortest_paths::dheap, graph_csr_costsAreInSync(), graph_pc_isPc(), graph_pc_isPcMw(), nnodes, csr_storage::nnodes, stortest_paths::nodes_dist, stortest_paths::nodes_isConnected, stortest_paths::nodes_pred, pruneSteinerTreePc_csr(), pruneSteinerTreeStp_csr(), SCIP_CALL, SCIP_OKAY, csr_storage::start, STP_DHCSTP, GRAPH::stp_type, and UNKNOWN.

Referenced by computeSteinerTreeCsr(), computeSteinerTreeDijkPcMw(), computeSteinerTreeDijkPcMwFull(), and computeSteinerTreeKeyNodesCsr().

solstp_reroot()

SCIP_RETCODE solstp_reroot	(	SCIP *	scip,
		const GRAPH *	g,
		int *	result,
		int	newroot
	)

changes solution according to given root

Parameters

scip	SCIP data structure
g	the graph
result	solution array (CONNECT/UNKNOWN)
newroot	the new root

Definition at line 1559 of file solstp.c.

References reroot(), SCIP_Bool, SCIP_CALL, and SCIP_OKAY.

Referenced by computeDualSolutionGuided(), redcostGraphSolRetransform(), and reduce_daPcMw().

solstp_rerootInfeas()

SCIP_RETCODE solstp_rerootInfeas	(	SCIP *	scip,
		GRAPH *	g,
		int *	result,
		int	newroot,
		SCIP_Bool *	isInfeasible
	)

changes solution according to given root; also checks for infeasibility

Parameters

scip	SCIP data structure
g	the graph
result	solution array (CONNECT/UNKNOWN)
newroot	the new root
isInfeasible	infeasible?

Definition at line 1579 of file solstp.c.

References reroot(), SCIP_CALL, and SCIP_OKAY.

Referenced by reduce_da(), and runDualAscent().

solstp_isUnreduced()

SCIP_Bool solstp_isUnreduced	(	SCIP *	scip,
		const GRAPH *	graph,
		const int *	result
	)

checks whether edge(s) of given primal solution have been deleted

Parameters

scip	SCIP data structure
graph	graph data structure
result	solution array, indicating whether an edge is in the solution

Definition at line 1596 of file solstp.c.

References CONNECT, GRAPH::cost, EAT_FREE, FALSE, FARAWAY, GE, graph_get_nEdges(), graph_typeIsDirected(), GRAPH::oeat, and TRUE.

Referenced by computeSteinerTreeRedCosts(), computeSteinerTreeRedCostsDirected(), extreduce_deleteEdges(), reduce_da(), reduce_dapaths(), reduce_daPcMw(), and reducePcMwTryBest().

solstp_containsNode()

SCIP_Bool solstp_containsNode	(	const GRAPH *	g,
		const int *	result,
		int	node
	)

is the node contained in the solution?

Parameters

g	graph data structure
result	solution array, indicating whether an edge is in the solution
node	node to check for

Definition at line 1628 of file solstp.c.

References CONNECT, EAT_LAST, FALSE, flipedge, GRAPH::oeat, GRAPH::outbeg, and TRUE.

solstp_isValid()

SCIP_Bool solstp_isValid	(	SCIP *	scip,
		const GRAPH *	graph,
		const int *	result
	)

verifies whether a given primal solution is feasible

Parameters

scip	SCIP data structure
graph	graph data structure
result	solution array, indicating whether an edge is in the solution

Definition at line 1650 of file solstp.c.

References CONNECT, EAT_LAST, GRAPH::edges, GRAPH::extended, FALSE, flipedge, graph_get_nNodes(), graph_knot_printInfo(), graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_nFixedTerms(), graph_pc_nProperPotentialTerms(), graph_pc_termIsNonLeafTerm(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_pseudoTerm, Is_term, GRAPH::maxdeg, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL_ABORT, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, solstp_print(), GRAPH::source, STP_DCSTP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by addRedsol(), computeDualSolutionGuided(), computePertubedSol(), computeReducedProbSolution(), computeReducedProbSolutionBiased(), computeSteinerTreeRedCosts(), computeSteinerTreeRedCostsDirected(), computeSteinerTreeRedCostsPcMw(), dpborder_solve(), dpterms_solve(), enumExec(), extreduce_deleteEdges(), extreduce_pseudoDeleteNodes(), keyNodesSetTerms(), localExtendPc(), localInsertion(), localInsertion2(), localKeyPathExchange(), localKeyPathExchangeMw(), localKeyPathExchangePc(), localKeyPathExchangePc2(), localKeyVertex(), localKeyVertexPc(), localKeyVertexPc2(), localRun(), localVertexInsertion(), markSolTreeNodes(), pruneSteinerTreePc(), pseudodeleteInit(), redcostGraphComputeSteinerTree(), redcostGraphComputeSteinerTreeDegCons(), redcostGraphComputeSteinerTreeDirected(), redcostGraphSolRetransform(), reduce_daPcMw(), reduce_daSlackPrune(), reduce_sollocalUpdateNodesol(), reduceLurk(), reducePcMw(), reducePcMwTryBest(), reduceWithEdgeFixingBounds(), reroot(), SCIP_DECL_HEUREXEC(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalExtendPcMw(), SCIPStpHeurLurkPruneRun(), SCIPStpHeurPruneRun(), SCIPStpHeurPruneUpdateSols(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), SCIPStpHeurSlackPruneRun(), selectBranchingVertexBySol(), sepafullAddSolForCand(), sepafullReduceFromSols(), solPrune(), solstp_addSolToProb(), solstp_getOrg(), solstp_prune(), solstp_pruneFromEdges(), tbottleneckInit(), updateBestSol(), and updateSolution().

solstp_print()

void solstp_print	(	const GRAPH *	graph,
		const int *	result
	)

prints given solution

Parameters

graph	graph data structure
result	solution array, indicating whether an edge is in the solution

Definition at line 1808 of file solstp.c.

References CONNECT, graph_edge_printInfo(), graph_get_nEdges(), and UNKNOWN.

Referenced by solstp_isValid(), and solstp_pruneFromEdges().

solstp_getObjBounded()

SCIP_Real solstp_getObjBounded	(	const GRAPH *	g,
		const int *	soledge,
		SCIP_Real	offset,
		int	nedges
	)

compute solution value for given edge-solution array (CONNECT/UNKNOWN) and offset

Parameters

g	the graph
soledge	solution
offset	offset
nedges	number of edges

Definition at line 1833 of file solstp.c.

References CONNECT, GRAPH::cost, GRAPH::edges, GRAPH::extended, graph_pc_isPcMw(), SCIP_Real, and UNKNOWN.

Referenced by computeSteinerTree(), getSolObj(), initializeIncumbent(), localExtendPc(), localInsertion(), localInsertion2(), localInsertion2pc(), localKeyPathExchangeMw(), localKeyPathExchangePc2(), localKeyVertex(), localKeyVertexHeuristics(), localKeyVertexPc(), localKeyVertexPc2(), localRun(), localVertexInsertion(), lurkpruneInit(), pcmwUpdateBestSol(), pcmwUpdateBestSol_csrInSync(), pruneSteinerTreePc(), redcostGraphComputeSteinerTree(), runTmPcMW_mode(), SCIP_DECL_HEUREXEC(), SCIPStpHeurLocalExtendPcMw(), SCIPStpHeurLocalExtendPcMwOut(), SCIPStpHeurPruneRun(), SCIPStpHeurPruneUpdateSols(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), SCIPStpHeurSlackPruneRun(), solAddTry(), solPrune(), solstp_getObj(), testPrunedSolIsImprovedPc1(), testPrunedSolIsImprovedPc2(), testTmGivesExpectedTreePcFull1(), testTmGivesExpectedTreePcFull2(), testTmGivesExpectedTreePcFull3(), and updateBestSol().

solstp_getObj()

SCIP_Real solstp_getObj	(	const GRAPH *	g,
		const int *	soledge,
		SCIP_Real	offset
	)

compute solution value for given edge-solution array (CONNECT/UNKNOWN) and offset

Parameters

g	the graph
soledge	solution
offset	offset

Definition at line 1859 of file solstp.c.

References GRAPH::edges, and solstp_getObjBounded().

Referenced by computeReducedProbSolution(), computeSteinerTreeRedCostsDirected(), dpborder_solve(), enumExec(), lurkpruneFinalize(), lurkpruneInit(), redcostGraphComputeSteinerTreeDegCons(), redcostGraphComputeSteinerTreeDirected(), redcostGraphSolRetransform(), reduce_dapaths(), reduce_sollocalUpdateNodesol(), SCIP_DECL_HEUREXEC(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurSlackPruneRun(), SCIPStpHeurTMRun(), solveWithDpBorder(), solveWithDpTerms(), substpsolver_getObjFromGraph(), termcompComputeSubgraphSol(), and updateSolution().

solstp_pcGetObjCsr()

SCIP_Real solstp_pcGetObjCsr	(	const GRAPH *	g,
		const CSR *	csr,
		const int *	soledge_csr,
		const STP_Bool *	solnode
	)

compute solution value for given edge-solution array

Parameters

g	the graph
csr	the csr
soledge_csr	solution (CONNECT/UNKNOWN)
solnode	solution vertices (TRUE/FALSE)

Definition at line 1872 of file solstp.c.

References CONNECT, csr_storage::cost, GRAPH::extended, GRAPH::grad, graph_csr_getNedges(), graph_get_nNodes(), graph_pc_isPc(), graph_pc_isPcMw(), Is_nonleafTerm, Is_pseudoTerm, nnodes, csr_storage::nnodes, GRAPH::prize, SCIP_Bool, SCIP_Real, GRAPH::term, and UNKNOWN.

Referenced by pcmwUpdateBestSol(), and pcmwUpdateBestSol_csrInSync().

solstp_getObjCsr()

SCIP_Real solstp_getObjCsr	(	const GRAPH *	g,
		const CSR *	csr,
		const int *	soledge_csr,
		const STP_Bool *	solnode
	)

compute solution value for given edge-solution array

Parameters

g	the graph
csr	the csr
soledge_csr	solution (CONNECT/UNKNOWN)
solnode	solution vertices (TRUE/FALSE)

Definition at line 1921 of file solstp.c.

References CONNECT, csr_storage::cost, graph_csr_getNedges(), graph_get_nNodes(), graph_pc_isPcMw(), csr_storage::nnodes, SCIP_Real, and UNKNOWN.

Referenced by updateBestSol().

solstp_getStpFromSCIPsol()

void solstp_getStpFromSCIPsol	(	SCIP *	scip,
		SCIP_SOL *	scipsol,
		const GRAPH *	g,
		int *	soledges
	)

gets STP solution from SCIP solution

Parameters

scip	SCIP data structure
scipsol	SCIP solution data structure
g	the graph
soledges	solution (CONNECT/UNKNOWN)

Definition at line 1949 of file solstp.c.

References CONNECT, EQ, graph_get_nEdges(), SCIP_Real, SCIPprobdataGetXval(), and UNKNOWN.

Referenced by runDualAscent().

solstp_convertCsrToGraph()

void solstp_convertCsrToGraph	(	SCIP *	scip,
		const GRAPH *	g,
		const CSR *	csr,
		const int *	soledge_csr,
		STP_Bool *RESTRICT	solnode,
		int *RESTRICT	soledge_g
	)

converts solution from CSR to graph based

Parameters

scip	SCIP data structure
g	the graph
csr	the CSR
soledge_csr	CSR solution (CONNECT/UNKNOWN)
solnode	solution vertices (TRUE/FALSE) in/out!
soledge_g	graph solution (CONNECT/UNKNOWN) out

Definition at line 1976 of file solstp.c.

References CONNECT, csr_storage::edge_id, graph_csr_getNedges(), graph_get_nEdges(), graph_pc_isPcMw(), solstp_pcConnectDummies(), solstp_pcGetSolRoot(), and UNKNOWN.

Referenced by pcmwUpdateBestSol(), pcmwUpdateBestSol_csrInSync(), and updateBestSol().

solstp_getTrivialSol()

void solstp_getTrivialSol	(	const GRAPH *	g,
		int *	soledge
	)

sets trivial solution (all UNKNOWN)

Parameters

g	the graph
soledge	solution

Definition at line 2020 of file solstp.c.

References graph_get_nEdges(), graph_pc_isPcMw(), NULL, pcsolGetTrivialEdges(), and UNKNOWN.

Referenced by SCIPStpHeurAscendPruneRun().

solstp_getNedges()

int solstp_getNedges	(	const GRAPH *	g,
		const int *	soledge
	)

computes number of edges in solution value

Parameters

g	the graph
soledge	solution

Definition at line 2040 of file solstp.c.

References CONNECT, and graph_get_nEdges().

Referenced by strongPruneSteinerTreePc(), and updateBestSol().

solstp_getNedgesBounded()

int solstp_getNedgesBounded	(	const GRAPH *	g,
		const int *	soledge,
		int	nedges
	)

computes number of edges in solution value

Parameters

g	the graph
soledge	solution
nedges	the (first) number of edges to consider

Definition at line 2058 of file solstp.c.

References CONNECT, and graph_get_nEdges().

Referenced by strongPruneSteinerTreePc_csr().

solstp_setVertexFromEdge()

void solstp_setVertexFromEdge	(	const GRAPH *	g,
		const int *	result,
		STP_Bool *	solnode
	)

marks vertices for given edge-solution array (CONNECT/UNKNOWN)

Parameters

g	the graph
result	solution array (CONNECT/UNKNOWN)
solnode	marks whether node is in solution

Definition at line 2078 of file solstp.c.

References CONNECT, EAT_FREE, GRAPH::edges, FALSE, GRAPH::head, GRAPH::knots, nnodes, GRAPH::oeat, GRAPH::source, GRAPH::tail, and TRUE.

Referenced by graph_pc_solGetObj(), pseudodeleteInit(), reducePcMw(), reduceRootedProb(), SCIPStpHeurLocalExtendPcMwImp(), SCIPStpHeurLocalExtendPcMwOut(), and solPrune().

solstp_setVertexFromEdgeConn()

void solstp_setVertexFromEdgeConn	(	const GRAPH *	g,
		const int *	soledge,
		int *	solnode
	)

marks vertices for given edge-solution array (both CONNECT/UNKNOWN)

Parameters

g	the graph
soledge	solution array (CONNECT/UNKNOWN)
solnode	marks whether node is in solution

Definition at line 2114 of file solstp.c.

References CONNECT, EAT_FREE, GRAPH::edges, GRAPH::head, GRAPH::knots, nnodes, GRAPH::oeat, GRAPH::source, GRAPH::tail, and UNKNOWN.

Referenced by reduce_sollocalUpdateNodesol().

solstp_getOrg()

SCIP_RETCODE solstp_getOrg	(	SCIP *	scip,
		const GRAPH *	transgraph,
		const GRAPH *	orggraph,
		const int *	transsoledge,
		int *	orgsoledge
	)

get original solution

Parameters

scip	SCIP data structure
transgraph	the transformed graph
orggraph	the original graph
transsoledge	solution for transformed problem
orgsoledge	new retransformed solution

Definition at line 2148 of file solstp.c.

References GRAPH::ancestors, CONNECT, GRAPH::edges, FALSE, graph_edge_getAncestors(), graph_getFixedges(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_nFixedTerms(), GRAPH::head, GRAPH::knots, NULL, GRAPH::pcancestors, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, setNodeList(), solstp_isValid(), solstp_markPcancestors(), solstp_prune(), GRAPH::source, GRAPH::stp_type, GRAPH::tail, GRAPH::terms, and TRUE.

Referenced by SCIPStpHeurPruneUpdateSols().

solstp_markPcancestors()

SCIP_RETCODE solstp_markPcancestors	(	SCIP *	scip,
		IDX **	pcancestors,
		const int *	tails,
		const int *	heads,
		int	orgnnodes,
		STP_Bool *	solnodemark,
		STP_Bool *	soledgemark,
		int *	solnodequeue,
		int *	nsolnodes,
		int *	nsoledges
	)

mark original solution

Parameters

scip	SCIP data structure
pcancestors	the ancestors
tails	tails array
heads	heads array
orgnnodes	original number of nodes
solnodemark	solution nodes mark array
soledgemark	solution edges mark array or NULL
solnodequeue	solution nodes queue or NULL
nsolnodes	number of solution nodes or NULL
nsoledges	number of solution edges or NULL

Definition at line 2200 of file solstp.c.

References nnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, and TRUE.

Referenced by computeHistoryPcMw(), retransformReducedProbSolution(), SCIPStpHeurRecExclude(), solstp_getOrg(), and updateEdgestateFromRedPcmw().