Scippy

SCIP

Solving Constraint Integer Programs

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_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

◆ BRANCH_STP_VERTEX_NONTERM

◆ BRANCH_STP_VERTEX_TERM

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
vertexchgsarray to store changes
consnameconstraint name
conflictFoundconflict 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 
)

◆ SCIPStpBranchruleGetVertexChgLast()

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

get last change

Parameters
scipSCIP data structure
vertexchanged vertex
isDeleteddeleted? (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
scipSCIP 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
ggraph data structure
nodestatenode 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()

◆ SCIPStpBranchruleProbIsCompatible()

SCIP_Bool SCIPStpBranchruleProbIsCompatible ( const GRAPH graph)

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

Parameters
graphgraph

Definition at line 1119 of file branch_stp.c.

References probIsCompatible().

Referenced by SCIP_DECL_CONSSEPALP().