problemreductions/rules/
feasibleregisterassignment_ilp.rs

1//! Bounded ranks with order selectors only for vertices sharing a register.
2
3use crate::models::algebraic::{Bounded, IntegerVariable, LinearConstraint, ObjectiveSense, ILP};
4use crate::models::misc::FeasibleRegisterAssignment;
5use crate::reduction;
6use crate::rules::ilp_helpers::{bounded_order_comparison, ranks_to_positions};
7use crate::rules::traits::{ReduceTo, ReductionResult};
8
9#[derive(Debug, Clone)]
10pub struct ReductionFeasibleRegisterAssignmentToILP {
11    target: ILP<i64, i64, Bounded>,
12    num_vertices: usize,
13}
14
15impl ReductionResult for ReductionFeasibleRegisterAssignmentToILP {
16    type Source = FeasibleRegisterAssignment;
17    type Target = ILP<i64, i64, Bounded>;
18
19    fn target_problem(&self) -> &ILP<i64, i64, Bounded> {
20        &self.target
21    }
22
23    fn extract_solution(
24        &self,
25        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
26    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
27        crate::rules::traits::validate_target_witness(
28            self.target_problem(),
29            target_solution,
30            |value| value.value.is_some(),
31            "target ILP assignment is infeasible",
32        )?;
33
34        Ok(ranks_to_positions(&target_solution[..self.num_vertices]))
35    }
36}
37
38#[crate::aggregate_reduction(ilp_feasibility)]
39impl crate::rules::AggregateReductionResult for ReductionFeasibleRegisterAssignmentToILP {}
40
41#[reduction(transform = {
42    exact {
43        num_vars = "num_vertices + num_same_register_pairs",
44    },
45    upper_bound {
46        num_constraints = "num_vertices * num_arcs + 2 * num_same_register_pairs",
47        num_nonzeros = "3 * num_vertices * num_arcs + 6 * num_same_register_pairs",
48        max_constraint_magnitude_bits = "num_vertices + 1",
49    },
50})]
51impl ReduceTo<ILP<i64, i64, Bounded>> 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 pairs: Vec<_> = (0..n)
57            .flat_map(|u| ((u + 1)..n).map(move |v| (u, v)))
58            .filter(|&(u, v)| self.assignment()[u] == self.assignment()[v])
59            .collect();
60        let num_vars = n.checked_add(pairs.len()).ok_or_else(|| {
61            crate::rules::ReductionError::integer_overflow::<Self, ILP<i64, i64, Bounded>>(
62                "counting register assignment variables",
63            )
64        })?;
65        let big_m = Self::exact_i64(n, "encoding the schedule order")?;
66        let last_position = big_m.saturating_sub(1).max(0);
67        let mut variables = vec![
68            IntegerVariable::new(Some(0), Some(last_position))
69                .map_err(Self::target_construction)?;
70            n
71        ];
72        variables.resize(num_vars, IntegerVariable::binary());
73        let mut constraints = Vec::new();
74        let mut dependents = vec![Vec::new(); n];
75        for &(dependent, dependency) in self.arcs() {
76            constraints.push(LinearConstraint::ge(
77                vec![(dependent, 1), (dependency, -1)],
78                1,
79            ));
80            dependents[dependency].push(dependent);
81        }
82        for (index, &(u, v)) in pairs.iter().enumerate() {
83            let selector = n + index;
84            constraints.extend(bounded_order_comparison(u, v, selector, big_m));
85            // An overwriter may consume the old value in that same operation.
86            // Every other consumer must finish strictly before the overwrite.
87            for &w in &dependents[u] {
88                if w != v {
89                    constraints.push(LinearConstraint::ge(
90                        vec![(v, 1), (w, -1), (selector, -big_m)],
91                        1 - big_m,
92                    ));
93                }
94            }
95            for &w in &dependents[v] {
96                if w != u {
97                    constraints.push(LinearConstraint::ge(
98                        vec![(u, 1), (w, -1), (selector, big_m)],
99                        1,
100                    ));
101                }
102            }
103        }
104        let target = ILP::with_variables(variables, constraints, vec![], ObjectiveSense::Minimize)
105            .map_err(Self::target_construction)?;
106        crate::rules::ilp_helpers::validate_bounded_constraint_arithmetic::<Self>(&target)?;
107
108        Ok(ReductionFeasibleRegisterAssignmentToILP {
109            target,
110            num_vertices: n,
111        })
112    }
113}
114
115#[cfg(feature = "example-db")]
116pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
117    vec![crate::example_db::specs::RuleExampleSpec {
118        id: "feasibleregisterassignment_to_ilp",
119        build: || {
120            let source = FeasibleRegisterAssignment::new(
121                4,
122                vec![(0, 1), (0, 2), (1, 3)],
123                2,
124                vec![0, 1, 0, 0],
125            );
126            crate::example_db::specs::rule_example_via_bounded_ilp::<_>(source)
127        },
128    }]
129}
130
131#[cfg(test)]
132#[path = "../unit_tests/rules/feasibleregisterassignment_ilp.rs"]
133mod tests;
problemreductions/rules/feasibleregisterassignment_ilp.rs

problemreductions/rules/
feasibleregisterassignment_ilp.rs
