dpterms_base.c
Go to the documentation of this file.
17 * @brief Dynamic programming solver for Steiner tree (sub-) problems with small number of terminals
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
87 SCIP_CALL( SCIPStpHeurAscendPruneRun(scip, NULL, graph, redcosts_tmp, soledges_tmp, graph->source, &success, FALSE));
536 if( graph->terms <= PROMISING_PARTLY_SMALL_MAXNTERMS && nedges >= PROMISING_PARTLY_SMALL_MINNEDGES )
539 if( graph->terms <= PROMISING_PARTLY_MEDIUM_MAXNTERMS && nedges >= PROMISING_PARTLY_MEDIUM_MINNEDGES )
542 if( graph->terms < PROMISING_PARTLY_LARGE_MAXNTERMS && nedges >= PROMISING_PARTLY_LARGE_MINNEDGES )
578 if( nedges < PROMISING_FULL_LARGE_MINNEDGES && LT((SCIP_Real) nedges / (SCIP_Real) nnodes, PROMISING_FULL_MAXAVGDEG) )
static SCIP_RETCODE dpsolverInitData(SCIP *scip, GRAPH *graph, DPSOLVER *dpsolver)
Definition: dpterms_base.c:302
SCIP_RETCODE dpterms_streeInit(SCIP *scip, int nterms, int nnodes, DPSTREE **dpstree)
Definition: dpterms_util.c:533
#define PROMISING_PARTLY_SMALL_MINNEDGES
Definition: dpterms_base.c:43
Definition: graphdefs.h:184
Definition: struct_scip.h:59
SCIP_RETCODE dpterms_solve(SCIP *scip, GRAPH *graph, int *solution, SCIP_Bool *wasSolved)
Definition: dpterms_base.c:489
SCIP_RETCODE stpprioqueue_create(SCIP *scip, int capacity, STP_PQ **prioqueue)
Definition: stpprioqueue.c:95
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:117
void stpprioqueue_free(SCIP *scip, STP_PQ **prioqueue)
Definition: stpprioqueue.c:121
SCIP_RETCODE solstp_pruneFromNodes(SCIP *scip, const GRAPH *g, int *result, STP_Bool *connected)
Definition: solstp.c:1415
Definition: dualascent.h:39
#define PROMISING_PARTLY_MEDIUM_MAXNTERMS
Definition: dpterms_base.c:44
includes methods for Steiner tree problem solutions
reduction and dual-cost based primal heuristic for Steiner problems
Includes dual-ascent for classic Steiner tree and some variants.
SCIP_RETCODE dpterms_coreSolve(SCIP *scip, GRAPH *graph, DPSOLVER *dpsolver, SCIP_Bool *wasSolved)
Definition: dpterms_core.c:1288
SCIP_Bool dpterms_isPromisingFully(const GRAPH *graph)
Definition: dpterms_base.c:563
Dynamic programming solver for Steiner tree (sub-) problems with small number of terminals.
SCIP_Real * nodes_rootdist
Definition: dptermsinterns.h:100
Definition: dptermsinterns.h:82
SCIP_RETCODE stpprioqueue_insert(SCIP *scip, void *data, int newkey, STP_PQ *prioqueue)
Definition: stpprioqueue.c:236
header only, simple implementation of an STL like vector
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
Definition: dptermsinterns.h:50
static SCIP_RETCODE dpgraphInit(SCIP *scip, const GRAPH *graph, DPGRAPH **dpgraph)
Definition: dpterms_base.c:159
void graph_path_execX(SCIP *, const GRAPH *, int, const SCIP_Real *, SCIP_Real *, int *)
Definition: graph_path.c:905
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
SCIP_Real * csr_redcosts
Definition: dptermsinterns.h:99
priority queue with integer keys
static void dpsolverFreeData(SCIP *scip, DPSOLVER *dpsolver)
Definition: dpterms_base.c:371
static SCIP_RETCODE dpsolverSolve(SCIP *scip, GRAPH *g, DPSOLVER *dpsolver, SCIP_Bool *wasSolved)
Definition: dpterms_base.c:408
static SCIP_RETCODE dpsolverGetSolution(SCIP *scip, GRAPH *graph, DPSOLVER *dpsolver, int *solution)
Definition: dpterms_base.c:423
Definition: dptermsinterns.h:71
SCIP_RETCODE SCIPStpHeurLocalRun(SCIP *scip, GRAPH *graph, int *solEdges)
Definition: heur_local.c:3899
Definition: type_retcode.h:33
header only, simple implementation of a bitset
Improvement heuristic for Steiner problems.
#define PROMISING_PARTLY_MEDIUM_MINNEDGES
Definition: dpterms_base.c:45
void graph_heap_free(SCIP *, SCIP_Bool, SCIP_Bool, DHEAP **)
Definition: graph_util.c:1034
static STP_Bitset stpbitset_newCopy(SCIP *scip, STP_Bitset bitsetOrg)
Definition: stpbitset.h:267
static SCIP_RETCODE dpmiscInit(SCIP *scip, const GRAPH *graph, DPMISC **dpmisc)
Definition: dpterms_base.c:236
Definition: graphdefs.h:138
SCIP_RETCODE graph_init_csrWithEdgeId(SCIP *, GRAPH *)
Definition: graph_util.c:1603
Dynamic programming internals for Steiner tree (sub-) problems with small number of terminals...
Definition: dptermsinterns.h:108
static SCIP_RETCODE dpsolverInit(SCIP *scip, GRAPH *graph, DPSOLVER **dpsolver)
Definition: dpterms_base.c:456
SCIP_Bool stpprioqueue_isClean(const STP_PQ *prioqueue)
Definition: stpprioqueue.c:78
SCIP_RETCODE graph_heap_create(SCIP *, int, int *, DENTRY *, DHEAP **)
Definition: graph_util.c:992
intrusive red black tree datastructure
static void stpbitset_setBitTrue(STP_Bitset bitset, int index)
Definition: stpbitset.h:129
SCIP_Bool solstp_isValid(SCIP *scip, const GRAPH *graph, const int *result)
Definition: solstp.c:1650
#define PROMISING_PARTLY_SMALL_MAXNTERMS
Definition: dpterms_base.c:42
Definition: objbenders.h:33
#define PROMISING_PARTLY_LARGE_MAXNTERMS
Definition: dpterms_base.c:46
SCIP_Bool dpterms_isPromisingEmbarrassingly(const GRAPH *graph)
Definition: dpterms_base.c:554
default SCIP plugins
SCIP_Real solstp_getObj(const GRAPH *g, const int *soledge, SCIP_Real offset)
Definition: solstp.c:1859
SCIP_Bool dpterms_isPromisingPartly(const GRAPH *graph)
Definition: dpterms_base.c:518
#define PROMISING_PARTLY_LARGE_MINNEDGES
Definition: dpterms_base.c:47
void dpterms_streeFree(SCIP *scip, DPSTREE **dpstree)
Definition: dpterms_util.c:560