problemreductions/rules/
partition_integralflowwithmultipliers.rs

1//! Reduction from Partition to IntegralFlowWithMultipliers.
2//!
3//! For an even total sum `S`, this is Sahni's multiplier-flow gadget:
4//! items are binary source choices amplified by vertex multipliers and merged
5//! through a single bottleneck arc of capacity `S / 2`. For an odd total sum,
6//! the reduction returns a fixed infeasible target instance.
7
8use crate::models::graph::IntegralFlowWithMultipliers;
9use crate::models::misc::Partition;
10use crate::reduction;
11use crate::rules::traits::{ReduceTo, ReductionResult};
12use crate::topology::DirectedGraph;
13
14/// Result of reducing Partition to IntegralFlowWithMultipliers.
15#[derive(Debug, Clone)]
16pub struct ReductionPartitionToIntegralFlowWithMultipliers {
17    target: IntegralFlowWithMultipliers,
18    source_n: usize,
19    item_arc_count: usize,
20}
21
22impl ReductionResult for ReductionPartitionToIntegralFlowWithMultipliers {
23    type Source = Partition;
24    type Target = IntegralFlowWithMultipliers;
25
26    fn target_problem(&self) -> &Self::Target {
27        &self.target
28    }
29
30    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
31        if self.item_arc_count == 0 {
32            return vec![0; self.source_n];
33        }
34
35        if target_solution.len() < self.item_arc_count {
36            return vec![0; self.source_n];
37        }
38
39        target_solution[..self.item_arc_count].to_vec()
40    }
41}
42
43#[reduction(overhead = {
44    num_vertices = "num_elements + 3",
45    num_arcs = "2 * num_elements + 1",
46    max_capacity = "total_sum",
47    requirement = "total_sum",
48})]
49impl ReduceTo<IntegralFlowWithMultipliers> for Partition {
50    type Result = ReductionPartitionToIntegralFlowWithMultipliers;
51
52    fn reduce_to(&self) -> Self::Result {
53        let total_sum = self.total_sum();
54        let source_n = self.num_elements();
55
56        if !total_sum.is_multiple_of(2) {
57            let graph = DirectedGraph::new(3, vec![(0, 1), (1, 2)]);
58            return ReductionPartitionToIntegralFlowWithMultipliers {
59                target: IntegralFlowWithMultipliers::new(graph, 0, 2, vec![1, 2, 1], vec![1, 1], 1),
60                source_n,
61                item_arc_count: 0,
62            };
63        }
64
65        let half_sum = total_sum / 2;
66        let relay = source_n + 1;
67        let sink = source_n + 2;
68
69        let mut arcs = Vec::with_capacity(2 * source_n + 1);
70        let mut capacities = Vec::with_capacity(2 * source_n + 1);
71        let mut multipliers = vec![1; source_n + 3];
72
73        for (index, &size) in self.sizes().iter().enumerate() {
74            let item_vertex = index + 1;
75            arcs.push((0, item_vertex));
76            capacities.push(1);
77            multipliers[item_vertex] = size;
78        }
79
80        for (index, &size) in self.sizes().iter().enumerate() {
81            let item_vertex = index + 1;
82            arcs.push((item_vertex, relay));
83            capacities.push(size);
84        }
85
86        arcs.push((relay, sink));
87        capacities.push(half_sum);
88        multipliers[relay] = 1;
89
90        let graph = DirectedGraph::new(source_n + 3, arcs);
91        ReductionPartitionToIntegralFlowWithMultipliers {
92            target: IntegralFlowWithMultipliers::new(
93                graph,
94                0,
95                sink,
96                multipliers,
97                capacities,
98                half_sum,
99            ),
100            source_n,
101            item_arc_count: source_n,
102        }
103    }
104}
105
106#[cfg(feature = "example-db")]
107pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
108    use crate::export::SolutionPair;
109
110    vec![crate::example_db::specs::RuleExampleSpec {
111        id: "partition_to_integralflowwithmultipliers",
112        build: || {
113            crate::example_db::specs::rule_example_with_witness::<_, IntegralFlowWithMultipliers>(
114                Partition::new(vec![2, 3, 4, 5, 6, 4]),
115                SolutionPair {
116                    source_config: vec![1, 0, 1, 0, 1, 0],
117                    target_config: vec![1, 0, 1, 0, 1, 0, 2, 0, 4, 0, 6, 0, 12],
118                },
119            )
120        },
121    }]
122}
123
124#[cfg(test)]
125#[path = "../unit_tests/rules/partition_integralflowwithmultipliers.rs"]
126mod tests;
problemreductions/rules/partition_integralflowwithmultipliers.rs

problemreductions/rules/
partition_integralflowwithmultipliers.rs
