problemreductions/rules/
integerknapsack_ilp.rs

1//! Reduction from IntegerKnapsack to `ILP<i64, i64, Bounded>`.
2//!
3//! Each item multiplicity becomes a non-negative integer ILP variable. The
4//! capacity inequality omits oversized items (whose multiplicities are zero), and explicit upper bounds
5//! `c_i <= floor(B / s_i)` preserve the exact witness domain of the source.
6
7use crate::models::algebraic::{Bounded, IntegerVariable, LinearConstraint, ObjectiveSense, ILP};
8use crate::models::set::IntegerKnapsack;
9use crate::reduction;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11
12#[derive(Debug, Clone)]
13pub struct ReductionIntegerKnapsackToILP {
14    target: ILP<i64, i64, Bounded>,
15}
16
17impl ReductionResult for ReductionIntegerKnapsackToILP {
18    type Source = IntegerKnapsack;
19    type Target = ILP<i64, i64, Bounded>;
20
21    fn target_problem(&self) -> &ILP<i64, i64, Bounded> {
22        &self.target
23    }
24
25    fn extract_solution(
26        &self,
27        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
28    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
29        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
30
31        crate::rules::ilp_helpers::decode_usize_values(target_solution)
32    }
33}
34
35#[reduction(transform = {
36    exact {
37        num_vars = "num_items",
38        num_constraints = "num_items + 1",
39    },
40    upper_bound {
41        max_constraint_magnitude_bits = "capacity_bits",
42        num_nonzeros = "2 * num_items",
43    },
44})]
45impl ReduceTo<ILP<i64, i64, Bounded>> for IntegerKnapsack {
46    type Result = ReductionIntegerKnapsackToILP;
47
48    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
49        let num_vars = self.num_items();
50        let mut constraints = Vec::with_capacity(num_vars + 1);
51        let sizes = self.sizes();
52        let values = self.values();
53
54        constraints.push(LinearConstraint::le(
55            sizes
56                .iter()
57                .enumerate()
58                // Oversized items already have multiplicity fixed to zero by their bounds.
59                .filter(|&(_, &size)| size <= self.capacity())
60                .map(|(item, &size)| (item, size))
61                .collect(),
62            self.capacity(),
63        ));
64
65        for (i, &size) in self.sizes().iter().enumerate() {
66            let upper_bound = self.capacity() / size;
67            constraints.push(LinearConstraint::le(vec![(i, 1)], upper_bound));
68        }
69
70        let objective = values.iter().copied().enumerate().collect();
71
72        let variables = self
73            .sizes()
74            .iter()
75            .map(|&size| IntegerVariable::new(Some(0), Some(self.capacity() / size)))
76            .collect::<Result<Vec<_>, _>>()
77            .map_err(Self::target_construction)?;
78
79        Ok(ReductionIntegerKnapsackToILP {
80            target: ILP::with_variables(
81                variables,
82                constraints,
83                objective,
84                ObjectiveSense::Maximize,
85            )
86            .map_err(Self::target_construction)?,
87        })
88    }
89}
90
91#[cfg(feature = "example-db")]
92pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
93    vec![crate::example_db::specs::RuleExampleSpec {
94        id: "integerknapsack_to_ilp",
95        build: || {
96            let source = IntegerKnapsack::new(vec![3, 4, 5], vec![4, 5, 7], 10).unwrap();
97            crate::example_db::specs::rule_example_via_bounded_ilp::<_>(source)
98        },
99    }]
100}
101
102#[cfg(test)]
103#[path = "../unit_tests/rules/integerknapsack_ilp.rs"]
104mod tests;
problemreductions/rules/integerknapsack_ilp.rs

problemreductions/rules/
integerknapsack_ilp.rs
