substpsolver.c File Reference

Detailed Description

Solver for Steiner tree (sub-) problems.

Author

Daniel Rehfeldt

Definition in file substpsolver.c.

#include "scip/scipdefplugins.h"
#include "substpsolver.h"
#include "solhistory.h"
#include "pricer_stp.h"
#include "probdata_stp.h"
#include "cons_stp.h"
#include "reduce.h"
#include "cons_stpcomponents.h"
#include "heur_tm.h"
#include "reader_stp.h"
#include "heur_local.h"
#include "heur_prune.h"
#include "heur_ascendprune.h"
#include "heur_slackprune.h"
#include "heur_lurkprune.h"
#include "heur_rec.h"
#include "dialog_stp.h"
#include "prop_stp.h"
#include "branch_stp.h"
#include "dpterms.h"
#include "solstp.h"
#include "relax_stp.h"
#include "relax_stpdp.h"

Go to the source code of this file.

Data Structures
struct	sub_steiner_tree_problem

Functions
static SCIP_RETCODE	subscipSetupCallbacks (SCIP *subscip)
static SCIP_RETCODE	subscipSetupParameters (SCIP *scip, const SUBSTP *substp, SCIP *subscip)
static SCIP_RETCODE	subscipSetup (SCIP *scip, const SUBSTP *substp, SCIP *subscip)
static SCIP_RETCODE	subscipSolve (SCIP *scip, SUBSTP *substp, SCIP_Bool *success)
static SCIP_RETCODE	subscipGetSol (SUBSTP *substp, int *subedgesSol)
static SCIP_RETCODE	initDefault (SCIP *scip, GRAPH *subgraph, SUBSTP **substp)
SCIP_RETCODE	substpsolver_init (SCIP *scip, GRAPH *subgraph, SUBSTP **substp)
SCIP_RETCODE	substpsolver_initDP (SCIP *scip, GRAPH *subgraph, SUBSTP **substp)
SCIP_RETCODE	substpsolver_initBC (SCIP *scip, GRAPH *subgraph, SUBSTP **substp)
void	substpsolver_free (SCIP *scip, SUBSTP **substp)
SCIP_RETCODE	substpsolver_transferHistory (const int *edgeMapToOrg, GRAPH *orggraph, SUBSTP *substp)
SCIP_RETCODE	substpsolver_initHistory (SUBSTP *substp)
SCIP_RETCODE	substpsolver_solve (SCIP *scip, SUBSTP *substp, SCIP_Bool *success)
int	substpsolver_getNsubedges (const SUBSTP *substp)
SCIP_RETCODE	substpsolver_getSolution (SUBSTP *substp, int *edgesol)
SCIP_RETCODE	substpsolver_setMute (SUBSTP *substp)
SCIP_RETCODE	substpsolver_setProbIsIndependent (SUBSTP *substp)
SCIP_RETCODE	substpsolver_setProbNoSubDP (SUBSTP *substp)
SCIP_RETCODE	substpsolver_setProbFullPresolve (SUBSTP *substp)
SCIP_RETCODE	substpsolver_getObjFromGraph (SCIP *scip, const GRAPH *graph, SCIP_Real *obj)

Function Documentation

subscipSetupCallbacks()

static SCIP_RETCODE subscipSetupCallbacks ( SCIP *  subscip )

static

helper

Parameters

subscip

sub-SCIP data structure

Definition at line 95 of file substpsolver.c.

References SCIP_CALL, SCIP_OKAY, SCIPincludeBranchruleStp(), SCIPincludeConshdlrStp(), SCIPincludeConshdlrStpcomponents(), SCIPincludeDefaultPlugins(), SCIPincludeDialogStp(), SCIPincludePricerStp(), SCIPincludePropStp(), SCIPincludeReaderStp(), SCIPincludeRelaxStp(), SCIPincludeRelaxStpdp(), SCIPStpIncludeHeurAscendPrune(), SCIPStpIncludeHeurLocal(), SCIPStpIncludeHeurLurkPrune(), SCIPStpIncludeHeurPrune(), SCIPStpIncludeHeurRec(), SCIPStpIncludeHeurSlackPrune(), and SCIPStpIncludeHeurTM().

Referenced by subscipSetup().

subscipSetupParameters()

static SCIP_RETCODE subscipSetupParameters ( SCIP *  scip, const SUBSTP *  substp, SCIP *  subscip  )

static

helper

Parameters

scip	SCIP data structure
substp	sub-problem
subscip	sub-SCIP data structure

Definition at line 139 of file substpsolver.c.

References FALSE, GT, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPprobdataSetDefaultParams(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetRealParam(), sub_steiner_tree_problem::subprobIsIndependent, and sub_steiner_tree_problem::useOutput.

Referenced by subscipSetup().

subscipSetup()

static SCIP_RETCODE subscipSetup ( SCIP *  scip, const SUBSTP *  substp, SCIP *  subscip  )

static

sets up the sub-SCIP

Parameters

scip	SCIP data structure
substp	sub-problem
subscip	sub-SCIP data structure

Definition at line 185 of file substpsolver.c.

References SCIP_CALL, SCIP_OKAY, subscipSetupCallbacks(), and subscipSetupParameters().

Referenced by substpsolver_initBC().

subscipSolve()

static SCIP_RETCODE subscipSolve ( SCIP *  scip, SUBSTP *  substp, SCIP_Bool *  success  )

static

solves sub-problem by using branch-and-cut

Parameters

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

Definition at line 201 of file substpsolver.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_STATUS_OPTIMAL, SCIPdebugMessage, SCIPgetSolvingTime(), SCIPgetStatus(), SCIPprobdataCreateFromGraph(), SCIPsolve(), sub_steiner_tree_problem::subgraph, sub_steiner_tree_problem::subprobIsIndependent, sub_steiner_tree_problem::subscip, and TRUE.

Referenced by substpsolver_solve().

subscipGetSol()

static SCIP_RETCODE subscipGetSol ( SUBSTP *  substp, int *  subedgesSol  )

static

gets solution

Parameters

substp	sub-problem
subedgesSol	solution

Definition at line 240 of file substpsolver.c.

References CONNECT, solution_history::norgedges, sub_steiner_tree_problem::nsubedges, solution_history::orgedges_isInSol, SCIP_CALL, SCIP_OKAY, SCIPgetBestSol(), SCIPprobdataGetGraph2(), solhistory_computeHistory(), solhistory_free(), solhistory_init(), sub_steiner_tree_problem::subgraph, sub_steiner_tree_problem::subscip, subsol, and UNKNOWN.

Referenced by substpsolver_getSolution().

initDefault()

static SCIP_RETCODE initDefault ( SCIP *  scip, GRAPH *  subgraph, SUBSTP **  substp  )

static

Initializes default stuff

Parameters

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

Definition at line 280 of file substpsolver.c.

References sub_steiner_tree_problem::dpsubsol, GRAPH::edges, FALSE, sub_steiner_tree_problem::nsubedges, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, sub, sub_steiner_tree_problem::subgraph, sub_steiner_tree_problem::subprobIsIndependent, sub_steiner_tree_problem::subscip, TRUE, and sub_steiner_tree_problem::useOutput.

Referenced by substpsolver_initBC(), and substpsolver_initDP().

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().