problemreductions/rules/
minimumweightandorgraph_ilp.rs

1//! Gate selection and source reachability, including shared or cyclic subgraphs.
2use crate::models::algebraic::{Bounded, IntegerVariable, LinearConstraint, ObjectiveSense, ILP};
3use crate::models::misc::MinimumWeightAndOrGraph;
4use crate::rules::traits::{ReduceTo, ReductionResult};
5
6#[derive(Debug, Clone)]
7pub struct ReductionMinimumWeightAndOrGraphToILP {
8    target: ILP<i64, i64, Bounded>,
9    num_arcs: usize,
10}
11impl ReductionResult for ReductionMinimumWeightAndOrGraphToILP {
12    type Source = MinimumWeightAndOrGraph;
13    type Target = ILP<i64, i64, Bounded>;
14    fn target_problem(&self) -> &Self::Target {
15        &self.target
16    }
17    fn extract_solution(&self, solution: &Vec<i64>) -> crate::rules::ExtractionResult<Vec<bool>> {
18        crate::rules::traits::validate_target_witness(
19            &self.target,
20            solution,
21            |v| v.value.is_some(),
22            "target ILP assignment is infeasible",
23        )?;
24        Ok(solution[..self.num_arcs].iter().map(|&v| v == 1).collect())
25    }
26}
27#[crate::reduction(transform = {
28    exact { num_vars = "num_vertices + 2 * num_arcs", },
29    upper_bound {
30        num_constraints = "2 * num_vertices + 4 * num_arcs",
31        num_nonzeros = "2 * num_vertices + 10 * num_arcs",
32        max_constraint_magnitude_bits = "num_vertices",
33    },
34})]
35impl ReduceTo<ILP<i64, i64, Bounded>> for MinimumWeightAndOrGraph {
36    type Result = ReductionMinimumWeightAndOrGraphToILP;
37    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
38        let n = self.num_vertices();
39        let m = self.num_arcs();
40        let count = m
41            .checked_mul(2)
42            .and_then(|v| v.checked_add(n))
43            .ok_or_else(|| {
44                crate::rules::ReductionError::integer_overflow::<Self, ILP<i64, i64, Bounded>>(
45                    "counting AND/OR flow variables",
46                )
47            })?;
48        let capacity = Self::exact_i64(n - 1, "bounding reachability flow")?;
49        let flow = m + n;
50        let mut variables = Vec::with_capacity(count);
51        variables.resize(flow, IntegerVariable::binary());
52        let mut outgoing = vec![Vec::new(); n];
53        let mut balance: Vec<_> = (0..n).map(|v| vec![(m + v, -1)]).collect();
54        let mut rows = vec![LinearConstraint::eq(vec![(m + self.source(), 1)], 1)];
55        for (e, &(u, v)) in self.arcs().iter().enumerate() {
56            let gate = self.gate_types()[u].is_some();
57            variables.push(
58                IntegerVariable::new(Some(0), Some(if gate { capacity } else { 0 }))
59                    .map_err(Self::target_construction)?,
60            );
61            outgoing[u].push((e, 1));
62            rows.push(LinearConstraint::le(vec![(e, 1), (m + u, -1)], 0));
63            if gate {
64                rows.push(LinearConstraint::le(vec![(e, 1), (m + v, -1)], 0));
65                rows.push(LinearConstraint::le(vec![(flow + e, 1), (e, -capacity)], 0));
66                balance[v].push((flow + e, 1));
67                balance[u].push((flow + e, -1));
68            }
69        }
70        for (u, terms) in outgoing.into_iter().enumerate() {
71            match self.gate_types()[u] {
72                Some(true) => rows.extend(
73                    terms
74                        .into_iter()
75                        .map(|(e, _)| LinearConstraint::le(vec![(m + u, 1), (e, -1)], 0)),
76                ),
77                Some(false) => {
78                    let mut terms = terms;
79                    terms.push((m + u, -1));
80                    rows.push(LinearConstraint::ge(terms, 0));
81                }
82                None => {}
83            }
84        }
85        for (v, terms) in balance.into_iter().enumerate() {
86            if v != self.source() {
87                rows.push(LinearConstraint::ge(terms, 0));
88            }
89        }
90        let objective = self.arc_weights().iter().copied().enumerate().collect();
91        let target = ILP::with_variables(variables, rows, objective, ObjectiveSense::Minimize)
92            .map_err(Self::target_construction)?;
93        crate::rules::ilp_helpers::validate_bounded_constraint_arithmetic::<Self>(&target)?;
94        Ok(Self::Result {
95            target,
96            num_arcs: m,
97        })
98    }
99}
100#[cfg(feature = "example-db")]
101pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
102    vec![crate::example_db::specs::RuleExampleSpec {
103        id: "minimumweightandorgraph_to_ilp",
104        build: || {
105            crate::example_db::specs::rule_example_via_bounded_ilp(MinimumWeightAndOrGraph::new(
106                3,
107                vec![(0, 1), (0, 2), (1, 2)],
108                0,
109                vec![Some(true), Some(false), None],
110                vec![1, 2, -4],
111            ))
112        },
113    }]
114}
115#[cfg(test)]
116#[path = "../unit_tests/rules/minimumweightandorgraph_ilp.rs"]
117mod tests;
problemreductions/rules/minimumweightandorgraph_ilp.rs

problemreductions/rules/
minimumweightandorgraph_ilp.rs
