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/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"

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

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

◆ selectBranchingVertexByLp()

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

select vertex to branch on by using LP

Parameters
sciporiginal SCIP data structure
vertexthe vertex to branch on
ggraph

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

◆ branchOnVertex()

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

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

◆ SCIP_DECL_BRANCHEXECPS()

static SCIP_DECL_BRANCHEXECPS ( branchExecpsStp  )
static

◆ 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
scipSCIP data structure
vertexchgsarray to store changes or NULL
graphgraph to modify or NULL
consnameconstraint name
deletehistorydelete 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
ggraph data structure
nodestatenode 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
scipSCIP data structure
vertexchgsarray to store changes or NULL
graphgraph 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()