dpborder_base.c File Reference

Detailed Description

Dynamic programming solver for Steiner tree (sub-) problems with small border.

Author

Daniel Rehfeldt

Definition in file dpborder_base.c.

#include "dpborder.h"
#include "dpborderinterns.h"
#include "stpvector.h"
#include "solstp.h"

Go to the source code of this file.

Macros
#define	DPB_MINTERMRATIO   0.4
#define	DPB_MAXNNODES   1000
#define	DPB_MINNNODES   100
#define	DPB_MAXAVGDEG   4.5

Functions
static SCIP_Bool	dpborderIsNonPromising (const GRAPH *graph)
static SCIP_RETCODE	dpborderInitHelper (SCIP *scip, GRAPH *graph, DPBORDER *dpborder)
SCIP_RETCODE	dpborder_dpbsequenceInit (SCIP *scip, const GRAPH *graph, DPBSEQUENCE **dpbsequence)
void	dpborder_dpbsequenceCopy (const DPBSEQUENCE *dpbsequence_source, DPBSEQUENCE *dpbsequence_target)
void	dpborder_dpbsequenceFree (SCIP *scip, DPBSEQUENCE **dpbsequence)
SCIP_RETCODE	dpborder_dpblevelInit (SCIP *scip, DPBLEVEL **dpblevel)
void	dpborder_dpblevelFree (SCIP *scip, DPBLEVEL **dpblevel)
SCIP_RETCODE	dpborder_probePotential (SCIP *scip, GRAPH *graph, DPBORDER *dpborder, SCIP_Bool *hasPotential)
SCIP_RETCODE	dpborder_solve (SCIP *scip, GRAPH *graph, DPBORDER *dpborder, int *solution, SCIP_Bool *wasSolved)
SCIP_RETCODE	dpborder_init (SCIP *scip, const GRAPH *graph, DPBORDER **dpborder)
void	dpborder_free (SCIP *scip, DPBORDER **dpborder)

Macro Definition Documentation

DPB_MINTERMRATIO

#define DPB_MINTERMRATIO   0.4

Definition at line 29 of file dpborder_base.c.

Referenced by dpborderIsNonPromising().

DPB_MAXNNODES

#define DPB_MAXNNODES   1000

Definition at line 30 of file dpborder_base.c.

Referenced by dpborderIsNonPromising().

DPB_MINNNODES

#define DPB_MINNNODES   100

Definition at line 31 of file dpborder_base.c.

Referenced by dpborderIsNonPromising().

DPB_MAXAVGDEG

#define DPB_MAXAVGDEG   4.5

Definition at line 32 of file dpborder_base.c.

Referenced by dpborderIsNonPromising().

Function Documentation

dpborderIsNonPromising()

static SCIP_Bool dpborderIsNonPromising ( const GRAPH *  graph )

static

non-promising? quick check

Parameters

graph

original graph

Definition at line 43 of file dpborder_base.c.

References DPB_MAXAVGDEG, DPB_MAXNNODES, DPB_MINNNODES, DPB_MINTERMRATIO, GRAPH::edges, FALSE, GRAPH::knots, SCIP_Real, GRAPH::terms, and TRUE.

Referenced by dpborder_probePotential().

dpborderInitHelper()

static SCIP_RETCODE dpborderInitHelper ( SCIP *  scip, GRAPH *  graph, DPBORDER *  dpborder  )

static

initializes helper

Parameters

scip	SCIP data structure
graph	graph of sub-problem
dpborder	border

Definition at line 65 of file dpborder_base.c.

References BMScopyMemoryArray, dynamic_programming_border::borderchardists, dynamic_programming_border::bordercharmap, BPBORDER_MAXBORDERSIZE, dpborder_dpbsequenceInit(), dynamic_programming_border::dpbsequence, GRAPH::grad, graph_get_nNodes(), nnodes, dynamic_programming_border::nnodes, dynamic_programming_border::nodes_isBorder, dynamic_programming_border::nodes_outdeg, SCIP_CALL, SCIP_OKAY, SCIPallocClearMemoryArray, and SCIPallocMemoryArray.

Referenced by dpborder_probePotential().

dpborder_dpbsequenceInit()

SCIP_RETCODE dpborder_dpbsequenceInit	(	SCIP *	scip,
		const GRAPH *	graph,
		DPBSEQUENCE **	dpbsequence
	)

initializes

Parameters

scip	SCIP data structure
graph	original graph
dpbsequence	to initialize

Definition at line 97 of file dpborder_base.c.

References dynamic_programming_border::dpbsequence, graph_get_nNodes(), dynamic_programming_border_nodes_sequence::maxbordersize, dynamic_programming_border_nodes_sequence::maxnpartitions, dynamic_programming_border_nodes_sequence::nnodes, nnodes, dynamic_programming_border_nodes_sequence::nodessquence, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, and SCIPallocMemoryArray.

Referenced by dpborder_coreUpdateOrdering(), dpborder_getPredLevel(), and dpborderInitHelper().

dpborder_dpbsequenceCopy()

void dpborder_dpbsequenceCopy	(	const DPBSEQUENCE *	dpbsequence_source,
		DPBSEQUENCE *	dpbsequence_target
	)

copies

Parameters

dpbsequence_source	to copy
dpbsequence_target	to copy to

Definition at line 119 of file dpborder_base.c.

References BMScopyMemoryArray, dynamic_programming_border_nodes_sequence::maxbordersize, dynamic_programming_border_nodes_sequence::maxnpartitions, dynamic_programming_border_nodes_sequence::nnodes, nnodes, and dynamic_programming_border_nodes_sequence::nodessquence.

Referenced by dpborder_coreUpdateOrdering(), and dpborder_getPredLevel().

dpborder_dpbsequenceFree()

void dpborder_dpbsequenceFree	(	SCIP *	scip,
		DPBSEQUENCE **	dpbsequence
	)

frees

Parameters

scip	SCIP data structure
dpbsequence	to free

Definition at line 134 of file dpborder_base.c.

References dynamic_programming_border::dpbsequence, dynamic_programming_border_nodes_sequence::nodessquence, SCIPfreeMemory, and SCIPfreeMemoryArray.

Referenced by dpborder_coreUpdateOrdering(), dpborder_free(), and dpborder_getPredLevel().

dpborder_dpblevelInit()

SCIP_RETCODE dpborder_dpblevelInit	(	SCIP *	scip,
		DPBLEVEL **	dpblevel
	)

initializes

Parameters

scip	SCIP data structure
dpblevel	to initialize

Definition at line 149 of file dpborder_base.c.

References dynamic_programming_border_level::exnodeIsTerm, dynamic_programming_border_level::extnode, FALSE, dynamic_programming_border_level::globalstartidx, dynamic_programming_border_level::nbordernodes, NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocMemory.

Referenced by addLevel(), addLevelFirst(), and dpborder_getPredLevel().

dpborder_dpblevelFree()

void dpborder_dpblevelFree	(	SCIP *	scip,
		DPBLEVEL **	dpblevel
	)

frees

Parameters

scip	SCIP data structure
dpblevel	to be freed

Definition at line 170 of file dpborder_base.c.

References SCIPfreeMemory, and StpVecFree.

Referenced by dpborder_free(), and dpborder_getPredLevel().

dpborder_probePotential()

SCIP_RETCODE dpborder_probePotential	(	SCIP *	scip,
		GRAPH *	graph,
		DPBORDER *	dpborder,
		SCIP_Bool *	hasPotential
	)

checks whether DP border has potential NOTE: needs to be called before dpborder_solve!

Parameters

scip	SCIP data structure
graph	graph of sub-problem
dpborder	border
hasPotential	was problem solved to optimality?

Definition at line 186 of file dpborder_base.c.

References BPBORDER_MAXBORDERSIZE, BPBORDER_MAXNPARTITIONS, dpborder_coreComputeOrderingSimple(), dpborderInitHelper(), dpborderIsNonPromising(), dynamic_programming_border::dpbsequence, FALSE, graph_free_csr(), graph_init_csrWithEdgeId(), dynamic_programming_border_nodes_sequence::maxbordersize, dynamic_programming_border_nodes_sequence::maxnpartitions, SCIP_CALL, SCIP_OKAY, and TRUE.

Referenced by SCIPStpDpRelaxIsPromising().

dpborder_solve()

SCIP_RETCODE dpborder_solve	(	SCIP *	scip,
		GRAPH *	graph,
		DPBORDER *	dpborder,
		int *	solution,
		SCIP_Bool *	wasSolved
	)

solves problem given by graph

Parameters

scip	SCIP data structure
graph	graph of sub-problem
dpborder	border
solution	optimal solution (out)
wasSolved	was problem solved to optimality?

Definition at line 230 of file dpborder_base.c.

References dpborder_coreSolve(), dpborder_coreUpdateOrdering(), DPBORDER_GROWTH_FACTOR, dpborder_markSolNodes(), dynamic_programming_border::dpbsequence, EQ, dynamic_programming_border::global_obj, graph_free_csr(), graph_init_csr(), dynamic_programming_border::hashmap, hashmap_create(), GRAPH::knots, dynamic_programming_border_nodes_sequence::maxnpartitions, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, solstp_getObj(), solstp_isValid(), and solstp_pruneFromNodes().

Referenced by solveWithDpBorder().

dpborder_init()

SCIP_RETCODE dpborder_init	(	SCIP *	scip,
		const GRAPH *	graph,
		DPBORDER **	dpborder
	)

initializes

Parameters

scip	SCIP data structure
graph	original graph
dpborder	to initialize

Definition at line 278 of file dpborder_base.c.

References dynamic_programming_border::borderchardists, dynamic_programming_border::bordercharmap, dynamic_programming_border::dpbsequence, hashmap_s::elements, FARAWAY, dynamic_programming_border::global_npartitions, dynamic_programming_border::global_obj, dynamic_programming_border::global_optposition, dynamic_programming_border::global_partcap, dynamic_programming_border::global_partitions, dynamic_programming_border::hashmap, GRAPH::knots, dynamic_programming_border::nnodes, dynamic_programming_border::nodes_isBorder, dynamic_programming_border::nodes_outdeg, dynamic_programming_border::nterms, dynamic_programming_border::ntermsvisited, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, and GRAPH::terms.

Referenced by SCIPStpDpRelaxIsPromising().

dpborder_free()

void dpborder_free	(	SCIP *	scip,
		DPBORDER **	dpborder
	)

frees

Parameters

scip	SCIP data structure
dpborder	to be freed

Definition at line 317 of file dpborder_base.c.

References dynamic_programming_border::borderchardists, dynamic_programming_border::bordercharmap, dpborder_dpblevelFree(), dpborder_dpbsequenceFree(), dynamic_programming_border::dpbsequence, hashmap_s::elements, dynamic_programming_border::global_partitions, dynamic_programming_border::hashmap, hashmap_destroy(), dynamic_programming_border::nodes_isBorder, dynamic_programming_border::nodes_outdeg, SCIPfreeMemory, SCIPfreeMemoryArrayNull, StpVecFree, and StpVecGetSize.

Referenced by SCIP_DECL_RELAXFREE().