Solving Constraint Integer Programs

reducedefs.h File Reference

Detailed Description

includes reductions definitions and inline methods used for Steiner tree problems

Daniel Rehfeldt

Definition in file reducedefs.h.

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

Go to the source code of this file.

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


#define STP_DAMODE_HOPS   -9991
#define STP_DAMODE_FAST   0


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


  extred_none = 0,
  extred_fast = 1,
  extred_full = 2


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



Definition at line 39 of file reducedefs.h.

Referenced by reduce_exec(), and SCIPprobdataCreateFromGraph().



Definition at line 40 of file reducedefs.h.

Referenced by reduce_exec().



Definition at line 41 of file reducedefs.h.

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


#define STP_DAMODE_HOPS   -9991

Definition at line 43 of file reducedefs.h.

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




Definition at line 45 of file reducedefs.h.

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



Definition at line 46 of file reducedefs.h.

Typedef Documentation


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.


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.


SD distance graph data

Definition at line 56 of file reducedefs.h.


SD neighbors

Definition at line 59 of file reducedefs.h.


link-cut tree for bottleneck operations

Definition at line 62 of file reducedefs.h.


primal solution data retained during reduction process

Definition at line 65 of file reducedefs.h.


INTERNAL primal solution data retained during reduction loop

Definition at line 68 of file reducedefs.h.


typedef struct reduction_parameters RPARAMS

reduction parameters


bi-decomposition reduction parameters


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


reduced cost reduction parameters


single special distance for PC

Enumeration Type Documentation



Definition at line 71 of file reducedefs.h.

Function Documentation

◆ reduce_sdprofitGetProfit()

◆ reduce_sdprofitGetBiasedDist()

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

gets biased distance

sdprofitthe SD profit
nodenode along which to get biased distance
edgecostedge cost
nodedistnode distance
nonsource1node that should not be a source
nonsource2node that should not be a source

Definition at line 214 of file reducedefs.h.

References GE, reduce_sdprofitGetProfit(), and SCIP_Real.

Referenced by tpathsGetDistNew(), and tpathsScan1st().