Detailed Description

several terminal-separator/dual-ascent based reductions for Steiner tree problems

Author: Daniel Rehfeldt

This file implements terminal-separator based reduction techniques for several Steiner problems that use dual-ascent for reductions

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

Definition in file reduce_termsepada.c.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "graph.h"
#include "dualascent.h"
#include "reduce.h"
#include "extreduce.h"
#include "solstp.h"
#include "heur_local.h"
#include "mincut.h"
#include "heur_ascendprune.h"
#include "portab.h"
#include "stpvector.h"
#include "scip/scip.h"

Go to the source code of this file.

Macros
#define	COMPONENT_NODESRATIO_MIN 0.01

#define	COMPONENT_NODESRATIO_SMALL 0.1

#define	COMPONENT_NODESRATIO_MAX 0.5

#define	SEPARATOR_MAXSIZE 5

#define	SEPARATOR_MAXNCHECKS 75

#define	SEPARATOR_MAXSIZE_FAST 4

#define	SEPARATOR_MAXNCHECKS_FAST 40

#define	SEPARATOR_MINTERMRATIO 0.12

#define	SEPARATOR_MINTERMRATIO_FAST 0.005

Functions
static void	termcompDeleteEdges (SCIP scip, const REDCOST redcostdata, const TERMCOMP termcomp, GRAPH g, EXTPERMA extperma, int nelims)

static void	termcompMarkPseudoDelNodes (SCIP scip, const REDCOST redcostdata, const TERMCOMP termcomp, GRAPH g, EXTPERMA extperma, SCIP_Bool pseudoDelNodes)

static SCIP_RETCODE	termcompReduceWithParams (SCIP scip, DAPARAMS daparams, GRAPH g, EXTPERMA extperma, TERMCOMP termcomp, SCIP_Bool pseudoDelNodes, int *nelims)

static SCIP_RETCODE	termcompReduce (SCIP scip, GRAPH g, EXTPERMA extperma, TERMCOMP termcomp, SCIP_Bool pseudoDelNodes, int nelims)

static SCIP_RETCODE	termcompComputeSubgraphSol (SCIP scip, TERMCOMP termcomp)

static SCIP_Bool	termcompIsPromising (const GRAPH g, const COMPBUILDER builder)

static SCIP_RETCODE	processComponent (SCIP scip, COMPBUILDER builder, GRAPH g, EXTPERMA extperma, SCIP_Bool pseudoDelNodes, int nelims)

static SCIP_RETCODE	initHelpers (SCIP scip, const GRAPH g, const EXTPERMA extperma, COMPBUILDER builder, TERMSEPAS *termsepas)

static void	freeHelpers (SCIP scip, COMPBUILDER builder, TERMSEPAS *termsepas)

SCIP_RETCODE	reduce_termsepaDaWithExperma (SCIP scip, GRAPH g, EXTPERMA extperma, SCIP_Bool pseudoDelNodes, int *nelims)

SCIP_RETCODE	reduce_termsepaDa (SCIP scip, GRAPH g, int *nelims)

Macro Definition Documentation

◆ COMPONENT_NODESRATIO_MIN

#define COMPONENT_NODESRATIO_MIN 0.01

Definition at line 48 of file reduce_termsepada.c.

◆ COMPONENT_NODESRATIO_SMALL

#define COMPONENT_NODESRATIO_SMALL 0.1

Definition at line 49 of file reduce_termsepada.c.

Referenced by termcompComputeSubgraphSol(), and termcompReduce().

◆ COMPONENT_NODESRATIO_MAX

#define COMPONENT_NODESRATIO_MAX 0.5

Definition at line 50 of file reduce_termsepada.c.

Referenced by termcompIsPromising().

◆ SEPARATOR_MAXSIZE

#define SEPARATOR_MAXSIZE 5

Definition at line 52 of file reduce_termsepada.c.

Referenced by initHelpers().

◆ SEPARATOR_MAXNCHECKS

#define SEPARATOR_MAXNCHECKS 75

Definition at line 53 of file reduce_termsepada.c.

Referenced by initHelpers().

◆ SEPARATOR_MAXSIZE_FAST

#define SEPARATOR_MAXSIZE_FAST 4

Definition at line 54 of file reduce_termsepada.c.

Referenced by initHelpers().

◆ SEPARATOR_MAXNCHECKS_FAST

#define SEPARATOR_MAXNCHECKS_FAST 40

Definition at line 55 of file reduce_termsepada.c.

Referenced by initHelpers().

◆ SEPARATOR_MINTERMRATIO

#define SEPARATOR_MINTERMRATIO 0.12

Definition at line 56 of file reduce_termsepada.c.

Referenced by initHelpers().

◆ SEPARATOR_MINTERMRATIO_FAST

#define SEPARATOR_MINTERMRATIO_FAST 0.005

Definition at line 57 of file reduce_termsepada.c.

Referenced by initHelpers().

Function Documentation

◆ termcompDeleteEdges()

static void termcompDeleteEdges	(	SCIP *	scip,
		const REDCOST *	redcostdata,
		const TERMCOMP *	termcomp,
		GRAPH *	g,
		EXTPERMA *	extperma,
		int *	nelims
	)

static

deletes

Parameters

scip	SCIP data structure
redcostdata	reduced costs
termcomp	component
g	graph data structure
extperma	extension data
nelims	number of eliminations

Definition at line 67 of file reduce_termsepada.c.

References CONNECT, shortest_path::dist, extension_data_permanent::distdata_default, EAT_LAST, terminal_separator_component::edgemap_subToOrg, extreduce_edgeRemove(), FALSE, flipedge, graph_edge_del(), graph_edge_isDeleted(), graph_edge_printInfo(), graph_get_nNodes(), graph_isMarked(), graph_valid(), GRAPH::head, GRAPH::oeat, GRAPH::outbeg, redcosts_getCutoffTop(), redcosts_getEdgeCostsTop(), redcosts_getNodeToTermsPathsTop(), redcosts_getRootToNodeDistTop(), extension_data_permanent::result, SCIP_Real, SCIPdebugMessage, SCIPisGT(), extension_data_permanent::solIsValid, and terminal_separator_component::subgraph.

Referenced by termcompReduceWithParams().

◆ termcompMarkPseudoDelNodes()

static void termcompMarkPseudoDelNodes	(	SCIP *	scip,
		const REDCOST *	redcostdata,
		const TERMCOMP *	termcomp,
		GRAPH *	g,
		EXTPERMA *	extperma,
		SCIP_Bool *	pseudoDelNodes
	)

static

marks nodes for pseudo-deletion

Parameters

scip	SCIP data structure
redcostdata	reduced costs
termcomp	component
g	graph data structure
extperma	extension data
pseudoDelNodes	array to mark pseudo deletable nodes

Definition at line 139 of file reduce_termsepada.c.

References shortest_path::dist, graph_get_nNodes(), graph_knot_isInRange(), graph_knot_printInfo(), Is_term, terminal_separator_component::nodemap_subToOrg, redcosts_getCutoffTop(), redcosts_getNodeToTermsPathsTop(), redcosts_getRootToNodeDistTop(), SCIP_Real, SCIPdebugMessage, SCIPisGT(), terminal_separator_component::subgraph, GRAPH::term, and TRUE.

Referenced by termcompReduceWithParams().

◆ termcompReduceWithParams()

static SCIP_RETCODE termcompReduceWithParams	(	SCIP *	scip,
		DAPARAMS *	daparams,
		GRAPH *	g,
		EXTPERMA *	extperma,
		TERMCOMP *	termcomp,
		SCIP_Bool *	pseudoDelNodes,
		int *	nelims
	)

static

perform reductions

Parameters

scip	SCIP data structure
daparams	dual-ascent parameters
g	graph data structure
extperma	extension data
termcomp	component
pseudoDelNodes	array to mark pseudo deletable nodes or NULL (OUT)
nelims	number of eliminations

Definition at line 179 of file reduce_termsepada.c.

References reduced_costs_parameters::cutoff, dualascent_exec(), GRAPH::edges, GE, graph_mark(), GRAPH::knots, NULL, redcosts_free(), redcosts_getEdgeCostsTop(), redcosts_initFromParams(), redcosts_initializeDistancesTop(), redcosts_setCutoffFromBoundTop(), redcosts_setDualBoundTop(), reduce_cost_parameters::root, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, terminal_separator_component::subgraph, terminal_separator_component::subprimalobj, termcompDeleteEdges(), and termcompMarkPseudoDelNodes().

Referenced by termcompReduce().

◆ termcompReduce()

static SCIP_RETCODE termcompReduce	(	SCIP *	scip,
		GRAPH *	g,
		EXTPERMA *	extperma,
		TERMCOMP *	termcomp,
		SCIP_Bool *	pseudoDelNodes,
		int *	nelims
	)

static

perform reductions

Parameters

scip	SCIP data structure
g	graph data structure
extperma	extension data
termcomp	component
pseudoDelNodes	array to mark pseudo deletable nodes or NULL (OUT)
nelims	number of eliminations

Definition at line 224 of file reduce_termsepada.c.

References reduce_cost_parameters::addcuts, terminal_separator_component::builder, COMPONENT_NODESRATIO_SMALL, FALSE, graph_knot_isInRange(), terminal_separator_component::nodemap_orgToSub, reduce_compbuilderGetSubNodesRatio(), reduce_cost_parameters::root, SCIP_CALL, SCIP_OKAY, terminial_component_initializer::sepaterms, GRAPH::source, terminal_separator_component::subgraph, and termcompReduceWithParams().

Referenced by processComponent().

◆ termcompComputeSubgraphSol()

static SCIP_RETCODE termcompComputeSubgraphSol	(	SCIP *	scip,
		TERMCOMP *	termcomp
	)

static

computes primal solution on subgraph

Parameters

scip	SCIP data structure
termcomp	component

Definition at line 257 of file reduce_termsepada.c.

References reduce_cost_parameters::addcuts, terminal_separator_component::builder, COMPONENT_NODESRATIO_SMALL, dualascent_exec(), FALSE, graph_get_nEdges(), terminal_separator_component::nodemap_orgToSub, NULL, reduce_compbuilderGetSubNodesRatio(), reduce_termcompInitTbottleneck(), reduce_cost_parameters::root, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), solstp_getObj(), terminial_component_initializer::sourceterm, terminal_separator_component::subgraph, terminal_separator_component::subprimalobj, subsol, and terminal_separator_component::subsolution.

Referenced by processComponent().

◆ termcompIsPromising()

static SCIP_Bool termcompIsPromising	(	const GRAPH *	g,
		const COMPBUILDER *	builder
	)

static

promising to perform reductions on given component?

Parameters

g	graph data structure
builder	terminal separator component initializer

Definition at line 309 of file reduce_termsepada.c.

References COMPONENT_NODESRATIO_MAX, terminial_component_initializer::componentnumber, GT, reduce_compbuilderGetSubNodesRatio(), SCIP_Real, SCIPdebugMessage, and TRUE.

Referenced by reduce_termsepaDaWithExperma().

◆ processComponent()

static SCIP_RETCODE processComponent	(	SCIP *	scip,
		COMPBUILDER *	builder,
		GRAPH *	g,
		EXTPERMA *	extperma,
		SCIP_Bool *	pseudoDelNodes,
		int *	nelims
	)

static

processes subgraph associated with SEPADA

Parameters

scip	SCIP data structure
builder	terminal separator component initializer
g	graph data structure
extperma	extension data
pseudoDelNodes	array to mark pseudo deletable nodes or NULL (OUT)
nelims	number of eliminations

Definition at line 345 of file reduce_termsepada.c.

References terminial_component_initializer::ncomponentnodes, reduce_termcompBuildSubgraphWithSds(), reduce_termcompChangeSubgraphToBottleneck(), reduce_termcompFree(), reduce_termcompInit(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, termcompComputeSubgraphSol(), and termcompReduce().

Referenced by reduce_termsepaDaWithExperma().

◆ initHelpers()

static SCIP_RETCODE initHelpers	(	SCIP *	scip,
		const GRAPH *	g,
		const EXTPERMA *	extperma,
		COMPBUILDER **	builder,
		TERMSEPAS **	termsepas
	)

static

initializes helpers

Parameters

scip	SCIP data structure
g	graph data structure
extperma	extension data
builder	to initialize
termsepas	to initialize

Definition at line 380 of file reduce_termsepada.c.

References extred_fast, mincut_termsepasInit(), extension_data_permanent::mode, reduce_compbuilderInit(), SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SEPARATOR_MAXNCHECKS, SEPARATOR_MAXNCHECKS_FAST, SEPARATOR_MAXSIZE, SEPARATOR_MAXSIZE_FAST, SEPARATOR_MINTERMRATIO, SEPARATOR_MINTERMRATIO_FAST, and GRAPH::terms.

Referenced by reduce_termsepaDaWithExperma().

◆ freeHelpers()

static void freeHelpers	(	SCIP *	scip,
		COMPBUILDER **	builder,
		TERMSEPAS **	termsepas
	)

static

frees helper

Parameters

scip	SCIP data structure
builder	to initialize
termsepas	to initialize

Definition at line 423 of file reduce_termsepada.c.

References mincut_termsepasFree(), and reduce_compbuilderFree().

Referenced by reduce_termsepaDaWithExperma().

◆ reduce_termsepaDaWithExperma()

SCIP_RETCODE reduce_termsepaDaWithExperma	(	SCIP *	scip,
		GRAPH *	g,
		EXTPERMA *	extperma,
		SCIP_Bool *	pseudoDelNodes,
		int *	nelims
	)

terminal-separator/dual-ascent reduction method given extperma todo maybe we want to also give terminal separators to be able to reuse them?

Parameters

scip	SCIP data structure
g	graph data structure
extperma	extension data
pseudoDelNodes	array to mark pseudo deletable nodes or NULL (OUT)
nelims	number of eliminations (OUT)

Definition at line 441 of file reduce_termsepada.c.

References BMSclearMemoryArray, terminial_component_initializer::componentnumber, freeHelpers(), initHelpers(), GRAPH::knots, mincut_findTerminalSeparators(), processComponent(), extension_data_permanent::randnumgen, reduce_termsepaGetNextComp(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, termcompIsPromising(), and GRAPH::terms.

Referenced by extreduce_deleteEdges(), and reduce_termsepaDa().

◆ reduce_termsepaDa()

SCIP_RETCODE reduce_termsepaDa	(	SCIP *	scip,
		GRAPH *	g,
		int *	nelims
	)

terminal-separator/dual-ascent reduction method NOTE: intended to be used for debugging and unit tests, since creation of SD data is expensive and is best combined with extended reduction techniques

Parameters

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

Definition at line 492 of file reduce_termsepada.c.

References extension_data_permanent::distdata_default, extred_fast, extreduce_distDataInit(), extreduce_exit(), extreduce_extPermaInit(), FALSE, graph_init_dcsr(), NULL, reduce_sdRepairSetUp(), reduce_termsepaDaWithExperma(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, distance_data::sdistdata, GRAPH::terms, and TRUE.

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ COMPONENT_NODESRATIO_MIN

◆ COMPONENT_NODESRATIO_SMALL

◆ COMPONENT_NODESRATIO_MAX

◆ SEPARATOR_MAXSIZE

◆ SEPARATOR_MAXNCHECKS

◆ SEPARATOR_MAXSIZE_FAST

◆ SEPARATOR_MAXNCHECKS_FAST

◆ SEPARATOR_MINTERMRATIO

◆ SEPARATOR_MINTERMRATIO_FAST

Function Documentation

◆ termcompDeleteEdges()

◆ termcompMarkPseudoDelNodes()

◆ termcompReduceWithParams()

◆ termcompReduce()

◆ termcompComputeSubgraphSol()

◆ termcompIsPromising()

◆ processComponent()

◆ initHelpers()

◆ freeHelpers()

◆ reduce_termsepaDaWithExperma()

◆ reduce_termsepaDa()