problemreductions/rules/
knapsack_ilp.rs

1//! Reduction from Knapsack to ILP (Integer Linear Programming).
2//!
3//! The standard 0-1 knapsack formulation is already a binary ILP:
4//! - Variables: one binary variable per item
5//! - Constraint: the total selected weight must not exceed capacity
6//! - Objective: maximize the total selected value
7//!
8//! Items exceeding capacity are fixed to zero and omitted from the capacity row.
9
10use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
11use crate::models::misc::Knapsack;
12use crate::reduction;
13use crate::rules::traits::{ReduceTo, ReductionResult};
14
15/// Result of reducing Knapsack to ILP.
16#[derive(Debug, Clone)]
17pub struct ReductionKnapsackToILP {
18    target: ILP<bool>,
19}
20
21impl ReductionResult for ReductionKnapsackToILP {
22    type Source = Knapsack;
23    type Target = ILP<bool>;
24
25    fn target_problem(&self) -> &ILP<bool> {
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        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
34
35        Ok(target_solution.iter().map(|&value| value == 1).collect())
36    }
37}
38
39#[reduction(transform = {
40    exact {
41        num_vars = "num_items",
42    },
43    upper_bound {
44        max_constraint_magnitude_bits = "capacity_bits",
45        num_constraints = "num_items + 1",
46        num_nonzeros = "num_items",
47    },
48})]
49impl ReduceTo<ILP<bool>> for Knapsack {
50    type Result = ReductionKnapsackToILP;
51
52    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
53        let num_vars = self.num_items();
54        let weights = self.weights();
55        let values = self.values();
56        let capacity = self.capacity();
57        let mut constraints = vec![LinearConstraint::le(
58            weights
59                .iter()
60                .enumerate()
61                .filter(|&(_, &weight)| weight <= capacity)
62                .map(|(item, &weight)| (item, weight))
63                .collect(),
64            capacity,
65        )];
66        // Oversized items are impossible choices; their magnitudes need not enter the ILP.
67        for (item, &weight) in weights.iter().enumerate() {
68            if weight > capacity {
69                constraints.push(LinearConstraint::eq(vec![(item, 1)], 0));
70            }
71        }
72        let objective = values.iter().copied().enumerate().collect();
73        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Maximize)
74            .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?;
75
76        Ok(ReductionKnapsackToILP { target })
77    }
78}
79
80#[cfg(feature = "example-db")]
81pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
82    use crate::export::SolutionPair;
83
84    vec![crate::example_db::specs::RuleExampleSpec {
85        id: "knapsack_to_ilp",
86        build: || {
87            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
88                Knapsack::new(vec![1, 3, 4, 5], vec![1, 4, 5, 7], 7),
89                SolutionPair {
90                    source_config: serde_json::json!(vec![false, true, true, false]),
91                    target_config: serde_json::json!(vec![0, 1, 1, 0]),
92                },
93            )
94        },
95    }]
96}
97
98#[cfg(test)]
99#[path = "../unit_tests/rules/knapsack_ilp.rs"]
100mod tests;
problemreductions/rules/knapsack_ilp.rs

problemreductions/rules/
knapsack_ilp.rs
