heur_tm.c
Go to the documentation of this file.
35 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
56 #define HEUR_TIMING (SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE)
106 int* result; /**< array indicating whether an arc is part of the solution (CONNECTED/UNKNOWN) */
107 int* best_result; /**< array indicating whether an arc is part of the solution (CONNECTED/UNKNOWN) */
186 solstp_convertCsrToGraph(scip, graph, tmbase->csr_orgcosts, result_csr, connected_dummy, result_dummy);
259 SCIP_CALL( graph_heap_create(scip, nnodes, tmbase->heap_position, tmbase->heap_entries, &(tmbase->dheap)) );
560 solstp_convertCsrToGraph(scip, graph, tmbase->csr_orgcosts, result_csr, connected, tmbase->best_result);
579 SCIPdebugMessage("edges vs hop-limit: %d, %d \n", solstp_getNedges(graph, result), graph->hoplimit);
617 solstp_convertCsrToGraph(scip, graph, tmbase->csr_orgcosts, result_csr, connected, tmbase->best_result);
652 if( maxtmruns > 0 && bestincstart >= 0 && bestincstart < nnodes && Is_pseudoTerm(graph->term[bestincstart])
673 const SCIP_Real* nodepriority, /**< vertex priorities for vertices to be starting points (NULL for no priorities) */
703 terminalprio[termcount++] = -SCIPrandomGetReal(heurdata->randnumgen, nodepriority[k] / 2.0, nodepriority[k]);
1055 SPATHS spaths = { .csr = tmbase->csr, .csr_orgcosts = tmbase->csr_orgcosts, .nodes_dist = tmbase->nodes_dist,
1056 .nodes_pred = tmbase->nodes_pred, .dheap = tmbase->dheap, .nodes_isConnected = tmbase->connected,
1083 SPATHS spaths = { .csr = tmbase->csr, .csr_orgcosts = tmbase->csr_orgcosts, .nodes_dist = tmbase->nodes_dist,
1084 .nodes_pred = tmbase->nodes_pred, .dheap = tmbase->dheap, .nodes_isConnected = tmbase->connected,
1180 SPATHS spaths = { .csr = tmbase->csr, .csr_orgcosts = tmbase->csr_orgcosts, .nodes_dist = tmbase->nodes_dist,
1181 .nodes_pred = tmbase->nodes_pred, .dheap = tmbase->dheap, .nodes_isConnected = tmbase->connected,
1208 tmbase->cost, prize, costsAreBiased, tmbase->nodes_dist, tmbase->nodes_pred, start, tmbase->connected);
1221 /** Dijkstra based shortest paths heuristic for PCSTP and MWCSP that computes tree spanning all positive
1233 SPATHS spaths = { .csr = tmbase->csr, .csr_orgcosts = tmbase->csr_orgcosts, .nodes_dist = tmbase->nodes_dist,
1242 graph_path_st_pcmw_full(g, tmbase->cost, tmbase->nodes_dist, tmbase->nodes_pred, start, tmbase->connected);
1266 SCIP_Bool directed = (g->stp_type == STP_SAP || g->stp_type == STP_DHCSTP || g->stp_type == STP_NWPTSPG);
1824 /* for each terminal: extend the voronoi regions until all neighbouring terminals have been visited */
1878 if( SCIPisGT(scip, vnoi[k].dist, vcost[old] + ((vbase[k] == root)? cost[oedge] : costrev[oedge])) )
1894 SCIP_CALL( graph_voronoiExtend(scip, g, ((term == root)? cost : costrev), vnoi, node_dist, node_base, node_edge, termsmark, reachednodes, &nreachednodes, nodenterms,
2036 if( (heurdata->nlpiterations == SCIPgetNLPIterations(scip) && SCIPrandomGetInt(heurdata->randnumgen, 0, 5) != 1)
2042 else if( graph->stp_type == STP_DCSTP && heurdata->ncalls != 1 && SCIPrandomGetInt(heurdata->randnumgen, 0, 1) == 1
2400 SCIP_CALL( computeDegConsTree(scip, graph, cost, costrev, start[r], result, tmallsp, heurdata->randnumgen, tmbase->connected, &solfound) );
2412 SCIP_CALL( computeSteinerTree(scip, graph, cost, costrev, start[r], result, tmallsp, tmbase->connected, heurdata->randnumgen) );
2416 SCIP_CALL( computeSteinerTreeVnoi(scip, graph, cost, costrev, start[r], (r == 0), tmvnoi, result, tmbase->connected) );
2432 // const SCIP_Real obj = solstp_getObjCsr(graph, tmbase->csr_orgcosts, tmbase->result, tmbase->connected);
2453 SCIP_Real* nodepriority, /**< vertex priorities for vertices to be starting points (NULL for no priorities) */
2526 SCIP_CALL( computeSteinerTreeDijkBMw(scip, graph, costorg, prize_in, start, tmbase, &solfound) );
2592 SCIP_Real* nodepriority, /**< vertex priorities for vertices to be starting points (NULL for no priorities) */
2598 enum PCMW_TmMode pcmw_mode = (pcmw_tmmode == pcmode_fromheurdata) ? heurdata->pcmw_mode : pcmw_tmmode;
2614 SCIP_CALL( runTmPcMW_mode(scip, graph, cost, prize, pcmode_simple, beststart, nodepriority, tmbase, success));
2618 SCIP_CALL( runTmPcMW_mode(scip, graph, cost, prize, pcmode_bias, beststart, nodepriority, tmbase, success));
2622 SCIP_CALL( runTmPcMW_mode(scip, graph, cost, prize, pcmode_biasfull, beststart, nodepriority, tmbase, success));
2626 SCIP_CALL( runTmPcMW_mode(scip, graph, cost, prize, pcmode_fulltree, beststart, nodepriority, tmbase, success));
2794 else if( ((heurtiming & SCIP_HEURTIMING_DURINGLPLOOP) && (heurdata->ncalls % heurdata->duringlpfreq == 0)) || (heurtiming & SCIP_HEURTIMING_AFTERLPLOOP) )
2812 if( (isPcMw || isSpg) && graph->edges < TM_HARD_MAXNEDGES && SCIPprobdataProbIsAdversarial(scip) )
2857 SCIPdebugMessage("TM solution added, value %f \n", solstp_getObj(graph, soledges, SCIPprobdataGetOffset(scip)));
2878 /** compute starting points among marked (w.r.t. g->mark) vertices for constructive heuristics */
3011 /** build (rooted) prize collecting Steiner tree in such a way that all leaves are terminals; objresult is set FARAWAY if infeasible */
3424 int* best_result, /**< array indicating whether an arc is part of the solution (CONNECTED/UNKNOWN) */
3430 SCIP_Real* nodepriority, /**< vertex priorities for vertices to be starting points (NULL for no priorities) */
3437 TMBASE tmbase = { .dheap = NULL, .cost = cost, .costrev = costrev, .nodes_dist = NULL, .sdprofit1st = NULL,
3449 for( int e = 0; e < nedges; e++) assert(SCIPisGE(scip, cost[e], 0.0) && SCIPisGE(scip, costrev[e], 0.0));
3475 SCIP_CALL( computeStarts(scip, graph, starts, startsgiven, nodepriority, &tmbase, &beststart) );
3480 SCIP_CALL( runTmPcMW(scip, graph, cost, prize, pcmw_tmmode, beststart, nodepriority, &tmbase, success));
3513 int* result, /**< (uninitialized) array indicating whether an arc is part of the solution (CONNECTED/UNKNOWN) */
3605 initCostsAndPrioLP(scip, heurdata, vars, graph, randupper, randlower, xval, nodepriority, prize, cost);
3639 graph, NULL, prize, result, runs, heurdata->beststartnode, cost, costrev, &(heurdata->hopfactor), nodepriority, success));
3677 graph, &(graph->source), prize, soledges, 1, heurdata->beststartnode, cost, costrev, &(heurdata->hopfactor),
3780 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "timing when heuristic should be called (%u:BEFORENODE, %u:DURINGLPLOOP, %u:AFTERLPLOOP, %u:AFTERNODE)", SCIP_HEURTIMING_BEFORENODE, SCIP_HEURTIMING_DURINGLPLOOP, SCIP_HEURTIMING_AFTERLPLOOP, SCIP_HEURTIMING_AFTERNODE);
3782 (int*) &heurdata->timing, TRUE, (int) HEUR_TIMING, (int) SCIP_HEURTIMING_BEFORENODE, 2 * (int) SCIP_HEURTIMING_AFTERPSEUDONODE - 1, NULL, NULL) ); /*lint !e713*/
Steiner tree relaxator.
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
static SCIP_RETCODE runTm(SCIP *scip, GRAPH *graph, TMBASE *tmbase, TMALLSP *tmallsp, TMVNOI *tmvnoi, SCIP_Bool *success)
Definition: heur_tm.c:2366
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
Definition: scip_randnumgen.c:70
SCIP_RETCODE reduce_sdprofitInit1stOnly(SCIP *, const GRAPH *, const SCIP_Real *, SDPROFIT **)
Definition: reduce_sdutil.c:1048
void graph_path_st(const GRAPH *, const SCIP_Real *, SCIP_Real *, int *, int, STP_Bool *)
Definition: graph_path.c:1199
Definition: type_result.h:33
Definition: type_result.h:47
static SCIP_RETCODE runTmDhcstp(SCIP *scip, GRAPH *graph, TMBASE *tmbase, TMALLSP *tmallsp, TMVNOI *tmvnoi, SCIP_Real *hopfactor, SCIP_Bool *success)
Definition: heur_tm.c:2635
static SCIP_RETCODE pcmwGetStartNodes(SCIP *scip, const SCIP_Real *nodepriority, int maxtmruns, int bestincstart, GRAPH *graph, int *terminalperm)
Definition: heur_tm.c:671
void graph_pc_getBiased(const GRAPH *, SCIP_Real *RESTRICT, SCIP_Real *RESTRICT)
SCIP_RETCODE solstp_addSolToProb(SCIP *scip, const GRAPH *g, const int *soledge, SCIP_HEUR *heur, SCIP_Bool *success)
Definition: solstp.c:1279
void shortestpath_computeSteinerTreePcMw(const GRAPH *g, int startnode, const SCIP_Real *prize, SCIP_Bool costIsBiased, SPATHSPC *spaths_pc, SPATHS *spaths)
Definition: shortestpath.c:1104
struct TM_base_data TMBASE
Definition: graphdefs.h:184
SCIP_RETCODE SCIPStpHeurTMBuildTreeDc(SCIP *scip, const GRAPH *g, int *result, STP_Bool *connected)
Definition: heur_tm.c:3226
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
Definition: scip_solvingstats.c:438
Definition: struct_scip.h:59
Definition: heur_tm.h:48
SCIP_Bool graph_csr_costsAreInSync(const GRAPH *, const CSR *, const SCIP_Real *)
Definition: graph_util.c:1448
SCIP_RETCODE shortestpath_pcInit(SCIP *scip, const GRAPH *graph, const SCIP_Real *costs, const SCIP_Real *prizes, SPATHSPC **sppc)
Definition: shortestpath.c:893
Shortest path based algorithms for Steiner problems.
Definition: struct_misc.h:69
static SCIP_RETCODE computeSteinerTreeKeyNodesCsr(SCIP *scip, GRAPH *g, int startnode, TMBASE *tmbase)
Definition: heur_tm.c:1076
static SCIP_RETCODE computeSteinerTree(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, int start, int *result, TMALLSP *tmallsp, STP_Bool *connected, SCIP_RANDNUMGEN *randnumgen)
Definition: heur_tm.c:1253
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:490
void graph_path_exec(SCIP *, const GRAPH *, int, int, const SCIP_Real *, PATH *)
Definition: graph_path.c:541
void graph_csr_build(const GRAPH *, const SCIP_Real *, CSR *)
Definition: graph_util.c:1351
Definition: struct_var.h:198
includes methods for Steiner tree problem solutions
Definition: heur_tm.c:117
Definition: graphdefs.h:301
static void tmAllspFree(SCIP *scip, const GRAPH *graph, TMALLSP *tmallsp)
Definition: heur_tm.c:367
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
static void keyNodesResetTerms(const int *solnodes_degree, GRAPH *g)
Definition: heur_tm.c:1022
SCIP_RETCODE SCIPStpHeurTMRunLP(SCIP *scip, GRAPH *graph, SCIP_HEUR *heur, int *result, int runs, SCIP_Bool *success)
Definition: heur_tm.c:3509
void shortestpath_computeSteinerTreePcMwFull(const GRAPH *g, int startnode, SPATHS *spaths)
Definition: shortestpath.c:1153
static void pcmwAdaptStarts(SCIP_HEURDATA *heurdata, const GRAPH *graph, int maxtmruns, int bestincstart, int *terminalperm)
Definition: heur_tm.c:640
void graph_pathHeapAdd(const PATH *, int, int *RESTRICT, int *RESTRICT, int *)
static void buildTmAllSp(SCIP *scip, const GRAPH *graph, const SCIP_Real *cost, const SCIP_Real *costrev, TMALLSP *tmallsp)
Definition: heur_tm.c:2191
Problem data for stp problem.
Definition: struct_misc.h:259
Definition: graphdefs.h:284
void solstp_convertCsrToGraph(SCIP *scip, const GRAPH *g, const CSR *csr, const int *soledge_csr, STP_Bool *RESTRICT solnode, int *RESTRICT soledge_g)
Definition: solstp.c:1976
SCIP_RETCODE solstp_pruneFromTmHeur(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int *RESTRICT result, STP_Bool *RESTRICT connected)
Definition: solstp.c:1474
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:108
static SCIP_RETCODE computeSteinerTreeVnoi(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, int start, STP_Bool firstrun, TMVNOI *tmvnoi, int *result, STP_Bool *connected)
Definition: heur_tm.c:1697
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:10003
static SCIP_Real getTmEdgeCostZeroOffset(SCIP *scip, const GRAPH *graph)
Definition: heur_tm.c:474
SCIP_Real graph_pc_getNonLeafTermOffset(SCIP *, const GRAPH *)
Definition: graph_pcbase.c:2209
void shortestpath_computeSteinerTreeDirected(SCIP *scip, const GRAPH *g, int startnode, SPATHS *spaths)
Definition: shortestpath.c:1055
SCIP_Real solstp_pcGetObjCsr(const GRAPH *g, const CSR *csr, const int *soledge_csr, const STP_Bool *solnode)
Definition: solstp.c:1872
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1362
static SCIP_RETCODE computeSteinerTreeCsr(SCIP *scip, const GRAPH *g, int startnode, TMBASE *tmbase)
Definition: heur_tm.c:1047
static void pcmwSetEdgeCosts(const GRAPH *graph, const SCIP_Real *cost, const SCIP_Real *costorg, const SCIP_Real *costfullbiased, enum PCMW_TmMode pcmwmode, TMBASE *tmbase)
Definition: heur_tm.c:755
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
void graph_csr_chgCosts(const GRAPH *, const SCIP_Real *, CSR *)
Definition: graph_util.c:1298
Definition: shortestpath.h:36
Definition: struct_sol.h:64
static void initCostsAndPrioLP(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR **vars, const GRAPH *graph, SCIP_Real randupper, SCIP_Real randlower, const SCIP_Real *xval, SCIP_Real *RESTRICT nodepriority, SCIP_Real *RESTRICT prize, SCIP_Real *RESTRICT cost)
Definition: heur_tm.c:2053
static void pcmwUpdateBestSol(SCIP *scip, const GRAPH *graph, TMBASE *tmbase, SCIP_Bool *success)
Definition: heur_tm.c:597
Definition: heur_tm.h:48
static SCIP_RETCODE computeSteinerTreeDijk(SCIP *scip, GRAPH *g, int start, TMBASE *tmbase)
Definition: heur_tm.c:1116
Definition: heur_tm.h:47
void graph_path_st_pcmw(GRAPH *, SCIP_Real *, int *, const SCIP_Real *, const SCIP_Real *, SCIP_Bool, SCIP_Real *, int *, int, STP_Bool *)
Definition: graph_path.c:1430
int graph_pc_getRoot2PtermEdge(const GRAPH *, int)
Definition: graph_pcbase.c:2499
void graph_path_execX(SCIP *, const GRAPH *, int, const SCIP_Real *, SCIP_Real *, int *)
Definition: graph_path.c:905
static SCIP_RETCODE tmAllspInit(SCIP *scip, const GRAPH *graph, TMALLSP *tmallsp)
Definition: heur_tm.c:332
static void tmLpGetEdgeRandomizations(SCIP *scip, SCIP_HEURDATA *heurdata, const GRAPH *graph, SCIP_Bool *partrand, SCIP_Bool *totalrand)
Definition: heur_tm.c:2025
Definition: reducedefs.h:135
static SCIP_RETCODE computeSteinerTreeDijkBMw(SCIP *scip, GRAPH *g, const SCIP_Real *cost_org, const SCIP_Real *prize, int start, TMBASE *tmbase, SCIP_Bool *solfound)
Definition: heur_tm.c:1143
void SCIPsortRealIntInt(SCIP_Real *realarray, int *intarray1, int *intarray2, int len)
Definition: type_result.h:35
SCIP_RETCODE graph_csr_allocWithEdgeId(SCIP *, int, int, CSR **)
Definition: graph_util.c:1270
void shortestpath_pcFree(SCIP *scip, SPATHSPC **sppc)
Definition: shortestpath.c:964
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:451
static SCIP_RETCODE runTmPcMW_mode(SCIP *scip, GRAPH *graph, const SCIP_Real *cost, const SCIP_Real *prize, enum PCMW_TmMode pcmwmode, int bestincstart, SCIP_Real *nodepriority, TMBASE *tmbase, SCIP_Bool *success)
Definition: heur_tm.c:2446
SCIP_Bool SCIPprobdataProbIsAdversarial(SCIP *scip)
Definition: probdata_stp.c:3324
static void keyNodesSetTerms(SCIP *scip, const int *soledge, GRAPH *g, int *solnodes_degree)
Definition: heur_tm.c:983
void SCIPStpHeurTMCompStarts(GRAPH *graph, int *starts, int *runs)
Definition: heur_tm.c:2879
Definition: graphdefs.h:294
static SCIP_RETCODE computeDegConsTree(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, int start, int *result, TMALLSP *tmallsp, SCIP_RANDNUMGEN *randnumgen, STP_Bool *connected, STP_Bool *solfound)
Definition: heur_tm.c:1434
static SCIP_RETCODE dhcstpWarmUp(SCIP *scip, GRAPH *graph, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *hopfactor, TMBASE *tmbase, SCIP_Bool *success)
Definition: heur_tm.c:2225
struct TM_all_shortestpath TMALLSP
internal miscellaneous methods
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:260
Definition: type_retcode.h:33
void shortestpath_computeSteinerTreeBiased(const GRAPH *g, const SDPROFIT *sdprofit, int startnode, SPATHS *spaths)
Definition: shortestpath.c:1081
static void computeSteinerTreeSingleNode(const GRAPH *graph, int node, TMBASE *tmbase, SCIP_Bool *success)
Definition: heur_tm.c:1407
SCIP_Real solstp_getObjCsr(const GRAPH *g, const CSR *csr, const int *soledge_csr, const STP_Bool *solnode)
Definition: solstp.c:1921
Definition: struct_heur.h:88
Definition: type_lp.h:34
int GNODECmpByDist(void *first_arg, void *second_arg)
SCIP_RETCODE solstp_pruneFromEdges(SCIP *scip, const GRAPH *g, int *result)
Definition: solstp.c:1432
void SCIPStpHeurTMBuildTree(SCIP *scip, GRAPH *g, PATH *mst, const SCIP_Real *cost, SCIP_Real *objresult, int *connected)
Definition: heur_tm.c:2932
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
Definition: scip_randnumgen.c:47
SCIP_Real solstp_getObjBounded(const GRAPH *g, const int *soledge, SCIP_Real offset, int nedges)
Definition: solstp.c:1833
void graph_path_st_rpcmw(GRAPH *, SCIP_Real *, int *, const SCIP_Real *, const SCIP_Real *, SCIP_Real *, int *, int, STP_Bool *)
Definition: graph_path.c:1988
void graph_heap_free(SCIP *, SCIP_Bool, SCIP_Bool, DHEAP **)
Definition: graph_util.c:1034
Definition: heur_tm.h:47
Definition: heur_tm.h:47
SCIP_RETCODE graph_path_st_brmwcs(SCIP *, GRAPH *, const SCIP_Real *, SCIP_Real *, int *, int, STP_Bool *, SCIP_Bool *)
Definition: graph_path.c:2146
static SCIP_RETCODE computeSteinerTreeDijkPcMw(SCIP *scip, GRAPH *g, const SCIP_Real *cost_org, const SCIP_Real *prize, SCIP_Bool costsAreBiased, int start, SPATHSPC *sppc, TMBASE *tmbase)
Definition: heur_tm.c:1168
void SCIPrandomPermuteIntArray(SCIP_RANDNUMGEN *randnumgen, int *array, int begin, int end)
Definition: misc.c:10044
SCIP_Bool stpsol_pruningIsPossible(const GRAPH *g, const int *result, const STP_Bool *connected)
Definition: solstp.c:1307
struct TM_voronoi TMVNOI
static SCIP_RETCODE tmVnoiInit(SCIP *scip, const GRAPH *graph, TMVNOI *tmvnoi)
Definition: heur_tm.c:391
Definition: graphdefs.h:138
static SCIP_RETCODE tmBaseInit(SCIP *scip, const GRAPH *graph, TMBASE *tmbase)
Definition: heur_tm.c:226
static SCIP_RETCODE runTmPcMW(SCIP *scip, GRAPH *graph, const SCIP_Real *cost, const SCIP_Real *prize, enum PCMW_TmMode pcmw_tmmode, int beststart, SCIP_Real *nodepriority, TMBASE *tmbase, SCIP_Bool *success)
Definition: heur_tm.c:2585
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10025
Portable definitions.
Definition: heur_tm.c:90
SCIP_RETCODE SCIPpqueueCreate(SCIP_PQUEUE **pqueue, int initsize, SCIP_Real sizefac, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), SCIP_DECL_PQUEUEELEMCHGPOS((*elemchgpos)))
Definition: misc.c:1236
void shortestpath_computeSteinerTreeRpcMw(const GRAPH *g, int startnode, const SCIP_Real *prize, SPATHSPC *spaths_pc, SPATHS *spaths)
Definition: shortestpath.c:1129
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:477
Definition: heur_tm.h:48
SCIP_RETCODE SCIPpqueueInsert(SCIP_PQUEUE *pqueue, void *elem)
Definition: misc.c:1335
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
static SCIP_RETCODE computeSteinerTreeDijkPcMwFull(SCIP *scip, GRAPH *g, const SCIP_Real *cost_org, int start, TMBASE *tmbase)
Definition: heur_tm.c:1224
void graph_path_st_pcmw_full(GRAPH *, const SCIP_Real *, SCIP_Real *, int *, int, STP_Bool *)
Definition: graph_path.c:1608
Definition: misc_stp.h:53
SCIP_RETCODE SCIPStpHeurTMBuildTreePcMw(SCIP *scip, const GRAPH *g, SCIP_Bool useRootSym, PATH *mst, const SCIP_Real *cost, SCIP_Real *objresult, int *connected)
Definition: heur_tm.c:3012
SCIP_Bool graph_pc_isUnrootedPcMw(const GRAPH *)
Definition: graph_pcbase.c:2669
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:185
SCIP_RETCODE graph_heap_create(SCIP *, int, int *, DENTRY *, DHEAP **)
Definition: graph_util.c:992
Definition: heur_tm.c:127
void shortestpath_computeSteinerTree(const GRAPH *g, int startnode, SPATHS *spaths)
Definition: shortestpath.c:1033
void graph_voronoi(const GRAPH *, const SCIP_Real *, const SCIP_Real *, const STP_Bool *, int *, PATH *)
Definition: graph_vnoi.c:333
SCIP_Real * SCIPprobdataGetXval(SCIP *scip, SCIP_SOL *sol)
Definition: probdata_stp.c:3190
shortest paths based primal heuristics for Steiner problems
void graph_pc_getOrgCostsCsr(SCIP *, const GRAPH *, CSR *)
Definition: graph_pcbase.c:1871
void graph_pc_getOrgCosts(SCIP *, const GRAPH *, SCIP_Real *)
Definition: graph_pcbase.c:1829
static SCIP_RETCODE computeStarts(SCIP *scip, const GRAPH *graph, const int *orgstarts, SCIP_Bool startsgiven, SCIP_Real *nodepriority, TMBASE *tmbase, int *bestp)
Definition: heur_tm.c:787
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:464
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
int * SCIPprobdataGetPctermsorder(SCIP *scip)
Definition: probdata_stp.c:3262
SCIP_Bool solstp_isValid(SCIP *scip, const GRAPH *graph, const int *result)
Definition: solstp.c:1650
static SCIP_Bool pcmwUpdateBestSol_csrInSync(SCIP *scip, const GRAPH *graph, const TMBASE *tmbase)
Definition: heur_tm.c:168
Definition: shortestpath.h:47
static void updateBestSol(SCIP *scip, const GRAPH *graph, int startnode, SCIP_Bool solfound, TMBASE *tmbase, SCIP_Bool *success)
Definition: heur_tm.c:529
Definition: objbenders.h:33
static void tmVnoiFree(SCIP *scip, const GRAPH *graph, TMVNOI *tmvnoi)
Definition: heur_tm.c:424
includes various reduction methods for Steiner tree problems
SCIP_Real solstp_getObj(const GRAPH *g, const int *soledge, SCIP_Real offset)
Definition: solstp.c:1859
void graph_csr_buildCosts(const GRAPH *, const CSR *, const SCIP_Real *, SCIP_Real *RESTRICT)
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:130
static void tmBaseFree(SCIP *scip, const GRAPH *graph, TMBASE *tmbase)
Definition: heur_tm.c:298
SCIP_RETCODE graph_voronoiExtend(SCIP *, const GRAPH *, const SCIP_Real *, PATH *, SCIP_Real **, int **, int **, STP_Bool *, int *, int *, int *, int, int, int)
Definition: graph_vnoi.c:253
Definition: heur_tm.h:48
SCIP_RETCODE solstp_pruneFromTmHeur_csr(SCIP *scip, const GRAPH *g, SPATHS *spaths, int *RESTRICT result)
Definition: solstp.c:1515
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:319