Detailed Description

several basic reductions for Steiner tree problems

Author: Daniel Rehfeldt

This file implements basic reduction techniques for several Steiner problems. All tests are described in "A Generic Approach to Solving the Steiner Tree Problem and Variants" by Daniel Rehfeldt.

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

Definition in file reduce_simple.c.

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

Go to the source code of this file.

Functions
static SCIP_Bool	adjterms (const GRAPH *g)

static unsigned	nchains (const GRAPH *g)

static SCIP_Bool	is_maxprize (SCIP scip, const GRAPH g, int i, SCIP_Real *maxprize)

static SCIP_RETCODE	trydg1edgepc (SCIP scip, GRAPH g, SCIP_Real offset, int solnode, int count, int i, int iout, SCIP_Bool rerun, SCIP_Real *maxprize)

static SCIP_RETCODE	traverseChain (SCIP scip, GRAPH g, int length, int final, int i, int i1, int i2, int e1)

static void	adjust0term (SCIP scip, GRAPH g, int i)

SCIP_RETCODE	reduce_contractZeroEdges (SCIP scip, GRAPH g, SCIP_Bool savehistory)

SCIP_RETCODE	reduce_simple (SCIP scip, GRAPH g, SCIP_Real fixed, int solnode, int nelims, int edgestate)

SCIP_RETCODE	reduce_simple_sap (SCIP scip, GRAPH g, SCIP_Real fixed, int count)

SCIP_RETCODE	reduce_rpt (SCIP scip, GRAPH g, SCIP_Real fixed, int count)

SCIP_RETCODE	reduce_simple_mw (SCIP scip, GRAPH g, int solnode, SCIP_Real fixed, int *count)

SCIP_RETCODE	reduce_simple_hc (SCIP scip, GRAPH g, SCIP_Real fixed, int count)

SCIP_RETCODE	reduce_simple_pc (SCIP scip, GRAPH g, SCIP_Real fixed, int count, int *solnode, SCIP_Bool contractroot)

Function Documentation

◆ adjterms()

static SCIP_Bool adjterms ( const GRAPH * g )

static

check whether problem has adjacent terminals

Parameters

g	graph data structure

Definition at line 39 of file reduce_simple.c.

References EAT_FREE, GRAPH::edges, FALSE, GRAPH::head, Is_term, GRAPH::mark, GRAPH::oeat, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by reduce_simple_mw().

◆ nchains()

static unsigned nchains ( const GRAPH * g )

static

count numbers of chains

Parameters

g	graph data structure

Definition at line 60 of file reduce_simple.c.

References EAT_FREE, GRAPH::edges, GRAPH::grad, GRAPH::head, Is_term, GRAPH::oeat, GRAPH::tail, and GRAPH::term.

Referenced by reduce_simple_mw().

◆ is_maxprize()

static SCIP_Bool is_maxprize	(	SCIP *	scip,
		const GRAPH *	g,
		int	i,
		SCIP_Real *	maxprize
	)

static

is there no vertex of higher prize?

Parameters

scip	SCIP data structure
g	graph data structure
i	the terminal to be checked
maxprize	stores incumbent prize (can be updated)

Definition at line 80 of file reduce_simple.c.

References FALSE, GRAPH::grad, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::prize, SCIP_Real, SCIPdebugMessage, GRAPH::source, STP_RPCSPG, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by reduce_simple_mw(), reduce_simple_pc(), and trydg1edgepc().

◆ trydg1edgepc()

static SCIP_RETCODE trydg1edgepc	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	offset,
		int *	solnode,
		int *	count,
		int	i,
		int	iout,
		SCIP_Bool *	rerun,
		SCIP_Real *	maxprize
	)

static

try to eliminate a terminal of degree one

Parameters

scip	SCIP data structure
g	graph data structure
offset	pointer to store the offset
solnode	solution nodes or NULL
count	pointer storing number of eliminated edges
i	the terminal to be checked
iout	outgoing arc
rerun	further eliminations possible?
maxprize	stores incumbent prize (can be updated)

Definition at line 129 of file reduce_simple.c.

References GRAPH::ancestors, GRAPH::cost, EAT_LAST, GRAPH::fixedges, flipedge, GRAPH::grad, graph_edge_del(), graph_pc_contractEdge(), graph_pc_deleteTerm(), graph_pc_knot2nonTerm(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, is_maxprize(), Is_pterm, Is_term, GRAPH::mark, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::pcancestors, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), SCIPisGE(), SCIPisGT(), SCIPisLE(), GRAPH::source, STP_MWCSP, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

Referenced by reduce_simple_mw(), and reduce_simple_pc().

◆ traverseChain()

static SCIP_RETCODE traverseChain	(	SCIP *	scip,
		GRAPH *	g,
		int *	length,
		int *	final,
		int	i,
		int	i1,
		int	i2,
		int	e1
	)

static

traverse one side of a chain (MWCSP)

Parameters

scip	SCIP data structure
g	graph data structure
length	pointer to store length of chain
final	pointer to store final vertex
i	start vertex
i1	first vertex
i2	last vertex
e1	first edge

Definition at line 306 of file reduce_simple.c.

References GRAPH::ancestors, GRAPH::cost, EAT_LAST, flipedge, GRAPH::grad, graph_edge_del(), graph_edge_redirect(), GRAPH::head, Is_term, GRAPH::mark, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), SCIPisGE(), SCIPisLE(), GRAPH::term, and TRUE.

Referenced by reduce_simple_mw().

◆ adjust0term()

static void adjust0term	(	SCIP *	scip,
		GRAPH *	g,
		int	i
	)

static

adjust for a (rooted) PC or MW problem

Parameters

scip	SCIP data structure
g	graph data structure
i	index of the terminal

Definition at line 402 of file reduce_simple.c.

References EAT_LAST, GRAPH::grad, graph_edge_del(), graph_pc_knot2nonTerm(), GRAPH::head, Is_pterm, Is_term, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIPisGT(), SCIPisZero(), GRAPH::source, STP_RPCSPG, GRAPH::stp_type, GRAPH::term, GRAPH::term2edge, TRUE, and UNKNOWN.

Referenced by reduce_simple_mw(), and reduce_simple_pc().

◆ reduce_contractZeroEdges()

SCIP_RETCODE reduce_contractZeroEdges	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Bool	savehistory
	)

contract edges of weight zero

Parameters

scip	SCIP data structure
g	graph data structure
savehistory	save the history?

Definition at line 453 of file reduce_simple.c.

References GRAPH::ancestors, GRAPH::cost, EAT_FREE, GRAPH::edges, GRAPH::fixedges, flipedge, graph_knot_contract(), GRAPH::head, NULL, GRAPH::oeat, SCIP_CALL, SCIP_OKAY, SCIPintListNodeAppendCopy(), SCIPisZero(), and GRAPH::tail.

Referenced by redbasedVarfixing(), and redLoopStp().

◆ reduce_simple()

SCIP_RETCODE reduce_simple	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	solnode,
		int *	nelims,
		int *	edgestate
	)

basic reduction tests for the STP

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offset value
solnode	node array to mark whether an node is part of a given solution (CONNECT), or NULL
nelims	pointer to number of reductions
edgestate	array to store status of (directed) edge (for propagation, can otherwise be set to NULL)

Definition at line 489 of file reduce_simple.c.

References GRAPH::ancestors, GRAPH::cost, EAT_LAST, Edge_anti, EDGE_BLOCKED, EQ, FALSE, FARAWAY, GRAPH::fixedges, flipedge, GRAPH::grad, graph_edge_del(), graph_knot_contract(), graph_knot_contractLowdeg2High(), graph_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPintListNodeAppendCopy(), SCIPisLE(), SCIPisLT(), GRAPH::term, TRUE, and UNKNOWN.

Referenced by nvreduce_sl(), and redLoopStp().

◆ reduce_simple_sap()

SCIP_RETCODE reduce_simple_sap	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	count
	)

basic reduction tests for the SAP

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offfset value
count	pointer to number of reductions

Definition at line 684 of file reduce_simple.c.

References GRAPH::ancestors, GRAPH::cost, EAT_LAST, Edge_anti, FALSE, FARAWAY, GRAPH::fixedges, GRAPH::grad, graph_edge_del(), graph_knot_contract(), graph_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPintListNodeAppendCopy(), SCIPisGT(), SCIPisLT(), SCIPqueueCreate(), SCIPqueueFree(), SCIPqueueInsert(), SCIPqueueIsEmpty(), SCIPqueueRemove(), GRAPH::source, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by reduceSap().

◆ reduce_rpt()

SCIP_RETCODE reduce_rpt	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	count
	)

root proximity terminal test (SAP)

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offset value
count	pointer to number of reductions

Definition at line 876 of file reduce_simple.c.

References GRAPH::ancestors, GRAPH::cost, EAT_LAST, GRAPH::fixedges, GRAPH::grad, graph_knot_contract(), graph_path_execX(), GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPintListNodeAppendCopy(), SCIPisGT(), GRAPH::source, GRAPH::tail, and GRAPH::term.

Referenced by reduceSap().

◆ reduce_simple_mw()

SCIP_RETCODE reduce_simple_mw	(	SCIP *	scip,
		GRAPH *	g,
		int *	solnode,
		SCIP_Real *	fixed,
		int *	count
	)

basic reduction tests for the MWCS problem

Parameters

scip	SCIP data structure
g	graph data structure
solnode	array to indicate whether a node is part of the current solution (==CONNECT)
fixed	pointer to offset value
count	pointer to number of reductions

Definition at line 947 of file reduce_simple.c.

References adjterms(), adjust0term(), GRAPH::cost, EAT_LAST, Edge_anti, FALSE, flipedge_Uint, GRAPH::grad, graph_edge_del(), graph_knot_contract(), graph_pc_contractEdge(), graph_pc_contractEdgeAncestors(), graph_pc_deleteTerm(), graph_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, is_maxprize(), Is_pterm, Is_term, GRAPH::knots, level0save(), GRAPH::mark, nchains(), nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGE(), SCIPisLE(), SCIPisZero(), GRAPH::source, STP_MWCSP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, traverseChain(), TRUE, and trydg1edgepc().

Referenced by redLoopMw().

◆ reduce_simple_hc()

SCIP_RETCODE reduce_simple_hc	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	count
	)

basic reduction tests for the HCDSTP

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offfset value
count	pointer to number of reductions

Definition at line 1247 of file reduce_simple.c.

References GRAPH::cost, EAT_LAST, FALSE, FARAWAY, flipedge, graph_edge_del(), GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_OKAY, SCIPdebugMessage, SCIPisGE(), SCIPisLT(), GRAPH::source, STP_DHCSTP, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by reduceHc().

◆ reduce_simple_pc()

SCIP_RETCODE reduce_simple_pc	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	count,
		int *	solnode,
		SCIP_Bool	contractroot
	)

basic reductions for RPCSTP and PCSPG

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offset value
count	pointer to number of reductions
solnode	solution nodes
contractroot	contract vertices into root (for rooted prize-collecting)

Definition at line 1327 of file reduce_simple.c.

References adjust0term(), GRAPH::ancestors, GRAPH::cost, EAT_LAST, Edge_anti, GRAPH::extended, FALSE, FARAWAY, GRAPH::fixedges, flipedge, GRAPH::grad, graph_edge_del(), graph_edge_redirect(), graph_knot_contract(), graph_pc_contractEdge(), graph_pc_deleteTerm(), graph_pc_knot2nonTerm(), graph_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, is_maxprize(), Is_pterm, Is_term, GRAPH::knots, level0save(), GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::pcancestors, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), SCIPisEQ(), SCIPisLE(), SCIPisLT(), SCIPisZero(), GRAPH::source, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, trydg1edgepc(), and UNKNOWN.

Referenced by nvreduce_sl(), and redLoopPc().

SCIP

Detailed Description

Functions

Function Documentation

◆ adjterms()

◆ nchains()

◆ is_maxprize()

◆ trydg1edgepc()

◆ traverseChain()

◆ adjust0term()

◆ reduce_contractZeroEdges()

◆ reduce_simple()

◆ reduce_simple_sap()

◆ reduce_rpt()

◆ reduce_simple_mw()

◆ reduce_simple_hc()

◆ reduce_simple_pc()