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<i64>,
15}
16
17impl ReductionResult for ReductionPCNFToILP {
18    type Source = PathConstrainedNetworkFlow;
19    type Target = ILP<i64>;
20
21    fn target_problem(&self) -> &ILP<i64> {
22        &self.target
23    }
24
25    fn extract_solution(
26        &self,
27        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
28    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
29        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
30
31        crate::rules::ilp_helpers::decode_usize_values(target_solution)
32    }
33}
34
35#[reduction(
36    transform = exact {
37        num_vars = "num_paths",
38        num_constraints = "num_arcs + 1",
39    },
40    unavailable = {
41        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
42    }
43)]
44impl ReduceTo<ILP<i64>> for PathConstrainedNetworkFlow {
45    type Result = ReductionPCNFToILP;
46
47    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
48        let num_paths = self.num_paths();
49        let num_arcs = self.num_arcs();
50        let mut constraints = Vec::new();
51
52        // Arc capacity: sum_{i : a in P_i} f_i <= c_a for all a
53        for arc_idx in 0..num_arcs {
54            let terms: Vec<(usize, i64)> = self
55                .paths()
56                .iter()
57                .enumerate()
58                .filter(|(_, path)| path.contains(&arc_idx))
59                .map(|(path_idx, _)| (path_idx, 1))
60                .collect();
61            if !terms.is_empty() {
62                constraints.push(LinearConstraint::le(terms, self.capacities()[arc_idx]));
63            }
64        }
65
66        // Total flow requirement: sum_i f_i >= R
67        let total_terms: Vec<(usize, i64)> = (0..num_paths).map(|i| (i, 1)).collect();
68        constraints.push(LinearConstraint::ge(total_terms, self.requirement()));
69
70        Ok(ReductionPCNFToILP {
71            target: ILP::new(num_paths, constraints, vec![], ObjectiveSense::Minimize)
72                .map_err(Self::target_construction)?,
73        })
74    }
75}
76
77#[cfg(feature = "example-db")]
78pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
79    use crate::topology::DirectedGraph;
80
81    vec![crate::example_db::specs::RuleExampleSpec {
82        id: "pathconstrainednetworkflow_to_ilp",
83        build: || {
84            // Simple graph: s=0, t=2, arcs 0->1->2 and 0->2
85            // Two paths: [0,1] (0->1->2) and [2] (0->2)
86            let source = PathConstrainedNetworkFlow::new(
87                DirectedGraph::new(3, vec![(0, 1), (1, 2), (0, 2)]),
88                vec![1, 1, 1],
89                0,
90                2,
91                vec![vec![0, 1], vec![2]],
92                2,
93            );
94            crate::example_db::specs::rule_example_via_ilp::<_, i64>(source)
95        },
96    }]
97}
98
99#[cfg(test)]
100#[path = "../unit_tests/rules/pathconstrainednetworkflow_ilp.rs"]
101mod tests;
problemreductions/rules/pathconstrainednetworkflow_ilp.rs

problemreductions/rules/
pathconstrainednetworkflow_ilp.rs
