problemreductions/rules/
feasibleregisterassignment_ilp.rs

1//! Reduction from Feasible Register Assignment to ILP (Integer Linear Programming).
2//!
3//! The formulation uses non-negative integer variables:
4//! - `t_v`: evaluation position of vertex `v`
5//! - `L_v`: latest position among `v` and all dependents of `v`
6//! - `z_uv`: binary order selector for each unordered pair `{u, v}`
7//!
8//! The pair-order constraints force the `t_v` values to form a permutation of
9//! `{0, ..., n-1}`. For same-register pairs, the extra constraints enforce
10//! interval non-overlap: if `u` is before `v`, then `v` must be scheduled no
11//! earlier than the latest dependent of `u`.
12
13use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
14use crate::models::misc::FeasibleRegisterAssignment;
15use crate::reduction;
16use crate::rules::traits::{ReduceTo, ReductionResult};
17
18#[derive(Debug, Clone)]
19pub struct ReductionFeasibleRegisterAssignmentToILP {
20    target: ILP<i64>,
21    num_vertices: usize,
22}
23
24impl ReductionResult for ReductionFeasibleRegisterAssignmentToILP {
25    type Source = FeasibleRegisterAssignment;
26    type Target = ILP<i64>;
27
28    fn target_problem(&self) -> &ILP<i64> {
29        &self.target
30    }
31
32    fn extract_solution(
33        &self,
34        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
35    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
36        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
37
38        crate::rules::ilp_helpers::decode_usize_values(&target_solution[..self.num_vertices])
39    }
40}
41
42#[reduction(
43    transform = exact {
44        num_vars = "2 * num_vertices + num_vertices * (num_vertices - 1) / 2",
45        num_constraints = "3 * num_vertices * (num_vertices - 1) / 2 + 3 * num_vertices + 2 * num_arcs + 2 * num_same_register_pairs",
46    },
47    unavailable = {
48        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
49    }
50)]
51impl ReduceTo<ILP<i64>> for FeasibleRegisterAssignment {
52    type Result = ReductionFeasibleRegisterAssignmentToILP;
53
54    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
55        let n = self.num_vertices();
56        let pair_list: Vec<(usize, usize)> = (0..n)
57            .flat_map(|u| ((u + 1)..n).map(move |v| (u, v)))
58            .collect();
59        let same_register_pairs: Vec<(usize, usize, usize)> = pair_list
60            .iter()
61            .copied()
62            .enumerate()
63            .filter(|(_, (u, v))| self.assignment()[*u] == self.assignment()[*v])
64            .map(|(pair_idx, (u, v))| (u, v, pair_idx))
65            .collect();
66
67        let num_pair_vars = pair_list.len();
68        let num_vars = 2 * n + num_pair_vars;
69        let big_m = Self::exact_i64(n, "encoding the schedule order")?;
70        let last_position =
71            Self::exact_i64(n.saturating_sub(1), "encoding the final schedule position")?;
72
73        let time_idx = |vertex: usize| -> usize { vertex };
74        let latest_idx = |vertex: usize| -> usize { n + vertex };
75        let order_idx = |pair_idx: usize| -> usize { 2 * n + pair_idx };
76
77        let mut constraints = Vec::with_capacity(
78            3 * num_pair_vars + 3 * n + 2 * self.num_arcs() + 2 * same_register_pairs.len(),
79        );
80
81        for vertex in 0..n {
82            constraints.push(LinearConstraint::le(
83                vec![(time_idx(vertex), 1)],
84                last_position,
85            ));
86            constraints.push(LinearConstraint::le(
87                vec![(latest_idx(vertex), 1)],
88                last_position,
89            ));
90            constraints.push(LinearConstraint::ge(
91                vec![(latest_idx(vertex), 1), (time_idx(vertex), -1)],
92                0,
93            ));
94        }
95
96        for &(dependent, dependency) in self.arcs() {
97            constraints.push(LinearConstraint::ge(
98                vec![(time_idx(dependent), 1), (time_idx(dependency), -1)],
99                1,
100            ));
101            constraints.push(LinearConstraint::ge(
102                vec![(latest_idx(dependency), 1), (time_idx(dependent), -1)],
103                0,
104            ));
105        }
106
107        for (pair_idx, &(u, v)) in pair_list.iter().enumerate() {
108            let order_var = order_idx(pair_idx);
109            constraints.push(LinearConstraint::le(vec![(order_var, 1)], 1));
110            constraints.push(LinearConstraint::ge(
111                vec![(time_idx(v), 1), (time_idx(u), -1), (order_var, -big_m)],
112                1 - big_m,
113            ));
114            constraints.push(LinearConstraint::ge(
115                vec![(time_idx(u), 1), (time_idx(v), -1), (order_var, big_m)],
116                1,
117            ));
118        }
119
120        for &(u, v, pair_idx) in &same_register_pairs {
121            let order_var = order_idx(pair_idx);
122            constraints.push(LinearConstraint::ge(
123                vec![(time_idx(v), 1), (latest_idx(u), -1), (order_var, -big_m)],
124                -big_m,
125            ));
126            constraints.push(LinearConstraint::ge(
127                vec![(time_idx(u), 1), (latest_idx(v), -1), (order_var, big_m)],
128                0,
129            ));
130        }
131
132        Ok(ReductionFeasibleRegisterAssignmentToILP {
133            target: ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
134                .map_err(Self::target_construction)?,
135            num_vertices: n,
136        })
137    }
138}
139
140#[cfg(feature = "example-db")]
141pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
142    vec![crate::example_db::specs::RuleExampleSpec {
143        id: "feasibleregisterassignment_to_ilp",
144        build: || {
145            let source = FeasibleRegisterAssignment::new(
146                4,
147                vec![(0, 1), (0, 2), (1, 3)],
148                2,
149                vec![0, 1, 0, 0],
150            );
151            crate::example_db::specs::rule_example_via_ilp::<_, i64>(source)
152        },
153    }]
154}
155
156#[cfg(test)]
157#[path = "../unit_tests/rules/feasibleregisterassignment_ilp.rs"]
158mod tests;
problemreductions/rules/feasibleregisterassignment_ilp.rs

problemreductions/rules/
feasibleregisterassignment_ilp.rs
