Detailed Description

Steiner vertex branching rule.

Author: Daniel Rehfeldt

The Steiner branching rule implemented in this file is described in "SCIP-Jack - A solver for STP and variants with parallelization extensions" by Gamrath, Koch, Maher, Rehfeldt and Shinano It includes and excludes Steiner vertices during branching.

Definition in file branch_stp.c.

#include <assert.h>
#include <string.h>
#include "scip/branch_fullstrong.h"
#include "scip/cons_linear.h"
#include "scip/cons_setppc.h"
#include "scip/var.h"
#include "scip/set.h"
#include "scip/pub_tree.h"
#include "scip/struct_scip.h"
#include "scip/clock.h"
#include "grph.h"
#include "heur_tm.h"
#include "heur_local.h"
#include "branch_stp.h"
#include "prop_stp.h"
#include "probdata_stp.h"

Go to the source code of this file.

Macros
#define	BRANCHRULE_NAME "stp"

#define	BRANCHRULE_DESC "stp branching on vertices"

#define	BRANCHRULE_PRIORITY 10000000

#define	BRANCHRULE_MAXDEPTH -1

#define	BRANCHRULE_MAXBOUNDDIST 1.0

#define	BRANCHRULE_TMRUNS 20

#define	BRANCH_STP_ON_LP 0

#define	BRANCH_STP_ON_LP2 1

#define	BRANCH_STP_ON_SOL 2

Functions
static SCIP_Bool	isProbCompatible (int probtype)

static SCIP_RETCODE	selectBranchingVertexByDegree (SCIP scip, int vertex, const GRAPH *g)

static SCIP_RETCODE	selectBranchingVertexBySol (SCIP scip, int vertex, SCIP_Bool addsol)

static SCIP_RETCODE	selectBranchingVertexByLp (SCIP scip, int vertex, const GRAPH *g)

static SCIP_RETCODE	selectBranchingVertexByLp2Flow (SCIP scip, int vertex, const GRAPH *g)

static SCIP_RETCODE	branchOnVertex (SCIP scip, const GRAPH g, int branchvertex)

static	SCIP_DECL_BRANCHCOPY (branchCopyStp)

static	SCIP_DECL_BRANCHFREE (branchFreeStp)

static	SCIP_DECL_BRANCHINIT (branchInitStp)

static	SCIP_DECL_BRANCHEXIT (branchExitStp)

static	SCIP_DECL_BRANCHEXECLP (branchExeclpStp)

static	SCIP_DECL_BRANCHEXECPS (branchExecpsStp)

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

void	SCIPStpBranchruleInitNodeState (const GRAPH g, int nodestate)

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

SCIP_RETCODE	SCIPincludeBranchruleStp (SCIP *scip)

Macro Definition Documentation

◆ BRANCHRULE_NAME

#define BRANCHRULE_NAME "stp"

Definition at line 45 of file branch_stp.c.

Referenced by SCIP_DECL_BRANCHCOPY(), SCIP_DECL_BRANCHEXECLP(), SCIP_DECL_BRANCHEXECPS(), and SCIPincludeBranchruleStp().

◆ BRANCHRULE_DESC

#define BRANCHRULE_DESC "stp branching on vertices"

Definition at line 46 of file branch_stp.c.

Referenced by SCIPincludeBranchruleStp().

◆ BRANCHRULE_PRIORITY

#define BRANCHRULE_PRIORITY 10000000

Definition at line 47 of file branch_stp.c.

Referenced by SCIPincludeBranchruleStp().

◆ BRANCHRULE_MAXDEPTH

#define BRANCHRULE_MAXDEPTH -1

Definition at line 48 of file branch_stp.c.

Referenced by SCIPincludeBranchruleStp().

◆ BRANCHRULE_MAXBOUNDDIST

#define BRANCHRULE_MAXBOUNDDIST 1.0

Definition at line 49 of file branch_stp.c.

Referenced by SCIPincludeBranchruleStp().

◆ BRANCHRULE_TMRUNS

#define BRANCHRULE_TMRUNS 20

Definition at line 50 of file branch_stp.c.

Referenced by selectBranchingVertexBySol().

◆ BRANCH_STP_ON_LP

#define BRANCH_STP_ON_LP 0

Definition at line 52 of file branch_stp.c.

Referenced by SCIP_DECL_BRANCHEXECLP(), and SCIPincludeBranchruleStp().

◆ BRANCH_STP_ON_LP2

#define BRANCH_STP_ON_LP2 1

Definition at line 53 of file branch_stp.c.

Referenced by SCIP_DECL_BRANCHEXECLP().

◆ BRANCH_STP_ON_SOL

#define BRANCH_STP_ON_SOL 2

Definition at line 54 of file branch_stp.c.

Referenced by SCIP_DECL_BRANCHEXECLP().

Function Documentation

◆ isProbCompatible()

static SCIP_Bool isProbCompatible ( int probtype )

static

check whether branching-rule is compatible with given problem type

Parameters

probtype the problem type

Definition at line 76 of file branch_stp.c.

References STP_OARSMT, STP_PCSPG, STP_RPCSPG, STP_RSMT, and STP_SPG.

Referenced by SCIP_DECL_BRANCHEXECLP(), and SCIP_DECL_BRANCHEXECPS().

◆ selectBranchingVertexByDegree()

static SCIP_RETCODE selectBranchingVertexByDegree	(	SCIP *	scip,
		int *	vertex,
		const GRAPH *	g
	)

static

select vertex to branch on by choosing vertex of highest degree

Parameters

scip	original SCIP data structure
vertex	the vertex to branch on
g	graph

Definition at line 86 of file branch_stp.c.

References BRANCH_STP_VERTEX_NONTERM, GRAPH::grad, graph_pc_isPcMw(), Is_pterm, Is_term, GRAPH::knots, nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPStpBranchruleApplyVertexChgs(), SCIPStpBranchruleInitNodeState(), GRAPH::term, and UNKNOWN.

Referenced by SCIP_DECL_BRANCHEXECLP(), and SCIP_DECL_BRANCHEXECPS().

◆ selectBranchingVertexBySol()

static SCIP_RETCODE selectBranchingVertexBySol	(	SCIP *	scip,
		int *	vertex,
		SCIP_Bool	addsol
	)

static

select vertex to branch on by using primal solution

Parameters

scip	original SCIP data structure
vertex	the vertex to branch on
addsol	add new solution to pool?

Definition at line 129 of file branch_stp.c.

References BMScopyMemoryArray, BRANCH_STP_VERTEX_NONTERM, BRANCH_STP_VERTEX_TERM, BRANCHRULE_TMRUNS, CONNECT, GRAPH::cost, EAT_LAST, GRAPH::edges, flipedge, GRAPH::grad, graph_knot_chg(), graph_pc_isPcMw(), graph_sol_valid(), Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetCurrentNode(), SCIPgetLPSolstat(), SCIPhasCurrentNodeLP(), SCIPnodeGetDepth(), SCIPprobdataAddNewSol(), SCIPprobdataGetGraph2(), SCIPprobdataGetNVars(), SCIPStpBranchruleApplyVertexChgs(), SCIPStpHeurLocalRun(), SCIPStpHeurTMRunLP(), GRAPH::term, and UNKNOWN.

Referenced by SCIP_DECL_BRANCHEXECLP().

◆ selectBranchingVertexByLp()

static SCIP_RETCODE selectBranchingVertexByLp	(	SCIP *	scip,
		int *	vertex,
		const GRAPH *	g
	)

static

select vertex to branch on by using LP

Parameters

scip	original SCIP data structure
vertex	the vertex to branch on
g	graph

Definition at line 254 of file branch_stp.c.

References a, EAT_LAST, fabs(), GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, NULL, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPgetLPSolstat(), SCIPhasCurrentNodeLP(), SCIPisLT(), SCIPisPositive(), SCIPprobdataGetEdgeVars(), SCIPvarGetLPSol(), GRAPH::term, and UNKNOWN.

Referenced by SCIP_DECL_BRANCHEXECLP().

◆ selectBranchingVertexByLp2Flow()

static SCIP_RETCODE selectBranchingVertexByLp2Flow	(	SCIP *	scip,
		int *	vertex,
		const GRAPH *	g
	)

static

select vertices with flow on at least two incoming arcs

Parameters

scip	original SCIP data structure
vertex	the vertex to branch on
g	graph

Definition at line 297 of file branch_stp.c.

References a, BRANCH_STP_VERTEX_NONTERM, BRANCH_STP_VERTEX_TERM, EAT_LAST, fabs(), GRAPH::grad, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, NULL, SCIP_CALL, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetCurrentNode(), SCIPgetLPSolstat(), SCIPhasCurrentNodeLP(), SCIPisPositive(), SCIPnodeGetDepth(), SCIPprobdataGetEdgeVars(), SCIPStpBranchruleApplyVertexChgs(), SCIPvarGetLPSol(), GRAPH::term, and UNKNOWN.

Referenced by SCIP_DECL_BRANCHEXECLP().

◆ branchOnVertex()

static SCIP_RETCODE branchOnVertex	(	SCIP *	scip,
		const GRAPH *	g,
		int	branchvertex
	)

static

branch on specified (Steiner) vertex

Parameters

scip	SCIP data structure
g	graph data structure
branchvertex	the vertex to branch on

Definition at line 372 of file branch_stp.c.

References EAT_LAST, FALSE, flipedge, GRAPH::ieat, GRAPH::inpbeg, Is_term, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCoefLinear(), SCIPaddCoefSetppc(), SCIPaddConsNode(), SCIPcreateChild(), SCIPcreateConsLinear(), SCIPcreateConsSetpart(), SCIPgetUpperbound(), SCIPprobdataGetEdgeVars(), SCIPreleaseCons(), SCIPsnprintf(), GRAPH::term, and TRUE.

Referenced by SCIP_DECL_BRANCHEXECLP(), and SCIP_DECL_BRANCHEXECPS().

◆ SCIP_DECL_BRANCHCOPY()

static SCIP_DECL_BRANCHCOPY ( branchCopyStp )

static

copy method for branchrule plugins (called when SCIP copies plugins)

Definition at line 434 of file branch_stp.c.

References BRANCHRULE_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPbranchruleGetName(), and SCIPincludeBranchruleStp().

◆ SCIP_DECL_BRANCHFREE()

static SCIP_DECL_BRANCHFREE ( branchFreeStp )

static

destructor of branching rule to free user data (called when SCIP is exiting)

Definition at line 448 of file branch_stp.c.

References NULL, SCIP_OKAY, SCIPbranchruleGetData(), SCIPbranchruleSetData(), and SCIPfreeMemory.

◆ SCIP_DECL_BRANCHINIT()

static SCIP_DECL_BRANCHINIT ( branchInitStp )

static

initialization method of branching rule (called after problem was transformed)

Definition at line 464 of file branch_stp.c.

References NULL, SCIP_OKAY, and SCIPbranchruleGetData().

◆ SCIP_DECL_BRANCHEXIT()

static SCIP_DECL_BRANCHEXIT ( branchExitStp )

static

deinitialization method of branching rule (called before transformed problem is freed)

Definition at line 478 of file branch_stp.c.

References NULL, SCIP_OKAY, SCIPbranchruleGetData(), and SCIPstatistic.

◆ SCIP_DECL_BRANCHEXECLP()

static SCIP_DECL_BRANCHEXECLP ( branchExeclpStp )

static

branching execution method for fractional LP solutions

Definition at line 495 of file branch_stp.c.

References BRANCH_STP_ON_LP, BRANCH_STP_ON_LP2, BRANCH_STP_ON_SOL, branchOnVertex(), BRANCHRULE_NAME, isProbCompatible(), NULL, SCIP_BRANCHED, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, SCIPbranchruleGetData(), SCIPbranchruleGetName(), SCIPdebugMessage, SCIPgetProbData(), SCIPprobdataGetGraph(), selectBranchingVertexByDegree(), selectBranchingVertexByLp(), selectBranchingVertexByLp2Flow(), selectBranchingVertexBySol(), GRAPH::stp_type, TRUE, and UNKNOWN.

◆ SCIP_DECL_BRANCHEXECPS()

static SCIP_DECL_BRANCHEXECPS ( branchExecpsStp )

static

branching execution method for not completely fixed pseudo solutions

Definition at line 559 of file branch_stp.c.

References branchOnVertex(), BRANCHRULE_NAME, isProbCompatible(), NULL, SCIP_BRANCHED, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, SCIPbranchruleGetName(), SCIPdebugMessage, SCIPdebugMsg, SCIPgetProbData(), SCIPprobdataGetGraph(), selectBranchingVertexByDegree(), GRAPH::stp_type, and UNKNOWN.

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

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

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

◆ SCIPincludeBranchruleStp()

SCIP_RETCODE SCIPincludeBranchruleStp ( SCIP * 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().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ BRANCHRULE_NAME

◆ BRANCHRULE_DESC

◆ BRANCHRULE_PRIORITY

◆ BRANCHRULE_MAXDEPTH

◆ BRANCHRULE_MAXBOUNDDIST

◆ BRANCHRULE_TMRUNS

◆ BRANCH_STP_ON_LP

◆ BRANCH_STP_ON_LP2

◆ BRANCH_STP_ON_SOL

Function Documentation

◆ isProbCompatible()

◆ selectBranchingVertexByDegree()

◆ selectBranchingVertexBySol()

◆ selectBranchingVertexByLp()

◆ selectBranchingVertexByLp2Flow()

◆ branchOnVertex()

◆ SCIP_DECL_BRANCHCOPY()

◆ SCIP_DECL_BRANCHFREE()

◆ SCIP_DECL_BRANCHINIT()

◆ SCIP_DECL_BRANCHEXIT()

◆ SCIP_DECL_BRANCHEXECLP()

◆ SCIP_DECL_BRANCHEXECPS()

◆ STPStpBranchruleParseConsname()

◆ SCIPStpBranchruleInitNodeState()

◆ SCIPStpBranchruleApplyVertexChgs()

◆ SCIPincludeBranchruleStp()