problemreductions/rules/
partitionintopathsoflength2_ilp.rs

1//! Reduction from PartitionIntoPathsOfLength2 to ILP (Integer Linear Programming).
2//!
3//! Each triple must contain at least 2 edges. We introduce product variables y_{e,g} = x_{u,g} * x_{v,g}
4//! for each edge (u,v) and group g, linearized with McCormick constraints:
5//!
6//! Variables:
7//! - x_{v,g}: binary, vertex v in group g (index: v * q + g)
8//! - y_{e,g}: binary product for edge e=(u,v) and group g (index: n*q + e * q + g)
9//!
10//! Constraints:
11//! - Σ_g x_{v,g} = 1 for each vertex v (assignment)
12//! - Σ_v x_{v,g} = 3 for each group g (size constraint)
13//! - For each edge e=(u,v) and group g (McCormick for y_{e,g} = x_{u,g} * x_{v,g}):
14//!   y_{e,g} ≤ x_{u,g}, y_{e,g} ≤ x_{v,g}, y_{e,g} ≥ x_{u,g} + x_{v,g} - 1
15//! - For each group g: Σ_e y_{e,g} ≥ 2 (at least 2 edges in group)
16//!
17//! Objective: Minimize 0 (feasibility)
18
19use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
20use crate::models::graph::PartitionIntoPathsOfLength2;
21use crate::reduction;
22use crate::rules::ilp_helpers::mccormick_product;
23use crate::rules::traits::{ReduceTo, ReductionResult};
24use crate::topology::{Graph, SimpleGraph};
25
26/// Result of reducing PartitionIntoPathsOfLength2 to ILP.
27///
28/// Variable layout:
29/// - x_{v,g} at index v * q + g  (v ∈ 0..n, g ∈ 0..q)
30/// - y_{e,g} at index n * q + e * q + g  (e ∈ 0..num_edges, g ∈ 0..q)
31#[derive(Debug, Clone)]
32pub struct ReductionPIPL2ToILP {
33    target: ILP<bool>,
34    num_vertices: usize,
35    num_groups: usize,
36}
37
38impl ReductionResult for ReductionPIPL2ToILP {
39    type Source = PartitionIntoPathsOfLength2<SimpleGraph>;
40    type Target = ILP<bool>;
41
42    fn target_problem(&self) -> &ILP<bool> {
43        &self.target
44    }
45
46    /// Extract solution: for each vertex v, find the unique group g where x_{v,g} = 1.
47    fn extract_solution(
48        &self,
49        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
50    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
51        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
52
53        crate::rules::ilp_helpers::one_hot_decode_rows(
54            target_solution,
55            self.num_vertices,
56            self.num_groups,
57            0,
58        )
59    }
60}
61
62#[reduction(
63    transform = upper_bound {
64        num_vars = "num_vertices^2 + num_edges * num_vertices",
65        num_constraints = "num_vertices^2 + num_edges * num_vertices + num_vertices",
66    },
67    unavailable = {
68        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
69    }
70)]
71impl ReduceTo<ILP<bool>> for PartitionIntoPathsOfLength2<SimpleGraph> {
72    type Result = ReductionPIPL2ToILP;
73
74    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
75        let num_vertices = self.num_vertices();
76        let q = self.num_groups();
77        let edges: Vec<(usize, usize)> = self.graph().edges();
78        let num_edges = edges.len();
79        let num_vars = num_vertices * q + num_edges * q;
80
81        let mut constraints = Vec::new();
82
83        // Assignment constraints: for each vertex v, Σ_g x_{v,g} = 1
84        for v in 0..num_vertices {
85            let terms: Vec<(usize, i64)> = (0..q).map(|g| (v * q + g, 1)).collect();
86            constraints.push(LinearConstraint::eq(terms, 1));
87        }
88
89        // Group size constraints: for each group g, Σ_v x_{v,g} = 3
90        for g in 0..q {
91            let terms: Vec<(usize, i64)> = (0..num_vertices).map(|v| (v * q + g, 1)).collect();
92            constraints.push(LinearConstraint::eq(terms, 3));
93        }
94
95        // McCormick linearization: y_{e,g} = x_{u,g} * x_{v,g} for each edge e=(u,v) and group g
96        // y_{e,g} is at index num_vertices * q + e * q + g
97        for (e, &(u, v)) in edges.iter().enumerate() {
98            for g in 0..q {
99                let y = num_vertices * q + e * q + g;
100                let xu = u * q + g;
101                let xv = v * q + g;
102
103                constraints.extend(mccormick_product(y, xu, xv));
104            }
105        }
106
107        // At-least-2-edges constraint: for each group g, Σ_e y_{e,g} ≥ 2
108        for g in 0..q {
109            let terms: Vec<(usize, i64)> = (0..num_edges)
110                .map(|e| (num_vertices * q + e * q + g, 1))
111                .collect();
112            constraints.push(LinearConstraint::ge(terms, 2));
113        }
114
115        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
116            .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?;
117
118        Ok(ReductionPIPL2ToILP {
119            target,
120            num_vertices,
121            num_groups: q,
122        })
123    }
124}
125
126#[cfg(feature = "example-db")]
127pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
128    vec![crate::example_db::specs::RuleExampleSpec {
129        id: "partitionintopathsoflength2_to_ilp",
130        build: || {
131            // Two P3 paths: 0-1-2 and 3-4-5
132            let source = PartitionIntoPathsOfLength2::new(SimpleGraph::new(
133                6,
134                vec![(0, 1), (1, 2), (3, 4), (4, 5)],
135            ));
136            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
137        },
138    }]
139}
140
141#[cfg(test)]
142#[path = "../unit_tests/rules/partitionintopathsoflength2_ilp.rs"]
143mod tests;
problemreductions/rules/partitionintopathsoflength2_ilp.rs

problemreductions/rules/
partitionintopathsoflength2_ilp.rs
