Scippy

SCIP

Solving Constraint Integer Programs

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_UNSET -2

#define	BRANCH_STP_VERTEX_KILLED -1

#define	BRANCH_STP_VERTEX_NONTERM 0

#define	BRANCH_STP_VERTEX_TERM 1

Functions
SCIP_RETCODE	STPStpBranchruleParseConsname (int vertexchgs, const char consname, SCIP_Bool *conflictFound)

SCIP_RETCODE	SCIPStpBranchruleGetVertexChgs (SCIP scip, int vertexchgs, SCIP_Bool *conflictFound)

SCIP_RETCODE	SCIPStpBranchruleGetVertexChgLast (SCIP scip, int vertex, SCIP_Bool *isDeleted)

SCIP_Bool	SCIPStpBranchruleIsActive (SCIP *scip)

void	SCIPStpBranchruleInitNodeState (const GRAPH g, int nodestate)

SCIP_RETCODE	SCIPincludeBranchruleStp (SCIP *scip)

SCIP_Bool	SCIPStpBranchruleProbIsCompatible (const GRAPH *graph)

Macro Definition Documentation

◆ BRANCH_STP_VERTEX_UNSET

#define BRANCH_STP_VERTEX_UNSET -2

Definition at line 36 of file branch_stp.h.

Referenced by getBoundchanges().

◆ BRANCH_STP_VERTEX_KILLED

#define BRANCH_STP_VERTEX_KILLED -1

Definition at line 37 of file branch_stp.h.

Referenced by applyBranchHistoryToGraph(), getBoundchangesPcMW(), initReceivedSubproblem(), propgraphApplyStates(), STPStpBranchruleParseConsname(), and trailGraphWithStates().

◆ BRANCH_STP_VERTEX_NONTERM

#define BRANCH_STP_VERTEX_NONTERM 0

Definition at line 38 of file branch_stp.h.

Referenced by getHighSolDegVertex(), SCIPStpBranchruleInitNodeState(), selectBranchingVertexByDegree(), selectBranchingVertexByLp(), and selectBranchingVertexByLp2Flow().

◆ BRANCH_STP_VERTEX_TERM

#define BRANCH_STP_VERTEX_TERM 1

Definition at line 39 of file branch_stp.h.

Referenced by applyBranchHistoryToGraph(), fixVarsDualcost(), getBoundchanges(), getBoundchangesPcMW(), getGraphStatesDirected(), initReceivedSubproblem(), propgraphApplyStates(), propgraphMarkFixedTermsPcMw(), SCIP_DECL_CONSSEPALP(), SCIPStpBranchruleInitNodeState(), STPStpBranchruleParseConsname(), and trailGraphWithStates().

Function Documentation

◆ STPStpBranchruleParseConsname()

SCIP_RETCODE STPStpBranchruleParseConsname	(	int *	vertexchgs,
		const char *	consname,
		SCIP_Bool *	conflictFound
	)

parse constraint name and apply changes to graph or array

Parameters

vertexchgs	array to store changes
consname	constraint name
conflictFound	conflict with existing vertex changes found?

Definition at line 902 of file branch_stp.c.

References BRANCH_STP_VERTEX_KILLED, BRANCH_STP_VERTEX_TERM, FALSE, SCIP_ERROR, SCIP_OKAY, SCIPdebugMessage, and TRUE.

Referenced by initReceivedSubproblem(), and SCIPStpBranchruleGetVertexChgs().

◆ SCIPStpBranchruleGetVertexChgs()

SCIP_RETCODE SCIPStpBranchruleGetVertexChgs	(	SCIP *	scip,
		int *	vertexchgs,
		SCIP_Bool *	conflictFound
	)

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
conflictFound	conflict with existing vertex changes found?

Definition at line 977 of file branch_stp.c.

References BRANCHRULE_NAME, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIPbranchruleGetData(), SCIPbranchruleGetName(), SCIPconsGetName(), SCIPerrorMessage, SCIPfindBranchrule(), SCIPgetCurrentNode(), SCIPnodeGetAddedConss(), SCIPnodeGetDepth(), SCIPnodeGetNAddedConss(), SCIPnodeGetParent(), STPStpBranchruleParseConsname(), and TRUE.

Referenced by fixVarsDualcost(), getBoundchanges(), getGraphStatesDirected(), SCIP_DECL_CONSSEPALP(), selectBranchingVertexByDegree(), selectBranchingVertexByLp(), selectBranchingVertexByLp2Flow(), and selectBranchingVertexBySol().

◆ SCIPStpBranchruleGetVertexChgLast()

SCIP_RETCODE SCIPStpBranchruleGetVertexChgLast	(	SCIP *	scip,
		int *	vertex,
		SCIP_Bool *	isDeleted
	)

get last change

Parameters

scip	SCIP data structure
vertex	changed vertex
isDeleted	deleted? (otherwise terminal)

Definition at line 1036 of file branch_stp.c.

References BRANCHRULE_NAME, FALSE, NULL, SCIP_ERROR, SCIP_OKAY, SCIPbranchruleGetData(), SCIPbranchruleGetName(), SCIPconsGetName(), SCIPdebugMessage, SCIPerrorMessage, SCIPfindBranchrule(), SCIPgetCurrentNode(), SCIPnodeGetAddedConss(), SCIPnodeGetNAddedConss(), and TRUE.

Referenced by applyLastVertexBranch().

◆ SCIPStpBranchruleIsActive()

SCIP_Bool SCIPStpBranchruleIsActive ( SCIP * scip )

is the branching rule active?

Parameters

scip	SCIP data structure

Definition at line 1099 of file branch_stp.c.

References BRANCHRULE_NAME, NULL, SCIPbranchruleGetData(), SCIPbranchruleGetName(), and SCIPfindBranchrule().

Referenced by applyLastVertexBranch(), fixVarsDualcost(), getGraphStatesDirected(), and SCIP_DECL_CONSSEPALP().

◆ 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 954 of file branch_stp.c.

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

Referenced by fixVarsDualcost(), getGraphStatesDirected(), initReceivedSubproblem(), SCIP_DECL_CONSSEPALP(), selectBranchingVertexByDegree(), selectBranchingVertexByLp(), selectBranchingVertexByLp2Flow(), and selectBranchingVertexBySol().

◆ SCIPincludeBranchruleStp()

SCIP_RETCODE SCIPincludeBranchruleStp ( SCIP * scip )

creates the stp branching rule and includes it to SCIP

creates the stp branching rule and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 1129 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, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPallocMemory, SCIPincludeBranchruleBasic(), SCIPsetBranchruleCopy(), SCIPsetBranchruleExecLp(), SCIPsetBranchruleExecPs(), SCIPsetBranchruleExit(), SCIPsetBranchruleFree(), SCIPsetBranchruleInit(), and TRUE.

Referenced by runShell(), SCIP_DECL_BRANCHCOPY(), and subscipSetupCallbacks().

◆ SCIPStpBranchruleProbIsCompatible()

SCIP_Bool SCIPStpBranchruleProbIsCompatible ( const GRAPH * graph )

returns whether branching-rule is compatible with given graph problem type

Parameters

graph graph

Definition at line 1119 of file branch_stp.c.

References probIsCompatible().

Referenced by SCIP_DECL_CONSSEPALP().