SCIP
Solving Constraint Integer Programs
dpterms.h File Reference
Detailed Description
Dynamic programming solver for Steiner tree (sub-) problems with small number of terminals.
This file implements a dynamic programming method to solve Steiner tree problems to optimality. FPT with respect to the number of terminals. Based on algorithm by Erickson, Monma and Veinott, which itself is a slight extension of Dryefus-Wagner. This implementation uses several reduction methods to improve the practical performance. It also uses a node-separator technique from "Separator-Based Pruned Dynamic Programming for Steiner Tree" by Iwata and Shigemura.
Definition in file dpterms.h.
Go to the source code of this file.
Functions | |
| SCIP_RETCODE | dpterms_solve (SCIP *, GRAPH *, int *, SCIP_Bool *) |
| SCIP_Bool | dpterms_isPromisingEmbarrassingly (const GRAPH *) |
| SCIP_Bool | dpterms_isPromisingFully (const GRAPH *) |
| SCIP_Bool | dpterms_isPromisingPartly (const GRAPH *) |
Function Documentation
◆ dpterms_solve()
| SCIP_RETCODE dpterms_solve | ( | SCIP * | scip, |
| GRAPH * | graph, | ||
| int * | solution, | ||
| SCIP_Bool * | wasSolved | ||
| ) |
solves problem given by graph
- Parameters
-
scip SCIP data structure graph graph of sub-problem solution optimal solution (out) wasSolved was problem solved to optimality?
Definition at line 489 of file dpterms_base.c.
References dpsolverFree(), dpsolverGetSolution(), dpsolverInit(), dpsolverSolve(), graph_free_csr(), graph_init_csrWithEdgeId(), SCIP_CALL, SCIP_OKAY, and solstp_isValid().
Referenced by solveWithDpTerms(), and substpsolver_solve().
◆ dpterms_isPromisingEmbarrassingly()
is DP embarrassingly promising?
- Parameters
-
graph graph
Definition at line 554 of file dpterms_base.c.
References GRAPH::terms.
◆ dpterms_isPromisingFully()
is DP fully promising?
- Parameters
-
graph graph
Definition at line 563 of file dpterms_base.c.
References FALSE, graph_get_nVET(), LT, nnodes, NULL, PROMISING_FULL_LARGE_MINNEDGES, PROMISING_FULL_MAXAVGDEG, PROMISING_FULL_MAXNTERMS, PROMISING_FULL_MAXNTERMS_LARGE, SCIP_Real, GRAPH::terms, and TRUE.
Referenced by dpterms_isPromisingPartly(), reduce_redLoopStp(), and substpsolver_init().
◆ dpterms_isPromisingPartly()
is DP at least partly promising?
- Parameters
-
graph graph
Definition at line 518 of file dpterms_base.c.
References density, dpterms_isPromisingFully(), GRAPH::edges, FALSE, GT, GRAPH::knots, PROMISING_PARTLY_LARGE_MAXNTERMS, PROMISING_PARTLY_LARGE_MINNEDGES, PROMISING_PARTLY_MAXDENSITY, PROMISING_PARTLY_MEDIUM_MAXNTERMS, PROMISING_PARTLY_MEDIUM_MINNEDGES, PROMISING_PARTLY_SMALL_MAXNTERMS, PROMISING_PARTLY_SMALL_MINNEDGES, SCIP_Real, GRAPH::terms, and TRUE.
Referenced by SCIPStpDpRelaxIsPromising().