Detailed Description
Steiner vertex branching rule.
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 |
Macro Definition Documentation
◆ BRANCHRULE_NAME
#define BRANCHRULE_NAME "stp" |
Definition at line 43 of file branch_stp.c.
Referenced by SCIP_DECL_BRANCHCOPY(), SCIP_DECL_BRANCHEXECLP(), SCIP_DECL_BRANCHEXECPS(), SCIPincludeBranchruleStp(), SCIPStpBranchruleGetVertexChgLast(), SCIPStpBranchruleGetVertexChgs(), and SCIPStpBranchruleIsActive().
◆ 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 |
Definition at line 50 of file branch_stp.c.
Referenced by branchruleGetType(), SCIP_DECL_BRANCHEXECLP(), and SCIPincludeBranchruleStp().
◆ 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()
check whether branching-rule is compatible with given problem type
- Parameters
-
graph graph
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()
check whether given problem type allows for solution based branching
- Parameters
-
graph graph
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()
|
inlinestatic |
check whether branching-rule is compatible with given problem type
- Parameters
-
scip SCIP data structure g graph branchruledata data
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 |
gets vertex with highest degree in solution
- Parameters
-
nodestatenew node state derived from branching history soledges solution edges mark graph graph
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 |
applies branching-changes to graph
- Parameters
-
scip SCIP data structure nodestatenew node state derived from branching history graph graph
Definition at line 191 of file branch_stp.c.
References BLOCKED, BRANCH_STP_VERTEX_KILLED, BRANCH_STP_VERTEX_TERM, GRAPH::cost, EAT_LAST, GRAPH::extended, FARAWAY, flipedge, GRAPH::grad, graph_knot_chg(), graph_pc_enforceNonLeafTerm(), graph_pc_enforcePseudoTerm(), graph_pc_isMw(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_nonTermToFixedTerm(), GRAPH::head, Is_anyTerm, Is_nonleafTerm, Is_pseudoTerm, Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIPisEQ(), SCIPisLT(), GRAPH::source, STP_TERM, GRAPH::term, and GRAPH::term2edge.
Referenced by selectBranchingVertexBySol().
◆ selectBranchingVertexByDegree()
|
static |
select vertex to branch on by choosing vertex of highest degree
- Parameters
-
scip SCIP data structure vertex the vertex to branch on g graph
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()
|
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 344 of file branch_stp.c.
References applyBranchHistoryToGraph(), BMScopyMemoryArray, BRANCHRULE_TMRUNS, BRANCHRULE_TMRUNS_SPG, CONNECT, GRAPH::cost, GRAPH::cost_org_pc, GRAPH::edges, GRAPH::extended, FALSE, getHighSolDegVertex(), graph_get_nEdges(), graph_get_nNodes(), graph_knot_chg(), graph_pc_isPc(), graph_pc_isPcMw(), graph_typeIsSpgLike(), graph_valid(), nnodes, NULL, GRAPH::prize, probAllowsSolBranching(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetCurrentNode(), SCIPnodeGetDepth(), SCIPprobdataAddNewSol(), SCIPprobdataGetGraph2(), SCIPprobdataGetNVars(), SCIPStpBranchruleGetVertexChgs(), SCIPStpBranchruleInitNodeState(), SCIPStpHeurLocalRun(), SCIPStpHeurTMRunLP(), solstp_isValid(), GRAPH::term, GRAPH::term2edge, GRAPH::terms, and UNKNOWN.
Referenced by SCIP_DECL_BRANCHEXECLP(), and SCIP_DECL_BRANCHEXECPS().
◆ selectBranchingVertexByLp()
|
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 480 of file branch_stp.c.
References a, BRANCH_STP_VERTEX_NONTERM, EAT_LAST, FALSE, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetCurrentNode(), SCIPgetLPSolstat(), SCIPhasCurrentNodeLP(), SCIPisLT(), SCIPisPositive(), SCIPnodeGetDepth(), SCIPprobdataGetEdgeVars(), SCIPStpBranchruleGetVertexChgs(), SCIPStpBranchruleInitNodeState(), SCIPvarGetLPSol(), GRAPH::term, and UNKNOWN.
Referenced by SCIP_DECL_BRANCHEXECLP().
◆ selectBranchingVertexByLp2Flow()
|
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 557 of file branch_stp.c.
References a, BRANCH_STP_VERTEX_NONTERM, EAT_LAST, FALSE, GRAPH::grad, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetCurrentNode(), SCIPgetLPSolstat(), SCIPhasCurrentNodeLP(), SCIPisPositive(), SCIPnodeGetDepth(), SCIPprobdataGetEdgeVars(), SCIPStpBranchruleGetVertexChgs(), SCIPStpBranchruleInitNodeState(), SCIPvarGetLPSol(), GRAPH::term, and UNKNOWN.
Referenced by SCIP_DECL_BRANCHEXECLP().
◆ branchOnVertex()
|
static |
branch on specified (Steiner) vertex
- Parameters
-
scip SCIP data structure g graph data structure branchvertex the 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 |
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 |
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 |
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 |
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()
|
static |
branching execution method for fractional LP solutions
Definition at line 752 of file branch_stp.c.
References BRANCH_STP_ON_LP, BRANCH_STP_ON_LP2, BRANCH_STP_ON_SOL, branchOnVertex(), BRANCHRULE_NAME, branchruleGetType(), FALSE, NULL, probIsCompatible(), SCIP_BRANCHED, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_ERROR, SCIP_OKAY, SCIPbranchruleGetData(), SCIPbranchruleGetName(), SCIPdebugMessage, SCIPgetProbData(), SCIPprobdataGetGraph(), selectBranchingVertexByDegree(), selectBranchingVertexByLp(), selectBranchingVertexByLp2Flow(), selectBranchingVertexBySol(), TRUE, and UNKNOWN.
◆ SCIP_DECL_BRANCHEXECPS()
|
static |
branching execution method for not completely fixed pseudo solutions
Definition at line 835 of file branch_stp.c.
References BRANCH_STP_ON_DEGREE, branchOnVertex(), BRANCHRULE_NAME, branchruleGetType(), FALSE, NULL, probAllowsSolBranching(), probIsCompatible(), SCIP_BRANCHED, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, SCIPbranchruleGetData(), SCIPbranchruleGetName(), SCIPdebugMessage, SCIPgetProbData(), SCIPprobdataGetGraph(), selectBranchingVertexByDegree(), selectBranchingVertexBySol(), TRUE, and UNKNOWN.
◆ 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().
◆ 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().
◆ 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()
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().
◆ SCIPStpBranchruleProbIsCompatible()
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().
◆ SCIPincludeBranchruleStp()
SCIP_RETCODE SCIPincludeBranchruleStp | ( | SCIP * | 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().