krashkov / pcsteiner

R Package: Convenient tool for solving the Prize-Collecting Steiner Tree problem

pcSteiner

The Steiner tree problem is a well-known combinatorial optimization problem which asks a minimum spanning subtree containing a given subset of vertices (terminals). However, in many practical applications nodes and edges have an additional numerical value which represents their significance. That is where the Prize-Collecting Steiner Tree problem arises: the goal is to find a subgraph connecting all the terminals with the most expensive nodes and least expensive edges. Since this problem is proven to be NP-hard, exact and efficient algorithm does not exist. Loopy belief propagation can be utilised to obtain an approximate solution to this problem [1,2].

Installation

To get the latest version of the package and install it from CRAN run the following command:

install.packages("pcSteiner")

References

1. M. Bayati, C. Borgs, A. Braunstein, J. Chayes, A. Ramezanpour, and R. Zecchina, "Statistical Mechanics of Steiner Trees". PRL, 2008.
2. I. Biazzo, A. Braunstein and R. Zecchina, "Performance of a cavity-method-based algorithm for the prize-collecting Steiner tree problem on graphs". PRL, 2012.

pcsteiner's Issues

No solutions; what is "eps"

I`m having a couple of issues even when only modifying the example in the Vignette. I initially modified it to a classical Steiner tree with all node prizes and edge costs = 1. As in this case there are equivalent solutions, I modified it as follows:

rm(list=ls())
cat("\014") #is the code to send ctrl+L to the console and therefore will clear the screen
plot.new()
library(pcSteiner)

g <- graph('Bull')
par(mar=c(0,0,0,0))
plot(g,edge.label=E(g))

V(g)
V(g)$prizes= c(1,1,1,1,1)
E(g)
E(g)$costs= c(1.1,1,1,1,1)

#run m times
par(mar=c(4,4,1,1))
m= 30
eps_val= 1E-5
costs= c()
for (i in 1:m) {
#set.seed(1)
tree= pcs.tree(graph=g,terminals=c(4,5),lambda=1,root=5,depth=5, eps=eps_val, max_iter=10)
#avoid similar solutions
costs[i]= tree$cost
}
costs[is.infinite(costs)]= 10
plot(1:m,costs,xlab='iteration',ylab='cost',main=paste('eps:',eps_val))

Apparently, running the pcs.tree multiple times leads to different outputs: Either a cost of 4 or no solution. I understand that a heuristic may yield different solutions on repeat runs, but in this case, the tolerance value seems low enough that this should not be the case. Having said that, I dont fully understand what the 'eps' does. In the example in the vignette its '-1', while in the documentation it's 1E-3.
Is it the case that pcs.tree decides to return no solution (cost = Inf; all edges == FALSE) if there are multiple equivalent solutions?
Also, in the above case, why is 4 returned as cost in cases where three edges, each at a cost of 1 are selected?

Thank you.