dualascent.c
Go to the documentation of this file.
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
450 graph_pathInLimitedExec(graph, redcost, nodes_abort, dapaths->centernode, dijklimited, &(dapaths->maxdist));
648 const SCIP_Real maxdeviation = (daparams->damaxdeviation > 0.0) ? daparams->damaxdeviation : DEFAULT_DAMAXDEVIATION;
762 const SCIP_Real prio2 = (SCIPpqueueNElems(pqueue) > 0) ? ((GNODE*) SCIPpqueueFirst(pqueue))->dist : FARAWAY;
1168 SCIP_CALL( SCIPStpHeurAscendPruneRun(scip, NULL, g, rescap, unsatarcs, root, &success, TRUE) );
1440 else if( transgraph->tail[i] == pseudoroot && !Is_term(transgraph->term[transgraph->head[i]]) )
1577 if( SCIPisLE(scip, (currscore - prio1) / prio1, maxdeviation) || (SCIPpqueueNElems(pqueue) == 0) )
1629 SCIP_CALL(SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, "da", 1.0, SCIPinfinity(scip), FALSE, FALSE, TRUE));
SCIP_RETCODE SCIPaddCoefLogicor(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_logicor.c:5392
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1626
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_setppc.c:9372
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_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1649
static SCIP_RETCODE dapathsInit(SCIP *scip, const GRAPH *graph, DAPATHS *dapaths)
Definition: dualascent.c:318
Definition: struct_misc.h:69
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1686
Definition: dualascent.h:39
static SCIP_RETCODE daExec(SCIP *scip, const GRAPH *g, const int *result, const DAPARAMS *daparams, SCIP_Bool updateRescaps, SCIP_Real *RESTRICT rescap, SCIP_Real *objval)
Definition: dualascent.c:623
SCIP_RETCODE SCIPcreateConsSetcover(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:9317
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:490
Definition: struct_var.h:198
reduction and dual-cost based primal heuristic for Steiner problems
Includes dual-ascent for classic Steiner tree and some variants.
Problem data for stp problem.
includes various files containing graph methods used for Steiner tree problems
static SCIP_Bool daNodeIsActive(const int *active, int realtail, int dfsbase)
Definition: dualascent.c:472
static void dapathsRunShortestPaths(const GRAPH *graph, DAPATHS *dapaths, SCIP_Real *RESTRICT redcost, SCIP_Real *objval)
Definition: dualascent.c:417
SCIP_RETCODE dualascent_update(SCIP *scip, const GRAPH *g, const int *result, const DAPARAMS *daparams, SCIP_Real *RESTRICT redcost, SCIP_Real *objval)
Definition: dualascent.c:1225
SCIP_RETCODE graph_transPcGetSap(SCIP *, GRAPH *, GRAPH **, SCIP_Real *)
Definition: graph_trans.c:931
Definition: dualascent.c:57
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
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 .
static SCIP_RETCODE daconsCreateEmpty(SCIP *scip, enum DACONS_Type constype, SCIP_Bool consUseInital, SCIP_CONS **cons)
Definition: dualascent.c:81
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
Definition: cons_linear.c:18162
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 daInit(SCIP *scip, const GRAPH *g, int root, SCIP_Bool is_pseudoroot, int *gmark, int *RESTRICT active, SCIP_PQUEUE *pqueue, GNODE *gnodearr, int *augmentingcomponent)
Definition: dualascent.c:538
void graph_dijkLimited_reset(const GRAPH *, DIJK *)
Definition: graph_util.c:2105
SCIP_RETCODE dualascent_paths(SCIP *scip, GRAPH *graph, SCIP_Real *RESTRICT redcost, SCIP_Real *objval, const int *result)
Definition: dualascent.c:1803
SCIP_RETCODE SCIPStpHeurAscendPruneRun(SCIP *scip, SCIP_HEUR *heur, const GRAPH *g, const SCIP_Real *redcosts, int *result, int root, SCIP_Bool *solfound, SCIP_Bool addsol)
Definition: heur_ascendprune.c:940
Definition: struct_cons.h:37
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:451
Definition: struct_cons.h:117
static void dapathsFreeMembers(SCIP *scip, DAPATHS *dapaths)
Definition: dualascent.c:458
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
void graph_getCsr(const GRAPH *, int *RESTRICT, int *RESTRICT, int *RESTRICT, int *)
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:241
internal miscellaneous methods
struct dual_ascent_paths DAPATHS
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:260
Definition: type_set.h:43
Definition: type_retcode.h:33
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:241
SCIP_Bool dualascent_allTermsReachable(SCIP *scip, const GRAPH *g, int root, const SCIP_Real *redcost)
Definition: dualascent.c:1835
int GNODECmpByDist(void *first_arg, void *second_arg)
SCIP_RETCODE graph_dijkLimited_init(SCIP *, const GRAPH *, DIJK **)
Definition: graph_util.c:1989
static SCIP_RETCODE daconsGetParams(SCIP *scip, enum DACONS_Type *constype, SCIP_Bool *consUseInital)
Definition: dualascent.c:112
Definition: dualascent.c:57
static SCIP_RETCODE daUpdateRescaps(SCIP *scip, const GRAPH *g, const int *edgemap, int ncsredges, SCIP_Real *rescap)
Definition: dualascent.c:508
Definition: struct_lp.h:192
Constraint handler for linear constraints in their most general form, .
SCIP_RETCODE SCIPcreateConsLogicor(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_logicor.c:5298
SCIP_RETCODE SCIPpqueueCreate(SCIP_PQUEUE **pqueue, int initsize, SCIP_Real sizefac, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), SCIP_DECL_PQUEUEELEMCHGPOS((*elemchgpos)))
Definition: misc.c:1236
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 void dapathsUpdate(const GRAPH *g, const DAPATHS *dapaths, SCIP_Real *RESTRICT redcost, SCIP_Real *objval)
Definition: dualascent.c:356
SCIP_RETCODE SCIPpqueueInsert(SCIP_PQUEUE *pqueue, void *elem)
Definition: misc.c:1335
void graph_pathInLimitedExec(const GRAPH *, const SCIP_Real *, const SCIP_Bool *, int, DIJK *, SCIP_Real *)
Definition: graph_path.c:610
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
Definition: misc_stp.h:53
static void daInitRescaps(const GRAPH *g, const int *edgemap, int ncsredges, SCIP_Real *RESTRICT rescap, SCIP_Real *dualobj)
Definition: dualascent.c:491
Definition: graphdefs.h:311
static void dapathsSetRunParams(const GRAPH *graph, DAPATHS *dapaths)
Definition: dualascent.c:262
static void dapathsInitRedCosts(const GRAPH *graph, SCIP_Real *RESTRICT redcost, SCIP_Real *objval)
Definition: dualascent.c:341
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
Definition: dualascent.c:61
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:464
Definition: dualascent.c:57
SCIP_RETCODE SCIPcreateEmptyRowConshdlr(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1382
static SCIP_RETCODE dapathsSortStarts(SCIP *scip, const GRAPH *graph, const int *result, DAPATHS *dapaths)
Definition: dualascent.c:143
Definition: objbenders.h:33
SCIP_RETCODE dualascent_pathsPcMw(SCIP *scip, const GRAPH *transgraph, SCIP_Real *RESTRICT redcost, SCIP_Real *objval, const int *result)
Definition: dualascent.c:1780
SCIP callable library.