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::traits::{ReduceTo, ReductionResult};
23use crate::topology::{Graph, SimpleGraph};
24
25/// Result of reducing PartitionIntoPathsOfLength2 to ILP.
26///
27/// Variable layout:
28/// - x_{v,g} at index v * q + g  (v ∈ 0..n, g ∈ 0..q)
29/// - y_{e,g} at index n * q + e * q + g  (e ∈ 0..num_edges, g ∈ 0..q)
30#[derive(Debug, Clone)]
31pub struct ReductionPIPL2ToILP {
32    target: ILP<bool>,
33    num_vertices: usize,
34    num_groups: usize,
35}
36
37impl ReductionResult for ReductionPIPL2ToILP {
38    type Source = PartitionIntoPathsOfLength2<SimpleGraph>;
39    type Target = ILP<bool>;
40
41    fn target_problem(&self) -> &ILP<bool> {
42        &self.target
43    }
44
45    /// Extract solution: for each vertex v, find the unique group g where x_{v,g} = 1.
46    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
47        let num_groups = self.num_groups;
48        (0..self.num_vertices)
49            .map(|v| {
50                (0..num_groups)
51                    .find(|&g| {
52                        let idx = v * num_groups + g;
53                        idx < target_solution.len() && target_solution[idx] == 1
54                    })
55                    .unwrap_or(0)
56            })
57            .collect()
58    }
59}
60
61#[reduction(
62    overhead = {
63        num_vars = "num_vertices^2 + num_edges * num_vertices",
64        num_constraints = "num_vertices^2 + num_edges * num_vertices + num_vertices",
65    }
66)]
67impl ReduceTo<ILP<bool>> for PartitionIntoPathsOfLength2<SimpleGraph> {
68    type Result = ReductionPIPL2ToILP;
69
70    fn reduce_to(&self) -> Self::Result {
71        let num_vertices = self.num_vertices();
72        let q = self.num_groups();
73        let edges: Vec<(usize, usize)> = self.graph().edges();
74        let num_edges = edges.len();
75        let num_vars = num_vertices * q + num_edges * q;
76
77        let mut constraints = Vec::new();
78
79        // Assignment constraints: for each vertex v, Σ_g x_{v,g} = 1
80        for v in 0..num_vertices {
81            let terms: Vec<(usize, f64)> = (0..q).map(|g| (v * q + g, 1.0)).collect();
82            constraints.push(LinearConstraint::eq(terms, 1.0));
83        }
84
85        // Group size constraints: for each group g, Σ_v x_{v,g} = 3
86        for g in 0..q {
87            let terms: Vec<(usize, f64)> = (0..num_vertices).map(|v| (v * q + g, 1.0)).collect();
88            constraints.push(LinearConstraint::eq(terms, 3.0));
89        }
90
91        // McCormick linearization: y_{e,g} = x_{u,g} * x_{v,g} for each edge e=(u,v) and group g
92        // y_{e,g} is at index num_vertices * q + e * q + g
93        for (e, &(u, v)) in edges.iter().enumerate() {
94            for g in 0..q {
95                let y = num_vertices * q + e * q + g;
96                let xu = u * q + g;
97                let xv = v * q + g;
98
99                // y ≤ x_{u,g}
100                constraints.push(LinearConstraint::le(vec![(y, 1.0), (xu, -1.0)], 0.0));
101                // y ≤ x_{v,g}
102                constraints.push(LinearConstraint::le(vec![(y, 1.0), (xv, -1.0)], 0.0));
103                // y ≥ x_{u,g} + x_{v,g} - 1  →  -y + x_{u,g} + x_{v,g} ≤ 1
104                constraints.push(LinearConstraint::le(
105                    vec![(y, -1.0), (xu, 1.0), (xv, 1.0)],
106                    1.0,
107                ));
108            }
109        }
110
111        // At-least-2-edges constraint: for each group g, Σ_e y_{e,g} ≥ 2
112        for g in 0..q {
113            let terms: Vec<(usize, f64)> = (0..num_edges)
114                .map(|e| (num_vertices * q + e * q + g, 1.0))
115                .collect();
116            constraints.push(LinearConstraint::ge(terms, 2.0));
117        }
118
119        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize);
120
121        ReductionPIPL2ToILP {
122            target,
123            num_vertices,
124            num_groups: q,
125        }
126    }
127}
128
129#[cfg(feature = "example-db")]
130pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
131    vec![crate::example_db::specs::RuleExampleSpec {
132        id: "partitionintopathsoflength2_to_ilp",
133        build: || {
134            // Two P3 paths: 0-1-2 and 3-4-5
135            let source = PartitionIntoPathsOfLength2::new(SimpleGraph::new(
136                6,
137                vec![(0, 1), (1, 2), (3, 4), (4, 5)],
138            ));
139            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
140        },
141    }]
142}
143
144#[cfg(test)]
145#[path = "../unit_tests/rules/partitionintopathsoflength2_ilp.rs"]
146mod tests;
problemreductions/rules/partitionintopathsoflength2_ilp.rs

problemreductions/rules/
partitionintopathsoflength2_ilp.rs
