branch_stp.h File Reference

Detailed Description

Steiner vertex branching rule.

Author

Daniel Rehfeldt

The Steiner branching rule implemented in this file is described in "A Generic Approach to Solving the Steiner Tree Problem and Variants" by Daniel Rehfeldt. It removes includes and exludes Steiner vertices during branching.

Definition in file branch_stp.h.

#include "scip/scip.h"

Go to the source code of this file.

Macros
#define	BRANCH_STP_VERTEX_KILLED   -1
#define	BRANCH_STP_VERTEX_NONTERM   0
#define	BRANCH_STP_VERTEX_TERM   1

Functions
SCIP_RETCODE	STPStpBranchruleParseConsname (SCIP *scip, int *vertexchgs, GRAPH *graph, const char *consname, SCIP_Bool deletehistory)
SCIP_RETCODE	SCIPStpBranchruleApplyVertexChgs (SCIP *scip, int *vertexchgs, GRAPH *graph)
void	SCIPStpBranchruleInitNodeState (const GRAPH *g, int *nodestate)
SCIP_RETCODE	SCIPincludeBranchruleStp (SCIP *scip)

Macro Definition Documentation

BRANCH_STP_VERTEX_KILLED

#define BRANCH_STP_VERTEX_KILLED   -1

Definition at line 36 of file branch_stp.h.

Referenced by initReceivedSubproblem(), SCIPStpBranchruleInitNodeState(), and STPStpBranchruleParseConsname().

BRANCH_STP_VERTEX_NONTERM

#define BRANCH_STP_VERTEX_NONTERM   0

Definition at line 37 of file branch_stp.h.

Referenced by SCIPStpBranchruleInitNodeState(), selectBranchingVertexByDegree(), selectBranchingVertexByLp2Flow(), and selectBranchingVertexBySol().

BRANCH_STP_VERTEX_TERM

#define BRANCH_STP_VERTEX_TERM   1

Definition at line 38 of file branch_stp.h.

Referenced by initReceivedSubproblem(), SCIP_DECL_CONSSEPALP(), SCIPStpBranchruleInitNodeState(), selectBranchingVertexByLp2Flow(), selectBranchingVertexBySol(), and STPStpBranchruleParseConsname().

Function Documentation

STPStpBranchruleParseConsname()

SCIP_RETCODE STPStpBranchruleParseConsname	(	SCIP *	scip,
		int *	vertexchgs,
		GRAPH *	graph,
		const char *	consname,
		SCIP_Bool	deletehistory
	)

parse constraint name and apply changes to graph or array

Parameters

scip	SCIP data structure
vertexchgs	array to store changes or NULL
graph	graph to modify or NULL
consname	constraint name
deletehistory	delete history of graph?

Definition at line 604 of file branch_stp.c.

References BRANCH_STP_VERTEX_KILLED, BRANCH_STP_VERTEX_TERM, FARAWAY, graph_knot_chg(), graph_knot_del(), graph_pc_chgPrize(), graph_pc_deleteTerm(), Is_pterm, Is_term, NULL, SCIP_ERROR, SCIP_OKAY, SCIPdebugMessage, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, and GRAPH::term.

Referenced by initReceivedSubproblem(), and SCIPStpBranchruleApplyVertexChgs().

SCIPStpBranchruleApplyVertexChgs()

SCIP_RETCODE SCIPStpBranchruleApplyVertexChgs	(	SCIP *	scip,
		int *	vertexchgs,
		GRAPH *	graph
	)

applies vertex changes caused by this branching rule, either on a graph or on an array

Parameters

scip	SCIP data structure
vertexchgs	array to store changes or NULL
graph	graph to apply changes on or NULL

Definition at line 708 of file branch_stp.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetName(), SCIPgetCurrentNode(), SCIPnodeGetAddedConss(), SCIPnodeGetDepth(), SCIPnodeGetNAddedConss(), SCIPnodeGetParent(), STPStpBranchruleParseConsname(), and TRUE.

Referenced by redbasedVarfixing(), SCIP_DECL_CONSSEPALP(), selectBranchingVertexByDegree(), selectBranchingVertexByLp2Flow(), and selectBranchingVertexBySol().

SCIPStpBranchruleInitNodeState()

void SCIPStpBranchruleInitNodeState	(	const GRAPH *	g,
		int *	nodestate
	)

applies vertex changes caused by this branching rule, either on a graph or on an array

Parameters

g	graph data structure
nodestate	node state array

Definition at line 683 of file branch_stp.c.

References BRANCH_STP_VERTEX_KILLED, BRANCH_STP_VERTEX_NONTERM, BRANCH_STP_VERTEX_TERM, GRAPH::grad, Is_term, GRAPH::knots, nnodes, NULL, and GRAPH::term.

Referenced by initReceivedSubproblem(), SCIP_DECL_CONSSEPALP(), and selectBranchingVertexByDegree().

SCIPincludeBranchruleStp()

SCIP_RETCODE SCIPincludeBranchruleStp

(

SCIP *

scip

)

creates the stp branching rule and includes it to SCIP

creates the multi-aggregated branching rule and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 747 of file branch_stp.c.

References BRANCH_STP_ON_LP, BRANCHRULE_DESC, BRANCHRULE_MAXBOUNDDIST, BRANCHRULE_MAXDEPTH, BRANCHRULE_NAME, BRANCHRULE_PRIORITY, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddIntParam(), SCIPallocMemory, SCIPincludeBranchruleBasic(), SCIPsetBranchruleCopy(), SCIPsetBranchruleExecLp(), SCIPsetBranchruleExecPs(), SCIPsetBranchruleExit(), SCIPsetBranchruleFree(), and SCIPsetBranchruleInit().

Referenced by runShell(), and SCIP_DECL_BRANCHCOPY().