Scippy

SCIP

Solving Constraint Integer Programs

reduce.h File Reference

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_Realreduce_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_Realreduce_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_Boolreduce_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_Realreduce_sdgraphGetOrderedMstCosts (const SDGRAPH *)
 
const int * reduce_sdgraphGetOrgnodesToSdMap (const SDGRAPH *)
 
void reduce_sdgraphInitOrderedMstCosts (SDGRAPH *)
 
const STP_Boolreduce_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
ggraph data structure
lowerboundlower 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()

◆ reduce_baseFree()

◆ 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
scipSCIP data structure
ggraph data structure
redsolprimal solution container
minelimsminimal number of edges to be eliminated in order to reiterate reductions
dualascentperform dual-ascent reductions?
nodereplacingshould node replacement (by edges) be performed?
userecuse recombination heuristic?
usestrongredsallow 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
scipSCIP data structure
redsolsolution storage
ggraph data structure
minelimsminimal number of edges to be eliminated in order to reiterate reductions
advancedperform advanced (e.g. dual ascent) reductions?
userecuse recombination heuristic?
nodereplacingshould node replacement (by edges) be performed?
usestrongredsallow 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
scipSCIP data structure
redsolsolution storage
ggraph data structure
minelimsminimal number of edges to be eliminated in order to reiterate reductions
advancedperform advanced reductions?
userecuse recombination heuristic?
usestrongredsallow 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
scipSCIP data structure
ggraph data structure
fixedpointer to store the offset value
minelimsminimal 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
scipSCIP data structure
ggraph data structure
dualascentperform dual-ascent reductions?
fixedpointer to store the offset value
minelimsminimal 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
scipSCIP data structure
ggraph data structure
fixedpointer to store the offset value
minelimsminimal 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
scipSCIP data structure
ggraph data structure
fixedpointer to store the offset value
minelimsminimal 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()

◆ 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
scipSCIP data structure
redsolsolution contained
ggraph data structure
vnoiVoronoi data structure
pathpath data structure
nodearrrealnodes-sized array
heapshortest path array
statevoronoi base array
vbasenodes-sized array
nodearrintnode-sized array
edgearrintedge-sized array
nodearrint2nodes-sized array
nodearrcharnodes-sized array
dualascentdo dual-ascent reduction?
breddo bound-based reduction?
tryrpctry to transform to rpc?
reductboundminimal number of edges to be eliminated in order to reiterate reductions
userecuse recombination heuristic?
nodereplacingshould node replacement (by edges) be performed?
usestrongredsallow 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
scipSCIP data structure
redsolsolution contained
ggraph data structure
vnoiVoronoi data structure
nodearrrealnodes-sized array
stateshortest path array
vbasevoronoi base array
nodearrintnodes-sized array
nodearrcharnodes-sized array
advanceddo advanced reduction?
breddo bound-based reduction?
tryrmwtry to convert problem to RMWCSP? Only possible if advanced = TRUE and userec = TRUE
redboundminimal number of edges to be eliminated in order to reiterate reductions
userecuse recombination heuristic?
usestrongredsallow 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 
)

◆ reduce_sollocalInit()

◆ reduce_sollocalFree()

void reduce_sollocalFree ( SCIP scip,
REDSOLLOCAL **  sollocal 
)

frees

Parameters
scipSCIP data structure
sollocalto 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)

◆ reduce_sollocalSetOffset()

void reduce_sollocalSetOffset ( SCIP_Real  offsetnew,
REDSOLLOCAL sollocal 
)

◆ reduce_sollocalUpdateUpperBound()

void reduce_sollocalUpdateUpperBound ( SCIP_Real  ubnew,
REDSOLLOCAL sollocal 
)

sets new sollocal bound if better than old one

Parameters
ubnewnew upper bound, not including offset!
sollocalsollocal

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 
)

◆ reduce_sollocalGetUpperBound()

SCIP_Real reduce_sollocalGetUpperBound ( const REDSOLLOCAL sollocal)

gets upper bound; not including (last set) offset

Parameters
sollocalsollocal

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
sollocalsollocal

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
sollocalsollocal

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
sollocalsollocal

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

◆ reduce_solInit()

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

◆ reduce_solFree()

◆ 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
scipSCIP data structure
ggraph data structure
redsolreduction solution
redsollocal_outpointer 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()

◆ reduce_solReInitLocal()

void reduce_solReInitLocal ( const GRAPH g,
REDSOL redsol 
)

reinitalizes local after it has been finished

Parameters
ggraph data structure
redsolreduction 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
ggraph data structure
nodes_old2packedmap to packed node IDs
nnodes_packednumber of packed nodes
redsolsollocal

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
scipSCIP data structure
ggraph data structure
redsolsollocal

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
scipSCIP data structure
subgraphgraph data structure
redsolreduction 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
scipSCIP data structure
ggraph data structure
redsolsollocal

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
scipSCIP data structure
redsolreduction 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
scipSCIP data structure
redsolsollocal

Definition at line 997 of file reduce_sol.c.

References redlevelClean(), and redsolGetNlevels().

Referenced by decomposeReduceSubDoIt().

◆ reduce_solLevelTopTransferSolBack()

◆ reduce_solLevelTopTransferSolTo()

SCIP_RETCODE reduce_solLevelTopTransferSolTo ( const int *  nodemap_orgToTop,
REDSOL redsol 
)

◆ reduce_solSetOffset()

void reduce_solSetOffset ( SCIP_Real  offsetnew,
REDSOL redsol 
)

sets offset

Parameters
offsetnewnew offset
redsolsolution

Definition at line 1124 of file reduce_sol.c.

References GE.

Referenced by decomposeReduceSubDoIt().

◆ reduce_solGetOffset()

SCIP_Real reduce_solGetOffset ( const REDSOL redsol)

◆ reduce_solGetUpperBoundWithOffset()

SCIP_Real reduce_solGetUpperBoundWithOffset ( const REDSOL redsol)

◆ reduce_solGetNodesolPointer()

const int* reduce_solGetNodesolPointer ( const REDSOL redsol)

gets

Parameters
redsolsolution

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
redsolsolution

Definition at line 1236 of file reduce_sol.c.

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

◆ reduce_solGetOffsetPointer()

◆ 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
scipSCIP data structure
ggraph data structure
redsolsolution
solvalFARAWAY if no solution available
edgesolsolution 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
ggraph data structure
nodesolincoming solution
redsolsolution

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
ggraph data structure
redsolsolution
nodesolsolution 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
scipSCIP data structure
edgelimitlimit for star test
ggraph structure
solnodenode array to mark whether an node is part of a given solution (CONNECT)
fixedoffset pointer
nelimsnumber 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()

◆ reduce_ans()

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

◆ reduce_ansAdv()

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

advanced adjacent neighbourhood reduction for the MWCSP

Parameters
scipSCIP data structure
ggraph data structure
nelimspointer to number of performed reductions
extneigbhooduse 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
scipSCIP data structure
ggraph data structure
nelimspointer 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
scipSCIP data structure
ggraph data structure
nelimspointer 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()

◆ reduce_nvAdv()

◆ 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
scipSCIP data structure
edgestatefor propagation or NULL
ggraph data structure
vnoiVoronoi data structure
fixedoffset pointer
vbaseVoronoi/shortest path bases array
vrnodesVoronoi/shortest path array
visitedVoronoi/shortest path array
solnodenode array to mark whether an node is part of a given solution (CONNECT), or NULL
nelimspointer 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
scipSCIP data structure
sdistancespecial distances storage
ggraph structure
solnodenode array to mark whether an node is part of a given solution (CONNECT)
fixedoffset pointer
nelimsnumber 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
scipSCIP data structure
sdistancespecial distances storage
ggraph structure
edgerecordkeeps 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
scipSCIP data structure
ggraph data structure
markednodes array for internal use
countpointer 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()

◆ reduce_chain2()

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

◆ reduce_sdEdgeCliqueStar()

◆ reduce_sdImpLongEdge()

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

long edge implied special distance test

Parameters
scipSCIP data structure
edgestatearray to store status of (directed) edge (for propagation, can otherwise be set to NULL)
ggraph data structure
sdistancespecial distances storage
nelimspoint to store number of deleted edges

Definition at line 1416 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
scipSCIP data structure
ggraph data structure
pathtailpath tails
heapheap
statetailtails
stateheadheads
memlbltailto save changed tails
memlblheadto save changed heads
nelimsnumber of eliminations
limitlimit for number checks
usestrongredsallow strong reductions?

Definition at line 4015 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
scipSCIP data structure
edgelimitlimit
usestrongredsallow strong reductions?
ggraph data structure
distvertex distances
star_basearray of size nnodes
visitlistarray of size nnodes
visitedarray of size nnodes
dheapDijkstra heap
nelimspoint to store number of deleted edges

Definition at line 3197 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
scipSCIP data structure
edgelimitlimit
usestrongredsallow strong reductions?
ggraph data structure
nelimspoint to store number of deleted edges

Definition at line 3327 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
scipSCIP data structure
edgelimitlimit
sdprofitwith profit given
usestrongredsallow strong reductions?
ggraph data structure
nelimspoint to store number of deleted edges

Definition at line 3348 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 
)

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

◆ 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 3738 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
scipSCIP data structure
edgelimitedge limit
edgestateper edge: state
ggraph data structure
termmarkper node: terminal property
distper node: distance
visitlistarray to store visited nodes
visitedper node: was visited?
dheaphead data structure
nelimspointer to store number of eliminations

Definition at line 2813 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
scipSCIP data structure
edgelimitedge limit
usestrongredsallow strong reductions?
ggraph data structure
termmarkterminal mark
distdistances
visitlistarray to store visited nodes
visitedper node: was visited?
dheapheap data structure
nelimsnumber of eliminations

Definition at line 3006 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
scipSCIP data structure
edgelimitedge limit
usestrongredsallow strong reductions?
ggraph data structure
distper node: distances
heapheap
statestate
visitlistarray to store visited nodes
visitednumber of visited nodes
nelimsnumber of eliminations

Definition at line 3822 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
scipSCIP data structure
edgelimitedge limit
edgestateper edge: state
ggraph data structure
termmarkper node: terminal state
distper node: distance
heapheap
statestate
visitlistvisited nodes
visitednumber of visited nodes
nelimsnumber of eliminations

Definition at line 3905 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
scipSCIP data structure
ggraph data structure
pathtailpath tails
pathheadpath heads
heapheap
statetailstates of tails
stateheadstates of heads
memlbltailstorage for tails
memlblheadstorage for heads
nelimsnumber of eliminations
limitlimit for number of visits

Definition at line 2656 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()

◆ reduce_sdBiased()

◆ reduce_sdBiasedNeighbor()

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

◆ 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
scipSCIP data structure
ggraph data structure
vnoiVoronoi data structure
heapheap array
statearray to store state of a node during Voronoi computation
vbaseVoronoi base to each node
nodesidarray
nodesorgarray
nelimspointer to store number of eliminated edges

Definition at line 2018 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
ggraph structure
ifirst vertex
i2second vertex
sd_upperupper bound on special distance that is accepted (can be FARAWAY)
sd_sufficientbound below which to terminate (can be 0.0)
sddataSD

Definition at line 2428 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
ggraph structure
ifirst vertex
i2second vertex
sd_upperupper bound on special distance that is accepted (can be FARAWAY)
sd_sufficientbound below which to terminate (can be 0.0)
sddataSD

Definition at line 2444 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 
)

◆ reduce_bdk()

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

bd_k test without given Steiner bottleneck distances

Parameters
scipSCIP data structure
edgevisitlimitmaximum edge visited per iteration
ggraph structure
nelimsnumber 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
scipSCIP data structure
edgevisitlimitmaximum edge visited per iteration
ggraph structure
nelimsnumber 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
scipSCIP data structure
edgevisitlimitmaximum edge visited per iteration
sdistancespecial distances storage
ggraph structure
nelimsnumber 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
scipSCIP data structure
ggraph data structure
nelimspointer 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
scipSCIP data structure
ggraph data structure
extpermaextension data
nelimspointer 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()

◆ 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
scipSCIP data structure
ggraph structure
sdgraphauxiliary graph structure
vnoipath structure
vbasebases for nearest terminals
nelimsnumber of eliminations

Definition at line 4305 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
scipSCIP data structure
graphgraph data structure
vnoiVoronoi data structure
radiusradius array
offsetpointer to the offset
upperboundpointer to an upper bound
heapheap array
statearray to store state of a node during Voronoi computation
vbaseVoronoi base to each node
nelimspointer 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
scipSCIP data structure
graphgraph data structure
vnoiVoronoi data structure (size 3 * nnodes)
offsetpointer to the offset
heapheap array
statearray to store state of a node during Voronoi computation
vbaseVoronoi base to each node
resultsolution array or NULL
nelimspointer 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
scipSCIP data structure
graphgraph data structure
vnoiVoronoi data structure
costedge cost array
radiusradius array
costrevreversed edge cost array
offsetpointer to the offset
heapheap array
statearray to store state of a node during Voronoi computation
vbaseVoronoi base to each node
solnodearray of nodes of current solution that is not to be destroyed
soledgearray of edges of current solution that is not to be destroyed
nelimspointer to store number of eliminated edges
minelimsminimum 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()

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

◆ reduce_boundHopRc()

◆ reduce_boundHopDa()

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

dual ascent based hop reductions for HCDSTP

Parameters
scipSCIP data structure
graphgraph data structure
nelimspointer to store number of reduced edges
randnumgenrandom 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
scipSCIP data structure
graphgraph data structure
paramsdaparameters
redsollocalprimal bound info or NULL
offsetppointer to store offset
nelimspointer to store number of reduced edges
randnumgenrandom 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()

◆ 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
scipSCIP data structure
graphgraph data structure
minelimsminimum number of edges to eliminate
solgivensolution provided?
soledgesolution edges (in/out)
solnodearray of nodes of current solution that is not to be destroyed (in/out)
nelimspointer to store number of reduced edges
upperboundpointer to store new upper bound
solImprovedsolution improved?
solReconstructedsolution 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
scipSCIP data structure
graphgraph data structure
paramsdaparameters
redprimalprimal bound info or NULL
vnoiVoronoi data structure array
pathdistdistance array for shortest path calculations
vbaseVoronoi base array
pathedgeshortest path incoming edge array for shortest path calculations
stateint 4 * vertices array
nodearrcharSTP_Bool node array for internal computations
nelimspointer to store number of reduced edges
randnumgenrandom number generator
prizesumsum 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
scipSCIP data structure
gthe 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
scipSCIP data structure
graphgraph data structure
rootgraph root from dual ascent
redcostreduced costs
pathdistshortest path distances
vnoiVoronoi paths
vbasebases to Voronoi paths
cutoffcutoff value
outedgestwo outgoing edge
inedgeincoming edge
treeboundto store a lower bound for the tree
ruleoutcould tree be ruled out?
eqstackstores edges that were used for equality comparison
eqstack_sizepointer to size of eqstack
eqmarkmarks 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
scipSCIP data structure
graphgraph data structure
vnoiVoronoi data structure
costdual ascent costs
pathdistdistance array from shortest path calculations
resultsol int array
minpathcostthe required reduced path cost to be surpassed
rootthe root
markededge array to mark which (directed) edge can be removed
markdirectedtry 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
scipSCIP
graphgraph 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
scipSCIP data structure
ggraph data structure
fixedpointer to offset value
solnodenode array to mark whether an node is part of a given solution (CONNECT), or NULL
nelimspointer to number of reductions
edgestatearray 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
scipSCIP data structure
ggraph 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
scipSCIP data structure
ggraph data structure
fixedpointer to offfset value
countpointer 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()

◆ reduce_deleteMultiedges()

◆ reduce_contract0Edges()

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

contract edges of weight zero

Parameters
scipSCIP data structure
ggraph data structure
solnodesolution node mark or NULL
savehistorysave 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
scipSCIP data structure
edgestatefor propagation or NULL
ggraph data structure
countnewpointer 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
scipSCIP data structure
cutedgethe edge
ggraph data structure
successcould 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 
)

◆ reduce_identifyNonLeafTerms()

◆ reduce_unconnected()

◆ reduce_unconnectedForDirected()

◆ 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
scipSCIP data structure
beVerbosebe verbose?
ggraph data structure
infeasis 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
scipSCIP data structure
ggraph data structure
fixedppointer to offset value
nelimspointer 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
scipSCIP data structure
ggraph data structure
redbasereduction base
solnodesolution nodes or NULL
wasDecomposedperformed 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
scipSCIP data structure
ggraph data structure
redbasereduction base
solnodesolution nodes or NULL
nelimsnumber 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
scipSCIP data structure
cutnodescut nodes
ggraph data structure
fixedppointer to offset value
nelimspointer 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()

◆ 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
scipSCIP data structure
edgestatefor propagation or NULL
ggraph data structure
fixedpointer to offset value
countnewpointer to number of new reductions (will be initially set to 0)
countallpointer to number of all reductions or NULL
solnodesolution 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
scipSCIP data structure
ggraph data structure
offsetppointer 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()

◆ reduce_unconnectedRpcRmwInfeas()

◆ reduce_impliedNodesGet()

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

gets implied nodes for each node

Parameters
scipSCIP data structure
graphgraph data structure
nodes_implicationsarray 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
scipSCIP data structure
graphgraph data structure
tailtail of eliminated edge
headhead of eliminated edge
nodes_implicationsinitialized 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
graphgraph data structure
nodes_implicationsinitialized 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 
)

◆ reduce_blctreeInit()

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

initializes BLC tree

Parameters
scipSCIP
graphthe graph
blctreeto 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
scipSCIP
blctreeto 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
blctreeBLC 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 
)

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

◆ 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
graphgraph
blctreeBLC tree
statelistof 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
scipSCIP
graphthe graph
blctreeto 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 
)

◆ reduce_dcmstFree()

void reduce_dcmstFree ( SCIP scip,
DCMST **  dcmst 
)

frees dynamic MST structure

Parameters
scipSCIP
dcmstto 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()

◆ 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
scipSCIP
mst_insource
adjcosts(undirected) adjacency costs for new node
dmstunderlying structure
mst_outtarget

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
scipSCIP
adjcosts(undirected) adjacency costs for new node
dmstunderlying structure
mstsource/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
scipSCIP
mstMST

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
scipSCIP
mstMST

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
scipSCIP
edgecostedge cost
mstMST

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
scipSCIP
edgecost01edge cost
edgecost02edge cost
edgecost12edge cost
mstMST

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
scipSCIP
mstMST for which to compute extended weight
adjcosts(undirected) adjacency costs for new node
dmstunderlying 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()

◆ reduce_dcmstGetMaxnnodes()

int reduce_dcmstGetMaxnnodes ( const DCMST dmst)

returns maximum number of nodes

Parameters
dmstunderlying 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
dmstunderlying 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()

◆ reduce_starFree()

◆ reduce_starReset()

◆ reduce_starResetWithEdges()

void reduce_starResetWithEdges ( const GRAPH ,
const   STP_Vectypeint,
STAR  
)

Referenced by generalStarCheckInit().

◆ reduce_starGetNext()

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

◆ reduce_starGetNextAndPosition()

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

gets next star

Parameters
starthe star (in/out)
positionarray to store the positions
nedgesnumber 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
starthe star
nedgesnumber 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
starthe 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
starthe star

Definition at line 1948 of file reduce_util.c.

References reduce_starAllAreChecked().

◆ reduce_starCurrentSetFailed()

void reduce_starCurrentSetFailed ( STAR star)

◆ reduce_starHasPromisingEdges()

SCIP_Bool reduce_starHasPromisingEdges ( const STAR star)

are there edge that might still be ruled out?

Parameters
starthe star

Definition at line 1990 of file reduce_util.c.

References node_one_hop_star::nedgesPromising.

Referenced by bdkTryDegGe4(), and testStar4EdgeIsCorrect().

◆ reduce_starAllAreChecked()

◆ reduce_sdneighborInit()

◆ 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
scipSCIP
sdnSD 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
scipSCIP
ggraph to initialize from
sddataSD
nupdatesnumber 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
scipSCIP
ggraph to initialize from
sdprofitthe 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
scipSCIP
ggraph to initialize from
edgecostsedge costs (w.r.t graph 'g')
sdprofitthe 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()

◆ 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
scipSCIP
ggraph
blctreeBLC tree
blctree_isUpdatedBLC tree fresh?
sdprofitthe 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
scipSCIP
ggraph
blctreeBLC tree
blctree_isUpdatedBLC tree fresh?
sdprofitthe 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
ggraph to initialize from
sdprofitthe 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()

◆ reduce_sdInitBiased()

◆ reduce_sdInitBiasedBottleneck()

◆ 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
scipSCIP
edgeedge to be deleted soon
withEdgeReplacementwith edge replacement?
ggraph NOTE: will mark the graph, thus not const :( terrible design
sdto 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
scipSCIP
ggraph
sdto 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
scipSCIP
ggraph
sdto 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()

◆ 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
scipSCIP
gthe graph
centernodecenter node or - 1
cliqueNodeMapmaps clique graph vertices to original ones
dijkdatadata for repeated path computations
sddataSD
cliquegraphclique graph to be filled

Definition at line 1389 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
scipSCIP
ggraph to initialize from
sdgraphthe 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
scipSCIP
ggraph to initialize from
distgraphdistance graph
node2distmap
sdgraphthe 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
scipSCIP
ggraph to initialize from
sdprofitSD profit
sdgraphthe 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
scipSCIP
ggraph to initialize from
sdprofitSD profit
tpathsterminal paths
sdgraphthe 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
sdgraphthe 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)

◆ reduce_sdgraphGetOrgnodesToSdMap()

const int* reduce_sdgraphGetOrgnodesToSdMap ( const SDGRAPH sdgraph)

returns mapping from original nodes to distance graph nodes

Parameters
sdgraphthe SD graph

Definition at line 2001 of file reduce_sdgraph.c.

References special_distance_graph::nodemapOrgToDist.

Referenced by sdgraphInsertEdge().

◆ reduce_sdgraphInitOrderedMstCosts()

◆ reduce_sdgraphGetMstHalfMark()

const STP_Bool* reduce_sdgraphGetMstHalfMark ( const SDGRAPH sdgraph)

returns edge mark

Parameters
sdgraphthe 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)

◆ reduce_sdgraphEdgeIsInMst()

SCIP_Bool reduce_sdgraphEdgeIsInMst ( const SDGRAPH sdgraph,
int  edge 
)

is edge in current SD MST?

Parameters
sdgraphthe SD graph
edgeedge

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
sdgraphthe 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
term1node 1
term2node 2
sdgraphthe 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()

◆ 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
scipSCIP
sdgraphthe 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
scipSCIP
ggraph to initialize from
g_sdthe 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_sdthe SD graph

Definition at line 2046 of file reduce_sdgraph.c.

References sdgraphMstSortCosts().

Referenced by sdneighborUpdate().

◆ reduce_termcompInit()

◆ reduce_termcompFree()

◆ reduce_termcompInitTbottleneck()

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

initializes tree bottleneck for terminal component

Parameters
scipSCIP data structure
subsoledgessolution tree to be represented
termcompto 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
scipSCIP data structure
orggraphgraph data structure
termcompcomponent

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
scipSCIP data structure
orggraphgraph data structure
extpermaextension data
termcompcomponent

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

◆ reduce_termsepaGetNextComp()

◆ reduce_compbuilderInit()

◆ reduce_compbuilderFree()

void reduce_compbuilderFree ( SCIP scip,
COMPBUILDER **  compbuilder 
)

frees

Parameters
scipSCIP data structure
compbuilderto 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)

◆ reduce_compbuilderPrintSeparators()

void reduce_compbuilderPrintSeparators ( const GRAPH orggraph,
const COMPBUILDER compbuilder 
)

prints

Parameters
orggraphgraph data structure
compbuilderbuilder

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
orggraphgraph data structure
termcompcomponent

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
scipSCIP data structure
ggraph data structure
extpermaextension data
pseudoDelNodesarray to mark pseudo deletable nodes or NULL (OUT)
nelimsnumber 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
scipSCIP data structure
ggraph data structure
nelimsnumber 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
scipSCIP data structure
ggraph data structure
solnodesolution nodes mark or NULL
redbasereduction base
nelimsnumber 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().