Prize-Collecting Steiner Trees (PCSTs)#

The PCST is a generalization of the Steiner Tree problem. In PCST, each vertex has a prize associated with it, and each edge has a cost. The objective is to find a tree that maximizes the difference between the total prize collected from the vertices in the tree and the total cost of the edges used. Unlike the Steiner Tree problem, where you must connect all terminal vertices, in PCST, you can choose to exclude some vertices (even terminal vertices) if the cost of connecting them is too high relative to their prize. The optimization problem is defined as:

\[ \text{argmin}_{x_v, y_e} L(x_v, y_e) = \sum_{e \in E} c_e y_e - \sum_{v \in V} p_v x_v \]

Where \(c_e\) is the cost of edge \(e\), \(p_v\) is the prize of vertex \(v\), \(x_v\) is a binary variable indicating whether vertex \(v\) is included in the tree, and \(y_e\) is a binary variable indicating whether edge \(e\) is included in the tree.

import numpy as np

import corneto as cn

cn.info()
Installed version:v1.0.0a0 (latest: v1.0.0-alpha)
Available backends:CVXPY v1.5.3, PICOS v2.4.17
Default backend (corneto.opt):CVXPY
Installed solvers:CLARABEL, CVXOPT, ECOS, ECOS_BB, GLPK, GLPK_MI, OSQP, SCIP, SCIPY, SCS
Graphviz version:v0.20.3
Repository:https://github.com/saezlab/corneto

We will create an undirected graph, where each edge has a weight of 1.0

from corneto._graph import EdgeType

G = cn.Graph()
G.add_edges(
    [
        ("A", "B"),
        ("A", "C"),
        ("A", "D"),
        ("D", "C"),
        ("D", "E"),
        ("B", "E"),
        ("E", "F"),
        ("A", "F"),
        ("F", "G"),
        ("F", "H"),
        ("H", "E"),
        ("I", "F"),
        ("D", "I"),
        ("J", "C"),
        ("J", "G"),
        ("C", "F"),
        ("J", "A"),
        ("I", "K"),
        ("H", "K"),
        ("B", "K"),
    ],
    type=EdgeType.UNDIRECTED,
    weight=1,
)
G.plot()
../../_images/7f176e8aefe22527503d15d10b915a9a5eefd54115b760202c03c7a83610c2ff.svg 
# We will put prizes only in two nodes

prizes = {"G": 10, "B": 10}

from corneto.methods.steiner import exact_steiner_tree

P, Gc = exact_steiner_tree(G, prizes)
P.solve(solver="SCIPY")

for n, o in zip(["Edge cost", "Prizes"], P.objectives):
    print(f"{n}:", o.value)

Edge cost: 3.0
Prizes: 20.0

Gc.edge_subgraph(np.where(P.symbols["_flow_i"].value)[0]).plot()
../../_images/0d03bcd2f66548837ee2c7089a03f4d6ff32f55b3fd5204568147c7b6daddd9c.svg
Show Source