Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

Dynamic programming solver for Steiner tree (sub-) problems with small number of terminals.

Author: Daniel Rehfeldt

Definition in file dpterms_base.c.

#include "scip/scipdefplugins.h"
#include "scip/rbtree.h"
#include "dpterms.h"
#include "dptermsinterns.h"
#include "stpbitset.h"
#include "stpvector.h"
#include "stpprioqueue.h"
#include "solstp.h"

Go to the source code of this file.

Macros
#define	PROMISING_FULL_MAXNTERMS 20

#define	PROMISING_FULL_MAXNTERMS_LARGE 15

#define	PROMISING_PARTLY_MAXDENSITY 2.2

#define	PROMISING_PARTLY_SMALL_MAXNTERMS 45

#define	PROMISING_PARTLY_SMALL_MINNEDGES 1100

#define	PROMISING_PARTLY_MEDIUM_MAXNTERMS 55

#define	PROMISING_PARTLY_MEDIUM_MINNEDGES 1500

#define	PROMISING_PARTLY_LARGE_MAXNTERMS 65

#define	PROMISING_PARTLY_LARGE_MINNEDGES 3000

#define	PROMISING_FULL_LARGE_MINNEDGES 100000

#define	PROMISING_FULL_MAXAVGDEG 5.0

Functions
static SCIP_RETCODE	dpgraphInit (SCIP scip, const GRAPH graph, DPGRAPH **dpgraph)

static void	dpgraphFree (SCIP scip, DPGRAPH *dpgraph)

static SCIP_RETCODE	dpmiscInit (SCIP scip, const GRAPH graph, DPMISC **dpmisc)

static void	dpmiscFree (SCIP scip, DPMISC *dpmisc)

static SCIP_RETCODE	dpsolverInitData (SCIP scip, GRAPH graph, DPSOLVER *dpsolver)

static void	dpsolverFreeData (SCIP scip, DPSOLVER dpsolver)

static SCIP_RETCODE	dpsolverSolve (SCIP scip, GRAPH g, DPSOLVER dpsolver, SCIP_Bool wasSolved)

static SCIP_RETCODE	dpsolverGetSolution (SCIP scip, GRAPH graph, DPSOLVER dpsolver, int solution)

static SCIP_RETCODE	dpsolverInit (SCIP scip, GRAPH graph, DPSOLVER **dpsolver)

static void	dpsolverFree (SCIP scip, DPSOLVER *dpsolver)

SCIP_RETCODE	dpterms_solve (SCIP scip, GRAPH graph, int solution, SCIP_Bool wasSolved)

SCIP_Bool	dpterms_isPromisingPartly (const GRAPH *graph)

SCIP_Bool	dpterms_isPromisingEmbarrassingly (const GRAPH *graph)

SCIP_Bool	dpterms_isPromisingFully (const GRAPH *graph)

Macro Definition Documentation

◆ PROMISING_FULL_MAXNTERMS

#define PROMISING_FULL_MAXNTERMS 20

Definition at line 39 of file dpterms_base.c.

Referenced by dpterms_isPromisingFully().

◆ PROMISING_FULL_MAXNTERMS_LARGE

#define PROMISING_FULL_MAXNTERMS_LARGE 15

Definition at line 40 of file dpterms_base.c.

Referenced by dpterms_isPromisingFully().

◆ PROMISING_PARTLY_MAXDENSITY

#define PROMISING_PARTLY_MAXDENSITY 2.2

Definition at line 41 of file dpterms_base.c.

Referenced by dpterms_isPromisingPartly().

◆ PROMISING_PARTLY_SMALL_MAXNTERMS

#define PROMISING_PARTLY_SMALL_MAXNTERMS 45

Definition at line 42 of file dpterms_base.c.

Referenced by dpterms_isPromisingPartly().

◆ PROMISING_PARTLY_SMALL_MINNEDGES

#define PROMISING_PARTLY_SMALL_MINNEDGES 1100

Definition at line 43 of file dpterms_base.c.

Referenced by dpterms_isPromisingPartly().

◆ PROMISING_PARTLY_MEDIUM_MAXNTERMS

#define PROMISING_PARTLY_MEDIUM_MAXNTERMS 55

Definition at line 44 of file dpterms_base.c.

Referenced by dpterms_isPromisingPartly().

◆ PROMISING_PARTLY_MEDIUM_MINNEDGES

#define PROMISING_PARTLY_MEDIUM_MINNEDGES 1500

Definition at line 45 of file dpterms_base.c.

Referenced by dpterms_isPromisingPartly().

◆ PROMISING_PARTLY_LARGE_MAXNTERMS

#define PROMISING_PARTLY_LARGE_MAXNTERMS 65

Definition at line 46 of file dpterms_base.c.

Referenced by dpterms_isPromisingPartly().

◆ PROMISING_PARTLY_LARGE_MINNEDGES

#define PROMISING_PARTLY_LARGE_MINNEDGES 3000

Definition at line 47 of file dpterms_base.c.

Referenced by dpterms_isPromisingPartly().

◆ PROMISING_FULL_LARGE_MINNEDGES

#define PROMISING_FULL_LARGE_MINNEDGES 100000

Definition at line 48 of file dpterms_base.c.

Referenced by dpterms_isPromisingFully().

◆ PROMISING_FULL_MAXAVGDEG

#define PROMISING_FULL_MAXAVGDEG 5.0

Definition at line 49 of file dpterms_base.c.

Referenced by dpterms_isPromisingFully().

Function Documentation

◆ dpgraphInit()

static SCIP_RETCODE dpgraphInit	(	SCIP *	scip,
		const GRAPH *	graph,
		DPGRAPH **	dpgraph
	)

static

initializes

Parameters

scip	SCIP data structure
graph	original graph
dpgraph	DP graph

Definition at line 159 of file dpterms_base.c.

References graph_get_nEdges(), graph_get_nNodes(), graph_get_nTerms(), graph_knot_isInRange(), Is_term, dynamic_programming_graph::nedges, nnodes, dynamic_programming_graph::nnodes, dynamic_programming_graph::nodes_termId, nterms, dynamic_programming_graph::nterms, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, GRAPH::term, and dynamic_programming_graph::terminals.

Referenced by dpsolverInitData().

◆ dpgraphFree()

static void dpgraphFree	(	SCIP *	scip,
		DPGRAPH **	dpgraph
	)

static

frees

Parameters

scip	SCIP data structure
dpgraph	DP graph

Definition at line 217 of file dpterms_base.c.

References dynamic_programming_graph::nodes_termId, SCIPfreeMemory, SCIPfreeMemoryArray, and dynamic_programming_graph::terminals.

Referenced by dpsolverFreeData().

◆ dpmiscInit()

static SCIP_RETCODE dpmiscInit	(	SCIP *	scip,
		const GRAPH *	graph,
		DPMISC **	dpmisc
	)

static

initializes

Parameters

scip	SCIP data structure
graph	original graph
dpmisc	to initialize

Definition at line 236 of file dpterms_base.c.

References FARAWAY, dynamic_programming_misc::global_size, NULL, dynamic_programming_misc::opt_obj, dynamic_programming_misc::opt_prev, dynamic_programming_misc::opt_root, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, and StpVecPushBack.

Referenced by dpsolverInitData().

◆ dpmiscFree()

static void dpmiscFree	(	SCIP *	scip,
		DPMISC **	dpmisc
	)

static

frees

Parameters

scip	SCIP data structure
dpmisc	to free

Definition at line 264 of file dpterms_base.c.

References SCIPfreeMemory, stpbitset_free(), StpVecFree, and StpVecGetSize.

Referenced by dpsolverFreeData().

◆ dpsolverInitData()

static SCIP_RETCODE dpsolverInitData	(	SCIP *	scip,
		GRAPH *	graph,
		DPSOLVER *	dpsolver
	)

static

initializes data

Parameters

scip	SCIP data structure
graph	graph of sub-problem
dpsolver	solver

Definition at line 302 of file dpterms_base.c.

References dynamic_programming_subsolution::bitkey, dynamic_programming_solver::dheap, dynamic_programming_solver::dpgraph, dpgraphInit(), dynamic_programming_solver::dpmisc, dpmiscInit(), dynamic_programming_solver::dpstree, dpterms_streeInit(), graph_heap_create(), Is_term, GRAPH::knots, nnodes, nterms, NULL, solution_trace::prevs, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPrbtreeInsert, dynamic_programming_solver::solpqueue, dynamic_programming_solver::soltree_root, stpbitset_new(), stpbitset_newCopy(), stpbitset_setBitTrue(), stpprioqueue_create(), stpprioqueue_insert(), StpVecPushBack, GRAPH::term, dynamic_programming_graph::terminals, and GRAPH::terms.

Referenced by dpsolverInit().

◆ dpsolverFreeData()

static void dpsolverFreeData	(	SCIP *	scip,
		DPSOLVER *	dpsolver
	)

static

frees data

Parameters

scip	SCIP data structure
dpsolver	solver

Definition at line 371 of file dpterms_base.c.

References dynamic_programming_solver::dheap, dynamic_programming_solver::dpgraph, dpgraphFree(), dynamic_programming_solver::dpmisc, dpmiscFree(), dynamic_programming_solver::dpstree, dpterms_streeFree(), FOR_EACH_NODE, graph_heap_free(), SCIPisStopped(), dynamic_programming_solver::solpqueue, dynamic_programming_solver::soltree_root, stpprioqueue_free(), stpprioqueue_isClean(), StpVecFree, and TRUE.

Referenced by dpsolverFree().

◆ dpsolverSolve()

static SCIP_RETCODE dpsolverSolve	(	SCIP *	scip,
		GRAPH *	g,
		DPSOLVER *	dpsolver,
		SCIP_Bool *	wasSolved
	)

static

solve problem

Parameters

scip	SCIP data structure
g	graph of sub-problem
dpsolver	solver
wasSolved	was problem solved to optimality?

Definition at line 408 of file dpterms_base.c.

References dpterms_coreSolve(), SCIP_CALL, and SCIP_OKAY.

Referenced by dpterms_solve().

◆ dpsolverGetSolution()

static SCIP_RETCODE dpsolverGetSolution	(	SCIP *	scip,
		GRAPH *	graph,
		DPSOLVER *	dpsolver,
		int *	solution
	)

static

gets optimal solution

Parameters

scip	SCIP data structure
graph	graph of sub-problem
dpsolver	the solver
solution	to store solution

Definition at line 423 of file dpterms_base.c.

References graph_knot_isInRange(), GRAPH::knots, SCIP_CALL, SCIP_OKAY, SCIPallocClearBufferArray, SCIPfreeBufferArray, solstp_pruneFromNodes(), STP_Vectype, StpVecGetSize, and TRUE.

Referenced by dpterms_solve().

◆ dpsolverInit()

static SCIP_RETCODE dpsolverInit	(	SCIP *	scip,
		GRAPH *	graph,
		DPSOLVER **	dpsolver
	)

static

initializes

Parameters

scip	SCIP data structure
graph	graph of sub-problem
dpsolver	solver

Definition at line 456 of file dpterms_base.c.

References dpsolverInitData(), SCIP_CALL, SCIP_OKAY, and SCIPallocMemory.

Referenced by dpterms_solve().

◆ dpsolverFree()

static void dpsolverFree	(	SCIP *	scip,
		DPSOLVER **	dpsolver
	)

static

frees

Parameters

scip	SCIP data structure
dpsolver	solver

Definition at line 472 of file dpterms_base.c.

References dpsolverFreeData(), and SCIPfreeMemory.

Referenced by dpterms_solve().

◆ dpterms_solve()

SCIP_RETCODE dpterms_solve	(	SCIP *	scip,
		GRAPH *	graph,
		int *	solution,
		SCIP_Bool *	wasSolved
	)

solves problem given by graph

Parameters

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

Definition at line 489 of file dpterms_base.c.

References dpsolverFree(), dpsolverGetSolution(), dpsolverInit(), dpsolverSolve(), graph_free_csr(), graph_init_csrWithEdgeId(), SCIP_CALL, SCIP_OKAY, and solstp_isValid().

Referenced by solveWithDpTerms(), and substpsolver_solve().

◆ dpterms_isPromisingPartly()

SCIP_Bool dpterms_isPromisingPartly ( const GRAPH * graph )

is DP at least partly promising?

Parameters

graph graph

Definition at line 518 of file dpterms_base.c.

References density, dpterms_isPromisingFully(), GRAPH::edges, FALSE, GT, GRAPH::knots, PROMISING_PARTLY_LARGE_MAXNTERMS, PROMISING_PARTLY_LARGE_MINNEDGES, PROMISING_PARTLY_MAXDENSITY, PROMISING_PARTLY_MEDIUM_MAXNTERMS, PROMISING_PARTLY_MEDIUM_MINNEDGES, PROMISING_PARTLY_SMALL_MAXNTERMS, PROMISING_PARTLY_SMALL_MINNEDGES, SCIP_Real, GRAPH::terms, and TRUE.

Referenced by SCIPStpDpRelaxIsPromising().

◆ dpterms_isPromisingEmbarrassingly()

SCIP_Bool dpterms_isPromisingEmbarrassingly ( const GRAPH * graph )

is DP embarrassingly promising?

Parameters

graph graph

Definition at line 554 of file dpterms_base.c.

References GRAPH::terms.

◆ dpterms_isPromisingFully()

SCIP_Bool dpterms_isPromisingFully ( const GRAPH * graph )

is DP fully promising?

Parameters

graph graph

Definition at line 563 of file dpterms_base.c.

References FALSE, graph_get_nVET(), LT, nnodes, NULL, PROMISING_FULL_LARGE_MINNEDGES, PROMISING_FULL_MAXAVGDEG, PROMISING_FULL_MAXNTERMS, PROMISING_FULL_MAXNTERMS_LARGE, SCIP_Real, GRAPH::terms, and TRUE.

Referenced by dpterms_isPromisingPartly(), reduce_redLoopStp(), and substpsolver_init().