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
8use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
9use crate::models::misc::Knapsack;
10use crate::reduction;
11use crate::rules::traits::{ReduceTo, ReductionResult};
12
13/// Result of reducing Knapsack to ILP.
14#[derive(Debug, Clone)]
15pub struct ReductionKnapsackToILP {
16    target: ILP<bool>,
17}
18
19impl ReductionResult for ReductionKnapsackToILP {
20    type Source = Knapsack;
21    type Target = ILP<bool>;
22
23    fn target_problem(&self) -> &ILP<bool> {
24        &self.target
25    }
26
27    fn extract_solution(
28        &self,
29        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
30    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
31        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
32
33        Ok(target_solution.iter().map(|&value| value == 1).collect())
34    }
35}
36
37#[reduction(
38    transform = exact {
39        num_vars = "num_items",
40        num_constraints = "1",
41    },
42    unavailable = {
43        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
44    }
45)]
46impl ReduceTo<ILP<bool>> for Knapsack {
47    type Result = ReductionKnapsackToILP;
48
49    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
50        let num_vars = self.num_items();
51        let weights = self.weights();
52        let values = self.values();
53        let capacity = self.capacity();
54        let constraints = vec![LinearConstraint::le(
55            weights
56                .iter()
57                .enumerate()
58                .map(|(item, &weight)| (item, weight))
59                .collect(),
60            capacity,
61        )];
62        let objective = values.iter().copied().enumerate().collect();
63        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Maximize)
64            .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?;
65
66        Ok(ReductionKnapsackToILP { target })
67    }
68}
69
70#[cfg(feature = "example-db")]
71pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
72    use crate::export::SolutionPair;
73
74    vec![crate::example_db::specs::RuleExampleSpec {
75        id: "knapsack_to_ilp",
76        build: || {
77            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
78                Knapsack::new(vec![1, 3, 4, 5], vec![1, 4, 5, 7], 7),
79                SolutionPair {
80                    source_config: serde_json::json!(vec![false, true, true, false]),
81                    target_config: serde_json::json!(vec![0, 1, 1, 0]),
82                },
83            )
84        },
85    }]
86}
87
88#[cfg(test)]
89#[path = "../unit_tests/rules/knapsack_ilp.rs"]
90mod tests;
problemreductions/rules/knapsack_ilp.rs

problemreductions/rules/
knapsack_ilp.rs
