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::{Bounded, IntegerVariable, 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, i64, Bounded>,
15}
16
17impl ReductionResult for ReductionPCNFToILP {
18    type Source = PathConstrainedNetworkFlow;
19    type Target = ILP<i64, i64, Bounded>;
20
21    fn target_problem(&self) -> &ILP<i64, i64, Bounded> {
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_witness(
30            self.target_problem(),
31            target_solution,
32            |value| value.value.is_some(),
33            "target ILP assignment is infeasible",
34        )?;
35
36        crate::rules::ilp_helpers::decode_usize_values(target_solution)
37    }
38}
39
40#[crate::aggregate_reduction(ilp_feasibility)]
41impl crate::rules::AggregateReductionResult for ReductionPCNFToILP {}
42
43#[reduction(
44    transform = upper_bound {
45        max_constraint_magnitude_bits = "max_capacity * (num_paths + 1) + 2",
46        num_vars = "num_paths",
47        num_constraints = "num_arcs + 1",
48        num_nonzeros = "num_paths * (num_arcs + 1)",
49    },
50)]
51impl ReduceTo<ILP<i64, i64, Bounded>> for PathConstrainedNetworkFlow {
52    type Result = ReductionPCNFToILP;
53
54    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
55        let num_paths = self.num_paths();
56        let num_arcs = self.num_arcs();
57        let mut constraints = Vec::new();
58
59        // Arc capacity: sum_{i : a in P_i} f_i <= c_a for all a
60        for arc_idx in 0..num_arcs {
61            let terms: Vec<(usize, i64)> = self
62                .paths()
63                .iter()
64                .enumerate()
65                .filter(|(_, path)| path.contains(&arc_idx))
66                .map(|(path_idx, _)| (path_idx, 1))
67                .collect();
68            if !terms.is_empty() {
69                constraints.push(LinearConstraint::le(terms, self.capacities()[arc_idx]));
70            }
71        }
72
73        // Total flow requirement: sum_i f_i >= R
74        let total_terms: Vec<(usize, i64)> = (0..num_paths).map(|i| (i, 1)).collect();
75        constraints.push(LinearConstraint::ge(
76            total_terms,
77            crate::rules::ilp_helpers::bounded_flow_requirement(
78                self.requirement(),
79                self.paths().iter().map(|path| self.path_bottleneck(path)),
80            ),
81        ));
82
83        let variables = self
84            .paths()
85            .iter()
86            .map(|path| IntegerVariable::new(Some(0), Some(self.path_bottleneck(path))))
87            .collect::<Result<Vec<_>, _>>()
88            .map_err(Self::target_construction)?;
89
90        Ok(ReductionPCNFToILP {
91            target: ILP::with_variables(variables, constraints, vec![], ObjectiveSense::Minimize)
92                .map_err(Self::target_construction)?,
93        })
94    }
95}
96
97#[cfg(feature = "example-db")]
98pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
99    use crate::topology::DirectedGraph;
100
101    vec![crate::example_db::specs::RuleExampleSpec {
102        id: "pathconstrainednetworkflow_to_ilp",
103        build: || {
104            // Simple graph: s=0, t=2, arcs 0->1->2 and 0->2
105            // Two paths: [0,1] (0->1->2) and [2] (0->2)
106            let source = PathConstrainedNetworkFlow::new(
107                DirectedGraph::new(3, vec![(0, 1), (1, 2), (0, 2)]),
108                vec![1, 1, 1],
109                0,
110                2,
111                vec![vec![0, 1], vec![2]],
112                2,
113            );
114            crate::example_db::specs::rule_example_via_bounded_ilp::<_>(source)
115        },
116    }]
117}
118
119#[cfg(test)]
120#[path = "../unit_tests/rules/pathconstrainednetworkflow_ilp.rs"]
121mod tests;
problemreductions/rules/pathconstrainednetworkflow_ilp.rs

problemreductions/rules/
pathconstrainednetworkflow_ilp.rs
