Detailed Description

includes methods for Steiner tree problem solutions

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.

Definition in file solstp.h.

#include "scip/scip.h"
#include "graph.h"
#include "shortestpath.h"

Go to the source code of this file.

Functions
void	solstp_pcConnectDummies (const GRAPH , int, int RESTRICT, STP_Bool *RESTRICT)

SCIP_Real	solstp_pcGetObjCsr (const GRAPH , const CSR , const int , const STP_Bool )

int	solstp_pcGetSolRoot (SCIP , const GRAPH , const STP_Bool *)

SCIP_RETCODE	solstp_addSolToProb (SCIP , const GRAPH , const int , SCIP_HEUR , SCIP_Bool *)

void	solstp_setVertexFromEdge (const GRAPH , const int , STP_Bool *)

void	solstp_setVertexFromEdgeConn (const GRAPH , const int , int *)

void	solstp_print (const GRAPH , const int )

SCIP_RETCODE	solstp_markPcancestors (SCIP , IDX , const int , const int , int, STP_Bool , STP_Bool , int , int , int )

SCIP_Bool	solstp_isUnreduced (SCIP , const GRAPH , const int *)

SCIP_Bool	solstp_isValid (SCIP , const GRAPH , const int *)

SCIP_Bool	solstp_containsNode (const GRAPH , const int , int)

SCIP_Bool	stpsol_pruningIsPossible (const GRAPH , const int , const STP_Bool *)

SCIP_Real	solstp_getObjBounded (const GRAPH , const int , SCIP_Real, int)

SCIP_Real	solstp_getObj (const GRAPH , const int , SCIP_Real)

SCIP_Real	solstp_getObjCsr (const GRAPH , const CSR , const int , const STP_Bool )

int	solstp_getNedges (const GRAPH , const int )

int	solstp_getNedgesBounded (const GRAPH , const int , int)

void	solstp_getTrivialSol (const GRAPH , int )

void	solstp_getStpFromSCIPsol (SCIP , SCIP_SOL , const GRAPH , int )

void	solstp_convertCsrToGraph (SCIP , const GRAPH , const CSR , const int , STP_Bool RESTRICT, int RESTRICT)

SCIP_RETCODE	solstp_getOrg (SCIP , const GRAPH , const GRAPH , const int , int *)

SCIP_RETCODE	solstp_reroot (SCIP , const GRAPH , int *, int)

SCIP_RETCODE	solstp_rerootInfeas (SCIP , GRAPH , int , int, SCIP_Bool )

SCIP_RETCODE	solstp_prune (SCIP , const GRAPH , int , STP_Bool )

SCIP_RETCODE	solstp_pruneFromTmHeur (SCIP , const GRAPH , const SCIP_Real , int RESTRICT, STP_Bool *RESTRICT)

SCIP_RETCODE	solstp_pruneFromTmHeur_csr (SCIP , const GRAPH , SPATHS , int RESTRICT)

SCIP_RETCODE	solstp_pruneFromNodes (SCIP , const GRAPH , int , STP_Bool )

SCIP_RETCODE	solstp_pruneFromEdges (SCIP , const GRAPH , int *)

Function Documentation

◆ solstp_pcConnectDummies()

void solstp_pcConnectDummies	(	const GRAPH *	,
		int	,
		int *	RESTRICT,
		STP_Bool *	RESTRICT
	)

◆ 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_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_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().

◆ 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_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_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().

◆ 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_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_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.

◆ 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_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_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_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_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_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 *	,
		const GRAPH *	,
		const CSR *	,
		const int *	,
		STP_Bool *	RESTRICT,
		int *	RESTRICT
	)

◆ 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_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_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_pruneFromTmHeur()

SCIP_RETCODE solstp_pruneFromTmHeur	(	SCIP *	,
		const GRAPH *	,
		const SCIP_Real *	,
		int *	RESTRICT,
		STP_Bool *	RESTRICT
	)

◆ solstp_pruneFromTmHeur_csr()

SCIP_RETCODE solstp_pruneFromTmHeur_csr	(	SCIP *	,
		const GRAPH *	,
		SPATHS *	,
		int *	RESTRICT
	)

◆ 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().

SCIP

Detailed Description

Functions

Function Documentation

◆ solstp_pcConnectDummies()

◆ solstp_pcGetObjCsr()

◆ solstp_pcGetSolRoot()

◆ solstp_addSolToProb()

◆ solstp_setVertexFromEdge()

◆ solstp_setVertexFromEdgeConn()

◆ solstp_print()

◆ solstp_markPcancestors()

◆ solstp_isUnreduced()

◆ solstp_isValid()

◆ solstp_containsNode()

◆ stpsol_pruningIsPossible()

◆ solstp_getObjBounded()

◆ solstp_getObj()

◆ solstp_getObjCsr()

◆ solstp_getNedges()

◆ solstp_getNedgesBounded()

◆ solstp_getTrivialSol()

◆ solstp_getStpFromSCIPsol()

◆ solstp_convertCsrToGraph()

◆ solstp_getOrg()

◆ solstp_reroot()

◆ solstp_rerootInfeas()

◆ solstp_prune()

◆ solstp_pruneFromTmHeur()

◆ solstp_pruneFromTmHeur_csr()

◆ solstp_pruneFromNodes()

◆ solstp_pruneFromEdges()