heur_local.c
Go to the documentation of this file.
20 * This file implements several local heuristics, including vertex insertion, key-path exchange and key-vertex elimination,
21 * ("Fast Local Search for Steiner Trees in Graphs" by Uchoa and Werneck). Other heuristics are for PCSTP and MWCSP.
27 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
37 /* @note if heuristic is running in root node timing is changed there to (SCIP_HEURTIMING_DURINGLPLOOP |
48 #define HEUR_TIMING (SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE)
59 #define GREEDY_MAXRESTARTS 3 /**< Max number of restarts for greedy PC/MW heuristic if improving solution has been found. */
60 #define GREEDY_EXTENSIONS_MW 6 /**< Number of extensions for greedy MW heuristic. MUST BE HIGHER THAN GREEDY_EXTENSIONS */
110 /** computes lowest common ancestors for all pairs {vbase(v), vbase(u)} such that {u,w} is a boundary edge,
126 int* uboundpaths; /* boundary-paths (each one represented by its boundary edge) having node 'u' as an endpoint */
139 SCIP_CALL( lca(scip, graph, v, uf, nodesmark, steineredges, lcalists, boundpaths, heapsize, vbase) );
156 /* if the ancestor of 'u' and 'v' is one of the two, the boundary-edge is already in boundpaths[u] */
173 /** checks whether node is crucial, i.e. a terminal or a vertex with degree at least 3 (w.r.t. the steinertree) */
212 int* best_result /**< array indicating whether an arc is part of the solution (CONNECTED/UNKNOWN) */
267 SCIP_CALL( SCIPStpHeurLocalExtendPcMw(scip, graph, cost, vnoi, best_result, steinertree, &dummy) );
294 if( probtype == STP_SPG || probtype == STP_RSMT || probtype == STP_OARSMT || probtype == STP_GSTP || (mwpc) )
334 /* if vertex i is not in the current ST and has at least two adjacent nodes, it might be added */
342 /* if an outgoing edge of vertex i points to the current ST, SCIPlinkcuttreeLink the edge to a list */
381 /* next vertex in the current Steiner tree adjacent to vertex i resp. v (the one being scrutinized for possible insertion) */
393 minweight = SCIPlinkcuttreeFindMinChain(scip, graph->prize, graph->head, stdeg, firstnode, &chainfirst, &chainlast);
465 /* finally, cut the edge added first (if it had been cut during the insertion process, it would have been restored above) */
555 * if node i is in the current ST, blists_start[i] points to a linked list of all nodes having i as their base */
722 SCIP_CALL( SCIPpairheapInsert(scip, &boundpaths[vbase[node]], e, edgecost, &(heapsize[vbase[node]])) );
723 SCIP_CALL( SCIPpairheapInsert(scip, &boundpaths[vbase[adjnode]], flipedge(e), edgecost, &(heapsize[vbase[adjnode]])) );
728 SCIP_CALL( lca(scip, graph, root, &uf, nodesmark, best_result, lvledges_start, boundpaths, heapsize, vbase) );
733 /* henceforth, nodesmark will be used to mark the current supervertices (except for the one representing the root-component) */
754 if( !pinned[crucnode] && !Is_term(graph->term[crucnode]) && nodeIsCrucial(graph, best_result, crucnode) )
768 if( (best_result[edge] > -1 && steinertree[graph->head[edge]]) || (best_result[flipedge(edge)] > -1 && steinertree[graph->tail[edge]]) )
786 while( !pinned[adjnode] && !nodeIsCrucial(graph, best_result, adjnode) && steinertree[adjnode] )
843 while( !pinned[adjnode] && !nodeIsCrucial(graph, best_result, adjnode) && steinertree[adjnode] )
871 /* reset all nodes (referred to as 'C' henceforth) whose bases are internal nodes of the current key-paths */
896 /* add vertical boundary-paths between the child components and the root-component (wrt node 'crucnode') */
906 node = (vbase[graph->head[edge]] == UNKNOWN)? UNKNOWN : SCIPStpunionfindFind(&uf, vbase[graph->head[edge]]);
908 /* check whether edge 'edge' represents a boundary-path having an endpoint in the kth-component and in the root-component respectively */
938 /* try to connect the nodes of C (directly) to COMP(C), as a preprocessing for graph_voronoiRepair */
953 /* check whether the adjacent node is not in C and allows a better voronoi assignment of the current node */
954 if( state[adjnode] == CONNECT && SCIPisGT(scip, vnoi[node].dist, vnoi[adjnode].dist + graph->cost[edge])
973 graph_voronoiRepairMult(scip, graph, graph->cost, &count, vbase, boundedges, &nboundedges, nodesmark, &uf, vnoi);
975 /* create a supergraph, having the endpoints of the key-paths incident to the current crucial node as (super-) vertices */
996 /* if node 'node' or 'adjnode' belongs to the root-component, take the (temporary) root-component identifier instead */
1002 graph_edge_add(scip, supergraph, supernodesid[node], supernodesid[adjnode], edgecost, edgecost);
1114 for( node = graph->tail[edge], adjnode = graph->head[edge]; node != vbase[node]; adjnode = node, node = graph->tail[vnoi[node].edge] )
1128 if( !Is_term(graph->term[node]) && scanned[node] && !pinned[node] && SCIPStpunionfindFind(&uf, node) == node )
1137 if( best_result[edge] == CONNECT && graphmark[adjnode] && steinertree[adjnode] && SCIPStpunionfindFind(&uf, adjnode) != node )
1142 SCIPpairheapMeldheaps(scip, &boundpaths[node], &boundpaths[adjnode], &heapsize[node], &heapsize[adjnode]);
1168 SCIPpairheapMeldheaps(scip, &boundpaths[node], &boundpaths[adjnode], &heapsize[node], &heapsize[adjnode]);
1175 /* mark the start node (lying in the root-component of the ST) of the current boundary-path as pinned,
1197 if( best_result[vnoi[node].edge] != CONNECT && best_result[flipedge(vnoi[node].edge)] != CONNECT )
1223 /* meld the heap pertaining to 'crucnode' and all heaps pertaining to descendant key-paths of node 'crucnode' */
1226 SCIPpairheapMeldheaps(scip, &boundpaths[crucnode], &boundpaths[kpnodes[k]], &heapsize[crucnode], &heapsize[kpnodes[k]]);
1230 SCIPpairheapMeldheaps(scip, &boundpaths[crucnode], &boundpaths[supernodes[k]], &heapsize[crucnode], &heapsize[supernodes[k]]);
1258 /* restore data of all nodes having the current (internal) key-path node as their voronoi base */
1296 SCIPpairheapMeldheaps(scip, &boundpaths[crucnode], &boundpaths[adjnode], &heapsize[crucnode], &heapsize[adjnode]);
1322 SCIPpairheapMeldheaps(scip, &boundpaths[crucnode], &boundpaths[adjnode], &heapsize[crucnode], &heapsize[adjnode]);
1350 /* reset all nodes (henceforth referred to as 'C') whose bases are internal nodes of the current keypath */
1374 SCIP_CALL( SCIPpairheapDeletemin(scip, &e, &edgecost, &boundpaths[crucnode], &(heapsize[crucnode])) );
1385 SCIP_CALL( SCIPpairheapInsert(scip, &boundpaths[crucnode], e, edgecost, &(heapsize[crucnode])) );
1402 /* try to connect the nodes of C (directly) to COMP(C), as a preprocessing for voronoi-repair */
1416 /* check whether the adjacent node is not in C and allows a better voronoi assignment of the current node */
1417 if( state[adjnode] == CONNECT && SCIPisGT(scip, vnoi[node].dist, vnoi[adjnode].dist + graph->cost[edge])
1449 edgecost = vnoi[graph->tail[newedge]].dist + graph->cost[newedge] + vnoi[graph->head[newedge]].dist;
1496 /* flip all edges on the ST path between the endnode of the new key-path and the current crucial node */
1521 if( !Is_term(graph->term[node]) && scanned[node] && !pinned[node] && SCIPStpunionfindFind(&uf, node) == node )
1527 if( best_result[edge] == CONNECT && steinertree[adjnode] && graphmark[adjnode] && SCIPStpunionfindFind(&uf, adjnode) != node )
1531 SCIPpairheapMeldheaps(scip, &boundpaths[node], &boundpaths[adjnode], &heapsize[node], &heapsize[adjnode]);
1557 SCIPpairheapMeldheaps(scip, &boundpaths[node], &boundpaths[adjnode], &heapsize[node], &heapsize[adjnode]);
1698 STP_Bool* stvertex, /**< uninitialized array to indicate whether a vertex is part of the Steiner tree */
1994 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
2019 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
2086 if( graph->stp_type != STP_SPG && graph->stp_type != STP_RSMT && graph->stp_type != STP_OARSMT &&
2148 if( graph->stp_type == STP_PCSPG || graph->stp_type == STP_RPCSPG || graph->stp_type == STP_MWCSP )
2200 if( graph->stp_type == STP_PCSPG || graph->stp_type == STP_RPCSPG || graph->stp_type == STP_MWCSP )
2241 if( heurdata->nbestsols < heurdata->maxnsols && SCIPisGT(scip, SCIPgetSolOrigObj(scip, bestsol) - SCIPprobdataGetOffset(scip), pobj) )
2246 SCIPdebugMessage("success in local: old: %f new: %f \n", (SCIPgetSolOrigObj(scip, bestsol) - SCIPprobdataGetOffset(scip)), pobj);
2254 if( heurdata->nbestsols > DEFAULT_MINNBESTSOLS && heurdata->nfails > 1 && graph->stp_type != STP_MWCSP )
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
Definition: type_result.h:47
void graph_voronoi(SCIP *scip, const GRAPH *, SCIP_Real *, SCIP_Real *, STP_Bool *, int *, PATH *)
Definition: grphpath.c:1751
SCIP_RETCODE SCIPStpunionfindInit(SCIP *scip, UF *uf, int length)
Definition: misc_stp.c:689
SCIP_Real SCIPlinkcuttreeFindMinChain(SCIP *scip, const SCIP_Real *nodeweight, const int *head, const int *stdeg, const NODE *start, NODE **first, NODE **last)
Definition: misc_stp.c:258
Definition: struct_scip.h:59
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip_heur.c:233
Definition: struct_misc.h:69
void SCIPpairheapMeldheaps(SCIP *scip, PHNODE **root1, PHNODE **root2, int *sizeroot1, int *sizeroot2)
Definition: misc_stp.c:599
Definition: struct_var.h:198
Definition: misc_stp.h:65
SCIP_RETCODE SCIPStpIncludeHeurLocal(SCIP *scip)
Definition: heur_local.c:2272
Problem data for stp problem.
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
SCIP_RETCODE SCIPpairheapDeletemin(SCIP *scip, int *element, SCIP_Real *key, PHNODE **root, int *size)
Definition: misc_stp.c:562
void graph_voronoiRepair(SCIP *, const GRAPH *, SCIP_Real *, int *, int *, PATH *, int *, int, UF *)
Definition: grphpath.c:2979
NODE * SCIPlinkcuttreeFindMax(SCIP *scip, const SCIP_Real *cost, NODE *v)
Definition: misc_stp.c:327
GRAPH * SCIPprobdataGetGraph(SCIP_PROBDATA *probdata)
Definition: probdata_stp.c:2357
void graph_voronoiRepairMult(SCIP *, const GRAPH *, SCIP_Real *, int *, int *, int *, int *, STP_Bool *, UF *, PATH *)
Definition: grphpath.c:3057
Definition: struct_sol.h:64
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:464
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
Definition: misc_stp.h:80
void graph_path_st_pcmw_extend(SCIP *, const GRAPH *, const SCIP_Real *, PATH *, STP_Bool *, SCIP_Bool *)
Definition: grphpath.c:1410
Definition: type_result.h:35
SCIP_RETCODE SCIPprobdataAddNewSol(SCIP *scip, SCIP_Real *nval, SCIP_SOL *sol, SCIP_HEUR *heur, SCIP_Bool *success)
Definition: probdata_stp.c:3153
Definition: misc_stp.h:57
SCIP_Bool graph_sol_valid(SCIP *, const GRAPH *, const int *)
Definition: grphbase.c:3070
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1350
void SCIPStpunionfindClear(SCIP *scip, UF *uf, int length)
Definition: misc_stp.c:708
void graph_path_exec(SCIP *, const GRAPH *, const int, int, const SCIP_Real *, PATH *)
Definition: grphpath.c:491
Definition: type_retcode.h:33
void SCIPStpunionfindUnion(UF *uf, int p, int q, SCIP_Bool compress)
Definition: misc_stp.c:752
SCIP_RETCODE SCIPStpHeurLocalExtendPcMw(SCIP *scip, GRAPH *graph, const SCIP_Real *cost, PATH *path, int *stedge, STP_Bool *stvertex, SCIP_Bool *extensions)
Definition: heur_local.c:1692
Definition: struct_heur.h:88
Improvement heuristic for Steiner problems.
int GNODECmpByDist(void *first_arg, void *second_arg)
SCIP_RETCODE SCIPStpValidateSol(SCIP *, const GRAPH *, const double *, SCIP_Bool *)
Definition: validate.c:136
SCIP_Real graph_sol_getObj(const SCIP_Real *, const int *, SCIP_Real, int)
Definition: grphbase.c:3200
SCIP_RETCODE SCIPpairheapInsert(SCIP *scip, PHNODE **root, int element, SCIP_Real key, int *size)
Definition: misc_stp.c:528
static STP_Bool nodeIsCrucial(const GRAPH *graph, int *steineredges, int node)
Definition: heur_local.c:175
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 SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
Definition: misc_stp.h:41
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
static void dfsorder(const GRAPH *graph, const int *edges, const int *node, int *counter, int *dfst)
Definition: heur_local.c:86
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
SCIP_Real * SCIPprobdataGetXval(SCIP *scip, SCIP_SOL *sol)
Definition: probdata_stp.c:2551
SCIP_RETCODE SCIPStpHeurTMPrunePc(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int *result, STP_Bool *connected)
Definition: heur_tm.c:167
SCIP_RETCODE SCIPStpHeurLocalRun(SCIP *scip, GRAPH *graph, const SCIP_Real *cost, int *best_result)
Definition: heur_local.c:208
shortest paths based primal heuristics for Steiner problems
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip_heur.c:217
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
SCIP_RETCODE SCIPpairheapBuffarr(SCIP *scip, PHNODE *root, int size, int **elements)
Definition: misc_stp.c:670
static SCIP_RETCODE lca(SCIP *scip, const GRAPH *graph, int u, UF *uf, STP_Bool *nodesmark, int *steineredges, IDX **lcalists, PHNODE **boundpaths, int *heapsize, int *vbase)
Definition: heur_local.c:113
Definition: objbenders.h:33
SCIP_RETCODE SCIPStpHeurTMPrune(SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int layer, int *result, STP_Bool *connected)
Definition: heur_tm.c:555
void graph_edge_add(SCIP *, GRAPH *, int, int, double, double)
SCIP_RETCODE SCIPpqueueInsert(SCIP_PQUEUE *pqueue, void *elem)
Definition: misc.c:1335