Detailed Description

several node-separator based reductions for Steiner tree problems

Author: Daniel Rehfeldt

This file implements node-separator based reduction techniques for several Steiner problems. It contains rather simple test with articulation points, and more involved ones with terminal-separators.

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

Definition in file reduce_sepa.c.

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

Go to the source code of this file.

Data Structures
struct	cut_tree_data

Macros
#define	BIDECOMP_MINRED_MULTIPLIER 2

#define	BIDECOMP_MINMAXCOMPRATIO_FIRST 0.95

#define	BIDECOMP_MINMAXCOMPRATIO 0.80

#define	BIDECOMP_MINMAXCOMPRATIO_PARTIAL 0.99

#define	BIDECOMP_MAXCOMPRATIO_PARTIAL 0.05

#define	BIDECOMP_MAXCOMPRATIO_AGGRESSIVE 0.5

#define	BIDECOMP_MINNODES 10

#define	BIDECOMP_MINNODES_PARTIAL 10

Typedefs
typedef struct cut_tree_data	CUTTREE

Functions
static int	cutNodesGetLastCutnode (const CUTNODES *cutnodes)

static void	cutNodesTreeAddNode (int node, const CUTNODES cutnodes, int lastcutnode, CUTTREE cuttree)

static void	cutNodesTreeBuildSteinerTree (SCIP scip, const GRAPH g, const CUTNODES cutnodes, CUTTREE cuttree)

static void	cutNodesTreeDeleteComponents (SCIP scip, const CUTNODES cutnodes, const CUTTREE cuttree, GRAPH g, SCIP_Real fixedp, int nelims)

static SCIP_Bool	cutNodesTreeMakeTermsIsComplete (const CUTNODES cutnodes, const GRAPH g)

static void	cutNodesTreeMakeTerms (SCIP scip, const CUTNODES cutnodes, const CUTTREE cuttree, GRAPH g)

static SCIP_RETCODE	cutNodesTreeInit (SCIP scip, const GRAPH g, const CUTNODES cutnodes, CUTTREE cuttree)

static void	cutNodesTreeExit (SCIP scip, CUTTREE cuttree)

static SCIP_RETCODE	decomposeReduceSubDoIt (SCIP scip, const BIDECOMP bidecomp, int compindex, GRAPH graph, REDBASE redbase)

static SCIP_RETCODE	decomposeReduceSub (SCIP scip, const BIDECOMP bidecomp, int compindex, GRAPH g, REDBASE redbase)

static SCIP_RETCODE	decomposeExactFixSol (SCIP scip, const SUBINOUT subinout, SUBSTP substp, GRAPH orggraph, REDBASE redbase, int nelims)

static SCIP_RETCODE	decomposeExactSubDoIt (SCIP scip, const BIDECOMP bidecomp, GRAPH orggraph, GRAPH subgraph, REDBASE redbase, int nelims)

static SCIP_RETCODE	decomposeExactSubTry (SCIP scip, const BIDECOMP bidecomp, int compindex, GRAPH g, REDBASE redbase, int *nelims)

static SCIP_Bool	decomposeIsPromising (const GRAPH g, const BIDECPARAMS bidecompparams, const BIDECOMP *bidecomp)

static SCIP_Bool	decomposePartialIsPromising (const GRAPH g, const REDBASE redbase, const BIDECOMP *bidecomp)

static SCIP_RETCODE	decomposeReduce (SCIP scip, GRAPH g, BIDECOMP bidecomp, REDBASE redbase)

static SCIP_RETCODE	decomposePartialExact (SCIP scip, SCIP_Real maxcompratio, GRAPH g, BIDECOMP bidecomp, int solnode, REDBASE redbase, int nelims)

static SCIP_RETCODE	decomposeExec (SCIP scip, const CUTNODES cutnodes, GRAPH g, REDBASE redbase, int solnode, SCIP_Bool wasDecomposed)

static SCIP_RETCODE	decomposeExecExact (SCIP scip, const CUTNODES cutnodes, GRAPH g, REDBASE redbase, int solnode, int nelims)

SCIP_RETCODE	reduce_nonTerminalComponents (SCIP scip, const CUTNODES cutnodes, GRAPH g, SCIP_Real fixedp, int *nelims)

SCIP_RETCODE	reduce_bidecomposition (SCIP scip, GRAPH g, REDBASE redbase, int solnode, SCIP_Bool *wasDecomposed)

SCIP_RETCODE	reduce_bidecompositionExact (SCIP scip, GRAPH g, REDBASE redbase, int solnode, int *nelims)

SCIP_RETCODE	reduce_articulations (SCIP scip, GRAPH g, SCIP_Real fixedp, int nelims)

Macro Definition Documentation

◆ BIDECOMP_MINRED_MULTIPLIER

#define BIDECOMP_MINRED_MULTIPLIER 2

Definition at line 46 of file reduce_sepa.c.

Referenced by decomposeReduceSubDoIt().

◆ BIDECOMP_MINMAXCOMPRATIO_FIRST

#define BIDECOMP_MINMAXCOMPRATIO_FIRST 0.95

Definition at line 47 of file reduce_sepa.c.

Referenced by decomposeIsPromising().

◆ BIDECOMP_MINMAXCOMPRATIO

#define BIDECOMP_MINMAXCOMPRATIO 0.80

Definition at line 48 of file reduce_sepa.c.

Referenced by decomposeIsPromising().

◆ BIDECOMP_MINMAXCOMPRATIO_PARTIAL

#define BIDECOMP_MINMAXCOMPRATIO_PARTIAL 0.99

Definition at line 49 of file reduce_sepa.c.

Referenced by decomposePartialIsPromising().

◆ BIDECOMP_MAXCOMPRATIO_PARTIAL

#define BIDECOMP_MAXCOMPRATIO_PARTIAL 0.05

Definition at line 50 of file reduce_sepa.c.

Referenced by decomposeExec().

◆ BIDECOMP_MAXCOMPRATIO_AGGRESSIVE

#define BIDECOMP_MAXCOMPRATIO_AGGRESSIVE 0.5

Definition at line 51 of file reduce_sepa.c.

Referenced by decomposeExecExact().

◆ BIDECOMP_MINNODES

#define BIDECOMP_MINNODES 10

Definition at line 52 of file reduce_sepa.c.

Referenced by decomposeIsPromising().

◆ BIDECOMP_MINNODES_PARTIAL

#define BIDECOMP_MINNODES_PARTIAL 10

Definition at line 53 of file reduce_sepa.c.

Referenced by decomposePartialIsPromising().

Typedef Documentation

◆ CUTTREE

typedef struct cut_tree_data CUTTREE

Steiner tree based bi-connected component reduction

Function Documentation

◆ cutNodesGetLastCutnode()

static int cutNodesGetLastCutnode ( const CUTNODES * cutnodes )

inlinestatic

helper

Parameters

cutnodes cut nodes

Definition at line 75 of file reduce_sepa.c.

References cut_nodes::biconn_nodesmark, cut_nodes::dfsroot, EAT_LAST, FALSE, graph_get_nNodes(), graph_knot_printInfo(), GRAPH::head, Is_term, nnodes, cut_tree_data::nodes_isTree, cut_tree_data::nodes_prednode, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, STP_Vectype, StpVecFree, StpVecGetSize, StpVecPopBack, StpVecPushBack, StpVecReserve, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by cutNodesTreeBuildSteinerTree(), and cutNodesTreeDeleteComponents().

◆ cutNodesTreeAddNode()

static void cutNodesTreeAddNode	(	int	node,
		const CUTNODES *	cutnodes,
		int	lastcutnode,
		CUTTREE *	cuttree
	)

inlinestatic

helper

Parameters

node	node to add
cutnodes	cut nodes
lastcutnode	last cut node
cuttree	cut tree data

Definition at line 225 of file reduce_sepa.c.

References cut_nodes::biconn_comproots, cut_nodes::biconn_nodesmark, cut_tree_data::comps_isHit, cut_tree_data::cutnode0isNeeded, cut_tree_data::nodes_isTree, and TRUE.

Referenced by cutNodesTreeBuildSteinerTree().

◆ cutNodesTreeBuildSteinerTree()

static void cutNodesTreeBuildSteinerTree	(	SCIP *	scip,
		const GRAPH *	g,
		const CUTNODES *	cutnodes,
		CUTTREE *	cuttree
	)

static

builds Steiner tree

Parameters

scip	SCIP data structure
g	graph data structure
cutnodes	cut nodes
cuttree	cut tree data

Definition at line 252 of file reduce_sepa.c.

References cut_nodes::biconn_nodesmark, cut_tree_data::comps_isHit, cut_tree_data::cutnode0isNeeded, cutNodesGetLastCutnode(), cutNodesTreeAddNode(), cut_nodes::dfsroot, EAT_LAST, graph_get_nNodes(), graph_knot_isInRange(), graph_pc_isPcMw(), graph_pc_nNonLeafTerms(), graph_pc_termIsNonLeafTerm(), GRAPH::head, Is_term, GRAPH::mark, nnodes, cut_tree_data::nodes_isTree, cut_tree_data::nodes_prednode, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, STP_Vectype, StpVecFree, StpVecGetSize, StpVecPopBack, StpVecPushBack, StpVecReserve, GRAPH::term, and GRAPH::terms.

Referenced by reduce_nonTerminalComponents().

◆ cutNodesTreeDeleteComponents()

static void cutNodesTreeDeleteComponents	(	SCIP *	scip,
		const CUTNODES *	cutnodes,
		const CUTTREE *	cuttree,
		GRAPH *	g,
		SCIP_Real *	fixedp,
		int *	nelims
	)

static

deletes unvisited components

Parameters

scip	SCIP data structure
cutnodes	cut nodes
cuttree	cut tree data
g	graph
fixedp	pointer to offset value
nelims	pointer to number of reductions

Definition at line 323 of file reduce_sepa.c.

References cut_nodes::biconn_nodesmark, cut_tree_data::comps_isHit, cutNodesGetLastCutnode(), graph_get_nNodes(), graph_knot_del(), graph_knot_printInfo(), graph_pc_deleteTerm(), graph_pc_isPcMw(), graph_pc_termIsNonLeafTerm(), Is_term, GRAPH::mark, nnodes, cut_tree_data::nodes_isTree, SCIP_Bool, SCIPdebugMessage, GRAPH::term, and TRUE.

Referenced by reduce_nonTerminalComponents().

◆ cutNodesTreeMakeTermsIsComplete()

static SCIP_Bool cutNodesTreeMakeTermsIsComplete	(	const CUTNODES *	cutnodes,
		const GRAPH *	g
	)

static

debug checker: makes sure that all remaining proper cut nodes are terminals

Parameters

cutnodes	cut nodes
g	graph

Definition at line 376 of file reduce_sepa.c.

References cut_nodes::biconn_comproots, cut_nodes::biconn_ncomps, cut_nodes::biconn_nodesmark, EAT_LAST, FALSE, GRAPH::grad, graph_get_nNodes(), graph_knot_isInRange(), graph_knot_printInfo(), GRAPH::head, Is_term, GRAPH::mark, nnodes, GRAPH::oeat, GRAPH::outbeg, GRAPH::term, and TRUE.

Referenced by cutNodesTreeMakeTerms().

◆ cutNodesTreeMakeTerms()

static void cutNodesTreeMakeTerms	(	SCIP *	scip,
		const CUTNODES *	cutnodes,
		const CUTTREE *	cuttree,
		GRAPH *	g
	)

static

changes required cut-nodes from non-terminals to terminals

Parameters

scip	SCIP data structure
cutnodes	cut nodes
cuttree	cut tree data
g	graph

Definition at line 445 of file reduce_sepa.c.

References cut_nodes::biconn_comproots, cut_nodes::biconn_nodesmark, cut_tree_data::cutnode0isNeeded, cutNodesTreeMakeTermsIsComplete(), EAT_LAST, FALSE, GRAPH::grad, graph_knot_chg(), graph_knot_isInRange(), graph_knot_printInfo(), GRAPH::head, Is_term, cut_tree_data::nodes_isTree, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIPdebugMessage, STP_TERM, StpVecGetSize, GRAPH::term, and TRUE.

Referenced by reduce_nonTerminalComponents().

◆ cutNodesTreeInit()

static SCIP_RETCODE cutNodesTreeInit	(	SCIP *	scip,
		const GRAPH *	g,
		const CUTNODES *	cutnodes,
		CUTTREE *	cuttree
	)

static

initializes

Parameters

scip	SCIP data structure
g	graph data structure
cutnodes	cut nodes
cuttree	cut tree data

Definition at line 517 of file reduce_sepa.c.

References cut_nodes::biconn_ncomps, cut_tree_data::comps_isHit, FALSE, graph_get_nNodes(), nnodes, cut_tree_data::nodes_isTree, cut_tree_data::nodes_prednode, SCIP_Bool, SCIP_CALL, SCIP_OKAY, and SCIPallocBufferArray.

Referenced by reduce_nonTerminalComponents().

◆ cutNodesTreeExit()

static void cutNodesTreeExit	(	SCIP *	scip,
		CUTTREE *	cuttree
	)

static

exits

Parameters

scip	SCIP data structure
cuttree	cut tree data

Definition at line 554 of file reduce_sepa.c.

References cut_tree_data::comps_isHit, cut_tree_data::nodes_isTree, cut_tree_data::nodes_prednode, and SCIPfreeBuffer.

Referenced by reduce_nonTerminalComponents().

◆ decomposeReduceSubDoIt()

static SCIP_RETCODE decomposeReduceSubDoIt	(	SCIP *	scip,
		const BIDECOMP *	bidecomp,
		int	compindex,
		GRAPH *	graph,
		REDBASE *	redbase
	)

static

helper that extracts, reduces, re-inserts

Parameters

scip	SCIP data structure
bidecomp	all-components storage
compindex	component index
graph	graph data structure
redbase	reduction stuff

Definition at line 567 of file reduce_sepa.c.

References BIDECOMP_MINRED_MULTIPLIER, reduction_base::bidecompparams, GE, graph_printInfoReduced(), graph_subgraphExtract(), graph_subgraphReinsert(), graph_subinoutGetOrgToSubNodeMap(), graph_subinoutGetSubToOrgNodeMap(), graph_valid(), bidecomposition_reduction_parameters::newLevelStarted, reduction_base::redparameters, reduction_base::redsol, reduce_getMinNreductions(), reduce_redLoopStp(), reduce_solGetOffset(), reduce_solLevelTopClean(), reduce_solLevelTopTransferSolBack(), reduce_solLevelTopTransferSolTo(), reduce_solLevelTopUpdate(), reduce_solSetOffset(), reduction_parameters::reductbound, reduction_parameters::reductbound_min, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, biconnected_component_decomposition::subinout, and TRUE.

Referenced by decomposeReduceSub().

◆ decomposeReduceSub()

static SCIP_RETCODE decomposeReduceSub	(	SCIP *	scip,
		const BIDECOMP *	bidecomp,
		int	compindex,
		GRAPH *	g,
		REDBASE *	redbase
	)

static

reduces subproblem

Parameters

scip	SCIP data structure
bidecomp	all-components storage
compindex	component index
g	graph data structure
redbase	reduction stuff

Definition at line 627 of file reduce_sepa.c.

References bidecomposition_componentIsTrivial(), bidecomposition_markSub(), reduction_base::bidecompparams, decomposeReduceSubDoIt(), bidecomposition_reduction_parameters::depth, SCIP_CALL, SCIP_OKAY, and SCIPdebugMessage.

Referenced by decomposeReduce().

◆ decomposeExactFixSol()

static SCIP_RETCODE decomposeExactFixSol	(	SCIP *	scip,
		const SUBINOUT *	subinout,
		SUBSTP *	substp,
		GRAPH *	orggraph,
		REDBASE *	redbase,
		int *	nelims
	)

static

fixes original edges

Parameters

scip	SCIP data structure
subinout	helper for problem mapping
substp	sub-problem
orggraph	original graph
redbase	reduction stuff
nelims	number of eliminations or NULL

Definition at line 654 of file reduce_sepa.c.

References CONNECT, GRAPH::cost, flipedge, graph_edge_del(), graph_edge_isInRange(), graph_knot_chg(), graph_subinoutGetSubToOrgEdgeMap(), GRAPH::head, reduction_base::redsol, reduce_solGetOffsetPointer(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, STP_TERM, substpsolver_getNsubedges(), substpsolver_getSolution(), GRAPH::tail, TRUE, and UNKNOWN.

Referenced by decomposeExactSubDoIt().

◆ decomposeExactSubDoIt()

static SCIP_RETCODE decomposeExactSubDoIt	(	SCIP *	scip,
		const BIDECOMP *	bidecomp,
		GRAPH *	orggraph,
		GRAPH *	subgraph,
		REDBASE *	redbase,
		int *	nelims
	)

static

solves subproblems

Parameters

scip	SCIP data structure
bidecomp	all-components storage
orggraph	graph data structure
subgraph	sub-graph
redbase	reduction stuff
nelims	number of eliminations or NULL

Definition at line 712 of file reduce_sepa.c.

References decomposeExactFixSol(), graph_printInfo(), graph_subinoutClean(), graph_subinoutGetSubToOrgEdgeMap(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, biconnected_component_decomposition::subinout, substpsolver_free(), substpsolver_init(), substpsolver_setMute(), substpsolver_setProbFullPresolve(), substpsolver_solve(), and substpsolver_transferHistory().

Referenced by decomposeExactSubTry().

◆ decomposeExactSubTry()

static SCIP_RETCODE decomposeExactSubTry	(	SCIP *	scip,
		const BIDECOMP *	bidecomp,
		int	compindex,
		GRAPH *	g,
		REDBASE *	redbase,
		int *	nelims
	)

static

tries to solve subproblem

Parameters

scip	SCIP data structure
bidecomp	all-components storage
compindex	component index
g	graph data structure
redbase	reduction stuff
nelims	number of eliminations or NULL

Definition at line 754 of file reduce_sepa.c.

References bidecomposition_componentIsTrivial(), bidecomposition_getMarkedSubRoot(), bidecomposition_markSub(), reduction_base::bidecompparams, decomposeExactSubDoIt(), bidecomposition_reduction_parameters::depth, graph_knot_printInfo(), graph_subgraphExtract(), SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, GRAPH::source, and biconnected_component_decomposition::subinout.

Referenced by decomposePartialExact().

◆ decomposeIsPromising()

static SCIP_Bool decomposeIsPromising	(	const GRAPH *	g,
		const BIDECPARAMS *	bidecompparams,
		const BIDECOMP *	bidecomp
	)

static

is promising?

Parameters

g	graph data structure
bidecompparams	bidecomposition parameters
bidecomp	bidecomposition data structure

Definition at line 801 of file reduce_sepa.c.

References BIDECOMP_MINMAXCOMPRATIO, BIDECOMP_MINMAXCOMPRATIO_FIRST, BIDECOMP_MINNODES, bidecomposition_getMaxcompNodeRatio(), bidecomposition_reduction_parameters::depth, FALSE, GT, GRAPH::knots, and SCIP_Real.

Referenced by decomposeExec().

◆ decomposePartialIsPromising()

static SCIP_Bool decomposePartialIsPromising	(	const GRAPH *	g,
		const REDBASE *	redbase,
		const BIDECOMP *	bidecomp
	)

static

is decomposition with (exact) solution of small components promising?

Parameters

g	graph data structure
redbase	reduction stuff
bidecomp	bidecomposition data structure

Definition at line 821 of file reduce_sepa.c.

References BIDECOMP_MINMAXCOMPRATIO_PARTIAL, BIDECOMP_MINNODES_PARTIAL, bidecomposition_getMaxcompNodeRatio(), FALSE, GT, GRAPH::knots, reduction_base::redparameters, SCIP_Real, and reduction_parameters::userec.

Referenced by decomposeExec(), and decomposeExecExact().

◆ decomposeReduce()

static SCIP_RETCODE decomposeReduce	(	SCIP *	scip,
		GRAPH *	g,
		BIDECOMP *	bidecomp,
		REDBASE *	redbase
	)

static

reduced biconnected components separately

Parameters

scip	SCIP data structure
g	graph data structure
bidecomp	bidecomposition data structure
redbase	reduction stuff

Definition at line 845 of file reduce_sepa.c.

References bidecomposition_initSubInOut(), reduction_base::bidecompparams, decomposeReduceSub(), bidecomposition_reduction_parameters::depth, biconnected_component_decomposition::nbicomps, reduction_base::redsol, reduce_solLevelAdd(), reduce_solLevelTopFinalize(), SCIP_CALL, and SCIP_OKAY.

Referenced by decomposeExec().

◆ decomposePartialExact()

static SCIP_RETCODE decomposePartialExact	(	SCIP *	scip,
		SCIP_Real	maxcompratio,
		GRAPH *	g,
		BIDECOMP *	bidecomp,
		int *	solnode,
		REDBASE *	redbase,
		int *	nelims
	)

static

solves smaller biconnected components to optimality

Parameters

scip	SCIP data structure
maxcompratio	max nodes ratio
g	graph data structure
bidecomp	bi-decomposition
solnode	solution nodes or NULL
redbase	reduction stuff
nelims	number of eliminations or NULL

Definition at line 874 of file reduce_sepa.c.

References bidecomposition_getCompNodeRatio(), bidecomposition_initSubInOut(), reduction_base::bidecompparams, decomposeExactSubTry(), bidecomposition_reduction_parameters::depth, graph_subinoutActivateEdgeMap(), graph_subinoutActivateNewHistory(), biconnected_component_decomposition::nbicomps, reduce_contract0Edges(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, biconnected_component_decomposition::subinout, and TRUE.

Referenced by decomposeExec(), and decomposeExecExact().

◆ decomposeExec()

static SCIP_RETCODE decomposeExec	(	SCIP *	scip,
		const CUTNODES *	cutnodes,
		GRAPH *	g,
		REDBASE *	redbase,
		int *	solnode,
		SCIP_Bool *	wasDecomposed
	)

static

tries to solve or reduce biconnected components separately

Parameters

scip	SCIP data structure
cutnodes	cut nodes
g	graph data structure
redbase	reduction stuff
solnode	solution nodes or NULL
wasDecomposed	performed recursive reduction?

Definition at line 927 of file reduce_sepa.c.

References BIDECOMP_MAXCOMPRATIO_PARTIAL, bidecomposition_free(), bidecomposition_init(), reduction_base::bidecompparams, decomposeIsPromising(), decomposePartialExact(), decomposePartialIsPromising(), decomposeReduce(), bidecomposition_reduction_parameters::depth, FALSE, graph_valid(), bidecomposition_reduction_parameters::maxdepth, NULL, SCIP_CALL, SCIP_OKAY, reduction_base::solnode, and TRUE.

Referenced by reduce_bidecomposition().

◆ decomposeExecExact()

static SCIP_RETCODE decomposeExecExact	(	SCIP *	scip,
		const CUTNODES *	cutnodes,
		GRAPH *	g,
		REDBASE *	redbase,
		int *	solnode,
		int *	nelims
	)

static

solves (not too large) biconnected component separately

Parameters

scip	SCIP data structure
cutnodes	cut nodes
g	graph data structure
redbase	reduction stuff
solnode	solution nodes or NULL
nelims	number of eliminations

Definition at line 967 of file reduce_sepa.c.

References BIDECOMP_MAXCOMPRATIO_AGGRESSIVE, bidecomposition_free(), bidecomposition_init(), reduction_base::bidecompparams, decomposePartialExact(), decomposePartialIsPromising(), graph_valid(), NULL, SCIP_CALL, SCIP_OKAY, and reduction_base::solnode.

Referenced by reduce_bidecompositionExact().

◆ reduce_nonTerminalComponents()

SCIP_RETCODE reduce_nonTerminalComponents	(	SCIP *	scip,
		const CUTNODES *	cutnodes,
		GRAPH *	g,
		SCIP_Real *	fixedp,
		int *	nelims
	)

removes non-necessary bi-connected components and creates new terminals from cut-nodes

Parameters

scip	SCIP data structure
cutnodes	cut nodes
g	graph data structure
fixedp	pointer to offset value
nelims	pointer to number of reductions

Definition at line 1004 of file reduce_sepa.c.

References cutNodesTreeBuildSteinerTree(), cutNodesTreeDeleteComponents(), cutNodesTreeExit(), cutNodesTreeInit(), cutNodesTreeMakeTerms(), FALSE, graph_pc_isPcMw(), NULL, SCIP_CALL, SCIP_OKAY, and StpVecGetSize.

Referenced by reduce_articulations(), reduce_bidecomposition(), and reduce_bidecompositionExact().

◆ reduce_bidecomposition()

SCIP_RETCODE reduce_bidecomposition	(	SCIP *	scip,
		GRAPH *	g,
		REDBASE *	redbase,
		int *	solnode,
		SCIP_Bool *	wasDecomposed
	)

decomposition into biconnected components and recursive reduction

Parameters

scip	SCIP data structure
g	graph data structure
redbase	reduction base
solnode	solution nodes or NULL
wasDecomposed	performed recursive reduction?

Definition at line 1039 of file reduce_sepa.c.

References cut_nodes::biconn_ncomps, bidecomposition_cutnodesCompute(), bidecomposition_cutnodesFree(), bidecomposition_cutnodesInit(), bidecomposition_isPossible(), decomposeExec(), FALSE, graph_mark(), graph_typeIsSpgLike(), reduction_base::redsol, reduce_nonTerminalComponents(), reduce_solGetOffsetPointer(), SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, and GRAPH::terms.

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

◆ reduce_bidecompositionExact()

SCIP_RETCODE reduce_bidecompositionExact	(	SCIP *	scip,
		GRAPH *	g,
		REDBASE *	redbase,
		int *	solnode,
		int *	nelims
	)

solves smaller connected components to optimality

Parameters

scip	SCIP data structure
g	graph data structure
redbase	reduction base
solnode	solution nodes or NULL
nelims	number of eliminations

Definition at line 1085 of file reduce_sepa.c.

References cut_nodes::biconn_ncomps, bidecomposition_cutnodesCompute(), bidecomposition_cutnodesFree(), bidecomposition_cutnodesInit(), bidecomposition_isPossible(), decomposeExecExact(), graph_mark(), graph_typeIsSpgLike(), reduction_base::redsol, reduce_nonTerminalComponents(), reduce_solGetOffsetPointer(), SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, and GRAPH::terms.

Referenced by reduce_termsepaFull().

◆ reduce_articulations()

SCIP_RETCODE reduce_articulations	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixedp,
		int *	nelims
	)

articulation points based, simple reduction

Parameters

scip	SCIP data structure
g	graph data structure
fixedp	pointer to offset value
nelims	pointer to number of reductions

Definition at line 1130 of file reduce_sepa.c.

References cut_nodes::biconn_ncomps, bidecomposition_cutnodesCompute(), bidecomposition_cutnodesFree(), bidecomposition_cutnodesInit(), bidecomposition_isPossible(), graph_mark(), reduce_nonTerminalComponents(), SCIP_CALL, SCIP_OKAY, and SCIPdebugMessage.

Referenced by reduce_exec(), testBiconnectedComponentsAreFound(), testBiconnectedComponentsAreFound2(), and testBiconnectedComponentsAreFound3().

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ BIDECOMP_MINRED_MULTIPLIER

◆ BIDECOMP_MINMAXCOMPRATIO_FIRST

◆ BIDECOMP_MINMAXCOMPRATIO

◆ BIDECOMP_MINMAXCOMPRATIO_PARTIAL

◆ BIDECOMP_MAXCOMPRATIO_PARTIAL

◆ BIDECOMP_MAXCOMPRATIO_AGGRESSIVE

◆ BIDECOMP_MINNODES

◆ BIDECOMP_MINNODES_PARTIAL

Typedef Documentation

◆ CUTTREE

Function Documentation

◆ cutNodesGetLastCutnode()

◆ cutNodesTreeAddNode()

◆ cutNodesTreeBuildSteinerTree()

◆ cutNodesTreeDeleteComponents()

◆ cutNodesTreeMakeTermsIsComplete()

◆ cutNodesTreeMakeTerms()

◆ cutNodesTreeInit()

◆ cutNodesTreeExit()

◆ decomposeReduceSubDoIt()

◆ decomposeReduceSub()

◆ decomposeExactFixSol()

◆ decomposeExactSubDoIt()

◆ decomposeExactSubTry()

◆ decomposeIsPromising()

◆ decomposePartialIsPromising()

◆ decomposeReduce()

◆ decomposePartialExact()

◆ decomposeExec()

◆ decomposeExecExact()

◆ reduce_nonTerminalComponents()

◆ reduce_bidecomposition()

◆ reduce_bidecompositionExact()

◆ reduce_articulations()