problemreductions/rules/
prizecollectingsteinerforest_steinertree.rs

1//! Reduction from Prize-Collecting Steiner Forest (PCSF) to Steiner Tree
2//! via the artificial-root + per-vertex prize gadget construction.
3//!
4//! The PCSF objective on `(V, E)` with vertex prizes `p`, edge costs `c`,
5//! tradeoff `beta`, and per-component penalty `omega` is
6//!
7//! ```text
8//! beta * sum_{v notin V_F} p(v) + sum_{e in E_F} c(e) + omega * kappa(F).
9//! ```
10//!
11//! We build a Steiner-tree instance on the augmented graph
12//! `H = (V cup {r} cup {t_v : v in V_p}, E_H)` where `V_p` collects the
13//! vertices with `p(v) > 0`, and
14//!
15//! - every original edge keeps its cost,
16//! - every `v in V` is attached to `r` by an edge of cost `omega` (so each
17//!   tree component of `F` is paid by exactly one root-attachment edge in
18//!   `T*`),
19//! - for every `v in V_p` we add `(v, t_v)` of cost `0` and `(r, t_v)` of
20//!   cost `beta * p(v)`,
21//! - the terminal set is `{r} cup {t_v : v in V_p}`.
22//!
23//! The Steiner-tree optimum then equals the PCSF optimum.
24//!
25//! References:
26//! - Bienstock, Goemans, Simchi-Levi, Williamson, "A note on the prize
27//!   collecting traveling salesman problem," Math. Programming 59 (1993).
28//!   <https://doi.org/10.1007/BF01581256>
29//! - Tuncbag et al., "Simultaneous Reconstruction of Multiple Signaling
30//!   Pathways via the Prize-Collecting Steiner Forest Problem,"
31//!   J. Comput. Biol. 20(2):124--136, 2013.
32//!   <https://doi.org/10.1089/cmb.2012.0092>
33
34use crate::models::graph::{PrizeCollectingSteinerForest, SteinerTree};
35use crate::reduction;
36use crate::rules::traits::{ReduceTo, ReductionResult};
37use crate::topology::{Graph, SimpleGraph};
38
39/// Result of reducing PCSF to SteinerTree.
40///
41/// Stores the original PCSF source parameterss plus the mapping from the target
42/// graph's edge list back to the source variables (the original edge index
43/// for each "original" edge, and the source vertex index for each gadget
44/// include-edge). Other target edges (root-attachment and gadget omit-edges)
45/// are not needed for extraction.
46#[derive(Debug, Clone)]
47pub struct ReductionPCSFToSteinerTree {
48    target: SteinerTree<SimpleGraph, i64>,
49    /// Number of vertices in the source graph (also the prefix size of the
50    /// source configuration's vertex-selector segment).
51    num_source_vertices: usize,
52    /// Number of edges in the source graph (length of the edge-selector
53    /// segment of the source configuration).
54    num_source_edges: usize,
55    /// `target_to_source_edge[i] = Some(j)` iff target edge `i` is the same
56    /// pair as source edge `j`; otherwise the target edge is a gadget edge.
57    target_to_source_edge: Vec<Option<usize>>,
58    /// `target_to_include_vertex[i] = Some(v)` iff target edge `i` is the
59    /// include-edge `(v, t_v)` of the per-vertex prize gadget. Original
60    /// edges and other gadget edges store `None`.
61    target_to_include_vertex: Vec<Option<usize>>,
62}
63
64impl ReductionResult for ReductionPCSFToSteinerTree {
65    type Source = PrizeCollectingSteinerForest<SimpleGraph, i64>;
66    type Target = SteinerTree<SimpleGraph, i64>;
67
68    fn target_problem(&self) -> &SteinerTree<SimpleGraph, i64> {
69        &self.target
70    }
71
72    fn extract_solution(
73        &self,
74        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
75    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
76        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
77
78        Ok({
79            let n = self.num_source_vertices;
80            let m = self.num_source_edges;
81            let mut selected_vertices = vec![false; n];
82            let mut selected_edges = vec![false; m];
83
84            // Mark vertices included via their gadget include-edge `(v, t_v)`,
85            // and edges via the matching original edge.
86            for (target_idx, &selected) in target_solution.iter().enumerate() {
87                if !selected {
88                    continue;
89                }
90                if let Some(v) = self.target_to_include_vertex[target_idx] {
91                    selected_vertices[v] = true;
92                } else if let Some(src_edge) = self.target_to_source_edge[target_idx] {
93                    selected_edges[src_edge] = true;
94                }
95            }
96
97            // Any original edge selected in `T*` forces both endpoints into
98            // `V_F`. The PCSF model rejects configurations where a selected
99            // edge has an unselected endpoint, so we mark endpoints explicitly
100            // (this also covers prize-zero endpoints, which have no gadget).
101            let edges = self.target.graph().edges();
102            for (target_idx, &(_, _)) in edges.iter().enumerate() {
103                if !target_solution[target_idx] {
104                    continue;
105                }
106                if let Some(src_edge) = self.target_to_source_edge[target_idx] {
107                    let (u, v) = self.source_edge_pair(src_edge);
108                    selected_vertices[u] = true;
109                    selected_vertices[v] = true;
110                }
111            }
112
113            (selected_vertices, selected_edges)
114        })
115    }
116}
117
118impl ReductionPCSFToSteinerTree {
119    /// Look up the endpoint pair of the `idx`-th source edge in the target
120    /// graph's edge list (source edges are placed first by construction).
121    fn source_edge_pair(&self, src_edge_idx: usize) -> (usize, usize) {
122        self.target.graph().edges()[src_edge_idx]
123    }
124}
125
126#[reduction(
127    transform = exact {
128        num_vertices = "num_vertices + num_vertices_with_prize + 1",
129        num_edges = "num_edges + num_vertices + 2 * num_vertices_with_prize",
130        num_terminals = "num_vertices_with_prize + 1",
131    }
132)]
133impl ReduceTo<SteinerTree<SimpleGraph, i64>> for PrizeCollectingSteinerForest<SimpleGraph, i64> {
134    type Result = ReductionPCSFToSteinerTree;
135
136    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
137        let n = self.num_vertices();
138        let m = self.num_edges();
139        let source_edges = self.graph().edges();
140        let source_edge_costs = self.edge_costs();
141        let source_prizes = self.vertex_prizes();
142        let beta = *self.beta();
143        let omega = *self.omega();
144
145        // Augmented vertex layout:
146        //   indices 0..n           -- original vertices
147        //   index   n               -- artificial root r
148        //   indices n+1..n+1+k      -- gadget terminals t_v for v in V_p,
149        //                              listed in increasing order of v.
150        let prized: Vec<usize> = (0..n).filter(|&v| source_prizes[v] > 0).collect();
151        let k = prized.len();
152        let root = n;
153        let gadget_terminal = |gadget_pos: usize| -> usize { n + 1 + gadget_pos };
154
155        let target_num_vertices = n + 1 + k;
156        let mut target_edges: Vec<(usize, usize)> = Vec::with_capacity(m + n + 2 * k);
157        let mut target_edge_weights: Vec<i64> = Vec::with_capacity(m + n + 2 * k);
158        let mut target_to_source_edge: Vec<Option<usize>> = Vec::with_capacity(m + n + 2 * k);
159        let mut target_to_include_vertex: Vec<Option<usize>> = Vec::with_capacity(m + n + 2 * k);
160
161        // 1. Original edges keep their cost.
162        for (idx, &(u, v)) in source_edges.iter().enumerate() {
163            target_edges.push((u, v));
164            target_edge_weights.push(source_edge_costs[idx]);
165            target_to_source_edge.push(Some(idx));
166            target_to_include_vertex.push(None);
167        }
168
169        // 2. Root-attachment edge (r, v) of cost omega for every v in V.
170        for v in 0..n {
171            target_edges.push((v, root));
172            target_edge_weights.push(omega);
173            target_to_source_edge.push(None);
174            target_to_include_vertex.push(None);
175        }
176
177        // 3. Per-prized-vertex gadget: (v, t_v) of cost 0 and (r, t_v) of
178        // cost beta * p(v).
179        for (gadget_pos, &v) in prized.iter().enumerate() {
180            let t_v = gadget_terminal(gadget_pos);
181            // include-edge: marks "v is in V_F" with cost 0.
182            target_edges.push((v, t_v));
183            target_edge_weights.push(0);
184            target_to_source_edge.push(None);
185            target_to_include_vertex.push(Some(v));
186            // omit-edge: pays beta * p(v) when v is excluded from V_F.
187            target_edges.push((root, t_v));
188            target_edge_weights.push(beta * source_prizes[v]);
189            target_to_source_edge.push(None);
190            target_to_include_vertex.push(None);
191        }
192
193        // 4. Terminal set: r plus every gadget terminal t_v.
194        let mut terminals: Vec<usize> = Vec::with_capacity(k + 1);
195        terminals.push(root);
196        for gadget_pos in 0..k {
197            terminals.push(gadget_terminal(gadget_pos));
198        }
199
200        let target_graph = SimpleGraph::new(target_num_vertices, target_edges);
201        let target =
202            SteinerTree::<SimpleGraph, i64>::new(target_graph, target_edge_weights, terminals);
203
204        Ok(ReductionPCSFToSteinerTree {
205            target,
206            num_source_vertices: n,
207            num_source_edges: m,
208            target_to_source_edge,
209            target_to_include_vertex,
210        })
211    }
212}
213
214#[cfg(feature = "example-db")]
215pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
216    use crate::example_db::specs::RuleExampleSpec;
217    use crate::export::SolutionPair;
218    use crate::solvers::BruteForce;
219
220    vec![RuleExampleSpec {
221        id: "prize_collecting_steiner_forest_to_steiner_tree",
222        build: || {
223            // Issue #1027 canonical instance with the omit-edge actually
224            // selected at the optimum: path 0 - 1 - 2 with c(0,1)=10,
225            // c(1,2)=10, prizes p = (5, 1, 5), beta = 1, omega = 1. The
226            // optimum drops vertex 1 (paying p(1) = 1) rather than paying a
227            // size-10 edge to reach it.
228            let source = PrizeCollectingSteinerForest::<SimpleGraph, i64>::new(
229                SimpleGraph::new(3, vec![(0, 1), (1, 2)]),
230                vec![5, 1, 5],
231                vec![10, 10],
232                1,
233                1,
234            )
235            .unwrap();
236            let reduction = <PrizeCollectingSteinerForest<SimpleGraph, i64> as ReduceTo<
237                SteinerTree<SimpleGraph, i64>,
238            >>::reduce_to(&source)
239            .expect("reduction should succeed");
240            let target = reduction.target_problem();
241            let target_config = BruteForce::new()
242                .solve(target)
243                .expect("canonical target evaluation must succeed")
244                .expect("canonical PCSF -> SteinerTree example must have an optimal target tree");
245            let source_config = reduction.extract_solution(&target_config).unwrap();
246            crate::example_db::specs::assemble_rule_example(
247                &source,
248                target,
249                vec![SolutionPair {
250                    source_config: serde_json::to_value(source_config)
251                        .expect("solution serialization must succeed"),
252                    target_config: serde_json::to_value(target_config)
253                        .expect("solution serialization must succeed"),
254                }],
255            )
256        },
257    }]
258}
259
260#[cfg(test)]
261#[path = "../unit_tests/rules/prizecollectingsteinerforest_steinertree.rs"]
262mod tests;
problemreductions/rules/prizecollectingsteinerforest_steinertree.rs

problemreductions/rules/
prizecollectingsteinerforest_steinertree.rs
