Scippy

SCIP

Solving Constraint Integer Programs

heur_tm.h File Reference

Detailed Description

shortest paths based primal heuristics for Steiner problems

Author
Gerald Gamrath
Thorsten Koch
Daniel Rehfeldt
Michael Winkler

This file implements several shortest paths based primal heuristics for Steiner problems, see "SCIP-Jack - A solver for STP and variants with parallelization extensions" by Gamrath, Koch, Maher, Rehfeldt and Shinano

Definition in file heur_tm.h.

#include "scip/scip.h"
#include "grph.h"

Go to the source code of this file.

Macros

#define DEFAULT_HOPFACTOR   0.33
 

Functions

void SCIPStpHeurTMCompStarts (GRAPH *graph, int *starts, int *runs)
 
SCIP_RETCODE SCIPStpIncludeHeurTM (SCIP *scip)
 
SCIP_RETCODE SCIPStpHeurTMRun (SCIP *scip, SCIP_HEURDATA *heurdata, GRAPH *graph, int *starts, int *bestnewstart, int *best_result, int runs, int bestincstart, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *hopfactor, SCIP_Real *nodepriority, SCIP_Real maxcost, SCIP_Bool *success, SCIP_Bool pcmwfull)
 
SCIP_RETCODE SCIPStpHeurTMRunLP (SCIP *scip, GRAPH *graph, SCIP_HEUR *heur, int *result, int runs, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Bool *success)
 
SCIP_RETCODE SCIPStpHeurTMPrune (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int layer, int *result, STP_Bool *connected)
 
SCIP_RETCODE SCIPStpHeurTMPrunePc (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int *result, STP_Bool *connected)
 
SCIP_RETCODE SCIPStpHeurTMBuildTreePcMw (SCIP *scip, const GRAPH *g, PATH *mst, const SCIP_Real *cost, SCIP_Real *objresult, int *connected)
 
SCIP_RETCODE SCIPStpHeurTMBuildTree (SCIP *scip, const GRAPH *g, PATH *mst, const SCIP_Real *cost, SCIP_Real *objresult, int *connected)
 
SCIP_RETCODE SCIPStpHeurTMBuildTreeDc (SCIP *scip, const GRAPH *g, int *result, STP_Bool *connected)
 

Macro Definition Documentation

◆ DEFAULT_HOPFACTOR

#define DEFAULT_HOPFACTOR   0.33

Function Documentation

◆ SCIPStpHeurTMCompStarts()

void SCIPStpHeurTMCompStarts ( GRAPH graph,
int *  starts,
int *  runs 
)

compute starting points among marked (w.r.t. g->mark) vertices for constructive heuristics

Parameters
graphgraph data structure
startsstarting points array
runspointer to number of runs

Definition at line 114 of file heur_tm.c.

References Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, r, GRAPH::source, GRAPH::term, and GRAPH::terms.

Referenced by computeNewSols(), reduce_bound(), and reduce_da().

◆ SCIPStpIncludeHeurTM()

◆ SCIPStpHeurTMRun()

SCIP_RETCODE SCIPStpHeurTMRun ( SCIP scip,
SCIP_HEURDATA heurdata,
GRAPH graph,
int *  starts,
int *  bestnewstart,
int *  best_result,
int  runs,
int  bestincstart,
SCIP_Real cost,
SCIP_Real costrev,
SCIP_Real hopfactor,
SCIP_Real nodepriority,
SCIP_Real  maxcost,
SCIP_Bool success,
SCIP_Bool  pcmwfull 
)

execute shortest paths heuristic to obtain a Steiner tree

Parameters
scipSCIP data structure
heurdataSCIP data structure
graphgraph data structure
startsarray containing start vertices (NULL to not provide any)
bestnewstartpointer to the start vertex resulting in the best solution
best_resultarray indicating whether an arc is part of the solution (CONNECTED/UNKNOWN)
runsnumber of runs
bestincstartbest incumbent start vertex
costarc costs
costrevreversed arc costs
hopfactoredge cost multiplicator for HC problems
nodepriorityvertex priorities for vertices to be starting points (NULL for no priorities)
maxcostmaximal edge cost (only for HC)
successpointer to store whether a solution could be found
pcmwfulluse full computation of tree (i.e. connect all terminals and prune), only for prize-collecting variants

Definition at line 1649 of file heur_tm.c.

References AUTO, BLOCKED, BMSclearMemoryArray, BMScopyMemoryArray, computeDegConsTree(), computeSteinerTree(), computeSteinerTreeDijk(), computeSteinerTreeDijkPcMw(), computeSteinerTreeDijkPcMwFull(), computeSteinerTreeVnoi(), CONNECT, GRAPH::cost, EAT_LAST, GRAPH::edges, fabs(), FALSE, FARAWAY, flipedge, GNODECmpByDist(), GRAPH::grad, graph_path_execX(), graph_pc_2transcheck(), GRAPH::head, GRAPH::hoplimit, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, r, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBuffer, SCIPallocBufferArray, SCIPdebugMessage, SCIPfindHeur(), SCIPfreeBuffer, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPheurGetData(), SCIPisGE(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPisStopped(), SCIPpqueueCreate(), SCIPpqueueFree(), SCIPrandomGetInt(), SCIPrandomGetReal(), SCIPrandomPermuteIntArray(), SCIPsortRealInt(), GRAPH::source, STP_DCSTP, STP_DHCSTP, STP_MWCSP, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, STP_SAP, GRAPH::stp_type, GRAPH::term, GRAPH::terms, TM_DIJKSTRA, TM_SP, TM_VORONOI, TRUE, and UNKNOWN.

Referenced by computeNewSols(), reduce_bound(), reduce_boundHopRc(), reduce_da(), reduce_daPcMw(), reduce_daSlackPruneMw(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), and SCIPStpHeurTMRunLP().

◆ SCIPStpHeurTMRunLP()

SCIP_RETCODE SCIPStpHeurTMRunLP ( SCIP scip,
GRAPH graph,
SCIP_HEUR heur,
int *  result,
int  runs,
SCIP_Real cost,
SCIP_Real costrev,
SCIP_Bool success 
)

run shortest path heuristic, but bias edge costs towards best current LP solution

Parameters
scipSCIP data structure
graphgraph data structure
heurheuristic or NULL
resultarray indicating whether an arc is part of the solution (CONNECTED/UNKNOWN)
runsnumber of runs
costarc costs (uninitialized)
costrevreversed arc costs (uninitialized)
successpointer to store whether a solution could be found

Definition at line 2352 of file heur_tm.c.

References BLOCKED, BMScopyMemoryArray, GRAPH::cost, GRAPH::edges, FALSE, FARAWAY, flipedge, GRAPH::grad, GRAPH::head, Is_term, GRAPH::knots, GRAPH::maxdeg, nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcreateSol(), SCIPepsilon(), SCIPfindHeur(), SCIPfreeBufferArrayNull, SCIPfreeSol(), SCIPgetLPSolstat(), SCIPgetNLPIterations(), SCIPhasCurrentNodeLP(), SCIPheurGetData(), SCIPisGE(), SCIPisGT(), SCIPisLT(), SCIPisZero(), SCIPlinkLPSol(), SCIPprobdataGetVars(), SCIPprobdataGetXval(), SCIPrandomGetInt(), SCIPrandomGetReal(), SCIPStpHeurTMRun(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), GRAPH::source, STP_DCSTP, STP_DHCSTP, STP_MWCSP, STP_PCSPG, STP_RMWCSP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

Referenced by SCIP_DECL_HEUREXEC(), and selectBranchingVertexBySol().

◆ SCIPStpHeurTMPrune()

SCIP_RETCODE SCIPStpHeurTMPrune ( SCIP scip,
const GRAPH g,
const SCIP_Real cost,
int  layer,
int *  result,
STP_Bool connected 
)

prune a Steiner tree in such a way that all leaves are terminals

Parameters
scipSCIP data structure
ggraph structure
costedge costs
layerlayer (usually 0)
resultST edges, which need to be set to UNKNOWN
connectedST nodes

Definition at line 555 of file heur_tm.c.

References EAT_LAST, shortest_path::edge, FALSE, graph_path_exec(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, GRAPH::knots, GRAPH::mark, MST_MODE, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebug, SCIPfreeBufferArray, GRAPH::source, GRAPH::term, GRAPH::terms, and UNKNOWN.

Referenced by graph_sol_getOrg(), prune(), SCIP_DECL_HEUREXEC(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), and SCIPStpHeurRecRun().

◆ SCIPStpHeurTMPrunePc()

SCIP_RETCODE SCIPStpHeurTMPrunePc ( SCIP scip,
const GRAPH g,
const SCIP_Real cost,
int *  result,
STP_Bool connected 
)

◆ SCIPStpHeurTMBuildTreePcMw()

SCIP_RETCODE SCIPStpHeurTMBuildTreePcMw ( SCIP scip,
const GRAPH g,
PATH mst,
const SCIP_Real cost,
SCIP_Real objresult,
int *  connected 
)

build (rooted) prize collecting Steiner tree in such a way that all leaves are positive-weight vertices

build (rooted) prize collecting Steiner tree in such a way that all leaves are terminals

Parameters
scipSCIP data structure
ggraph structure
mstpath data structure array
costedge costs
objresultpointer to store objective value of result
connectedCONNECT/UNKNOWN

Definition at line 382 of file heur_tm.c.

References a, CONNECT, EAT_LAST, shortest_path::edge, FALSE, graph_path_exec(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_state, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

Referenced by SCIPStpHeurPruneUpdateSols().

◆ SCIPStpHeurTMBuildTree()

SCIP_RETCODE SCIPStpHeurTMBuildTree ( SCIP scip,
const GRAPH g,
PATH mst,
const SCIP_Real cost,
SCIP_Real objresult,
int *  connected 
)

build Steiner tree in such a way that all leaves are terminals

Parameters
scipSCIP data structure
ggraph structure
mstpath data structure array
costedge costs
objresultpointer to store objective value of result
connectedCONNECT/UNKNOWN

Definition at line 653 of file heur_tm.c.

References CONNECT, EAT_LAST, shortest_path::edge, FALSE, FARAWAY, graph_path_exec(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_OKAY, SCIP_Real, GRAPH::source, GRAPH::term, and UNKNOWN.

Referenced by SCIPStpHeurPruneUpdateSols().

◆ SCIPStpHeurTMBuildTreeDc()

SCIP_RETCODE SCIPStpHeurTMBuildTreeDc ( SCIP scip,
const GRAPH g,
int *  result,
STP_Bool connected 
)

prune a degree constrained Steiner tree in such a way that all leaves are terminals

Parameters
scipSCIP data structure
ggraph structure
resultST edges
connectedST nodes (to be set)

Definition at line 732 of file heur_tm.c.

References CONNECT, EAT_LAST, FALSE, flipedge, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebug, SCIPfreeBufferArray, GRAPH::source, GRAPH::term, TRUE, and UNKNOWN.

Referenced by computeDegConsTree(), and SCIPStpHeurRecRun().