Detailed Description

bound based reductions for Steiner tree problems

Author: Daniel Rehfeldt

This file implements bound-based reduction techniques for several Steiner problems. All tests can be found in "A Generic Approach to Solving the Steiner Tree Problem and Variants" by Daniel Rehfeldt.

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

Definition in file reduce_bnd.c.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "scip/scip.h"
#include "grph.h"
#include "heur_tm.h"
#include "heur_ascendprune.h"
#include "cons_stp.h"
#include "heur_local.h"
#include "misc_stp.h"
#include "prop_stp.h"
#include "probdata_stp.h"
#include "heur_rec.h"
#include "heur_slackprune.h"

Go to the source code of this file.

Macros
#define	DEFAULT_HEURRUNS 100

#define	DEFAULT_DARUNS 7

#define	DEFAULT_NMAXROOTS 8

#define	PERTUBATION_RATIO 0.05

#define	PERTUBATION_RATIO_PC 0.005

#define	SOLPOOL_SIZE 20

#define	STP_RED_MINBNDTERMS 750

#define	STP_DABD_MAXDEGREE 5

#define	STP_DABD_MAXDNEDGES 10

#define	STP_DAEX_MAXDFSDEPTH 6

#define	STP_DAEX_MINDFSDEPTH 4

#define	STP_DAEX_MAXGRAD 8

#define	STP_DAEX_MINGRAD 6

#define	STP_DAEX_EDGELIMIT 50000

#define	DAMAXDEVIATION_RANDOM_LOWER 0.15

#define	DAMAXDEVIATION_RANDOM_UPPER 0.30

#define	DAMAXDEVIATION_FAST 0.75

#define	EXEDGE_FREE 0

#define	EXEDGE_FIXED 1

#define	EXEDGE_KILLED 2

Functions
static SCIP_Bool	markAncestorsConflict (const GRAPH graph, int edge, int ancestormark)

static void	markAncestors (const GRAPH graph, int edge, int ancestormark)

static void	unmarkAncestorsConflict (const GRAPH graph, int edge, int ancestormark)

static void	unmarkAncestors (const GRAPH graph, int edge, int ancestormark)

static void	finalizeSubtree (const GRAPH graph, const int edgeends, const int treeedges, int dfsdepth, SCIP_Bool stopped, SCIP_Real localbound, SCIP_Real globalbound, SCIP_Bool ruleout, int nodepos, int *ancestormark)

static SCIP_Bool	truncateSubtree (const GRAPH graph, SCIP_Real extendedcost, int root, int currhead, int maxgrad, int dfsdepth, int maxdfsdepth, SCIP_Real minbound, SCIP_Bool *stopped)

static SCIP_Real	shortenSubtree (SCIP scip, const GRAPH graph, const SCIP_Real redcost, const int treeedges, SCIP_Real treecostold, SCIP_Real treecostoffset, int dfsdepth, int lastnode, int nodepos, int ancestormark, unsigned int *nstallrounds)

static int	extendSubtreeHead (SCIP scip, const GRAPH graph, const SCIP_Real redcost, int curredge, int currhead, int dfsdepth, int nadded_edges, SCIP_Real treecost, SCIP_Real treecosts, int nodepos, int treeedges, int edgestack, int *ancestormark)

static int	extendSubtreeTail (const GRAPH graph, const SCIP_Real redcost, int curredge, int currtail, int dfsdepth, int nadded_edges, SCIP_Real treecost, SCIP_Real treecosts, int nodepos, int treeedges, int edgestack, int ancestormark)

static void	updateEqArrays (int edge, unsigned int eqstack, int eqstack_size, SCIP_Bool *eqmark)

static SCIP_Bool	bottleneckRuleOut (SCIP scip, const GRAPH graph, const SCIP_Real treecosts, const SCIP_Real basebottlenecks, const int nodepos, const int treeedges, SCIP_Real orgedgecost, SCIP_Real extedgecost, int orgedge, int extedge, int dfsdepth, SCIP_Bool allow_eq, unsigned int eqstack, int eqstack_size, SCIP_Bool *eqmark)

static SCIP_Bool	ruleOutSubtree (SCIP scip, const GRAPH graph, const SCIP_Real treecosts, const SCIP_Real basebottlenecks, const int nodepos, const int treeedges, SCIP_Real cutoff, SCIP_Real extendedcost, int dfsdepth, int curredge, SCIP_Bool allowequality, const int ancestormark, unsigned int eqstack, int eqstack_size, SCIP_Bool eqmark)

static void	updateNodeFixingBounds (SCIP_Real fixingbounds, const GRAPH graph, const SCIP_Real pathdist, const PATH vnoi, SCIP_Real lpobjval, SCIP_Bool initialize)

static SCIP_RETCODE	updateNodeReplaceBounds (SCIP scip, SCIP_Real replacebounds, const GRAPH graph, const SCIP_Real cost, const SCIP_Real pathdist, const PATH vnoi, const int vbase, int nodearrint, SCIP_Real lpobjval, SCIP_Real upperbound, int root, SCIP_Bool initialize, SCIP_Bool extendedsearch)

static void	updateEdgeFixingBounds (SCIP_Real fixingbounds, const GRAPH graph, const SCIP_Real cost, const SCIP_Real pathdist, const PATH *vnoi, SCIP_Real lpobjval, int extnedges, SCIP_Bool initialize, SCIP_Bool undirected)

static int	reduceWithNodeFixingBounds (SCIP scip, GRAPH graph, GRAPH transgraph, const SCIP_Real fixingbounds, SCIP_Real upperbound)

static int	reduceWithNodeReplaceBounds (SCIP scip, GRAPH graph, const PATH vnoi, const SCIP_Real pathdist, const SCIP_Real cost, const SCIP_Real replacebounds, int *nodetouched, SCIP_Real lpobjval, SCIP_Real upperbound)

static int	reduceWithEdgeFixingBounds (SCIP scip, GRAPH graph, GRAPH transgraph, const SCIP_Real fixingbounds, const int *result, SCIP_Real upperbound)

static void	findDaRoots (SCIP scip, GRAPH graph, const GRAPH transgraph, const SCIP_Real cost, const SCIP_Real bestcost, SCIP_Real lpobjval, SCIP_Real bestlpobjval, SCIP_Real upperbound, SCIP_Real prizesum, SCIP_Bool rerun, SCIP_Bool probrooted, PATH vnoi, int state, int pathedge, int vbase, STP_Bool nodearrchar, int roots, int rootscount)

static void	markPcMwRoots (SCIP scip, const int roots, int nrootsold, int nrootsnew, SCIP_Real prizesum, GRAPH graph, SCIP_Bool userec, STPSOLPOOL **solpool)

static SCIP_Bool	dualCostIsValid (SCIP scip, GRAPH transgraph, const SCIP_Real cost, int nodearrint, STP_Bool *nodearrbool)

static void	pertubateEdgeCosts (SCIP scip, const GRAPH graph, GRAPH transgraph, const int result, STP_Bool *nodearrchar, int randomize)

static SCIP_RETCODE	orderDaRoots (SCIP scip, const GRAPH graph, int terms, int nterms, SCIP_Bool randomize, SCIP_RANDNUMGEN randnumgen)

static SCIP_RETCODE	computeDaSolPcMw (SCIP scip, GRAPH graph, STPSOLPOOL pool, PATH vnoi, const SCIP_Real cost, SCIP_Real pathdist, SCIP_Real upperbound, int result1, int result2, int vbase, int pathedge, STP_Bool nodearrchar, SCIP_Bool *apsol)

static SCIP_RETCODE	computePertubedSol (SCIP scip, GRAPH graph, GRAPH transgraph, STPSOLPOOL pool, PATH vnoi, GNODE gnodearr, SCIP_Real cost, SCIP_Real costrev, SCIP_Real bestcost, SCIP_Real pathdist, int state, int vbase, int pathedge, int result, int result2, int transresult, STP_Bool nodearrchar, SCIP_Real upperbound, SCIP_Real lpobjval, SCIP_Real bestlpobjval, SCIP_Real minpathcost, SCIP_Bool *apsol, SCIP_Real offset, int extnedges, int pertubation)

static void	computeTransVoronoi (SCIP scip, GRAPH transgraph, PATH vnoi, const SCIP_Real cost, SCIP_Real costrev, SCIP_Real pathdist, int vbase, int pathedge)

static int	reduceSPG (SCIP scip, GRAPH graph, SCIP_Real offset, STP_Bool marked, STP_Bool nodearrchar, const PATH vnoi, const SCIP_Real cost, const SCIP_Real pathdist, const int *result, SCIP_Real minpathcost, int root, SCIP_Bool solgiven)

static int	reducePcMw (SCIP scip, GRAPH graph, GRAPH transgraph, const PATH vnoi, const SCIP_Real cost, const SCIP_Real pathdist, SCIP_Real minpathcost, const int result, STP_Bool marked, STP_Bool *nodearrchar, SCIP_Bool solgiven)

static int	reducePcMwTryBest (SCIP scip, GRAPH graph, GRAPH transgraph, PATH vnoi, const SCIP_Real cost, SCIP_Real costrev, SCIP_Real bestcost, SCIP_Real pathdist, SCIP_Real upperbound, SCIP_Real lpobjval, SCIP_Real bestlpobjval, SCIP_Real minpathcost, SCIP_Real oldupperbound, const int result, int vbase, int state, int pathedge, STP_Bool marked, STP_Bool nodearrchar, SCIP_Bool *solgiven, int extnedges)

static SCIP_RETCODE	reduceCheckEdge (SCIP scip, const GRAPH graph, int root, const SCIP_Real redcost, const SCIP_Real pathdist, const PATH vnoi, SCIP_Real cutoff, int edge, SCIP_Bool equality, int edgestack, SCIP_Bool deletable, unsigned int eqstack, int eqstack_size, SCIP_Bool eqmark)

SCIP_RETCODE	reduce_deleteConflictEdges (SCIP scip, GRAPH g)

SCIP_RETCODE	reduce_check3Tree (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, int edgestack, SCIP_Real treebound, SCIP_Bool ruleout, unsigned int eqstack, int eqstack_size, SCIP_Bool *eqmark)

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, int nodearr, STP_Bool marked)

SCIP_RETCODE	reduce_da (SCIP scip, GRAPH graph, PATH vnoi, GNODE gnodearr, SCIP_Real cost, SCIP_Real costrev, SCIP_Real pathdist, SCIP_Real ub, SCIP_Real offset, int edgearrint, int vbase, int state, int pathedge, int nodearrint, int heursources, STP_Bool nodearrchar, int nelims, int prevrounds, SCIP_RANDNUMGEN *randnumgen, SCIP_Bool userec, SCIP_Bool extended)

SCIP_RETCODE	reduce_daSlackPrune (SCIP scip, SCIP_VAR vars, GRAPH graph, PATH vnoi, GNODE gnodearr, SCIP_Real cost, SCIP_Real costrev, SCIP_Real pathdist, SCIP_Real upperbound, int edgearrint, int edgearrint2, int vbase, int pathedge, int state, int solnode, STP_Bool nodearrchar, STP_Bool edgearrchar, int nelims, int minelims, SCIP_Bool solgiven)

SCIP_RETCODE	reduce_daPcMw (SCIP scip, GRAPH graph, PATH vnoi, GNODE gnodearr, SCIP_Real cost, SCIP_Real costrev, SCIP_Real pathdist, int vbase, int pathedge, int edgearrint, int state, STP_Bool nodearrchar, int nelims, SCIP_Bool solbasedda, SCIP_Bool varyroot, SCIP_Bool markroots, SCIP_Bool userec, SCIP_Bool fastmode, SCIP_RANDNUMGEN *randnumgen, SCIP_Real prizesum)

SCIP_RETCODE	reduce_daSlackPruneMw (SCIP scip, GRAPH graph, PATH vnoi, GNODE gnodearr, SCIP_Real cost, SCIP_Real costrev, SCIP_Real pathdist, int vbase, int pathedge, int soledge, int state, int solnode, STP_Bool nodearrchar, int *nelims, int minelims, SCIP_Bool solgiven)

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

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

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

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

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)

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

Macro Definition Documentation

◆ DEFAULT_HEURRUNS

#define DEFAULT_HEURRUNS 100

number of runs of constructive heuristic

Definition at line 44 of file reduce_bnd.c.

Referenced by reduce_bound(), reduce_da(), reduce_daPcMw(), and reduce_daSlackPruneMw().

◆ DEFAULT_DARUNS

#define DEFAULT_DARUNS 7

number of runs for dual ascent heuristic

Definition at line 45 of file reduce_bnd.c.

Referenced by reduce_da().

◆ DEFAULT_NMAXROOTS

#define DEFAULT_NMAXROOTS 8

max number of roots to use for new graph in dual ascent heuristic

Definition at line 46 of file reduce_bnd.c.

Referenced by reduce_daPcMw().

◆ PERTUBATION_RATIO

#define PERTUBATION_RATIO 0.05

pertubation ratio for dual-ascent primal bound computation

Definition at line 47 of file reduce_bnd.c.

Referenced by pertubateEdgeCosts().

◆ PERTUBATION_RATIO_PC

#define PERTUBATION_RATIO_PC 0.005

pertubation ratio for dual-ascent primal bound computation

Definition at line 48 of file reduce_bnd.c.

Referenced by pertubateEdgeCosts().

◆ SOLPOOL_SIZE

#define SOLPOOL_SIZE 20

size of presolving solution pool

Definition at line 49 of file reduce_bnd.c.

Referenced by reduce_da(), and reduce_daPcMw().

◆ STP_RED_MINBNDTERMS

#define STP_RED_MINBNDTERMS 750

Definition at line 50 of file reduce_bnd.c.

Referenced by reduce_daPcMw().

◆ STP_DABD_MAXDEGREE

#define STP_DABD_MAXDEGREE 5

Definition at line 51 of file reduce_bnd.c.

Referenced by reduceWithNodeReplaceBounds(), and updateNodeReplaceBounds().

◆ STP_DABD_MAXDNEDGES

#define STP_DABD_MAXDNEDGES 10

Definition at line 52 of file reduce_bnd.c.

Referenced by reduceWithNodeReplaceBounds().

◆ STP_DAEX_MAXDFSDEPTH

#define STP_DAEX_MAXDFSDEPTH 6

Definition at line 53 of file reduce_bnd.c.

Referenced by reduce_check3Tree(), and reduceCheckEdge().

◆ STP_DAEX_MINDFSDEPTH

#define STP_DAEX_MINDFSDEPTH 4

Definition at line 54 of file reduce_bnd.c.

Referenced by reduce_check3Tree(), and reduceCheckEdge().

◆ STP_DAEX_MAXGRAD

#define STP_DAEX_MAXGRAD 8

Definition at line 55 of file reduce_bnd.c.

Referenced by reduce_check3Tree(), reduceCheckEdge(), ruleOutSubtree(), and truncateSubtree().

◆ STP_DAEX_MINGRAD

#define STP_DAEX_MINGRAD 6

Definition at line 56 of file reduce_bnd.c.

Referenced by reduce_check3Tree(), and reduceCheckEdge().

◆ STP_DAEX_EDGELIMIT

#define STP_DAEX_EDGELIMIT 50000

Definition at line 57 of file reduce_bnd.c.

Referenced by reduce_check3Tree(), and reduceCheckEdge().

◆ DAMAXDEVIATION_RANDOM_LOWER

#define DAMAXDEVIATION_RANDOM_LOWER 0.15

random upper bound for max deviation for dual ascent

Definition at line 58 of file reduce_bnd.c.

Referenced by reduce_da().

◆ DAMAXDEVIATION_RANDOM_UPPER

#define DAMAXDEVIATION_RANDOM_UPPER 0.30

random upper bound for max deviation for dual ascent

Definition at line 59 of file reduce_bnd.c.

Referenced by reduce_da().

◆ DAMAXDEVIATION_FAST

#define DAMAXDEVIATION_FAST 0.75

Definition at line 60 of file reduce_bnd.c.

Referenced by reduce_daPcMw().

◆ EXEDGE_FREE

#define EXEDGE_FREE 0

Definition at line 62 of file reduce_bnd.c.

Referenced by truncateSubtree().

◆ EXEDGE_FIXED

#define EXEDGE_FIXED 1

Definition at line 63 of file reduce_bnd.c.

Referenced by truncateSubtree().

◆ EXEDGE_KILLED

#define EXEDGE_KILLED 2

Definition at line 64 of file reduce_bnd.c.

Referenced by truncateSubtree().

Function Documentation

◆ markAncestorsConflict()

static SCIP_Bool markAncestorsConflict	(	const GRAPH *	graph,
		int	edge,
		int *	ancestormark
	)

static

mark ancestors of given edge

Parameters

graph	graph data structure
edge	edge to use
ancestormark	ancestor mark array

Definition at line 69 of file reduce_bnd.c.

References GRAPH::ancestors, GRAPH::edges, FALSE, MAX, NULL, GRAPH::orgedges, and TRUE.

Referenced by reduce_check3Tree(), and reduce_deleteConflictEdges().

◆ markAncestors()

static void markAncestors	(	const GRAPH *	graph,
		int	edge,
		int *	ancestormark
	)

static

mark ancestors of given edge

Parameters

graph	graph data structure
edge	edge to use
ancestormark	ancestor mark array

Definition at line 96 of file reduce_bnd.c.

References GRAPH::ancestors, GRAPH::edges, MAX, NULL, and GRAPH::orgedges.

Referenced by extendSubtreeHead(), extendSubtreeTail(), and reduceCheckEdge().

◆ unmarkAncestorsConflict()

static void unmarkAncestorsConflict	(	const GRAPH *	graph,
		int	edge,
		int *	ancestormark
	)

static

unmark ancestors of given edge

Parameters

graph	graph data structure
edge	edge to use
ancestormark	ancestor mark array

Definition at line 116 of file reduce_bnd.c.

References GRAPH::ancestors, GRAPH::edges, MAX, NULL, and GRAPH::orgedges.

Referenced by reduce_check3Tree(), and reduce_deleteConflictEdges().

◆ unmarkAncestors()

static void unmarkAncestors	(	const GRAPH *	graph,
		int	edge,
		int *	ancestormark
	)

static

unmark ancestors of given edge

Parameters

graph	graph data structure
edge	edge to use
ancestormark	ancestor mark array

Definition at line 134 of file reduce_bnd.c.

References GRAPH::ancestors, GRAPH::edges, MAX, NULL, and GRAPH::orgedges.

Referenced by finalizeSubtree(), reduceCheckEdge(), and shortenSubtree().

◆ finalizeSubtree()

static void finalizeSubtree	(	const GRAPH *	graph,
		const int *	edgeends,
		const int *	treeedges,
		int	dfsdepth,
		SCIP_Bool	stopped,
		SCIP_Real	localbound,
		SCIP_Real *	globalbound,
		SCIP_Bool *	ruleout,
		int *	nodepos,
		int *	ancestormark
	)

static

finalize subtree computations (clean up, update global bound)

Parameters

graph	graph data structure
edgeends	heads or tail of edge
treeedges	tree edges
dfsdepth	dfs depth
stopped	has extension been stopped?
localbound	local bound
globalbound	points to global bound
ruleout	rule out?
nodepos	node position in tree
ancestormark	ancestor mark array

Definition at line 157 of file reduce_bnd.c.

References TRUE, and unmarkAncestors().

Referenced by reduce_check3Tree(), and reduceCheckEdge().

◆ truncateSubtree()

static SCIP_Bool truncateSubtree	(	const GRAPH *	graph,
		SCIP_Real	extendedcost,
		int	root,
		int	currhead,
		int	maxgrad,
		int	dfsdepth,
		int	maxdfsdepth,
		SCIP_Real *	minbound,
		SCIP_Bool *	stopped
	)

static

should we truncate subtree?

Parameters

graph	graph data structure
extendedcost	cost of subtree
root	DA root
currhead	latest node
maxgrad	maximum allowed degree
dfsdepth	dfs depth
maxdfsdepth	max dfs depth
minbound	bound
stopped	real truncation?

Definition at line 195 of file reduce_bnd.c.

References GRAPH::cost, EAT_LAST, EXEDGE_FIXED, EXEDGE_FREE, EXEDGE_KILLED, FALSE, GRAPH::grad, GRAPH::head, Is_term, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_Real, SCIPisLT(), STP_DAEX_MAXGRAD, GRAPH::term, and TRUE.

Referenced by reduce_check3Tree(), and reduceCheckEdge().

◆ shortenSubtree()

static SCIP_Real shortenSubtree	(	SCIP *	scip,
		const GRAPH *	graph,
		const SCIP_Real *	redcost,
		const int *	treeedges,
		SCIP_Real	treecostold,
		SCIP_Real	treecostoffset,
		int	dfsdepth,
		int	lastnode,
		int *	nodepos,
		int *	ancestormark,
		unsigned int *	nstallrounds
	)

static

remove latest edge from subtree and returns new tree cost

Parameters

scip	SCIP
graph	graph data structure
redcost	reduced costs
treeedges	edges of tree
treecostold	old tree cost
treecostoffset	tree cost offset
dfsdepth	DFS depth
lastnode	last node
nodepos	array to mark node position
ancestormark	ancestor mark array
nstallrounds	rounds since latest update

Definition at line 334 of file reduce_bnd.c.

References SCIP_Real, SCIPisEQ(), SCIPisGE(), and unmarkAncestors().

Referenced by reduce_check3Tree(), and reduceCheckEdge().

◆ extendSubtreeHead()

static int extendSubtreeHead	(	SCIP *	scip,
		const GRAPH *	graph,
		const SCIP_Real *	redcost,
		int	curredge,
		int	currhead,
		int	dfsdepth,
		int	nadded_edges,
		SCIP_Real *	treecost,
		SCIP_Real *	treecosts,
		int *	nodepos,
		int *	treeedges,
		int *	edgestack,
		int *	ancestormark
	)

static

extend subtree and return new nadded_edges

Parameters

scip	SCIP
graph	graph data structure
redcost	reduced costs
curredge	added edges
currhead	latest node
dfsdepth	DFS depth
nadded_edges	added edges
treecost	pointer to treecost
treecosts	edge costs of tree
nodepos	node position in tree
treeedges	edges of tree
edgestack	stack
ancestormark	ancestor mark array

Definition at line 383 of file reduce_bnd.c.

References GRAPH::cost, EAT_LAST, GRAPH::head, markAncestors(), GRAPH::oeat, and GRAPH::outbeg.

Referenced by reduce_check3Tree(), and reduceCheckEdge().

◆ extendSubtreeTail()

static int extendSubtreeTail	(	const GRAPH *	graph,
		const SCIP_Real *	redcost,
		int	curredge,
		int	currtail,
		int	dfsdepth,
		int	nadded_edges,
		SCIP_Real *	treecost,
		SCIP_Real *	treecosts,
		int *	nodepos,
		int *	treeedges,
		int *	edgestack,
		int *	ancestormark
	)

static

extend subtree and return new nadded_edges

Parameters

graph	graph data structure
redcost	reduced costs
curredge	added edges
currtail	latest node
dfsdepth	DFS depth
nadded_edges	added edges
treecost	pointer to treecost
treecosts	edge costs of tree
nodepos	node position in tree
treeedges	edges of tree
edgestack	stack
ancestormark	ancestor mark array

Definition at line 416 of file reduce_bnd.c.

References GRAPH::cost, EAT_LAST, GRAPH::ieat, GRAPH::inpbeg, markAncestors(), and GRAPH::tail.

Referenced by reduce_check3Tree(), and reduceCheckEdge().

◆ updateEqArrays()

static void updateEqArrays	(	int	edge,
		unsigned int *	eqstack,
		int *	eqstack_size,
		SCIP_Bool *	eqmark
	)

static

small helper

Parameters

edge	the edge
eqstack	stores edges that were used for equality comparison
eqstack_size	pointer to size of eqstack
eqmark	marks edges that were used for equality comparison

Definition at line 449 of file reduce_bnd.c.

References TRUE.

Referenced by bottleneckRuleOut().

◆ bottleneckRuleOut()

static SCIP_Bool bottleneckRuleOut	(	SCIP *	scip,
		const GRAPH *	graph,
		const SCIP_Real *	treecosts,
		const SCIP_Real *	basebottlenecks,
		const int *	nodepos,
		const int *	treeedges,
		SCIP_Real	orgedgecost,
		SCIP_Real	extedgecost,
		int	orgedge,
		int	extedge,
		int	dfsdepth,
		SCIP_Bool	allow_eq,
		unsigned int *	eqstack,
		int *	eqstack_size,
		SCIP_Bool *	eqmark
	)

static

compare with tree bottleneck

Parameters

scip	SCIP
graph	graph data structure
treecosts	costs of edges of the tree
basebottlenecks	bottleneck costs for innode and basenode
nodepos	node position in tree
treeedges	edges in tree (corresponding to treecosts)
orgedgecost	cost of original edge
extedgecost	cost of short-cut edge
orgedge	original edge
extedge	short-cut edge
dfsdepth	dfs depth
allow_eq	test for equality?
eqstack	stores edges that were used for equality comparison
eqstack_size	pointer to size of eqstack
eqmark	marks edges that were used for equality comparison

Definition at line 472 of file reduce_bnd.c.

References FALSE, GRAPH::knots, NULL, SCIPisEQ(), SCIPisLE(), SCIPisLT(), GRAPH::tail, TRUE, and updateEqArrays().

Referenced by ruleOutSubtree().

◆ ruleOutSubtree()

static SCIP_Bool ruleOutSubtree	(	SCIP *	scip,
		const GRAPH *	graph,
		const SCIP_Real *	treecosts,
		const SCIP_Real *	basebottlenecks,
		const int *	nodepos,
		const int *	treeedges,
		SCIP_Real	cutoff,
		SCIP_Real	extendedcost,
		int	dfsdepth,
		int	curredge,
		SCIP_Bool	allowequality,
		const int *	ancestormark,
		unsigned int *	eqstack,
		int *	eqstack_size,
		SCIP_Bool *	eqmark
	)

static

can subtree be ruled out?

Parameters

scip	SCIP
graph	graph data structure
treecosts	costs of edges of the tree
basebottlenecks	bottleneck costs for innode and basenode
nodepos	node position in tree
treeedges	edges in tree (corresponding to treecosts)
cutoff	cut-off bound
extendedcost	cost of subtree
dfsdepth	dfs depth
curredge	latest edge
allowequality	rule out also in case of equality
ancestormark	ancestor mark array
eqstack	stores edges that were used for equality comparison
eqstack_size	pointer to size of eqstack
eqmark	marks edges that were used for equality comparison

Definition at line 552 of file reduce_bnd.c.

References GRAPH::ancestors, bottleneckRuleOut(), GRAPH::cost, EAT_LAST, GRAPH::edges, FALSE, flipedge, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, MAX, NULL, GRAPH::oeat, GRAPH::orgedges, GRAPH::outbeg, SCIP_Bool, SCIP_Real, SCIPisGT(), STP_DAEX_MAXGRAD, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by reduce_check3Tree(), and reduceCheckEdge().

◆ updateNodeFixingBounds()

static void updateNodeFixingBounds	(	SCIP_Real *	fixingbounds,
		const GRAPH *	graph,
		const SCIP_Real *	pathdist,
		const PATH *	vnoi,
		SCIP_Real	lpobjval,
		SCIP_Bool	initialize
	)

static

updates node bounds for reduced cost fixings

Parameters

fixingbounds	fixing bounds
graph	graph data structure
pathdist	shortest path distances
vnoi	Voronoi paths
lpobjval	LP objective
initialize	initialize fixing bounds?

Definition at line 654 of file reduce_bnd.c.

References shortest_path::dist, GRAPH::extended, FARAWAY, Is_pterm, GRAPH::knots, GRAPH::mark, nnodes, SCIP_Real, STP_RSMT, STP_SPG, GRAPH::stp_type, and GRAPH::term.

Referenced by reduce_da(), and reduce_daPcMw().

◆ updateNodeReplaceBounds()

static SCIP_RETCODE updateNodeReplaceBounds	(	SCIP *	scip,
		SCIP_Real *	replacebounds,
		const GRAPH *	graph,
		const SCIP_Real *	cost,
		const SCIP_Real *	pathdist,
		const PATH *	vnoi,
		const int *	vbase,
		int *	nodearrint,
		SCIP_Real	lpobjval,
		SCIP_Real	upperbound,
		int	root,
		SCIP_Bool	initialize,
		SCIP_Bool	extendedsearch
	)

static

updates node bounds for reduced cost replacement

Parameters

scip	SCIP
replacebounds	replacement bounds
graph	graph data structure
cost	reduced costs
pathdist	shortest path distances
vnoi	Voronoi paths
vbase	bases to Voronoi paths
nodearrint	for internal computations
lpobjval	LP objective
upperbound	upper bound
root	DA root
initialize	initialize fixing bounds?
extendedsearch	perform extended searching?

Definition at line 689 of file reduce_bnd.c.

References shortest_path::dist, EAT_LAST, GRAPH::edges, GRAPH::extended, FALSE, FARAWAY, flipedge, GRAPH::grad, GRAPH::head, Is_gterm, Is_pterm, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, reduce_check3Tree(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPisGE(), SCIPisLE(), SCIPisLT(), SCIPisNegative(), STP_DABD_MAXDEGREE, STP_RSMT, STP_SPG, GRAPH::stp_type, and GRAPH::term.

Referenced by reduce_da().

◆ updateEdgeFixingBounds()

static void updateEdgeFixingBounds	(	SCIP_Real *	fixingbounds,
		const GRAPH *	graph,
		const SCIP_Real *	cost,
		const SCIP_Real *	pathdist,
		const PATH *	vnoi,
		SCIP_Real	lpobjval,
		int	extnedges,
		SCIP_Bool	initialize,
		SCIP_Bool	undirected
	)

static

updates edge fixing bounds for reduced cost fixings

Parameters

fixingbounds	fixing bounds
graph	graph data structure
cost	reduced costs
pathdist	shortest path distances
vnoi	Voronoi paths
lpobjval	LP objective
extnedges	number of edges for extended problem
initialize	initialize fixing bounds?
undirected	only consider undirected edges

Definition at line 859 of file reduce_bnd.c.

References shortest_path::dist, EAT_LAST, GRAPH::extended, FARAWAY, flipedge, GRAPH::head, Is_pterm, GRAPH::knots, GRAPH::mark, nnodes, GRAPH::oeat, GRAPH::outbeg, SCIP_Real, STP_RSMT, STP_SPG, GRAPH::stp_type, and GRAPH::term.

Referenced by reduce_da(), and reduce_daPcMw().

◆ reduceWithNodeFixingBounds()

static int reduceWithNodeFixingBounds	(	SCIP *	scip,
		GRAPH *	graph,
		GRAPH *	transgraph,
		const SCIP_Real *	fixingbounds,
		SCIP_Real	upperbound
	)

static

eliminate nodes by using fixing-bounds and reduced costs

Parameters

scip	SCIP data structure
graph	graph data structure
transgraph	graph data structure or NULL
fixingbounds	fixing bounds
upperbound	best upperbound

Definition at line 930 of file reduce_bnd.c.

References GRAPH::extended, FALSE, GRAPH::grad, graph_knot_del(), Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, SCIPdebugMessage, SCIPisLT(), STP_RSMT, STP_SPG, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by reduce_da(), and reduce_daPcMw().

◆ reduceWithNodeReplaceBounds()

static int reduceWithNodeReplaceBounds	(	SCIP *	scip,
		GRAPH *	graph,
		const PATH *	vnoi,
		const SCIP_Real *	pathdist,
		const SCIP_Real *	cost,
		const SCIP_Real *	replacebounds,
		int *	nodetouched,
		SCIP_Real	lpobjval,
		SCIP_Real	upperbound
	)

static

Parameters

scip	SCIP data structure
graph	graph data structure
vnoi	Voronoi data structure
pathdist	distance array from shortest path calculations
cost	dual ascent costs
replacebounds	replacement bounds
nodetouched	node array for internal computations
lpobjval	lower bound corresponding to pathdist and vnoi
upperbound	best upperbound

Definition at line 963 of file reduce_bnd.c.

References shortest_path::dist, EAT_LAST, GRAPH::grad, graph_knot_delPseudo(), GRAPH::head, Is_gterm, GRAPH::knots, nnodes, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL_ABORT, SCIP_Real, SCIPisLT(), STP_DABD_MAXDEGREE, STP_DABD_MAXDNEDGES, and GRAPH::term.

Referenced by reduce_da().

◆ reduceWithEdgeFixingBounds()

static int reduceWithEdgeFixingBounds	(	SCIP *	scip,
		GRAPH *	graph,
		GRAPH *	transgraph,
		const SCIP_Real *	fixingbounds,
		const int *	result,
		SCIP_Real	upperbound
	)

static

eliminate edges by using fixing-bounds and reduced costs

Parameters

scip	SCIP data structure
graph	graph data structure
transgraph	graph data structure or NULL
fixingbounds	fixing bounds
result	solution
upperbound	best upperbound

Definition at line 1050 of file reduce_bnd.c.

References CONNECT, EAT_LAST, GRAPH::extended, FALSE, flipedge, graph_edge_del(), graph_sol_valid(), GRAPH::head, Is_pterm, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIPdebugMessage, SCIPisLT(), STP_RSMT, STP_SPG, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by reduce_da(), and reduce_daPcMw().

◆ findDaRoots()

static void findDaRoots	(	SCIP *	scip,
		GRAPH *	graph,
		const GRAPH *	transgraph,
		const SCIP_Real *	cost,
		const SCIP_Real *	bestcost,
		SCIP_Real	lpobjval,
		SCIP_Real	bestlpobjval,
		SCIP_Real	upperbound,
		SCIP_Real	prizesum,
		SCIP_Bool	rerun,
		SCIP_Bool	probrooted,
		PATH *	vnoi,
		int *	state,
		int *	pathedge,
		int *	vbase,
		STP_Bool *	nodearrchar,
		int *	roots,
		int *	rootscount
	)

static

find roots for PC and MW during DA reduction

Parameters

scip	SCIP data structure
graph	graph data structure
transgraph	graph data structure
cost	da reduced cost
bestcost	best incumbent da reduced cost
lpobjval	da lower bound
bestlpobjval	best da lower bound
upperbound	da upper bound
prizesum	sum of positive prizes
rerun	not the first run?
probrooted	is transgraph a rooted RMW or RPC?
vnoi	SP array
state	array
pathedge	array
vbase	array
nodearrchar	bool array
roots	root array
rootscount	number of roots

Definition at line 1110 of file reduce_bnd.c.

References BMSclearMemoryArray, GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::extended, FARAWAY, GRAPH::grad, graph_pc_2org(), graph_pc_2trans(), graph_sdPaths(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_Real, SCIPdebugMessage, SCIPisEQ(), SCIPisGT(), SCIPisPositive(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::term2edge, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by reduce_daPcMw().

◆ markPcMwRoots()

static void markPcMwRoots	(	SCIP *	scip,
		const int *	roots,
		int	nrootsold,
		int	nrootsnew,
		SCIP_Real	prizesum,
		GRAPH *	graph,
		SCIP_Bool *	userec,
		STPSOLPOOL **	solpool
	)

static

set prize of marked terminals to blocked

Parameters

scip	SCIP data structure
roots	root array
nrootsold	old number of roots
nrootsnew	new number of roots
prizesum	sum of positive prizes
graph	graph data structure
userec	recombination?
solpool	solution pool

Definition at line 1312 of file reduce_bnd.c.

References GRAPH::cost, EAT_LAST, GRAPH::extended, FALSE, graph_pc_2org(), graph_pc_2trans(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_pterm, Is_term, NULL, GRAPH::prize, SCIP_Bool, SCIPisEQ(), SCIPisPositive(), SCIPStpHeurRecFreePool(), GRAPH::source, GRAPH::tail, GRAPH::term, and GRAPH::term2edge.

Referenced by reduce_daPcMw().

◆ dualCostIsValid()

static SCIP_Bool dualCostIsValid	(	SCIP *	scip,
		GRAPH *	transgraph,
		const SCIP_Real *	cost,
		int *	nodearrint,
		STP_Bool *	nodearrbool
	)

static

are the dual costs still valid, i.e. are there zero cost paths from the root to all terminals?

Parameters

scip	SCIP data structure
transgraph	graph data structure
cost	dual ascent costs
nodearrint	int array
nodearrbool	bool array

Definition at line 1369 of file reduce_bnd.c.

References a, BMSclearMemoryArray, EAT_LAST, FALSE, GRAPH::head, Is_term, GRAPH::knots, nnodes, GRAPH::oeat, GRAPH::outbeg, SCIPisZero(), GRAPH::source, GRAPH::term, and TRUE.

Referenced by reduce_daPcMw(), and reducePcMwTryBest().

◆ pertubateEdgeCosts()

static void pertubateEdgeCosts	(	SCIP *	scip,
		const GRAPH *	graph,
		GRAPH *	transgraph,
		const int *	result,
		STP_Bool *	nodearrchar,
		int	randomize
	)

static

pertubate edge costs for PCMW dual-ascent

Definition at line 1424 of file reduce_bnd.c.

References BMSclearMemoryArray, CONNECT, GRAPH::cost, EAT_LAST, GRAPH::edges, flipedge, GRAPH::grad, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_gterm, Is_pterm, Is_term, GRAPH::knots, nnodes, PERTUBATION_RATIO, PERTUBATION_RATIO_PC, SCIP_Real, SCIPisPositive(), GRAPH::source, STP_MWCSP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by computePertubedSol().

◆ orderDaRoots()

static SCIP_RETCODE orderDaRoots	(	SCIP *	scip,
		const GRAPH *	graph,
		int *	terms,
		int	nterms,
		SCIP_Bool	randomize,
		SCIP_RANDNUMGEN *	randnumgen
	)

static

order roots

Parameters

scip	SCIP data structure
graph	graph structure
terms	sol int array corresponding to upper bound
nterms	number of terminals
randomize	randomize
randnumgen	random number generator

Definition at line 1564 of file reduce_bnd.c.

References GRAPH::grad, nterms, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPrandomGetInt(), and SCIPsortIntInt().

Referenced by reduce_da(), and reduce_daPcMw().

◆ computeDaSolPcMw()

static SCIP_RETCODE computeDaSolPcMw	(	SCIP *	scip,
		GRAPH *	graph,
		STPSOLPOOL *	pool,
		PATH *	vnoi,
		const SCIP_Real *	cost,
		SCIP_Real *	pathdist,
		SCIP_Real *	upperbound,
		int *	result1,
		int *	result2,
		int *	vbase,
		int *	pathedge,
		STP_Bool *	nodearrchar,
		SCIP_Bool *	apsol
	)

static

compute primal solution during dual-ascent routine for PCSTP or MWCSP

Parameters

scip	SCIP data structure
graph	graph data structure
pool	solution pool
vnoi	Voronoi data structure
cost	dual ascent costs
pathdist	distance array from shortest path calculations
upperbound	upperbound pointer
result1	sol int array corresponding to upper bound
result2	sol int array
vbase	int array
pathedge	int array
nodearrchar	node array storing solution vertices
apsol	ascend-prune sol?

Definition at line 1606 of file reduce_bnd.c.

References BMScopyMemoryArray, GRAPH::cost, GRAPH::edges, FALSE, graph_sol_getObj(), graph_sol_valid(), stp_solution_pool::maxindex, NULL, stp_solution::obj, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisLE(), SCIPisLT(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurRecAddToPool(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), SCIPStpHeurRecSolfromIdx(), stp_solution_pool::size, stp_solution::soledges, stp_solution_pool::sols, STP_MWCSP, GRAPH::stp_type, and TRUE.

Referenced by computePertubedSol(), and reduce_daPcMw().

◆ computePertubedSol()

static SCIP_RETCODE computePertubedSol	(	SCIP *	scip,
		GRAPH *	graph,
		GRAPH *	transgraph,
		STPSOLPOOL *	pool,
		PATH *	vnoi,
		GNODE **	gnodearr,
		SCIP_Real *	cost,
		SCIP_Real *	costrev,
		SCIP_Real *	bestcost,
		SCIP_Real *	pathdist,
		int *	state,
		int *	vbase,
		int *	pathedge,
		int *	result,
		int *	result2,
		int *	transresult,
		STP_Bool *	nodearrchar,
		SCIP_Real *	upperbound,
		SCIP_Real *	lpobjval,
		SCIP_Real *	bestlpobjval,
		SCIP_Real *	minpathcost,
		SCIP_Bool *	apsol,
		SCIP_Real	offset,
		int	extnedges,
		int	pertubation
	)

static

try to improve both dual and primal solution

Definition at line 1716 of file reduce_bnd.c.

References BMScopyMemoryArray, bound, computeDaSolPcMw(), CONNECT, GRAPH::cost, EAT_LAST, GRAPH::edges, FALSE, graph_pc_2transcheck(), graph_sol_getObj(), graph_sol_valid(), graph_valid(), GRAPH::head, Is_term, GRAPH::knots, NULL, GRAPH::oeat, GRAPH::outbeg, pertubateEdgeCosts(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisGE(), SCIPisLE(), SCIPStpDualAscent(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), GRAPH::source, STP_MWCSP, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.

Referenced by reduce_daPcMw().

◆ computeTransVoronoi()

static void computeTransVoronoi	(	SCIP *	scip,
		GRAPH *	transgraph,
		PATH *	vnoi,
		const SCIP_Real *	cost,
		SCIP_Real *	costrev,
		SCIP_Real *	pathdist,
		int *	vbase,
		int *	pathedge
	)

static

compute Voronoi region for dual-ascent elimination for PC/MW

Definition at line 1863 of file reduce_bnd.c.

References EAT_LAST, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_path_execX(), graph_voronoiTerms(), Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, SCIPisEQ(), GRAPH::source, and GRAPH::term.

Referenced by reduce_daPcMw(), and reducePcMwTryBest().

◆ reduceSPG()

static int reduceSPG	(	SCIP *	scip,
		GRAPH *	graph,
		SCIP_Real *	offset,
		STP_Bool *	marked,
		STP_Bool *	nodearrchar,
		const PATH *	vnoi,
		const SCIP_Real *	cost,
		const SCIP_Real *	pathdist,
		const int *	result,
		SCIP_Real	minpathcost,
		int	root,
		SCIP_Bool	solgiven
	)

static

reduce SPG graph based on information from dual ascent and given upper bound

Parameters

scip	SCIP data structure
graph	graph data structure
offset	offset pointer
marked	edge array to mark which (directed) edge can be removed
nodearrchar	node array storing solution vertices
vnoi	Voronoi data structure
cost	dual ascent costs
pathdist	distance array from shortest path calculations
result	sol int array
minpathcost	the required reduced path cost to be surpassed
root	the root
solgiven	is sol given?

Definition at line 1902 of file reduce_bnd.c.

References CONNECT, shortest_path::dist, EAT_LAST, GRAPH::edges, FALSE, flipedge, GRAPH::grad, graph_edge_del(), graph_knot_del(), graph_pc_2org(), graph_pc_deleteTerm(), GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nnodes, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_Real, SCIPisEQ(), SCIPisGT(), SCIPisZero(), STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by reduce_da().

◆ reducePcMw()

static int reducePcMw	(	SCIP *	scip,
		GRAPH *	graph,
		GRAPH *	transgraph,
		const PATH *	vnoi,
		const SCIP_Real *	cost,
		const SCIP_Real *	pathdist,
		SCIP_Real	minpathcost,
		const int *	result,
		STP_Bool *	marked,
		STP_Bool *	nodearrchar,
		SCIP_Bool	solgiven
	)

static

reduce PCSTP or MWCS graph based on information from dual ascent and given upper bound

Parameters

scip	SCIP data structure
graph	graph data structure
transgraph	graph data structure
vnoi	Voronoi data structure
cost	dual ascent costs
pathdist	distance array from shortest path calculations
minpathcost	the required reduced path cost to be surpassed
result	sol int array
marked	edge array to mark which (directed) edge can be removed
nodearrchar	node array storing solution vertices
solgiven	is sol given?

Definition at line 2010 of file reduce_bnd.c.

References CONNECT, shortest_path::dist, EAT_FREE, EAT_LAST, GRAPH::edges, FALSE, flipedge, GRAPH::grad, graph_edge_del(), graph_pc_2orgcheck(), graph_sol_valid(), GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_Real, SCIPdebugMessage, SCIPisGE(), SCIPisGT(), SCIPisZero(), GRAPH::source, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by reduce_daPcMw(), and reducePcMwTryBest().

◆ reducePcMwTryBest()

static int reducePcMwTryBest	(	SCIP *	scip,
		GRAPH *	graph,
		GRAPH *	transgraph,
		PATH *	vnoi,
		const SCIP_Real *	cost,
		SCIP_Real *	costrev,
		SCIP_Real *	bestcost,
		SCIP_Real *	pathdist,
		SCIP_Real *	upperbound,
		SCIP_Real *	lpobjval,
		SCIP_Real *	bestlpobjval,
		SCIP_Real *	minpathcost,
		SCIP_Real	oldupperbound,
		const int *	result,
		int *	vbase,
		int *	state,
		int *	pathedge,
		STP_Bool *	marked,
		STP_Bool *	nodearrchar,
		SCIP_Bool *	solgiven,
		int	extnedges
	)

static

try to run reduction method for best known reduced costs (if they are valid)

Parameters

scip	SCIP data structure
graph	graph data structure
transgraph	graph data structure
vnoi	Voronoi data structure
cost	dual ascent costs
costrev	SCIP_Real array
bestcost	best dual ascent costs
pathdist	distance array from shortest path calculations
upperbound	upper bound
lpobjval	reduced cost value
bestlpobjval	best reduced cost value
minpathcost	the required reduced path cost to be surpassed
oldupperbound	old upper bound
result	sol int array
vbase	array for Voronoi bases
state	int 4 * nnodes array for internal computations
pathedge	array for predecessor edge on a path
marked	edge array to mark which (directed) edge can be removed
nodearrchar	node array storing solution vertices
solgiven	is sol given?
extnedges	number of edges for transgraph

Definition at line 2159 of file reduce_bnd.c.

References BMScopyMemoryArray, computeTransVoronoi(), dualCostIsValid(), graph_sol_unreduced(), graph_sol_valid(), reducePcMw(), SCIP_Bool, SCIPisGE(), SCIPisGT(), and SCIPisLT().

Referenced by reduce_daPcMw().

◆ reduceCheckEdge()

static SCIP_RETCODE reduceCheckEdge	(	SCIP *	scip,
		const GRAPH *	graph,
		int	root,
		const SCIP_Real *	redcost,
		const SCIP_Real *	pathdist,
		const PATH *	vnoi,
		SCIP_Real	cutoff,
		int	edge,
		SCIP_Bool	equality,
		int *	edgestack,
		SCIP_Bool *	deletable,
		unsigned int *	eqstack,
		int *	eqstack_size,
		SCIP_Bool *	eqmark
	)

static

check (directed) edge

Parameters

scip	SCIP data structure
graph	graph data structure
root	graph root from dual ascent
redcost	reduced costs
pathdist	shortest path distances
vnoi	Voronoi paths
cutoff	cutoff value
edge	(directed) edge to be checked
equality	allow equality?
edgestack	array of size nodes for internal computations
deletable	is edge deletable?
eqstack	stores edges that were used for equality comparison
eqstack_size	pointer to size of eqstack
eqmark	marks edges that were used for equality comparison

Definition at line 2211 of file reduce_bnd.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, markAncestors(), MAX, nnodes, NULL, GRAPH::oeat, GRAPH::orgedges, GRAPH::outbeg, ruleOutSubtree(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocCleanBufferArray, SCIPfreeCleanBufferArray, SCIPisEQ(), SCIPisGE(), SCIPisGT(), shortenSubtree(), STP_DAEX_EDGELIMIT, STP_DAEX_MAXDFSDEPTH, STP_DAEX_MAXGRAD, STP_DAEX_MINDFSDEPTH, STP_DAEX_MINGRAD, GRAPH::tail, GRAPH::term, TRUE, truncateSubtree(), and unmarkAncestors().

Referenced by reduce_extendedEdge().

◆ reduce_deleteConflictEdges()

SCIP_RETCODE reduce_deleteConflictEdges	(	SCIP *	scip,
		GRAPH *	g
	)

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

Parameters

scip	SCIP data structure
g	the graph

Definition at line 2421 of file reduce_bnd.c.

References GRAPH::ancestors, EAT_FREE, GRAPH::edges, FALSE, graph_edge_del(), markAncestorsConflict(), MAX, NULL, GRAPH::oeat, GRAPH::orgedges, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, TRUE, and unmarkAncestorsConflict().

Referenced by redLoopStp(), and reduce_da().

◆ reduce_check3Tree()

SCIP_RETCODE reduce_check3Tree	(	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,
		int *	edgestack,
		SCIP_Real *	treebound,
		SCIP_Bool *	ruleout,
		unsigned int *	eqstack,
		int *	eqstack_size,
		SCIP_Bool *	eqmark
	)

check 3-tree

Parameters

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

Definition at line 2464 of file reduce_bnd.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, ruleOutSubtree(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocCleanBufferArray, SCIPfreeCleanBufferArray, SCIPisGE(), SCIPisGT(), shortenSubtree(), STP_DAEX_EDGELIMIT, STP_DAEX_MAXDFSDEPTH, STP_DAEX_MAXGRAD, STP_DAEX_MINDFSDEPTH, STP_DAEX_MINGRAD, 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,
		int *	nodearr,
		STP_Bool *	marked
	)

reduce SPG graph based on reduced cost information and given upper bound

Parameters

scip	SCIP data structure
graph	graph data structure
vnoi	Voronoi data structure
cost	dual ascent costs
pathdist	distance array from shortest path calculations
result	sol int array
minpathcost	the required reduced path cost to be surpassed
root	the root
nodearr	for internal stuff
marked	edge array to mark which (directed) edge can be removed

Definition at line 2774 of file reduce_bnd.c.

References CONNECT, EAT_FREE, GRAPH::edges, FALSE, GRAPH::grad, graph_edge_del(), graph_pc_2orgcheck(), GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, reduceCheckEdge(), SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPisZero(), STP_RPCSPG, GRAPH::stp_type, and TRUE.

Referenced by reduce_da(), and reduceRedcostExtended().

◆ reduce_da()

SCIP_RETCODE reduce_da	(	SCIP *	scip,
		GRAPH *	graph,
		PATH *	vnoi,
		GNODE **	gnodearr,
		SCIP_Real *	cost,
		SCIP_Real *	costrev,
		SCIP_Real *	pathdist,
		SCIP_Real *	ub,
		SCIP_Real *	offset,
		int *	edgearrint,
		int *	vbase,
		int *	state,
		int *	pathedge,
		int *	nodearrint,
		int *	heursources,
		STP_Bool *	nodearrchar,
		int *	nelims,
		int	prevrounds,
		SCIP_RANDNUMGEN *	randnumgen,
		SCIP_Bool	userec,
		SCIP_Bool	extended
	)

dual ascent based reductions

Parameters

scip	SCIP data structure
graph	graph data structure
vnoi	Voronoi data structure
gnodearr	GNODE* terminals array for internal computations or NULL
cost	edge costs
costrev	reverse edge costs
pathdist	distance array for shortest path calculations
ub	pointer to provide upper bound and return upper bound found during ascent and prune (if better)
offset	pointer to store offset
edgearrint	int edges array for internal computations or NULL
vbase	array for Voronoi bases
state	int 4 * nnodes array for internal computations
pathedge	array for predecessor edge on a path
nodearrint	int nnodes array for internal computations
heursources	array to store starting points of TM heuristic
nodearrchar	STP_Bool node array for internal computations
nelims	pointer to store number of reduced edges
prevrounds	number of reduction rounds that have been performed already
randnumgen	random number generator
userec	use recombination heuristic?
extended	use extended tests?

Definition at line 2861 of file reduce_bnd.c.

References BMScopyMemoryArray, GRAPH::cost, DAMAXDEVIATION_RANDOM_LOWER, DAMAXDEVIATION_RANDOM_UPPER, DEFAULT_DARUNS, DEFAULT_HEURRUNS, EAT_LAST, GRAPH::edges, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_get4nextTerms(), graph_path_execX(), graph_pc_2org(), graph_pc_2trans(), graph_pc_2transcheck(), graph_sol_getObj(), graph_sol_reroot(), graph_sol_valid(), graph_valid(), graph_voronoiTerms(), Is_term, GRAPH::knots, level0(), GRAPH::mark, stp_solution_pool::maxindex, nnodes, nterms, NULL, stp_solution::obj, GRAPH::oeat, orderDaRoots(), GRAPH::outbeg, GRAPH::path_heap, reduce_deleteConflictEdges(), reduce_extendedEdge(), reduceSPG(), reduceWithEdgeFixingBounds(), reduceWithNodeFixingBounds(), reduceWithNodeReplaceBounds(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPisGE(), SCIPisLE(), SCIPisLT(), SCIPisZero(), SCIPrandomGetInt(), SCIPrandomGetReal(), SCIPStpDualAscent(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurRecAddToPool(), SCIPStpHeurRecFreePool(), SCIPStpHeurRecInitPool(), SCIPStpHeurRecRun(), SCIPStpHeurRecSolfromIdx(), SCIPStpHeurTMCompStarts(), SCIPStpHeurTMRun(), stp_solution_pool::size, stp_solution::soledges, SOLPOOL_SIZE, GRAPH::source, STP_NWSPG, STP_RPCSPG, STP_RSMT, STP_SAP, GRAPH::stp_type, GRAPH::term, GRAPH::terms, TRUE, UNKNOWN, updateEdgeFixingBounds(), updateNodeFixingBounds(), and updateNodeReplaceBounds().

Referenced by redLoopPc(), redLoopStp(), reduceNw(), and reduceSap().

◆ reduce_daSlackPrune()

SCIP_RETCODE reduce_daSlackPrune	(	SCIP *	scip,
		SCIP_VAR **	vars,
		GRAPH *	graph,
		PATH *	vnoi,
		GNODE **	gnodearr,
		SCIP_Real *	cost,
		SCIP_Real *	costrev,
		SCIP_Real *	pathdist,
		SCIP_Real *	upperbound,
		int *	edgearrint,
		int *	edgearrint2,
		int *	vbase,
		int *	pathedge,
		int *	state,
		int *	solnode,
		STP_Bool *	nodearrchar,
		STP_Bool *	edgearrchar,
		int *	nelims,
		int	minelims,
		SCIP_Bool	solgiven
	)

dual ascent reduction for slack-and-prune heuristic

Parameters

scip	SCIP data structure
vars	problem variables or NULL
graph	graph data structure
vnoi	Voronoi data structure
gnodearr	GNODE* terminals array for internal computations or NULL
cost	array to store reduced costs
costrev	reverse edge costs
pathdist	distance array for shortest path calculations
upperbound	pointer to store new upper bound
edgearrint	int edges array to store solution value
edgearrint2	int edges array for internal computations
vbase	array for Voronoi bases
pathedge	array for predecessor edge on a path
state	int 4 * nnodes array for internal computations
solnode	array of nodes of current solution that is not to be destroyed
nodearrchar	STP_Bool node array for internal computations
edgearrchar	STP_Bool edge array for internal computations
nelims	pointer to store number of reduced edges
minelims	minimum number of edges to eliminate
solgiven	solution provided?

Definition at line 3279 of file reduce_bnd.c.

References a, CONNECT, GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_get4nextTerms(), graph_path_exec(), graph_path_execX(), graph_pc_2org(), graph_pc_2trans(), graph_sol_getObj(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPepsilon(), SCIPfreeBufferArray, SCIPintListNodeFree(), SCIPisEQ(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPqueueCreate(), SCIPqueueFree(), SCIPqueueInsert(), SCIPqueueIsEmpty(), SCIPqueueRemove(), SCIPsortReal(), SCIPStpDualAscent(), SCIPStpHeurAscendPruneRun(), GRAPH::source, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

Referenced by SCIPStpHeurSlackPruneRun().

◆ reduce_daPcMw()

SCIP_RETCODE reduce_daPcMw	(	SCIP *	scip,
		GRAPH *	graph,
		PATH *	vnoi,
		GNODE **	gnodearr,
		SCIP_Real *	cost,
		SCIP_Real *	costrev,
		SCIP_Real *	pathdist,
		int *	vbase,
		int *	pathedge,
		int *	edgearrint,
		int *	state,
		STP_Bool *	nodearrchar,
		int *	nelims,
		SCIP_Bool	solbasedda,
		SCIP_Bool	varyroot,
		SCIP_Bool	markroots,
		SCIP_Bool	userec,
		SCIP_Bool	fastmode,
		SCIP_RANDNUMGEN *	randnumgen,
		SCIP_Real	prizesum
	)

dual ascent based reductions for PCSPG and MWCSP

Parameters

scip	SCIP data structure
graph	graph data structure
vnoi	Voronoi data structure array
gnodearr	GNODE* terminals array for internal computations or NULL
cost	reduced edge costs
costrev	reduced reverse edge costs
pathdist	distance array for shortest path calculations
vbase	Voronoi base array
pathedge	shortest path incoming edge array for shortest path calculations
edgearrint	int edges array for internal computations or NULL
state	int 4 * vertices array
nodearrchar	STP_Bool node array for internal computations
nelims	pointer to store number of reduced edges
solbasedda	rerun Da based on best primal solution
varyroot	vary root for DA if possible
markroots	should terminals proven to be part of an opt. sol. be marked as such?
userec	use recombination heuristic?
fastmode	run heuristic in fast mode?
randnumgen	random number generator
prizesum	sum of positive prizes

Definition at line 3801 of file reduce_bnd.c.

References BMScopyMemoryArray, computeDaSolPcMw(), computePertubedSol(), computeTransVoronoi(), GRAPH::cost, DAMAXDEVIATION_FAST, DEFAULT_HEURRUNS, DEFAULT_NMAXROOTS, dualCostIsValid(), EAT_LAST, GRAPH::edges, FALSE, FARAWAY, findDaRoots(), flipedge, GRAPH::grad, graph_free(), graph_get2next(), graph_init_history(), graph_path_execX(), graph_path_exit(), graph_path_init(), graph_pc_2org(), graph_pc_2orgcheck(), graph_pc_2trans(), graph_pc_getRsap(), graph_pc_getSap(), graph_sol_getObj(), graph_sol_reroot(), graph_sol_unreduced(), graph_sol_valid(), graph_valid(), graph_voronoiTerms(), GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, markPcMwRoots(), nnodes, nterms, NULL, stp_solution::obj, GRAPH::oeat, orderDaRoots(), GRAPH::outbeg, GRAPH::path_heap, GRAPH::prize, reducePcMw(), reducePcMwTryBest(), reduceWithEdgeFixingBounds(), reduceWithNodeFixingBounds(), roots, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPisEQ(), SCIPisGT(), SCIPStpDualAscent(), SCIPStpHeurLocalRun(), SCIPStpHeurRecAddToPool(), SCIPStpHeurRecFreePool(), SCIPStpHeurRecInitPool(), SCIPStpHeurTMRun(), SOLPOOL_SIZE, stp_solution_pool::sols, GRAPH::source, STP_MWCSP, STP_RED_MINBNDTERMS, STP_RPCSPG, STP_SAP, GRAPH::stp_type, GRAPH::term, GRAPH::terms, TRUE, updateEdgeFixingBounds(), and updateNodeFixingBounds().

Referenced by redLoopMw(), and redLoopPc().

◆ reduce_daSlackPruneMw()

SCIP_RETCODE reduce_daSlackPruneMw	(	SCIP *	scip,
		GRAPH *	graph,
		PATH *	vnoi,
		GNODE **	gnodearr,
		SCIP_Real *	cost,
		SCIP_Real *	costrev,
		SCIP_Real *	pathdist,
		int *	vbase,
		int *	pathedge,
		int *	soledge,
		int *	state,
		int *	solnode,
		STP_Bool *	nodearrchar,
		int *	nelims,
		int	minelims,
		SCIP_Bool	solgiven
	)

dual ascent based heuristic reductions for MWCSP

Parameters

scip	SCIP data structure
graph	graph data structure
vnoi	Voronoi data structure array
gnodearr	GNODE* terminals array for internal computations or NULL
cost	edge costs
costrev	reverse edge costs
pathdist	distance array for shortest path calculations
vbase	Voronoi base array
pathedge	shortest path incoming edge array for shortest path calculations
soledge	edge solution array (CONNECT/UNKNOWN) or NULL; needs to contain solution if solgiven == TRUE
state	int 4 * vertices array
solnode	array of nodes of current solution that is not to be destroyed
nodearrchar	STP_Bool node array for internal computations
nelims	pointer to store number of reduced edges
minelims	minimum number of edges to eliminate
solgiven	solution provided?

Definition at line 4237 of file reduce_bnd.c.

References CONNECT, GRAPH::cost, DEFAULT_HEURRUNS, DEFAULT_HOPFACTOR, shortest_path::dist, EAT_LAST, GRAPH::edges, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_free(), graph_init_history(), graph_path_execX(), graph_path_exit(), graph_path_init(), graph_pc_2org(), graph_pc_2trans(), graph_pc_getSap(), graph_sol_getObj(), graph_sol_valid(), graph_voronoiTerms(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPepsilon(), SCIPfindHeur(), SCIPfreeBufferArray, SCIPheurGetData(), SCIPintListNodeFree(), SCIPisEQ(), SCIPisGE(), SCIPisGT(), SCIPisLE(), SCIPprobdataGetOffset(), SCIPsortReal(), SCIPStpDualAscent(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurTMPrunePc(), SCIPStpHeurTMRun(), GRAPH::source, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by SCIPStpHeurSlackPruneRunPcMw().

◆ reduce_bound()

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

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

Parameters

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

Definition at line 4653 of file reduce_bnd.c.

References BLOCKED, bound, CONNECT, GRAPH::cost, DEFAULT_HEURRUNS, DEFAULT_HOPFACTOR, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_free(), graph_get2next(), graph_get3next(), graph_get4next(), graph_get4nextTTerms(), graph_init(), graph_knot_chg(), graph_knot_delPseudo(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_pc_2org(), graph_pc_2trans(), graph_pc_deleteTerm(), graph_valid(), graph_voronoiWithRadius(), GRAPH::head, Is_pterm, Is_term, GRAPH::knots, 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, SCIPfindHeur(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPheurGetData(), SCIPisGE(), SCIPisGT(), SCIPisLT(), SCIPsortReal(), SCIPsortRealInt(), SCIPStpHeurTMCompStarts(), SCIPStpHeurTMRun(), GRAPH::source, STP_DHCSTP, STP_MWCSP, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by redLoopPc(), redLoopStp(), and reduceHc().

◆ reduce_boundMw()

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

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

Parameters

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

Definition at line 5243 of file reduce_bnd.c.

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

Referenced by redLoopMw().

◆ reduce_boundPrune()

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

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

Parameters

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

Definition at line 5415 of file reduce_bnd.c.

References BLOCKED, bound, CONNECT, GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_free(), graph_get2next(), graph_get3next(), graph_init(), graph_knot_chg(), graph_knot_delPseudo(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_valid(), graph_voronoiMw(), graph_voronoiWithRadius(), GRAPH::head, Is_gterm, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_state, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPepsilon(), SCIPfreeBufferArray, SCIPisGE(), SCIPisGT(), SCIPisLT(), SCIPsortReal(), GRAPH::source, STP_DHCSTP, STP_MWCSP, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by SCIPStpHeurPruneRun().

◆ reduce_boundHop()

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

bound-based reduction test for the HCDSTP

Definition at line 5904 of file reduce_bnd.c.

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

Referenced by reduceHc().

◆ reduce_boundHopR()

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

hop bound-based reduction test for the HCDSTP

Definition at line 6098 of file reduce_bnd.c.

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

Referenced by reduceHc().

◆ reduce_boundHopRc()

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

Definition at line 6226 of file reduce_bnd.c.

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

Referenced by reduceHc().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ DEFAULT_HEURRUNS

◆ DEFAULT_DARUNS

◆ DEFAULT_NMAXROOTS

◆ PERTUBATION_RATIO

◆ PERTUBATION_RATIO_PC

◆ SOLPOOL_SIZE

◆ STP_RED_MINBNDTERMS

◆ STP_DABD_MAXDEGREE

◆ STP_DABD_MAXDNEDGES

◆ STP_DAEX_MAXDFSDEPTH

◆ STP_DAEX_MINDFSDEPTH

◆ STP_DAEX_MAXGRAD

◆ STP_DAEX_MINGRAD

◆ STP_DAEX_EDGELIMIT

◆ DAMAXDEVIATION_RANDOM_LOWER

◆ DAMAXDEVIATION_RANDOM_UPPER

◆ DAMAXDEVIATION_FAST

◆ EXEDGE_FREE

◆ EXEDGE_FIXED

◆ EXEDGE_KILLED

Function Documentation

◆ markAncestorsConflict()

◆ markAncestors()

◆ unmarkAncestorsConflict()

◆ unmarkAncestors()

◆ finalizeSubtree()

◆ truncateSubtree()

◆ shortenSubtree()

◆ extendSubtreeHead()

◆ extendSubtreeTail()

◆ updateEqArrays()

◆ bottleneckRuleOut()

◆ ruleOutSubtree()

◆ updateNodeFixingBounds()

◆ updateNodeReplaceBounds()

◆ updateEdgeFixingBounds()

◆ reduceWithNodeFixingBounds()

◆ reduceWithNodeReplaceBounds()

◆ reduceWithEdgeFixingBounds()

◆ findDaRoots()

◆ markPcMwRoots()

◆ dualCostIsValid()

◆ pertubateEdgeCosts()

◆ orderDaRoots()

◆ computeDaSolPcMw()

◆ computePertubedSol()

◆ computeTransVoronoi()

◆ reduceSPG()

◆ reducePcMw()

◆ reducePcMwTryBest()

◆ reduceCheckEdge()

◆ reduce_deleteConflictEdges()

◆ reduce_check3Tree()

◆ reduce_extendedEdge()

◆ reduce_da()

◆ reduce_daSlackPrune()

◆ reduce_daPcMw()

◆ reduce_daSlackPruneMw()

◆ reduce_bound()

◆ reduce_boundMw()

◆ reduce_boundPrune()

◆ reduce_boundHop()

◆ reduce_boundHopR()

◆ reduce_boundHopRc()