Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

Solver for Steiner tree (sub-) problems.

Author: Daniel Rehfeldt

This file implements methods to solve Steiner tree subproblems to optimality, and to obtain an optimal Steiner tree. Branch-and-cut or dynamic programming is used for solving the subproblems.

Definition in file substpsolver.h.

#include "scip/scip.h"
#include "graph.h"
#include "probdata_stp.h"

Go to the source code of this file.

Typedefs
typedef struct sub_steiner_tree_problem	SUBSTP

Functions
SCIP_RETCODE	substpsolver_init (SCIP , GRAPH , SUBSTP **)

SCIP_RETCODE	substpsolver_initDP (SCIP , GRAPH , SUBSTP **)

SCIP_RETCODE	substpsolver_initBC (SCIP , GRAPH , SUBSTP **)

void	substpsolver_free (SCIP , SUBSTP *)

SCIP_RETCODE	substpsolver_transferHistory (const int , GRAPH , SUBSTP *)

SCIP_RETCODE	substpsolver_initHistory (SUBSTP *)

SCIP_RETCODE	substpsolver_solve (SCIP , SUBSTP , SCIP_Bool *)

int	substpsolver_getNsubedges (const SUBSTP *)

SCIP_RETCODE	substpsolver_getSolution (SUBSTP , int )

SCIP_RETCODE	substpsolver_setMute (SUBSTP *)

SCIP_RETCODE	substpsolver_setProbIsIndependent (SUBSTP *)

SCIP_RETCODE	substpsolver_setProbNoSubDP (SUBSTP *)

SCIP_RETCODE	substpsolver_setProbFullPresolve (SUBSTP *)

SCIP_RETCODE	substpsolver_getObjFromGraph (SCIP , const GRAPH , SCIP_Real *)

Typedef Documentation

◆ SUBSTP

typedef struct sub_steiner_tree_problem SUBSTP

Steiner tree sub-problem

Definition at line 38 of file substpsolver.h.

Function Documentation

◆ substpsolver_init()

SCIP_RETCODE substpsolver_init	(	SCIP *	scip,
		GRAPH *	subgraph,
		SUBSTP **	substp
	)

Initializes from given sub-graph. Decides automatically whether to use DP or B&C. NOTE: Sub-graph will be moved into internal data structure and also released once substp is freed!

Parameters

scip	SCIP data structure
subgraph	subproblem to initialize from; NOTE: will be moved
substp	initialize

Definition at line 313 of file substpsolver.c.

References dpterms_isPromisingFully(), SCIP_CALL, SCIP_OKAY, substpsolver_initBC(), and substpsolver_initDP().

Referenced by decomposeExactSubDoIt(), and decomposeSolveSub().

◆ substpsolver_initDP()

SCIP_RETCODE substpsolver_initDP	(	SCIP *	scip,
		GRAPH *	subgraph,
		SUBSTP **	substp
	)

Initializes from given sub-graph, and always uses dynamic programming for solving NOTE: Sub-graph will be moved into internal data structure and also released once substp is freed!

Parameters

scip	SCIP data structure
subgraph	subproblem to initialize from; NOTE: will be moved
substp	initialize

Definition at line 337 of file substpsolver.c.

References sub_steiner_tree_problem::dpsubsol, GRAPH::edges, initDefault(), SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, sub, TRUE, and sub_steiner_tree_problem::useDP.

Referenced by substpsolver_init().

◆ substpsolver_initBC()

SCIP_RETCODE substpsolver_initBC	(	SCIP *	scip,
		GRAPH *	subgraph,
		SUBSTP **	substp
	)

Initializes from given sub-graph, and always uses B&C for solving NOTE: Sub-graph will be moved into internal data structure and also released once substp is freed!

Parameters

scip	SCIP data structure
subgraph	subproblem to initialize from; NOTE: will be moved
substp	initialize

Definition at line 359 of file substpsolver.c.

References FALSE, initDefault(), SCIP_CALL, SCIP_OKAY, SCIPcreate(), sub, sub_steiner_tree_problem::subscip, subscipSetup(), and sub_steiner_tree_problem::useDP.

Referenced by solveSub(), substpsolver_getObjFromGraph(), and substpsolver_init().

◆ substpsolver_free()

void substpsolver_free	(	SCIP *	scip,
		SUBSTP **	substp
	)

frees

Parameters

scip	SCIP data structure
substp	to be freed

Definition at line 380 of file substpsolver.c.

References sub_steiner_tree_problem::dpsubsol, SCIPfree(), SCIPfreeMemory, SCIPfreeMemoryArrayNull, sub, and sub_steiner_tree_problem::subscip.

Referenced by decomposeExactSubDoIt(), decomposeSolveSub(), solveSub(), and substpsolver_getObjFromGraph().

◆ substpsolver_transferHistory()

SCIP_RETCODE substpsolver_transferHistory	(	const int *	edgeMapToOrg,
		GRAPH *	orggraph,
		SUBSTP *	substp
	)

Transfers history. Useful in order to have (fixed and edge) pseudo-ancestors up-to-date. NOTE: fixed edges are not transferred! Only pseudo-ancestors

Parameters

edgeMapToOrg	maps edges of subgraph to original graph
orggraph	original graph
substp	sub-problem

Definition at line 404 of file substpsolver.c.

References graph_subgraphCompleteNewHistory(), SCIP_CALL, SCIP_OKAY, sub_steiner_tree_problem::subgraph, sub_steiner_tree_problem::subscip, and sub_steiner_tree_problem::useDP.

Referenced by decomposeExactSubDoIt(), and decomposeSolveSub().

◆ substpsolver_initHistory()

SCIP_RETCODE substpsolver_initHistory ( SUBSTP * substp )

initializes history, but does not transfer any information!

Parameters

substp sub-problem

Definition at line 430 of file substpsolver.c.

References graph_initHistory(), SCIP_CALL, SCIP_OKAY, sub_steiner_tree_problem::subgraph, sub_steiner_tree_problem::subscip, and sub_steiner_tree_problem::useDP.

Referenced by solveSub(), and substpsolver_getObjFromGraph().

◆ substpsolver_solve()

SCIP_RETCODE substpsolver_solve	(	SCIP *	scip,
		SUBSTP *	substp,
		SCIP_Bool *	success
	)

solves sub-problem

Parameters

scip	SCIP data structure
substp	sub-problem
success	was sub-problem solved to optimality?

Definition at line 452 of file substpsolver.c.

References sub_steiner_tree_problem::dpsubsol, dpterms_solve(), graph_free(), graph_path_exists(), graph_path_init(), NULL, SCIP_CALL, SCIP_OKAY, sub_steiner_tree_problem::subgraph, subscipSolve(), TRUE, and sub_steiner_tree_problem::useDP.

Referenced by decomposeExactSubDoIt(), decomposeSolveSub(), solveSub(), and substpsolver_getObjFromGraph().

◆ substpsolver_getNsubedges()

int substpsolver_getNsubedges ( const SUBSTP * substp )

gets number of edges of subproblem

Parameters

substp sub-problem

Definition at line 488 of file substpsolver.c.

References sub_steiner_tree_problem::nsubedges.

Referenced by decomposeExactFixSol(), and subsolInit().

◆ substpsolver_getSolution()

SCIP_RETCODE substpsolver_getSolution	(	SUBSTP *	substp,
		int *	edgesol
	)

gets solution to sub-problem

Parameters

substp	sub-problem
edgesol	array to store edge solution; CONNECT/UNKNOWN

Definition at line 500 of file substpsolver.c.

References BMScopyMemoryArray, sub_steiner_tree_problem::dpsubsol, sub_steiner_tree_problem::nsubedges, SCIP_CALL, SCIP_OKAY, sub_steiner_tree_problem::subgraph, sub_steiner_tree_problem::subscip, subscipGetSol(), and sub_steiner_tree_problem::useDP.

Referenced by decomposeExactFixSol(), solveSub(), subsolGet(), and substpsolver_getObjFromGraph().

◆ substpsolver_setMute()

SCIP_RETCODE substpsolver_setMute ( SUBSTP * substp )

sets to no output

Parameters

substp sub-problem

Definition at line 525 of file substpsolver.c.

References FALSE, SCIP_CALL, SCIP_OKAY, SCIPsetIntParam(), sub_steiner_tree_problem::subscip, and sub_steiner_tree_problem::useOutput.

Referenced by decomposeExactSubDoIt(), decomposeSolveSub(), solveSub(), and substpsolver_getObjFromGraph().

◆ substpsolver_setProbIsIndependent()

SCIP_RETCODE substpsolver_setProbIsIndependent ( SUBSTP * substp )

sets to independent problem

Parameters

substp sub-problem

Definition at line 542 of file substpsolver.c.

References SCIP_OKAY, sub_steiner_tree_problem::subprobIsIndependent, and TRUE.

◆ substpsolver_setProbNoSubDP()

SCIP_RETCODE substpsolver_setProbNoSubDP ( SUBSTP * substp )

disables DP for solving sub-problems

Parameters

substp sub-problem

Definition at line 553 of file substpsolver.c.

References SCIP_CALL, SCIP_OKAY, SCIPsetIntParam(), and sub_steiner_tree_problem::subscip.

Referenced by substpsolver_getObjFromGraph().

◆ substpsolver_setProbFullPresolve()

SCIP_RETCODE substpsolver_setProbFullPresolve ( SUBSTP * substp )

sets full presolving

Parameters

substp sub-problem

Definition at line 568 of file substpsolver.c.

References SCIP_CALL, SCIP_OKAY, SCIPsetIntParam(), and sub_steiner_tree_problem::subscip.

Referenced by decomposeExactSubDoIt(), and solveSub().

◆ substpsolver_getObjFromGraph()

SCIP_RETCODE substpsolver_getObjFromGraph	(	SCIP *	scip,
		const GRAPH *	graph,
		SCIP_Real *	obj
	)

Gets optimal objective by B&C. NOTE: Meant for debugging only! NOTE: Need to be careful with recursion! Might run into infinite loop.

Parameters

scip	SCIP data structure
graph	graph
obj	to store solution

Definition at line 585 of file substpsolver.c.

References GRAPH::edges, FALSE, graph_copy(), GRAPH::is_packed, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, SCIPfreeMemoryArray, solstp_getObj(), substpsolver_free(), substpsolver_getSolution(), substpsolver_initBC(), substpsolver_initHistory(), substpsolver_setMute(), substpsolver_setProbNoSubDP(), and substpsolver_solve().

Referenced by solveWithDpTerms().