Detailed Description

Reduction tests for Steiner problems.

Author: Gerald Gamrath; Thorsten Koch; Stephen Maher; 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 grph.h.

Definition in file reduce.c.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "grph.h"
#include "heur_tm.h"
#include "misc_stp.h"
#include "scip/scip.h"
#include "probdata_stp.h"
#include "prop_stp.h"

Go to the source code of this file.

Macros
#define	REDUCE_C

#define	STP_RED_SDSPBOUND 200

#define	STP_RED_SDSPBOUND2 600

#define	STP_RED_BD3BOUND 500

#define	STP_RED_EXTENSIVE FALSE

#define	STP_RED_MWTERMBOUND 400

#define	STP_RED_MAXNROUNDS 15

#define	STP_RED_EXFACTOR 2

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

static SCIP_RETCODE	nvreduce_sl (SCIP scip, GRAPH g, PATH vnoi, SCIP_Real nodearrreal, SCIP_Real fixed, int edgearrint, int heap, int state, int vbase, int neighb, int distnode, int solnode, STP_Bool visited, int nelims, int minelims)

SCIP_RETCODE	level0 (SCIP scip, GRAPH g)

SCIP_RETCODE	level0save (SCIP scip, GRAPH g)

SCIP_RETCODE	reduceStp (SCIP scip, GRAPH graph, SCIP_Real fixed, int minelims, SCIP_Bool dualascent, SCIP_Bool nodereplacing, SCIP_Bool userec)

static SCIP_RETCODE	reducePc (SCIP scip, GRAPH graph, SCIP_Real fixed, int minelims, STP_Bool dualascent, SCIP_Bool userec)

static SCIP_RETCODE	reduceMw (SCIP scip, GRAPH graph, SCIP_Real fixed, int minelims, STP_Bool advanced, SCIP_Bool userec)

static SCIP_RETCODE	reduceHc (SCIP scip, GRAPH graph, SCIP_Real fixed, int minelims)

static SCIP_RETCODE	reduceSap (SCIP scip, GRAPH graph, SCIP_Real fixed, int minelims)

static SCIP_RETCODE	reduceNw (SCIP scip, GRAPH graph, SCIP_Real fixed, int minelims)

SCIP_RETCODE	redLoopMw (SCIP scip, GRAPH g, PATH vnoi, PATH path, GNODE *gnodearr, SCIP_Real nodearrreal, SCIP_Real edgearrreal, SCIP_Real edgearrreal2, int state, int vbase, int nodearrint, int edgearrint, int nodearrint2, int nodearrint3, int solnode, STP_Bool nodearrchar, SCIP_Real *fixed, STP_Bool advanced, STP_Bool bred, STP_Bool tryrmw, int redbound, SCIP_Bool userec)

SCIP_RETCODE	redLoopPc (SCIP scip, GRAPH g, PATH vnoi, PATH path, GNODE *gnodearr, SCIP_Real nodearrreal, SCIP_Real exedgearrreal, SCIP_Real exedgearrreal2, int heap, int state, int vbase, int nodearrint, int edgearrint, int nodearrint2, int solnode, STP_Bool nodearrchar, SCIP_Real *fixed, SCIP_Bool dualascent, SCIP_Bool bred, int reductbound, SCIP_Bool userec)

SCIP_RETCODE	redLoopStp (SCIP scip, GRAPH g, PATH vnoi, PATH path, GNODE *gnodearr, SCIP_Real nodearrreal, SCIP_Real edgearrreal, SCIP_Real edgearrreal2, int heap, int state, int vbase, int nodearrint, int edgearrint, int nodearrint2, int solnode, STP_Bool nodearrchar, SCIP_Real *fixed, SCIP_Real upperbound, SCIP_Bool dualascent, SCIP_Bool boundreduce, SCIP_Bool nodereplacing, int reductbound, SCIP_Bool userec, SCIP_Bool fullreduce)

SCIP_RETCODE	reduce (SCIP scip, GRAPH graph, SCIP_Real offset, int level, int minelims, SCIP_Bool userec)

Macro Definition Documentation

◆ REDUCE_C

#define REDUCE_C

Definition at line 31 of file reduce.c.

◆ STP_RED_SDSPBOUND

#define STP_RED_SDSPBOUND 200

visited edges bound for SDSP test

Definition at line 32 of file reduce.c.

Referenced by redLoopPc(), and redLoopStp().

◆ STP_RED_SDSPBOUND2

#define STP_RED_SDSPBOUND2 600

visited edges bound for SDSP test

Definition at line 33 of file reduce.c.

Referenced by redLoopPc(), and redLoopStp().

◆ STP_RED_BD3BOUND

#define STP_RED_BD3BOUND 500

visited edges bound for BD3 test

Definition at line 34 of file reduce.c.

Referenced by redLoopPc(), and redLoopStp().

◆ STP_RED_EXTENSIVE

#define STP_RED_EXTENSIVE FALSE

Definition at line 35 of file reduce.c.

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

◆ STP_RED_MWTERMBOUND

#define STP_RED_MWTERMBOUND 400

Definition at line 36 of file reduce.c.

Referenced by redLoopMw().

◆ STP_RED_MAXNROUNDS

#define STP_RED_MAXNROUNDS 15

Definition at line 37 of file reduce.c.

Referenced by redLoopMw(), and redLoopPc().

◆ STP_RED_EXFACTOR

#define STP_RED_EXFACTOR 2

Definition at line 38 of file reduce.c.

Referenced by redLoopStp().

Function Documentation

◆ reduceStatsPrint()

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

static

print reduction information

Definition at line 55 of file reduce.c.

Referenced by redLoopStp().

◆ nvreduce_sl()

static SCIP_RETCODE nvreduce_sl	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	vnoi,
		SCIP_Real *	nodearrreal,
		SCIP_Real *	fixed,
		int *	edgearrint,
		int *	heap,
		int *	state,
		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

Definition at line 72 of file reduce.c.

References FALSE, 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 redLoopPc(), and redLoopStp().

◆ level0()

SCIP_RETCODE level0	(	SCIP *	scip,
		GRAPH *	g
	)

Parameters

scip	SCIP data structure
g	graph data structure

Definition at line 153 of file reduce.c.

References EAT_LAST, FALSE, GRAPH::grad, graph_edge_del(), graph_trail_arr(), GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, SCIP_CALL, SCIP_OKAY, GRAPH::source, GRAPH::term, and TRUE.

Referenced by redbasedVarfixing(), redLoopMw(), redLoopStp(), reduce(), reduce_da(), reduce_ledge(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurPruneRun(), SCIPStpHeurSlackPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().

◆ level0save()

SCIP_RETCODE level0save	(	SCIP *	scip,
		GRAPH *	g
	)

Parameters

scip	SCIP data structure
g	graph data structure

Definition at line 185 of file reduce.c.

References BMScopyMemoryArray, EAT_LAST, FALSE, GRAPH::grad, graph_edge_del(), graph_trail_arr(), GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, GRAPH::source, GRAPH::term, and TRUE.

Referenced by reduce_simple_mw(), and reduce_simple_pc().

◆ reduceStp()

SCIP_RETCODE reduceStp	(	SCIP *	scip,
		GRAPH **	graph,
		SCIP_Real *	fixed,
		int	minelims,
		SCIP_Bool	dualascent,
		SCIP_Bool	nodereplacing,
		SCIP_Bool	userec
	)

basic reduction package for the STP

Parameters

scip	SCIP data structure
graph	graph data structure
fixed	pointer to store the offset value
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?

Definition at line 223 of file reduce.c.

References GRAPH::edges, FALSE, GRAPH::knots, MAX, nnodes, nterms, NULL, redLoopStp(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemory, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBlockMemory, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPisLE(), GRAPH::terms, and TRUE.

Referenced by redbasedVarfixing(), and reduce().

◆ reducePc()

static SCIP_RETCODE reducePc	(	SCIP *	scip,
		GRAPH **	graph,
		SCIP_Real *	fixed,
		int	minelims,
		STP_Bool	dualascent,
		SCIP_Bool	userec
	)

static

basic reduction package for the (R)PCSTP

Parameters

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

Definition at line 338 of file reduce.c.

References GRAPH::edges, FALSE, GRAPH::knots, MAX, nnodes, nterms, NULL, redLoopPc(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemory, SCIPallocBufferArray, SCIPfreeBlockMemory, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetRealParam(), SCIPisLE(), STP_RPCSPG, GRAPH::stp_type, GRAPH::terms, and TRUE.

Referenced by reduce().

◆ reduceMw()

static SCIP_RETCODE reduceMw	(	SCIP *	scip,
		GRAPH **	graph,
		SCIP_Real *	fixed,
		int	minelims,
		STP_Bool	advanced,
		SCIP_Bool	userec
	)

static

reduction package for the MWCSP

Parameters

scip	SCIP data structure
graph	graph data structure
fixed	pointer to store the offset value
minelims	minimal number of edges to be eliminated in order to reiterate reductions
advanced	perform advanced reductions?
userec	use recombination heuristic?

Definition at line 459 of file reduce.c.

References GRAPH::edges, FALSE, GRAPH::knots, MAX, nnodes, nterms, NULL, redLoopMw(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemory, SCIPallocBufferArray, SCIPfreeBlockMemory, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPisLE(), GRAPH::terms, and TRUE.

Referenced by reduce().

◆ reduceHc()

static SCIP_RETCODE reduceHc	(	SCIP *	scip,
		GRAPH **	graph,
		SCIP_Real *	fixed,
		int	minelims
	)

static

basic reduction package for the HCDSTP

Parameters

scip	SCIP data structure
graph	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 571 of file reduce.c.

References GRAPH::edges, FALSE, GRAPH::knots, MAX, nnodes, NULL, reduce_bound(), reduce_boundHop(), reduce_boundHopR(), reduce_boundHopRc(), reduce_simple_hc(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetRealParam(), SCIPgetTotalTime(), SCIPisStopped(), and TRUE.

Referenced by reduce().

◆ reduceSap()

static SCIP_RETCODE reduceSap	(	SCIP *	scip,
		GRAPH **	graph,
		SCIP_Real *	fixed,
		int	minelims
	)

static

basic reduction package for the SAP

Parameters

scip	SCIP data structure
graph	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 691 of file reduce.c.

References GRAPH::cost, GRAPH::edges, FALSE, FARAWAY, GRAPH::knots, MAX, nnodes, nterms, reduce_da(), reduce_rpt(), reduce_sdspSap(), reduce_simple_sap(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemory, SCIPallocBufferArray, SCIPcreateRandom(), SCIPfreeBlockMemory, SCIPfreeBufferArray, SCIPfreeRandom(), SCIPgetRealParam(), SCIPgetTotalTime(), SCIPisEQ(), SCIPisStopped(), GRAPH::terms, and TRUE.

Referenced by reduce().

◆ reduceNw()

static SCIP_RETCODE reduceNw	(	SCIP *	scip,
		GRAPH **	graph,
		SCIP_Real *	fixed,
		int	minelims
	)

static

Parameters

scip	SCIP data structure
graph	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 825 of file reduce.c.

References GRAPH::edges, FALSE, FARAWAY, GRAPH::knots, MAX, nnodes, nterms, reduce_da(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemory, SCIPallocBufferArray, SCIPcreateRandom(), SCIPfreeBlockMemory, SCIPfreeBufferArray, SCIPfreeRandom(), SCIPgetRealParam(), SCIPgetTotalTime(), SCIPisStopped(), GRAPH::terms, and TRUE.

Referenced by reduce().

◆ redLoopMw()

SCIP_RETCODE redLoopMw	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	vnoi,
		PATH *	path,
		GNODE **	gnodearr,
		SCIP_Real *	nodearrreal,
		SCIP_Real *	edgearrreal,
		SCIP_Real *	edgearrreal2,
		int *	state,
		int *	vbase,
		int *	nodearrint,
		int *	edgearrint,
		int *	nodearrint2,
		int *	nodearrint3,
		int *	solnode,
		STP_Bool *	nodearrchar,
		SCIP_Real *	fixed,
		STP_Bool	advanced,
		STP_Bool	bred,
		STP_Bool	tryrmw,
		int	redbound,
		SCIP_Bool	userec
	)

MWCS loop

Parameters

scip	SCIP data structure
g	graph data structure
vnoi	Voronoi data structure
path	path data structure
gnodearr	nodes-sized array
nodearrreal	nodes-sized array
edgearrreal	edges-sized array
edgearrreal2	edges-sized array
state	shortest path array
vbase	voronoi base array
nodearrint	nodes-sized array
edgearrint	edges-sized array
nodearrint2	nodes-sized array
nodearrint3	nodes-sized array
solnode	array to indicate whether a node is part of the current solution (==CONNECT)
nodearrchar	nodes-sized array
fixed	pointer to store the offset value
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?

Definition at line 921 of file reduce.c.

References FALSE, graph_pc_2org(), graph_pc_2trans(), graph_pc_getPosPrizeSum(), graph_pc_mw2rmw(), graph_pc_term2edgeConsistent(), level0(), NULL, reduce_ans(), reduce_ansAdv(), reduce_ansAdv2(), reduce_boundMw(), reduce_chain2(), reduce_daPcMw(), reduce_nnp(), reduce_npv(), reduce_simple_mw(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcreateRandom(), SCIPdebugMessage, SCIPfreeRandom(), SCIPgetRealParam(), SCIPgetTotalTime(), SCIPisStopped(), STP_RED_EXTENSIVE, STP_RED_MAXNROUNDS, STP_RED_MWTERMBOUND, GRAPH::terms, and TRUE.

Referenced by reduceMw(), SCIPStpHeurPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().

◆ redLoopPc()

SCIP_RETCODE redLoopPc	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	vnoi,
		PATH *	path,
		GNODE **	gnodearr,
		SCIP_Real *	nodearrreal,
		SCIP_Real *	exedgearrreal,
		SCIP_Real *	exedgearrreal2,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	nodearrint,
		int *	edgearrint,
		int *	nodearrint2,
		int *	solnode,
		STP_Bool *	nodearrchar,
		SCIP_Real *	fixed,
		SCIP_Bool	dualascent,
		SCIP_Bool	bred,
		int	reductbound,
		SCIP_Bool	userec
	)

(R)PC loop

Parameters

scip	SCIP data structure
g	graph data structure
vnoi	Voronoi data structure
path	path data structure
gnodearr	nodes-sized array
nodearrreal	nodes-sized array
exedgearrreal	edges-sized array
exedgearrreal2	edges-sized array
heap	shortest path array
state	voronoi base array
vbase	nodes-sized array
nodearrint	edges-sized array
edgearrint	nodes-sized array
nodearrint2	nodes-sized array
solnode	solution nodes array (or NULL)
nodearrchar	nodes-sized array
fixed	pointer to store the offset value
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?

Definition at line 1158 of file reduce.c.

References FALSE, FARAWAY, GRAPH::grad, graph_pc_2org(), graph_pc_2trans(), graph_pc_getPosPrizeSum(), graph_pc_presolExit(), graph_pc_presolInit(), graph_pc_term2edgeConsistent(), NULL, nvreduce_sl(), GRAPH::prize, reduce_bd34(), reduce_bound(), reduce_da(), reduce_daPcMw(), reduce_sdPc(), reduce_sdsp(), reduce_simple_pc(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcreateRandom(), SCIPdebugMessage, SCIPfreeRandom(), SCIPgetRealParam(), SCIPgetTotalTime(), SCIPisStopped(), GRAPH::source, STP_RED_BD3BOUND, STP_RED_EXTENSIVE, STP_RED_MAXNROUNDS, STP_RED_SDSPBOUND, STP_RED_SDSPBOUND2, STP_RPCSPG, GRAPH::stp_type, GRAPH::terms, and TRUE.

Referenced by reducePc(), and SCIPStpHeurPruneRun().

◆ redLoopStp()

SCIP_RETCODE redLoopStp	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	vnoi,
		PATH *	path,
		GNODE **	gnodearr,
		SCIP_Real *	nodearrreal,
		SCIP_Real *	edgearrreal,
		SCIP_Real *	edgearrreal2,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	nodearrint,
		int *	edgearrint,
		int *	nodearrint2,
		int *	solnode,
		STP_Bool *	nodearrchar,
		SCIP_Real *	fixed,
		SCIP_Real	upperbound,
		SCIP_Bool	dualascent,
		SCIP_Bool	boundreduce,
		SCIP_Bool	nodereplacing,
		int	reductbound,
		SCIP_Bool	userec,
		SCIP_Bool	fullreduce
	)

STP loop

Parameters

scip	SCIP data structure
g	graph data structure
vnoi	Voronoi data structure
path	path data structure
gnodearr	nodes-sized array
nodearrreal	nodes-sized array
edgearrreal	edges-sized array
edgearrreal2	edges-sized array
heap	heap array
state	shortest path array
vbase	Voronoi base array
nodearrint	edges-sized array
edgearrint	nodes-sized array
nodearrint2	nodes-sized array
solnode	solution nodes array (or NULL)
nodearrchar	nodes-sized array
fixed	pointer to store the offset value
upperbound	upper bound
dualascent	do dual-ascent reduction?
boundreduce	do bound-based reduction?
nodereplacing	should node replacement (by edges) be performed?
reductbound	minimal number of edges to be eliminated in order to reiterate reductions
userec	use recombination heuristic?
fullreduce	use full reductions? (including extended techniques)

Definition at line 1409 of file reduce.c.

References FALSE, graph_valid(), level0(), NULL, nvreduce_sl(), reduce_bd34(), reduce_bound(), reduce_contractZeroEdges(), reduce_da(), reduce_deleteConflictEdges(), reduce_ledge(), reduce_sd(), reduce_sdsp(), reduce_simple(), reduceStatsPrint(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcreateRandom(), SCIPdebugMessage, SCIPfreeRandom(), SCIPgetRealParam(), SCIPgetTotalTime(), SCIPisStopped(), STP_RED_BD3BOUND, STP_RED_EXFACTOR, STP_RED_EXTENSIVE, STP_RED_SDSPBOUND, STP_RED_SDSPBOUND2, and TRUE.

Referenced by reduceStp(), SCIPStpHeurPruneRun(), and SCIPStpHeurSlackPruneRun().

◆ reduce()

SCIP_RETCODE reduce	(	SCIP *	scip,
		GRAPH **	graph,
		SCIP_Real *	offset,
		int	level,
		int	minelims,
		SCIP_Bool	userec
	)

reduces the graph

Parameters

scip	SCIP data structure
graph	graph structure
offset	pointer to store offset generated by reductions
level	reduction level 0: none, 1: basic, 2: advanced
minelims	minimal amount of reductions to reiterate reduction methods
userec	use recombination heuristic?

Definition at line 1673 of file reduce.c.

References FALSE, graph_init_history(), graph_path_exit(), graph_path_init(), graph_valid(), level0(), NULL, reduceHc(), reduceMw(), reduceNw(), reducePc(), reduceSap(), reduceStp(), SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, STP_DCSTP, STP_DHCSTP, STP_MWCSP, STP_NWSPG, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, STP_SAP, and TRUE.

Referenced by SCIPprobdataCreate(), SCIPStpHeurRecExclude(), and SCIPStpHeurRecRun().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ REDUCE_C

◆ STP_RED_SDSPBOUND

◆ STP_RED_SDSPBOUND2

◆ STP_RED_BD3BOUND

◆ STP_RED_EXTENSIVE

◆ STP_RED_MWTERMBOUND

◆ STP_RED_MAXNROUNDS

◆ STP_RED_EXFACTOR

Function Documentation

◆ reduceStatsPrint()

◆ nvreduce_sl()

◆ level0()

◆ level0save()

◆ reduceStp()

◆ reducePc()

◆ reduceMw()

◆ reduceHc()

◆ reduceSap()

◆ reduceNw()

◆ redLoopMw()

◆ redLoopPc()

◆ redLoopStp()

◆ reduce()