Scippy

SCIP

Solving Constraint Integer Programs

branch_stp.c File Reference

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/cons_linear.h"
#include "scip/cons_setppc.h"
#include "scip/var.h"
#include "scip/set.h"
#include "scip/struct_scip.h"
#include "graph.h"
#include "heur_tm.h"
#include "solstp.h"
#include "heur_local.h"
#include "branch_stp.h"
#include "prop_stp.h"
#include "probdata_stp.h"
#include "scip/pub_tree.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 BRANCHRULE_TMRUNS_SPG   8
 
#define BRANCH_STP_ON_LP   0
 
#define BRANCH_STP_ON_LP2   1
 
#define BRANCH_STP_ON_SOL   2
 
#define BRANCH_STP_ON_DEGREE   3
 

Functions

static SCIP_Bool probIsCompatible (const GRAPH *graph)
 
static SCIP_Bool probAllowsSolBranching (const GRAPH *graph)
 
static int branchruleGetType (SCIP *scip, const GRAPH *g, SCIP_BRANCHRULEDATA *branchruledata)
 
static int getHighSolDegVertex (const int *nodestatenew, const int *soledges, const GRAPH *graph)
 
static void applyBranchHistoryToGraph (SCIP *scip, const int *nodestatenew, GRAPH *graph)
 
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 (int *vertexchgs, const char *consname, SCIP_Bool *conflictFound)
 
void SCIPStpBranchruleInitNodeState (const GRAPH *g, int *nodestate)
 
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)
 
SCIP_Bool SCIPStpBranchruleProbIsCompatible (const GRAPH *graph)
 
SCIP_RETCODE SCIPincludeBranchruleStp (SCIP *scip)
 

Macro Definition Documentation

◆ BRANCHRULE_NAME

◆ BRANCHRULE_DESC

#define BRANCHRULE_DESC   "stp branching on vertices"

Definition at line 44 of file branch_stp.c.

Referenced by SCIPincludeBranchruleStp().

◆ BRANCHRULE_PRIORITY

#define BRANCHRULE_PRIORITY   10000000

Definition at line 45 of file branch_stp.c.

Referenced by SCIPincludeBranchruleStp().

◆ BRANCHRULE_MAXDEPTH

#define BRANCHRULE_MAXDEPTH   -1

Definition at line 46 of file branch_stp.c.

Referenced by SCIPincludeBranchruleStp().

◆ BRANCHRULE_MAXBOUNDDIST

#define BRANCHRULE_MAXBOUNDDIST   1.0

Definition at line 47 of file branch_stp.c.

Referenced by SCIPincludeBranchruleStp().

◆ BRANCHRULE_TMRUNS

#define BRANCHRULE_TMRUNS   20

Definition at line 48 of file branch_stp.c.

Referenced by selectBranchingVertexBySol().

◆ BRANCHRULE_TMRUNS_SPG

#define BRANCHRULE_TMRUNS_SPG   8

Definition at line 49 of file branch_stp.c.

Referenced by selectBranchingVertexBySol().

◆ BRANCH_STP_ON_LP

#define BRANCH_STP_ON_LP   0

◆ BRANCH_STP_ON_LP2

#define BRANCH_STP_ON_LP2   1

Definition at line 51 of file branch_stp.c.

Referenced by branchruleGetType(), and SCIP_DECL_BRANCHEXECLP().

◆ BRANCH_STP_ON_SOL

#define BRANCH_STP_ON_SOL   2

Definition at line 52 of file branch_stp.c.

Referenced by branchruleGetType(), and SCIP_DECL_BRANCHEXECLP().

◆ BRANCH_STP_ON_DEGREE

#define BRANCH_STP_ON_DEGREE   3

Definition at line 53 of file branch_stp.c.

Referenced by SCIP_DECL_BRANCHEXECPS().

Function Documentation

◆ probIsCompatible()

static SCIP_Bool probIsCompatible ( const GRAPH graph)
inlinestatic

check whether branching-rule is compatible with given problem type

Parameters
graphgraph

Definition at line 79 of file branch_stp.c.

References STP_DCSTP, and GRAPH::stp_type.

Referenced by SCIP_DECL_BRANCHEXECLP(), SCIP_DECL_BRANCHEXECPS(), and SCIPStpBranchruleProbIsCompatible().

◆ probAllowsSolBranching()

static SCIP_Bool probAllowsSolBranching ( const GRAPH graph)
inlinestatic

check whether given problem type allows for solution based branching

Parameters
graphgraph

Definition at line 89 of file branch_stp.c.

References graph_pc_isPcMw(), graph_typeIsSpgLike(), STP_BRMWCSP, and GRAPH::stp_type.

Referenced by branchruleGetType(), SCIP_DECL_BRANCHEXECPS(), and selectBranchingVertexBySol().

◆ branchruleGetType()

static int branchruleGetType ( SCIP scip,
const GRAPH g,
SCIP_BRANCHRULEDATA branchruledata 
)
inlinestatic

check whether branching-rule is compatible with given problem type

Parameters
scipSCIP data structure
ggraph
branchruledatadata

Definition at line 99 of file branch_stp.c.

References BRANCH_STP_ON_LP, BRANCH_STP_ON_LP2, BRANCH_STP_ON_SOL, graph_pc_isPcMw(), probAllowsSolBranching(), SCIPprobdataProbIsAdversarial(), and TRUE.

Referenced by SCIP_DECL_BRANCHEXECLP(), and SCIP_DECL_BRANCHEXECPS().

◆ getHighSolDegVertex()

static int getHighSolDegVertex ( const int *  nodestatenew,
const int *  soledges,
const GRAPH graph 
)
static

gets vertex with highest degree in solution

Parameters
nodestatenewnode state derived from branching history
soledgessolution edges mark
graphgraph

Definition at line 142 of file branch_stp.c.

References BRANCH_STP_VERTEX_NONTERM, CONNECT, EAT_LAST, FALSE, flipedge, GRAPH::grad, graph_pc_isPcMw(), Is_pseudoTerm, Is_term, GRAPH::knots, nnodes, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, GRAPH::term, and TRUE.

Referenced by selectBranchingVertexBySol().

◆ applyBranchHistoryToGraph()

static void applyBranchHistoryToGraph ( SCIP scip,
const int *  nodestatenew,
GRAPH graph 
)
static

◆ 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
scipSCIP data structure
vertexthe vertex to branch on
ggraph

Definition at line 280 of file branch_stp.c.

References BRANCH_STP_VERTEX_NONTERM, GRAPH::extended, FALSE, GRAPH::grad, graph_pc_isPcMw(), Is_pseudoTerm, Is_term, GRAPH::knots, nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetCurrentNode(), SCIPnodeGetDepth(), SCIPStpBranchruleGetVertexChgs(), SCIPStpBranchruleInitNodeState(), GRAPH::term, TRUE, and UNKNOWN.

Referenced by SCIP_DECL_BRANCHEXECLP(), and SCIP_DECL_BRANCHEXECPS().

◆ selectBranchingVertexBySol()

◆ selectBranchingVertexByLp()

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

◆ selectBranchingVertexByLp2Flow()

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

◆ branchOnVertex()

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

branch on specified (Steiner) vertex

Parameters
scipSCIP data structure
ggraph data structure
branchvertexthe vertex to branch on

Definition at line 632 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(), SCIPaddConsNode(), SCIPcreateChild(), SCIPcreateConsLinear(), 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 699 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 713 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 729 of file branch_stp.c.

References FALSE, 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 743 of file branch_stp.c.

References SCIP_OKAY, and SCIPstatistic.

◆ SCIP_DECL_BRANCHEXECLP()

◆ SCIP_DECL_BRANCHEXECPS()

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

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

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

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

◆ SCIPincludeBranchruleStp()