reduce_base.c File Reference

Detailed Description

Reduction tests for Steiner problems.

Author

Daniel Rehfeldt

This file includes several packages of reduction techniques for different Steiner problem variants.

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

Definition in file reduce_base.c.

#include "mincut.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "graph.h"
#include "reduce.h"
#include "heur_tm.h"
#include "misc_stp.h"
#include "scip/scip.h"
#include "probdata_stp.h"
#include "prop_stp.h"
#include "portab.h"
#include "dpterms.h"
#include "relax_stpenum.h"

Go to the source code of this file.

Macros
#define	REDUCE_C
#define	STP_RED_EXTENSIVE   FALSE
#define	STP_REDBOUND_SDSP   200
#define	STP_REDBOUND_SDSP2   800
#define	STP_REDBOUND_PCBDK   80
#define	STP_REDBOUND_PCBDK2   400
#define	STP_REDBOUND_BDK   400
#define	STP_REDBOUND_BDK2   600
#define	STP_REDBOUND_SDSTAR   400
#define	STP_REDBOUND_SDSTAR2   800
#define	STP_RED_MWTERMBOUND   400
#define	STP_RED_EXPENSIVEFACTOR   2
#define	STP_RED_GLBFACTOR   3
#define	STP_RED_EDGELIMIT   100000
#define	STP_RED_EDGELIMIT_HUGE   1000000
#define	STP_RED_MAXNINNROUNDS   15
#define	STP_RED_MAXNOUTROUNDS_PC   4
#define	STP_RED_MAXNOUTROUNDS_MW   4
#define	STP_BND_THRESHOLD   0.03
#define	USE_FULLSEPA

Enumerations
enum	PC_REDTYPE {   pc_sdc,   pc_sdstar,   pc_sdstar2,   pc_sdw1,   pc_sdw2,   pc_bd3 }
enum	STP_REDTYPE {   stp_bdk,   stp_sdstar,   stp_sdstarbot }

Functions
static int	getWorkLimitsStp (const GRAPH *g, int roundnumber, SCIP_Bool fullreduce, enum STP_REDTYPE redtype)
static int	getWorkLimitsPc (const GRAPH *g, int roundnumber, SCIP_Bool beFast, enum PC_REDTYPE redtype)
static void	reduceStatsPrint (SCIP_Bool print, const char *method, int nelims)
static SCIP_RETCODE	execNvSl (SCIP *scip, const int *edgestate, GRAPH *g, PATH *vnoi, SCIP_Real *nodearrreal, SCIP_Real *fixed, int *edgearrint, int *vbase, int *neighb, int *distnode, int *solnode, STP_Bool *visited, int *nelims, int minelims)
static SCIP_RETCODE	execPc_SD (SCIP *scip, GRAPH *g, PATH *vnoi, int *heap, int *state, int *vbase, int *nodesid, int *nodesorg, int *nelims, int redbound, SCIP_Bool verbose, SCIP_Bool *rerun)
static SCIP_RETCODE	execPc_BDk (SCIP *scip, GRAPH *g, PATH *pathtail, PATH *pathhead, int *heap, int *statetail, int *statehead, int *memlbltail, int *memlblhead, int *nelims, int limit, SCIP_Real *offset, int redbound, SCIP_Bool verbose, SCIP_Bool *rerun)
static SCIP_RETCODE	execPc_NVSL (SCIP *scip, SCIP_Bool usestrongreds, GRAPH *g, PATH *vnoi, SCIP_Real *nodearrreal, SCIP_Real *fixed, int *edgearrint, int *vbase, int *neighb, int *distnode, int *solnode, STP_Bool *visited, int *nelims, int redbound, SCIP_Bool verbose, SCIP_Bool *rerun)
static SCIP_RETCODE	execPc_BND (SCIP *scip, GRAPH *graph, PATH *vnoi, SCIP_Real *radius, SCIP_Real *offset, int *heap, int *state, int *vbase, int *nelims, int redbound, SCIP_Bool verbose, SCIP_Bool *rerun)
static SCIP_Real *	redbaseGetOffsetPointer (REDBASE *redbase)
static int *	redbaseGetSolnode (REDSOLLOCAL *redsollocal, REDBASE *redbase)
static SCIP_RETCODE	redLoopInnerStp (SCIP *scip, SCIP_RANDNUMGEN *randnumgen, GRAPH *g, REDSOLLOCAL *redsollocal, REDBASE *redbase, SCIP_Bool *wasDecomposed)
static SCIP_RETCODE	redLoopInnerMw (SCIP *scip, GRAPH *g, REDSOLLOCAL *redsollocal, PATH *vnoi, SCIP_Real *nodearrreal, int *state, int *vbase, int *nodearrint, STP_Bool *nodearrchar, SCIP_Real *fixed, STP_Bool dualascent, STP_Bool bred, int redbound, SCIP_Bool userec, SCIP_Real prizesum)
static SCIP_RETCODE	redLoopInnerPc (SCIP *scip, GRAPH *g, REDSOLLOCAL *redsollocal, DHEAP *dheap, PATH *vnoi, PATH *path, SCIP_Real *nodearrreal, int *heap, int *state, int *vbase, int *nodearrint, int *edgearrint, int *nodearrint2, STP_Bool *nodearrchar, SCIP_Real *fixed, SCIP_RANDNUMGEN *randnumgen, SCIP_Real prizesum, SCIP_Bool dualascent, SCIP_Bool bred, int reductbound, SCIP_Bool userec, SCIP_Bool nodereplacing, SCIP_Bool usestrongreds, SCIP_Bool beFast, int *ninnerelims)
int	reduce_getMinNreductions (const GRAPH *g, int lowerbound)
SCIP_RETCODE	reduce_baseInit (SCIP *scip, const GRAPH *g, REDBASE **redbase)
void	reduce_baseFree (SCIP *scip, REDBASE **redbase)
SCIP_RETCODE	reduce_stp (SCIP *scip, GRAPH *g, REDSOL *redsol, int minelims, SCIP_Bool dualascent, SCIP_Bool nodereplacing, SCIP_Bool userec, SCIP_Bool usestrongreds)
SCIP_RETCODE	reduce_pc (SCIP *scip, REDSOL *redsol, GRAPH *g, int minelims, SCIP_Bool advanced, SCIP_Bool userec, SCIP_Bool nodereplacing, SCIP_Bool usestrongreds)
SCIP_RETCODE	reduce_mw (SCIP *scip, REDSOL *redsol, GRAPH *g, int minelims, SCIP_Bool advanced, SCIP_Bool userec, SCIP_Bool usestrongreds)
SCIP_RETCODE	reduce_hc (SCIP *scip, GRAPH *g, SCIP_Real *fixed, int minelims)
SCIP_RETCODE	reduce_sap (SCIP *scip, GRAPH *g, SCIP_Bool dualascent, SCIP_Real *fixed, int minelims)
SCIP_RETCODE	reduce_nw (SCIP *scip, GRAPH *g, SCIP_Real *fixed, int minelims)
SCIP_RETCODE	reduce_dc (SCIP *scip, GRAPH *g, SCIP_Real *fixed, int minelims)
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)
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)
SCIP_RETCODE	reduce_redLoopStp (SCIP *scip, GRAPH *g, REDBASE *redbase)
SCIP_RETCODE	reduce_exec (SCIP *scip, GRAPH *graph, REDSOL *redsol, int reductionlevel, int minelims, SCIP_Bool userec)

Macro Definition Documentation

REDUCE_C

#define REDUCE_C

Definition at line 28 of file reduce_base.c.

STP_RED_EXTENSIVE

#define STP_RED_EXTENSIVE   FALSE

just for testing

Definition at line 29 of file reduce_base.c.

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

STP_REDBOUND_SDSP

#define STP_REDBOUND_SDSP   200

visited edges bound for SDSP test

Definition at line 30 of file reduce_base.c.

Referenced by getWorkLimitsPc(), and redLoopInnerStp().

STP_REDBOUND_SDSP2

#define STP_REDBOUND_SDSP2   800

visited edges bound for SDSP test

Definition at line 31 of file reduce_base.c.

Referenced by getWorkLimitsPc(), and redLoopInnerStp().

STP_REDBOUND_PCBDK

#define STP_REDBOUND_PCBDK   80

visited edges bound for PC BDK test

Definition at line 32 of file reduce_base.c.

Referenced by getWorkLimitsPc().

STP_REDBOUND_PCBDK2

#define STP_REDBOUND_PCBDK2   400

visited edges bound for PC BDK test

Definition at line 33 of file reduce_base.c.

Referenced by getWorkLimitsPc().

STP_REDBOUND_BDK

#define STP_REDBOUND_BDK   400

visited edges bound for BDK test

Definition at line 35 of file reduce_base.c.

Referenced by getWorkLimitsStp().

STP_REDBOUND_BDK2

#define STP_REDBOUND_BDK2   600

visited edges bound for BDK test

Definition at line 36 of file reduce_base.c.

Referenced by getWorkLimitsStp().

STP_REDBOUND_SDSTAR

#define STP_REDBOUND_SDSTAR   400

visited edges bound for SD Star test

Definition at line 37 of file reduce_base.c.

Referenced by getWorkLimitsStp().

STP_REDBOUND_SDSTAR2

#define STP_REDBOUND_SDSTAR2   800

visited edges bound for SD Star test

Definition at line 38 of file reduce_base.c.

Referenced by getWorkLimitsStp().

STP_RED_MWTERMBOUND

#define STP_RED_MWTERMBOUND   400

Definition at line 39 of file reduce_base.c.

Referenced by reduce_redLoopMw().

STP_RED_EXPENSIVEFACTOR

#define STP_RED_EXPENSIVEFACTOR   2

Definition at line 40 of file reduce_base.c.

Referenced by redLoopInnerStp(), and reduce_redLoopStp().

STP_RED_GLBFACTOR

#define STP_RED_GLBFACTOR   3

Definition at line 41 of file reduce_base.c.

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

STP_RED_EDGELIMIT

#define STP_RED_EDGELIMIT   100000

Definition at line 42 of file reduce_base.c.

STP_RED_EDGELIMIT_HUGE

#define STP_RED_EDGELIMIT_HUGE   1000000

Definition at line 43 of file reduce_base.c.

Referenced by redLoopInnerPc().

STP_RED_MAXNINNROUNDS

#define STP_RED_MAXNINNROUNDS   15

Definition at line 44 of file reduce_base.c.

Referenced by redLoopInnerMw(), and redLoopInnerPc().

STP_RED_MAXNOUTROUNDS_PC

#define STP_RED_MAXNOUTROUNDS_PC   4

Definition at line 45 of file reduce_base.c.

Referenced by reduce_redLoopPc().

STP_RED_MAXNOUTROUNDS_MW

#define STP_RED_MAXNOUTROUNDS_MW   4

Definition at line 46 of file reduce_base.c.

STP_BND_THRESHOLD

#define STP_BND_THRESHOLD   0.03

Definition at line 48 of file reduce_base.c.

Referenced by reduce_pc(), and reduce_stp().

USE_FULLSEPA

#define USE_FULLSEPA

Definition at line 49 of file reduce_base.c.

Enumeration Type Documentation

PC_REDTYPE

enum PC_REDTYPE

Enumerator
pc_sdc
pc_sdstar
pc_sdstar2
pc_sdw1
pc_sdw2
pc_bd3

Definition at line 69 of file reduce_base.c.

STP_REDTYPE

enum STP_REDTYPE

Enumerator
stp_bdk
stp_sdstar
stp_sdstarbot

Definition at line 70 of file reduce_base.c.

Function Documentation

getWorkLimitsStp()

static int getWorkLimitsStp ( const GRAPH *  g, int  roundnumber, SCIP_Bool  fullreduce, enum STP_REDTYPE  redtype  )

static

returns limit parameter for SPG method

Definition at line 75 of file reduce_base.c.

References stp_bdk, STP_REDBOUND_BDK, STP_REDBOUND_BDK2, STP_REDBOUND_SDSTAR, STP_REDBOUND_SDSTAR2, stp_sdstar, and stp_sdstarbot.

Referenced by redLoopInnerStp().

getWorkLimitsPc()

static int getWorkLimitsPc ( const GRAPH *  g, int  roundnumber, SCIP_Bool  beFast, enum PC_REDTYPE  redtype  )

static

returns limit parameters for PCSTP method

Definition at line 118 of file reduce_base.c.

References GRAPH::edges, MAX, pc_bd3, pc_sdc, pc_sdstar, pc_sdstar2, pc_sdw1, pc_sdw2, STP_REDBOUND_PCBDK, STP_REDBOUND_PCBDK2, STP_REDBOUND_SDSP, and STP_REDBOUND_SDSP2.

Referenced by redLoopInnerPc().

reduceStatsPrint()

static void reduceStatsPrint ( SCIP_Bool  print, const char *  method, int  nelims  )

static

print reduction information

Definition at line 178 of file reduce_base.c.

Referenced by redLoopInnerStp(), and reduce_redLoopStp().

execNvSl()

static SCIP_RETCODE execNvSl ( SCIP *  scip, const int *  edgestate, GRAPH *  g, PATH *  vnoi, SCIP_Real *  nodearrreal, SCIP_Real *  fixed, int *  edgearrint, int *  vbase, int *  neighb, int *  distnode, int *  solnode, STP_Bool *  visited, int *  nelims, int  minelims  )

static

iterate NV and SL test while at least minelims many contractions are being performed

Parameters

scip	SCIP data structure
edgestate	for propagation or NULL
g	graph
vnoi	Voronoi
nodearrreal	array
fixed	offset
edgearrint	array
vbase	array
neighb	array
distnode	array
solnode	array
visited	array
nelims	number of eliminations
minelims	minimum number of eliminations

Definition at line 196 of file reduce_base.c.

References graph_valid(), NULL, reduce_nvAdv(), reduce_simple(), reduce_simple_pc(), reduce_sl(), SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, STP_PCSPG, STP_RPCSPG, and GRAPH::stp_type.

Referenced by execPc_NVSL(), and redLoopInnerStp().

execPc_SD()

static SCIP_RETCODE execPc_SD ( SCIP *  scip, GRAPH *  g, PATH *  vnoi, int *  heap, int *  state, int *  vbase, int *  nodesid, int *  nodesorg, int *  nelims, int  redbound, SCIP_Bool  verbose, SCIP_Bool *  rerun  )

static

Parameters

scip	SCIP data structure
g	graph data structure
vnoi	Voronoi data structure
heap	heap array
state	array to store state of a node during Voronoi computation
vbase	Voronoi base to each node
nodesid	array
nodesorg	array
nelims	pointer to store number of eliminated edges
redbound	reduction bound
verbose	be verbose?
rerun	use again?

Definition at line 274 of file reduce_base.c.

References FALSE, reduce_sdPc(), SCIP_CALL, and SCIP_OKAY.

Referenced by redLoopInnerPc().

execPc_BDk()

static SCIP_RETCODE execPc_BDk ( SCIP *  scip, GRAPH *  g, PATH *  pathtail, PATH *  pathhead, int *  heap, int *  statetail, int *  statehead, int *  memlbltail, int *  memlblhead, int *  nelims, int  limit, SCIP_Real *  offset, int  redbound, SCIP_Bool  verbose, SCIP_Bool *  rerun  )

static

Parameters

scip	SCIP data structure
g	graph structure
pathtail	array for internal use
pathhead	array for internal use
heap	array for internal use
statetail	array for internal use
statehead	array for internal use
memlbltail	array for internal use
memlblhead	array for internal use
nelims	point to return number of eliminations
limit	limit for edges to consider for each vertex
offset	offset
redbound	reduction bound
verbose	be verbose?
rerun	use again?

Definition at line 307 of file reduce_base.c.

References FALSE, reduce_bd34(), SCIP_CALL, and SCIP_OKAY.

Referenced by redLoopInnerPc().

execPc_NVSL()

static SCIP_RETCODE execPc_NVSL ( SCIP *  scip, SCIP_Bool  usestrongreds, GRAPH *  g, PATH *  vnoi, SCIP_Real *  nodearrreal, SCIP_Real *  fixed, int *  edgearrint, int *  vbase, int *  neighb, int *  distnode, int *  solnode, STP_Bool *  visited, int *  nelims, int  redbound, SCIP_Bool  verbose, SCIP_Bool *  rerun  )

static

Parameters

scip	SCIP data structure
usestrongreds	allow strong reductions?
g	graph
vnoi	Voronoi data structure
nodearrreal	array
fixed	offset
edgearrint	array
vbase	array
neighb	array
distnode	array
solnode	array
visited	array
nelims	number of eliminations
redbound	reduction bound
verbose	be verbose?
rerun	use again?

Definition at line 338 of file reduce_base.c.

References execNvSl(), FALSE, NULL, SCIP_CALL, and SCIP_OKAY.

Referenced by redLoopInnerPc().

execPc_BND()

static SCIP_RETCODE execPc_BND ( SCIP *  scip, GRAPH *  graph, PATH *  vnoi, SCIP_Real *  radius, SCIP_Real *  offset, int *  heap, int *  state, int *  vbase, int *  nelims, int  redbound, SCIP_Bool  verbose, SCIP_Bool *  rerun  )

static

Parameters

scip	SCIP data structure
graph	graph data structure
vnoi	Voronoi data structure
radius	radius 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
nelims	pointer to store number of eliminated edges
redbound	reduction bound
verbose	be verbose?
rerun	use again?

Definition at line 371 of file reduce_base.c.

References FALSE, reduce_bound(), SCIP_CALL, SCIP_OKAY, and SCIP_Real.

Referenced by redLoopInnerPc().

redbaseGetOffsetPointer()

static SCIP_Real* redbaseGetOffsetPointer ( REDBASE *  redbase )

static

returns pointer

Parameters

redbase

base

Definition at line 403 of file reduce_base.c.

References reduction_base::redsol, and reduce_solGetOffsetPointer().

Referenced by redLoopInnerStp(), and reduce_redLoopStp().

redbaseGetSolnode()

static int* redbaseGetSolnode ( REDSOLLOCAL *  redsollocal, REDBASE *  redbase  )

static

returns pointer todo: remove once redsol is properly tested

Parameters

redsollocal	data structure for retaining primal solution
redbase	base

Definition at line 417 of file reduce_base.c.

References reduction_base::redsol, reduce_sollocalGetSolnode(), reduce_sollocalUsesNodesol(), reduce_solUsesNodesol(), and reduction_base::solnode.

Referenced by redLoopInnerStp(), and reduce_redLoopStp().

redLoopInnerStp()

static SCIP_RETCODE redLoopInnerStp ( SCIP *  scip, SCIP_RANDNUMGEN *  randnumgen, GRAPH *  g, REDSOLLOCAL *  redsollocal, REDBASE *  redbase, SCIP_Bool *  wasDecomposed  )

static

inner STP reduction loop

Parameters

scip	SCIP data structure
randnumgen	generator
g	graph data structure
redsollocal	data structure for retaining primal solution
redbase	parameters
wasDecomposed	pointer to mark whether to exit early

Definition at line 441 of file reduce_base.c.

References reduction_base::bidecompparams, reduction_parameters::boundreduce, reduce_costs_reduction_parameters::damode, bidecomposition_reduction_parameters::depth, reduction_parameters::dualascent, reduction_base::edgearrint, execNvSl(), extred_none, FALSE, reduction_parameters::fullreduce, getWorkLimitsStp(), reduction_base::heap, bidecomposition_reduction_parameters::maxdepth, bidecomposition_reduction_parameters::newLevelStarted, reduction_base::nodearrchar, reduction_base::nodearrint, reduction_base::nodearrint2, reduction_base::nodearrreal, reduction_parameters::nodereplacing, NULL, redbaseGetOffsetPointer(), redbaseGetSolnode(), reduction_base::redparameters, reduce_bdk(), reduce_bidecomposition(), reduce_bound(), reduce_da(), reduce_impliedProfitBased(), reduce_pathreplace(), reduce_sd(), reduce_sdsp(), reduce_sdStarBiased(), reduce_simple(), reduce_sollocalGetUpperBound(), reduce_sollocalSetOffset(), reduce_unconnected(), reduceStatsPrint(), reduction_parameters::reductbound, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPgetRealParam(), SCIPgetTotalTime(), SCIPisStopped(), reduction_base::state, stp_bdk, STP_DAMODE_FAST, STP_DAMODE_MEDIUM, STP_RED_EXPENSIVEFACTOR, STP_RED_EXTENSIVE, STP_RED_GLBFACTOR, STP_REDBOUND_SDSP, STP_REDBOUND_SDSP2, stp_sdstar, stp_sdstarbot, TRUE, reduction_parameters::userec, reduction_parameters::usestrongreds, reduction_base::vbase, and reduction_base::vnoi.

Referenced by reduce_redLoopStp().

redLoopInnerMw()

static SCIP_RETCODE redLoopInnerMw ( SCIP *  scip, GRAPH *  g, REDSOLLOCAL *  redsollocal, PATH *  vnoi, SCIP_Real *  nodearrreal, int *  state, int *  vbase, int *  nodearrint, STP_Bool *  nodearrchar, SCIP_Real *  fixed, STP_Bool  dualascent, STP_Bool  bred, int  redbound, SCIP_Bool  userec, SCIP_Real  prizesum  )

static

inner MWCS loop todo use REDBASE here instead of all the parameters and also allocate the memory locally!

Parameters

scip	SCIP data structure
g	graph data structure
redsollocal	data structure for retaining primal solution
vnoi	Voronoi data structure
nodearrreal	nodes-sized array
state	shortest path array
vbase	voronoi base array
nodearrint	nodes-sized array
nodearrchar	nodes-sized array
fixed	pointer to store the offset value
dualascent	do dual-ascent reduction?
bred	do bound-based reduction?
redbound	minimal number of edges to be eliminated in order to reiterate reductions
userec	use recombination heuristic?
prizesum	prize sum

Definition at line 691 of file reduce_base.c.

References reduce_costs_reduction_parameters::damode, extred_none, FALSE, graph_get_nVET(), graph_pc_isRootedPcMw(), NULL, reduce_ans(), reduce_ansAdv(), reduce_ansAdv2(), reduce_boundMw(), reduce_chain2(), reduce_da(), reduce_daPcMw(), reduce_nnp(), reduce_npv(), reduce_simple_mw(), reduce_sollocalGetSolnode(), reduce_sollocalRebuildTry(), reduce_sollocalSetOffset(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcreateRandom(), SCIPdebugMessage, SCIPfreeRandom(), SCIPgetRealParam(), SCIPgetTotalTime(), SCIPisStopped(), STP_DAMODE_FAST, STP_RED_EXTENSIVE, STP_RED_MAXNINNROUNDS, and TRUE.

Referenced by reduce_redLoopMw().

redLoopInnerPc()

static SCIP_RETCODE redLoopInnerPc ( SCIP *  scip, GRAPH *  g, REDSOLLOCAL *  redsollocal, DHEAP *  dheap, PATH *  vnoi, PATH *  path, SCIP_Real *  nodearrreal, int *  heap, int *  state, int *  vbase, int *  nodearrint, int *  edgearrint, int *  nodearrint2, STP_Bool *  nodearrchar, SCIP_Real *  fixed, SCIP_RANDNUMGEN *  randnumgen, SCIP_Real  prizesum, SCIP_Bool  dualascent, SCIP_Bool  bred, int  reductbound, SCIP_Bool  userec, SCIP_Bool  nodereplacing, SCIP_Bool  usestrongreds, SCIP_Bool  beFast, int *  ninnerelims  )

static

inner (R)PC loop todo use REDBASE here instead of all the parameters and also allocate the memory locally!

Parameters

scip	SCIP data structure
g	graph data structure
redsollocal	solution store
dheap	heap data structure
vnoi	Voronoi data structure
path	path data structure
nodearrreal	nodes-sized array
heap	shortest path array
state	voronoi base array
vbase	nodes-sized array
nodearrint	node-sized array
edgearrint	edge-sized array
nodearrint2	nodes-sized array
nodearrchar	nodes-sized array
fixed	offset
randnumgen	random number generator
prizesum	prize sum
dualascent	do dual-ascent reduction?
bred	do bound-based reduction?
reductbound	minimal number of edges to be eliminated in order to reiterate reductions
userec	use recombination heuristic?
nodereplacing	should node replacement (by edges) be performed?
usestrongreds	allow strong reductions?
beFast	fast mode?
ninnerelims	number of eliminations

Definition at line 872 of file reduce_base.c.

References reduce_costs_reduction_parameters::damode, GRAPH::edges, execPc_BDk(), execPc_BND(), execPc_NVSL(), execPc_SD(), extred_none, FALSE, getWorkLimitsPc(), graph_pc_isRootedPcMw(), NULL, pc_bd3, pc_sdstar, pc_sdstar2, pc_sdw1, pc_sdw2, reduce_costs_reduction_parameters::pcmw_fastDa, reduce_costs_reduction_parameters::pcmw_solbasedda, reduce_da(), reduce_dapaths(), reduce_daPcMw(), reduce_pathreplace(), reduce_sdStarBiased(), reduce_sdStarPc2(), reduce_sdWalkExt(), reduce_sdWalkTriangle(), reduce_simple_pc(), reduce_sollocalGetSolnode(), reduce_sollocalRebuildTry(), reduce_sollocalSetOffset(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetRealParam(), SCIPgetTotalTime(), SCIPisStopped(), STP_DAMODE_FAST, STP_RED_EDGELIMIT_HUGE, STP_RED_EXTENSIVE, STP_RED_GLBFACTOR, STP_RED_MAXNINNROUNDS, STP_RPCSPG, GRAPH::stp_type, and TRUE.

Referenced by reduce_redLoopPc().

reduce_getMinNreductions()

int reduce_getMinNreductions	(	const GRAPH *	g,
		int	lowerbound
	)

gets reduction bound

Parameters

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

Definition at line 1087 of file reduce_base.c.

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

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

reduce_baseInit()

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

initializes

Parameters

scip	SCIP data structure
g	graph data structure
redbase	base

Definition at line 1120 of file reduce_base.c.

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

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

reduce_baseFree()

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

frees

Parameters

scip	SCIP data structure
redbase	base

Definition at line 1155 of file reduce_base.c.

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

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

reduce_stp()

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

basic reduction package for the STP

Parameters

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

Definition at line 1181 of file reduce_base.c.

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

Referenced by fixVarsRedbased(), and reduce_exec().

reduce_pc()

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

basic reduction package for the (R)PCSTP

Parameters

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

Definition at line 1260 of file reduce_base.c.

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

Referenced by fixVarsRedbased(), and reduce_exec().

reduce_mw()

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

reduction package for the MWCSP

Parameters

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

Definition at line 1344 of file reduce_base.c.

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

Referenced by fixVarsRedbased(), and reduce_exec().

reduce_hc()

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

basic reduction package for the HCDSTP

Parameters

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

Definition at line 1403 of file reduce_base.c.

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

Referenced by reduce_exec().

reduce_sap()

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

basic reduction package for the SAP

Parameters

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

Definition at line 1557 of file reduce_base.c.

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

Referenced by reduce_exec().

reduce_nw()

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

reduce node-weighted Steiner tree problem

Parameters

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

Definition at line 1669 of file reduce_base.c.

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

Referenced by reduce_exec().

reduce_dc()

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

reduce degree constrained Steiner tree problem

Parameters

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

Definition at line 1729 of file reduce_base.c.

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

Referenced by reduce_exec().

reduce_redLoopMw()

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

MWCS loop

Parameters

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

Definition at line 1771 of file reduce_base.c.

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

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

reduce_redLoopPc()

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

(R)PC loop

Parameters

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

Definition at line 1896 of file reduce_base.c.

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

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

reduce_redLoopStp()

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

STP loop

Parameters

scip	SCIP data structure
g	graph data structure
redbase	parameters

Definition at line 2074 of file reduce_base.c.

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

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

reduce_exec()

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

reduces the graph

Parameters

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

Definition at line 2192 of file reduce_base.c.

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

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