prop_stp.c
Go to the documentation of this file.
20 * This propagator makes use of the reduced cost of an optimally solved LP relaxation to propagate the variables
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
44 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found reductions? */
58 #define DEFAULT_MAXNWAITINGROUNDS 2 /**< maximum number of rounds to wait until propagating again */
59 #define REDUCTION_WAIT_RATIO 0.02 /**< ratio of edges to be newly fixed before performing reductions for additional fixing */
72 SCIP_Real* fixingbounds; /**< saves largest upper bound to each variable that would allow to fix it */
79 int postrednfixededges; /**< total number of arcs fixed by 'fixedgevar' method of this propagator after the last reductions */
214 assert(SCIPisFeasEQ(scip, SCIPgetSolVal(scip, NULL, vars[e]), 1.0) || SCIPisDualfeasZero(scip, SCIPgetVarRedcost(scip, vars[e])));
352 SCIP_CALL( globalfixing(scip, vars, nfixed, propdata->fixingbounds, graph, cutoffbound, nedges) );
404 extnfixed = reduce_extendedEdge(scip, propgraph, vnoi, redcost, pathdist, NULL, minpathcost, propgraph->source, nodearr, NULL);
422 * To this end, the already 0-fixed edges are (temporarily) removed from the underlying graph to strengthen the reduction methods. */
575 if( (remain[e] == PROP_STP_EDGE_UNSET || remain[e] == PROP_STP_EDGE_KILLED) && (SCIPvarGetLbLocal(vars[e]) > 0.5) )
686 if( propdata->nfails > 0 && (propdata->nlastcall + propdata->maxnwaitrounds >= propdata->ncalls)
771 if( graph->stp_type == STP_SPG || graph->stp_type == STP_RSMT || graph->stp_type == STP_RPCSPG ||
779 if( SCIPvarGetUbGlobal(vars[e]) < 0.5 && SCIPvarGetUbGlobal(vars[erev]) < 0.5 && graph->cost[e] < BLOCKED )
799 /** solving process initialization method of propagator (called when branch and bound process is about to begin) */
821 /** solving process deinitialization method of propagator (called before branch and bound process data is freed) */
915 SCIP_CALL( SCIPincludePropBasic(scip, &prop, PROP_NAME, PROP_DESC, PROP_PRIORITY, PROP_FREQ, PROP_DELAY, PROP_TIMING,
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
Definition: misc_stp.h:73
Definition: type_result.h:33
void SCIPStpPropGetGraph(SCIP *scip, GRAPH **graph, SCIP_Longint *graphnodenumber)
Definition: prop_stp.c:883
internal methods for branch and bound tree
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:490
Definition: struct_scip.h:59
SCIP_RETCODE fixedgevar(SCIP *scip, SCIP_VAR *edgevar, int *nfixed)
Definition: prop_stp.c:848
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1353
Definition: struct_var.h:198
SCIP_RETCODE reduce_contractZeroEdges(SCIP *, GRAPH *, SCIP_Bool)
Definition: reduce_simple.c:453
Definition: grph.h:143
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
int reduce_extendedEdge(SCIP *, GRAPH *, const PATH *, const SCIP_Real *, const SCIP_Real *, const int *, SCIP_Real, int, int *, STP_Bool *)
Definition: reduce_bnd.c:2774
GRAPH * SCIPprobdataGetGraph(SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:2357
Definition: struct_tree.h:132
SCIP_Bool SCIPisDualfeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:1035
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
Definition: scip_prop.c:142
SCIP_Bool SCIPisDualfeasZero(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:1011
static SCIP_RETCODE globalfixing(SCIP *scip, SCIP_VAR **vars, int *nfixededges, const SCIP_Real *fixingbounds, const GRAPH *graph, SCIP_Real cutoffbound, int nedges)
Definition: prop_stp.c:121
void graph_path_execX(SCIP *, const GRAPH *, int, const SCIP_Real *, SCIP_Real *, int *)
Definition: grphpath.c:781
static SCIP_RETCODE reduceRedcostExtended(SCIP *scip, SCIP_Real lpobjval, SCIP_VAR **vars, GRAPH *propgraph)
Definition: prop_stp.c:367
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4677
Definition: type_result.h:35
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:773
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip_prop.c:158
Definition: type_retcode.h:33
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITSOL((*propexitsol)))
Definition: scip_prop.c:222
SCIP_RETCODE graph_copy_data(SCIP *, const GRAPH *, GRAPH *)
Definition: grphbase.c:3809
Definition: type_result.h:42
static void setRedcosts(SCIP *scip, SCIP_VAR **vars, int nedges, SCIP_Real *cost)
Definition: prop_stp.c:180
static SCIP_RETCODE dualcostVarfixing(SCIP *scip, SCIP_Real lpobjval, SCIP_VAR **vars, SCIP_PROPDATA *propdata, int *nfixed, const GRAPH *graph)
Definition: prop_stp.c:287
Definition: type_lp.h:34
Definition: struct_prop.h:37
Definition: type_retcode.h:34
propagator for Steiner tree problems, using the LP reduced costs
static void updateFixingBounds(SCIP_Real *fixingbounds, const GRAPH *graph, const SCIP_Real *cost, const SCIP_Real *pathdist, const PATH *vnoi, SCIP_Real lpobjal)
Definition: prop_stp.c:260
static SCIP_RETCODE redbasedVarfixing(SCIP *scip, SCIP_Real lpobjval, SCIP_VAR **vars, SCIP_PROPDATA *propdata, int *nfixed, SCIP_Bool *probisinfeas, const GRAPH *g)
Definition: prop_stp.c:424
SCIP_Bool SCIPisDualfeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:1023
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4767
includes various files containing graph methods used for Steiner tree problems
Steiner vertex branching rule.
SCIP_RETCODE SCIPchgVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:5030
SCIP_RETCODE SCIPStpBranchruleApplyVertexChgs(SCIP *scip, int *vertexchgs, GRAPH *graph)
Definition: branch_stp.c:708
SCIP_RETCODE reduceStp(SCIP *, GRAPH **, SCIP_Real *, int, SCIP_Bool, SCIP_Bool, SCIP_Bool)
Definition: reduce.c:223
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
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:451
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:477
Definition: type_set.h:44
SCIP_RETCODE SCIPincludePropBasic(SCIP *scip, SCIP_PROP **propptr, const char *name, const char *desc, int priority, int freq, SCIP_Bool delay, SCIP_PROPTIMING timingmask, SCIP_DECL_PROPEXEC((*propexec)), SCIP_PROPDATA *propdata)
Definition: scip_prop.c:105
static void setVnoiDistances(SCIP *scip, const SCIP_Real *cost, const GRAPH *graph, PATH *vnoi, SCIP_Real *costrev, SCIP_Real *pathdist, int *pathedge, int *vbase)
Definition: prop_stp.c:227
Definition: objbenders.h:33
SCIP_RETCODE SCIPsetPropInitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITSOL((*propinitsol)))
Definition: scip_prop.c:206
void graph_voronoiTerms(SCIP *, const GRAPH *, const SCIP_Real *, PATH *, int *, int *, int *)
Definition: grphpath.c:2307
Definition: type_result.h:39