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    item_arc_count: Option<usize>,
19}
20
21impl ReductionResult for ReductionPartitionToIntegralFlowWithMultipliers {
22    type Source = Partition;
23    type Target = IntegralFlowWithMultipliers;
24
25    fn target_problem(&self) -> &Self::Target {
26        &self.target
27    }
28
29    fn extract_solution(
30        &self,
31        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
32    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
33        Ok({
34            let item_arc_count = self.item_arc_count.ok_or_else(|| {
35                crate::rules::ExtractionError::invalid(
36                    "the fixed infeasible target instance has no extractable witness",
37                )
38            })?;
39            crate::rules::traits::validate_target_witness(
40                self.target_problem(),
41                target_solution,
42                |value| value.0,
43                "target witness does not satisfy the target problem",
44            )?;
45
46            target_solution[..item_arc_count]
47                .iter()
48                .map(|&flow| flow > 0)
49                .collect()
50        })
51    }
52}
53
54#[crate::aggregate_reduction(identity)]
55impl crate::rules::AggregateReductionResult for ReductionPartitionToIntegralFlowWithMultipliers {}
56
57#[reduction(
58    transform = upper_bound {
59        // Odd sums use capacity 1; otherwise max(1,max(sizes),S/2)<=S.
60        max_capacity = "total_sum",
61        max_capacity_bits = "max_numeric_magnitude_bits + num_elements",
62        num_vertices = "num_elements + 3",
63        num_arcs = "2 * num_elements + 1",
64    },
65)]
66impl ReduceTo<IntegralFlowWithMultipliers> for Partition {
67    type Result = ReductionPartitionToIntegralFlowWithMultipliers;
68
69    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
70        let total_sum = self.total_sum();
71        let source_n = self.num_elements();
72
73        if total_sum % 2 != 0 {
74            let graph = DirectedGraph::new(3, vec![(0, 1), (1, 2)]);
75            return Ok(ReductionPartitionToIntegralFlowWithMultipliers {
76                target: IntegralFlowWithMultipliers::new(graph, 0, 2, vec![1, 2, 1], vec![1, 1], 1),
77                item_arc_count: None,
78            });
79        }
80
81        let half_sum = total_sum / 2;
82        let relay = source_n + 1;
83        let sink = source_n + 2;
84
85        let mut arcs = Vec::with_capacity(2 * source_n + 1);
86        let mut capacities = Vec::with_capacity(2 * source_n + 1);
87        let mut multipliers = vec![1; source_n + 3];
88
89        for (index, &size) in self.sizes().iter().enumerate() {
90            let item_vertex = index + 1;
91            arcs.push((0, item_vertex));
92            capacities.push(1);
93            multipliers[item_vertex] = size;
94        }
95
96        for (index, &size) in self.sizes().iter().enumerate() {
97            let item_vertex = index + 1;
98            arcs.push((item_vertex, relay));
99            capacities.push(size);
100        }
101
102        arcs.push((relay, sink));
103        capacities.push(half_sum);
104        multipliers[relay] = 1;
105
106        let graph = DirectedGraph::new(source_n + 3, arcs);
107        Ok(ReductionPartitionToIntegralFlowWithMultipliers {
108            target: IntegralFlowWithMultipliers::new(
109                graph,
110                0,
111                sink,
112                multipliers,
113                capacities,
114                half_sum,
115            ),
116            item_arc_count: Some(source_n),
117        })
118    }
119}
120
121#[cfg(feature = "example-db")]
122pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
123    use crate::export::SolutionPair;
124
125    vec![crate::example_db::specs::RuleExampleSpec {
126        id: "partition_to_integralflowwithmultipliers",
127        build: || {
128            crate::example_db::specs::rule_example_with_witness::<_, IntegralFlowWithMultipliers>(
129                Partition::new(vec![2, 3, 4, 5, 6, 4]).unwrap(),
130                SolutionPair {
131                    source_config: serde_json::json!(vec![true, false, true, false, true, false]),
132                    target_config: serde_json::json!(vec![1, 0, 1, 0, 1, 0, 2, 0, 4, 0, 6, 0, 12]),
133                },
134            )
135        },
136    }]
137}
138
139#[cfg(test)]
140#[path = "../unit_tests/rules/partition_integralflowwithmultipliers.rs"]
141mod tests;
problemreductions/rules/partition_integralflowwithmultipliers.rs

problemreductions/rules/
partition_integralflowwithmultipliers.rs
