branch_stp.c
Go to the documentation of this file.
25 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
93 return (graph_typeIsSpgLike(graph) || (graph_pc_isPcMw(graph) && graph->stp_type != STP_BRMWCSP));
257 else if( !rpcmw && graph->head[e] == graph->source ) /* do not change edge going to pseudo-root */
265 assert(SCIPisLT(scip, graph->cost[e], FARAWAY) && SCIPisLT(scip, graph->cost[flipedge(e)], FARAWAY));
512 if( SCIPisLT(scip, inflow, 1.0) && SCIPisPositive(scip, inflow) && fabs(inflow - 0.5) < bestflow )
550 SCIPdebugMessage("maxflow %f on vertex %d, term? %d \n", bestflow, *vertex, Is_term(g->term[*vertex]) );
661 consnamein, 0, NULL, NULL, 1.0, 1.0, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE) );
664 consnameout, 0, NULL, NULL, 0.0, 0.0, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE) );
665 //+ consnameout, 0, NULL, NULL, 0.0, 0.0, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE) );
875 if( probAllowsSolBranching(g) && branchruleGetType(scip, g, branchruledata) != BRANCH_STP_ON_DEGREE )
1011 for( SCIP_NODE* node = SCIPgetCurrentNode(scip); SCIPnodeGetDepth(node) > 0; node = SCIPnodeGetParent(node) )
1141 SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY,
static SCIP_RETCODE selectBranchingVertexByLp2Flow(SCIP *scip, int *vertex, const GRAPH *g)
Definition: branch_stp.c:557
Definition: type_result.h:33
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1840
Definition: graphdefs.h:184
public methods for branch and bound tree
SCIP_RETCODE SCIPsetBranchruleExecPs(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: scip_branch.c:272
SCIP_RETCODE SCIPStpBranchruleGetVertexChgs(SCIP *scip, int *vertexchgs, SCIP_Bool *conflictFound)
Definition: branch_stp.c:977
Definition: struct_scip.h:59
static void applyBranchHistoryToGraph(SCIP *scip, const int *nodestatenew, GRAPH *graph)
Definition: branch_stp.c:191
Definition: struct_var.h:198
includes methods for Steiner tree problem solutions
SCIP_RETCODE SCIPsetBranchruleExit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXIT((*branchexit)))
Definition: scip_branch.c:192
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip_branch.c:160
SCIP_RETCODE SCIPincludeBranchruleStp(SCIP *scip)
Definition: branch_stp.c:1129
SCIP_RETCODE SCIPStpBranchruleGetVertexChgLast(SCIP *scip, int *vertex, SCIP_Bool *isDeleted)
Definition: branch_stp.c:1036
SCIP_RETCODE SCIPStpHeurTMRunLP(SCIP *scip, GRAPH *graph, SCIP_HEUR *heur, int *result, int runs, SCIP_Bool *success)
Definition: heur_tm.c:3509
static SCIP_Bool probAllowsSolBranching(const GRAPH *graph)
Definition: branch_stp.c:89
void SCIPStpBranchruleInitNodeState(const GRAPH *g, int *nodestate)
Definition: branch_stp.c:954
Problem data for stp problem.
void graph_pc_enforceNonLeafTerm(SCIP *, GRAPH *, int)
Definition: graph_pcbase.c:1556
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:144
includes various files containing graph methods used for Steiner tree problems
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:288
static int branchruleGetType(SCIP *scip, const GRAPH *g, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch_stp.c:99
SCIP_RETCODE SCIPincludeBranchruleBasic(SCIP *scip, SCIP_BRANCHRULE **branchruleptr, const char *name, const char *desc, int priority, int maxdepth, SCIP_Real maxbounddist, SCIP_BRANCHRULEDATA *branchruledata)
Definition: scip_branch.c:107
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
Constraint handler for the set partitioning / packing / covering constraints .
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:74
GRAPH * SCIPprobdataGetGraph(SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:2948
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
Definition: cons_linear.c:18162
Definition: struct_tree.h:132
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:240
SCIP_RETCODE STPStpBranchruleParseConsname(int *vertexchgs, const char *consname, SCIP_Bool *conflictFound)
Definition: branch_stp.c:902
Definition: struct_cons.h:37
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:451
SCIP_Bool SCIPprobdataProbIsAdversarial(SCIP *scip)
Definition: probdata_stp.c:3324
SCIP_RETCODE SCIPprobdataAddNewSol(SCIP *scip, SCIP_Real *nval, SCIP_HEUR *heur, SCIP_Bool *success)
Definition: probdata_stp.c:3693
SCIP_RETCODE SCIPStpHeurLocalRun(SCIP *scip, GRAPH *graph, int *solEdges)
Definition: heur_local.c:3899
Definition: type_retcode.h:33
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: scip_branch.c:1008
SCIP_Bool SCIPStpBranchruleIsActive(SCIP *scip)
Definition: branch_stp.c:1099
static int getHighSolDegVertex(const int *nodestatenew, const int *soledges, const GRAPH *graph)
Definition: branch_stp.c:142
internal methods for global SCIP settings
SCIP main data structure.
Definition: struct_branch.h:69
Improvement heuristic for Steiner problems.
Definition: type_lp.h:34
void graph_pc_enforcePseudoTerm(SCIP *, GRAPH *, int)
Definition: graph_pcbase.c:1530
Definition: type_retcode.h:34
SCIP_RETCODE SCIPaddConsNode(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode)
Definition: scip_prob.c:3322
internal methods for problem variables
propagator for Steiner tree problems, using the LP reduced costs
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1850
SCIP_VAR ** SCIPprobdataGetEdgeVars(SCIP *scip)
Definition: probdata_stp.c:3277
SCIP_Bool SCIPStpBranchruleProbIsCompatible(const GRAPH *graph)
Definition: branch_stp.c:1119
Constraint handler for linear constraints in their most general form, .
Steiner vertex branching rule.
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_linear.c:17821
static SCIP_RETCODE selectBranchingVertexBySol(SCIP *scip, int *vertex, SCIP_Bool addsol)
Definition: branch_stp.c:344
SCIP_Bool graph_pc_knotIsFixedTerm(const GRAPH *, int)
Definition: graph_pcbase.c:1257
static SCIP_RETCODE selectBranchingVertexByDegree(SCIP *scip, int *vertex, const GRAPH *g)
Definition: branch_stp.c:280
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1962
SCIP_RETCODE SCIPsetBranchruleInit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINIT((*branchinit)))
Definition: scip_branch.c:176
shortest paths based primal heuristics for Steiner problems
static SCIP_RETCODE selectBranchingVertexByLp(SCIP *scip, int *vertex, const GRAPH *g)
Definition: branch_stp.c:480
Definition: type_result.h:45
SCIP_Bool solstp_isValid(SCIP *scip, const GRAPH *graph, const int *result)
Definition: solstp.c:1650
Definition: objbenders.h:33
void SCIPnodeGetAddedConss(SCIP_NODE *node, SCIP_CONS **addedconss, int *naddedconss, int addedconsssize)
Definition: tree.c:1672
void graph_pc_nonTermToFixedTerm(GRAPH *, int, SCIP_Real *)
Definition: graph_pcbase.c:1115
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
static SCIP_RETCODE branchOnVertex(SCIP *scip, const GRAPH *g, int branchvertex)
Definition: branch_stp.c:632