problemreductions/rules/
pathconstrainednetworkflow_ilp.rs

1//! Reduction from PathConstrainedNetworkFlow to ILP.
2//!
3//! One integer variable per prescribed path. Arc capacity aggregation
4//! across paths and total flow requirement.
5
6use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
7use crate::models::graph::PathConstrainedNetworkFlow;
8use crate::reduction;
9use crate::rules::traits::{ReduceTo, ReductionResult};
10
11/// Result of reducing PathConstrainedNetworkFlow to ILP.
12#[derive(Debug, Clone)]
13pub struct ReductionPCNFToILP {
14    target: ILP<i32>,
15}
16
17impl ReductionResult for ReductionPCNFToILP {
18    type Source = PathConstrainedNetworkFlow;
19    type Target = ILP<i32>;
20
21    fn target_problem(&self) -> &ILP<i32> {
22        &self.target
23    }
24
25    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
26        target_solution.to_vec()
27    }
28}
29
30#[reduction(
31    overhead = {
32        num_vars = "num_paths",
33        num_constraints = "num_arcs + 1",
34    }
35)]
36impl ReduceTo<ILP<i32>> for PathConstrainedNetworkFlow {
37    type Result = ReductionPCNFToILP;
38
39    fn reduce_to(&self) -> Self::Result {
40        let num_paths = self.num_paths();
41        let num_arcs = self.num_arcs();
42        let mut constraints = Vec::new();
43
44        // Arc capacity: sum_{i : a in P_i} f_i <= c_a for all a
45        for arc_idx in 0..num_arcs {
46            let terms: Vec<(usize, f64)> = self
47                .paths()
48                .iter()
49                .enumerate()
50                .filter(|(_, path)| path.contains(&arc_idx))
51                .map(|(path_idx, _)| (path_idx, 1.0))
52                .collect();
53            if !terms.is_empty() {
54                constraints.push(LinearConstraint::le(
55                    terms,
56                    self.capacities()[arc_idx] as f64,
57                ));
58            }
59        }
60
61        // Total flow requirement: sum_i f_i >= R
62        let total_terms: Vec<(usize, f64)> = (0..num_paths).map(|i| (i, 1.0)).collect();
63        constraints.push(LinearConstraint::ge(total_terms, self.requirement() as f64));
64
65        ReductionPCNFToILP {
66            target: ILP::new(num_paths, constraints, vec![], ObjectiveSense::Minimize),
67        }
68    }
69}
70
71#[cfg(feature = "example-db")]
72pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
73    use crate::topology::DirectedGraph;
74
75    vec![crate::example_db::specs::RuleExampleSpec {
76        id: "pathconstrainednetworkflow_to_ilp",
77        build: || {
78            // Simple graph: s=0, t=2, arcs 0->1->2 and 0->2
79            // Two paths: [0,1] (0->1->2) and [2] (0->2)
80            let source = PathConstrainedNetworkFlow::new(
81                DirectedGraph::new(3, vec![(0, 1), (1, 2), (0, 2)]),
82                vec![1, 1, 1],
83                0,
84                2,
85                vec![vec![0, 1], vec![2]],
86                2,
87            );
88            crate::example_db::specs::rule_example_via_ilp::<_, i32>(source)
89        },
90    }]
91}
92
93#[cfg(test)]
94#[path = "../unit_tests/rules/pathconstrainednetworkflow_ilp.rs"]
95mod tests;
problemreductions/rules/pathconstrainednetworkflow_ilp.rs

problemreductions/rules/
pathconstrainednetworkflow_ilp.rs
