Detailed Description

several basic reductions for Steiner tree PC/MW problems

Author: Daniel Rehfeldt

This file implements basic reduction techniques for prize-collecting Steiner tree and maximum-weight connected subgraph. Mosts 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 reduce.h.

Definition in file reduce_pcsimple.c.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "graph.h"
#include "reduce.h"
#include "portab.h"
#include "enumeration.h"
#include "scip/scip.h"

Go to the source code of this file.

Functions
static SCIP_Bool	hasAdjacentTerminals (const GRAPH *g)

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

static int	mwGetNchains (const GRAPH *g)

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

static SCIP_RETCODE	mwContractNonPositiveChain (SCIP scip, int i, GRAPH g, int *nelims)

static SCIP_RETCODE	mwContract0WeightVertices (SCIP scip, GRAPH g, int solnode, int nelims)

static SCIP_RETCODE	mwContractTerminalsChainWise (SCIP scip, GRAPH g, SCIP_Real offset, int solnode, int *nelims)

static SCIP_RETCODE	mwContractTerminalsSimple (SCIP scip, GRAPH g, SCIP_Real offset, int solnode, int *nelims)

static SCIP_RETCODE	mwReduceTermDeg1 (SCIP scip, const int edgestate, GRAPH g, SCIP_Real offset, int solnode, int nelims, int i, int iout, SCIP_Bool rerun, SCIP_Real maxprize)

static void	rpcTryFullReduce (SCIP scip, GRAPH g)

static void	pcmwReduceKnotDeg1 (SCIP scip, GRAPH g, int i, SCIP_Bool *rerun)

static SCIP_RETCODE	pcReduceKnotDeg2 (SCIP scip, GRAPH g, int i, int solnode, SCIP_Bool rerun)

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

static void	pcmwDeleteNonSolEdges (SCIP scip, const int result, GRAPH g, int nelims)

static SCIP_RETCODE	pcmwEnumerationTry (SCIP scip, GRAPH g, int nelims, SCIP_Bool rerun)

static SCIP_RETCODE	pcReduceTermDeg1 (SCIP scip, const int edgestate, GRAPH g, SCIP_Real offset, int solnode, int nelims, int i, SCIP_Bool rerun, SCIP_Real maxprize)

static SCIP_RETCODE	pcReduceTermDeg2 (SCIP scip, const int edgestate, GRAPH g, SCIP_Real offset, int solnode, int nelims, int i, SCIP_Bool rerun, SCIP_Real maxprize)

static SCIP_RETCODE	pcContractWithAdjacentTerm (SCIP scip, const int edgestate, GRAPH g, SCIP_Real offset, int solnode, int nelims, int i, SCIP_Bool *rerun)

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

SCIP_RETCODE	reduce_simple_pc (SCIP scip, const int edgestate, GRAPH g, SCIP_Real fixed, int countnew, int countall, int *solnode)

void	reduce_removeDeg0NonLeafTerms (SCIP scip, GRAPH g, SCIP_Real *offsetp)

SCIP_RETCODE	reduce_unconnectedRpcRmwInfeas (SCIP scip, GRAPH g, SCIP_Real offsetp, SCIP_Bool infeas)

SCIP_RETCODE	reduce_unconnectedRpcRmw (SCIP scip, GRAPH g, SCIP_Real *offsetp)

Function Documentation

◆ hasAdjacentTerminals()

static SCIP_Bool hasAdjacentTerminals ( const GRAPH * g )

static

check whether problem has adjacent terminals

Parameters

g	graph data structure

Definition at line 44 of file reduce_pcsimple.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().

◆ isMaxprizeTerm()

static SCIP_Bool isMaxprizeTerm	(	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 66 of file reduce_pcsimple.c.

References FALSE, graph_get_nNodes(), graph_pc_isRootedPcMw(), Is_term, GRAPH::mark, nnodes, GRAPH::prize, SCIP_Real, SCIPdebugMessage, GRAPH::source, and GRAPH::term.

Referenced by mwReduceTermDeg1(), pcReduceTermDeg1(), pcReduceTermDeg2(), reduce_removeDeg0NonLeafTerms(), reduce_simple_mw(), and reduce_simple_pc().

◆ mwGetNchains()

static int mwGetNchains ( const GRAPH * g )

inlinestatic

count numbers of chains

Parameters

g	graph data structure

Definition at line 123 of file reduce_pcsimple.c.

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

Referenced by reduce_simple_mw().

◆ mwTraverseChain()

static SCIP_RETCODE mwTraverseChain	(	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 149 of file reduce_pcsimple.c.

References GRAPH::ancestors, GRAPH::cost, EAT_LAST, Edge_even, flipedge, GRAPH::grad, graph_edge_del(), graph_edge_delHistory(), graph_edge_getAncestors(), graph_edge_redirect(), graph_pc_isMw(), 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 mwContractNonPositiveChain().

◆ mwContractNonPositiveChain()

static SCIP_RETCODE mwContractNonPositiveChain	(	SCIP *	scip,
		int	i,
		GRAPH *	g,
		int *	nelims
	)

static

contracts non-positive chains (path of degree 2 vertices) for (R)MWCS

Parameters

scip	SCIP data structure
i	the start node
g	graph data structure
nelims	pointer to number of reductions

Definition at line 240 of file reduce_pcsimple.c.

References GRAPH::cost, EAT_LAST, GRAPH::grad, graph_edge_del(), graph_pc_isMw(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, GRAPH::mark, mwTraverseChain(), GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, and TRUE.

Referenced by reduce_simple_mw().

◆ mwContract0WeightVertices()

static SCIP_RETCODE mwContract0WeightVertices	(	SCIP *	scip,
		GRAPH *	g,
		int *	solnode,
		int *	nelims
	)

static

contract 0-weight vertices 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)
nelims	pointer to number of reductions

Definition at line 292 of file reduce_pcsimple.c.

References EAT_LAST, FALSE, flipedge_Uint, GRAPH::grad, graph_get_nNodes(), graph_knot_contract(), graph_pc_contractEdge(), graph_pc_contractNodeAncestors(), graph_pc_isMw(), GRAPH::head, Is_term, GRAPH::mark, nnodes, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPisGE(), SCIPisZero(), and GRAPH::term.

Referenced by reduce_simple_mw().

◆ mwContractTerminalsChainWise()

static SCIP_RETCODE mwContractTerminalsChainWise	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	offset,
		int *	solnode,
		int *	nelims
	)

static

contract positive vertices for the MWCS problem

Parameters

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

Definition at line 344 of file reduce_pcsimple.c.

References FALSE, GRAPH::grad, graph_get_nNodes(), graph_pc_contractEdge(), graph_pc_isMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsFixedTerm(), GRAPH::head, Is_term, LE, GRAPH::mark, nnodes, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, GRAPH::source, GRAPH::term, and TRUE.

Referenced by reduce_simple_mw().

◆ mwContractTerminalsSimple()

static SCIP_RETCODE mwContractTerminalsSimple	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	offset,
		int *	solnode,
		int *	nelims
	)

static

contract positive vertices for the MWCS problem

Parameters

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

Definition at line 460 of file reduce_pcsimple.c.

References EAT_LAST, FALSE, GRAPH::grad, graph_get_nNodes(), graph_pc_contractEdge(), graph_pc_isMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), GRAPH::head, Is_term, GRAPH::mark, nnodes, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, GRAPH::source, GRAPH::term, and TRUE.

Referenced by reduce_simple_mw().

◆ mwReduceTermDeg1()

static SCIP_RETCODE mwReduceTermDeg1	(	SCIP *	scip,
		const int *	edgestate,
		GRAPH *	g,
		SCIP_Real *	offset,
		int *	solnode,
		int *	nelims,
		int	i,
		int	iout,
		SCIP_Bool *	rerun,
		SCIP_Real *	maxprize
	)

static

try to eliminate a terminal of degree one

Parameters

scip	SCIP data structure
edgestate	for propagation or NULL
g	graph data structure
offset	pointer to store the offset
solnode	solution nodes or NULL
nelims	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 526 of file reduce_pcsimple.c.

References GRAPH::cost, EDGE_BLOCKED, EQ, GRAPH::grad, graph_pc_contractEdge(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsFixedTerm(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, isMaxprizeTerm(), GRAPH::mark, MAX, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGE(), SCIPisGT(), SCIPisLE(), GRAPH::tail, GRAPH::term, and TRUE.

Referenced by reduce_simple_mw().

◆ rpcTryFullReduce()

static void rpcTryFullReduce	(	SCIP *	scip,
		GRAPH *	g
	)

static

tries to reduce full graph for a rooted PC problem

Parameters

scip	SCIP data structure
g	graph data structure

Definition at line 619 of file reduce_pcsimple.c.

References GRAPH::grad, graph_knot_del(), graph_pc_nFixedTerms(), graph_pc_nProperPotentialTerms(), GRAPH::knots, nnodes, GRAPH::source, STP_RPCSPG, GRAPH::stp_type, and TRUE.

Referenced by reduce_simple_pc().

◆ pcmwReduceKnotDeg1()

static void pcmwReduceKnotDeg1	(	SCIP *	scip,
		GRAPH *	g,
		int	i,
		SCIP_Bool *	rerun
	)

static

reduces non-terminal of degree 1 for a (rooted) PC/MW problem

Parameters

scip	SCIP data structure
g	graph data structure
i	index of the terminal
rerun	further eliminations possible?

Definition at line 649 of file reduce_pcsimple.c.

References EAT_LAST, Edge_anti, FALSE, GRAPH::grad, graph_edge_del(), GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIPdebugMessage, SCIPisLE(), GRAPH::tail, GRAPH::term, and TRUE.

Referenced by reduce_simple_mw(), and reduce_simple_pc().

◆ pcReduceKnotDeg2()

static SCIP_RETCODE pcReduceKnotDeg2	(	SCIP *	scip,
		GRAPH *	g,
		int	i,
		int *	solnode,
		SCIP_Bool *	rerun
	)

static

reduces non-terminal of degree 2 for a (rooted) PC problem (by replacement)

Parameters

scip	SCIP data structure
g	graph data structure
i	index of the terminal
solnode	solution nodes or NULL
rerun	further eliminations possible?

Definition at line 681 of file reduce_pcsimple.c.

References GRAPH::cost, graph_knot_replaceDeg2(), GRAPH::head, Is_term, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, GRAPH::term, and TRUE.

Referenced by reduce_simple_pc().

◆ pcmwReduceTerm0Prize()

static void pcmwReduceTerm0Prize	(	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 709 of file reduce_pcsimple.c.

References EAT_LAST, GRAPH::extended, graph_edge_del(), graph_knot_del(), graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_knotToNonTermProperty(), graph_pc_termIsNonLeafTerm(), GRAPH::head, Is_pseudoTerm, Is_term, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIPisZero(), GRAPH::source, STP_RPCSPG, GRAPH::stp_type, GRAPH::term, GRAPH::term2edge, TRUE, and UNKNOWN.

Referenced by reduce_simple_mw(), and reduce_simple_pc().

◆ pcmwDeleteNonSolEdges()

static void pcmwDeleteNonSolEdges	(	SCIP *	scip,
		const int *	result,
		GRAPH *	g,
		int *	nelims
	)

static

check for possible enumeration

Parameters

scip	SCIP data structure
result	the result
g	graph data structure
nelims	number of eliminations

Definition at line 764 of file reduce_pcsimple.c.

References CONNECT, GRAPH::cost, EAT_LAST, FARAWAY, flipedge, graph_edge_del(), graph_get_nNodes(), graph_mark(), GRAPH::head, LT, GRAPH::mark, nnodes, GRAPH::oeat, GRAPH::outbeg, and TRUE.

Referenced by pcmwEnumerationTry().

◆ pcmwEnumerationTry()

static SCIP_RETCODE pcmwEnumerationTry	(	SCIP *	scip,
		GRAPH *	g,
		int *	nelims,
		SCIP_Bool *	rerun
	)

static

check for possible enumeration

Parameters

scip	SCIP data structure
g	graph data structure
nelims	number of eliminations
rerun	further eliminations possible?

Definition at line 815 of file reduce_pcsimple.c.

References enumeration_findSolPcMw(), enumeration_isPossible(), FALSE, GRAPH::grad, graph_get_nEdges(), graph_printInfo(), GRAPH::mark, NULL, pcmwDeleteNonSolEdges(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, GRAPH::source, STP_RPCSPG, GRAPH::stp_type, and TRUE.

Referenced by reduce_simple_mw(), and reduce_simple_pc().

◆ pcReduceTermDeg1()

static SCIP_RETCODE pcReduceTermDeg1	(	SCIP *	scip,
		const int *	edgestate,
		GRAPH *	g,
		SCIP_Real *	offset,
		int *	solnode,
		int *	nelims,
		int	i,
		SCIP_Bool *	rerun,
		SCIP_Real *	maxprize
	)

inlinestatic

try to eliminate a terminal of degree one

Parameters

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

Definition at line 862 of file reduce_pcsimple.c.

References GRAPH::cost, EAT_LAST, EDGE_BLOCKED, GRAPH::grad, graph_pc_contractEdge(), graph_pc_deleteTerm(), graph_pc_knotIsFixedTerm(), graph_pc_termIsNonLeafTerm(), GRAPH::head, Is_term, isMaxprizeTerm(), GRAPH::mark, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPisGT(), SCIPisLE(), GRAPH::source, STP_PCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by reduce_simple_pc().

◆ pcReduceTermDeg2()

static SCIP_RETCODE pcReduceTermDeg2	(	SCIP *	scip,
		const int *	edgestate,
		GRAPH *	g,
		SCIP_Real *	offset,
		int *	solnode,
		int *	nelims,
		int	i,
		SCIP_Bool *	rerun,
		SCIP_Real *	maxprize
	)

inlinestatic

Parameters

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

Definition at line 936 of file reduce_pcsimple.c.

References GRAPH::cost, EAT_LAST, EDGE_BLOCKED, graph_edge_del(), graph_edge_reinsert(), graph_pc_contractEdge(), graph_pc_deleteTerm(), graph_pc_knotIsFixedTerm(), graph_pc_termIsNonLeafTerm(), graph_singletonAncestors_freeMembers(), graph_singletonAncestors_init(), GRAPH::head, Is_term, isMaxprizeTerm(), GRAPH::mark, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPisGE(), SCIPisGT(), SCIPisLE(), GRAPH::source, STP_PCSPG, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by reduce_simple_pc().

◆ pcContractWithAdjacentTerm()

static SCIP_RETCODE pcContractWithAdjacentTerm	(	SCIP *	scip,
		const int *	edgestate,
		GRAPH *	g,
		SCIP_Real *	offset,
		int *	solnode,
		int *	nelims,
		int	i,
		SCIP_Bool *	rerun
	)

inlinestatic

try to contract terminal with adjacent one

Parameters

scip	SCIP data structure
edgestate	for propagation or NULL
g	graph data structure
offset	pointer to store the offset
solnode	solution nodes or NULL
nelims	pointer storing number of eliminated edges
i	the terminal to be checked
rerun	further eliminations possible?

Definition at line 1038 of file reduce_pcsimple.c.

References GRAPH::cost, EDGE_BLOCKED, FARAWAY, graph_pc_contractEdgeUnordered(), GRAPH::head, Is_term, GRAPH::mark, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisEQ(), SCIPisLE(), SCIPisLT(), GRAPH::source, STP_PCSPG, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.

Referenced by reduce_simple_pc().

◆ reduce_simple_mw()

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

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
nelims	pointer to number of reductions

Definition at line 1107 of file reduce_pcsimple.c.

References EAT_LAST, FALSE, GE, GRAPH::grad, graph_get_nNodes(), graph_mark(), graph_pc_deleteTerm(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsFixedTerm(), graph_pc_realDegree(), graph_valid(), hasAdjacentTerminals(), GRAPH::head, Is_pseudoTerm, Is_term, isMaxprizeTerm(), LE, GRAPH::mark, mwContract0WeightVertices(), mwContractNonPositiveChain(), mwContractTerminalsChainWise(), mwContractTerminalsSimple(), mwGetNchains(), mwReduceTermDeg1(), nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, pcmwEnumerationTry(), pcmwReduceKnotDeg1(), pcmwReduceTerm0Prize(), GRAPH::prize, reduce_unconnected(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisLE(), GRAPH::source, STP_MWCSP, STP_RMWCSP, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by redLoopInnerMw(), reduce_redLoopMw(), testRmwTerminalContraction(), testRmwTerminalDeg1Contraction1(), testRmwTerminalDeg1Contraction2(), and testRmwTerminalDeg1Contraction3().

◆ reduce_simple_pc()

SCIP_RETCODE reduce_simple_pc	(	SCIP *	scip,
		const int *	edgestate,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	countnew,
		int *	countall,
		int *	solnode
	)

basic reductions for RPCSTP and PCSPG

Parameters

scip	SCIP data structure
edgestate	for propagation or NULL
g	graph data structure
fixed	pointer to offset value
countnew	pointer to number of new reductions (will be initially set to 0)
countall	pointer to number of all reductions or NULL
solnode	solution nodes