problemreductions/rules/
multiplechoicebranching_ilp.rs

1//! Reduction from MultipleChoiceBranching with integer weights to integer ILP.
2
3use crate::models::algebraic::{Bounded, IntegerVariable, LinearConstraint, ObjectiveSense, ILP};
4use crate::models::graph::MultipleChoiceBranching;
5use crate::reduction;
6use crate::rules::traits::{ReduceTo, ReductionResult};
7
8#[derive(Debug, Clone)]
9pub struct ReductionMultipleChoiceBranchingToILP {
10    target: ILP<i64, i64, Bounded>,
11    num_arcs: usize,
12}
13
14impl ReductionResult for ReductionMultipleChoiceBranchingToILP {
15    type Source = MultipleChoiceBranching<i64>;
16    type Target = ILP<i64, i64, Bounded>;
17
18    fn target_problem(&self) -> &Self::Target {
19        &self.target
20    }
21
22    fn extract_solution(
23        &self,
24        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
25    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
26        crate::rules::traits::validate_target_witness(
27            self.target_problem(),
28            target_solution,
29            |value| value.value.is_some(),
30            "target ILP assignment is infeasible",
31        )?;
32        Ok(target_solution[..self.num_arcs]
33            .iter()
34            .map(|&selected| selected == 1)
35            .collect())
36    }
37}
38
39#[crate::aggregate_reduction(ilp_feasibility)]
40impl crate::rules::AggregateReductionResult for ReductionMultipleChoiceBranchingToILP {}
41
42#[reduction(transform = {
43    exact {
44        num_vars = "num_arcs + num_vertices",
45        num_constraints = "2 * num_arcs + 2 * num_vertices + num_partition_groups + 1",
46    },
47    upper_bound {
48        max_constraint_magnitude_bits = "max_weight_bits + num_vertices",
49        num_nonzeros = "(num_arcs + num_vertices) * (2 * num_arcs + 2 * num_vertices + num_partition_groups + 1)",
50    },
51})]
52impl ReduceTo<ILP<i64, i64, Bounded>> for MultipleChoiceBranching<i64> {
53    type Result = ReductionMultipleChoiceBranchingToILP;
54
55    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
56        let num_arcs = self.num_arcs();
57        let num_vertices = self.num_vertices();
58        let order = |vertex: usize| num_arcs + vertex;
59        let mut constraints = Vec::new();
60
61        for arc in 0..num_arcs {
62            constraints.push(LinearConstraint::le(vec![(arc, 1)], 1));
63        }
64        if num_vertices > 0 {
65            let big_m = <Self as ReduceTo<ILP<i64, i64, Bounded>>>::exact_i64(
66                num_vertices,
67                "encoding topological-order constraints",
68            )?;
69            for vertex in 0..num_vertices {
70                constraints.push(LinearConstraint::le(vec![(order(vertex), 1)], big_m - 1));
71            }
72            for (arc, &(source, target)) in self.graph().arcs().iter().enumerate() {
73                constraints.push(LinearConstraint::le(
74                    vec![(order(source), 1), (order(target), -1), (arc, big_m)],
75                    big_m - 1,
76                ));
77            }
78        }
79        for group in self.partition() {
80            constraints.push(LinearConstraint::le(
81                group.iter().map(|&arc| (arc, 1)).collect(),
82                1,
83            ));
84        }
85        for vertex in 0..num_vertices {
86            constraints.push(LinearConstraint::le(
87                self.graph()
88                    .arcs()
89                    .iter()
90                    .enumerate()
91                    .filter_map(|(arc, &(_, target))| (target == vertex).then_some((arc, 1)))
92                    .collect(),
93                1,
94            ));
95        }
96        constraints.push(LinearConstraint::ge(
97            self.weights()
98                .iter()
99                .enumerate()
100                .map(|(arc, &weight)| (arc, weight))
101                .collect(),
102            *self.threshold(),
103        ));
104
105        let mut variables = vec![IntegerVariable::binary(); num_arcs + num_vertices];
106        variables[num_arcs..].fill(
107            IntegerVariable::new(
108                Some(0),
109                Some(Self::exact_i64(
110                    num_vertices.saturating_sub(1),
111                    "bounding topological labels",
112                )?),
113            )
114            .map_err(Self::target_construction)?,
115        );
116
117        let target = ILP::with_variables(variables, constraints, vec![], ObjectiveSense::Minimize)
118            .map_err(<Self as ReduceTo<ILP<i64, i64, Bounded>>>::target_construction)?;
119        Ok(ReductionMultipleChoiceBranchingToILP { target, num_arcs })
120    }
121}
122
123#[cfg(feature = "example-db")]
124pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
125    use crate::topology::DirectedGraph;
126
127    vec![crate::example_db::specs::RuleExampleSpec {
128        id: "multiplechoicebranching_to_ilp",
129        build: || {
130            let source = MultipleChoiceBranching::new(
131                DirectedGraph::new(3, vec![(0, 1), (1, 2)]),
132                vec![2, 3],
133                vec![vec![0], vec![1]],
134                5,
135            );
136            crate::example_db::specs::rule_example_via_bounded_ilp::<_>(source)
137        },
138    }]
139}
140
141#[cfg(test)]
142#[path = "../unit_tests/rules/multiplechoicebranching_ilp.rs"]
143mod tests;
problemreductions/rules/multiplechoicebranching_ilp.rs

problemreductions/rules/
multiplechoicebranching_ilp.rs
