problemreductions/rules/
integerknapsack_ilp.rs

1//! Reduction from IntegerKnapsack to `ILP<i64>`.
2//!
3//! Each item multiplicity becomes a non-negative integer ILP variable. The
4//! capacity inequality is kept directly, and explicit upper bounds
5//! `c_i <= floor(B / s_i)` preserve the exact witness domain of the source.
6
7use crate::models::algebraic::{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>,
15}
16
17impl ReductionResult for ReductionIntegerKnapsackToILP {
18    type Source = IntegerKnapsack;
19    type Target = ILP<i64>;
20
21    fn target_problem(&self) -> &ILP<i64> {
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(
36    transform = exact {
37        num_vars = "num_items",
38        num_constraints = "num_items + 1",
39    },
40    unavailable = {
41        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
42    }
43)]
44impl ReduceTo<ILP<i64>> for IntegerKnapsack {
45    type Result = ReductionIntegerKnapsackToILP;
46
47    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
48        let num_vars = self.num_items();
49        let mut constraints = Vec::with_capacity(num_vars + 1);
50        let sizes = self.sizes();
51        let values = self.values();
52
53        constraints.push(LinearConstraint::le(
54            sizes
55                .iter()
56                .enumerate()
57                .map(|(item, &size)| (item, size))
58                .collect(),
59            self.capacity(),
60        ));
61
62        for (i, &size) in self.sizes().iter().enumerate() {
63            let upper_bound = self.capacity() / size;
64            constraints.push(LinearConstraint::le(vec![(i, 1)], upper_bound));
65        }
66
67        let objective = values.iter().copied().enumerate().collect();
68
69        Ok(ReductionIntegerKnapsackToILP {
70            target: ILP::new(num_vars, constraints, objective, ObjectiveSense::Maximize)
71                .map_err(Self::target_construction)?,
72        })
73    }
74}
75
76#[cfg(feature = "example-db")]
77pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
78    vec![crate::example_db::specs::RuleExampleSpec {
79        id: "integerknapsack_to_ilp",
80        build: || {
81            let source = IntegerKnapsack::new(vec![3, 4, 5], vec![4, 5, 7], 10).unwrap();
82            crate::example_db::specs::rule_example_via_ilp::<_, i64>(source)
83        },
84    }]
85}
86
87#[cfg(test)]
88#[path = "../unit_tests/rules/integerknapsack_ilp.rs"]
89mod tests;
problemreductions/rules/integerknapsack_ilp.rs

problemreductions/rules/
integerknapsack_ilp.rs
