Detailed Description

Altenative based reduction tests for Steiner problems.

Author: Thorsten Koch; Stephen Maher; Daniel Rehfeldt

This file implements alternative-based reduction techniques for several Steiner problems. All tests can be found in "Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem" by Daniel Rehfeldt and Thorsten Koch, or in "Reduction Techniques for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem" by Daniel Rehfeldt et al.

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

Definition in file reduce_alt.c.

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

Go to the source code of this file.

Macros
#define	VERTEX_CONNECT 0

#define	VERTEX_TEMPNEIGHBOR 1

#define	VERTEX_NEIGHBOR 2

#define	VERTEX_OTHER 3

#define	STP_RED_CNSNN 25

#define	STP_RED_ANSMAXCANDS 500

#define	STP_RED_ANSEXMAXCANDS 50

#define	STP_RED_ANSMAXNEIGHBORS 25

#define	STP_BDR_MAXDEGREE 4

#define	STP_BDR_MAXDNEDGES 6

#define	STP_BD_MAXDEGREE 4

#define	STP_BD_MAXDNEDGES 6

Functions
static SCIP_Bool	sddeltable (SCIP scip, GRAPH g, PATH path, int vbase, int *forbidden, int tpos, int hpos, int tail, int head, int edge, int nnodes)

static int	getcloseterms (SCIP scip, const PATH vnoi, SCIP_Real termdist, SCIP_Real ecost, const int vbase, int *neighbterms, int i, int nnodes)

static int	getcloseterms2term (SCIP scip, const GRAPH g, const GRAPH netgraph, SCIP_Real termdist, SCIP_Real ecost, int neighbterms, int nodesid, int *nodesorg, int i)

static int	getlecloseterms (SCIP scip, PATH vnoi, SCIP_Real termdist, SCIP_Real ecost, int vbase, int *neighbterms, int i, int nnodes)

static void	ansProcessCandidate (SCIP scip, GRAPH g, int marked, int count, SCIP_Real min, int candvertex)

SCIP_RETCODE	reduce_sd (SCIP scip, GRAPH g, PATH vnoi, SCIP_Real edgepreds, SCIP_Real mstsdist, int heap, int state, int vbase, int nodesid, int nodesorg, int forbidden, int nelims, SCIP_Bool nodereplacing, int *edgestate)

SCIP_RETCODE	reduce_sdPc (SCIP scip, GRAPH g, PATH vnoi, int heap, int state, int vbase, int nodesid, int nodesorg, int *nelims)

static SCIP_Real	getRSD (SCIP scip, GRAPH g, GRAPH netgraph, PATH mst, PATH vnoi, SCIP_Real mstsdist, SCIP_Real termdist1, SCIP_Real termdist2, SCIP_Real sd_initial, int vbase, int nodesid, int neighbterms1, int neighbterms2, int i, int i2, int limit)

SCIP_RETCODE	reduce_getSd (SCIP scip, GRAPH g, PATH pathtail, PATH pathhead, SCIP_Real sdist, SCIP_Real distlimit, int heap, int statetail, int statehead, int memlbltail, int memlblhead, int i, int i2, int limit, SCIP_Bool pc, SCIP_Bool mw)

SCIP_RETCODE	reduce_getSdPcMw (SCIP scip, const GRAPH g, PATH pathtail, PATH pathhead, SCIP_Real sdist, SCIP_Real distlimit, int heap, int statetail, int statehead, int memlbltail, int memlblhead, int pathmaxnodetail, int pathmaxnodehead, int i, int i2, int limit)

SCIP_RETCODE	reduce_sdspSap (SCIP scip, GRAPH g, PATH pathtail, PATH pathhead, int heap, int statetail, int statehead, int memlbltail, int memlblhead, int nelims, int limit)

SCIP_RETCODE	reduce_sdsp (SCIP scip, GRAPH g, PATH pathtail, PATH pathhead, int heap, int statetail, int statehead, int memlbltail, int memlblhead, int nelims, int limit, int *edgestate)

SCIP_RETCODE	reduce_bdr (SCIP scip, GRAPH g, GRAPH netgraph, PATH netmst, PATH vnoi, SCIP_Real mstsdist, SCIP_Real termdist1, SCIP_Real termdist2, int vbase, int nodesid, int neighbterms1, int neighbterms2, int *nelims)

SCIP_RETCODE	reduce_bd34 (SCIP scip, GRAPH g, PATH pathtail, PATH pathhead, int heap, int statetail, int statehead, int memlbltail, int memlblhead, int nelims, int limit)

SCIP_RETCODE	reduce_nts (SCIP scip, GRAPH g, PATH pathtail, PATH pathhead, int heap, int statetail, int statehead, int memlbltail, int memlblhead, int nelims, int limit)

SCIP_RETCODE	reduce_sl (SCIP scip, GRAPH g, PATH vnoi, double fixed, int heap, int state, int vbase, int vrnodes, STP_Bool visited, int solnode, int *nelims)

SCIP_RETCODE	reduce_nv (SCIP scip, GRAPH g, PATH vnoi, double fixed, int edgearrint, int heap, int state, int vbase, int solnode, int nelims)

SCIP_RETCODE	reduce_nvAdv (SCIP scip, GRAPH g, PATH vnoi, SCIP_Real distance, double fixed, int edgearrint, int heap, int state, int vbase, int neighb, int distnode, int solnode, int *nelims)

SCIP_RETCODE	reduce_ledge (SCIP scip, GRAPH g, PATH vnoi, int heap, int state, int vbase, int nelims, int edgestate)

void	reduce_ans (SCIP scip, GRAPH g, int marked, int count)

void	reduce_ansAdv (SCIP scip, GRAPH g, int marked, int count, SCIP_Bool extneigbhood)

void	reduce_ansAdv2 (SCIP scip, GRAPH g, int marked, int count)

SCIP_RETCODE	reduce_cnsAdv (SCIP scip, GRAPH g, int marked, int count)

SCIP_RETCODE	reduce_npv (SCIP scip, GRAPH g, PATH pathtail, PATH pathhead, int heap, int statetail, int statehead, int memlbltail, int memlblhead, int nelims, int limit)

SCIP_RETCODE	reduce_chain2 (SCIP scip, GRAPH g, PATH pathtail, PATH pathhead, int heap, int statetail, int statehead, int memlbltail, int memlblhead, int nelims, int limit)

void	reduce_nnp (SCIP scip, GRAPH g, int marked, int count)

Macro Definition Documentation

◆ VERTEX_CONNECT

#define VERTEX_CONNECT 0

Definition at line 43 of file reduce_alt.c.

Referenced by reduce_cnsAdv().

◆ VERTEX_TEMPNEIGHBOR

#define VERTEX_TEMPNEIGHBOR 1

Definition at line 44 of file reduce_alt.c.

Referenced by reduce_cnsAdv().

◆ VERTEX_NEIGHBOR

#define VERTEX_NEIGHBOR 2

Definition at line 45 of file reduce_alt.c.

Referenced by reduce_cnsAdv().

◆ VERTEX_OTHER

#define VERTEX_OTHER 3

Definition at line 46 of file reduce_alt.c.

Referenced by reduce_cnsAdv().

◆ STP_RED_CNSNN

#define STP_RED_CNSNN 25

Definition at line 47 of file reduce_alt.c.

Referenced by reduce_ansAdv(), reduce_ansAdv2(), and reduce_cnsAdv().

◆ STP_RED_ANSMAXCANDS

#define STP_RED_ANSMAXCANDS 500

Definition at line 48 of file reduce_alt.c.

Referenced by reduce_ansAdv().

◆ STP_RED_ANSEXMAXCANDS

#define STP_RED_ANSEXMAXCANDS 50

Definition at line 49 of file reduce_alt.c.

Referenced by reduce_ansAdv().

◆ STP_RED_ANSMAXNEIGHBORS

#define STP_RED_ANSMAXNEIGHBORS 25

Definition at line 50 of file reduce_alt.c.

Referenced by reduce_ans().

◆ STP_BDR_MAXDEGREE

#define STP_BDR_MAXDEGREE 4

Definition at line 2743 of file reduce_alt.c.

Referenced by reduce_bdr().

◆ STP_BDR_MAXDNEDGES

#define STP_BDR_MAXDNEDGES 6

Definition at line 2744 of file reduce_alt.c.

Referenced by reduce_bdr().

◆ STP_BD_MAXDEGREE

#define STP_BD_MAXDEGREE 4

Definition at line 2952 of file reduce_alt.c.

Referenced by reduce_bd34(), and reduce_nts().

◆ STP_BD_MAXDNEDGES

#define STP_BD_MAXDNEDGES 6

Definition at line 2953 of file reduce_alt.c.

Referenced by reduce_bd34(), and reduce_nts().

Function Documentation

◆ sddeltable()

static SCIP_Bool sddeltable	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	path,
		int *	vbase,
		int *	forbidden,
		int	tpos,
		int	hpos,
		int	tail,
		int	head,
		int	edge,
		int	nnodes
	)

static

Definition at line 55 of file reduce_alt.c.

References GRAPH::cost, EAT_FREE, EAT_LAST, shortest_path::edge, FALSE, flipedge, GRAPH::head, GRAPH::ieat, Is_term, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Real, SCIPisEQ(), GRAPH::tail, GRAPH::term, and TRUE.

Referenced by reduce_sd().

◆ getcloseterms()

static int getcloseterms	(	SCIP *	scip,
		const PATH *	vnoi,
		SCIP_Real *	termdist,
		SCIP_Real	ecost,
		const int *	vbase,
		int *	neighbterms,
		int	i,
		int	nnodes
	)

static

Definition at line 167 of file reduce_alt.c.

References shortest_path::dist, nnodes, NULL, and SCIPisLT().

Referenced by getRSD(), and reduce_sdPc().

◆ getcloseterms2term()

static int getcloseterms2term	(	SCIP *	scip,
		const GRAPH *	g,
		const GRAPH *	netgraph,
		SCIP_Real *	termdist,
		SCIP_Real	ecost,
		int *	neighbterms,
		int *	nodesid,
		int *	nodesorg,
		int	i
	)

static

Definition at line 206 of file reduce_alt.c.

References GRAPH::cost, EAT_LAST, GRAPH::head, Is_term, GRAPH::oeat, GRAPH::outbeg, SCIP_Real, SCIPisGT(), SCIPisLT(), GRAPH::term, and UNKNOWN.

Referenced by reduce_sdPc().

◆ getlecloseterms()

static int getlecloseterms	(	SCIP *	scip,
		PATH *	vnoi,
		SCIP_Real *	termdist,
		SCIP_Real	ecost,
		int *	vbase,
		int *	neighbterms,
		int	i,
		int	nnodes
	)

static

Definition at line 257 of file reduce_alt.c.

References a, GRAPH::ancestors, b, CONNECT, correct(), GRAPH::cost, shortest_path::dist, EAT_LAST, Edge_anti, GRAPH::edges, FALSE, FARAWAY, GRAPH::fixedges, FSP_MODE, GRAPH::grad, graph_edge_del(), graph_knot_contract(), graph_path_exec(), graph_valid(), GT, GRAPH::head, GRAPH::hoplimit, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, LE, LT, GRAPH::mark, nearest(), nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebug, SCIPdebugMessage, SCIPgetRealParam(), SCIPgetTotalTime(), SCIPintListNodeAppendCopy(), SCIPisEQ(), SCIPisGE(), SCIPisGT(), SCIPisLE(), SCIPisLT(), GRAPH::source, STP_DHCSTP, STP_MWCSP, STP_PCSPG, STP_SAP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, UNKNOWN, and voronoi_term().

Referenced by reduce_sd().

◆ ansProcessCandidate()

static void ansProcessCandidate	(	SCIP *	scip,
		GRAPH *	g,
		int *	marked,
		int *	count,
		SCIP_Real	min,
		int	candvertex
	)

static

ans subtest

Parameters

scip	SCIP data structure
g	graph data structure
marked	nodes array
count	pointer to number of reductions
min	value to not surpass
candvertex	candidate

Definition at line 1028 of file reduce_alt.c.

References EAT_LAST, FALSE, GRAPH::grad, graph_edge_del(), GRAPH::head, Is_pterm, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIPisGT(), SCIPisLE(), GRAPH::source, GRAPH::term, and TRUE.

Referenced by reduce_ans(), reduce_ansAdv(), and reduce_ansAdv2().

◆ reduce_sd()

SCIP_RETCODE reduce_sd	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	vnoi,
		SCIP_Real *	edgepreds,
		SCIP_Real *	mstsdist,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	nodesid,
		int *	nodesorg,
		int *	forbidden,
		int *	nelims,
		SCIP_Bool	nodereplacing,
		int *	edgestate
	)

Special distance test

Parameters

scip	SCIP data structure
g	graph data structure
vnoi	Voronoi data structure
edgepreds	array to store edge predecessors of auxiliary graph
mstsdist	array to store mst distances in auxiliary graph
heap	array representing a heap
state	array to indicate whether a node has been scanned during SP calculation
vbase	Voronoi base to each vertex
nodesid	array to map nodes in auxiliary graph to original ones
nodesorg	array to map terminals of original graph vertices of auxiliary graph
forbidden	array to mark whether an edge may be eliminated
nelims	point to store number of deleted edges
nodereplacing	should node replacement (by edges) be performed?
edgestate	array to store status of (directed) edge (for propagation, can otherwise be set to NULL)

Definition at line 1105 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_FREE, EAT_LAST, shortest_path::edge, EDGE_BLOCKED, GRAPH::edges, FALSE, flipedge, getlecloseterms(), GRAPH::grad, graph_edge_add(), graph_edge_del(), graph_free(), graph_get4nextTerms(), graph_init(), graph_knot_add(), graph_knot_chg(), graph_path_exec(), graph_path_exit(), graph_path_init(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, reduce_bdr(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisEQ(), SCIPisGE(), SCIPisGT(), SCIPisLT(), sddeltable(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by redLoopStp().

◆ reduce_sdPc()

SCIP_RETCODE reduce_sdPc	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	vnoi,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	nodesid,
		int *	nodesorg,
		int *	nelims
	)

SD test for PC

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

Definition at line 1499 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_FREE, EAT_LAST, GRAPH::edges, FARAWAY, flipedge, getcloseterms(), getcloseterms2term(), GRAPH::grad, graph_edge_add(), graph_edge_del(), graph_free(), graph_get4nextTerms(), graph_get4nextTTerms(), graph_init(), graph_knot_add(), graph_valid(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGT(), SCIPisLT(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by redLoopPc().

◆ getRSD()

static SCIP_Real getRSD	(	SCIP *	scip,
		GRAPH *	g,
		GRAPH *	netgraph,
		PATH *	mst,
		PATH *	vnoi,
		SCIP_Real *	mstsdist,
		SCIP_Real *	termdist1,
		SCIP_Real *	termdist2,
		SCIP_Real	sd_initial,
		int *	vbase,
		int *	nodesid,
		int *	neighbterms1,
		int *	neighbterms2,
		int	i,
		int	i2,
		int	limit
	)

static

get RSD to a single edge

Parameters

scip	SCIP data structure
g	graph structure
netgraph	auxiliary graph structure
mst	MST structure
vnoi	path structure
mstsdist	MST distance in aux-graph
termdist1	dist array
termdist2	second dist array
sd_initial	initial sd or -1.0
vbase	bases for nearest terminals
nodesid	nodes identification array
neighbterms1	neighbour terminals array
neighbterms2	second neighbour terminals array
i	first vertex
i2	second vertex
limit	limit for incident edges to consider

Definition at line 1777 of file reduce_alt.c.

References GRAPH::cost, EAT_LAST, shortest_path::edge, FARAWAY, getcloseterms(), GRAPH::head, Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Real, SCIPisGT(), SCIPisLT(), GRAPH::tail, and GRAPH::term.

Referenced by reduce_bdr().

◆ reduce_getSd()

SCIP_RETCODE reduce_getSd	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	pathtail,
		PATH *	pathhead,
		SCIP_Real *	sdist,
		SCIP_Real	distlimit,
		int *	heap,
		int *	statetail,
		int *	statehead,
		int *	memlbltail,
		int *	memlblhead,
		int	i,
		int	i2,
		int	limit,
		SCIP_Bool	pc,
		SCIP_Bool	mw
	)

get SD to a single edge

Definition at line 1970 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, graph_sdPaths(), GRAPH::head, Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPisGT(), SCIPisLE(), SCIPisLT(), GRAPH::term, and UNKNOWN.

Referenced by reduce_bd34(), reduce_chain2(), reduce_npv(), and reduce_nts().

◆ reduce_getSdPcMw()

SCIP_RETCODE reduce_getSdPcMw	(	SCIP *	scip,
		const GRAPH *	g,
		PATH *	pathtail,
		PATH *	pathhead,
		SCIP_Real *	sdist,
		SCIP_Real	distlimit,
		int *	heap,
		int *	statetail,
		int *	statehead,
		int *	memlbltail,
		int *	memlblhead,
		int *	pathmaxnodetail,
		int *	pathmaxnodehead,
		int	i,
		int	i2,
		int	limit
	)

get SD to a single edge

Definition at line 2110 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, graph_path_PcMwSd(), GRAPH::head, Is_term, GRAPH::knots, misc_stp_maxReal(), nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGT(), SCIPisNegative(), SCIPisPositive(), STP_MWCSP, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::term, and UNKNOWN.

Referenced by reduce_bd34(), and reduce_nts().

◆ reduce_sdspSap()

SCIP_RETCODE reduce_sdspSap	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	pathtail,
		PATH *	pathhead,
		int *	heap,
		int *	statetail,
		int *	statehead,
		int *	memlbltail,
		int *	memlblhead,
		int *	nelims,
		int	limit
	)

SDC test for the SAP using a limited version of Dijkstra's algorithm from both endpoints of an arc

Definition at line 2308 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_sdPaths(), GRAPH::head, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisGE(), SCIPisGT(), TRUE, and UNKNOWN.

Referenced by reduceSap().

◆ reduce_sdsp()

SCIP_RETCODE reduce_sdsp	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	pathtail,
		PATH *	pathhead,
		int *	heap,
		int *	statetail,
		int *	statehead,
		int *	memlbltail,
		int *	memlblhead,
		int *	nelims,
		int	limit,
		int *	edgestate
	)

SD test using only limited dijkstra from both endpoints of an edge

Definition at line 2459 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, EDGE_BLOCKED, FALSE, FARAWAY, GRAPH::grad, graph_edge_del(), graph_path_PcMwSd(), graph_sdPaths(), graph_valid(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArrayNull, SCIPisGE(), SCIPisGT(), SCIPisLT(), SCIPisNegative(), SCIPisPositive(), STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.

Referenced by redLoopPc(), and redLoopStp().

◆ reduce_bdr()

SCIP_RETCODE reduce_bdr	(	SCIP *	scip,
		GRAPH *	g,
		GRAPH *	netgraph,
		PATH *	netmst,
		PATH *	vnoi,
		SCIP_Real *	mstsdist,
		SCIP_Real *	termdist1,
		SCIP_Real *	termdist2,
		int *	vbase,
		int *	nodesid,
		int *	neighbterms1,
		int *	neighbterms2,
		int *	nelims
	)

bd_k test for given Steiner bottleneck distances todo bd5

Parameters

scip	SCIP data structure
g	graph structure
netgraph	auxiliary graph structure
netmst	MST structure
vnoi	path structure
mstsdist	MST distance in aux-graph
termdist1	dist array
termdist2	second dist array
vbase	bases for nearest terminals
nodesid	nodes identification array
neighbterms1	neighbour terminals array
neighbterms2	second neighbour terminals array
nelims	number of eliminations

Definition at line 2747 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, GRAPH::edges, FALSE, flipedge, getRSD(), GRAPH::grad, graph_edge_add(), graph_free(), graph_init(), graph_knot_add(), graph_knot_delPseudo(), graph_path_exec(), graph_path_exit(), graph_path_init(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, STP_BDR_MAXDEGREE, STP_BDR_MAXDNEDGES, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.

Referenced by reduce_sd().

◆ reduce_bd34()

SCIP_RETCODE reduce_bd34	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	pathtail,
		PATH *	pathhead,
		int *	heap,
		int *	statetail,
		int *	statehead,
		int *	memlbltail,
		int *	memlblhead,
		int *	nelims,
		int	limit
	)

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

Definition at line 2964 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_edge_add(), graph_free(), graph_init(), graph_knot_add(), graph_knot_delPseudo(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_valid(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, reduce_getSd(), reduce_getSdPcMw(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArrayNull, SCIPisGE(), SCIPisLE(), SCIPisLT(), STP_BD_MAXDEGREE, STP_BD_MAXDNEDGES, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.

Referenced by redLoopPc(), and redLoopStp().

◆ reduce_nts()

SCIP_RETCODE reduce_nts	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	pathtail,
		PATH *	pathhead,
		int *	heap,
		int *	statetail,
		int *	statehead,
		int *	memlbltail,
		int *	memlblhead,
		int *	nelims,
		int	limit
	)

Non-Terminal-Set test

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

Definition at line 3217 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_FREE, EAT_LAST, shortest_path::edge, GRAPH::edges, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_edge_add(), graph_free(), graph_init(), graph_knot_add(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_valid(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, reduce_getSd(), reduce_getSdPcMw(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArrayNull, SCIPisGE(), SCIPisGT(), SCIPisLT(), STP_BD_MAXDEGREE, STP_BD_MAXDNEDGES, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

◆ reduce_sl()

SCIP_RETCODE reduce_sl	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	vnoi,
		double *	fixed,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	vrnodes,
		STP_Bool *	visited,
		int *	solnode,
		int *	nelims
	)

Parameters

scip	SCIP data structure
g	graph data structure
vnoi	Voronoi data structure
fixed	offset pointer
heap	heap array
state	shortest path array
vbase	Voronoi/shortest path bases array
vrnodes	Voronoi/shortest path array
visited	Voronoi/shortest path array
solnode	node array to mark whether an node is part of a given solution (CONNECT), or NULL
nelims	pointer to store number of eliminations

Definition at line 3483 of file reduce_alt.c.

References GRAPH::ancestors, GRAPH::cost, shortest_path::dist, EAT_LAST, FALSE, FARAWAY, GRAPH::fixedges, GRAPH::grad, graph_knot_chg(), graph_knot_contract(), graph_pc_contractEdge(), graph_voronoiTerms(), GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPintListNodeAppendCopy(), SCIPisGE(), SCIPisLE(), SCIPisLT(), SCIPqueueCreate(), SCIPqueueFree(), SCIPqueueInsert(), SCIPqueueIsEmpty(), SCIPqueueRemove(), GRAPH::source, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by nvreduce_sl().

◆ reduce_nv()

SCIP_RETCODE reduce_nv	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	vnoi,
		double *	fixed,
		int *	edgearrint,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	solnode,
		int *	nelims
	)

Parameters

scip	SCIP data structure
g	graph data structure
vnoi	Voronoi data structure
fixed	offset pointer
edgearrint	edge int array for internal computations
heap	heap array
state	array for internal computations
vbase	array for internal computations
solnode	node array to mark whether an node is part of a given solution (CONNECT), or NULL
nelims	pointer to store number of eliminations

Definition at line 3710 of file reduce_alt.c.

References GRAPH::ancestors, GRAPH::cost, shortest_path::dist, EAT_LAST, FARAWAY, GRAPH::fixedges, GRAPH::grad, graph_knot_contract(), graph_pc_contractEdge(), graph_voronoiWithDist(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPintListNodeAppendCopy(), SCIPisGE(), SCIPisLE(), GRAPH::source, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, and UNKNOWN.

◆ reduce_nvAdv()

SCIP_RETCODE reduce_nvAdv	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	vnoi,
		SCIP_Real *	distance,
		double *	fixed,
		int *	edgearrint,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	neighb,
		int *	distnode,
		int *	solnode,
		int *	nelims
	)

Parameters

scip	SCIP data structure
g	graph data structure
vnoi	Voronoi data structure
distance	nodes-sized distance array
fixed	offset pointer
edgearrint	edges-sized array
heap	heap array
state	shortest path array
vbase	Voronoi base array
neighb	nodes-sized neighborhood array
distnode	nodes-sized distance array
solnode	node array to mark whether an node is part of a given solution (CONNECT), or NULL
nelims	pointer to store number of eliminations

Definition at line 3903 of file reduce_alt.c.

References GRAPH::ancestors, GRAPH::cost, shortest_path::dist, EAT_LAST, FALSE, FARAWAY, GRAPH::fixedges, flipedge, GRAPH::grad, graph_knot_contract(), graph_pc_contractEdge(), graph_voronoiWithDist(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPintListNodeAppendCopy(), SCIPisGE(), SCIPisLE(), SCIPisLT(), GRAPH::source, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by nvreduce_sl().

◆ reduce_ledge()

SCIP_RETCODE reduce_ledge	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	vnoi,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	nelims,
		int *	edgestate
	)

Definition at line 4143 of file reduce_alt.c.

References BMSclearMemoryArray, CONNECT, GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, Edge_anti, EDGE_BLOCKED, GRAPH::edges, FALSE, GRAPH::grad, graph_edge_add(), graph_edge_del(), graph_free(), graph_init(), graph_knot_add(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_valid(), graph_voronoiTerms(), GRAPH::head, Is_term, GRAPH::knots, level0(), GRAPH::mark, MST_MODE, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_state, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisGE(), SCIPisGT(), GRAPH::source, STP_SPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

Referenced by redLoopStp().

◆ reduce_ans()

void reduce_ans	(	SCIP *	scip,
		GRAPH *	g,
		int *	marked,
		int *	count
	)

adjacent neighbourhood reduction for the MWCSP

Parameters

scip	SCIP data structure
g	graph data structure
marked	nodes array
count	pointer to number of reductions

Definition at line 4447 of file reduce_alt.c.

References ansProcessCandidate(), EAT_LAST, FALSE, GRAPH::grad, graph_valid(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Real, SCIPisLT(), STP_MWCSP, STP_RED_ANSMAXNEIGHBORS, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by redLoopMw().

◆ reduce_ansAdv()

void reduce_ansAdv	(	SCIP *	scip,
		GRAPH *	g,
		int *	marked,
		int *	count,
		SCIP_Bool	extneigbhood
	)

advanced adjacent neighbourhood reduction for the MWCSP

Parameters

scip	SCIP data structure
g	graph data structure
marked	nodes array
count	pointer to number of performed reductions
extneigbhood	use extended neighbour hood

Definition at line 4515 of file reduce_alt.c.

References ansProcessCandidate(), EAT_LAST, FALSE, GRAPH::grad, graph_valid(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, MAX, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Real, SCIPdebugMessage, SCIPisGT(), SCIPisLE(), STP_MWCSP, STP_RED_ANSEXMAXCANDS, STP_RED_ANSMAXCANDS, STP_RED_CNSNN, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by redLoopMw().

◆ reduce_ansAdv2()

void reduce_ansAdv2	(	SCIP *	scip,
		GRAPH *	g,
		int *	marked,
		int *	count
	)

alternative advanced adjacent neighbourhood reduction for the MWCSP

Parameters

scip	SCIP data structure
g	graph data structure
marked	nodes array
count	pointer to number of reductions

Definition at line 4621 of file reduce_alt.c.

References ansProcessCandidate(), EAT_LAST, FALSE, GRAPH::grad, graph_valid(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Real, SCIPisGE(), SCIPisGT(), SCIPisLE(), STP_MWCSP, STP_RED_CNSNN, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.

Referenced by redLoopMw().

◆ reduce_cnsAdv()

SCIP_RETCODE reduce_cnsAdv	(	SCIP *	scip,
		GRAPH *	g,
		int *	marked,
		int *	count
	)

advanced connected neighborhood subset reduction test for the MWCSP

Parameters

scip	SCIP data structure
g	graph data structure
marked	nodes array for internal use
count	pointer to number of reductions

Definition at line 4748 of file reduce_alt.c.

References EAT_LAST, FALSE, GRAPH::grad, graph_edge_del(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_OKAY, SCIP_Real, SCIPisGE(), SCIPisGT(), SCIPisLE(), STP_MWCSP, STP_RED_CNSNN, GRAPH::stp_type, GRAPH::term, TRUE, UNKNOWN, VERTEX_CONNECT, VERTEX_NEIGHBOR, VERTEX_OTHER, and VERTEX_TEMPNEIGHBOR.

◆ reduce_npv()

SCIP_RETCODE reduce_npv	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	pathtail,
		PATH *	pathhead,
		int *	heap,
		int *	statetail,
		int *	statehead,
		int *	memlbltail,
		int *	memlblhead,
		int *	nelims,
		int	limit
	)

non-positive vertex reduction for the MWCSP

Definition at line 5024 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_edge_add(), graph_edge_del(), graph_free(), graph_init(), graph_knot_add(), graph_path_exec(), graph_path_exit(), graph_path_init(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, reduce_getSd(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGE(), SCIPisGT(), SCIPisLE(), GRAPH::source, GRAPH::term, TRUE, and UNKNOWN.

Referenced by redLoopMw().

◆ reduce_chain2()

SCIP_RETCODE reduce_chain2	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	pathtail,
		PATH *	pathhead,
		int *	heap,
		int *	statetail,
		int *	statehead,
		int *	memlbltail,
		int *	memlblhead,
		int *	nelims,
		int	limit
	)

chain reduction (NPV_2) for the MWCSP

Definition at line 5367 of file reduce_alt.c.

References shortest_path::dist, shortest_path::edge, FALSE, FARAWAY, GRAPH::grad, graph_edge_del(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, reduce_getSd(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGE(), GRAPH::term, TRUE, and UNKNOWN.

Referenced by redLoopMw().

◆ reduce_nnp()

void reduce_nnp	(	SCIP *	scip,
		GRAPH *	g,
		int *	marked,
		int *	count
	)

non-negative path reduction for the MWCSP

Parameters

scip	SCIP data structure
g	graph data structure
marked	nodes array
count	pointer to number of reductions

Definition at line 5450 of file reduce_alt.c.

References EAT_LAST, FALSE, graph_edge_del(), graph_valid(), GRAPH::head, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, STP_MWCSP, GRAPH::stp_type, and TRUE.

Referenced by redLoopMw().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ VERTEX_CONNECT

◆ VERTEX_TEMPNEIGHBOR

◆ VERTEX_NEIGHBOR

◆ VERTEX_OTHER

◆ STP_RED_CNSNN

◆ STP_RED_ANSMAXCANDS

◆ STP_RED_ANSEXMAXCANDS

◆ STP_RED_ANSMAXNEIGHBORS

◆ STP_BDR_MAXDEGREE

◆ STP_BDR_MAXDNEDGES

◆ STP_BD_MAXDEGREE

◆ STP_BD_MAXDNEDGES

Function Documentation

◆ sddeltable()

◆ getcloseterms()

◆ getcloseterms2term()

◆ getlecloseterms()

◆ ansProcessCandidate()

◆ reduce_sd()

◆ reduce_sdPc()

◆ getRSD()

◆ reduce_getSd()

◆ reduce_getSdPcMw()

◆ reduce_sdspSap()

◆ reduce_sdsp()

◆ reduce_bdr()

◆ reduce_bd34()

◆ reduce_nts()

◆ reduce_sl()

◆ reduce_nv()

◆ reduce_nvAdv()

◆ reduce_ledge()

◆ reduce_ans()

◆ reduce_ansAdv()

◆ reduce_ansAdv2()

◆ reduce_cnsAdv()

◆ reduce_npv()

◆ reduce_chain2()

◆ reduce_nnp()