Detailed Description

includes various reduction methods for Steiner tree problems

Author: Daniel Rehfeldt

Definition in file reduce.h.

#include "scip/scip.h"
#include "graph.h"
#include "mincut.h"
#include "bidecomposition.h"
#include "stpvector.h"
#include "redcosts.h"
#include "reducedefs.h"
#include "extreducedefs.h"
#include "termsepadefs.h"

Go to the source code of this file.

Functions
int	reduce_getMinNreductions (const GRAPH *, int)

SCIP_RETCODE	reduce_baseInit (SCIP , const GRAPH , REDBASE **)

void	reduce_baseFree (SCIP , REDBASE *)

SCIP_RETCODE	reduce_stp (SCIP , GRAPH , REDSOL *, int, SCIP_Bool, SCIP_Bool, SCIP_Bool, SCIP_Bool)

SCIP_RETCODE	reduce_pc (SCIP , REDSOL , GRAPH *, int, SCIP_Bool, SCIP_Bool, SCIP_Bool, SCIP_Bool)

SCIP_RETCODE	reduce_mw (SCIP , REDSOL , GRAPH *, int, SCIP_Bool, SCIP_Bool, SCIP_Bool)

SCIP_RETCODE	reduce_hc (SCIP , GRAPH , SCIP_Real *, int)

SCIP_RETCODE	reduce_sap (SCIP , GRAPH , SCIP_Bool, SCIP_Real *, int)

SCIP_RETCODE	reduce_nw (SCIP , GRAPH , SCIP_Real *, int)

SCIP_RETCODE	reduce_dc (SCIP , GRAPH , SCIP_Real *, int)

SCIP_RETCODE	reduce_redLoopStp (SCIP , GRAPH , REDBASE *)

SCIP_RETCODE	reduce_redLoopPc (SCIP , REDSOL , GRAPH , PATH , PATH , SCIP_Real , int , int , int , int , int , int , STP_Bool *, SCIP_Bool, SCIP_Bool, SCIP_Bool, int, SCIP_Bool, SCIP_Bool, SCIP_Bool)

SCIP_RETCODE	reduce_redLoopMw (SCIP , REDSOL , GRAPH , PATH , SCIP_Real , int , int , int , STP_Bool *, STP_Bool, STP_Bool, STP_Bool, int, SCIP_Bool, SCIP_Bool)

SCIP_RETCODE	reduce_exec (SCIP , GRAPH , REDSOL *, int, int, SCIP_Bool)

SCIP_RETCODE	reduce_sollocalInit (SCIP , const GRAPH , REDSOLLOCAL **)

void	reduce_sollocalFree (SCIP , REDSOLLOCAL *)

int *	reduce_sollocalGetSolnode (REDSOLLOCAL *)

void	reduce_sollocalSetOffset (SCIP_Real, REDSOLLOCAL *)

void	reduce_sollocalUpdateUpperBound (SCIP_Real, REDSOLLOCAL *)

SCIP_RETCODE	reduce_sollocalUpdateNodesol (SCIP , const int , GRAPH , REDSOLLOCAL )

SCIP_Real	reduce_sollocalGetUpperBound (const REDSOLLOCAL *)

SCIP_Real	reduce_sollocalGetUpperBoundWithOffset (const REDSOLLOCAL *)

SCIP_Bool	reduce_sollocalHasUpperBound (const REDSOLLOCAL *)

SCIP_Bool	reduce_sollocalUsesNodesol (const REDSOLLOCAL *)

SCIP_RETCODE	reduce_sollocalRebuildTry (SCIP , GRAPH , REDSOLLOCAL *)

SCIP_RETCODE	reduce_solInit (SCIP , const GRAPH , SCIP_Bool, REDSOL **)

void	reduce_solFree (SCIP , REDSOL *)

SCIP_RETCODE	reduce_solInitLocal (SCIP , const GRAPH , REDSOL , REDSOLLOCAL *)

void	reduce_solFinalizeLocal (SCIP , const GRAPH , REDSOL *)

void	reduce_solReInitLocal (const GRAPH , REDSOL )

void	reduce_solPack (const GRAPH , const int , int, REDSOL *)

SCIP_RETCODE	reduce_solLevelAdd (SCIP , const GRAPH , REDSOL *)

SCIP_RETCODE	reduce_solLevelTopUpdate (SCIP , const GRAPH , REDSOL *)

void	reduce_solLevelTopFinalize (SCIP , GRAPH , REDSOL *)

void	reduce_solLevelTopRemove (SCIP , REDSOL )

void	reduce_solLevelTopClean (SCIP , REDSOL )

void	reduce_solLevelTopTransferSolBack (const int , REDSOL )

SCIP_RETCODE	reduce_solLevelTopTransferSolTo (const int , REDSOL )

void	reduce_solSetOffset (SCIP_Real, REDSOL *)

SCIP_Real	reduce_solGetOffset (const REDSOL *)

SCIP_Real	reduce_solGetUpperBoundWithOffset (const REDSOL *)

const int *	reduce_solGetNodesolPointer (const REDSOL *)

SCIP_Bool	reduce_solUsesNodesol (const REDSOL *)

SCIP_Real *	reduce_solGetOffsetPointer (REDSOL *)

SCIP_RETCODE	reduce_solGetEdgesol (SCIP , GRAPH , REDSOL , SCIP_Real , int *)

SCIP_RETCODE	reduce_solAddNodesol (const GRAPH , const int , REDSOL *)

void	reduce_solGetNodesol (const GRAPH , REDSOL , int *)

SCIP_RETCODE	reduce_impliedProfitBased (SCIP , int, GRAPH , int , SCIP_Real , int *)

SCIP_RETCODE	reduce_impliedProfitBasedRpc (SCIP , GRAPH , REDSOLLOCAL , SCIP_Real , int *)

SCIP_RETCODE	reduce_ans (SCIP , GRAPH , int *)

SCIP_RETCODE	reduce_ansAdv (SCIP , GRAPH , int *, SCIP_Bool)

SCIP_RETCODE	reduce_ansAdv2 (SCIP , GRAPH , int *)

SCIP_RETCODE	reduce_nnp (SCIP , GRAPH , int *)

SCIP_RETCODE	reduce_nv (SCIP , GRAPH , PATH , SCIP_Real , int , int , int , int )

SCIP_RETCODE	reduce_nvAdv (SCIP , const int , GRAPH , PATH , SCIP_Real , SCIP_Real , int , int , int , int , int *)

SCIP_RETCODE	reduce_sl (SCIP , const int , GRAPH , PATH , SCIP_Real , int , int , STP_Bool , int , int )

SCIP_RETCODE	reduce_nsvImplied (SCIP , const SD , GRAPH , int , SCIP_Real , int )

SCIP_RETCODE	reduce_nsvImpliedRecord (SCIP , const SD , GRAPH , STP_Vectype(int) )

SCIP_RETCODE	reduce_cnsAdv (SCIP , GRAPH , int , int )

SCIP_RETCODE	reduce_npv (SCIP , GRAPH , PATH , int , int , int , int *, int)

SCIP_RETCODE	reduce_chain2 (SCIP , GRAPH , PATH , int , int , int , int *, int)

SCIP_RETCODE	reduce_sdEdgeCliqueStar (SCIP , int, GRAPH , int *)

SCIP_RETCODE	reduce_sdImpLongEdge (SCIP , const int , GRAPH , SD , int *)

SCIP_RETCODE	reduce_sdsp (SCIP , GRAPH , PATH , int , int , int , int , int , int *, int, SCIP_Bool)

SCIP_RETCODE	reduce_sdStar (SCIP , int, SCIP_Bool, GRAPH , SCIP_Real , int , int , STP_Bool , DHEAP , int )

SCIP_RETCODE	reduce_sdStarBiased (SCIP , int, SCIP_Bool, GRAPH , int *)

SCIP_RETCODE	reduce_sdStarBiasedWithProfit (SCIP , int, const SDPROFIT , SCIP_Bool, GRAPH , int )

SCIP_RETCODE	reduce_sdStarPc (SCIP , int, const int , GRAPH , SCIP_Real , int , int , STP_Bool , DHEAP , int *)

SCIP_RETCODE	reduce_sdStarPc2 (SCIP , int, SCIP_Bool, GRAPH , SCIP_Real , int , int , STP_Bool , DHEAP , int )

SCIP_RETCODE	reduce_sdWalk (SCIP , int, const int , GRAPH , int , SCIP_Real , int , int , int , STP_Bool , int )

SCIP_RETCODE	reduce_sdWalk_csr (SCIP , int, const int , GRAPH , int , SCIP_Real , int , STP_Bool , DHEAP , int *)

SCIP_RETCODE	reduce_sdWalkTriangle (SCIP , int, SCIP_Bool, GRAPH , int , SCIP_Real , int , STP_Bool , DHEAP , int )

SCIP_RETCODE	reduce_sdWalkExt (SCIP , int, SCIP_Bool, GRAPH , SCIP_Real , int , int , int , STP_Bool , int )

SCIP_RETCODE	reduce_sdWalkExt2 (SCIP , int, const int , GRAPH , int , SCIP_Real , int , int , int , STP_Bool , int )

SCIP_RETCODE	reduce_sdspSap (SCIP , GRAPH , PATH , PATH , int , int , int , int , int , int , int)

SCIP_RETCODE	reduce_sd (SCIP , GRAPH , REDBASE , int )

SCIP_RETCODE	reduce_sdBiased (SCIP , SD , GRAPH , int )

SCIP_RETCODE	reduce_sdBiasedNeighbor (SCIP , SD , GRAPH , int )

SCIP_RETCODE	reduce_sdPc (SCIP , GRAPH , PATH , int , int , int , int , int , int *)

SCIP_Real	reduce_sdGetSd (const GRAPH , int, int, SCIP_Real, SCIP_Real, SD )

SCIP_Real	reduce_sdGetSdIntermedTerms (const GRAPH , int, int, SCIP_Real, SCIP_Real, SD )

SCIP_RETCODE	reduce_getSdByPaths (SCIP , GRAPH , PATH , PATH , SCIP_Real , SCIP_Real, int , int , int , int , int , int, int, int, SCIP_Bool, SCIP_Bool)

SCIP_RETCODE	reduce_bdk (SCIP , int, GRAPH , int *)

SCIP_RETCODE	reduce_bdkBiased (SCIP , int, GRAPH , int *)

SCIP_RETCODE	reduce_bdkWithSd (SCIP , int, SD , GRAPH , int )

SCIP_RETCODE	reduce_pathreplace (SCIP , GRAPH , int *)

SCIP_RETCODE	reduce_pathreplaceExt (SCIP , GRAPH , EXTPERMA , int )

SCIP_RETCODE	reduce_bd34 (SCIP , GRAPH , PATH , PATH , int , int , int , int , int , int , int, SCIP_Real *)

SCIP_RETCODE	reduce_bd34WithSd (SCIP , GRAPH , SDGRAPH , PATH , int , int )

SCIP_RETCODE	reduce_bound (SCIP , GRAPH , PATH , SCIP_Real , SCIP_Real , SCIP_Real , int , int , int , int )

SCIP_RETCODE	reduce_boundMw (SCIP , GRAPH , PATH , SCIP_Real , int , int , int , int , int *)

SCIP_RETCODE	reduce_boundPruneHeur (SCIP , GRAPH , PATH , SCIP_Real , SCIP_Real , SCIP_Real , SCIP_Real , int , int , int , const int , const int , int *, int)

SCIP_RETCODE	reduce_boundHop (SCIP , GRAPH , PATH , SCIP_Real , SCIP_Real , SCIP_Real , int , int , int , int )

SCIP_RETCODE	reduce_boundHopR (SCIP , GRAPH , PATH , SCIP_Real , SCIP_Real , SCIP_Real , int , int , int , int , int *)

SCIP_RETCODE	reduce_boundHopRc (SCIP , GRAPH , PATH , SCIP_Real , SCIP_Real , SCIP_Real , SCIP_Real, int , int , int , int , int *, SCIP_Bool)

SCIP_RETCODE	reduce_boundHopDa (SCIP , GRAPH , int , SCIP_RANDNUMGEN )

SCIP_RETCODE	reduce_da (SCIP , GRAPH , const RPDA , REDSOLLOCAL , SCIP_Real , int , SCIP_RANDNUMGEN *)

SCIP_RETCODE	reduce_dapaths (SCIP , GRAPH , SCIP_Real , int )

SCIP_RETCODE	reduce_daSlackPrune (SCIP , GRAPH , int, SCIP_Bool, int , int , int , SCIP_Real , SCIP_Bool , SCIP_Bool )

SCIP_RETCODE	reduce_daPcMw (SCIP , GRAPH , const RPDA , REDSOLLOCAL , PATH , SCIP_Real , int , int , int , STP_Bool , int , SCIP_RANDNUMGEN , SCIP_Real)

SCIP_RETCODE	reduce_deleteConflictEdges (SCIP , GRAPH )

SCIP_RETCODE	reduce_extendedCheck3Tree (SCIP , const GRAPH , int, const SCIP_Real , const SCIP_Real , const PATH , const int , SCIP_Real, const int , int, SCIP_Real , SCIP_Bool , unsigned int , int , SCIP_Bool )

int	reduce_extendedEdge (SCIP , GRAPH , const PATH , const SCIP_Real , const SCIP_Real , const int , SCIP_Real, int, STP_Bool *, SCIP_Bool)

void	reduce_nodesDeg1 (SCIP , GRAPH )

SCIP_RETCODE	reduce_simple (SCIP , GRAPH , SCIP_Real , int , int , int )

void	reduce_simple_dc (SCIP , GRAPH )

SCIP_RETCODE	reduce_simple_hc (SCIP , GRAPH , SCIP_Real , int )

SCIP_RETCODE	reduce_simple_sap (SCIP , GRAPH , SCIP_Real , int )

SCIP_RETCODE	reduce_deleteMultiedges (SCIP , GRAPH )

SCIP_RETCODE	reduce_contract0Edges (SCIP , GRAPH , int *, SCIP_Bool)

SCIP_RETCODE	reduce_fixedConflicts (SCIP , const int , GRAPH , int )

SCIP_RETCODE	reduce_cutEdgeTryPrune (SCIP , int, GRAPH , SCIP_Bool *)

SCIP_RETCODE	reduce_rpt (SCIP , GRAPH , SCIP_Real , int )

void	reduce_identifyNonLeafTerms (SCIP , GRAPH )

SCIP_RETCODE	reduce_unconnected (SCIP , GRAPH )

SCIP_RETCODE	reduce_unconnectedForDirected (SCIP , GRAPH )

SCIP_RETCODE	reduce_unconnectedInfeas (SCIP , SCIP_Bool, GRAPH , SCIP_Bool *)

SCIP_RETCODE	reduce_articulations (SCIP , GRAPH , SCIP_Real , int )

SCIP_RETCODE	reduce_bidecomposition (SCIP , GRAPH , REDBASE , int , SCIP_Bool *)

SCIP_RETCODE	reduce_bidecompositionExact (SCIP , GRAPH , REDBASE , int , int *)

SCIP_RETCODE	reduce_nonTerminalComponents (SCIP , const CUTNODES , GRAPH , SCIP_Real , int *)

SCIP_RETCODE	reduce_simple_mw (SCIP , GRAPH , int , SCIP_Real , int *)

SCIP_RETCODE	reduce_simple_pc (SCIP , const int , GRAPH , SCIP_Real , int , int , int *)

void	reduce_removeDeg0NonLeafTerms (SCIP , GRAPH , SCIP_Real *)

SCIP_RETCODE	reduce_unconnectedRpcRmw (SCIP , GRAPH , SCIP_Real *)

SCIP_RETCODE	reduce_unconnectedRpcRmwInfeas (SCIP , GRAPH , SCIP_Real , SCIP_Bool )

void	reduce_impliedNodesGet (SCIP , const GRAPH , STP_Vectype(int) *)

void	reduce_impliedNodesRepair (SCIP , const GRAPH , int, int, STP_Vectype(int) *)

SCIP_Bool	reduce_impliedNodesIsValid (const GRAPH , const STP_Vectype(int) )

SCIP_RETCODE	reduce_applyPseudoDeletions (SCIP , const SCIP_Bool , REDCOST , GRAPH , SCIP_Real , int )

SCIP_RETCODE	reduce_blctreeInit (SCIP , GRAPH , BLCTREE **)

void	reduce_blctreeFree (SCIP , BLCTREE *)

int	reduce_blctreeGetMstNedges (const BLCTREE *)

void	reduce_blctreeGetMstEdges (const GRAPH , const BLCTREE , int *)

void	reduce_blctreeGetMstEdgesToCutDist (const GRAPH , const BLCTREE , SCIP_Real RESTRICT, SCIP_Real RESTRICT)

void	reduce_blctreeGetMstBottlenecks (const GRAPH , const BLCTREE , SCIP_Real *)

void	reduce_blctreeGetMstEdgesState (const GRAPH , const BLCTREE , SCIP_Bool *)

SCIP_RETCODE	reduce_blctreeRebuild (SCIP , GRAPH , BLCTREE *)

SCIP_RETCODE	reduce_dcmstInit (SCIP , int, DCMST *)

void	reduce_dcmstFree (SCIP , DCMST *)

SCIP_Bool	reduce_dcmstMstIsValid (SCIP , const CSR )

void	reduce_dcmstAddNode (SCIP , const CSR , const SCIP_Real , DCMST , CSR *)

void	reduce_dcmstAddNodeInplace (SCIP , const SCIP_Real , DCMST , CSR )

void	reduce_dcmstGet0NodeMst (SCIP , CSR )

void	reduce_dcmstGet1NodeMst (SCIP , CSR )

void	reduce_dcmstGet2NodeMst (SCIP , SCIP_Real, CSR )

void	reduce_dcmstGet3NodeMst (SCIP , SCIP_Real, SCIP_Real, SCIP_Real, CSR )

SCIP_Real	reduce_dcmstGetExtWeight (SCIP , const CSR , const SCIP_Real , DCMST )

SCIP_Real	reduce_dcmstGetWeight (SCIP , const CSR )

int	reduce_dcmstGetMaxnnodes (const DCMST *)

SCIP_Real *	reduce_dcmstGetAdjcostBuffer (const DCMST *)

SCIP_RETCODE	reduce_starInit (SCIP , int, STAR *)

void	reduce_starFree (SCIP , STAR *)

void	reduce_starReset (const GRAPH , int, STAR )

void	reduce_starResetWithEdges (const GRAPH , const STP_Vectype(int), STAR )

const int *	reduce_starGetNext (STAR , int )

const int *	reduce_starGetNextAndPosition (STAR , int , int *)

const int *	reduce_starGetRuledOutEdges (STAR , int )

int	reduce_starGetCenter (const STAR *)

void	reduce_starCurrentSetRuledOut (STAR *)

void	reduce_starCurrentSetFailed (STAR *)

SCIP_Bool	reduce_starHasPromisingEdges (const STAR *)

SCIP_Bool	reduce_starAllAreChecked (const STAR *)

SCIP_RETCODE	reduce_sdneighborInit (SCIP , const GRAPH , SDN **)

void	reduce_sdneighborGetCloseTerms (const GRAPH , const SDN , int, SCIP_Real, int RESTRICT, SCIP_Real RESTRICT, int *RESTRICT)

void	reduce_sdneighborFree (SCIP , SDN *)

const SCIP_Bool *	reduce_sdneighborGetBlocked (const SDN *)

SCIP_RETCODE	reduce_sdUpdateWithSdNeighbors (SCIP , GRAPH , SD , int )

SCIP_RETCODE	reduce_sdprofitInit (SCIP , const GRAPH , SDPROFIT **)

SCIP_RETCODE	reduce_sdprofitInit1stOnly (SCIP , const GRAPH , const SCIP_Real , SDPROFIT *)

void	reduce_sdprofitFree (SCIP , SDPROFIT *)

SCIP_RETCODE	reduce_sdprofitUpdateFromBLC (SCIP , const GRAPH , const BLCTREE , SCIP_Bool, SDPROFIT )

SCIP_RETCODE	reduce_sdprofitBuildFromBLC (SCIP , const GRAPH , const BLCTREE , SCIP_Bool, SDPROFIT )

void	reduce_sdprofitPrintStats (const GRAPH , const SDPROFIT )

SCIP_RETCODE	reduce_sdInit (SCIP , GRAPH , SD **)

SCIP_RETCODE	reduce_sdInitBiased (SCIP , GRAPH , SD **)

SCIP_RETCODE	reduce_sdInitBiasedBottleneck (SCIP , GRAPH , SD **)

SCIP_RETCODE	reduce_sdRepair (SCIP , int, SCIP_Bool, GRAPH , SD *)

SCIP_RETCODE	reduce_sdRepairSetUp (SCIP , const GRAPH , SD *)

SCIP_RETCODE	reduce_sdAddNeighborSd (SCIP , const GRAPH , SD *)

void	reduce_sdFree (SCIP , SD *)

SCIP_RETCODE	reduce_sdGetSdsCliquegraph (SCIP , const GRAPH , int, const int , DIJK , SD , GRAPH )

SCIP_RETCODE	reduce_sdgraphInit (SCIP , const GRAPH , SDGRAPH **)

SCIP_RETCODE	reduce_sdgraphInitFromDistGraph (SCIP , const GRAPH , GRAPH , int , SDGRAPH **)

SCIP_RETCODE	reduce_sdgraphInitBiased (SCIP , const GRAPH , const SDPROFIT , SDGRAPH *)

SCIP_RETCODE	reduce_sdgraphInitBiasedFromTpaths (SCIP , GRAPH , const SDPROFIT , const TPATHS , SDGRAPH **)

SCIP_Real	reduce_sdgraphGetMaxCost (const SDGRAPH *)

const SCIP_Real *	reduce_sdgraphGetOrderedMstCosts (const SDGRAPH *)

const int *	reduce_sdgraphGetOrgnodesToSdMap (const SDGRAPH *)

void	reduce_sdgraphInitOrderedMstCosts (SDGRAPH *)

const STP_Bool *	reduce_sdgraphGetMstHalfMark (const SDGRAPH *)

SCIP_Bool	reduce_sdgraphHasMstHalfMark (const SDGRAPH *)

SCIP_Bool	reduce_sdgraphEdgeIsInMst (const SDGRAPH *, int)

SCIP_Bool	reduce_sdgraphHasOrderedMstCosts (const SDGRAPH *)

SCIP_Real	reduce_sdgraphGetSd (int, int, SDGRAPH *)

void	reduce_sdgraphFree (SCIP , SDGRAPH *)

void	reduce_sdgraphFreeFromDistGraph (SCIP , SDGRAPH *)

void	reduce_sdgraphInsertEdge (SCIP , int, int, SCIP_Real, int, int RESTRICT, SDGRAPH , SCIP_Bool )

SCIP_RETCODE	reduce_sdgraphMstBuild (SCIP , const GRAPH , SDGRAPH *)

void	reduce_sdgraphMstSortCosts (SDGRAPH *)

SCIP_RETCODE	reduce_termcompInit (SCIP , const GRAPH , COMPBUILDER , TERMCOMP *)

void	reduce_termcompFree (SCIP , TERMCOMP *)

SCIP_RETCODE	reduce_termcompInitTbottleneck (SCIP , const int , TERMCOMP *)

SCIP_RETCODE	reduce_termcompBuildSubgraph (SCIP , GRAPH , TERMCOMP *)

SCIP_RETCODE	reduce_termcompBuildSubgraphWithSds (SCIP , GRAPH , EXTPERMA , TERMCOMP )

SCIP_RETCODE	reduce_termcompChangeSubgraphToBottleneck (SCIP , GRAPH , TERMCOMP , SCIP_Bool )

void	reduce_termsepaGetNextComp (SCIP , const GRAPH , TERMSEPAS , COMPBUILDER , SCIP_Bool *)

SCIP_RETCODE	reduce_compbuilderInit (SCIP , const GRAPH , COMPBUILDER **)

void	reduce_compbuilderFree (SCIP , COMPBUILDER *)

SCIP_Real	reduce_compbuilderGetSubNodesRatio (const COMPBUILDER *)

void	reduce_compbuilderPrintSeparators (const GRAPH , const COMPBUILDER )

void	reduce_termcompChangeSubgraphToOrgCosts (const GRAPH , TERMCOMP )

SCIP_RETCODE	reduce_termsepaDaWithExperma (SCIP , GRAPH , EXTPERMA , SCIP_Bool , int *)

SCIP_RETCODE	reduce_termsepaDa (SCIP , GRAPH , int *)

SCIP_RETCODE	reduce_termsepaFull (SCIP , GRAPH , int , REDBASE , int *)

Function Documentation

◆ reduce_getMinNreductions()

int reduce_getMinNreductions	(	const GRAPH *	g,
		int	lowerbound
	)

gets reduction bound

Parameters

g	graph data structure
lowerbound	lower bound on number of reductions (>= 1)

Definition at line 1087 of file reduce_base.c.

References graph_get_nEdges(), graph_get_nNodes(), graph_pc_isMw(), graph_pc_isPc(), graph_typeIsSpgLike(), MAX, and nnodes.

Referenced by decomposeReduceSubDoIt(), reduce_mw(), reduce_pc(), and reduce_stp().

◆ reduce_baseInit()

SCIP_RETCODE reduce_baseInit	(	SCIP *	scip,
		const GRAPH *	g,
		REDBASE **	redbase
	)

initializes

Parameters

scip	SCIP data structure
g	graph data structure
redbase	base

Definition at line 1120 of file reduce_base.c.

References reduction_base::edgearrint, graph_get_nEdges(), graph_get_nNodes(), reduction_base::heap, nnodes, reduction_base::nodearrchar, reduction_base::nodearrint, reduction_base::nodearrint2, reduction_base::nodearrreal, NULL, reduction_base::path, reduction_base::redparameters, reduction_base::redsol, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, reduction_base::solnode, reduction_base::state, reduction_base::vbase, and reduction_base::vnoi.

Referenced by testBiconnectedDecomposition(), testBiconnectedDecomposition2(), and testBiconnectedDecomposition3().

◆ reduce_baseFree()

void reduce_baseFree	(	SCIP *	scip,
		REDBASE **	redbase
	)

frees

Parameters

scip	SCIP data structure
redbase	base

Definition at line 1155 of file reduce_base.c.

References reduction_base::edgearrint, reduction_base::heap, reduction_base::nodearrchar, reduction_base::nodearrint, reduction_base::nodearrint2, reduction_base::nodearrreal, SCIPfreeMemory, SCIPfreeMemoryArray, reduction_base::state, reduction_base::vbase, and reduction_base::vnoi.

Referenced by testBiconnectedDecomposition(), testBiconnectedDecomposition2(), and testBiconnectedDecomposition3().

◆ reduce_stp()

SCIP_RETCODE reduce_stp	(	SCIP *	scip,
		GRAPH *	g,
		REDSOL *	redsol,
		int	minelims,
		SCIP_Bool	dualascent,
		SCIP_Bool	nodereplacing,
		SCIP_Bool	userec,
		SCIP_Bool	usestrongreds
	)

basic reduction package for the STP

Parameters

scip	SCIP data structure
g	graph data structure
redsol	primal solution container
minelims	minimal number of edges to be eliminated in order to reiterate reductions
dualascent	perform dual-ascent reductions?
nodereplacing	should node replacement (by edges) be performed?
userec	use recombination heuristic?
usestrongreds	allow strong reductions? NOTE: needed for propagation, because arcs might have been fixed to 0

Definition at line 1181 of file reduce_base.c.

References bidecomposition_reduction_parameters::depth, reduction_parameters::dualascent, FALSE, graph_get_nEdges(), graph_get_nNodes(), graph_get_nTerms(), nnodes, nterms, NULL, reduction_base::redparameters, reduce_getMinNreductions(), reduce_redLoopStp(), reduce_solGetOffset(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisLE(), STP_BND_THRESHOLD, and TRUE.

Referenced by fixVarsRedbased(), and reduce_exec().

◆ reduce_pc()

SCIP_RETCODE reduce_pc	(	SCIP *	scip,
		REDSOL *	redsol,
		GRAPH *	g,
		int	minelims,
		SCIP_Bool	advanced,
		SCIP_Bool	userec,
		SCIP_Bool	nodereplacing,
		SCIP_Bool	usestrongreds
	)

basic reduction package for the (R)PCSTP

Parameters

scip	SCIP data structure
redsol	solution storage
g	graph data structure
minelims	minimal number of edges to be eliminated in order to reiterate reductions
advanced	perform advanced (e.g. dual ascent) reductions?
userec	use recombination heuristic?
nodereplacing	should node replacement (by edges) be performed?
usestrongreds	allow strong reductions? NOTE: needed for propagation, because arcs might have been fixed to 0

Definition at line 1260 of file reduce_base.c.

References GRAPH::edges, FALSE, graph_pc_nNonLeafTerms(), GRAPH::knots, nnodes, nterms, NULL, reduce_getMinNreductions(), reduce_redLoopPc(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetRealParam(), SCIPisGT(), SCIPisLE(), STP_BND_THRESHOLD, GRAPH::terms, and TRUE.

Referenced by fixVarsRedbased(), and reduce_exec().

◆ reduce_mw()

SCIP_RETCODE reduce_mw	(	SCIP *	scip,
		REDSOL *	redsol,
		GRAPH *	g,
		int	minelims,
		SCIP_Bool	advanced,
		SCIP_Bool	userec,
		SCIP_Bool	usestrongreds
	)

reduction package for the MWCSP

Parameters

scip	SCIP data structure
redsol	solution storage
g	graph data structure
minelims	minimal number of edges to be eliminated in order to reiterate reductions
advanced	perform advanced reductions?
userec	use recombination heuristic?
usestrongreds	allow strong reductions? NOTE: needed for propagation, because arcs might have been fixed to 0

Definition at line 1344 of file reduce_base.c.

References FALSE, graph_get_nNodes(), graph_get_nTerms(), nnodes, nterms, NULL, reduce_getMinNreductions(), reduce_redLoopMw(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPisLE(), and TRUE.

Referenced by fixVarsRedbased(), and reduce_exec().

◆ reduce_hc()

SCIP_RETCODE reduce_hc	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int	minelims
	)

basic reduction package for the HCDSTP

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to store the offset value
minelims	minimal number of edges to be eliminated in order to reiterate reductions

Definition at line 1403 of file reduce_base.c.

References reduce_costs_reduction_parameters::damode, extred_none, FALSE, graph_get_nEdges(), graph_get_nNodes(), GRAPH::knots, MAX, nnodes, NULL, reduce_bound(), reduce_boundHop(), reduce_boundHopDa(), reduce_boundHopR(), reduce_boundHopRc(), reduce_da(), reduce_simple_hc(), reduce_sollocalFree(), reduce_sollocalInit(), reduce_unconnectedForDirected(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcreateRandom(), SCIPfreeBufferArray, SCIPfreeRandom(), SCIPgetRealParam(), SCIPgetTotalTime(), SCIPisStopped(), STP_DAMODE_FAST, and TRUE.

Referenced by reduce_exec().

◆ reduce_sap()

SCIP_RETCODE reduce_sap	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Bool	dualascent,
		SCIP_Real *	fixed,
		int	minelims
	)

basic reduction package for the SAP

Parameters

scip	SCIP data structure
g	graph data structure
dualascent	perform dual-ascent reductions?
fixed	pointer to store the offset value
minelims	minimal number of edges to be eliminated in order to reiterate reductions

Definition at line 1557 of file reduce_base.c.

References GRAPH::cost, reduce_costs_reduction_parameters::damode, EQ, extred_none, FALSE, FARAWAY, graph_get_nEdges(), graph_get_nNodes(), graph_typeIsUndirected(), MAX, nnodes, NULL, reduce_da(), reduce_rpt(), reduce_sdspSap(), reduce_simple_sap(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcreateRandom(), SCIPfreeBufferArray, SCIPfreeRandom(), SCIPgetRealParam(), SCIPgetTotalTime(), SCIPisStopped(), STP_DAMODE_FAST, STP_SAP, GRAPH::stp_type, and TRUE.

Referenced by reduce_exec().

◆ reduce_nw()

SCIP_RETCODE reduce_nw	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int	minelims
	)

reduce node-weighted Steiner tree problem

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to store the offset value
minelims	minimal number of edges to be eliminated in order to reiterate reductions

Definition at line 1669 of file reduce_base.c.

References reduce_costs_reduction_parameters::damode, extred_none, FALSE, GRAPH::knots, MAX, nnodes, NULL, reduce_da(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcreateRandom(), SCIPfreeBufferArray, SCIPfreeRandom(), SCIPgetRealParam(), SCIPgetTotalTime(), SCIPisStopped(), STP_DAMODE_FAST, and TRUE.

Referenced by reduce_exec().

◆ reduce_dc()

SCIP_RETCODE reduce_dc	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int	minelims
	)

reduce degree constrained Steiner tree problem

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to store the offset value
minelims	minimal number of edges to be eliminated in order to reiterate reductions

Definition at line 1729 of file reduce_base.c.

References reduce_costs_reduction_parameters::damode, extred_none, FALSE, graph_get_nNodes(), MAX, nnodes, reduce_da(), reduce_simple_dc(), reduce_sollocalFree(), reduce_sollocalInit(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcreateRandom(), SCIPfreeRandom(), SCIPgetRealParam(), SCIPgetTotalTime(), SCIPisStopped(), STP_DAMODE_FAST, and TRUE.

Referenced by reduce_exec().

◆ reduce_redLoopStp()

SCIP_RETCODE reduce_redLoopStp	(	SCIP *	scip,
		GRAPH *	g,
		REDBASE *	redbase
	)

STP loop

Parameters

scip	SCIP data structure
g	graph data structure
redbase	parameters

Definition at line 2074 of file reduce_base.c.

References reduce_costs_reduction_parameters::damode, dpterms_isPromisingFully(), extred_fast, extred_full, FALSE, reduction_parameters::fullreduce, graph_typeIsSpgLike(), graph_valid(), graph_valid_ancestors(), reduction_parameters::nodereplacing, NULL, redbaseGetOffsetPointer(), redbaseGetSolnode(), redLoopInnerStp(), reduction_base::redparameters, reduction_base::redsol, reduce_contract0Edges(), reduce_da(), reduce_fixedConflicts(), reduce_simple(), reduce_solFinalizeLocal(), reduce_solInitLocal(), reduce_termsepaFull(), reduceStatsPrint(), reduction_parameters::reductbound, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcreateRandom(), SCIPfreeRandom(), SCIPgetRealParam(), SCIPgetTotalTime(), SCIPisStopped(), SCIPStpEnumRelaxIsPromising(), STP_DAMODE_FAST, STP_DAMODE_MEDIUM, STP_RED_EXPENSIVEFACTOR, TRUE, and reduction_parameters::userec.

Referenced by decomposeReduceSubDoIt(), reduce_stp(), reduceExact(), and SCIPStpHeurPruneRun().

◆ reduce_redLoopPc()

SCIP_RETCODE reduce_redLoopPc	(	SCIP *	scip,
		REDSOL *	redsol,
		GRAPH *	g,
		PATH *	vnoi,
		PATH *	path,
		SCIP_Real *	nodearrreal,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	nodearrint,
		int *	edgearrint,
		int *	nodearrint2,
		STP_Bool *	nodearrchar,
		SCIP_Bool	dualascent,
		SCIP_Bool	bred,
		SCIP_Bool	tryrpc,
		int	reductbound,
		SCIP_Bool	userec,
		SCIP_Bool	nodereplacing,
		SCIP_Bool	usestrongreds
	)

(R)PC loop

Parameters

scip	SCIP data structure
redsol	solution contained
g	graph data structure
vnoi	Voronoi data structure
path	path data structure
nodearrreal	nodes-sized array
heap	shortest path array
state	voronoi base array
vbase	nodes-sized array
nodearrint	node-sized array
edgearrint	edge-sized array
nodearrint2	nodes-sized array
nodearrchar	nodes-sized array
dualascent	do dual-ascent reduction?
bred	do bound-based reduction?
tryrpc	try to transform to rpc?
reductbound	minimal number of edges to be eliminated in order to reiterate reductions
userec	use recombination heuristic?
nodereplacing	should node replacement (by edges) be performed?
usestrongreds	allow strong reductions?

Definition at line 1896 of file reduce_base.c.

References reduce_costs_reduction_parameters::damode, extred_fast, extred_full, FALSE, FARAWAY, graph_heap_create(), graph_heap_free(), graph_pc_2org(), graph_pc_2trans(), graph_pc_getPosPrizeSum(), graph_pc_nNonLeafTerms(), graph_pc_nProperPotentialTerms(), graph_pc_presolExit(), graph_pc_presolInit(), graph_pc_term2edgeIsConsistent(), graph_printInfo(), graph_transPcmw2rooted(), graph_transRpc2SpgTrivial(), GRAPH::knots, NULL, redLoopInnerPc(), reduce_da(), reduce_daPcMw(), reduce_deleteConflictEdges(), reduce_impliedProfitBasedRpc(), reduce_simple_pc(), reduce_solFinalizeLocal(), reduce_solGetOffsetPointer(), reduce_solInitLocal(), reduce_sollocalGetSolnode(), reduce_sollocalRebuildTry(), reduce_sollocalSetOffset(), reduce_unconnectedRpcRmw(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcreateRandom(), SCIPdebugMessage, SCIPfreeRandom(), SCIPgetRealParam(), STP_DAMODE_MEDIUM, STP_RED_GLBFACTOR, STP_RED_MAXNOUTROUNDS_PC, STP_RPCSPG, GRAPH::stp_type, GRAPH::terms, and TRUE.

Referenced by reduce_pc(), reduceExact(), and SCIPStpHeurPruneRun().

◆ reduce_redLoopMw()

SCIP_RETCODE reduce_redLoopMw	(	SCIP *	scip,
		REDSOL *	redsol,
		GRAPH *	g,
		PATH *	vnoi,
		SCIP_Real *	nodearrreal,
		int *	state,
		int *	vbase,
		int *	nodearrint,
		STP_Bool *	nodearrchar,
		STP_Bool	advanced,
		STP_Bool	bred,
		STP_Bool	tryrmw,
		int	redbound,
		SCIP_Bool	userec,
		SCIP_Bool	usestrongreds
	)

MWCS loop

Parameters

scip	SCIP data structure
redsol	solution contained
g	graph data structure
vnoi	Voronoi data structure
nodearrreal	nodes-sized array
state	shortest path array
vbase	voronoi base array
nodearrint	nodes-sized array
nodearrchar	nodes-sized array
advanced	do advanced reduction?
bred	do bound-based reduction?
tryrmw	try to convert problem to RMWCSP? Only possible if advanced = TRUE and userec = TRUE
redbound	minimal number of edges to be eliminated in order to reiterate reductions
userec	use recombination heuristic?
usestrongreds	allow strong reductions?

Definition at line 1771 of file reduce_base.c.

References reduce_costs_reduction_parameters::damode, extred_none, FALSE, graph_pc_2org(), graph_pc_2trans(), graph_pc_getPosPrizeSum(), graph_pc_isRootedPcMw(), graph_pc_term2edgeIsConsistent(), graph_transPcmw2rooted(), redLoopInnerMw(), reduce_da(), reduce_daPcMw(), reduce_simple_mw(), reduce_solFinalizeLocal(), reduce_solGetOffsetPointer(), reduce_solInitLocal(), reduce_sollocalGetSolnode(), reduce_sollocalRebuildTry(), reduce_sollocalSetOffset(), reduce_unconnected(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcreateRandom(), SCIPdebugMessage, SCIPfreeRandom(), SCIPgetRealParam(), SCIPisStopped(), STP_DAMODE_FAST, STP_RED_EXTENSIVE, STP_RED_MWTERMBOUND, GRAPH::terms, and TRUE.

Referenced by reduce_mw(), reduceExact(), and SCIPStpHeurPruneRun().

◆ reduce_exec()

SCIP_RETCODE reduce_exec	(	SCIP *	scip,
		GRAPH *	graph,
		REDSOL *	redsol,
		int	reductionlevel,
		int	minelims,
		SCIP_Bool	userec
	)

reduces the graph

Parameters

scip	SCIP data structure
graph	graph structure
redsol	primal solution container
reductionlevel	reduction level 0: none, 1: basic, 2: advanced
minelims	minimal amount of reductions to reiterate reduction methods
userec	use recombination heuristic?

Definition at line 2192 of file reduce_base.c.

References EQ, FALSE, graph_getFixedges(), graph_initHistory(), graph_isSetUp(), graph_path_exists(), graph_path_exit(), graph_path_init(), graph_typeIsSpgLike(), graph_valid(), NULL, reduce_articulations(), reduce_dc(), reduce_hc(), reduce_mw(), reduce_nw(), reduce_pc(), reduce_sap(), reduce_solGetOffsetPointer(), reduce_solReInitLocal(), reduce_stp(), reduce_unconnected(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, STP_BRMWCSP, STP_DCSTP, STP_DHCSTP, STP_MWCSP, STP_NWPTSPG, STP_NWSPG, STP_PCSPG, STP_REDUCTION_ADVANCED, STP_REDUCTION_BASIC, STP_REDUCTION_NONE, STP_RMWCSP, STP_RPCSPG, STP_SAP, STP_SPG, GRAPH::stp_type, and TRUE.

Referenced by graph_writeReductionRatioStatsLive(), presolveStp(), SCIPStpHeurRecExclude(), and SCIPStpHeurRecRun().

◆ reduce_sollocalInit()

SCIP_RETCODE reduce_sollocalInit	(	SCIP *	scip,
		const GRAPH *	g,
		REDSOLLOCAL **	sollocal
	)

initializes

Parameters

scip	SCIP data structure
g	graph data structure
sollocal	to initialize

Definition at line 447 of file reduce_sol.c.

References FALSE, FARAWAY, graph_get_nNodes(), graph_pc_isPcMw(), reduction_local_solution_storage::isPcMw, reduction_local_solution_storage::nnodes, reduction_local_solution_storage::nodesol, reduction_local_solution_storage::nodesol_ub, reduction_local_solution_storage::nodesol_use, NULL, reduction_local_solution_storage::offset, reduction_local_solution_storage::primalbound, REDSOLVAL_UNSET, SCIP_CALL, SCIP_OKAY, and SCIPallocMemory.

Referenced by redlevelAddLocal(), reduce_dc(), and reduce_hc().

◆ reduce_sollocalFree()

void reduce_sollocalFree	(	SCIP *	scip,
		REDSOLLOCAL **	sollocal
	)

frees

Parameters

scip	SCIP data structure
sollocal	to free

Definition at line 472 of file reduce_sol.c.

References SCIPfreeMemory, and SCIPfreeMemoryArrayNull.

Referenced by redlevelFree(), reduce_dc(), reduce_hc(), and reduce_solFinalizeLocal().

◆ reduce_sollocalGetSolnode()

int* reduce_sollocalGetSolnode ( REDSOLLOCAL * sollocal )

gets array

Parameters

sollocal sollocal

Definition at line 651 of file reduce_sol.c.

References reduction_local_solution_storage::nodesol, NULL, and reduce_sollocalUsesNodesol().

Referenced by redbaseGetSolnode(), redlevelGetNodesol(), redLoopInnerMw(), redLoopInnerPc(), reduce_impliedProfitBasedRpc(), reduce_redLoopMw(), and reduce_redLoopPc().

◆ reduce_sollocalSetOffset()

void reduce_sollocalSetOffset	(	SCIP_Real	offsetnew,
		REDSOLLOCAL *	sollocal
	)

sets offset NOTE: offset is only used within this structure!

Parameters

offsetnew	new offset
sollocal	sollocal

Definition at line 488 of file reduce_sol.c.

References EQ, FARAWAY, GE, reduction_local_solution_storage::isPcMw, reduction_local_solution_storage::offset, reduction_local_solution_storage::primalbound, and SCIPdebugMessage.

Referenced by redLoopInnerMw(), redLoopInnerPc(), redLoopInnerStp(), reduce_da(), reduce_impliedProfitBasedRpc(), reduce_redLoopMw(), reduce_redLoopPc(), reduce_solFinalizeLocal(), and reduce_solLevelTopFinalize().

◆ reduce_sollocalUpdateUpperBound()

void reduce_sollocalUpdateUpperBound	(	SCIP_Real	ubnew,
		REDSOLLOCAL *	sollocal
	)

sets new sollocal bound if better than old one

Parameters

ubnew	new upper bound, not including offset!
sollocal	sollocal

Definition at line 610 of file reduce_sol.c.

References FARAWAY, GE, LE, reduction_local_solution_storage::offset, reduction_local_solution_storage::primalbound, SCIP_Real, and SCIPdebugMessage.

Referenced by reduce_da(), reduce_daPcMw(), reduce_solFinalizeLocal(), and reduce_solLevelTopFinalize().

◆ reduce_sollocalUpdateNodesol()

SCIP_RETCODE reduce_sollocalUpdateNodesol	(	SCIP *	scip,
		const int *	edgesol,
		GRAPH *	g,
		REDSOLLOCAL *	sollocal
	)

updates

Parameters

scip	SCIP data structure
edgesol	incoming solution
g	graph data structure
sollocal	sollocal

Definition at line 565 of file reduce_sol.c.

References EQ, FARAWAY, graph_get_nNodes(), LT, reduction_local_solution_storage::nnodes, reduction_local_solution_storage::nodesol, reduction_local_solution_storage::nodesol_ub, nodesolUpdate(), REDSOLVAL_UNSET, reduce_sollocalUsesNodesol(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, solstp_getObj(), solstp_isValid(), and solstp_setVertexFromEdgeConn().

Referenced by reduce_da(), and reduce_daPcMw().

◆ reduce_sollocalGetUpperBound()

SCIP_Real reduce_sollocalGetUpperBound ( const REDSOLLOCAL * sollocal )

gets upper bound; not including (last set) offset

Parameters

sollocal sollocal

Definition at line 633 of file reduce_sol.c.

References EQ, FARAWAY, GE_FEAS, MAX, reduction_local_solution_storage::offset, reduction_local_solution_storage::primalbound, and SCIPdebugMessage.

Referenced by redLoopInnerStp(), reduce_da(), reduce_daPcMw(), and reduce_impliedProfitBasedRpc().

◆ reduce_sollocalGetUpperBoundWithOffset()

SCIP_Real reduce_sollocalGetUpperBoundWithOffset ( const REDSOLLOCAL * sollocal )

gets upper bound; including (last set) offset

Parameters

sollocal sollocal

Definition at line 664 of file reduce_sol.c.

References reduction_local_solution_storage::primalbound.

Referenced by reduce_solFinalizeLocal().

◆ reduce_sollocalHasUpperBound()

SCIP_Bool reduce_sollocalHasUpperBound ( const REDSOLLOCAL * sollocal )

do we have a (non-trivial) primal bound?

Parameters

sollocal sollocal

Definition at line 675 of file reduce_sol.c.

References EQ, FARAWAY, LE, and reduction_local_solution_storage::primalbound.

Referenced by reduce_solFinalizeLocal().

◆ reduce_sollocalUsesNodesol()

SCIP_Bool reduce_sollocalUsesNodesol ( const REDSOLLOCAL * sollocal )

updates

Parameters

sollocal sollocal

Definition at line 554 of file reduce_sol.c.

References reduction_local_solution_storage::nodesol_use.

Referenced by redbaseGetSolnode(), reduce_da(), reduce_daPcMw(), reduce_sollocalGetSolnode(), and reduce_sollocalUpdateNodesol().

◆ reduce_sollocalRebuildTry()

SCIP_RETCODE reduce_sollocalRebuildTry	(	SCIP *	scip,
		GRAPH *	g,
		REDSOLLOCAL *	sollocal
	)

tries to rebuild solnode if possible and necessary

Parameters

scip	SCIP data structure
g	graph
sollocal	sollocal

Definition at line 507 of file reduce_sol.c.

References EQ, GRAPH::extended, FARAWAY, GE, graph_pc_2org(), graph_pc_2trans(), graph_pc_getNonLeafTermOffset(), graph_pc_isPc(), graph_pc_isPcMw(), GT, GRAPH::knots, reduction_local_solution_storage::nnodes, reduction_local_solution_storage::nodesol, reduction_local_solution_storage::nodesol_ub, nodesolUpdate(), reduction_local_solution_storage::offset, reduction_local_solution_storage::primalbound, REDSOLVAL_UNSET, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, and GRAPH::terms.

Referenced by redLoopInnerMw(), redLoopInnerPc(), reduce_da(), reduce_impliedProfitBasedRpc(), reduce_redLoopMw(), and reduce_redLoopPc().

◆ reduce_solInit()

SCIP_RETCODE reduce_solInit	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Bool	useNodeSol,
		REDSOL **	redsol
	)

initializes

Parameters

scip	SCIP data structure
g	graph data structure
useNodeSol	should solution be used? (additionally to solution value)
redsol	to be initialized

Definition at line 687 of file reduce_sol.c.

References graph_pc_isPcMw(), GRAPH::knots, reduction_solution_level::nodesol_use, NULL, redlevelInit(), redsolGetNlevels(), SCIP_CALL, SCIP_OKAY, SCIPallocMemory, and StpVecPushBack.

Referenced by fixVarsRedbased(), graph_writeReductionRatioStatsLive(), reduceExact(), SCIPprobdataCreateFromGraph(), SCIPStpHeurPruneRun(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), testBiconnectedDecomposition(), testBiconnectedDecomposition2(), and testBiconnectedDecomposition3().

◆ reduce_solFree()

void reduce_solFree	(	SCIP *	scip,
		REDSOL **	redsol
	)

frees

Parameters

scip	SCIP data structure
redsol	to be freed

Definition at line 818 of file reduce_sol.c.

References redlevelFree(), SCIPfreeMemory, StpVecFree, StpVecGetSize, StpVecIsEmpty, and StpVecPopBack.

Referenced by fixVarsRedbased(), graph_writeReductionRatioStatsLive(), reduceExact(), SCIPprobdataCreateFromGraph(), SCIPStpHeurPruneRun(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), testBiconnectedDecomposition(), testBiconnectedDecomposition2(), and testBiconnectedDecomposition3().

◆ reduce_solInitLocal()

SCIP_RETCODE reduce_solInitLocal	(	SCIP *	scip,
		const GRAPH *	g,
		REDSOL *	redsol,
		REDSOLLOCAL **	redsollocal_out
	)

adds local for given level; call before reduction loop

Parameters

scip	SCIP data structure
g	graph data structure
redsol	reduction solution
redsollocal_out	pointer to newly initialized local

Definition at line 717 of file reduce_sol.c.

References redlevelAddLocal(), redsolGetNlevels(), SCIP_CALL, and SCIP_OKAY.

Referenced by reduce_redLoopMw(), reduce_redLoopPc(), reduce_redLoopStp(), testBiconnectedDecomposition(), testBiconnectedDecomposition2(), and testBiconnectedDecomposition3().

◆ reduce_solFinalizeLocal()

void reduce_solFinalizeLocal	(	SCIP *	scip,
		const GRAPH *	g,
		REDSOL *	redsol
	)

finalizes local for given level; call after reduction loop

Parameters

scip	SCIP data structure
g	graph data structure
redsol	reduction solution

Definition at line 735 of file reduce_sol.c.

References EQ, FARAWAY, reduction_local_solution_storage::nodesol, reduction_solution_level::nodesol, reduction_local_solution_storage::nodesol_ub, reduction_solution_level::nodesol_ub, reduction_local_solution_storage::nodesol_use, nodesolSetTrivial(), NULL, reduction_local_solution_storage::offset, redsolGetNlevels(), redsolGetTopLevel(), reduction_solution_level::redsollocal, REDSOLVAL_UNSET, reduce_solGetOffset(), reduce_sollocalFree(), reduce_sollocalGetUpperBoundWithOffset(), reduce_sollocalHasUpperBound(), reduce_sollocalSetOffset(), reduce_sollocalUpdateUpperBound(), SCIP_CALL_ABORT, SCIP_Real, reduction_solution_level::solval_postred, and GRAPH::terms.

Referenced by reduce_redLoopMw(), reduce_redLoopPc(), reduce_redLoopStp(), testBiconnectedDecomposition(), testBiconnectedDecomposition2(), and testBiconnectedDecomposition3().

◆ reduce_solReInitLocal()

void reduce_solReInitLocal	(	const GRAPH *	g,
		REDSOL *	redsol
	)

reinitalizes local after it has been finished

Parameters

g	graph data structure
redsol	reduction solution

Definition at line 793 of file reduce_sol.c.

References GRAPH::knots, reduction_solution_level::nnodes, reduction_solution_level::nodesol, reduction_solution_level::nodesol_transfer, reduction_solution_level::nodesol_ub, NULL, redsolGetTopLevel(), REDSOLVAL_UNSET, and reduction_solution_level::solval_postred.

Referenced by reduce_exec().

◆ reduce_solPack()

void reduce_solPack	(	const GRAPH *	g,
		const int *	nodes_old2packed,
		int	nnodes_packed,
		REDSOL *	redsol
	)

packs solution

Parameters

g	graph data structure
nodes_old2packed	map to packed node IDs
nnodes_packed	number of packed nodes
redsol	sollocal

Definition at line 846 of file reduce_sol.c.

References graph_get_nNodes(), graph_pc_isPcMw(), reduction_local_solution_storage::nnodes, reduction_solution_level::nnodes, reduction_local_solution_storage::nodesol, and reduction_solution_level::nodesol.

Referenced by graph_pack().

◆ reduce_solLevelAdd()

SCIP_RETCODE reduce_solLevelAdd	(	SCIP *	scip,
		const GRAPH *	g,
		REDSOL *	redsol
	)

adds level

Parameters

scip	SCIP data structure
g	graph data structure
redsol	sollocal

Definition at line 897 of file reduce_sol.c.

References EQ, reduction_solution_level::nodesol_use, redlevelInit(), redlevelInitIncomplete(), redsolGetNlevels(), redsolGetTopLevel(), SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, and StpVecPushBack.

Referenced by decomposeReduce().

◆ reduce_solLevelTopUpdate()

SCIP_RETCODE reduce_solLevelTopUpdate	(	SCIP *	scip,
		const GRAPH *	subgraph,
		REDSOL *	redsol
	)

initializes level with given (sub) graph

Parameters

scip	SCIP data structure
subgraph	graph data structure
redsol	reduction solution

Definition at line 922 of file reduce_sol.c.

References graph_get_nNodes(), reduction_local_solution_storage::nnodes, reduction_solution_level::nnodes, redlevelIsClean(), redsolGetTopLevel(), and SCIP_OKAY.

Referenced by decomposeReduceSubDoIt().

◆ reduce_solLevelTopFinalize()

void reduce_solLevelTopFinalize	(	SCIP *	scip,
		GRAPH *	g,
		REDSOL *	redsol
	)

finalizes top level; also removes the level!

Parameters

scip	SCIP data structure
g	graph data structure
redsol	sollocal

Definition at line 956 of file reduce_sol.c.

References redlevelFree(), redsolGetNlevels(), redsolGetTopLevel(), reduction_solution_level::redsollocal, reduce_sollocalSetOffset(), reduce_sollocalUpdateUpperBound(), SCIPdebugMessage, reduction_solution_level::solval_incomplete, and StpVecPopBack.

Referenced by decomposeReduce().

◆ reduce_solLevelTopRemove()

void reduce_solLevelTopRemove	(	SCIP *	scip,
		REDSOL *	redsol
	)

removes top level

Parameters

scip	SCIP data structure
redsol	reduction solution

Definition at line 940 of file reduce_sol.c.

References redlevelFree(), redsolGetNlevels(), and StpVecPopBack.

◆ reduce_solLevelTopClean()

void reduce_solLevelTopClean	(	SCIP *	scip,
		REDSOL *	redsol
	)

removes level

Parameters

scip	SCIP data structure
redsol	sollocal

Definition at line 997 of file reduce_sol.c.

References redlevelClean(), and redsolGetNlevels().

Referenced by decomposeReduceSubDoIt().

◆ reduce_solLevelTopTransferSolBack()

void reduce_solLevelTopTransferSolBack	(	const int *	nodemap_subToOrg,
		REDSOL *	redsol
	)

merges level up

Parameters

nodemap_subToOrg	map
redsol	sollocal

Definition at line 1010 of file reduce_sol.c.

References CONNECT, EQ, FARAWAY, GE, GT, MAX, reduction_local_solution_storage::nnodes, reduction_solution_level::nnodes, reduction_local_solution_storage::nodesol_ub, reduction_solution_level::nodesol_ub, reduction_solution_level::nodesol_use, redlevelGetNodesol(), redsolGetNlevels(), redsolGetTopLevel(), redsolGetTopParentLevel(), reduction_solution_level::redsollocal, REDSOLVAL_UNSET, SCIPdebugMessage, reduction_solution_level::solval_incomplete, reduction_solution_level::solval_postred, and UNKNOWN.

Referenced by decomposeReduceSubDoIt().

◆ reduce_solLevelTopTransferSolTo()

SCIP_RETCODE reduce_solLevelTopTransferSolTo	(	const int *	nodemap_orgToTop,
		REDSOL *	redsol
	)

transfers solution from parent to top level

Parameters

nodemap_orgToTop	map
redsol	sollocal

Definition at line 1067 of file reduce_sol.c.

References reduction_solution_level::nnodes, reduction_solution_level::nodesol_transfer, reduction_solution_level::nodesol_use, redlevelGetNodesol(), redsolGetTopLevel(), redsolGetTopParentLevel(), reduction_solution_level::redsollocal, SCIP_CALL, SCIP_OKAY, and SCIPallocMemoryArray.

Referenced by decomposeReduceSubDoIt().

◆ reduce_solSetOffset()

void reduce_solSetOffset	(	SCIP_Real	offsetnew,
		REDSOL *	redsol
	)

sets offset

Parameters

offsetnew	new offset
redsol	solution

Definition at line 1124 of file reduce_sol.c.

References GE.

Referenced by decomposeReduceSubDoIt().

◆ reduce_solGetOffset()

SCIP_Real reduce_solGetOffset ( const REDSOL * redsol )

gets

Parameters

redsol solution

Definition at line 1137 of file reduce_sol.c.

Referenced by decomposeReduceSubDoIt(), fixVarsRedbased(), reduce_solFinalizeLocal(), reduce_stp(), reduceExact(), SCIPprobdataCreateFromGraph(), and SCIPStpHeurPruneRun().

◆ reduce_solGetUpperBoundWithOffset()

SCIP_Real reduce_solGetUpperBoundWithOffset ( const REDSOL * redsol )

gets

Parameters

redsol solution

Definition at line 1263 of file reduce_sol.c.

References EQ, FARAWAY, redsolGetNlevels(), REDSOLVAL_UNSET, SCIP_Real, and reduction_solution_level::solval_postred.

Referenced by presolveStp(), testBiconnectedDecomposition(), testBiconnectedDecomposition2(), and testBiconnectedDecomposition3().

◆ reduce_solGetNodesolPointer()

const int* reduce_solGetNodesolPointer ( const REDSOL * redsol )

gets

Parameters

redsol solution

Definition at line 1248 of file reduce_sol.c.

References reduction_solution_level::nodesol, redsolGetNlevels(), redsolGetTopLevel(), and reduce_solUsesNodesol().

◆ reduce_solUsesNodesol()

SCIP_Bool reduce_solUsesNodesol ( const REDSOL * redsol )

is node solution in use?

Parameters

redsol solution

Definition at line 1236 of file reduce_sol.c.

Referenced by computeReducedProbSolution(), redbaseGetSolnode(), and reduce_solGetNodesolPointer().

◆ reduce_solGetOffsetPointer()

SCIP_Real* reduce_solGetOffsetPointer ( REDSOL * redsol )

gets

Parameters

redsol solution

Definition at line 1285 of file reduce_sol.c.

Referenced by decomposeExactFixSol(), graph_pack(), redbaseGetOffsetPointer(), reduce_bidecomposition(), reduce_bidecompositionExact(), reduce_exec(), reduce_redLoopMw(), reduce_redLoopPc(), and sepafullReduceFromSols().

◆ reduce_solGetEdgesol()

SCIP_RETCODE reduce_solGetEdgesol	(	SCIP *	scip,
		GRAPH *	g,
		REDSOL *	redsol,
		SCIP_Real *	solval,
		int *	edgesol
	)

gets edge solution, if available, and solution value

Parameters

scip	SCIP data structure
g	graph data structure
redsol	solution
solval	FARAWAY if no solution available
edgesol	solution array to be filled

Definition at line 1197 of file reduce_sol.c.

References FARAWAY, graph_get_nNodes(), GRAPH::knots, LT, reduction_local_solution_storage::nnodes, reduction_solution_level::nodesol, reduction_solution_level::nodesol_ub, nodesolGetEdgeSol(), nodesolUpdate(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, and SCIPfreeBufferArray.

Referenced by addRedsol(), and computeReducedProbSolution().

◆ reduce_solAddNodesol()

SCIP_RETCODE reduce_solAddNodesol	(	const GRAPH *	g,
		const int *	nodesol,
		REDSOL *	redsol
	)

adds (and possibly overwrites) nodesol

Parameters

g	graph data structure
nodesol	incoming solution
redsol	solution

Definition at line 1150 of file reduce_sol.c.

References BMScopyMemoryArray, GRAPH::knots, reduction_solution_level::nnodes, reduction_solution_level::nodesol_transfer, reduction_solution_level::nodesol_ub, redsolGetNlevels(), SCIP_CALL, SCIP_OKAY, and SCIPallocMemoryArray.

Referenced by reduceExact(), and SCIPStpHeurPruneRun().

◆ reduce_solGetNodesol()

void reduce_solGetNodesol	(	const GRAPH *	g,
		REDSOL *	redsol,
		int *	nodesol
	)

gets

Parameters

g	graph data structure
redsol	solution
nodesol	solution array to be filled

Definition at line 1176 of file reduce_sol.c.

References BMScopyMemoryArray, GRAPH::knots, reduction_solution_level::nnodes, reduction_solution_level::nodesol, and redsolGetNlevels().

Referenced by reduceExact(), and SCIPStpHeurPruneRun().

◆ reduce_impliedProfitBased()

SCIP_RETCODE reduce_impliedProfitBased	(	SCIP *	scip,
		int	edgelimit,
		GRAPH *	g,
		int *	solnode,
		SCIP_Real *	fixed,
		int *	nelims
	)

Combined implied-profit based tests: First elimination tests are used, afterwards edge contraction test are applied. NOTE: The expensive part is to build the bottleneck distances, thus we always apply all other tests.

Parameters

scip	SCIP data structure
edgelimit	limit for star test
g	graph structure
solnode	node array to mark whether an node is part of a given solution (CONNECT)
fixed	offset pointer
nelims	number of eliminations

Definition at line 2609 of file reduce_alt.c.

References special_distance_storage::blctree, FALSE, graph_pc_isPcMw(), graph_tpathsRecomputeBiased(), reduce_nsvImplied(), reduce_sdBiased(), reduce_sdFree(), reduce_sdInitBiasedBottleneck(), reduce_sdprofitBuildFromBLC(), reduce_sdStarBiasedWithProfit(), reduce_unconnected(), reduce_unconnectedRpcRmw(), SCIP_CALL, SCIP_OKAY, nearest_special_distance_test_data::sdistance, special_distance_storage::sdprofit, special_distance_storage::terminalpaths, GRAPH::terms, and TRUE.

Referenced by redLoopInnerStp().

◆ reduce_impliedProfitBasedRpc()

SCIP_RETCODE reduce_impliedProfitBasedRpc	(	SCIP *	scip,
		GRAPH *	g,
		REDSOLLOCAL *	redsollocal,
		SCIP_Real *	fixed,
		int *	nelims
	)

similar to above, but for rooted-prize collecting Steiner tree problem

Parameters

scip	SCIP data structure
g	graph structure
redsollocal	primal bound info
fixed	offset pointer
nelims	number of eliminations

Definition at line 2664 of file reduce_alt.c.

References special_distance_storage::blctree, GRAPH::cost, EAT_FREE, GRAPH::edges, FALSE, FARAWAY, GE, graph_edge_del(), graph_edge_isInRange(), graph_edge_printInfo(), graph_free(), graph_mark(), graph_path_exit(), graph_path_init(), graph_pc_contractEdge(), graph_pc_knotIsFixedTerm(), graph_pc_knotIsPropPotTerm(), graph_tpathsRecomputeBiased(), graph_transRpcGetSpg(), graph_transRpcToSpgIsStable(), graph_valid(), GRAPH::head, Is_term, NULL, GRAPH::oeat, reduce_nsvImpliedRecord(), reduce_sdBiased(), reduce_sdFree(), reduce_sdInitBiasedBottleneck(), reduce_sdprofitBuildFromBLC(), reduce_sollocalGetSolnode(), reduce_sollocalGetUpperBound(), reduce_sollocalRebuildTry(), reduce_sollocalSetOffset(), reduce_unconnectedRpcRmw(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPfreeMemoryArray, nearest_special_distance_test_data::sdistance, special_distance_storage::sdprofit, GRAPH::source, STP_RPCSPG, GRAPH::stp_type, STP_Vectype, StpVecFree, StpVecGetSize, GRAPH::tail, GRAPH::term, special_distance_storage::terminalpaths, GRAPH::terms, and TRUE.

Referenced by reduce_redLoopPc().

◆ reduce_ans()

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

adjacent neighbourhood reduction for the MWCSP

Parameters

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

Definition at line 1470 of file reduce_alt.c.

References ansProcessCandidate(), ansUnmark(), EAT_LAST, FALSE, GRAPH::grad, graph_get_nNodes(), graph_mark(), graph_pc_isMw(), graph_pc_knotIsDummyTerm(), graph_valid(), GRAPH::head, Is_term, LT, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, STP_RED_ANSMAXNEIGHBORS, GRAPH::term, and TRUE.

Referenced by redLoopInnerMw(), testRmwAnsDeletesOneEdge(), testRmwAnsDeletesOneNode(), and testRmwAnsDeletesTwoNodes().

◆ reduce_ansAdv()

SCIP_RETCODE reduce_ansAdv	(	SCIP *	scip,
		GRAPH *	g,
		int *	nelims,
		SCIP_Bool	extneigbhood
	)

advanced adjacent neighbourhood reduction for the MWCSP

Parameters

scip	SCIP data structure
g	graph data structure
nelims	pointer to number of performed reductions
extneigbhood	use extended neighbour hood

Definition at line 1544 of file reduce_alt.c.

References ansProcessCandidate(), ansUnmark(), EAT_LAST, FALSE, GRAPH::grad, graph_get_nNodes(), graph_pc_isMw(), graph_pc_knotIsDummyTerm(), graph_valid(), GRAPH::head, Is_term, GRAPH::mark, MAX, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisGT(), SCIPisLE(), STP_RED_ANSEXMAXCANDS, STP_RED_ANSMAXCANDS, STP_RED_CNSNN, GRAPH::term, and TRUE.

Referenced by redLoopInnerMw().

◆ reduce_ansAdv2()

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

alternative advanced adjacent neighbourhood reduction for the MWCSP

Parameters

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

Definition at line 1656 of file reduce_alt.c.

References ansProcessCandidate(), ansUnmark(), EAT_LAST, FALSE, GRAPH::grad, graph_get_nNodes(), graph_pc_isMw(), graph_pc_knotIsDummyTerm(), graph_valid(), GT, GRAPH::head, Is_term, LT, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisGE(), SCIPisLE(), STP_RED_CNSNN, GRAPH::term, TRUE, UNKNOWN, and VERTEX_NEIGHBOR.

Referenced by redLoopInnerMw().

◆ reduce_nnp()

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

non-negative path reduction for the MWCSP

Parameters

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

Definition at line 2534 of file reduce_alt.c.

References EAT_LAST, FALSE, graph_edge_del(), graph_get_nNodes(), graph_pc_isMw(), graph_valid(), GRAPH::head, LT, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, and TRUE.

Referenced by redLoopInnerMw().

◆ reduce_nv()

SCIP_RETCODE reduce_nv	(	SCIP *	,
		GRAPH *	,
		PATH *	,
		SCIP_Real *	,
		int *	,
		int *	,
		int *	,
		int *
	)

Definition at line 932 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, FARAWAY, GRAPH::grad, graph_knot_contractFixed(), graph_pc_contractEdge(), graph_voronoiWithDist(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPisGE(), SCIPisLE(), GRAPH::source, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, and UNKNOWN.

◆ reduce_nvAdv()

SCIP_RETCODE reduce_nvAdv	(	SCIP *	,
		const int *	,
		GRAPH *	,
		PATH *	,
		SCIP_Real *	,
		SCIP_Real *	,
		int *	,
		int *	,
		int *	,
		int *	,
		int *
	)

Definition at line 1121 of file reduce_alt.c.

References BMSclearMemoryArray, GRAPH::cost, shortest_path::dist, EAT_LAST, EDGE_BLOCKED, GRAPH::extended, FALSE, FARAWAY, flipedge, GE, GRAPH::grad, graph_edge_del(), graph_get_nNodes(), graph_get_nTerms(), graph_getIsTermArray(), graph_knot_contractFixed(), graph_mark(), graph_pc_contractEdge(), graph_pc_knotIsNonLeafTerm(), graph_voronoiWithDist(), GRAPH::head, Is_term, GRAPH::knots, LE, GRAPH::mark, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisGE(), SCIPisLE(), SCIPisLT(), GRAPH::source, STP_PCSPG, STP_RPCSPG, STP_SPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

Referenced by execNvSl().

◆ reduce_sl()

SCIP_RETCODE reduce_sl	(	SCIP *	scip,
		const int *	edgestate,
		GRAPH *	g,
		PATH *	vnoi,
		SCIP_Real *	fixed,
		int *	vbase,
		int *	vrnodes,
		STP_Bool *	visited,
		int *	solnode,
		int *	nelims
	)

shortest link reduction

Parameters

scip	SCIP data structure
edgestate	for propagation or NULL
g	graph data structure
vnoi	Voronoi data structure
fixed	offset pointer
vbase	Voronoi/shortest path bases array
vrnodes	Voronoi/shortest path array
visited	Voronoi/shortest path array
solnode	node array to mark whether an node is part of a given solution (CONNECT), or NULL
nelims	pointer to store number of eliminations

Definition at line 665 of file reduce_alt.c.

References BMSclearMemoryArray, GRAPH::cost, shortest_path::dist, EAT_LAST, EDGE_BLOCKED, EQ, FALSE, FARAWAY, GE, GRAPH::grad, graph_edge_printInfo(), graph_getIsTermArray(), graph_knot_chg(), graph_knot_contractFixed(), graph_mark(), graph_pc_contractEdge(), graph_pc_isPc(), graph_pc_isUnrootedPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_knotIsNonLeafTerm(), graph_pc_knotToFixedTerm(), graph_voronoiTerms(), GRAPH::head, Is_anyTerm, Is_pseudoTerm, GRAPH::knots, LE, LT, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPfreeBufferArray, SCIPisGE(), SCIPisLE(), SCIPisLT(), GRAPH::source, STP_RPCSPG, STP_TERM, GRAPH::stp_type, STP_Vectype, StpVecFree, StpVecGetSize, StpVecPopBack, StpVecPushBack, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by execNvSl().

◆ reduce_nsvImplied()

SCIP_RETCODE reduce_nsvImplied	(	SCIP *	scip,
		const SD *	sdistance,
		GRAPH *	g,
		int *	solnode,
		SCIP_Real *	fixed,
		int *	nelims
	)

implied version of NSV test

Parameters

scip	SCIP data structure
sdistance	special distances storage
g	graph structure
solnode	node array to mark whether an node is part of a given solution (CONNECT)
fixed	offset pointer
nelims	number of eliminations

Definition at line 621 of file reduce_alt.c.

References nsvExec(), nsvFreeData(), nsvInitData(), SCIP_CALL, and SCIP_OKAY.

Referenced by reduce_impliedProfitBased(), testNsvImpliedContractsCutDistEdge(), testNsvImpliedContractsCutDistMiddleEdge(), testNsvImpliedContractsEdge(), testNsvImpliedContractsEdge2(), and testNsvImpliedContractsImpliedToTermEdge().

◆ reduce_nsvImpliedRecord()

SCIP_RETCODE reduce_nsvImpliedRecord	(	SCIP *	scip,
		const SD *	sdistance,
		GRAPH *	g,
		STP_Vectype(int) *	edgerecord
	)

implied version of NSV test. Does not perform the reductions, but rather records them

Parameters

scip	SCIP data structure
sdistance	special distances storage
g	graph structure
edgerecord	keeps number edges

Definition at line 643 of file reduce_alt.c.

References nsvExec(), nsvFreeData(), nsvInitData(), nsvInitRecording(), NULL, SCIP_CALL, and SCIP_OKAY.

Referenced by reduce_impliedProfitBasedRpc().

◆ reduce_cnsAdv()

SCIP_RETCODE reduce_cnsAdv	(	SCIP *	scip,
		GRAPH *	g,
		int *	marked,
		int *	count
	)

advanced connected neighborhood subset reduction test for the MWCSP

Parameters

scip	SCIP data structure
g	graph data structure
marked	nodes array for internal use
count	pointer to number of reductions

Definition at line 1793 of file reduce_alt.c.

References EAT_LAST, FALSE, GE, GRAPH::grad, graph_edge_del(), graph_get_nNodes(), GRAPH::head, Is_term, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_OKAY, SCIP_Real, SCIPisGE(), SCIPisGT(), SCIPisLE(), STP_MWCSP, STP_RED_CNSNN, GRAPH::stp_type, GRAPH::term, TRUE, UNKNOWN, VERTEX_CONNECT, VERTEX_NEIGHBOR, VERTEX_OTHER, and VERTEX_TEMPNEIGHBOR.

◆ reduce_npv()

SCIP_RETCODE reduce_npv	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	pathtail,
		int *	heap,
		int *	statetail,
		int *	statehead,
		int *	nelims,
		int	limit
	)

non-positive vertex reduction for the MWCSP

Definition at line 2067 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_edge_add(), graph_edge_del(), graph_free(), graph_get_nNodes(), graph_init(), graph_knot_add(), graph_knot_del(), graph_mark(), graph_path_exec(), graph_path_exit(), graph_path_init(), GRAPH::head, Is_term, GRAPH::mark, MST_MODE, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, reduce_getSdByPaths(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisGE(), SCIPisGT(), SCIPisLE(), GRAPH::term, TRUE, and UNKNOWN.

Referenced by redLoopInnerMw(), and testRmwNpv3DeletesNode().

◆ reduce_chain2()

SCIP_RETCODE reduce_chain2	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	pathtail,
		int *	heap,
		int *	statetail,
		int *	statehead,
		int *	nelims,
		int	limit
	)

chain reduction (NPV_2) for the MWCSP

Definition at line 2445 of file reduce_alt.c.

References shortest_path::dist, shortest_path::edge, FALSE, FARAWAY, GRAPH::grad, graph_edge_del(), graph_get_nNodes(), GRAPH::head, Is_term, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, reduce_getSdByPaths(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisGE(), GRAPH::term, TRUE, and UNKNOWN.

Referenced by redLoopInnerMw(), and testRmwChain2DeletesNode().

◆ reduce_sdEdgeCliqueStar()

SCIP_RETCODE reduce_sdEdgeCliqueStar	(	SCIP *	scip,
		int	edgelimit,
		GRAPH *	g,
		int *	nelims
	)

SD test

Parameters

scip	SCIP data structure
edgelimit	edge limit
g	graph data structure
nelims	number of eliminations

Definition at line 2939 of file reduce_sd.c.

References GRAPH::cost, special_distance_clique::dijkdata, EAT_LAST, dijkstra_data::edgelimit, FARAWAY, graph_dijkLimited_clean(), graph_dijkLimited_free(), graph_dijkLimited_init(), graph_dijkLimited_reset(), graph_edge_del(), graph_edge_printInfo(), graph_get_nNodes(), graph_mark(), graph_sdComputeCliqueStar(), GRAPH::head, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, reduce_sdprofitFree(), reduce_sdprofitInit(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisLT(), and TRUE.

Referenced by testSdCliqueStarDeletesEdge().

◆ reduce_sdImpLongEdge()

SCIP_RETCODE reduce_sdImpLongEdge	(	SCIP *	scip,
		const int *	edgestate,
		GRAPH *	g,
		SD *	sdistance,
		int *	nelims
	)

long edge implied special distance test

Parameters

scip	SCIP data structure
edgestate	array to store status of (directed) edge (for propagation, can otherwise be set to NULL)
g	graph data structure
sdistance	special distances storage
nelims	point to store number of deleted edges

Definition at line 1421 of file reduce_sd.c.

References GRAPH::cost, deleteEdge(), EAT_LAST, EDGE_BLOCKED, FALSE, graph_edge_del(), graph_edge_printInfo(), graph_get_nNodes(), special_distance_storage::hasNeigborUpdate, GRAPH::head, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, reduce_sdgraphGetMaxCost(), reduce_sdgraphGetMstHalfMark(), reduce_sdgraphHasMstHalfMark(), reduce_sdneighborGetBlocked(), reduce_unconnected(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGE(), SCIPisGT(), special_distance_storage::sdgraph, special_distance_storage::sdneighbors, and TRUE.

Referenced by reduce_sdBiased(), and reduce_sdBiasedNeighbor().

◆ reduce_sdsp()

SCIP_RETCODE reduce_sdsp	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	pathtail,
		int *	heap,
		int *	statetail,
		int *	statehead,
		int *	memlbltail,
		int *	memlblhead,
		int *	nelims,
		int	limit,
		SCIP_Bool	usestrongreds
	)

SD test using only limited Dijkstra from both endpoints of an edge

Parameters

scip	SCIP data structure
g	graph data structure
pathtail	path tails
heap	heap
statetail	tails
statehead	heads
memlbltail	to save changed tails
memlblhead	to save changed heads
nelims	number of eliminations
limit	limit for number checks
usestrongreds	allow strong reductions?

Definition at line 4020 of file reduce_sd.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::extended, FALSE, FARAWAY, GRAPH::grad, graph_edge_del(), graph_get_nNodes(), graph_path_PcMwSd(), graph_sdPaths(), graph_valid(), GRAPH::head, Is_term, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPisEQ(), SCIPisGE(), SCIPisGT(), SCIPisNegative(), SCIPisPositive(), STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.

Referenced by redLoopInnerStp().

◆ reduce_sdStar()

SCIP_RETCODE reduce_sdStar	(	SCIP *	scip,
		int	edgelimit,
		SCIP_Bool	usestrongreds,
		GRAPH *	g,
		SCIP_Real *	dist,
		int *	star_base,
		int *	visitlist,
		STP_Bool *	visited,
		DHEAP *	dheap,
		int *	nelims
	)

SD star test for PcMw and SPG

Parameters

scip	SCIP data structure
edgelimit	limit
usestrongreds	allow strong reductions?
g	graph data structure
dist	vertex distances
star_base	array of size nnodes
visitlist	array of size nnodes
visited	array of size nnodes
dheap	Dijkstra heap
nelims	point to store number of deleted edges

Definition at line 3202 of file reduce_sd.c.

References dynamic_csr_storage::cost, GRAPH::dcsr_storage, EAT_FREE, dynamic_csr_storage::edgeid, GRAPH::edges, csr_range::end, GRAPH::extended, FALSE, FARAWAY, GRAPH::grad, graph_dcsr_deleteEdgeBi(), graph_edge_delBlocked(), graph_free_dcsr(), graph_heap_clean(), graph_init_dcsr(), graph_pc_isPcMw(), graph_sdStar(), dynamic_csr_storage::head, GRAPH::head, dynamic_csr_storage::id2csredge, GRAPH::knots, GRAPH::mark, nnodes, GRAPH::oeat, dynamic_csr_storage::range, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisLE(), SDSTAR_BASE_KILLED, SDSTAR_BASE_UNSET, sdStarReset(), GRAPH::source, csr_range::start, GRAPH::tail, and TRUE.

◆ reduce_sdStarBiased()

SCIP_RETCODE reduce_sdStarBiased	(	SCIP *	scip,
		int	edgelimit,
		SCIP_Bool	usestrongreds,
		GRAPH *	g,
		int *	nelims
	)

SD star test for PcMw and SPG

Parameters

scip	SCIP data structure
edgelimit	limit
usestrongreds	allow strong reductions?
g	graph data structure
nelims	point to store number of deleted edges

Definition at line 3332 of file reduce_sd.c.

References reduce_sdprofitFree(), reduce_sdprofitInit(), reduce_sdStarBiasedWithProfit(), SCIP_CALL, and SCIP_OKAY.

Referenced by redLoopInnerPc(), redLoopInnerStp(), testSdStarBiasedDeletesEdge(), testSdStarBiasedDeletesEdge2(), and testSdStarBiasedDeletesEdge3().

◆ reduce_sdStarBiasedWithProfit()

SCIP_RETCODE reduce_sdStarBiasedWithProfit	(	SCIP *	scip,
		int	edgelimit,
		const SDPROFIT *	sdprofit,
		SCIP_Bool	usestrongreds,
		GRAPH *	g,
		int *	nelims
	)

SD star test for PcMw and SPG

Parameters

scip	SCIP data structure
edgelimit	limit
sdprofit	with profit given
usestrongreds	allow strong reductions?
g	graph data structure
nelims	point to store number of deleted edges

Definition at line 3353 of file reduce_sd.c.

References GRAPH::grad, graph_free_dcsr(), graph_get_nNodes(), graph_init_dcsr(), GRAPH::mark, nnodes, SCIP_Bool, SCIP_CALL, SCIP_OKAY, sdStarBiasedProcessNode(), sdStarFinalize(), sdStarInit(), and GRAPH::source.

Referenced by reduce_impliedProfitBased(), and reduce_sdStarBiased().

◆ reduce_sdStarPc()

SCIP_RETCODE reduce_sdStarPc	(	SCIP *	scip,
		int	edgelimit,
		const int *	edgestate,
		GRAPH *	g,
		SCIP_Real *	dist,
		int *	star_base,
		int *	visitlist,
		STP_Bool *	visited,
		DHEAP *	dheap,
		int *	nelims
	)

SD star test for PcMw NOTE: deprecated

Parameters

scip	SCIP data structure
edgelimit	limit
edgestate	state array or NULL
g	graph data structure
dist	vertex distances
star_base	array of size nnodes
visitlist	array of size nnodes
visited	array of size nnodes
dheap	Dijkstra heap
nelims	point to store number of deleted edges

Definition at line 3546 of file reduce_sd.c.

◆ reduce_sdStarPc2()

SCIP_RETCODE reduce_sdStarPc2	(	SCIP *	scip,
		int	edgelimit,
		SCIP_Bool	usestrongreds,
		GRAPH *	g,
		SCIP_Real *	dist,
		int *	star_base,
		int *	visitlist,
		STP_Bool *	visited,
		DHEAP *	dheap,
		int *	nelims
	)

SD star test for PcMw

Parameters

scip	SCIP data structure
edgelimit	limit
usestrongreds	allow strong reductions?
g	graph data structure
dist	vertex distances
star_base	array of size nnodes
visitlist	array of size nnodes
visited	array of size nnodes
dheap	Dijkstra heap
nelims	point to store number of deleted edges

Definition at line 3394 of file reduce_sd.c.

References dynamic_csr_storage::cost, dynamic_csr_storage::cost2, GRAPH::dcsr_storage, EAT_FREE, dynamic_csr_storage::edgeid, GRAPH::edges, csr_range::end, EQ, GRAPH::extended, FALSE, FARAWAY, GRAPH::grad, graph_dcsr_deleteEdgeBi(), graph_edge_delBlocked(), graph_free_dcsr(), graph_heap_clean(), graph_init_dcsr(), graph_mark(), graph_pc_isPcMw(), graph_sdStar(), dynamic_csr_storage::head, GRAPH::head, dynamic_csr_storage::id2csredge, GRAPH::knots, GRAPH::mark, dynamic_csr_storage::nedges, nnodes, NULL, GRAPH::oeat, pcBiasCostsDCSR(), dynamic_csr_storage::range, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisLE(), SDSTAR_BASE_KILLED, SDSTAR_BASE_UNSET, sdStarReset(), GRAPH::source, csr_range::start, GRAPH::tail, and TRUE.

Referenced by redLoopInnerPc(), and testSdStarPcKillsEdge().

◆ reduce_sdWalk()

SCIP_RETCODE reduce_sdWalk	(	SCIP *	scip,
		int	edgelimit,
		const int *	edgestate,
		GRAPH *	g,
		int *	termmark,
		SCIP_Real *	dist,
		int *	heap,
		int *	state,
		int *	visitlist,
		STP_Bool *	visited,
		int *	nelims
	)

SD test for PcMw using only limited Dijkstra-like walk from both endpoints of an edge

Definition at line 3743 of file reduce_sd.c.

References GRAPH::cost, EAT_LAST, EDGE_BLOCKED, GRAPH::extended, FALSE, FARAWAY, graph_edge_del(), graph_pc_isPcMw(), graph_pc_termMarkProper(), graph_sdWalks(), GRAPH::head, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_OKAY, SCIP_Real, sdwalkReset(), TRUE, and UNKNOWN.

◆ reduce_sdWalk_csr()

SCIP_RETCODE reduce_sdWalk_csr	(	SCIP *	scip,
		int	edgelimit,
		const int *	edgestate,
		GRAPH *	g,
		int *	termmark,
		SCIP_Real *	dist,
		int *	visitlist,
		STP_Bool *	visited,
		DHEAP *	dheap,
		int *	nelims
	)

SD test for PcMw using only limited Dijkstra-like walk from both endpoints of an edge

Parameters

scip	SCIP data structure
edgelimit	edge limit
edgestate	per edge: state
g	graph data structure
termmark	per node: terminal property
dist	per node: distance
visitlist	array to store visited nodes
visited	per node: was visited?
dheap	head data structure
nelims	pointer to store number of eliminations

Definition at line 2818 of file reduce_sd.c.

References dynamic_csr_storage::cost, GRAPH::dcsr_storage, EAT_FREE, EDGE_BLOCKED, dynamic_csr_storage::edgeid, GRAPH::edges, csr_range::end, GRAPH::extended, FALSE, FARAWAY, graph_dcsr_deleteEdgeBi(), graph_edge_delBlocked(), graph_free_dcsr(), graph_heap_clean(), graph_init_dcsr(), graph_pc_isPcMw(), graph_pc_termMarkProper(), graph_sdWalks_csr(), dynamic_csr_storage::head, GRAPH::head, dynamic_csr_storage::id2csredge, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, dijkstra_heap::position, dynamic_csr_storage::range, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, sdwalkReset(), csr_range::start, GRAPH::tail, and TRUE.

◆ reduce_sdWalkTriangle()

SCIP_RETCODE reduce_sdWalkTriangle	(	SCIP *	scip,
		int	edgelimit,
		SCIP_Bool	usestrongreds,
		GRAPH *	g,
		int *	termmark,
		SCIP_Real *	dist,
		int *	visitlist,
		STP_Bool *	visited,
		DHEAP *	dheap,
		int *	nelims
	)

SD test for PcMw using limited Dijkstra-like walk from both endpoints of an edge

Parameters

scip	SCIP data structure
edgelimit	edge limit
usestrongreds	allow strong reductions?
g	graph data structure
termmark	terminal mark
dist	distances
visitlist	array to store visited nodes
visited	per node: was visited?
dheap	heap data structure
nelims	number of eliminations

Definition at line 3011 of file reduce_sd.c.

References dynamic_csr_storage::cost, GRAPH::dcsr_storage, EAT_FREE, dynamic_csr_storage::edgeid, GRAPH::edges, csr_range::end, GRAPH::extended, FALSE, FARAWAY, graph_dcsr_deleteEdgeBi(), graph_edge_delBlocked(), graph_free_dcsr(), graph_heap_clean(), graph_init_dcsr(), graph_pc_isPcMw(), graph_pc_termMarkProper(), graph_sdWalksTriangle(), dynamic_csr_storage::head, GRAPH::head, dynamic_csr_storage::id2csredge, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, dijkstra_heap::position, dynamic_csr_storage::range, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisLE(), sdwalkReset(), csr_range::start, GRAPH::tail, TRUE, and UNKNOWN.

Referenced by checkSdWalk(), and redLoopInnerPc().

◆ reduce_sdWalkExt()

SCIP_RETCODE reduce_sdWalkExt	(	SCIP *	scip,
		int	edgelimit,
		SCIP_Bool	usestrongreds,
		GRAPH *	g,
		SCIP_Real *	dist,
		int *	heap,
		int *	state,
		int *	visitlist,
		STP_Bool *	visited,
		int *	nelims
	)

SD test for PcMw using only limited Dijkstra-like walk from both endpoints of an edge

Parameters

scip	SCIP data structure
edgelimit	edge limit
usestrongreds	allow strong reductions?
g	graph data structure
dist	per node: distances
heap	heap
state	state
visitlist	array to store visited nodes
visited	number of visited nodes
nelims	number of eliminations

Definition at line 3827 of file reduce_sd.c.

References GRAPH::cost, EAT_LAST, GRAPH::extended, FALSE, FARAWAY, graph_edge_del(), graph_pc_isPcMw(), graph_sdWalksExt(), GRAPH::head, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, sdwalkResetExt(), STP_SDWALK_MAXNPREVS, TRUE, and UNKNOWN.

Referenced by checkSdWalk(), and redLoopInnerPc().

◆ reduce_sdWalkExt2()

SCIP_RETCODE reduce_sdWalkExt2	(	SCIP *	scip,
		int	edgelimit,
		const int *	edgestate,
		GRAPH *	g,
		int *	termmark,
		SCIP_Real *	dist,
		int *	heap,
		int *	state,
		int *	visitlist,
		STP_Bool *	visited,
		int *	nelims
	)

SD test for PcMw using only limited Dijkstra-like walk from both endpoints of an edge

Parameters

scip	SCIP data structure
edgelimit	edge limit
edgestate	per edge: state
g	graph data structure
termmark	per node: terminal state
dist	per node: distance
heap	heap
state	state
visitlist	visited nodes
visited	number of visited nodes
nelims	number of eliminations

Definition at line 3910 of file reduce_sd.c.

References GRAPH::cost, EAT_LAST, EDGE_BLOCKED, GRAPH::extended, FALSE, FARAWAY, graph_edge_del(), graph_pc_isPcMw(), graph_pc_termMarkProper(), graph_sdWalksExt2(), GRAPH::head, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, sdwalkResetExt2(), STP_SDWALK_MAXNPREVS, TRUE, and UNKNOWN.

◆ reduce_sdspSap()

SCIP_RETCODE reduce_sdspSap	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	pathtail,
		PATH *	pathhead,
		int *	heap,
		int *	statetail,
		int *	statehead,
		int *	memlbltail,
		int *	memlblhead,
		int *	nelims,
		int	limit
	)

SDC test for the SAP using a limited version of Dijkstra's algorithm from both endpoints of an arc

Parameters

scip	SCIP data structure
g	graph data structure
pathtail	path tails
pathhead	path heads
heap	heap
statetail	states of tails
statehead	states of heads
memlbltail	storage for tails
memlblhead	storage for heads
nelims	number of eliminations
limit	limit for number of visits

Definition at line 2661 of file reduce_sd.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_sdPaths(), GRAPH::head, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisGE(), SCIPisGT(), SCIPisLT(), TRUE, and UNKNOWN.

Referenced by reduce_sap().

◆ reduce_sd()

SCIP_RETCODE reduce_sd	(	SCIP *	scip,
		GRAPH *	g,
		REDBASE *	redbase,
		int *	nelims
	)

Special distance test

Parameters

scip	SCIP data structure
g	graph data structure
redbase	reduction data
nelims	point to store number of deleted edges

Definition at line 1517 of file reduce_sd.c.

References GRAPH::cost, EAT_FREE, EAT_LAST, shortest_path::edge, reduction_base::edgearrint, GRAPH::edges, FALSE, flipedge, GE, getlecloseterms(), GRAPH::grad, graph_edge_add(), graph_edge_del(), graph_free(), graph_get4nextTermPaths(), graph_get_nEdges(), graph_get_nNodes(), graph_init(), graph_knot_add(), graph_knot_chg(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_valid(), GT, GRAPH::head, Is_term, GRAPH::knots, ledgeFromNetgraph(), LT, GRAPH::mark, MST_MODE, nnodes, reduction_base::nodearrint, reduction_base::nodearrint2, reduction_parameters::nodereplacing, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, reduction_base::redparameters, reduce_bd34WithSd(), reduce_sdgraphFreeFromDistGraph(), reduce_sdgraphGetSd(), reduce_sdgraphInitFromDistGraph(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisEQ(), SCIPisGE(), sddeltable(), GRAPH::source, reduction_base::state, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, UNKNOWN, reduction_parameters::usestrongreds, reduction_base::vbase, and reduction_base::vnoi.

Referenced by redLoopInnerStp().

◆ reduce_sdBiased()

SCIP_RETCODE reduce_sdBiased	(	SCIP *	scip,
		SD *	sdistance,
		GRAPH *	g,
		int *	nelims
	)

implied-profit special distance test

Parameters

scip	SCIP data structure
sdistance	special distances storage
g	graph structure
nelims	number of eliminations

Definition at line 1845 of file reduce_sd.c.

References GRAPH::cost, deleteEdge(), EAT_LAST, EQ, FALSE, FARAWAY, graph_edge_del(), graph_edge_printInfo(), graph_get_nNodes(), graph_mark(), graph_valid(), special_distance_storage::hasNeigborUpdate, GRAPH::head, Is_term, LT, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, reduce_sdgraphGetMaxCost(), reduce_sdImpLongEdge(), reduce_sdprofitGetProfit(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisEQ(), SCIPisLT(), sdGetSd(), special_distance_storage::sdgraph, special_distance_storage::sdprofit, GRAPH::term, and TRUE.

Referenced by reduce_impliedProfitBased(), reduce_impliedProfitBasedRpc(), testSdBiasedBottleneckDeletesEdge(), testSdBiasedBottleneckTermPathDeletesEdge(), and testSdBiasedDeletesEdge().

◆ reduce_sdBiasedNeighbor()

SCIP_RETCODE reduce_sdBiasedNeighbor	(	SCIP *	scip,
		SD *	sdistance,
		GRAPH *	g,
		int *	nelims
	)

implied-profit neighbor special distance test NOTE: invalidates SD for other methods!

Parameters

scip	SCIP data structure
sdistance	special distances storage
g	graph structure
nelims	number of eliminations

Definition at line 1927 of file reduce_sd.c.

References GRAPH::cost, deleteEdge(), EAT_LAST, FALSE, graph_edge_del(), graph_edge_printInfo(), graph_get_nNodes(), graph_mark(), graph_valid(), special_distance_storage::hasNeigborUpdate, GRAPH::head, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, reduce_sdgraphGetMaxCost(), reduce_sdgraphHasMstHalfMark(), reduce_sdImpLongEdge(), reduce_sdneighborGetBlocked(), reduce_sdUpdateWithSdNeighbors(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisLT(), sdGetSd(), sdGetSdNeighbor(), special_distance_storage::sdgraph, special_distance_storage::sdneighbors, GRAPH::terms, and TRUE.

Referenced by testSdBiasedDeletesEdge().

◆ reduce_sdPc()

SCIP_RETCODE reduce_sdPc	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	vnoi,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	nodesid,
		int *	nodesorg,
		int *	nelims
	)

SD test for PC

Parameters

scip	SCIP data structure
g	graph data structure
vnoi	Voronoi data structure
heap	heap array
state	array to store state of a node during Voronoi computation
vbase	Voronoi base to each node
nodesid	array
nodesorg	array
nelims	pointer to store number of eliminated edges

Definition at line 2023 of file reduce_sd.c.

References GRAPH::cost, shortest_path::dist, EAT_FREE, EAT_LAST, GRAPH::edges, GRAPH::extended, FARAWAY, flipedge, getcloseterms(), getcloseterms2term(), graph_edge_add(), graph_edge_del(), graph_free(), graph_get4nextTermPaths(), graph_get4nextTTerms(), graph_init(), graph_knot_add(), graph_valid(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGT(), SCIPisLT(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by execPc_SD().

◆ reduce_sdGetSd()

SCIP_Real reduce_sdGetSd	(	const GRAPH *	g,
		int	i,
		int	i2,
		SCIP_Real	sd_upper,
		SCIP_Real	sd_sufficient,
		SD *	sddata
	)

gets special distance to a pair of nodes

Parameters

g	graph structure
i	first vertex
i2	second vertex
sd_upper	upper bound on special distance that is accepted (can be FARAWAY)
sd_sufficient	bound below which to terminate (can be 0.0)
sddata	SD

Definition at line 2433 of file reduce_sd.c.

References FALSE, and sdGetSd().

Referenced by distDataGetSpecialDist(), and testSdRepair().

◆ reduce_sdGetSdIntermedTerms()

SCIP_Real reduce_sdGetSdIntermedTerms	(	const GRAPH *	g,
		int	i,
		int	i2,
		SCIP_Real	sd_upper,
		SCIP_Real	sd_sufficient,
		SD *	sddata
	)

gets special distance to a pair of nodes, but only allows SDs with intermediate terminals

Parameters

g	graph structure
i	first vertex
i2	second vertex
sd_upper	upper bound on special distance that is accepted (can be FARAWAY)
sd_sufficient	bound below which to terminate (can be 0.0)
sddata	SD

Definition at line 2449 of file reduce_sd.c.

References sdGetSd(), and TRUE.

Referenced by distDataGetSpecialDistIntermedTerms().

◆ reduce_getSdByPaths()

SCIP_RETCODE reduce_getSdByPaths	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	pathtail,
		PATH *	pathhead,
		SCIP_Real *	sdist,
		SCIP_Real	distlimit,
		int *	heap,
		int *	statetail,
		int *	statehead,
		int *	memlbltail,
		int *	memlblhead,
		int	i,
		int	i2,
		int	limit,
		SCIP_Bool	pc,
		SCIP_Bool	mw
	)

get SD to a single edge by using path computations

Definition at line 2304 of file reduce_sd.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, graph_sdPaths(), GRAPH::head, Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPisGT(), SCIPisLE(), SCIPisLT(), GRAPH::term, and UNKNOWN.

Referenced by reduce_chain2(), and reduce_npv().

◆ reduce_bdk()

SCIP_RETCODE reduce_bdk	(	SCIP *	scip,
		int	edgevisitlimit,
		GRAPH *	g,
		int *	nelims
	)

bd_k test without given Steiner bottleneck distances

Parameters

scip	SCIP data structure
edgevisitlimit	maximum edge visited per iteration
g	graph structure
nelims	number of eliminations

Definition at line 774 of file reduce_sdcomp.c.

References reduce_bdkWithSd(), reduce_sdFree(), reduce_sdInit(), SCIP_CALL, SCIP_OKAY, bottleneck_distance_storage::sdistance, and GRAPH::terms.

Referenced by redLoopInnerStp(), testBdkSdMstDeletesNodeDeg3(), testBdkSdMstDeletesNodeDeg4(), testBdkSdMstStarDeletesNodeDeg4(), and testBdkTreeDistDeletesNodeDeg4().

◆ reduce_bdkBiased()

SCIP_RETCODE reduce_bdkBiased	(	SCIP *	scip,
		int	edgevisitlimit,
		GRAPH *	g,
		int *	nelims
	)

biased bd_k test without given Steiner bottleneck distances

Parameters

scip	SCIP data structure
edgevisitlimit	maximum edge visited per iteration
g	graph structure
nelims	number of eliminations

Definition at line 796 of file reduce_sdcomp.c.

References reduce_bdkWithSd(), reduce_sdFree(), reduce_sdInitBiased(), SCIP_CALL, SCIP_OKAY, bottleneck_distance_storage::sdistance, and GRAPH::terms.

◆ reduce_bdkWithSd()

SCIP_RETCODE reduce_bdkWithSd	(	SCIP *	scip,
		int	edgevisitlimit,
		SD *	sdistance,
		GRAPH *	g,
		int *	nelims
	)

bd_k test for given Steiner bottleneck distances

Parameters

scip	SCIP data structure
edgevisitlimit	maximum edge visited per iteration
sdistance	special distances storage
g	graph structure
nelims	number of eliminations

Definition at line 818 of file reduce_sdcomp.c.

References bdkFree(), bdkGetCliqueSds(), bdkGetNeighborhood(), bdkInit(), bdkNodeIsInvalid(), bdkTryDeg3(), bdkTryDegGe4(), dijkstra_data::edgelimit, graph_dijkLimited_clean(), graph_dijkLimited_free(), graph_dijkLimited_init(), graph_dijkLimited_reset(), graph_get_nNodes(), graph_mark(), graph_pc_isPcMw(), nnodes, reduce_unconnected(), SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, STP_BDKIMP_MAXDEGREE, and GRAPH::terms.

Referenced by reduce_bdk(), and reduce_bdkBiased().

◆ reduce_pathreplace()

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

paths elimination

Parameters

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

Definition at line 1119 of file reduce_path.c.

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

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

◆ reduce_pathreplaceExt()

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

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

Parameters

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

Definition at line 1080 of file reduce_path.c.

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

Referenced by extreduce_deleteEdges().

◆ reduce_bd34()

SCIP_RETCODE reduce_bd34	(	SCIP *	,
		GRAPH *	,
		PATH *	,
		PATH *	,
		int *	,
		int *	,
		int *	,
		int *	,
		int *	,
		int *	,
		int	,
		SCIP_Real *
	)

Definition at line 4516 of file reduce_sd.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, EQ, GRAPH::extended, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_buildCompleteGraph(), graph_free(), graph_knot_delPseudo(), graph_mark(), graph_path_exit(), graph_path_init(), graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_realDegree(), graph_pc_termIsNonLeafTerm(), graph_valid(), GRAPH::head, Is_term, isPseudoDeletable(), isPseudoDeletableDeg3(), GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, single_special_distance_pc::pathtail, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArrayNull, sdGetSdPcMw(), STP_BD_MAXDEGREE, STP_BD_MAXDNEDGES, GRAPH::term, TRUE, and UNKNOWN.

Referenced by execPc_BDk().

◆ reduce_bd34WithSd()

SCIP_RETCODE reduce_bd34WithSd	(	SCIP *	scip,
		GRAPH *	g,
		SDGRAPH *	sdgraph,
		PATH *	vnoi,
		int *	vbase,
		int *	nelims
	)

bd_k test for given Steiner bottleneck distances

Parameters

scip	SCIP data structure
g	graph structure
sdgraph	auxiliary graph structure
vnoi	path structure
vbase	bases for nearest terminals
nelims	number of eliminations

Definition at line 4310 of file reduce_sd.c.

References GRAPH::cost, EAT_LAST, GRAPH::edges, EQ, flipedge, getSd(), GRAPH::grad, graph_buildCompleteGraph(), graph_free(), graph_knot_delPseudo(), graph_mark(), graph_path_exit(), graph_path_init(), graph_pc_isPcMw(), graph_valid(), GRAPH::head, Is_term, isPseudoDeletable(), isPseudoDeletableDeg3(), GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, reduce_unconnected(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, STP_BD_MAXDEGREE, STP_BD_MAXDNEDGES, GRAPH::term, and TRUE.

Referenced by reduce_sd().

◆ reduce_bound()

SCIP_RETCODE reduce_bound	(	SCIP *	scip,
		GRAPH *	graph,
		PATH *	vnoi,
		SCIP_Real *	radius,
		SCIP_Real *	offset,
		SCIP_Real *	upperbound,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	nelims
	)

bound-based reductions for the (R)PCSTP, the MWCSP and the STP

Parameters

scip	SCIP data structure
graph	graph data structure
vnoi	Voronoi data structure
radius	radius array
offset	pointer to the offset
upperbound	pointer to an upper bound
heap	heap array
state	array to store state of a node during Voronoi computation
vbase	Voronoi base to each node
nelims	pointer to store number of eliminated edges

Definition at line 655 of file reduce_bnd.c.

References bound, computeSteinerTree(), CONNECT, GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::extended, FARAWAY, flipedge, GRAPH::grad, graph_add2ndTermPaths(), graph_add3rdTermPaths(), graph_add4thTermPaths(), graph_edge_del(), graph_free(), graph_get4nextTTerms(), graph_get_nEdges(), graph_get_nNodes(), graph_getEdgeCosts(), graph_init(), graph_knot_chg(), graph_knot_delPseudo(), graph_knot_printInfo(), graph_mark(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_pc_deleteTerm(), graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), graph_printInfo(), graph_valid(), graph_voronoiWithRadius(), GT, GRAPH::head, Is_pseudoTerm, Is_term, LT, GRAPH::mark, MST_MODE, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_state, GRAPH::prize, r, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPisGE(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPsortReal(), SCIPsortRealInt(), GRAPH::source, STP_DHCSTP, STP_MWCSP, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by execPc_BND(), redLoopInnerStp(), and reduce_hc().

◆ reduce_boundMw()

SCIP_RETCODE reduce_boundMw	(	SCIP *	scip,
		GRAPH *	graph,
		PATH *	vnoi,
		SCIP_Real *	offset,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	result,
		int *	nelims
	)

Bound-based reduction method for the MWCSP . The reduction method tries to eliminate nodes and vertices by checking whether an upper bound for each solution that contains them is smaller than the best known solution value. The essence of the approach is a decomposition of the graph such that this upper bound is minimized.

Parameters

scip	SCIP data structure
graph	graph data structure
vnoi	Voronoi data structure (size 3 * nnodes)
offset	pointer to the offset
heap	heap array
state	array to store state of a node during Voronoi computation
vbase	Voronoi base to each node
result	solution array or NULL
nelims	pointer to store number of eliminated edges

Definition at line 1058 of file reduce_bnd.c.

References bound, CONNECT, GRAPH::cost, shortest_path::dist, EAT_LAST, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_add2ndTermPaths(), graph_edge_del(), graph_pc_isRootedPcMw(), graph_voronoiMw(), graph_voronoiWithRadiusMw(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPisGE(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPsortReal(), GRAPH::source, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by redLoopInnerMw().

◆ reduce_boundPruneHeur()

SCIP_RETCODE reduce_boundPruneHeur	(	SCIP *	scip,
		GRAPH *	graph,
		PATH *	vnoi,
		SCIP_Real *	cost,
		SCIP_Real *	radius,
		SCIP_Real *	costrev,
		SCIP_Real *	offset,
		int *	heap,
		int *	state,
		int *	vbase,
		const int *	solnode,
		const int *	soledge,
		int *	nelims,
		int	minelims
	)

heuristic bound-based reductions for the (R)PCSTP, the MWCSP and the STP; used by prune heuristic

Parameters

scip	SCIP data structure
graph	graph data structure
vnoi	Voronoi data structure
cost	edge cost array
radius	radius array
costrev	reversed edge cost array
offset	pointer to the offset
heap	heap array
state	array to store state of a node during Voronoi computation
vbase	Voronoi base to each node
solnode	array of nodes of current solution that is not to be destroyed
soledge	array of edges of current solution that is not to be destroyed
nelims	pointer to store number of eliminated edges
minelims	minimum number of edges to be eliminated

Definition at line 1237 of file reduce_bnd.c.

References boundPruneHeur(), boundPruneHeurMw(), GRAPH::extended, graph_pc_isMw(), graph_valid(), NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, and GRAPH::source.

Referenced by SCIPStpHeurPruneRun().

◆ reduce_boundHop()

SCIP_RETCODE reduce_boundHop	(	SCIP *	scip,
		GRAPH *	graph,
		PATH *	vnoi,
		SCIP_Real *	cost,
		SCIP_Real *	radius,
		SCIP_Real *	costrev,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	nelims
	)

bound-based reduction test for the HCDSTP

Definition at line 1323 of file reduce_bnd.c.

References bound, CONNECT, GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_add2ndTermPaths(), graph_edge_del(), graph_free(), graph_init(), graph_knot_chg(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_valid(), graph_voronoiWithRadius(), GRAPH::head, GRAPH::hoplimit, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_state, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisGT(), SCIPisLT(), SCIPsortReal(), GRAPH::source, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by reduce_hc().

◆ reduce_boundHopR()

SCIP_RETCODE reduce_boundHopR	(	SCIP *	scip,
		GRAPH *	graph,
		PATH *	vnoi,
		SCIP_Real *	cost,
		SCIP_Real *	costrev,
		SCIP_Real *	pathdist,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	nelims,
		int *	pathedge
	)

hop bound-based reduction test for the HCDSTP

Definition at line 1518 of file reduce_bnd.c.

References bound, GRAPH::cost, shortest_path::dist, EAT_LAST, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_add1stTermPaths(), graph_edge_del(), graph_path_execX(), graph_valid(), GRAPH::head, GRAPH::hoplimit, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGT(), SCIPisLT(), GRAPH::source, GRAPH::term, and TRUE.

Referenced by reduce_hc().

◆ reduce_boundHopRc()

SCIP_RETCODE reduce_boundHopRc	(	SCIP *	,
		GRAPH *	,
		PATH *	,
		SCIP_Real *	,
		SCIP_Real *	,
		SCIP_Real *	,
		SCIP_Real	,
		int *	,
		int *	,
		int *	,
		int *	,
		int *	,
		SCIP_Bool
	)

Definition at line 1646 of file reduce_bnd.c.

References BLOCKED, bound, CONNECT, GRAPH::cost, DEFAULT_HOPFACTOR, shortest_path::dist, EAT_LAST, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_add1stTermPaths(), graph_edge_del(), graph_path_execX(), graph_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, pcmode_fromheurdata, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetCutoffbound(), SCIPisGT(), SCIPisLT(), SCIPprobdataGetVars(), SCIPStpFixEdgeVarTo0(), SCIPStpHeurTMRun(), SCIPvarGetUbLocal(), GRAPH::source, GRAPH::term, TRUE, and UNKNOWN.

Referenced by reduce_hc().

◆ reduce_boundHopDa()

SCIP_RETCODE reduce_boundHopDa	(	SCIP *	scip,
		GRAPH *	graph,
		int *	nelims,
		SCIP_RANDNUMGEN *	randnumgen
	)

dual ascent based hop reductions for HCDSTP

Parameters

scip	SCIP data structure
graph	graph data structure
nelims	pointer to store number of reduced edges
randnumgen	random number generator

Definition at line 1286 of file reduce_bnd.c.

References BMScopyMemoryArray, GRAPH::cost, reduce_costs_reduction_parameters::damode, EQ, extred_none, FALSE, FARAWAY, graph_get_nEdges(), graph_valid(), LT, NULL, reduce_da(), reduce_unconnectedForDirected(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, and STP_DAMODE_HOPS.

Referenced by reduce_hc().

◆ reduce_da()

SCIP_RETCODE reduce_da	(	SCIP *	scip,
		GRAPH *	graph,
		const RPDA *	paramsda,
		REDSOLLOCAL *	redsollocal,
		SCIP_Real *	offsetp,
		int *	nelims,
		SCIP_RANDNUMGEN *	randnumgen
	)

dual ascent based reductions

Parameters

scip	SCIP data structure
graph	graph data structure
paramsda	parameters
redsollocal	primal bound info or NULL
offsetp	pointer to store offset
nelims	pointer to store number of reduced edges
randnumgen	random number generator

Definition at line 2471 of file reduce_da.c.

References collectFixedTerminals(), computeDualSolution(), computeDualSolutionGuided(), computeSteinerTreeRedCosts(), computeSteinerTreeRedCostsDirected(), GRAPH::cost, daGetMaxDeviation(), daGetNruns(), daGuidedIsPromising(), reduce_costs_reduction_parameters::damode, daOrderRoots(), daRedcostsExit(), daRedcostsInit(), daRoundExit(), daRoundInit(), GRAPH::edges, GRAPH::extended, extred_none, reduce_costs_reduction_parameters::extredMode, extreduce_exit(), extreduce_extPermaAddRandnumgen(), extreduce_init(), extreduce_pseudoDeleteNodes(), FALSE, FARAWAY, GE, GRAPH::grad, graph_mark(), graph_pc_2orgcheck(), graph_pc_2trans(), graph_pc_isMw(), graph_pc_isPc(), graph_pc_isRootedPcMw(), graph_typeIsDirected(), graph_valid(), graph_valid_ancestors(), GRAPH::hoplimit, GRAPH::knots, markPseudoDeletablesFromBounds(), nnodes, reduce_costs_reduction_parameters::nodereplacing, NULL, redcosts_addLevel(), redcosts_getDualBoundTop(), redcosts_getEdgeCostsTop(), redcosts_getNodeToTermsPathsTop(), redcosts_getRootToNodeDistTop(), redcosts_increaseOnDeletedArcsTop(), redcosts_setRootTop(), reduce_applyPseudoDeletions(), reduce_identifyNonLeafTerms(), reduce_sollocalGetUpperBound(), reduce_sollocalRebuildTry(), reduce_sollocalSetOffset(), reduce_sollocalUpdateNodesol(), reduce_sollocalUpdateUpperBound(), reduce_sollocalUsesNodesol(), reduceRootedProb(), reduceWithEdgeExtReds(), reduceWithEdgeFixingBounds(), reduceWithNodeFixingBounds(), extension_data_permanent::result, SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisFeasGT(), SCIPisZero(), extension_data_permanent::solIsValid, solpool_free(), solpool_init(), SOLPOOL_SIZE, solstp_isUnreduced(), solstp_rerootInfeas(), GRAPH::source, STP_DAMODE_HOPS, STP_DCSTP, STP_DHCSTP, STP_RPCSPG, GRAPH::stp_type, GRAPH::terms, TRUE, updateEdgeFixingBounds(), updateNodeFixingBounds(), updateNodeReplaceBounds(), reduce_costs_reduction_parameters::useRec, and reduce_costs_reduction_parameters::useSlackPrune.

Referenced by redLoopInnerMw(), redLoopInnerPc(), redLoopInnerStp(), reduce_boundHopDa(), reduce_dc(), reduce_hc(), reduce_nw(), reduce_redLoopMw(), reduce_redLoopPc(), reduce_redLoopStp(), and reduce_sap().

◆ reduce_dapaths()

SCIP_RETCODE reduce_dapaths	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	offsetp,
		int *	nelims
	)

dual ascent path based reductions

Parameters

scip	SCIP data structure
g	graph data structure
offsetp	pointer to store offset
nelims	pointer to store number of reduced edges

Definition at line 2397 of file reduce_da.c.

References computeSteinerTreeTM(), dapathsDeleteEdges(), dapathsFixPotTerms(), dapathsIsPromising(), dapathsReplaceNodes(), dualascent_paths(), GRAPH::extended, FARAWAY, graph_get_nEdges(), graph_isMarked(), graph_mark(), graph_pc_2org(), graph_pc_2trans(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_valid(), GRAPH::knots, redcosts_free(), redcosts_getEdgeCostsTop(), redcosts_init(), redcosts_initializeDistancesTop(), redcosts_setCutoffFromBoundTop(), redcosts_setDualBoundTop(), reduce_unconnected(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPStpHeurLocalRun(), solstp_getObj(), solstp_isUnreduced(), GRAPH::source, and GRAPH::terms.

Referenced by redLoopInnerPc().

◆ reduce_daSlackPrune()

SCIP_RETCODE reduce_daSlackPrune	(	SCIP *	scip,
		GRAPH *	graph,
		int	minelims,
		SCIP_Bool	solgiven,
		int *	soledge,
		int *	solnode,
		int *	nelims,
		SCIP_Real *	upperbound,
		SCIP_Bool *	solImproved,
		SCIP_Bool *	solReconstructed
	)

dual ascent reduction for slack-and-prune heuristic

Parameters

scip	SCIP data structure
graph	graph data structure
minelims	minimum number of edges to eliminate
solgiven	solution provided?
soledge	solution edges (in/out)
solnode	array of nodes of current solution that is not to be destroyed (in/out)
nelims	pointer to store number of reduced edges
upperbound	pointer to store new upper bound
solImproved	solution improved?
solReconstructed	solution reconstructed?

Definition at line 2741 of file reduce_da.c.

References reduce_cost_parameters::addcuts, CONNECT, GRAPH::cost, shortest_path::dist, dualascent_allTermsReachable(), dualascent_exec(), EAT_LAST, shortest_path::edge, GRAPH::extended, FALSE, FARAWAY, flipedge, getSolObj(), GRAPH::grad, graph_edge_del(), graph_get2nextTermPaths(), graph_get_nEdges(), graph_get_nNodes(), graph_knot_del(), graph_mark(), graph_path_exec(), graph_path_execX(), graph_pc_2org(), graph_pc_2trans(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::mark, MST_MODE, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPepsilon(), SCIPfreeBufferArray, SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPsortReal(), SCIPStpHeurAscendPruneRun(), solstp_isValid(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by SCIPStpHeurSlackPruneRun().

◆ reduce_daPcMw()

SCIP_RETCODE reduce_daPcMw	(	SCIP *	scip,
		GRAPH *	graph,
		const RPDA *	paramsda,
		REDSOLLOCAL *	redprimal,
		PATH *	vnoi,
		SCIP_Real *	pathdist,
		int *	vbase,
		int *	pathedge,
		int *	state,
		STP_Bool *	nodearrchar,
		int *	nelims,
		SCIP_RANDNUMGEN *	randnumgen,
		SCIP_Real	prizesum
	)

dual ascent based reductions for PCSPG and MWCSP

Parameters

scip	SCIP data structure
graph	graph data structure
paramsda	parameters
redprimal	primal bound info or NULL
vnoi	Voronoi data structure array
pathdist	distance array for shortest path calculations
vbase	Voronoi base array
pathedge	shortest path incoming edge array for shortest path calculations
state	int 4 * vertices array
nodearrchar	STP_Bool node array for internal computations
nelims	pointer to store number of reduced edges
randnumgen	random number generator
prizesum	sum of positive prizes

Definition at line 3174 of file reduce_da.c.

References reduce_cost_parameters::addcuts, BMScopyMemoryArray, computePertubedSol(), computeSteinerTreeRedCostsPcMw(), computeTransVoronoi(), reduce_cost_parameters::damaxdeviation, DAMAXDEVIATION_FAST, daOrderRoots(), daPcAddTmSolToPool(), daPcFindRoots(), daPcMarkRoots(), daRedCostIsValid(), DEFAULT_NMAXROOTS, dualascent_allTermsReachable(), dualascent_exec(), dualascent_pathsPcMw(), EAT_LAST, GRAPH::edges, FALSE, FARAWAY, flipedge, GE, getSolObj(), GRAPH::grad, graph_add1stTermPaths(), graph_add2ndTermPaths(), graph_free(), graph_get_nEdges(), graph_get_nNodes(), graph_mark(), graph_path_execX(), graph_path_exit(), graph_path_init(), graph_pc_2org(), graph_pc_2orgcheck(), graph_pc_2trans(), graph_pc_isPc(), graph_pc_knotIsNonLeafTerm(), graph_transPcGetRsap(), graph_transPcGetSap(), graph_valid(), GRAPH::head, reduce_cost_parameters::is_pseudoroot, Is_pseudoTerm, Is_term, GRAPH::knots, LT, GRAPH::mark, nnodes, NULL, stp_solution::obj, GRAPH::oeat, GRAPH::outbeg, reduce_costs_reduction_parameters::pcmw_fastDa, reduce_costs_reduction_parameters::pcmw_markroots, reduce_costs_reduction_parameters::pcmw_solbasedda, reduce_costs_reduction_parameters::pcmw_useMultRoots, GRAPH::prize, reduce_identifyNonLeafTerms(), reduce_sollocalGetUpperBound(), reduce_sollocalUpdateNodesol(), reduce_sollocalUpdateUpperBound(), reduce_sollocalUsesNodesol(), reducePcMw(), reducePcMwTryBest(), reduceWithEdgeFixingBounds(), reduceWithNodeFixingBounds(), reduce_cost_parameters::root, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPisEQ(), SCIPisGE(), SCIPisGT(), solpool_free(), solpool_init(), SOLPOOL_SIZE, stp_solution_pool::sols, solstp_isUnreduced(), solstp_isValid(), solstp_reroot(), GRAPH::source, STP_MWCSP, STP_RED_MINBNDTERMS, STP_RPCSPG, STP_SAP, GRAPH::stp_type, GRAPH::term, GRAPH::terms, TRUE, updateEdgeFixingBounds(), updateNodeFixingBounds(), and reduce_costs_reduction_parameters::useRec.

Referenced by redLoopInnerMw(), redLoopInnerPc(), reduce_redLoopMw(), and reduce_redLoopPc().

◆ reduce_deleteConflictEdges()

SCIP_RETCODE reduce_deleteConflictEdges	(	SCIP *	scip,
		GRAPH *	g
	)

todo don't use this function, but check for conflicts in misc_stp.c and handle them

Parameters

scip	SCIP data structure
g	the graph

Definition at line 791 of file reduce_ext.c.

References GRAPH::ancestors, GRAPH::cost, EAT_FREE, GRAPH::edges, GRAPH::extended, FALSE, graph_edge_del(), graph_pc_isPcMw(), GRAPH::head, Is_pseudoTerm, markAncestorsConflict(), MAX, NULL, GRAPH::oeat, GRAPH::orgedges, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, GRAPH::tail, GRAPH::term, TRUE, and unmarkAncestorsConflict().

Referenced by reduce_redLoopPc().

◆ reduce_extendedCheck3Tree()

SCIP_RETCODE reduce_extendedCheck3Tree	(	SCIP *	scip,
		const GRAPH *	graph,
		int	root,
		const SCIP_Real *	redcost,
		const SCIP_Real *	pathdist,
		const PATH *	vnoi,
		const int *	vbase,
		SCIP_Real	cutoff,
		const int *	outedges,
		int	inedge,
		SCIP_Real *	treebound,
		SCIP_Bool *	ruleout,
		unsigned int *	eqstack,
		int *	eqstack_size,
		SCIP_Bool *	eqmark
	)

check 3-tree

Parameters

scip	SCIP data structure
graph	graph data structure
root	graph root from dual ascent
redcost	reduced costs
pathdist	shortest path distances
vnoi	Voronoi paths
vbase	bases to Voronoi paths
cutoff	cutoff value
outedges	two outgoing edge
inedge	incoming edge
treebound	to store a lower bound for the tree
ruleout	could tree be ruled out?
eqstack	stores edges that were used for equality comparison
eqstack_size	pointer to size of eqstack
eqmark	marks edges that were used for equality comparison

Definition at line 842 of file reduce_ext.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, GRAPH::edges, extendSubtreeHead(), extendSubtreeTail(), FALSE, FARAWAY, finalizeSubtree(), flipedge, GRAPH::grad, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, markAncestorsConflict(), MAX, nnodes, NULL, GRAPH::oeat, GRAPH::orgedges, GRAPH::outbeg, RED_EXT_EDGELIMIT, RED_EXT_MAXDFSDEPTH, RED_EXT_MAXGRAD, RED_EXT_MINDFSDEPTH, RED_EXT_MINGRAD, ruleOutSubtree(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPisGE(), SCIPisGT(), shortenSubtree(), GRAPH::tail, GRAPH::term, TRUE, truncateSubtree(), and unmarkAncestorsConflict().

Referenced by updateNodeReplaceBounds().

◆ reduce_extendedEdge()

int reduce_extendedEdge	(	SCIP *	scip,
		GRAPH *	graph,
		const PATH *	vnoi,
		const SCIP_Real *	cost,
		const SCIP_Real *	pathdist,
		const int *	result,
		SCIP_Real	minpathcost,
		int	root,
		STP_Bool *	marked,
		SCIP_Bool	markdirected
	)

reduce SPG graph based on reduced cost information and given upper bound todo to be deleted and replaced by reduce_extendedEdge2

Parameters

scip	SCIP data structure
graph	graph data structure
vnoi	Voronoi data structure
cost	dual ascent costs
pathdist	distance array from shortest path calculations
result	sol int array
minpathcost	the required reduced path cost to be surpassed
root	the root
marked	edge array to mark which (directed) edge can be removed
markdirected	try to also mark edge if anti-parallel is not marked

Definition at line 1155 of file reduce_ext.c.

References CONNECT, GRAPH::cost, EAT_FREE, GRAPH::edges, GRAPH::extended, FALSE, GRAPH::grad, graph_pc_isPcMw(), Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, reduceCheckEdge(), removeEdge(), SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPisEQ(), SCIPisZero(), GRAPH::term, and TRUE.

Referenced by fixVarsExtendedRed().

◆ reduce_nodesDeg1()

void reduce_nodesDeg1	(	SCIP *	scip,
		GRAPH *	graph
	)

removes nodes of degree one and unmarks

Parameters

scip	SCIP
graph	graph data structure (in/out)

Definition at line 149 of file reduce_simple.c.

References FALSE, GRAPH::grad, graph_get_nNodes(), graph_knot_del(), graph_knot_isInRange(), GRAPH::head, Is_term, GRAPH::mark, nnodes, GRAPH::outbeg, SCIP_Bool, GRAPH::term, and TRUE.

Referenced by pseudodeleteExecute(), and reduce_pathreplace().

◆ reduce_simple()

SCIP_RETCODE reduce_simple	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	solnode,
		int *	nelims,
		int *	edgestate
	)

basic reduction tests for the STP

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offset value
solnode	node array to mark whether an node is part of a given solution (CONNECT), or NULL
nelims	pointer to number of reductions
edgestate	array to store status of (directed) edge (for propagation, can otherwise be set to NULL)

Definition at line 184 of file reduce_simple.c.

References GRAPH::cost, EAT_LAST, Edge_anti, EDGE_BLOCKED, FALSE, FARAWAY, GRAPH::grad, graph_edge_del(), graph_fixed_addEdge(), graph_knot_contract(), graph_knot_contractLowdeg2High(), graph_knot_replaceDeg2(), graph_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, reduce_unconnected(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisLE(), SCIPisLT(), GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by execNvSl(), redLoopInnerStp(), and reduce_redLoopStp().

◆ reduce_simple_dc()

void reduce_simple_dc	(	SCIP *	scip,
		GRAPH *	g
	)

basic reduction tests for the DCSTP...call only once!

Parameters

scip	SCIP data structure
g	graph data structure

Definition at line 619 of file reduce_simple.c.

References EAT_LAST, graph_edge_del(), graph_get_nNodes(), GRAPH::head, GRAPH::maxdeg, nnodes, GRAPH::oeat, GRAPH::outbeg, STP_DCSTP, GRAPH::stp_type, GRAPH::terms, and TRUE.

Referenced by reduce_dc().

◆ reduce_simple_hc()

SCIP_RETCODE reduce_simple_hc	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	count
	)

basic reduction tests for the HCDSTP

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offfset value
count	pointer to number of reductions

Definition at line 655 of file reduce_simple.c.

References GRAPH::cost, EAT_LAST, FALSE, FARAWAY, flipedge, graph_edge_del(), GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_OKAY, SCIPdebugMessage, SCIPisGE(), SCIPisLT(), GRAPH::source, STP_DHCSTP, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by reduce_hc().

◆ reduce_simple_sap()

SCIP_RETCODE reduce_simple_sap	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	count
	)

basic reduction tests for the SAP

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offfset value
count	pointer to number of reductions

Definition at line 397 of file reduce_simple.c.

References GRAPH::ancestors, GRAPH::cost, EAT_LAST, Edge_anti, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_edge_printInfo(), graph_get_nNodes(), graph_knot_contract(), graph_knot_contractFixed(), graph_knot_del(), graph_knot_printInfo(), graph_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, LT, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPintListNodeAppendCopy(), SCIPisGT(), SCIPqueueCreate(), SCIPqueueFree(), SCIPqueueInsert(), SCIPqueueIsEmpty(), SCIPqueueRemove(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by reduce_sap().

◆ reduce_deleteMultiedges()

SCIP_RETCODE reduce_deleteMultiedges	(	SCIP *	,
		GRAPH *
	)

Definition at line 782 of file reduce_simple.c.

References EAT_LAST, graph_edge_del(), GRAPH::head, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, and TRUE.

◆ reduce_contract0Edges()

SCIP_RETCODE reduce_contract0Edges	(	SCIP *	scip,
		GRAPH *	g,
		int *	solnode,
		SCIP_Bool	savehistory
	)

contract edges of weight zero

Parameters

scip	SCIP data structure
g	graph data structure
solnode	solution node mark or NULL
savehistory	save the history?

Definition at line 733 of file reduce_simple.c.

References GRAPH::cost, EAT_FREE, GRAPH::edges, flipedge, graph_edge_getAncestors(), graph_fixed_addEdge(), graph_knot_contract(), graph_pc_isPcMw(), GRAPH::head, NULL, GRAPH::oeat, GRAPH::pcancestors, SCIP_CALL, SCIP_OKAY, SCIPintListNodeAppendCopy(), SCIPisZero(), and GRAPH::tail.

Referenced by decomposePartialExact(), reduce_redLoopStp(), and reduce_termsepaFull().

◆ reduce_fixedConflicts()

SCIP_RETCODE reduce_fixedConflicts	(	SCIP *	scip,
		const int *	edgestate,
		GRAPH *	g,
		int *	countnew
	)

basic reductions

Parameters

scip	SCIP data structure
edgestate	for propagation or NULL
g	graph data structure
countnew	pointer to number of new reductions (will be initially set to 0)

Definition at line 832 of file reduce_simple.c.

References EAT_FREE, EDGE_BLOCKED, graph_edge_del(), graph_edge_getPseudoAncestors(), graph_edge_nPseudoAncestors(), graph_get_nEdges(), graph_getFixpseudonodes(), graph_getNfixpseudonodes(), graph_pseudoAncestorsGetHashArraySize(), GRAPH::is_packed, NULL, GRAPH::oeat, GRAPH::pseudoancestors, SCIP_CALL, SCIP_OKAY, SCIPallocCleanBufferArray, SCIPdebugMessage, SCIPfreeCleanBufferArray, and TRUE.

Referenced by reduce_redLoopStp().

◆ reduce_cutEdgeTryPrune()

SCIP_RETCODE reduce_cutEdgeTryPrune	(	SCIP *	scip,
		int	cutedge,
		GRAPH *	g,
		SCIP_Bool *	success
	)

try to remove cute edge and prune one side of the graph

Parameters

scip	SCIP data structure
cutedge	the edge
g	graph data structure
success	could we prune the edge?

Definition at line 1001 of file reduce_simple.c.

References cutEdgeProbe(), cutEdgePrune(), FALSE, GRAPH::grad, graph_edge_isInRange(), graph_get_nNodes(), GRAPH::head, Is_term, nnodes, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by nsvExec().

◆ reduce_rpt()

SCIP_RETCODE reduce_rpt	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	count
	)

root proximity terminal test (SAP)

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offset value
count	pointer to number of reductions

Definition at line 916 of file reduce_simple.c.

References GRAPH::cost, EAT_LAST, FALSE, GRAPH::grad, graph_edge_printInfo(), graph_get_nNodes(), graph_knot_contractFixed(), graph_knot_printInfo(), graph_knotIsNWLeaf(), graph_path_execX(), graph_typeIsUndirected(), GT, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, GRAPH::source, STP_NWPTSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by reduce_sap().

◆ reduce_identifyNonLeafTerms()

void reduce_identifyNonLeafTerms	(	SCIP *	scip,
		GRAPH *	g
	)

identify non-leaf terminals and remove extensions

Parameters

scip	SCIP data structure
g	graph data structure

Definition at line 1052 of file reduce_simple.c.

References GRAPH::extended, FALSE, GRAPH::grad, graph_get_nNodes(), graph_pc_evalTermIsNonLeaf(), graph_pc_isPc(), graph_pc_knotIsFixedTerm(), graph_pc_knotIsNonLeafTerm(), graph_pc_term2edgeIsConsistent(), graph_pc_termIsNonLeafTerm(), graph_pc_termToNonLeafTerm(), graph_valid(), Is_term, nnodes, GRAPH::prize, SCIPdebugMessage, SCIPisGE(), GRAPH::source, STP_PCSPG, GRAPH::stp_type, GRAPH::term, and GRAPH::term2edge.

Referenced by reduce_da(), reduce_daPcMw(), and reduce_simple_pc().

◆ reduce_unconnected()

SCIP_RETCODE reduce_unconnected	(	SCIP *	,
		GRAPH *
	)

◆ reduce_unconnectedForDirected()

SCIP_RETCODE reduce_unconnectedForDirected	(	SCIP *	,
		GRAPH *
	)

Definition at line 1134 of file reduce_simple.c.

References GRAPH::grad, graph_get_nNodes(), graph_knot_del(), graph_trail_costAware(), graph_typeIsUndirected(), Is_term, nnodes, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, GRAPH::source, GRAPH::term, and TRUE.

Referenced by daRoundExit(), redcostGraphComputeSteinerTreeDirected(), reduce_boundHopDa(), and reduce_hc().

◆ reduce_unconnectedInfeas()

SCIP_RETCODE reduce_unconnectedInfeas	(	SCIP *	scip,
		SCIP_Bool	beVerbose,
		GRAPH *	g,
		SCIP_Bool *	infeas
	)

remove unconnected vertices and checks whether problem is infeasible

Parameters

scip	SCIP data structure
beVerbose	be verbose?
g	graph data structure
infeas	is problem infeasible?

Definition at line 1164 of file reduce_simple.c.

References EAT_LAST, FALSE, GRAPH::grad, graph_edge_del(), graph_get_nNodes(), graph_trail_arr(), GRAPH::inpbeg, Is_term, nnodes, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, GRAPH::source, GRAPH::term, and TRUE.

Referenced by check_inputgraph(), and propgraphPruneUnconnected().

◆ reduce_articulations()

SCIP_RETCODE reduce_articulations	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixedp,
		int *	nelims
	)

articulation points based, simple reduction

Parameters

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

Definition at line 1130 of file reduce_sepa.c.

References cut_nodes::biconn_ncomps, bidecomposition_cutnodesCompute(), bidecomposition_cutnodesFree(), bidecomposition_cutnodesInit(), bidecomposition_isPossible(), graph_mark(), reduce_nonTerminalComponents(), SCIP_CALL, SCIP_OKAY, and SCIPdebugMessage.

Referenced by reduce_exec(), testBiconnectedComponentsAreFound(), testBiconnectedComponentsAreFound2(), and testBiconnectedComponentsAreFound3().

◆ reduce_bidecomposition()

SCIP_RETCODE reduce_bidecomposition	(	SCIP *	scip,
		GRAPH *	g,
		REDBASE *	redbase,
		int *	solnode,
		SCIP_Bool *	wasDecomposed
	)

decomposition into biconnected components and recursive reduction

Parameters

scip	SCIP data structure
g	graph data structure
redbase	reduction base
solnode	solution nodes or NULL
wasDecomposed	performed recursive reduction?

Definition at line 1039 of file reduce_sepa.c.

References cut_nodes::biconn_ncomps, bidecomposition_cutnodesCompute(), bidecomposition_cutnodesFree(), bidecomposition_cutnodesInit(), bidecomposition_isPossible(), decomposeExec(), FALSE, graph_mark(), graph_typeIsSpgLike(), reduction_base::redsol, reduce_nonTerminalComponents(), reduce_solGetOffsetPointer(), SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, and GRAPH::terms.

Referenced by redLoopInnerStp(), testBiconnectedDecomposition(), testBiconnectedDecomposition2(), and testBiconnectedDecomposition3().

◆ reduce_bidecompositionExact()

SCIP_RETCODE reduce_bidecompositionExact	(	SCIP *	scip,
		GRAPH *	g,
		REDBASE *	redbase,
		int *	solnode,
		int *	nelims
	)

solves smaller connected components to optimality

Parameters

scip	SCIP data structure
g	graph data structure
redbase	reduction base
solnode	solution nodes or NULL
nelims	number of eliminations

Definition at line 1085 of file reduce_sepa.c.

References cut_nodes::biconn_ncomps, bidecomposition_cutnodesCompute(), bidecomposition_cutnodesFree(), bidecomposition_cutnodesInit(), bidecomposition_isPossible(), decomposeExecExact(), graph_mark(), graph_typeIsSpgLike(), reduction_base::redsol, reduce_nonTerminalComponents(), reduce_solGetOffsetPointer(), SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, and GRAPH::terms.

Referenced by reduce_termsepaFull().

◆ reduce_nonTerminalComponents()

SCIP_RETCODE reduce_nonTerminalComponents	(	SCIP *	scip,
		const CUTNODES *	cutnodes,
		GRAPH *	g,
		SCIP_Real *	fixedp,
		int *	nelims
	)

removes non-necessary bi-connected components and creates new terminals from cut-nodes

Parameters

scip	SCIP data structure
cutnodes	cut nodes
g	graph data structure
fixedp	pointer to offset value
nelims	pointer to number of reductions

Definition at line 1004 of file reduce_sepa.c.

References cutNodesTreeBuildSteinerTree(), cutNodesTreeDeleteComponents(), cutNodesTreeExit(), cutNodesTreeInit(), cutNodesTreeMakeTerms(), FALSE, graph_pc_isPcMw(), NULL, SCIP_CALL, SCIP_OKAY, and StpVecGetSize.

Referenced by reduce_articulations(), reduce_bidecomposition(), and reduce_bidecompositionExact().

◆ reduce_simple_mw()

SCIP_RETCODE reduce_simple_mw	(	SCIP *	scip,
		GRAPH *	g,
		int *	solnode,
		SCIP_Real *	fixed,
		int *	nelims
	)

basic reduction tests for the MWCS problem

Parameters

scip	SCIP data structure
g	graph data structure
solnode	array to indicate whether a node is part of the current solution (==CONNECT)
fixed	pointer to offset value
nelims	pointer to number of reductions

Definition at line 1107 of file reduce_pcsimple.c.

References EAT_LAST, FALSE, GE, GRAPH::grad, graph_get_nNodes(), graph_mark(), graph_pc_deleteTerm(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsFixedTerm(), graph_pc_realDegree(), graph_valid(), hasAdjacentTerminals(), GRAPH::head, Is_pseudoTerm, Is_term, isMaxprizeTerm(), LE, GRAPH::mark, mwContract0WeightVertices(), mwContractNonPositiveChain(), mwContractTerminalsChainWise(), mwContractTerminalsSimple(), mwGetNchains(), mwReduceTermDeg1(), nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, pcmwEnumerationTry(), pcmwReduceKnotDeg1(), pcmwReduceTerm0Prize(), GRAPH::prize, reduce_unconnected(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisLE(), GRAPH::source, STP_MWCSP, STP_RMWCSP, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by redLoopInnerMw(), reduce_redLoopMw(), testRmwTerminalContraction(), testRmwTerminalDeg1Contraction1(), testRmwTerminalDeg1Contraction2(), and testRmwTerminalDeg1Contraction3().

◆ reduce_simple_pc()

SCIP_RETCODE reduce_simple_pc	(	SCIP *	scip,
		const int *	edgestate,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	countnew,
		int *	countall,
		int *	solnode
	)

basic reductions for RPCSTP and PCSPG

Parameters

scip	SCIP data structure
edgestate	for propagation or NULL
g	graph data structure
fixed	pointer to offset value
countnew	pointer to number of new reductions (will be initially set to 0)
countall	pointer to number of all reductions or NULL
solnode	solution nodes

Definition at line 1239 of file reduce_pcsimple.c.

References GRAPH::extended, FALSE, GRAPH::grad, graph_get_nNodes(), graph_pc_deleteTerm(), graph_pc_isPc(), graph_pc_knotIsFixedTerm(), graph_pc_knotIsNonLeafTerm(), graph_pc_realDegree(), graph_valid(), Is_pseudoTerm, Is_term, isMaxprizeTerm(), GRAPH::mark, nnodes, NULL, pcContractWithAdjacentTerm(), pcmwEnumerationTry(), pcmwReduceKnotDeg1(), pcmwReduceTerm0Prize(), pcReduceKnotDeg2(), pcReduceTermDeg1(), pcReduceTermDeg2(), GRAPH::prize, reduce_identifyNonLeafTerms(), reduce_unconnected(), rpcTryFullReduce(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisLE(), GRAPH::source, STP_RPCSPG, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by execNvSl(), redLoopInnerPc(), and reduce_redLoopPc().

◆ reduce_removeDeg0NonLeafTerms()

void reduce_removeDeg0NonLeafTerms	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	offsetp
	)

reduction test for PCSPG

Parameters

scip	SCIP data structure
g	graph data structure
offsetp	pointer to offset value

Definition at line 1380 of file reduce_pcsimple.c.

References GRAPH::extended, GRAPH::grad, graph_get_nNodes(), graph_pc_deleteTerm(), graph_pc_isPc(), graph_pc_knotIsNonLeafTerm(), isMaxprizeTerm(), nnodes, and SCIP_Real.

Referenced by extreduce_pseudoDeleteNodes().

◆ reduce_unconnectedRpcRmw()

SCIP_RETCODE reduce_unconnectedRpcRmw	(	SCIP *	,
		GRAPH *	,
		SCIP_Real *
	)

Definition at line 1524 of file reduce_pcsimple.c.

References reduce_unconnectedRpcRmwInfeas(), SCIP_Bool, SCIP_CALL, SCIP_ERROR, and SCIP_OKAY.

Referenced by reduce_impliedProfitBased(), reduce_impliedProfitBasedRpc(), reduce_redLoopPc(), and SCIPStpHeurPruneRun().

◆ reduce_unconnectedRpcRmwInfeas()

SCIP_RETCODE reduce_unconnectedRpcRmwInfeas	(	SCIP *	,
		GRAPH *	,
		SCIP_Real *	,
		SCIP_Bool *
	)

◆ reduce_impliedNodesGet()

void reduce_impliedNodesGet	(	SCIP *	scip,
		const GRAPH *	graph,
		STP_Vectype(int) *	nodes_implications
	)

gets implied nodes for each node

Parameters

scip	SCIP data structure
graph	graph data structure
nodes_implications	array of size \|V\|; returned with implications per node or NULL

Definition at line 937 of file reduce_util.c.

References GRAPH::extended, graph_get_nNodes(), graph_pc_isPcMw(), impliedNodesAddTerm(), Is_term, nnodes, NULL, and GRAPH::term.

Referenced by extreduce_extPermaInit().

◆ reduce_impliedNodesRepair()

void reduce_impliedNodesRepair	(	SCIP *	scip,
		const GRAPH *	graph,
		int	tail,
		int	head,
		STP_Vectype(int) *	nodes_implications
	)

repairs implied nodes list AFTER edge elimination

Parameters

scip	SCIP data structure
graph	graph data structure
tail	tail of eliminated edge
head	head of eliminated edge
nodes_implications	initialized array of size \|V\|

Definition at line 962 of file reduce_util.c.

References GRAPH::extended, graph_knot_isInRange(), graph_pc_isPcMw(), impliedNodesAddTerm(), impliedNodesRemoveTerm(), Is_term, SCIP_Bool, and GRAPH::term.

Referenced by removeEdge(), and replaceEdgeByPath().

◆ reduce_impliedNodesIsValid()

SCIP_Bool reduce_impliedNodesIsValid	(	const GRAPH *	graph,
		const STP_Vectype(int) *	nodes_implications
	)

implied nodes list is valid

Parameters

graph	graph data structure
nodes_implications	initialized array of size \|V\|

Definition at line 996 of file reduce_util.c.

References EAT_LAST, FALSE, GRAPH::grad, graph_get_nNodes(), graph_knot_isInRange(), GRAPH::head, nnodes, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, STP_Vectype, StpVecGetSize, and TRUE.

Referenced by removeEdge(), and replaceEdgeByPath().

◆ reduce_applyPseudoDeletions()

SCIP_RETCODE reduce_applyPseudoDeletions	(	SCIP *	scip,
		const SCIP_Bool *	pseudoDelNodes,
		REDCOST *	redcostdata,
		GRAPH *	graph,
		SCIP_Real *	offsetp,
		int *	nelims
	)

apply pseudo eliminations provided

Parameters

scip	SCIP data structure
pseudoDelNodes	node with pseudo deletable nodes
redcostdata	reduced cost data
graph	graph data structure
offsetp	offset pointer (for PC)
nelims	number of eliminations

Definition at line 1042 of file reduce_util.c.

References shortest_path::dist, EAT_LAST, GRAPH::extended, FALSE, GE, GRAPH::grad, graph_get_nNodes(), graph_knot_delPseudo(), graph_knot_printInfo(), graph_pc_2orgcheck(), graph_pc_2trans(), graph_pc_isPc(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsNonLeafTerm(), graph_valid(), complete_edge::head, GRAPH::head, Is_anyTerm, GRAPH::mark, nnodes, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, redcosts_getCutoffTop(), redcosts_getEdgeCostsTop(), redcosts_getNodeToTermsPathsTop(), redcosts_getRootToNodeDistTop(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, STP_DELPSEUDO_MAXGRAD, STP_DELPSEUDO_MAXNEDGES, GRAPH::term, and TRUE.

Referenced by dapathsReplaceNodes(), and reduce_da().

◆ reduce_blctreeInit()

SCIP_RETCODE reduce_blctreeInit	(	SCIP *	scip,
		GRAPH *	graph,
		BLCTREE **	blctree
	)

initializes BLC tree

Parameters

scip	SCIP
graph	the graph
blctree	to be initialized

Definition at line 1168 of file reduce_util.c.

References blctreeInitBottlenecks(), blctreeInitPrimitives(), graph_mark(), SCIP_CALL, and SCIP_OKAY.

Referenced by reduce_sdInitBiasedBottleneck(), testBLCworksFor3Star(), testBLCworksFor3StarAfterReduction(), and testBLCworksFor5Tree().

◆ reduce_blctreeFree()

void reduce_blctreeFree	(	SCIP *	scip,
		BLCTREE **	blctree
	)

frees BLC tree

Parameters

scip	SCIP
blctree	to be freed

Definition at line 1201 of file reduce_util.c.

References SCIPfreeMemory, and SCIPfreeMemoryArray.

Referenced by reduce_sdFree(), testBLCworksFor3Star(), testBLCworksFor3StarAfterReduction(), and testBLCworksFor5Tree().

◆ reduce_blctreeGetMstNedges()

int reduce_blctreeGetMstNedges ( const BLCTREE * blctree )

gets number of BLC MST edges

Parameters

blctree BLC tree

Definition at line 1218 of file reduce_util.c.

References bottleneck_link_cut_tree::nnodes_curr.

Referenced by nsvInitData(), and reduce_sdprofitUpdateFromBLC().

◆ reduce_blctreeGetMstEdges()

void reduce_blctreeGetMstEdges	(	const GRAPH *	graph,
		const BLCTREE *	blctree,
		int *	edgelist
	)

gets BLC MST edges

Parameters

graph	graph
blctree	BLC tree
edgelist	of size nodes - 1

Definition at line 1230 of file reduce_util.c.

References bottleneck_link_cut_node::edge, graph_get_nNodes(), bottleneck_link_cut_tree::mst, bottleneck_link_cut_tree::nnodes_curr, bottleneck_link_cut_tree::nnodes_org, bottleneck_link_cut_tree::root, and UNKNOWN.

Referenced by nsvInitData(), reduce_sdprofitUpdateFromBLC(), testBLCworksFor3Star(), testBLCworksFor3StarAfterReduction(), and testBLCworksFor5Tree().

◆ reduce_blctreeGetMstEdgesToCutDist()

void reduce_blctreeGetMstEdgesToCutDist	(	const GRAPH *	,
		const BLCTREE *	,
		SCIP_Real *	RESTRICT,
		SCIP_Real *	RESTRICT
	)

Referenced by nsvInitData().

◆ reduce_blctreeGetMstBottlenecks()

void reduce_blctreeGetMstBottlenecks	(	const GRAPH *	graph,
		const BLCTREE *	blctree,
		SCIP_Real *	costlist
	)

gets BLC MST bottleneck costs

Parameters

graph	graph
blctree	BLC tree
costlist	of size nodes - 1

Definition at line 1349 of file reduce_util.c.

References bottleneck_link_cut_node::edge, bottleneck_link_cut_node::edgebottleneck, graph_get_nNodes(), bottleneck_link_cut_tree::mst, bottleneck_link_cut_tree::nnodes_curr, bottleneck_link_cut_tree::nnodes_org, bottleneck_link_cut_tree::root, and UNKNOWN.

Referenced by nsvInitData(), reduce_sdprofitUpdateFromBLC(), testBLCworksFor3Star(), testBLCworksFor3StarAfterReduction(), and testBLCworksFor5Tree().

◆ reduce_blctreeGetMstEdgesState()

void reduce_blctreeGetMstEdgesState	(	const GRAPH *	graph,
		const BLCTREE *	blctree,
		SCIP_Bool *	statelist
	)

returns BLC MST edges state. I.e. whether the ede is between two terminal or not

Parameters

graph	graph
blctree	BLC tree
statelist	of size nodes - 1

Definition at line 1315 of file reduce_util.c.

References bottleneck_link_cut_node::edge, graph_get_nNodes(), bottleneck_link_cut_tree::mst, bottleneck_link_cut_tree::mstedges_isLink, bottleneck_link_cut_tree::nnodes_curr, bottleneck_link_cut_tree::nnodes_org, bottleneck_link_cut_tree::root, and UNKNOWN.

Referenced by nsvInitData().

◆ reduce_blctreeRebuild()

SCIP_RETCODE reduce_blctreeRebuild	(	SCIP *	scip,
		GRAPH *	graph,
		BLCTREE *	blctree
	)

rebuilds BLC tree (needs to be initializes)

Parameters

scip	SCIP
graph	the graph
blctree	to be initialized

Definition at line 1186 of file reduce_util.c.

References blctreeInitBottlenecks(), SCIP_CALL, and SCIP_OKAY.

◆ reduce_dcmstInit()

SCIP_RETCODE reduce_dcmstInit	(	SCIP *	scip,
		int	maxnnodes,
		DCMST **	dcmst
	)

initializes dynamic MST structure

Parameters

scip	SCIP
maxnnodes	maximum number of nodes that can be handled
dcmst	to be initialized

Definition at line 1385 of file reduce_util.c.

References dynamic_complete_minimum_spanning_tree::adjcost_buffer, dynamic_complete_minimum_spanning_tree::edgestore, dynamic_complete_minimum_spanning_tree::maxnnodes, dynamic_complete_minimum_spanning_tree::nodemark, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, and SCIPallocMemoryArray.

Referenced by dcmstTest1(), dcmstTest2(), dcmstTest2b(), dcmstTest3(), and extreduce_extPermaInit().

◆ reduce_dcmstFree()

void reduce_dcmstFree	(	SCIP *	scip,
		DCMST **	dcmst
	)

frees dynamic MST structure

Parameters

scip	SCIP
dcmst	to be initialized

Definition at line 1634 of file reduce_util.c.

References SCIPfreeMemory, and SCIPfreeMemoryArray.

Referenced by dcmstTest1(), dcmstTest2(), dcmstTest2b(), dcmstTest3(), and extreduce_extPermaFree().

◆ reduce_dcmstMstIsValid()

SCIP_Bool reduce_dcmstMstIsValid	(	SCIP *	scip,
		const CSR *	cmst
	)

is the CSR a valid MST on any underlying graph (with number of nodes and edges of the CSR)?

Parameters

scip	SCIP
cmst	the MST candidate

Definition at line 1650 of file reduce_util.c.

References FALSE, graph_csr_isValid(), complete_edge::head, csr_storage::head, csr_storage::nedges_max, nnodes, csr_storage::nnodes, SCIP_Bool, SCIP_CALL_ABORT, SCIPallocMemoryArray, SCIPdebugMessage, SCIPfreeMemoryArray, csr_storage::start, and TRUE.

Referenced by extreduce_mstTopLevelBaseObjValid(), reduce_dcmstAddNode(), reduce_dcmstAddNodeInplace(), reduce_dcmstGet0NodeMst(), reduce_dcmstGet1NodeMst(), reduce_dcmstGet2NodeMst(), reduce_dcmstGetExtWeight(), and reduce_dcmstGetWeight().

◆ reduce_dcmstAddNode()

void reduce_dcmstAddNode	(	SCIP *	scip,
		const CSR *	mst_in,
		const SCIP_Real *	adjcosts,
		DCMST *	dmst,
		CSR *	mst_out
	)

adds node to CSR "mst_in" and saves result in "mst_out"

Parameters

scip	SCIP
mst_in	source
adjcosts	(undirected) adjacency costs for new node
dmst	underlying structure
mst_out	target

Definition at line 1411 of file reduce_util.c.

References dcmstAddNode(), dcmstGetCSRfromStore(), dynamic_complete_minimum_spanning_tree::maxnnodes, csr_storage::nedges_max, csr_storage::nnodes, and reduce_dcmstMstIsValid().

Referenced by dcmstTest1(), dcmstTest2(), dcmstTest2b(), dcmstTest3(), mstExtend(), and ruledOut().

◆ reduce_dcmstAddNodeInplace()

void reduce_dcmstAddNodeInplace	(	SCIP *	scip,
		const SCIP_Real *	adjcosts,
		DCMST *	dmst,
		CSR *	mst
	)

Adds node to CSR "mst". NOTE: There needs to be enough space in CSR arrays for one more node!

Parameters

scip	SCIP
adjcosts	(undirected) adjacency costs for new node
dmst	underlying structure
mst	source/target

Definition at line 1438 of file reduce_util.c.

References dcmstAddNode(), dcmstGetCSRfromStore(), dynamic_complete_minimum_spanning_tree::maxnnodes, csr_storage::nedges_max, csr_storage::nnodes, and reduce_dcmstMstIsValid().

Referenced by mstExtend().

◆ reduce_dcmstGet0NodeMst()

void reduce_dcmstGet0NodeMst	(	SCIP *	scip,
		CSR *	mst
	)

computes MST on 0 node

Parameters

scip	SCIP
mst	MST

Definition at line 1461 of file reduce_util.c.

References EQ, csr_storage::nedges_max, csr_storage::nnodes, reduce_dcmstGetWeight(), reduce_dcmstMstIsValid(), and csr_storage::start.

◆ reduce_dcmstGet1NodeMst()

void reduce_dcmstGet1NodeMst	(	SCIP *	scip,
		CSR *	mst
	)

computes MST on 1 node

Parameters

scip	SCIP
mst	MST

Definition at line 1479 of file reduce_util.c.

References EQ, csr_storage::nedges_max, csr_storage::nnodes, reduce_dcmstGetWeight(), reduce_dcmstMstIsValid(), and csr_storage::start.

Referenced by add1NodeMst(), and dcmstTest1().

◆ reduce_dcmstGet2NodeMst()

void reduce_dcmstGet2NodeMst	(	SCIP *	scip,
		SCIP_Real	edgecost,
		CSR *	mst
	)

computes MST on 2 nodes

Parameters

scip	SCIP
edgecost	edge cost
mst	MST

Definition at line 1498 of file reduce_util.c.

References complete_edge::cost, csr_storage::cost, EQ, csr_storage::head, csr_storage::nedges_max, csr_storage::nnodes, reduce_dcmstGetWeight(), reduce_dcmstMstIsValid(), SCIP_Real, and csr_storage::start.

Referenced by dcmstTest2(), dcmstTest2b(), and dcmstTest3().

◆ reduce_dcmstGet3NodeMst()

void reduce_dcmstGet3NodeMst	(	SCIP *	scip,
		SCIP_Real	edgecost01,
		SCIP_Real	edgecost02,
		SCIP_Real	edgecost12,
		CSR *	mst
	)

computes MST on 3 nodes

Parameters

scip	SCIP
edgecost01	edge cost
edgecost02	edge cost
edgecost12	edge cost
mst	MST

Definition at line 1528 of file reduce_util.c.

◆ reduce_dcmstGetExtWeight()

SCIP_Real reduce_dcmstGetExtWeight	(	SCIP *	scip,
		const CSR *	mst,
		const SCIP_Real *	adjcosts,
		DCMST *	dmst
	)

gets weight of MST extended along given vertex

Parameters

scip	SCIP
mst	MST for which to compute extended weight
adjcosts	(undirected) adjacency costs for new node
dmst	underlying structure

Definition at line 1541 of file reduce_util.c.

References dcmstAddNode(), dcmstGetWeightFromStore(), FARAWAY, GE, GT, csr_storage::nedges_max, csr_storage::nnodes, reduce_dcmstMstIsValid(), and SCIP_Real.

Referenced by mstLevelLeafTryExtMst().

◆ reduce_dcmstGetWeight()

SCIP_Real reduce_dcmstGetWeight	(	SCIP *	scip,
		const CSR *	mst_in
	)

gets weight of MST

Parameters

scip	SCIP
mst_in	source

Definition at line 1573 of file reduce_util.c.

References complete_edge::cost, csr_storage::cost, FARAWAY, GE, GT, csr_storage::nedges_max, reduce_dcmstMstIsValid(), and SCIP_Real.

Referenced by baseMstFinalizeNew(), dcmstTest1(), dcmstTest2(), dcmstTest2b(), dcmstTest3(), mstCompRuleOut(), mstTopLevelBaseValidWeight(), reduce_dcmstGet0NodeMst(), reduce_dcmstGet1NodeMst(), reduce_dcmstGet2NodeMst(), and ruledOut().

◆ reduce_dcmstGetMaxnnodes()

int reduce_dcmstGetMaxnnodes ( const DCMST * dmst )

returns maximum number of nodes

Parameters

dmst	underlying structure

Definition at line 1604 of file reduce_util.c.

References dynamic_complete_minimum_spanning_tree::maxnnodes.

Referenced by mstCompAddLeaf().

◆ reduce_dcmstGetAdjcostBuffer()

SCIP_Real* reduce_dcmstGetAdjcostBuffer ( const DCMST * dmst )

Returns buffer of size 'reduce_dcmstGetMaxnnodes'. NOTE: buffer is never used within any other function, apart from allocation and freeing. NOTE: in debug mode the array is initialized to -1.0

Parameters

dmst	underlying structure

Definition at line 1617 of file reduce_util.c.

References dynamic_complete_minimum_spanning_tree::adjcost_buffer, and dynamic_complete_minimum_spanning_tree::maxnnodes.

Referenced by baseMstBuildNew(), and mstCompAddLeaf().

◆ reduce_starInit()

SCIP_RETCODE reduce_starInit	(	SCIP *	scip,
		int	maxdegree,
		STAR **	star
	)

initializes STAR structure

Parameters

scip	SCIP
maxdegree	maximum node degree that can be handled
star	the star

Definition at line 1725 of file reduce_util.c.

References node_one_hop_star::allStarsChecked, node_one_hop_star::edgeId, node_one_hop_star::edgeIsFailed, node_one_hop_star::edgesPromising, node_one_hop_star::edgesSelected, node_one_hop_star::edgesSelectedPos, node_one_hop_star::edgesSelectedPosPrev, FALSE, node_one_hop_star::maxNodeDegree, node_one_hop_star::nedgesPromising, node_one_hop_star::nodeDegree, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, node_one_hop_star::starcenter, and node_one_hop_star::starDegree.

Referenced by bdkInit(), extCheckNode(), generalStarInit(), pseudodeleteExecute(), testStar3IsCorrect(), testStar4EdgeIsCorrect(), testStar4IsCorrect(), and testStar5IsCorrect().

◆ reduce_starFree()

void reduce_starFree	(	SCIP *	scip,
		STAR **	star
	)

frees STAR structure

Parameters

scip	SCIP
star	the star

Definition at line 1758 of file reduce_util.c.

References node_one_hop_star::edgeId, node_one_hop_star::edgeIsFailed, node_one_hop_star::edgesPromising, node_one_hop_star::edgesSelected, node_one_hop_star::edgesSelectedPos, node_one_hop_star::edgesSelectedPosPrev, SCIPfreeMemory, and SCIPfreeMemoryArray.

Referenced by bdkFree(), extCheckNode(), generalStarExit(), pseudodeleteExecute(), testStar3IsCorrect(), testStar4EdgeIsCorrect(), testStar4IsCorrect(), and testStar5IsCorrect().

◆ reduce_starReset()

void reduce_starReset	(	const GRAPH *	g,
		int	node,
		STAR *	star
	)

resets star data structure with new node data

Parameters

g	graph
node	the node (degree <= STP_DELPSEUDO_MAXGRAD)
star	the star

Definition at line 1781 of file reduce_util.c.

References node_one_hop_star::allStarsChecked, EAT_LAST, node_one_hop_star::edgeId, node_one_hop_star::edgeIsFailed, node_one_hop_star::edgesSelectedPosPrev, FALSE, GRAPH::grad, node_one_hop_star::maxNodeDegree, node_one_hop_star::nedgesPromising, node_one_hop_star::nodeDegree, GRAPH::oeat, GRAPH::outbeg, node_one_hop_star::starcenter, node_one_hop_star::starDegree, node_one_hop_star::starDegreePrev, and starSelectedPositionsReset().

Referenced by bdkTryDegGe4(), pseudodeleteInitStar(), testStar3IsCorrect(), testStar4EdgeIsCorrect(), testStar4IsCorrect(), and testStar5IsCorrect().

◆ reduce_starResetWithEdges()

void reduce_starResetWithEdges	(	const GRAPH *	,
		const	STP_Vectypeint,
		STAR *
	)

Referenced by generalStarCheckInit().

◆ reduce_starGetNext()

const int* reduce_starGetNext	(	STAR *	star,
		int *	nedges
	)

gets next star

Parameters

star	the star (in/out)
nedges	number of edges of next star (out)

Definition at line 1863 of file reduce_util.c.

References node_one_hop_star::allStarsChecked, node_one_hop_star::edgesSelected, reduce_starAllAreChecked(), node_one_hop_star::starDegree, starIsDeg2(), starSelectedEdgesUpdate(), starSelectedPositionsSetNext(), and TRUE.

Referenced by generalStarCheckGetNextStar(), pseudodeleteGetNextStar(), testStar3IsCorrect(), testStar4EdgeIsCorrect(), testStar4IsCorrect(), and testStar5IsCorrect().

◆ reduce_starGetNextAndPosition()

const int* reduce_starGetNextAndPosition	(	STAR *	star,
		int *	position,
		int *	nedges
	)

gets next star

Parameters

star	the star (in/out)
position	array to store the positions
nedges	number of edges of next star (out)

Definition at line 1886 of file reduce_util.c.

References node_one_hop_star::allStarsChecked, node_one_hop_star::edgesSelected, reduce_starAllAreChecked(), node_one_hop_star::starDegree, starIsDeg2(), starSelectedEdgesUpdate(), starSelectedPositionsCopy(), starSelectedPositionsSetNext(), and TRUE.

Referenced by bdkStarLoadNext().

◆ reduce_starGetRuledOutEdges()

const int* reduce_starGetRuledOutEdges	(	STAR *	star,
		int *	nedges
	)

gets ruled out edges after termination

Parameters

star	the star
nedges	number of ruled-out edges

Definition at line 1918 of file reduce_util.c.

References node_one_hop_star::edgeId, node_one_hop_star::edgeIsFailed, node_one_hop_star::edgesPromising, node_one_hop_star::nedgesPromising, node_one_hop_star::nodeDegree, and reduce_starAllAreChecked().

Referenced by bdkTryDegGe4(), and testStar4EdgeIsCorrect().

◆ reduce_starGetCenter()

int reduce_starGetCenter ( const STAR * star )

gets center

Parameters

star	the star (in/out)

Definition at line 1853 of file reduce_util.c.

References node_one_hop_star::starcenter.

◆ reduce_starCurrentSetRuledOut()

void reduce_starCurrentSetRuledOut ( STAR * star )

sets current star to ruled-out

Parameters

star the star

Definition at line 1948 of file reduce_util.c.

References reduce_starAllAreChecked().

◆ reduce_starCurrentSetFailed()

void reduce_starCurrentSetFailed ( STAR * star )

sets current star to failed

Parameters

star the star

Definition at line 1960 of file reduce_util.c.

References node_one_hop_star::edgeIsFailed, node_one_hop_star::edgesSelectedPosPrev, node_one_hop_star::nedgesPromising, node_one_hop_star::starDegreePrev, and TRUE.

Referenced by bdkTryDegGe4(), and testStar4EdgeIsCorrect().

◆ reduce_starHasPromisingEdges()

SCIP_Bool reduce_starHasPromisingEdges ( const STAR * star )

are there edge that might still be ruled out?

Parameters

star the star

Definition at line 1990 of file reduce_util.c.

References node_one_hop_star::nedgesPromising.

Referenced by bdkTryDegGe4(), and testStar4EdgeIsCorrect().

◆ reduce_starAllAreChecked()

SCIP_Bool reduce_starAllAreChecked ( const STAR * star )

have all stars been checked?

Parameters

star the star

Definition at line 2002 of file reduce_util.c.

References node_one_hop_star::allStarsChecked.

Referenced by bdkTryDegGe4(), generalStarCheck(), generalStarCheckGetNextStar(), pseudodeleteAllStarsChecked(), reduce_starCurrentSetRuledOut(), reduce_starGetNext(), reduce_starGetNextAndPosition(), reduce_starGetRuledOutEdges(), testStar3IsCorrect(), testStar4EdgeIsCorrect(), testStar4IsCorrect(), and testStar5IsCorrect().

◆ reduce_sdneighborInit()

SCIP_RETCODE reduce_sdneighborInit	(	SCIP *	scip,
		const GRAPH *	g,
		SDN **	sdn
	)

initializes SDN

Parameters

scip	SCIP
g	graph to initialize from
sdn	SD neighbors

Definition at line 970 of file reduce_sdutil.c.

References special_distance_neighbors::closeterms_distN, special_distance_neighbors::closetermsN, special_distance_neighbors::dijkdata, graph_get_nNodes(), special_distance_neighbors::hitlist, special_distance_neighbors::N, nnodes, special_distance_neighbors::nnodesHit, special_distance_neighbors::nodes_isBlocked, special_distance_neighbors::nodes_maxdist, special_distance_neighbors::nodes_nhits, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, and STP_SDN_NCLOSETERMS.

Referenced by reduce_sdAddNeighborSd().

◆ reduce_sdneighborGetCloseTerms()

void reduce_sdneighborGetCloseTerms	(	const GRAPH *	,
		const SDN *	,
		int	,
		SCIP_Real	,
		int *	RESTRICT,
		SCIP_Real *	RESTRICT,
		int *	RESTRICT
	)

Referenced by sdGetSdNeighbor().

◆ reduce_sdneighborFree()

void reduce_sdneighborFree	(	SCIP *	scip,
		SDN **	sdn
	)

frees SDN

Parameters

scip	SCIP
sdn	SD neighbors

Definition at line 1000 of file reduce_sdutil.c.

References SCIPfreeMemory, and SCIPfreeMemoryArray.

Referenced by reduce_sdFree().

◆ reduce_sdneighborGetBlocked()

const SCIP_Bool* reduce_sdneighborGetBlocked ( const SDN * sdneighbors )

get blocked nodes

Definition at line 915 of file reduce_sdutil.c.

References special_distance_neighbors::nodes_isBlocked.

Referenced by reduce_sdBiasedNeighbor(), and reduce_sdImpLongEdge().

◆ reduce_sdUpdateWithSdNeighbors()

SCIP_RETCODE reduce_sdUpdateWithSdNeighbors	(	SCIP *	scip,
		GRAPH *	g,
		SD *	sddata,
		int *	nupdates
	)

updates SDs by using neighbor argument NOTE: invalidates certain SD routines!

Parameters

scip	SCIP
g	graph to initialize from
sddata	SD
nupdates	number of distance updates

Definition at line 1015 of file reduce_sdutil.c.

References SCIP_OKAY, special_distance_storage::sdneighbors, and sdneighborUpdate().

Referenced by reduce_sdBiasedNeighbor().

◆ reduce_sdprofitInit()

SCIP_RETCODE reduce_sdprofitInit	(	SCIP *	scip,
		const GRAPH *	g,
		SDPROFIT **	sdprofit
	)

initializes SD profit

Parameters

scip	SCIP
g	graph to initialize from
sdprofit	the SD profit

Definition at line 1032 of file reduce_sdutil.c.

References SCIP_CALL, SCIP_OKAY, sdprofitAlloc(), sdprofitBuild(), and TRUE.

Referenced by prInit(), reduce_sdEdgeCliqueStar(), reduce_sdInitBiased(), reduce_sdInitBiasedBottleneck(), reduce_sdStarBiased(), testBiasedTerminalPathsTo4NextFound(), and testSdGraphStrongBiasedDistsAreValid().

◆ reduce_sdprofitInit1stOnly()

SCIP_RETCODE reduce_sdprofitInit1stOnly	(	SCIP *	scip,
		const GRAPH *	g,
		const SCIP_Real *	edgecosts,
		SDPROFIT **	sdprofit
	)

initializes SD profit

Parameters

scip	SCIP
g	graph to initialize from
edgecosts	edge costs (w.r.t graph 'g')
sdprofit	the SD profit

Definition at line 1048 of file reduce_sdutil.c.

References FALSE, SCIP_CALL, SCIP_OKAY, sdprofitAlloc(), and sdprofitBuild1stOnly().

Referenced by pseudodeleteBiasedIsPromising(), and tmBaseInit().

◆ reduce_sdprofitFree()

void reduce_sdprofitFree	(	SCIP *	scip,
		SDPROFIT **	sdprofit
	)

frees SD profit

Parameters

scip	SCIP
sdprofit	the SD profit

Definition at line 1102 of file reduce_sdutil.c.

References special_distance_implied_profit::nodes_bias, special_distance_implied_profit::nodes_bias2, special_distance_implied_profit::nodes_biassource, special_distance_implied_profit::nodes_biassource2, SCIPfreeMemory, SCIPfreeMemoryArray, and SCIPfreeMemoryArrayNull.

Referenced by prFree(), pseudodeleteBiasedIsPromising(), reduce_sdEdgeCliqueStar(), reduce_sdFree(), reduce_sdStarBiased(), testBiasedTerminalPathsTo4NextFound(), testSdGraphStrongBiasedDistsAreValid(), and tmBaseFree().

◆ reduce_sdprofitUpdateFromBLC()

SCIP_RETCODE reduce_sdprofitUpdateFromBLC	(	SCIP *	scip,
		const GRAPH *	g,
		const BLCTREE *	blctree,
		SCIP_Bool	blctree_isUpdated,
		SDPROFIT *	sdprofit
	)

updates implied profits by using exact bottleneck distances

Parameters

scip	SCIP
g	graph
blctree	BLC tree
blctree_isUpdated	BLC tree fresh?
sdprofit	the SD profit

Definition at line 1123 of file reduce_sdutil.c.

References GRAPH::cost, graph_edge_isInRange(), GRAPH::head, Is_term, LE, LT, reduce_blctreeGetMstBottlenecks(), reduce_blctreeGetMstEdges(), reduce_blctreeGetMstNedges(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, sdprofitUpdateNode(), GRAPH::tail, and GRAPH::term.

Referenced by reduce_sdInitBiasedBottleneck(), and reduce_sdprofitBuildFromBLC().

◆ reduce_sdprofitBuildFromBLC()

SCIP_RETCODE reduce_sdprofitBuildFromBLC	(	SCIP *	scip,
		const GRAPH *	g,
		const BLCTREE *	blctree,
		SCIP_Bool	blctree_isUpdated,
		SDPROFIT *	sdprofit
	)

builds implied profits by using exact bottleneck distances

Parameters

scip	SCIP
g	graph
blctree	BLC tree
blctree_isUpdated	BLC tree fresh?
sdprofit	the SD profit

Definition at line 1179 of file reduce_sdutil.c.

References reduce_sdprofitUpdateFromBLC(), SCIP_CALL, SCIP_OKAY, and sdprofitBuild().

Referenced by reduce_impliedProfitBased(), and reduce_impliedProfitBasedRpc().

◆ reduce_sdprofitPrintStats()

void reduce_sdprofitPrintStats	(	const GRAPH *	g,
		const SDPROFIT *	sdprofit
	)

prints SD profit statistics

Parameters

g	graph to initialize from
sdprofit	the SD profit

Definition at line 1065 of file reduce_sdutil.c.

References graph_get_nNodes(), GT, Is_term, nnodes, special_distance_implied_profit::nodes_bias, SCIP_Real, and GRAPH::term.

◆ reduce_sdInit()

SCIP_RETCODE reduce_sdInit	(	SCIP *	scip,
		GRAPH *	g,
		SD **	sd
	)

initializes SD structure

Parameters

scip	SCIP
g	graph NOTE: will mark the graph, thus not const :( terrible design
sd	to initialize

Definition at line 724 of file reduce_sdutil.c.

References special_distance_storage::blctree, FALSE, graph_tpathsInit(), special_distance_storage::hasNeigborUpdate, special_distance_storage::isBiased, NULL, reduce_sdgraphInit(), reduce_sdgraphInitOrderedMstCosts(), SCIP_CALL, SCIP_OKAY, SCIPallocMemory, special_distance_storage::sdgraph, special_distance_storage::sdneighbors, special_distance_storage::sdprofit, and special_distance_storage::terminalpaths.

Referenced by extreduce_distDataInit(), reduce_bdk(), testSdGetterReturnsCorrectSds(), testSdGraphQueriesAreValid(), and testSdRepair().

◆ reduce_sdInitBiased()

SCIP_RETCODE reduce_sdInitBiased	(	SCIP *	scip,
		GRAPH *	g,
		SD **	sd
	)

initializes biased SD structure

Parameters

scip	SCIP
g	graph NOTE: will mark the graph, thus not const :( terrible design
sd	to initialize

Definition at line 751 of file reduce_sdutil.c.

References special_distance_storage::blctree, FALSE, graph_tpathsInitBiased(), special_distance_storage::hasNeigborUpdate, special_distance_storage::isBiased, NULL, reduce_sdgraphInitBiased(), reduce_sdgraphInitOrderedMstCosts(), reduce_sdprofitInit(), SCIP_CALL, SCIP_OKAY, SCIPallocMemory, special_distance_storage::sdgraph, special_distance_storage::sdneighbors, special_distance_storage::sdprofit, special_distance_storage::terminalpaths, and TRUE.

Referenced by reduce_bdkBiased(), testSdBiasedDeletesEdge(), testSdCliqueStarDeg3IsCorrect(), testSdCliqueStarDeg3IsCorrect2(), testSdGraphDistsAreValid(), and testSdGraphDistsAreValid2().

◆ reduce_sdInitBiasedBottleneck()

SCIP_RETCODE reduce_sdInitBiasedBottleneck	(	SCIP *	scip,
		GRAPH *	g,
		SD **	sd
	)

initializes fully biased SD structure

Parameters

scip	SCIP
g	graph NOTE: will mark the graph, thus not const :( terrible design
sd	to initialize

Definition at line 779 of file reduce_sdutil.c.

References special_distance_storage::blctree, FALSE, graph_tpathsInitBiased(), special_distance_storage::hasNeigborUpdate, special_distance_storage::isBiased, NULL, reduce_blctreeInit(), reduce_sdgraphInitBiasedFromTpaths(), reduce_sdgraphInitOrderedMstCosts(), reduce_sdprofitInit(), reduce_sdprofitUpdateFromBLC(), SCIP_CALL, SCIP_OKAY, SCIPallocMemory, special_distance_storage::sdgraph, special_distance_storage::sdneighbors, special_distance_storage::sdprofit, special_distance_storage::terminalpaths, and TRUE.

Referenced by extreduce_distDataInit(), reduce_impliedProfitBased(), reduce_impliedProfitBasedRpc(), testNsvImpliedContractsCutDistEdge(), testNsvImpliedContractsCutDistMiddleEdge(), testNsvImpliedContractsEdge(), testNsvImpliedContractsEdge2(), testNsvImpliedContractsImpliedToTermEdge(), testSdBiasedBottleneckDeletesEdge(), testSdBiasedBottleneckTermPathDeletesEdge(), and testSdBiasedDeletesEdge().

◆ reduce_sdRepair()

SCIP_RETCODE reduce_sdRepair	(	SCIP *	scip,
		int	edge,
		SCIP_Bool	withEdgeReplacement,
		GRAPH *	g,
		SD *	sd
	)

repairs SD structure for imminent edge elimination

Parameters

scip	SCIP
edge	edge to be deleted soon
withEdgeReplacement	with edge replacement?
g	graph NOTE: will mark the graph, thus not const :( terrible design
sd	to be repaired

Definition at line 811 of file reduce_sdutil.c.

References GRAPH::cost, EQ, FARAWAY, flipedge, graph_edge_isInRange(), graph_tpathsRepair(), special_distance_storage::hasNeigborUpdate, special_distance_storage::isBiased, reduce_sdgraphEdgeIsInMst(), reduce_sdgraphFree(), reduce_sdgraphInit(), reduce_sdgraphInitOrderedMstCosts(), SCIP_CALL, SCIP_OKAY, SCIP_Real, special_distance_storage::sdgraph, special_distance_storage::sdneighbors, special_distance_storage::sdprofit, and special_distance_storage::terminalpaths.

Referenced by removeEdge(), replaceEdgeByPath(), and testSdRepair().

◆ reduce_sdRepairSetUp()

SCIP_RETCODE reduce_sdRepairSetUp	(	SCIP *	scip,
		const GRAPH *	g,
		SD *	sd
	)

sets up SD repairing mechanism

Parameters

scip	SCIP
g	graph
sd	to be repaired

Definition at line 853 of file reduce_sdutil.c.

References graph_tpathsRepairSetUp(), SCIP_CALL, SCIP_OKAY, and special_distance_storage::terminalpaths.

Referenced by extreduce_deleteArcs(), extreduce_deleteEdges(), extreduce_deleteGeneralStars(), reduce_termsepaDa(), and testSdRepair().

◆ reduce_sdAddNeighborSd()

SCIP_RETCODE reduce_sdAddNeighborSd	(	SCIP *	scip,
		const GRAPH *	g,
		SD *	sd
	)

adds biased neighbor SD structure

Parameters

scip	SCIP
g	graph
sd	to add to

Definition at line 868 of file reduce_sdutil.c.

References special_distance_storage::hasNeigborUpdate, reduce_sdneighborInit(), SCIP_CALL, SCIP_OKAY, special_distance_storage::sdneighbors, and TRUE.

Referenced by testSdBiasedDeletesEdge().

◆ reduce_sdFree()

void reduce_sdFree	(	SCIP *	scip,
		SD **	sd
	)

frees SD structure

Parameters

scip	SCIP
sd	to free

Definition at line 886 of file reduce_sdutil.c.

References special_distance_storage::blctree, graph_tpathsFree(), reduce_blctreeFree(), reduce_sdgraphFree(), reduce_sdneighborFree(), reduce_sdprofitFree(), SCIPfreeMemory, special_distance_storage::sdgraph, special_distance_storage::sdneighbors, special_distance_storage::sdprofit, and special_distance_storage::terminalpaths.

Referenced by extreduce_distDataFree(), reduce_bdk(), reduce_bdkBiased(), reduce_impliedProfitBased(), reduce_impliedProfitBasedRpc(), testNsvImpliedContractsCutDistEdge(), testNsvImpliedContractsCutDistMiddleEdge(), testNsvImpliedContractsEdge(), testNsvImpliedContractsEdge2(), testNsvImpliedContractsImpliedToTermEdge(), testSdBiasedBottleneckDeletesEdge(), testSdBiasedBottleneckTermPathDeletesEdge(), testSdBiasedDeletesEdge(), testSdCliqueStarDeg3IsCorrect(), testSdCliqueStarDeg3IsCorrect2(), testSdGetterReturnsCorrectSds(), testSdGraphDistsAreValid(), testSdGraphDistsAreValid2(), testSdGraphQueriesAreValid(), and testSdRepair().

◆ reduce_sdGetSdsCliquegraph()

SCIP_RETCODE reduce_sdGetSdsCliquegraph	(	SCIP *	scip,
		const GRAPH *	g,
		int	centernode,
		const int *	cliqueNodeMap,
		DIJK *	dijkdata,
		SD *	sddata,
		GRAPH *	cliquegraph
	)

get SDs between all pairs of marked vertices of given clique graph

Parameters

scip	SCIP
g	the graph
centernode	center node or - 1
cliqueNodeMap	maps clique graph vertices to original ones
dijkdata	data for repeated path computations
sddata	SD
cliquegraph	clique graph to be filled

Definition at line 1394 of file reduce_sd.c.

References GRAPH::edges, GRAPH::knots, SCIP_CALL, SCIP_OKAY, sdCliqueFreeData(), sdCliqueInitData(), sdCliqueUpdateGraphWithStarWalks(), sdGetSdsCliqueTermWalks(), and special_distance_storage::sdprofit.

Referenced by bdkGetCliqueSds(), and testSdGetterReturnsCorrectSds().

◆ reduce_sdgraphInit()

SCIP_RETCODE reduce_sdgraphInit	(	SCIP *	scip,
		const GRAPH *	g,
		SDGRAPH **	sdgraph
	)

initializes SD graph

Parameters

scip	SCIP
g	graph to initialize from
sdgraph	the SD graph

Definition at line 1764 of file reduce_sdgraph.c.

References NULL, SCIP_CALL, SCIP_OKAY, sdgraphAlloc(), sdgraphBuildDistgraph(), sdgraphFinalize(), sdgraphMstBuild(), sdgraphMstMarkOrgEdges(), and sdqueryInit().

Referenced by reduce_sdInit(), and reduce_sdRepair().

◆ reduce_sdgraphInitFromDistGraph()

SCIP_RETCODE reduce_sdgraphInitFromDistGraph	(	SCIP *	scip,
		const GRAPH *	g,
		GRAPH *	distgraph,
		int *	node2dist,
		SDGRAPH **	sdgraph
	)

initializes SD graph

Parameters

scip	SCIP
g	graph to initialize from
distgraph	distance graph
node2dist	map
sdgraph	the SD graph

Definition at line 1788 of file reduce_sdgraph.c.

References special_distance_graph::distgraph, SCIP_CALL, SCIP_OKAY, sdgraphAllocRestricted(), sdgraphMstBuild(), and sdqueryInit().

Referenced by reduce_sd().

◆ reduce_sdgraphInitBiased()

SCIP_RETCODE reduce_sdgraphInitBiased	(	SCIP *	scip,
		const GRAPH *	g,
		const SDPROFIT *	sdprofit,
		SDGRAPH **	sdgraph
	)

initializes biased SD graph

Parameters

scip	SCIP
g	graph to initialize from
sdprofit	SD profit
sdgraph	the SD graph

Definition at line 1811 of file reduce_sdgraph.c.

References SCIP_CALL, SCIP_OKAY, sdgraphAlloc(), sdgraphBuildDistgraph(), sdgraphFinalize(), sdgraphMstBuild(), sdgraphMstMarkOrgEdges(), and sdqueryInit().

Referenced by reduce_sdInitBiased().

◆ reduce_sdgraphInitBiasedFromTpaths()

SCIP_RETCODE reduce_sdgraphInitBiasedFromTpaths	(	SCIP *	scip,
		GRAPH *	g,
		const SDPROFIT *	sdprofit,
		const TPATHS *	tpaths,
		SDGRAPH **	sdgraph
	)

initializes biased SD graph from given terminal paths

Parameters

scip	SCIP
g	graph to initialize from
sdprofit	SD profit
tpaths	terminal paths
sdgraph	the SD graph

Definition at line 1836 of file reduce_sdgraph.c.

References FALSE, SCIP_CALL, SCIP_OKAY, SCIPfreeMemoryArray, sdgraphAlloc(), sdgraphBuildDistgraphFromTpaths(), sdgraphMstBuild(), sdgraphUpdateDistgraphFromTpaths(), and sdqueryInit().

Referenced by reduce_sdInitBiasedBottleneck(), and testSdGraphStrongBiasedDistsAreValid().

◆ reduce_sdgraphGetMaxCost()

SCIP_Real reduce_sdgraphGetMaxCost ( const SDGRAPH * sdgraph )

return maximum MST edge cost

Parameters

sdgraph the SD graph

Definition at line 1867 of file reduce_sdgraph.c.

References GE, and special_distance_graph::mstmaxcost.

Referenced by generalStarSetUp(), reduce_sdBiased(), reduce_sdBiasedNeighbor(), reduce_sdImpLongEdge(), and sdGetSdsCliqueTermWalks().

◆ reduce_sdgraphGetOrderedMstCosts()

const SCIP_Real* reduce_sdgraphGetOrderedMstCosts ( const SDGRAPH * sdgraph )

returns all MST costs in descending order

Parameters

sdgraph the SD graph

Definition at line 1989 of file reduce_sdgraph.c.

References special_distance_graph::mstcosts, special_distance_graph::mstmaxcost, and reduce_sdgraphHasOrderedMstCosts().

Referenced by bdkStarGetCombinedSdCost(), bdkStarIsReplacableDeg3(), bdkStarIsSdTreeReplacable(), testSdGraphDistsAreValid(), testSdGraphDistsAreValid2(), and testSdGraphStrongBiasedDistsAreValid().

◆ reduce_sdgraphGetOrgnodesToSdMap()

const int* reduce_sdgraphGetOrgnodesToSdMap ( const SDGRAPH * sdgraph )

returns mapping from original nodes to distance graph nodes

Parameters

sdgraph the SD graph

Definition at line 2001 of file reduce_sdgraph.c.

References special_distance_graph::nodemapOrgToDist.

Referenced by sdgraphInsertEdge().

◆ reduce_sdgraphInitOrderedMstCosts()

void reduce_sdgraphInitOrderedMstCosts ( SDGRAPH * sdgraph )

initializes all MST costs in descending order

Parameters

sdgraph the SD graph

Definition at line 1938 of file reduce_sdgraph.c.

References special_distance_graph::mstcosts, special_distance_graph::mstcostsReady, special_distance_graph::mstmaxcost, reduce_sdgraphHasOrderedMstCosts(), sdgraphMstSortCosts(), and TRUE.

Referenced by reduce_sdInit(), reduce_sdInitBiased(), reduce_sdInitBiasedBottleneck(), reduce_sdRepair(), testSdGraphDistsAreValid(), testSdGraphDistsAreValid2(), testSdGraphQueriesAreValid(), and testSdGraphStrongBiasedDistsAreValid().

◆ reduce_sdgraphGetMstHalfMark()

const STP_Bool* reduce_sdgraphGetMstHalfMark ( const SDGRAPH * sdgraph )

returns edge mark

Parameters

sdgraph the SD graph

Definition at line 1879 of file reduce_sdgraph.c.

References special_distance_graph::halfedge_isInMst, and reduce_sdgraphHasMstHalfMark().

Referenced by bdkInit(), generalStarSetUp(), and reduce_sdImpLongEdge().

◆ reduce_sdgraphHasMstHalfMark()

SCIP_Bool reduce_sdgraphHasMstHalfMark ( const SDGRAPH * sdgraph )

has edge mark?

Parameters

sdgraph the SD graph

Definition at line 1891 of file reduce_sdgraph.c.

References special_distance_graph::edgemarkReady, FALSE, special_distance_graph::halfedge_isInMst, and TRUE.

Referenced by bdkInit(), reduce_sdBiasedNeighbor(), reduce_sdgraphEdgeIsInMst(), reduce_sdgraphGetMstHalfMark(), and reduce_sdImpLongEdge().

◆ reduce_sdgraphEdgeIsInMst()

SCIP_Bool reduce_sdgraphEdgeIsInMst	(	const SDGRAPH *	sdgraph,
		int	edge
	)

is edge in current SD MST?

Parameters

sdgraph	the SD graph
edge	edge

Definition at line 1909 of file reduce_sdgraph.c.

References special_distance_graph::halfedge_isInMst, and reduce_sdgraphHasMstHalfMark().

Referenced by extreduce_deleteEdges(), generalStarSetUp(), pathreplaceExec(), and reduce_sdRepair().

◆ reduce_sdgraphHasOrderedMstCosts()

SCIP_Bool reduce_sdgraphHasOrderedMstCosts ( const SDGRAPH * sdgraph )

MST costs in descending order available?

Parameters

sdgraph the SD graph

Definition at line 1924 of file reduce_sdgraph.c.

References special_distance_graph::mstcosts, and special_distance_graph::mstcostsReady.

Referenced by reduce_sdgraphGetOrderedMstCosts(), and reduce_sdgraphInitOrderedMstCosts().

◆ reduce_sdgraphGetSd()

SCIP_Real reduce_sdgraphGetSd	(	int	term1,
		int	term2,
		SDGRAPH *	sdgraph
	)

Gets special distance (e.g. bottleneck distance) from distance graph. Only works if both nodes are terminals!

Parameters

term1	node 1
term2	node 2
sdgraph	the SD graph

Definition at line 1958 of file reduce_sdgraph.c.

References EQ, special_distance_graph::mstcosts, special_distance_graph::mstsdist, special_distance_graph::nnodesorg, special_distance_graph::nodemapOrgToDist, sdqueryFullGetSd(), sdqueryGetSd(), UNKNOWN, and special_distance_graph::usingRMQ.

Referenced by getSd(), reduce_sd(), sdGetSd(), sdGetSdNeighbor(), sdneighborUpdateNode(), and testSdGraphQueriesAreValid().

◆ reduce_sdgraphFree()

void reduce_sdgraphFree	(	SCIP *	scip,
		SDGRAPH **	sdgraph
	)

frees SD graph

Parameters

scip	SCIP
sdgraph	the SD graph

Definition at line 2055 of file reduce_sdgraph.c.

References special_distance_graph::distgraph, graph_free(), special_distance_graph::halfedge_isInMst, special_distance_graph::mstcosts, special_distance_graph::mstsdist, special_distance_graph::nodemapOrgToDist, SCIPfreeMemory, SCIPfreeMemoryArray, SCIPfreeMemoryArrayNull, special_distance_graph::sdmst, sdqueryFree(), and TRUE.

Referenced by reduce_sdFree(), reduce_sdRepair(), and testSdGraphStrongBiasedDistsAreValid().

◆ reduce_sdgraphFreeFromDistGraph()

void reduce_sdgraphFreeFromDistGraph	(	SCIP *	scip,
		SDGRAPH **	sdgraph
	)

frees SD graph, but does not free actual graph and node-map (assumed to be non-owned)

Parameters

scip	SCIP
sdgraph	the SD graph

Definition at line 2080 of file reduce_sdgraph.c.

References special_distance_graph::halfedge_isInMst, special_distance_graph::mstcosts, special_distance_graph::mstsdist, SCIPfreeMemory, SCIPfreeMemoryArray, special_distance_graph::sdmst, and sdqueryFree().

Referenced by reduce_sd().

◆ reduce_sdgraphInsertEdge()

void reduce_sdgraphInsertEdge	(	SCIP *	,
		int	,
		int	,
		SCIP_Real	,
		int	,
		int *	RESTRICT,
		SDGRAPH *	,
		SCIP_Bool *
	)

Referenced by sdgraphInsertEdge().

◆ reduce_sdgraphMstBuild()

SCIP_RETCODE reduce_sdgraphMstBuild	(	SCIP *	scip,
		const GRAPH *	g,
		SDGRAPH *	g_sd
	)

Builds MST on distance graph. NOTE: just a wrapper, should only be used by other reduce_sd* methods

Parameters

scip	SCIP
g	graph to initialize from
g_sd	the SD graph

Definition at line 2032 of file reduce_sdgraph.c.

References SCIP_CALL, SCIP_OKAY, and sdgraphMstBuild().

Referenced by sdneighborUpdate().

◆ reduce_sdgraphMstSortCosts()

void reduce_sdgraphMstSortCosts ( SDGRAPH * g_sd )

Builds MST costs (ordered) for distance graph NOTE: just a wrapper, should only be used by other reduce_sd* methods

Parameters

g_sd	the SD graph

Definition at line 2046 of file reduce_sdgraph.c.

References sdgraphMstSortCosts().

Referenced by sdneighborUpdate().

◆ reduce_termcompInit()

SCIP_RETCODE reduce_termcompInit	(	SCIP *	scip,
		const GRAPH *	g,
		COMPBUILDER *	builder,
		TERMCOMP **	termcomp
	)

initializes

Parameters

scip	SCIP data structure
g	graph data structure
builder	initializer
termcomp	to initialize

Definition at line 982 of file reduce_termsepa.c.

Referenced by processComponent().

◆ reduce_termcompFree()

void reduce_termcompFree	(	SCIP *	scip,
		TERMCOMP **	termcomp
	)

frees

Parameters

scip	SCIP data structure
termcomp	to initialize

Definition at line 1039 of file reduce_termsepa.c.

References terminal_separator_component::edgemap_subToOrg, graph_free(), terminal_separator_component::nodemap_orgToSub, terminal_separator_component::nodemap_subToOrg, terminal_separator_component::nodes_mark, SCIPfreeMemory, SCIPfreeMemoryArray, SCIPfreeMemoryArrayNull, StpVecFree, terminal_separator_component::subgraph, terminal_separator_component::subsolbottleneck, terminal_separator_component::subsolution, tbottleneckFree(), and TRUE.

Referenced by processComponent().

◆ reduce_termcompInitTbottleneck()

SCIP_RETCODE reduce_termcompInitTbottleneck	(	SCIP *	scip,
		const int *	subsoledges,
		TERMCOMP *	termcomp
	)

initializes tree bottleneck for terminal component

Parameters

scip	SCIP data structure
subsoledges	solution tree to be represented
termcomp	to initialize for

Definition at line 1019 of file reduce_termsepa.c.

References SCIP_CALL, SCIP_OKAY, terminal_separator_component::subgraph, terminal_separator_component::subsolbottleneck, and tbottleneckInit().

Referenced by termcompComputeSubgraphSol().

◆ reduce_termcompBuildSubgraph()

SCIP_RETCODE reduce_termcompBuildSubgraph	(	SCIP *	scip,
		GRAPH *	orggraph,
		TERMCOMP *	termcomp
	)

builds extended subgraph with BLOCKED weighted edges between terminal-separator nodes

Parameters

scip	SCIP data structure
orggraph	graph data structure
termcomp	component

Definition at line 818 of file reduce_termsepa.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, subgraphBuild(), and subgraphIdentify().

Referenced by processComponent().

◆ reduce_termcompBuildSubgraphWithSds()

SCIP_RETCODE reduce_termcompBuildSubgraphWithSds	(	SCIP *	scip,
		GRAPH *	orggraph,
		EXTPERMA *	extperma,
		TERMCOMP *	termcomp
	)

builds extended subgraph with SD weighted edges between terminal-separator nodes

Parameters

scip	SCIP data structure
orggraph	graph data structure
extperma	extension data
termcomp	component

Definition at line 799 of file reduce_termsepa.c.

References SCIP_Bool, SCIP_CALL, SCIP_OKAY, subgraphBuild(), subgraphIdentify(), and TRUE.

Referenced by processComponent().

◆ reduce_termcompChangeSubgraphToBottleneck()

SCIP_RETCODE reduce_termcompChangeSubgraphToBottleneck	(	SCIP *	scip,
		GRAPH *	g,
		TERMCOMP *	termcomp,
		SCIP_Bool *	success
	)

Changes weights between terminal separator nodes to bottlenecks. NOTE: also computes the bottleneck distances, so potentially expensive!

Parameters

scip	SCIP data structure
g	graph data structure
termcomp	component
success	pointer to store whether computation was successful (OUT)

Definition at line 837 of file reduce_termsepa.c.

References b, terminal_separator_component::builder, GRAPH::cost, EAT_LAST, FALSE, flipedge, getExtBottleneckDist(), graph_get_nNodes(), graph_knot_isInRange(), graph_mark(), graph_path_exec(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, MARK_NONACTIVE, MARK_SEPARATOR, MARK_SUBNODE, MST_MODE, nnodes, terminal_separator_component::nodemap_orgToSub, terminal_separator_component::nodemap_subToOrg, terminial_component_initializer::nodes_bdist, terminal_separator_component::nodes_mark, terminial_component_initializer::nsepatterms, GRAPH::oeat, GRAPH::outbeg, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, terminial_component_initializer::sepaterms, terminal_separator_component::subgraph, terminal_separator_component::subsolbottleneck, GRAPH::term, and TRUE.

Referenced by processComponent(), and sepafullBuildSolcands().

◆ reduce_termsepaGetNextComp()

void reduce_termsepaGetNextComp	(	SCIP *	scip,
		const GRAPH *	g,
		TERMSEPAS *	termsepas,
		COMPBUILDER *	builder,
		SCIP_Bool *	compWasFound
	)

gets next separator component

Parameters

scip	SCIP data structure
g	graph data structure
termsepas	terminal separator store
builder	builder
compWasFound	was new component found?

Definition at line 1072 of file reduce_termsepa.c.

Referenced by reduce_termsepaDaWithExperma(), and reduce_termsepaFull().

◆ reduce_compbuilderInit()

SCIP_RETCODE reduce_compbuilderInit	(	SCIP *	scip,
		const GRAPH *	g,
		COMPBUILDER **	compbuilder
	)

initializes

Parameters

scip	SCIP data structure
g	graph data structure
compbuilder	to initialize

Definition at line 716 of file reduce_termsepa.c.

Referenced by initHelpers().

◆ reduce_compbuilderFree()

void reduce_compbuilderFree	(	SCIP *	scip,
		COMPBUILDER **	compbuilder
	)

frees

Parameters

scip	SCIP data structure
compbuilder	to free

Definition at line 751 of file reduce_termsepa.c.

References terminial_component_initializer::nodes_bdist, SCIPfreeMemory, and SCIPfreeMemoryArray.

Referenced by freeHelpers().

◆ reduce_compbuilderGetSubNodesRatio()

SCIP_Real reduce_compbuilderGetSubNodesRatio ( const COMPBUILDER * compbuilder )

gets nodes ratio of subgraph

Parameters

compbuilder builder

Definition at line 765 of file reduce_termsepa.c.

References GT, LE, terminial_component_initializer::ncomponentnodes, terminial_component_initializer::ngraphnodes, and SCIP_Real.

Referenced by sepafullSolcandsArePromising(), termcompComputeSubgraphSol(), termcompIsPromising(), and termcompReduce().

◆ reduce_compbuilderPrintSeparators()

void reduce_compbuilderPrintSeparators	(	const GRAPH *	orggraph,
		const COMPBUILDER *	compbuilder
	)

prints

Parameters

orggraph	graph data structure
compbuilder	builder

Definition at line 779 of file reduce_termsepa.c.

References graph_knot_isInRange(), graph_knot_printInfo(), terminial_component_initializer::nsepatterms, and terminial_component_initializer::sepaterms.

Referenced by processComponent().

◆ reduce_termcompChangeSubgraphToOrgCosts()

void reduce_termcompChangeSubgraphToOrgCosts	(	const GRAPH *	orggraph,
		TERMCOMP *	termcomp
	)

changes weights between terminal separator nodes to original costs (or BLOCKED)

Parameters

orggraph	graph data structure
termcomp	component

Definition at line 930 of file reduce_termsepa.c.

References BLOCKED, terminal_separator_component::builder, GRAPH::cost, EAT_LAST, terminal_separator_component::edgemap_subToOrg, GRAPH::edges, EQ, GRAPH::head, Is_term, terminial_component_initializer::nsepatterms, GRAPH::oeat, GRAPH::outbeg, terminal_separator_component::subgraph, GRAPH::tail, and GRAPH::term.

Referenced by sepafullBuildSolcands().

◆ reduce_termsepaDaWithExperma()

SCIP_RETCODE reduce_termsepaDaWithExperma	(	SCIP *	scip,
		GRAPH *	g,
		EXTPERMA *	extperma,
		SCIP_Bool *	pseudoDelNodes,
		int *	nelims
	)

terminal-separator/dual-ascent reduction method given extperma todo maybe we want to also give terminal separators to be able to reuse them?

Parameters

scip	SCIP data structure
g	graph data structure
extperma	extension data
pseudoDelNodes	array to mark pseudo deletable nodes or NULL (OUT)
nelims	number of eliminations (OUT)

Definition at line 441 of file reduce_termsepada.c.

References BMSclearMemoryArray, terminial_component_initializer::componentnumber, freeHelpers(), initHelpers(), GRAPH::knots, mincut_findTerminalSeparators(), processComponent(), extension_data_permanent::randnumgen, reduce_termsepaGetNextComp(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, termcompIsPromising(), and GRAPH::terms.

Referenced by extreduce_deleteEdges(), and reduce_termsepaDa().

◆ reduce_termsepaDa()

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

terminal-separator/dual-ascent reduction method NOTE: intended to be used for debugging and unit tests, since creation of SD data is expensive and is best combined with extended reduction techniques

Parameters

scip	SCIP data structure
g	graph data structure
nelims	number of eliminations

Definition at line 492 of file reduce_termsepada.c.

References extension_data_permanent::distdata_default, extred_fast, extreduce_distDataInit(), extreduce_exit(), extreduce_extPermaInit(), FALSE, graph_init_dcsr(), NULL, reduce_sdRepairSetUp(), reduce_termsepaDaWithExperma(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, distance_data::sdistdata, GRAPH::terms, and TRUE.

◆ reduce_termsepaFull()

SCIP_RETCODE reduce_termsepaFull	(	SCIP *	scip,
		GRAPH *	g,
		int *	solnode,
		REDBASE *	redbase,
		int *	nelims
	)

terminal-separator reduction method using optimal (full) solution of sub-problems

Parameters

scip	SCIP data structure
g	graph data structure
solnode	solution nodes mark or NULL
redbase	reduction base
nelims	number of eliminations

Definition at line 1107 of file reduce_termsepafull.c.

References terminial_component_initializer::componentnumber, freeHelpers(), initHelpers(), mincut_findTerminalSeparators(), mincut_termsepasGetNall(), processComponent(), reduce_bidecompositionExact(), reduce_contract0Edges(), reduce_termsepaGetNextComp(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPdebugMessage, SCIPfreeRandom(), termcompIsPromising(), GRAPH::terms, and TRUE.

Referenced by reduce_redLoopStp().

SCIP

Detailed Description

Functions

Function Documentation

◆ reduce_getMinNreductions()

◆ reduce_baseInit()

◆ reduce_baseFree()

◆ reduce_stp()

◆ reduce_pc()

◆ reduce_mw()

◆ reduce_hc()

◆ reduce_sap()

◆ reduce_nw()

◆ reduce_dc()

◆ reduce_redLoopStp()

◆ reduce_redLoopPc()

◆ reduce_redLoopMw()

◆ reduce_exec()

◆ reduce_sollocalInit()

◆ reduce_sollocalFree()

◆ reduce_sollocalGetSolnode()

◆ reduce_sollocalSetOffset()

◆ reduce_sollocalUpdateUpperBound()

◆ reduce_sollocalUpdateNodesol()

◆ reduce_sollocalGetUpperBound()

◆ reduce_sollocalGetUpperBoundWithOffset()

◆ reduce_sollocalHasUpperBound()

◆ reduce_sollocalUsesNodesol()

◆ reduce_sollocalRebuildTry()

◆ reduce_solInit()

◆ reduce_solFree()

◆ reduce_solInitLocal()

◆ reduce_solFinalizeLocal()

◆ reduce_solReInitLocal()

◆ reduce_solPack()

◆ reduce_solLevelAdd()

◆ reduce_solLevelTopUpdate()

◆ reduce_solLevelTopFinalize()

◆ reduce_solLevelTopRemove()

◆ reduce_solLevelTopClean()

◆ reduce_solLevelTopTransferSolBack()

◆ reduce_solLevelTopTransferSolTo()

◆ reduce_solSetOffset()

◆ reduce_solGetOffset()

◆ reduce_solGetUpperBoundWithOffset()

◆ reduce_solGetNodesolPointer()

◆ reduce_solUsesNodesol()

◆ reduce_solGetOffsetPointer()

◆ reduce_solGetEdgesol()

◆ reduce_solAddNodesol()

◆ reduce_solGetNodesol()

◆ reduce_impliedProfitBased()

◆ reduce_impliedProfitBasedRpc()

◆ reduce_ans()

◆ reduce_ansAdv()

◆ reduce_ansAdv2()

◆ reduce_nnp()

◆ reduce_nv()

◆ reduce_nvAdv()

◆ reduce_sl()

◆ reduce_nsvImplied()

◆ reduce_nsvImpliedRecord()

◆ reduce_cnsAdv()

◆ reduce_npv()

◆ reduce_chain2()

◆ reduce_sdEdgeCliqueStar()

◆ reduce_sdImpLongEdge()

◆ reduce_sdsp()

◆ reduce_sdStar()

◆ reduce_sdStarBiased()

◆ reduce_sdStarBiasedWithProfit()

◆ reduce_sdStarPc()

◆ reduce_sdStarPc2()

◆ reduce_sdWalk()

◆ reduce_sdWalk_csr()

◆ reduce_sdWalkTriangle()

◆ reduce_sdWalkExt()

◆ reduce_sdWalkExt2()

◆ reduce_sdspSap()

◆ reduce_sd()