problemreductions/rules/
multiplechoicebranching_ilp.rs

1//! Reduction from MultipleChoiceBranching with integer weights to integer ILP.
2
3use crate::models::algebraic::{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>,
11    num_arcs: usize,
12}
13
14impl ReductionResult for ReductionMultipleChoiceBranchingToILP {
15    type Source = MultipleChoiceBranching<i64>;
16    type Target = ILP<i64>;
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_solution(self.target_problem(), target_solution)?;
27        Ok(target_solution[..self.num_arcs]
28            .iter()
29            .map(|&selected| selected == 1)
30            .collect())
31    }
32}
33
34#[reduction(
35    transform = exact {
36        num_vars = "num_arcs + num_vertices",
37        num_constraints = "2 * num_arcs + 2 * num_vertices + num_partition_groups + 1",
38    },
39    unavailable = {
40        num_nonzeros = "zero weights and loop normalization determine the exact nonzero count",
41    }
42)]
43impl ReduceTo<ILP<i64>> for MultipleChoiceBranching<i64> {
44    type Result = ReductionMultipleChoiceBranchingToILP;
45
46    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
47        let num_arcs = self.num_arcs();
48        let num_vertices = self.num_vertices();
49        let order = |vertex: usize| num_arcs + vertex;
50        let mut constraints = Vec::new();
51
52        for arc in 0..num_arcs {
53            constraints.push(LinearConstraint::le(vec![(arc, 1)], 1));
54        }
55        if num_vertices > 0 {
56            let big_m = <Self as ReduceTo<ILP<i64>>>::exact_i64(
57                num_vertices,
58                "encoding topological-order constraints",
59            )?;
60            for vertex in 0..num_vertices {
61                constraints.push(LinearConstraint::le(vec![(order(vertex), 1)], big_m - 1));
62            }
63            for (arc, &(source, target)) in self.graph().arcs().iter().enumerate() {
64                constraints.push(LinearConstraint::le(
65                    vec![(order(source), 1), (order(target), -1), (arc, big_m)],
66                    big_m - 1,
67                ));
68            }
69        }
70        for group in self.partition() {
71            constraints.push(LinearConstraint::le(
72                group.iter().map(|&arc| (arc, 1)).collect(),
73                1,
74            ));
75        }
76        for vertex in 0..num_vertices {
77            constraints.push(LinearConstraint::le(
78                self.graph()
79                    .arcs()
80                    .iter()
81                    .enumerate()
82                    .filter_map(|(arc, &(_, target))| (target == vertex).then_some((arc, 1)))
83                    .collect(),
84                1,
85            ));
86        }
87        constraints.push(LinearConstraint::ge(
88            self.weights()
89                .iter()
90                .enumerate()
91                .map(|(arc, &weight)| (arc, weight))
92                .collect(),
93            *self.threshold(),
94        ));
95
96        let target = ILP::new(
97            num_arcs + num_vertices,
98            constraints,
99            vec![],
100            ObjectiveSense::Minimize,
101        )
102        .map_err(<Self as ReduceTo<ILP<i64>>>::target_construction)?;
103        Ok(ReductionMultipleChoiceBranchingToILP { target, num_arcs })
104    }
105}
106
107#[cfg(feature = "example-db")]
108pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
109    use crate::topology::DirectedGraph;
110
111    vec![crate::example_db::specs::RuleExampleSpec {
112        id: "multiplechoicebranching_to_ilp",
113        build: || {
114            let source = MultipleChoiceBranching::new(
115                DirectedGraph::new(3, vec![(0, 1), (1, 2)]),
116                vec![2, 3],
117                vec![vec![0], vec![1]],
118                5,
119            );
120            crate::example_db::specs::rule_example_via_ilp::<_, i64>(source)
121        },
122    }]
123}
124
125#[cfg(test)]
126#[path = "../unit_tests/rules/multiplechoicebranching_ilp.rs"]
127mod tests;
problemreductions/rules/multiplechoicebranching_ilp.rs

problemreductions/rules/
multiplechoicebranching_ilp.rs
