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_solution(self.target_problem(), target_solution)?;
40
41            target_solution[..item_arc_count]
42                .iter()
43                .map(|&flow| flow > 0)
44                .collect()
45        })
46    }
47}
48
49#[reduction(
50    transform = exact {
51        num_vertices = "num_elements + 3",
52        num_arcs = "2 * num_elements + 1",
53    },
54    unavailable = {
55        max_capacity = "the target capacity depends on source numeric values not represented by Partition parameters",
56        requirement = "the target requirement depends on source numeric values not represented by Partition parameters",
57    }
58)]
59impl ReduceTo<IntegralFlowWithMultipliers> for Partition {
60    type Result = ReductionPartitionToIntegralFlowWithMultipliers;
61
62    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
63        let total_sum = self.total_sum();
64        let source_n = self.num_elements();
65
66        if total_sum % 2 != 0 {
67            let graph = DirectedGraph::new(3, vec![(0, 1), (1, 2)]);
68            return Ok(ReductionPartitionToIntegralFlowWithMultipliers {
69                target: IntegralFlowWithMultipliers::new(graph, 0, 2, vec![1, 2, 1], vec![1, 1], 1),
70                item_arc_count: None,
71            });
72        }
73
74        let half_sum = total_sum / 2;
75        let relay = source_n + 1;
76        let sink = source_n + 2;
77
78        let mut arcs = Vec::with_capacity(2 * source_n + 1);
79        let mut capacities = Vec::with_capacity(2 * source_n + 1);
80        let mut multipliers = vec![1; source_n + 3];
81
82        for (index, &size) in self.sizes().iter().enumerate() {
83            let item_vertex = index + 1;
84            arcs.push((0, item_vertex));
85            capacities.push(1);
86            multipliers[item_vertex] = size;
87        }
88
89        for (index, &size) in self.sizes().iter().enumerate() {
90            let item_vertex = index + 1;
91            arcs.push((item_vertex, relay));
92            capacities.push(size);
93        }
94
95        arcs.push((relay, sink));
96        capacities.push(half_sum);
97        multipliers[relay] = 1;
98
99        let graph = DirectedGraph::new(source_n + 3, arcs);
100        Ok(ReductionPartitionToIntegralFlowWithMultipliers {
101            target: IntegralFlowWithMultipliers::new(
102                graph,
103                0,
104                sink,
105                multipliers,
106                capacities,
107                half_sum,
108            ),
109            item_arc_count: Some(source_n),
110        })
111    }
112}
113
114#[cfg(feature = "example-db")]
115pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
116    use crate::export::SolutionPair;
117
118    vec![crate::example_db::specs::RuleExampleSpec {
119        id: "partition_to_integralflowwithmultipliers",
120        build: || {
121            crate::example_db::specs::rule_example_with_witness::<_, IntegralFlowWithMultipliers>(
122                Partition::new(vec![2, 3, 4, 5, 6, 4]).unwrap(),
123                SolutionPair {
124                    source_config: serde_json::json!(vec![true, false, true, false, true, false]),
125                    target_config: serde_json::json!(vec![1, 0, 1, 0, 1, 0, 2, 0, 4, 0, 6, 0, 12]),
126                },
127            )
128        },
129    }]
130}
131
132#[cfg(test)]
133#[path = "../unit_tests/rules/partition_integralflowwithmultipliers.rs"]
134mod tests;
problemreductions/rules/partition_integralflowwithmultipliers.rs

problemreductions/rules/
partition_integralflowwithmultipliers.rs
