Scippy

SCIP

Solving Constraint Integer Programs

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
scipSCIP data structure
gthe graph
resultsolution array (CONNECT/UNKNOWN)
newrootthe new root
isInfeasibleinfeasible?

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
ggraph structure
subtree_rootroot of the subtree
dfsposarray to mark DFS positions of nodes
resultST edges
connectedST 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_orgcostsCSR
subtree_rootroot of the subtree
dfsposarray to mark DFS positions of nodes
resultST edges
connectedST 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
ggraph structure
costedge costs
subtree_rootroot of the subtree
dfsposarray to mark DFS positions of nodes
resultST edges
connectedST nodes
dfscountcounter

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_orgcostsCSR
prizethe prize
isPcis PC?
subtree_rootroot of the subtree
dfsposarray to mark DFS positions of nodes
resultST edges
connectedST nodes
dfscountcounter

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
ggraph structure
connectedST nodes
resultMST 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
scipSCIP data structure
ggraph structure
costedge costs
rootroot of solution
resultMST 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
connectedST nodes
ggraph 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
ggraph structure
connectedST 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
ggraph structure
resultMST solution, which does not include artificial terminals
connectedST 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
ggraph structure
mstthe MST
resultST edges (need to be set to UNKNOWN)
connectedST 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
ggraph structure
connectedST nodes
rootroot of solution
mstthe MST
resultMST 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
scipSCIP data structure
ggraph structure
costedge costs
solrootroot of the solution
resultST edges
connectedST 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
scipSCIP data structure
ggraph structure
csr_orgcostsCSR
solrootroot of the solution
resultST edges
connectedST 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
scipSCIP data structure
ggraph structure
costedge costs
resultST edges, which need to be set to UNKNOWN
connectedST 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
ggraph structure
mstthe MST
resultST edges (need to be set to UNKNOWN)
connectedST 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

◆ pruneSteinerTreePc_csr()

static SCIP_RETCODE pruneSteinerTreePc_csr ( SCIP scip,
const GRAPH g,
MST mst,
int *RESTRICT  result,
STP_Bool *RESTRICT  connected 
)
static
Parameters
scipSCIP data structure
ggraph structure
mstthe MST
resultST edges (need to be set to UNKNOWN)
connectedST 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
ggraph data structure
solnodesolution nodes array (TRUE/FALSE)
listnodeedge 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
scipSCIP data structure
ggraph structure
connectedST 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
ggraph structure
solrootroot of solution
resultMST solution, which does not include artificial terminals
connectedST 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
scipSCIP data structure
ggraph structure
soledgesolution
heurheuristic data or NULL
successdenotes 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
ggraph structure
resultST edges
connectedST 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()

◆ solstp_pruneFromNodes()

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

prune solution given by included nodes

Parameters
scipSCIP data structure
ggraph structure
resultST edges
connectedST 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
scipSCIP data structure
ggraph structure
resultST 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
scipSCIP data structure
ggraph structure
costedge costs (original edge costs for PC!)
resultST edges
connectedST 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
scipSCIP data structure
ggraph structure
spathsshortest paths; NOTE: distances and preds not valid afterwards! hacky, but improves cache-efficiency
resultST 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
scipSCIP data structure
gthe graph
resultsolution array (CONNECT/UNKNOWN)
newrootthe 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
scipSCIP data structure
gthe graph
resultsolution array (CONNECT/UNKNOWN)
newrootthe new root
isInfeasibleinfeasible?

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
scipSCIP data structure
graphgraph data structure
resultsolution 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
ggraph data structure
resultsolution array, indicating whether an edge is in the solution
nodenode 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
scipSCIP data structure
graphgraph data structure
resultsolution 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
graphgraph data structure
resultsolution 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()

◆ solstp_getObj()

◆ 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
gthe graph
csrthe csr
soledge_csrsolution (CONNECT/UNKNOWN)
solnodesolution 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
gthe graph
csrthe csr
soledge_csrsolution (CONNECT/UNKNOWN)
solnodesolution 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
scipSCIP data structure
scipsolSCIP solution data structure
gthe graph
soledgessolution (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
scipSCIP data structure
gthe graph
csrthe CSR
soledge_csrCSR solution (CONNECT/UNKNOWN)
solnodesolution vertices (TRUE/FALSE) in/out!
soledge_ggraph 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
gthe graph
soledgesolution

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
gthe graph
soledgesolution

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
gthe graph
soledgesolution
nedgesthe (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
gthe graph
resultsolution array (CONNECT/UNKNOWN)
solnodemarks 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
gthe graph
soledgesolution array (CONNECT/UNKNOWN)
solnodemarks 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
scipSCIP data structure
transgraphthe transformed graph
orggraphthe original graph
transsoledgesolution for transformed problem
orgsoledgenew 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
scipSCIP data structure
pcancestorsthe ancestors
tailstails array
headsheads array
orgnnodesoriginal number of nodes
solnodemarksolution nodes mark array
soledgemarksolution edges mark array or NULL
solnodequeuesolution nodes queue or NULL
nsolnodesnumber of solution nodes or NULL
nsoledgesnumber 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().