Solving Constraint Integer Programs

dpterms.h File Reference

Detailed Description

Dynamic programming solver for Steiner tree (sub-) problems with small number of terminals.

Daniel Rehfeldt

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.

#include "scip/scip.h"
#include "graph.h"

Go to the source code of this file.


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

scipSCIP data structure
graphgraph of sub-problem
solutionoptimal solution (out)
wasSolvedwas 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()

SCIP_Bool dpterms_isPromisingEmbarrassingly ( const GRAPH graph)

is DP embarrassingly promising?


Definition at line 554 of file dpterms_base.c.

References GRAPH::terms.

◆ dpterms_isPromisingFully()

SCIP_Bool dpterms_isPromisingFully ( const GRAPH graph)

◆ dpterms_isPromisingPartly()