Detailed Description

includes reductions definitions and inline methods used for Steiner tree problems

Author: Daniel Rehfeldt

Definition in file reducedefs.h.

#include "scip/scip.h"
#include "portab.h"

Data Structures
struct	reduction_parameters

struct	bidecomposition_reduction_parameters

struct	reduction_base

struct	special_distance_storage

struct	special_distance_implied_profit

struct	reduce_costs_reduction_parameters

struct	single_special_distance_pc

Macros
#define	STP_REDUCTION_NONE 0

#define	STP_REDUCTION_BASIC 1

#define	STP_REDUCTION_ADVANCED 2

#define	STP_DAMODE_HOPS -9991

#define	STP_DAMODE_FAST 0

#define	STP_DAMODE_MEDIUM 1

#define	STP_DAMODE_EXTENSIVE 2

Typedefs
typedef struct dynamic_complete_minimum_spanning_tree	DCMST

typedef struct node_one_hop_star	STAR

typedef struct special_distance_graph	SDGRAPH

typedef struct special_distance_neighbors	SDN

typedef struct bottleneck_link_cut_tree	BLCTREE

typedef struct reduction_solution_storage	REDSOL

typedef struct reduction_local_solution_storage	REDSOLLOCAL

typedef struct reduction_parameters	RPARAMS

typedef struct bidecomposition_reduction_parameters	BIDECPARAMS

typedef struct reduction_base	REDBASE

typedef struct special_distance_storage	SD

typedef struct reduce_costs_reduction_parameters	RPDA

typedef struct single_special_distance_pc	SD1PC

Enumerations
enum	EXTRED_MODE { extred_none = 0, extred_fast = 1, extred_full = 2 }

Functions
static SCIP_Real	reduce_sdprofitGetProfit (const SDPROFIT *sdprofit, int node, int nonsource1, int nonsource2)

static SCIP_Real	reduce_sdprofitGetBiasedDist (const SDPROFIT *sdprofit, int node, SCIP_Real edgecost, SCIP_Real nodedist, int nonsource1, int nonsource2)

Macro Definition Documentation

◆ STP_REDUCTION_NONE

#define STP_REDUCTION_NONE 0

Definition at line 39 of file reducedefs.h.

Referenced by reduce_exec(), and SCIPprobdataCreateFromGraph().

◆ STP_REDUCTION_BASIC

#define STP_REDUCTION_BASIC 1

Definition at line 40 of file reducedefs.h.

Referenced by reduce_exec().

◆ STP_REDUCTION_ADVANCED

#define STP_REDUCTION_ADVANCED 2

Definition at line 41 of file reducedefs.h.

Referenced by graph_writeReductionRatioStatsLive(), reduce_exec(), and SCIPStpHeurRecRun().

◆ STP_DAMODE_HOPS

#define STP_DAMODE_HOPS -9991

Definition at line 43 of file reducedefs.h.

Referenced by daGetNruns(), reduce_boundHopDa(), and reduce_da().

◆ STP_DAMODE_FAST

#define STP_DAMODE_FAST 0

Definition at line 44 of file reducedefs.h.

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

◆ STP_DAMODE_MEDIUM

#define STP_DAMODE_MEDIUM 1

Definition at line 45 of file reducedefs.h.

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

◆ STP_DAMODE_EXTENSIVE

#define STP_DAMODE_EXTENSIVE 2

Definition at line 46 of file reducedefs.h.

Typedef Documentation

◆ DCMST

typedef struct dynamic_complete_minimum_spanning_tree DCMST

lightweight minimum spanning tree structure that allows to add vertices to given MST on complete graph (in CSR format)

Definition at line 50 of file reducedefs.h.

◆ STAR

typedef struct node_one_hop_star STAR

auxiliary data structure for ruling out all 1-hop stars of a given node

Definition at line 53 of file reducedefs.h.

◆ SDGRAPH

typedef struct special_distance_graph SDGRAPH

SD distance graph data

Definition at line 56 of file reducedefs.h.

◆ SDN

typedef struct special_distance_neighbors SDN

SD neighbors

Definition at line 59 of file reducedefs.h.

◆ BLCTREE

typedef struct bottleneck_link_cut_tree BLCTREE

link-cut tree for bottleneck operations

Definition at line 62 of file reducedefs.h.

◆ REDSOL

typedef struct reduction_solution_storage REDSOL

primal solution data retained during reduction process

Definition at line 65 of file reducedefs.h.

◆ REDSOLLOCAL

typedef struct reduction_local_solution_storage REDSOLLOCAL

INTERNAL primal solution data retained during reduction loop

Definition at line 68 of file reducedefs.h.

◆ RPARAMS

typedef struct reduction_parameters RPARAMS

reduction parameters

◆ BIDECPARAMS

typedef struct bidecomposition_reduction_parameters BIDECPARAMS

bi-decomposition reduction parameters

◆ REDBASE

typedef struct reduction_base REDBASE

reduction information and some buffers

◆ SD

typedef struct special_distance_storage SD

Stores data for computation of special distance/bottleneck distance computations

◆ RPDA

typedef struct reduce_costs_reduction_parameters RPDA

reduced cost reduction parameters

◆ SD1PC

typedef struct single_special_distance_pc SD1PC

single special distance for PC

Enumeration Type Documentation

◆ EXTRED_MODE

enum EXTRED_MODE

Enumerator
extred_none
extred_fast
extred_full

Definition at line 71 of file reducedefs.h.

Function Documentation

◆ reduce_sdprofitGetProfit()

static SCIP_Real reduce_sdprofitGetProfit	(	const SDPROFIT *	sdprofit,
		int	node,
		int	nonsource1,
		int	nonsource2
	)

inlinestatic

gets profit for given node

Parameters

sdprofit	the SD profit
node	node to get profit for
nonsource1	node that should not be a source
nonsource2	node that should not be a source

Definition at line 178 of file reducedefs.h.

References FARAWAY, GE, LE, special_distance_implied_profit::nodes_bias, special_distance_implied_profit::nodes_bias2, special_distance_implied_profit::nodes_biassource, and special_distance_implied_profit::nodes_biassource2.

Referenced by bdkNodeIsInvalid(), closeNodesRunCompute(), distgraphGetBoundaryEdgeDist(), distgraphGetBoundaryEdgeDist2(), extreduce_mstbiasedCheck3NodeSimple(), graph_sdCloseNodesBiased(), graph_sdStarBiased(), graph_tpathsGetProfitNodes(), nsvExec(), pseudodeleteNodeIsPromising(), reduce_sdBiased(), reduce_sdprofitGetBiasedDist(), sdCliqueStarComputeSds(), sdCliqueStarGetFinalProfitData(), sdCliqueStarGetNodeBias(), tpathsPrintPath(), and vnoiComputeImplied().

◆ reduce_sdprofitGetBiasedDist()

static SCIP_Real reduce_sdprofitGetBiasedDist	(	const SDPROFIT *	sdprofit,
		int	node,
		SCIP_Real	edgecost,
		SCIP_Real	nodedist,
		int	nonsource1,
		int	nonsource2
	)