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