problemreductions/rules/
integerknapsack_ilp.rs

1//! Reduction from IntegerKnapsack to ILP<i32>.
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<i32>,
15}
16
17impl ReductionResult for ReductionIntegerKnapsackToILP {
18    type Source = IntegerKnapsack;
19    type Target = ILP<i32>;
20
21    fn target_problem(&self) -> &ILP<i32> {
22        &self.target
23    }
24
25    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
26        target_solution.to_vec()
27    }
28}
29
30#[reduction(
31    overhead = {
32        num_vars = "num_items",
33        num_constraints = "num_items + 1",
34    }
35)]
36impl ReduceTo<ILP<i32>> for IntegerKnapsack {
37    type Result = ReductionIntegerKnapsackToILP;
38
39    fn reduce_to(&self) -> Self::Result {
40        let num_vars = self.num_items();
41        let mut constraints = Vec::with_capacity(num_vars + 1);
42
43        constraints.push(LinearConstraint::le(
44            self.sizes()
45                .iter()
46                .enumerate()
47                .map(|(i, &size)| (i, size as f64))
48                .collect(),
49            self.capacity() as f64,
50        ));
51
52        for (i, &size) in self.sizes().iter().enumerate() {
53            let upper_bound = self.capacity() / size;
54            assert!(
55                upper_bound <= i32::MAX as i64,
56                "IntegerKnapsack -> ILP requires multiplicity bounds to fit in ILP<i32> variable bounds"
57            );
58            constraints.push(LinearConstraint::le(vec![(i, 1.0)], upper_bound as f64));
59        }
60
61        let objective = self
62            .values()
63            .iter()
64            .enumerate()
65            .map(|(i, &value)| (i, value as f64))
66            .collect();
67
68        ReductionIntegerKnapsackToILP {
69            target: ILP::new(num_vars, constraints, objective, ObjectiveSense::Maximize),
70        }
71    }
72}
73
74#[cfg(feature = "example-db")]
75pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
76    vec![crate::example_db::specs::RuleExampleSpec {
77        id: "integerknapsack_to_ilp",
78        build: || {
79            let source = IntegerKnapsack::new(vec![3, 4, 5], vec![4, 5, 7], 10);
80            crate::example_db::specs::rule_example_via_ilp::<_, i32>(source)
81        },
82    }]
83}
84
85#[cfg(test)]
86#[path = "../unit_tests/rules/integerknapsack_ilp.rs"]
87mod tests;
problemreductions/rules/integerknapsack_ilp.rs

problemreductions/rules/
integerknapsack_ilp.rs
