subOptimalSteinerProblem: Collect degenerate and sub-optimal solutions to Steiner...

In adamsardar/stoneTrees: Solve Node Centric Steiner Tree Problems

Collect degenerate and sub-optimal solutions to Steiner problems (MStTP or MWCS) with uniform or no edge weights.

Description

Rather than find just a single solution to a MStTP/MWCS, one can populate a solution pool with multiple degenerate/tolerable solutions.

Format

R6Class subOptimalSteinerProblem Construct an object representation of a multiple-solution Steiner tree/maximum weight connected subgraph (MWCS) problem

Details

This class is derived from *nodeCentricSteinerTreeProblem*: all methods available in the superclass are available here. The difference is that after each acceptable solution is found, the solution is a.) stored in a solution pool and b.) used to generate a 'novelty' constraint on future solutions.

methods

Alongisde those for *nodeCentricSteinerTreeProblem*

new(network, solverChoice = chooseSolver(), verbose = TRUE, presolveGraph = TRUE, solverTimeLimit = 300, solverTrace = as.integer(verbose), solutionTolerance = 0)

Constructor for the subOptimalSteinerProblem class. Alongside the arguments for the super-class constructor, there is also 'solutionTolerance', which instructs the object as to the gap between optimal and observed solution that is acceptable.

identifyMultipleSteinerSolutions(maxItr = 10)

Add solutions to the solution pool. maxItr is an argument dictating the number of runs through the optimsation procedure.

getSolutionPoolGraphs(collapseSols = TRUE)

Either return a list of solutions within tolerance (collapseSols = FALSE) or pool all solutions together and return a single graph (collapseSols = TRUE, defaults)

getSolutionPoolScores()

Compute the scores of the solutions in the solution pool. These are in the same order as the list of graphs returned by $getSolutionPoolGraphs(FALSE)

getOptimumScore()

Returns the optimum score from solutions in the solution pool

getSolutionTolerance()

Retreive the tolerance that permits a solution to be added to the solution pool in future calls to $identifyMultipleSteinerSolutions()

setSolutionTolerance(x)

Alter the tolerance that permits a solution to be added to the solution pool in future calls to $identifyMultipleSteinerSolutions()

Super class

stoneTrees::nodeCentricSteinerTreeProblem -> subOptimalSteinerProblem

Methods

Public methods

• subOptimalSteinerProblem$new()

• subOptimalSteinerProblem$getSolutionPool()

• subOptimalSteinerProblem$getSolutionPoolGraphs()

• subOptimalSteinerProblem$getSolutionPoolScores()

• subOptimalSteinerProblem$getOptimumScore()

• subOptimalSteinerProblem$getNoveltyConstraints()

• subOptimalSteinerProblem$getSolutionTolerance()

• subOptimalSteinerProblem$setSolutionTolerance()

• subOptimalSteinerProblem$getNconnectivityConstraintsCalls()

• subOptimalSteinerProblem$identifyMultipleSteinerSolutions()

• subOptimalSteinerProblem$clone()

Inherited methods

• stoneTrees::nodeCentricSteinerTreeProblem$findSingleSteinerSolution()

• stoneTrees::nodeCentricSteinerTreeProblem$getConnectivityConstraints()

• stoneTrees::nodeCentricSteinerTreeProblem$getCurrentSolutionGraph()

• stoneTrees::nodeCentricSteinerTreeProblem$getCurrentSolutionScore()

• stoneTrees::nodeCentricSteinerTreeProblem$getEdgeDT()

• stoneTrees::nodeCentricSteinerTreeProblem$getFixedTerminalConstraints()

• stoneTrees::nodeCentricSteinerTreeProblem$getNodeDT()

• stoneTrees::nodeCentricSteinerTreeProblem$getNodeDegreeConstraints()

• stoneTrees::nodeCentricSteinerTreeProblem$getTerminals()

• stoneTrees::nodeCentricSteinerTreeProblem$getTwoCycleConstraints()

• stoneTrees::nodeCentricSteinerTreeProblem$getnConnectivityConstraintsCalls()

• stoneTrees::nodeCentricSteinerTreeProblem$isSolutionConnected()

---

Method new()

Usage

subOptimalSteinerProblem$new(
  network,
  solverChoice = chooseSolver(),
  verbose = TRUE,
  presolveGraph = TRUE,
  solverTimeLimit = 300,
  solutionTolerance = 0,
  solverTrace = as.integer(verbose)
)

---

Method getSolutionPool()

Usage

subOptimalSteinerProblem$getSolutionPool()

---

Method getSolutionPoolGraphs()

Usage

subOptimalSteinerProblem$getSolutionPoolGraphs(collapseSols = TRUE)

---

Method getSolutionPoolScores()

Usage

subOptimalSteinerProblem$getSolutionPoolScores()

---

Method getOptimumScore()

Usage

subOptimalSteinerProblem$getOptimumScore()

---

Method getNoveltyConstraints()

Usage

subOptimalSteinerProblem$getNoveltyConstraints()

---

Method getSolutionTolerance()

Usage

subOptimalSteinerProblem$getSolutionTolerance()

---

Method setSolutionTolerance()

Usage

subOptimalSteinerProblem$setSolutionTolerance(x)

---

Method getNconnectivityConstraintsCalls()

Usage

subOptimalSteinerProblem$getNconnectivityConstraintsCalls()

---

Method identifyMultipleSteinerSolutions()

Usage

subOptimalSteinerProblem$identifyMultipleSteinerSolutions(maxItr = 10)

---

Method clone()

The objects of this class are cloneable with this method.

Usage

subOptimalSteinerProblem$clone(deep = FALSE)

Arguments

deep

Whether to make a deep clone.

References

Fischetti M, Leitner M, Ljubić I, Luipersbeck M, Monaci M, Resch M, et al. Thinning out Steiner trees: a node-based model for uniform edge costs. Math Program Comput. dimacs11.cs.princeton.edu; 2017;9: 203–229.

Beisser D, Klau GW, Dandekar T, Müller T, Dittrich MT. BioNet: An R-Package for the functional analysis of biological networks. Bioinformatics. 2010;26: 1129–1130.

https://en.wikipedia.org/wiki/Steiner_tree_problem

See Also

nodeCentricSteinerTreeProblem

Other SteinerProblemSolver: nodeCentricSteinerForestProblem, nodeCentricSteinerTreeProblem

Examples

library(igraph)

 # Maximum-Weight Connected Subgraph (MWCS) - find sub-optimal solutions

 ## Vertex attribute details node costs/prizes
 head(V(lymphomaGraph)$nodeScore)

 lymphoma_multiMWCS = subOptimalSteinerProblem$new(lymphomaGraph, solutionTolerance = 0.5)

 #Populate the solution pool with multiple solutions - notice the
 lymphoma_multiMWCS$identifyMultipleSteinerSolutions()

 lymphoma_multiMWCS$getSolutionPoolGraphs(collapseSols = FALSE)

 lymphoma_multiMWCS$getSolutionPoolScores()

 #All solution scores are within tolerance
 diff(range(lymphoma_multiMWCS$getSolutionPoolScores()))

adamsardar/stoneTrees documentation built on May 20, 2022, 7:38 p.m.