probdata_stp.c
Go to the documentation of this file.
23 * This file implements the problem data for Steiner problems. For more details see \ref STP_PROBLEMDATA page.
29 * The problem data contains the (preprocessed) graph, several constraints and further information.
31 * The function SCIPprobdataCreate(), which is called in the \ref reader_stp.c "reader plugin", parses the input file
32 * reduces the graph, initializes the problem data structure and creates the problem in the SCIP environment.
38 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
341 SCIPdebugMessage("try to add reduction solution with obj=%f, success=%d \n", solval + probdata->offset, success);
444 if( probdata->stp_type == STP_PCSPG || probdata->stp_type == STP_RPCSPG || probdata->stp_type == STP_MWCSP )
606 /* @todo with presolving contractions enabled one might set rhs = rhs - (number of fixed edges) */
631 SCIP_CALL( SCIPcreateConsLinear ( scip, &(probdata->budgetcons), "BudgetConstraint", 0, NULL, NULL,
632 -SCIPinfinity(scip), graph->budget, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
665 -SCIPinfinity(scip), (SCIP_Real)graph->maxdeg[k], TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
705 SCIP_CALL( SCIPcreateConsLinear ( scip, &(probdata->prizecons), consname, 0, NULL, NULL, 1.0, 1.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE));
721 SCIP_CALL( SCIPcreateConsSetpack(scip, &(probdata->prizesymcons[r]), consname, 0, NULL, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ));
740 SCIP_CALL( SCIPcreateConsLinear ( scip, &(probdata->prizecyclecons[ro2]), consname, 0, NULL, NULL,
745 SCIP_CALL( SCIPcreateConsLinear ( scip, &(probdata->prizecyclecons[ro2]), consname, 0, NULL, NULL,
920 for( int inedge_j = graph->inpbeg[node_j]; inedge_j != EAT_LAST; inedge_j = graph->ieat[inedge_j] )
989 SCIP_CALL( SCIPcreateConsLinear ( scip, &( probdata->edgecons[t * nedges + e] ), consname, 0, NULL, NULL,
990 -SCIPinfinity(scip), 0.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, probdata->mode == STP_MODE_PRICE, FALSE, FALSE, FALSE) );
1018 SCIP_CALL( SCIPcreateConsLinear ( scip, &(probdata->pathcons[t]), consname, 0, NULL, NULL, 1.0, SCIPinfinity(scip),
1044 SCIP_CALL( SCIPcreateConsLinear(scip, &( probdata->pathcons[t * (nnodes - 1) + k2] ), consname,
1053 SCIP_CALL( SCIPcreateConsLinear(scip, &( probdata->pathcons[t * (nnodes - 1) + k2] ), consname,
1148 SCIP_CALL( SCIPcreateVarBasic(scip, &probdata->edgevars[e], varname, 0.0, 1.0, graph->cost[e], SCIP_VARTYPE_BINARY) );
1192 SCIP_CALL( SCIPaddCoefLinear(scip, probdata->degcons[k], probdata->edgevars[flipedge(e)], 1.0) );
1230 SCIP_CALL(SCIPchgVarBranchPriority(scip, probdata->edgevars[e], 100 + (int)(100.0 * graph->prize[head])));
1263 SCIP_CALL(SCIPaddCoefLinear(scip, probdata->prizecyclecons[e], probdata->edgevars[flipedge(e)], 1.0));
1357 SCIP_CALL( SCIPaddCoefLinear(scip, probdata->prizesymcons[prev], probdata->edgevars[prootedge], 1.0) );
1362 SCIP_CALL(SCIPaddCoefLinear(scip, probdata->prizesymcons[s], probdata->edgevars[twinrootedge], -1.0));
1391 SCIP_CALL( SCIPcreateVarBasic(scip, &var, varname, 0.0, 1.0, graph->cost[e], SCIP_VARTYPE_BINARY) );
1435 SCIP_CALL( SCIPcreateVarBasic(scip, &var, varname, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
1444 SCIP_CALL( SCIPaddCoefLinear(scip, probdata->edgecons[t * nedges + path[tail].edge], var, 1.0));
1477 (void)SCIPsnprintf(varname, SCIP_MAXSTRLEN, "FlowVar%d.%d_%d", t, graph->tail[e], graph->head[e]);
1478 SCIP_CALL( SCIPcreateVarBasic(scip, &var, varname, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
1481 SCIP_CALL( SCIPaddCoefLinear(scip, probdata->edgecons[t * nedges + e], probdata->flowvars[t * nedges + e], 1.0) );
1496 SCIP_CALL( SCIPaddCoefLinear(scip, probdata->pathcons[t * (nnodes - 1) + k2], probdata->flowvars[t * nedges + e], 1.0) );
1502 SCIP_CALL( SCIPaddCoefLinear(scip, probdata->pathcons[t * (nnodes - 1) + k2], probdata->flowvars[t * nedges + e], -1.0) );
1526 SCIP_CALL( SCIPcreateVarBasic(scip, &probdata->offsetvar, varname, 1.0, 1.0, offset, SCIP_VARTYPE_INTEGER) );
1615 /* if the problem is a Prize-Collecting-STP or a Maximum Weight Connected Subgraph Problem, additional constraints are required */
1753 graph, NULL, NULL, soledge, 32, graph->source, graph->cost, graph->cost, NULL, NULL, &success));
1921 if( cyclecons == STP_CONS_ALWAYS || (cyclecons == STP_CONS_AUTOMATIC && graph->edges <= CYC_CONS_LIMIT) )
1924 if( symcons == STP_CONS_ALWAYS || (symcons == STP_CONS_AUTOMATIC && graph->terms <= SYM_CONS_LIMIT) )
2016 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcedata->offsetvar, &((*targetdata)->offsetvar), varmap, consmap, global, &success) );
2034 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcedata->edgevars[v], &((*targetdata)->edgevars[v]), varmap, consmap, global, &success) );
2051 SCIPgetConsCopy(sourcescip, scip, sourcedata->degcons[c], &((*targetdata)->degcons[c]), SCIPconsGetHdlr(sourcedata->degcons[c]),
2052 varmap, consmap, SCIPconsGetName(sourcedata->degcons[c]), SCIPconsIsInitial(sourcedata->degcons[c]),
2064 if( sourcedata->stp_type == STP_PCSPG || sourcedata->stp_type == STP_RPCSPG || sourcedata->stp_type == STP_MWCSP )
2070 SCIP_CALL( SCIPgetConsCopy(sourcescip, scip, sourcedata->flowbcons[c], &((*targetdata)->flowbcons[c]),
2096 SCIPgetConsCopy(sourcescip, scip, sourcedata->prizecyclecons[c], &((*targetdata)->prizecyclecons[c]),
2097 SCIPconsGetHdlr(sourcedata->prizecyclecons[c]), varmap, consmap, SCIPconsGetName(sourcedata->prizecyclecons[c]),
2098 SCIPconsIsInitial(sourcedata->prizecyclecons[c]), SCIPconsIsSeparated(sourcedata->prizecyclecons[c]),
2099 SCIPconsIsEnforced(sourcedata->prizecyclecons[c]), SCIPconsIsChecked(sourcedata->prizecyclecons[c]),
2100 SCIPconsIsPropagated(sourcedata->prizecyclecons[c]), SCIPconsIsLocal(sourcedata->prizecyclecons[c]),
2101 SCIPconsIsModifiable(sourcedata->prizecyclecons[c]), SCIPconsIsDynamic(sourcedata->prizecyclecons[c]),
2102 SCIPconsIsRemovable(sourcedata->prizecyclecons[c]), SCIPconsIsStickingAtNode(sourcedata->prizecyclecons[c]), global,
2121 SCIPgetConsCopy(sourcescip, scip, sourcedata->prizesymcons[c], &((*targetdata)->prizesymcons[c]),
2122 SCIPconsGetHdlr(sourcedata->prizesymcons[c]), varmap, consmap, SCIPconsGetName(sourcedata->prizesymcons[c]),
2123 SCIPconsIsInitial(sourcedata->prizesymcons[c]), SCIPconsIsSeparated(sourcedata->prizesymcons[c]),
2124 SCIPconsIsEnforced(sourcedata->prizesymcons[c]), SCIPconsIsChecked(sourcedata->prizesymcons[c]),
2125 SCIPconsIsPropagated(sourcedata->prizesymcons[c]), SCIPconsIsLocal(sourcedata->prizesymcons[c]),
2126 SCIPconsIsModifiable(sourcedata->prizesymcons[c]), SCIPconsIsDynamic(sourcedata->prizesymcons[c]),
2127 SCIPconsIsRemovable(sourcedata->prizesymcons[c]), SCIPconsIsStickingAtNode(sourcedata->prizesymcons[c]), global,
2138 SCIPgetConsCopy(sourcescip, scip, sourcedata->prizecons, &((*targetdata)->prizecons), SCIPconsGetHdlr(sourcedata->prizecons),
2139 varmap, consmap, SCIPconsGetName(sourcedata->prizecons), SCIPconsIsInitial(sourcedata->prizecons),
2154 SCIPgetConsCopy(sourcescip, scip, sourcedata->hopcons, &((*targetdata)->hopcons), SCIPconsGetHdlr(sourcedata->hopcons),
2169 SCIPgetConsCopy(sourcescip, scip, sourcedata->budgetcons, &((*targetdata)->budgetcons), SCIPconsGetHdlr(sourcedata->budgetcons),
2170 varmap, consmap, SCIPconsGetName(sourcedata->budgetcons), SCIPconsIsInitial(sourcedata->budgetcons),
2194 SCIPconsGetHdlr(sourcedata->edgecons[c]), varmap, consmap, SCIPconsGetName(sourcedata->edgecons[c]),
2199 SCIPconsIsRemovable(sourcedata->edgecons[c]), SCIPconsIsStickingAtNode(sourcedata->edgecons[c]), global, &success));
2207 SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->edgecons, sourcedata->realnterms * sourcedata->nedges));
2212 SCIPconsGetHdlr(sourcedata->edgecons[c]), varmap, consmap, SCIPconsGetName(sourcedata->edgecons[c]),
2217 SCIPconsIsRemovable(sourcedata->edgecons[c]), SCIPconsIsStickingAtNode(sourcedata->edgecons[c]), global, &success));
2232 SCIPconsGetHdlr(sourcedata->pathcons[c]), varmap, consmap, SCIPconsGetName(sourcedata->pathcons[c]),
2237 SCIPconsIsRemovable(sourcedata->pathcons[c]), SCIPconsIsStickingAtNode(sourcedata->pathcons[c]), global, &success));
2254 SCIPconsGetHdlr(sourcedata->pathcons[c]), varmap, consmap, SCIPconsGetName(sourcedata->pathcons[c]),
2259 SCIPconsIsRemovable(sourcedata->pathcons[c]), SCIPconsIsStickingAtNode(sourcedata->pathcons[c]), global, &success));
2268 SCIPgetVarCopy(sourcescip, scip, sourcedata->flowvars[v], &((*targetdata)->flowvars[v]), varmap, consmap, global, &success));
2276 SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->flowvars, sourcedata->realnterms * sourcedata->nedges));
2277 SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->pathcons, sourcedata->realnterms * (sourcedata->nnodes - 1)));
2282 SCIPconsGetHdlr(sourcedata->pathcons[c]), varmap, consmap, SCIPconsGetName(sourcedata->pathcons[c]),
2287 SCIPconsIsRemovable(sourcedata->pathcons[c]), SCIPconsIsStickingAtNode(sourcedata->pathcons[c]), global, &success));
2296 SCIPgetVarCopy(sourcescip, scip, sourcedata->flowvars[v], &((*targetdata)->flowvars[v]), varmap, consmap, global, &success));
2428 SCIP_CALL( SCIPtransformVars(scip, sourcedata->nvars, sourcedata->edgevars, (*targetdata)->edgevars) );
2439 SCIP_CALL( SCIPtransformConss(scip, sourcedata->nnodes, sourcedata->degcons, (*targetdata)->degcons) );
2444 SCIP_CALL( SCIPtransformConss(scip, sourcedata->nnonterms, sourcedata->flowbcons, (*targetdata)->flowbcons) );
2452 SCIP_CALL( SCIPtransformConss(scip, sourcedata->nedges, sourcedata->prizecyclecons, (*targetdata)->prizecyclecons) );
2463 SCIP_CALL( SCIPtransformConss(scip, i, sourcedata->prizesymcons, (*targetdata)->prizesymcons) );
2481 SCIP_CALL(SCIPtransformConss(scip, sourcedata->nedges, sourcedata->edgecons, (*targetdata)->edgecons));
2485 SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->edgecons, sourcedata->realnterms * sourcedata->nedges));
2486 SCIP_CALL(SCIPtransformConss(scip, sourcedata->realnterms * sourcedata->nedges, sourcedata->edgecons, (*targetdata)->edgecons));
2493 SCIP_CALL(SCIPtransformConss(scip, sourcedata->realnterms, sourcedata->pathcons, (*targetdata)->pathcons));
2502 SCIP_CALL(SCIPtransformConss(scip, (sourcedata->nnodes - 1), sourcedata->pathcons, (*targetdata)->pathcons));
2503 SCIP_CALL(SCIPtransformVars(scip, sourcedata->nedges, sourcedata->flowvars, (*targetdata)->flowvars));
2507 SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->flowvars, sourcedata->realnterms * sourcedata->nedges));
2508 SCIP_CALL(SCIPallocMemoryArray(scip, &(*targetdata)->pathcons, sourcedata->realnterms * (sourcedata->nnodes - 1)));
2509 SCIP_CALL(SCIPtransformConss(scip, sourcedata->realnterms * (sourcedata->nnodes - 1), sourcedata->pathcons, (*targetdata)->pathcons));
2510 SCIP_CALL(SCIPtransformVars(scip, sourcedata->nedges * sourcedata->realnterms, sourcedata->flowvars, (*targetdata)->flowvars));
2564 if( probdata->stp_type == STP_MWCSP || probdata->stp_type == STP_RMWCSP || probdata->stp_type == STP_BRMWCSP )
2665 printf("\n using SoPlex specific parameters (use of commercial LP solver is recommended!) \n\n");
2676 SCIP_CALL( SCIPsetRealParam(scip, "cutselection/hybrid/minorthoroot", 0.4) ); // todo tune > 0.4
2847 useNodeSol = (graph_pc_isPcMw(graph) || graph_typeIsSpgLike(graph)) && (reduction != STP_REDUCTION_NONE);
2911 if( (usedp == STP_USEDP_ALWAYS || SCIPStpDpRelaxIsPromising(scip, graph)) && graph->terms > 1 )
3403 if( !SCIPisZero(scip, SCIPgetSolVal(scip, sol, edgevars[e])) || !SCIPisZero(scip, SCIPgetSolVal(scip, sol, edgevars[e + 1])) )
3475 || graph->stp_type == STP_NWSPG || graph->stp_type == STP_DHCSTP || graph->stp_type == STP_GSTP
3613 SCIPinfoMessage(scip, file, "E %d %d\n", nodenumber[graph->orgtail[e]] + 1, nodenumber[graph->orghead[e]] + 1);
3695 SCIP_Real* nval, /**< array [0..nvars], nval[v] = 1 if node v is in the solution, nval[v] = 0 if not */
3719 /* create path variables (Price mode) or set the flow vars (Flow mode) corresponding to the new solution */
3737 SCIP_CALL( SCIPallocMemoryArray(scip, &flowvals, nedges * (probdata->bigt ? 1 : realnterms)) );
3740 /* allocate memory for the edgecost and the path array (both used for computing shortest paths) */
3776 SCIP_CALL( SCIPcreateVarBasic(scip, &var, varname, 0.0, SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS) );
3795 SCIP_CALL( SCIPaddCoefLinear(scip, probdata->edgecons[t * nedges + path[tail].edge], var, 1.0) );
3829 SCIP_CALL( SCIPsetSolVals(scip, sol, nedges * (probdata->bigt ? 1 : realnterms) , probdata->flowvars, flowvals) );
3851 if( SCIPisGT(scip, nval[e], SCIPvarGetUbGlobal(edgevars[e])) || SCIPisGT(scip, SCIPvarGetLbGlobal(edgevars[e]), nval[e]) )
4003 if( probdata->stp_type == STP_MWCSP || probdata->stp_type == STP_RMWCSP || probdata->stp_type == STP_BRMWCSP )
static SCIP_RETCODE createInitialCuts(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:1718
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
Definition: graphdefs.h:274
SCIP_RETCODE SCIPgetStringParam(SCIP *scip, const char *name, char **value)
Definition: scip_param.c:336
SCIP_RETCODE SCIPgetCharParam(SCIP *scip, const char *name, char *value)
Definition: scip_param.c:317
SCIP_RETCODE solstp_addSolToProb(SCIP *scip, const GRAPH *g, const int *soledge, SCIP_HEUR *heur, SCIP_Bool *success)
Definition: solstp.c:1279
static SCIP_RETCODE createVariables(SCIP *scip, SCIP_PROBDATA *probdata, SCIP_Real offset)
Definition: probdata_stp.c:1100
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_setppc.c:9371
SCIP_Bool SCIPprobdataObjIsIntegral(SCIP *scip)
Definition: probdata_stp.c:3308
Definition: graphdefs.h:184
Definition: struct_scip.h:59
SCIP_RETCODE dualascent_execDegCons(SCIP *scip, const GRAPH *g, const int *result, const DAPARAMS *daparams, SCIP_Real *RESTRICT redcost, SCIP_Real *objval)
Definition: dualascent.c:1256
SCIP_RETCODE SCIPaddOrigObjoffset(SCIP *scip, SCIP_Real addval)
Definition: scip_prob.c:1288
SCIP_CONS ** SCIPprobdataGetEdgeConstraints(SCIP *scip)
Definition: probdata_stp.c:3218
static SCIP_RETCODE setStpSolvingMode(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:280
Constraint handler for Steiner problems.
SCIP_RETCODE reduce_solGetEdgesol(SCIP *, GRAPH *, REDSOL *, SCIP_Real *, int *)
Definition: reduce_sol.c:1197
static SCIP_RETCODE freeConstraintsNonCutModel(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:490
void SCIPprobdataSetOffset(SCIP_PROBDATA *probdata, SCIP_Real offset)
Definition: probdata_stp.c:2973
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:298
SCIP_RETCODE reduce_solInit(SCIP *, const GRAPH *, SCIP_Bool, REDSOL **)
Definition: reduce_sol.c:687
SCIP_RETCODE SCIPsetProbCopy(SCIP *scip, SCIP_DECL_PROBCOPY((*probcopy)))
Definition: scip_prob.c:296
SCIP_RETCODE SCIPaddSolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool *stored)
Definition: scip_sol.c:3015
Definition: type_result.h:49
static SCIP_RETCODE createModel(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:1538
SCIP_RETCODE graph_findCentralTerminal(SCIP *, const GRAPH *, int, int *)
Definition: graph_util.c:410
Definition: dualascent.h:39
void graph_path_exec(SCIP *, const GRAPH *, int, int, const SCIP_Real *, PATH *)
Definition: graph_path.c:541
SCIP_RETCODE SCIPprobdataCreateFromGraph(SCIP *scip, SCIP_Real offset, const char *probname, SCIP_Bool isSubProb, GRAPH *graph_move)
Definition: probdata_stp.c:2784
Definition: struct_var.h:198
void SCIPsplitFilename(char *filename, char **path, char **name, char **extension, char **compression)
Definition: misc.c:10974
includes methods for Steiner tree problem solutions
static SCIP_RETCODE createBudgetConstraint(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:617
SCIP_RETCODE SCIPStpHeurTMRun(SCIP *scip, enum PCMW_TmMode pcmw_tmmode, GRAPH *graph, int *starts, const SCIP_Real *prize, int *best_result, int runs, int bestincstart, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *hopfactor, SCIP_Real *nodepriority, SCIP_Bool *success)
Definition: heur_tm.c:3418
SCIP_RETCODE SCIPchgVarUbLazy(SCIP *scip, SCIP_VAR *var, SCIP_Real lazyub)
Definition: scip_var.c:5161
dual-ascent and reduction based primal heuristic for Steiner problems
SCIP_RETCODE SCIPtransformConss(SCIP *scip, int nconss, SCIP_CONS **conss, SCIP_CONS **transconss)
Definition: scip_cons.c:1562
SCIP_RETCODE SCIPsetProbExitsol(SCIP *scip, SCIP_DECL_PROBEXITSOL((*probexitsol)))
Definition: scip_prob.c:275
SCIP_RETCODE SCIPprobdataWriteIntermediateSolution(SCIP *scip)
Definition: probdata_stp.c:3419
Includes dual-ascent for classic Steiner tree and some variants.
static SCIP_RETCODE probdataCreate(SCIP *scip, SCIP_PROBDATA **probdata, GRAPH *graph)
Definition: probdata_stp.c:238
void SCIPStpBranchruleInitNodeState(const GRAPH *g, int *nodestate)
Definition: branch_stp.c:954
miscellaneous datastructures
Problem data for stp problem.
SCIP_RETCODE graph_grid_coordinates(SCIP *, int **, int **, int *, int, int)
Definition: graph_grid.c:486
includes various files containing graph methods used for Steiner tree problems
Definition: type_var.h:53
SCIP_RETCODE SCIPwriteOrigProblem(SCIP *scip, const char *filename, const char *extension, SCIP_Bool genericnames)
Definition: scip_prob.c:599
Definition: graphdefs.h:284
SCIP_RETCODE SCIPsetProbData(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: scip_prob.c:1012
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
Definition: scip_var.c:185
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
SCIP_Bool SCIPStpcomponentsAllowsDecomposition(SCIP *scip)
Definition: cons_stpcomponents.c:689
SCIP_RETCODE graph_pack(SCIP *, GRAPH *, GRAPH **, REDSOL *, SCIP_Bool)
Definition: graph_base.c:1324
static SCIP_RETCODE createConstraints(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:954
Constraint handler for the set partitioning / packing / covering constraints .
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:594
SCIP_Real reduce_solGetUpperBoundWithOffset(const REDSOL *)
Definition: reduce_sol.c:1263
SCIP_Bool SCIPStpDpRelaxIsPromising(SCIP *scip, GRAPH *graph)
Definition: relax_stpdp.c:239
SCIP_RETCODE SCIPprobdataWriteLogfileEnd(SCIP *scip)
Definition: probdata_stp.c:3987
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
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:199
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
Definition: scip_prob.c:170
SCIP_RETCODE SCIPcreateOrigSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:556
SCIP_RETCODE dualascent_exec(SCIP *scip, const GRAPH *g, const int *result, const DAPARAMS *daparams, SCIP_Real *RESTRICT redcost, SCIP_Real *objval)
Definition: dualascent.c:1191
static SCIP_RETCODE addCut(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff)
Definition: cons_logicor.c:1665
SCIP_RETCODE SCIPtransformVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
Definition: scip_var.c:1386
Components constraint handler for Steiner problems.
Definition: struct_sol.h:64
SCIP_RETCODE STPStpBranchruleParseConsname(int *vertexchgs, const char *consname, SCIP_Bool *conflictFound)
Definition: branch_stp.c:902
void SCIPprobdataWriteLogLine(SCIP *scip, const char *formatstr,...)
Definition: probdata_stp.c:3659
Definition: heur_tm.h:48
SCIP_RETCODE SCIPprobdataWriteSolution(SCIP *scip, FILE *file)
Definition: probdata_stp.c:3435
SCIP_RETCODE SCIPsetObjsense(SCIP *scip, SCIP_OBJSENSE objsense)
Definition: scip_prob.c:1240
int graph_pc_getRoot2PtermEdge(const GRAPH *, int)
Definition: graph_pcbase.c:2499
SCIP_RETCODE solhistory_init(SCIP *scip, const GRAPH *graph, SOLHISTORY **solhistory)
Definition: solhistory.c:389
includes methods working on the (reduction) history of solutions to Steiner tree problems ...
static SCIP_RETCODE probdataFree(SCIP *scip, SCIP_PROBDATA **probdata)
Definition: probdata_stp.c:542
void SCIPprobdataSetNSolvers(SCIP *scip, int nSolvers)
Definition: probdata_stp.c:4063
SCIP_CONS ** SCIPprobdataGetPathConstraints(SCIP *scip)
Definition: probdata_stp.c:3232
SCIP_RETCODE reduce_exec(SCIP *, GRAPH *, REDSOL *, int, int, SCIP_Bool)
Definition: reduce_base.c:2192
SCIP_Real SCIPprobdataGetPresolUpperBound(SCIP *scip)
Definition: probdata_stp.c:3141
Definition: struct_cons.h:37
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1389
SCIP_RETCODE SCIPprobdataPrintGraph(SCIP *scip, const char *filename, SCIP_SOL *sol, SCIP_Bool printsol)
Definition: probdata_stp.c:3375
SCIP_Bool SCIPprobdataProbIsAdversarial(SCIP *scip)
Definition: probdata_stp.c:3324
Definition: reduce_sol.c:70
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:420
SCIP_RETCODE SCIPprobdataAddNewSol(SCIP *scip, SCIP_Real *nval, SCIP_HEUR *heur, SCIP_Bool *success)
Definition: probdata_stp.c:3693
SCIP_RETCODE SCIPcheckSolOrig(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *feasible, SCIP_Bool printreason, SCIP_Bool completely)
Definition: scip_sol.c:3497
static void writeCommentSection(SCIP *scip, GRAPH *graph, const char *filename)
Definition: probdata_stp.c:164
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:241
internal miscellaneous methods
SCIP_RETCODE graph_initPseudoAncestors(SCIP *, GRAPH *)
Definition: graph_history.c:1049
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:260
SCIP_RETCODE SCIPtransformCons(SCIP *scip, SCIP_CONS *cons, SCIP_CONS **transcons)
Definition: scip_cons.c:1521
Definition: type_retcode.h:33
static int sepaBadGetZeroHalfMaxrounds(const GRAPH *g)
Definition: probdata_stp.c:1844
SCIP_RETCODE graph_writeReductionRatioStatsLive(SCIP *, GRAPH *, const char *)
Definition: graph_save.c:316
SCIP_RETCODE SCIPcaptureCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1075
Definition: struct_heur.h:88
includes solution pool for Steiner tree problems
SCIP_RETCODE SCIPprobdataCreate(SCIP *scip, const char *filename)
Definition: probdata_stp.c:2728
static SCIP_Bool setParamsSepaIsBad(SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:1811
Definition: type_retcode.h:34
SCIP_RETCODE SCIPgetConsCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_CONS *sourcecons, SCIP_CONS **targetcons, SCIP_CONSHDLR *sourceconshdlr, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *name, 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, SCIP_Bool global, SCIP_Bool *valid)
Definition: scip_copy.c:1577
SCIP_RETCODE SCIPcreateConsSetpack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, 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_setppc.c:9258
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1212
SCIP_RETCODE solhistory_computeHistory(SCIP *scip, SCIP_SOL *scipsol, const GRAPH *g, SOLHISTORY *solhistory)
Definition: solhistory.c:437
void graph_pc_getReductionRatios(const GRAPH *, SCIP_Real *, SCIP_Real *)
Definition: graph_pcbase.c:1751
SCIP_RETCODE SCIPcheckSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *feasible)
Definition: scip_sol.c:3440
SCIP_RETCODE SCIPsetProbTrans(SCIP *scip, SCIP_DECL_PROBTRANS((*probtrans)))
Definition: scip_prob.c:211
SCIP_RETCODE SCIPprobdataSetDefaultParams(SCIP *scip)
Definition: probdata_stp.c:2645
void SCIPprobdataSetGraph(SCIP_PROBDATA *probdata, GRAPH *graph)
Definition: probdata_stp.c:2936
Definition: type_var.h:54
SCIP_VAR ** SCIPprobdataGetEdgeVars(SCIP *scip)
Definition: probdata_stp.c:3277
SCIP_RETCODE SCIPtrySolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip_sol.c:3231
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:478
SCIP_RETCODE SCIPStpHeurSlackPruneRun(SCIP *scip, SCIP_VAR **vars, GRAPH *g, int *soledge, SCIP_Bool *success, SCIP_Bool initialreduce, SCIP_Bool fullreduce)
Definition: heur_slackprune.c:532
void SCIPprobdataSetDualBound(SCIP *scip, SCIP_Real dual)
Definition: probdata_stp.c:4048
SCIP_RETCODE SCIPchgVarBranchPriority(SCIP *scip, SCIP_VAR *var, int branchpriority)
Definition: scip_var.c:7977
SCIP_Real SCIPprobdataGetPresolUpperBoundWithOffset(SCIP *scip)
Definition: probdata_stp.c:3157
SCIP_RETCODE graph_copyPseudoAncestors(SCIP *, const GRAPH *, GRAPH *)
Definition: graph_base.c:1088
Constraint handler for linear constraints in their most general form, .
static SCIP_RETCODE presolveStp(SCIP *scip, SCIP_PROBDATA *probdata, REDSOL *redsol)
Definition: probdata_stp.c:353
SCIP_RETCODE SCIPcreateConsStp(SCIP *scip, SCIP_CONS **cons, const char *name, GRAPH *graph)
Definition: cons_stp.c:1135
SCIP_Bool SCIPprobdataIsSubproblem(SCIP *scip)
Definition: probdata_stp.c:3359
SCIP_RETCODE SCIPsetCharParam(SCIP *scip, const char *name, char value)
Definition: scip_param.c:652
Definition: type_retcode.h:39
void graph_pc_enforceNode(SCIP *, GRAPH *, int, SCIP_Real *)
Definition: graph_pcbase.c:1606
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
SCIP_RETCODE SCIPsetProbInitsol(SCIP *scip, SCIP_DECL_PROBINITSOL((*probinitsol)))
Definition: scip_prob.c:253
static SCIP_RETCODE setParams(SCIP *scip, SCIP_PROBDATA *probdata, int symcons, int cyclecons)
Definition: probdata_stp.c:1862
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:477
static SCIP_RETCODE freeConstraintsCutModel(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:423
static SCIP_RETCODE createLogfile(SCIP *scip, SCIP_PROBDATA *probdata, const char *intlogfilename, const char *logfilename, const char *filename, const char *probname)
Definition: probdata_stp.c:1657
SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
Definition: scip_copy.c:702
includes various testing methods for Steiner tree problems
void SCIPmessageVFPrintInfo(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char *formatstr, va_list ap)
Definition: message.c:624
SCIP_Bool graph_pc_knotIsDummyTerm(const GRAPH *, int)
Definition: graph_pcbase.c:1344
SCIP_Bool graph_pc_knotIsFixedTerm(const GRAPH *, int)
Definition: graph_pcbase.c:1257
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
SCIP_RETCODE graph_load(SCIP *, GRAPH **, const char *, PRESOL *)
Definition: graph_load.c:885
SCIP_Real * SCIPprobdataGetXval(SCIP *scip, SCIP_SOL *sol)
Definition: probdata_stp.c:3190
Definition: solhistory.h:40
SCIP_RETCODE SCIPtransformVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1346
SCIP_VAR * SCIPprobdataGetedgeVarByIndex(SCIP *scip, int idx)
Definition: probdata_stp.c:3173
shortest paths based primal heuristics for Steiner problems
void initReceivedSubproblem(SCIP *scip, const int lLinearConsNames, const char *linearConsNames, const int lSetppcConsNames, const char *setppcConsNames)
Definition: probdata_stp.c:4077
SCIP_RETCODE dualascent_execPcMw(SCIP *scip, GRAPH *g, SCIP_Real *redcost, SCIP_Real *objval, SCIP_Bool addcuts, SCIP_Bool ascendandprune, int nruns)
Definition: dualascent.c:1319
static SCIP_RETCODE createHopConstraint(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:590
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1254
SCIP_RETCODE SCIPsetProbDeltrans(SCIP *scip, SCIP_DECL_PROBDELTRANS((*probdeltrans)))
Definition: scip_prob.c:232
static SCIP_RETCODE createPrizeConstraints(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:676
int * SCIPprobdataGetPctermsorder(SCIP *scip)
Definition: probdata_stp.c:3262
SCIP_RETCODE SCIPsetProbDelorig(SCIP *scip, SCIP_DECL_PROBDELORIG((*probdelorig)))
Definition: scip_prob.c:190
SCIP_Bool solstp_isValid(SCIP *scip, const GRAPH *graph, const int *result)
Definition: solstp.c:1650
Definition: type_prob.h:39
static SCIP_Real getEdgeReductionRatio(SCIP_PROBDATA *probdata, const GRAPH *graph)
Definition: probdata_stp.c:1783
static SCIP_RETCODE createDegreeConstraints(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:641
Definition: objbenders.h:33
SCIP_RETCODE graph_writeGml(const GRAPH *, const char *, const SCIP_Bool *)
Definition: graph_save.c:441
SCIP_RETCODE solpool_addSolToScip(SCIP *scip, SCIP_HEUR *heur, const GRAPH *g, const int *result, SCIP_Bool *success)
Definition: solpool.c:150
includes various reduction methods for Steiner tree problems
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
void solhistory_free(SCIP *scip, SOLHISTORY **solhistory)
Definition: solhistory.c:419
Steiner tree dynamic programming relaxator.
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:874
SCIP_RETCODE SCIPStpcomponentsSetUp(SCIP *scip, GRAPH *graph)
Definition: cons_stpcomponents.c:660
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:319
static SCIP_RETCODE addRedsol(SCIP *scip, SCIP_PROBDATA *probdata, REDSOL *redsol)
Definition: probdata_stp.c:304
Definition: type_var.h:58