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<i32>,
21    num_vertices: usize,
22}
23
24impl ReductionResult for ReductionFeasibleRegisterAssignmentToILP {
25    type Source = FeasibleRegisterAssignment;
26    type Target = ILP<i32>;
27
28    fn target_problem(&self) -> &ILP<i32> {
29        &self.target
30    }
31
32    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
33        target_solution[..self.num_vertices].to_vec()
34    }
35}
36
37#[reduction(overhead = {
38    num_vars = "2 * num_vertices + num_vertices * (num_vertices - 1) / 2",
39    num_constraints = "3 * num_vertices * (num_vertices - 1) / 2 + 3 * num_vertices + 2 * num_arcs + 2 * num_same_register_pairs",
40})]
41impl ReduceTo<ILP<i32>> for FeasibleRegisterAssignment {
42    type Result = ReductionFeasibleRegisterAssignmentToILP;
43
44    fn reduce_to(&self) -> Self::Result {
45        let n = self.num_vertices();
46        let pair_list: Vec<(usize, usize)> = (0..n)
47            .flat_map(|u| ((u + 1)..n).map(move |v| (u, v)))
48            .collect();
49        let same_register_pairs: Vec<(usize, usize, usize)> = pair_list
50            .iter()
51            .copied()
52            .enumerate()
53            .filter(|(_, (u, v))| self.assignment()[*u] == self.assignment()[*v])
54            .map(|(pair_idx, (u, v))| (u, v, pair_idx))
55            .collect();
56
57        let num_pair_vars = pair_list.len();
58        let num_vars = 2 * n + num_pair_vars;
59        let big_m = n as f64;
60
61        let time_idx = |vertex: usize| -> usize { vertex };
62        let latest_idx = |vertex: usize| -> usize { n + vertex };
63        let order_idx = |pair_idx: usize| -> usize { 2 * n + pair_idx };
64
65        let mut constraints = Vec::with_capacity(
66            3 * num_pair_vars + 3 * n + 2 * self.num_arcs() + 2 * same_register_pairs.len(),
67        );
68
69        for vertex in 0..n {
70            constraints.push(LinearConstraint::le(
71                vec![(time_idx(vertex), 1.0)],
72                (n.saturating_sub(1)) as f64,
73            ));
74            constraints.push(LinearConstraint::le(
75                vec![(latest_idx(vertex), 1.0)],
76                (n.saturating_sub(1)) as f64,
77            ));
78            constraints.push(LinearConstraint::ge(
79                vec![(latest_idx(vertex), 1.0), (time_idx(vertex), -1.0)],
80                0.0,
81            ));
82        }
83
84        for &(dependent, dependency) in self.arcs() {
85            constraints.push(LinearConstraint::ge(
86                vec![(time_idx(dependent), 1.0), (time_idx(dependency), -1.0)],
87                1.0,
88            ));
89            constraints.push(LinearConstraint::ge(
90                vec![(latest_idx(dependency), 1.0), (time_idx(dependent), -1.0)],
91                0.0,
92            ));
93        }
94
95        for (pair_idx, &(u, v)) in pair_list.iter().enumerate() {
96            let order_var = order_idx(pair_idx);
97            constraints.push(LinearConstraint::le(vec![(order_var, 1.0)], 1.0));
98            constraints.push(LinearConstraint::ge(
99                vec![(time_idx(v), 1.0), (time_idx(u), -1.0), (order_var, -big_m)],
100                1.0 - big_m,
101            ));
102            constraints.push(LinearConstraint::ge(
103                vec![(time_idx(u), 1.0), (time_idx(v), -1.0), (order_var, big_m)],
104                1.0,
105            ));
106        }
107
108        for &(u, v, pair_idx) in &same_register_pairs {
109            let order_var = order_idx(pair_idx);
110            constraints.push(LinearConstraint::ge(
111                vec![
112                    (time_idx(v), 1.0),
113                    (latest_idx(u), -1.0),
114                    (order_var, -big_m),
115                ],
116                -big_m,
117            ));
118            constraints.push(LinearConstraint::ge(
119                vec![
120                    (time_idx(u), 1.0),
121                    (latest_idx(v), -1.0),
122                    (order_var, big_m),
123                ],
124                0.0,
125            ));
126        }
127
128        ReductionFeasibleRegisterAssignmentToILP {
129            target: ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize),
130            num_vertices: n,
131        }
132    }
133}
134
135#[cfg(feature = "example-db")]
136pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
137    vec![crate::example_db::specs::RuleExampleSpec {
138        id: "feasibleregisterassignment_to_ilp",
139        build: || {
140            let source = FeasibleRegisterAssignment::new(
141                4,
142                vec![(0, 1), (0, 2), (1, 3)],
143                2,
144                vec![0, 1, 0, 0],
145            );
146            crate::example_db::specs::rule_example_via_ilp::<_, i32>(source)
147        },
148    }]
149}
150
151#[cfg(test)]
152#[path = "../unit_tests/rules/feasibleregisterassignment_ilp.rs"]
153mod tests;
problemreductions/rules/feasibleregisterassignment_ilp.rs

problemreductions/rules/
feasibleregisterassignment_ilp.rs
