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(&self, target_solution: &[usize]) -> Vec<usize> {
28        target_solution.to_vec()
29    }
30}
31
32#[reduction(
33    overhead = {
34        num_vars = "num_items",
35        num_constraints = "1",
36    }
37)]
38impl ReduceTo<ILP<bool>> for Knapsack {
39    type Result = ReductionKnapsackToILP;
40
41    fn reduce_to(&self) -> Self::Result {
42        let num_vars = self.num_items();
43        let constraints = vec![LinearConstraint::le(
44            self.weights()
45                .iter()
46                .enumerate()
47                .map(|(i, &weight)| (i, weight as f64))
48                .collect(),
49            self.capacity() as f64,
50        )];
51        let objective = self
52            .values()
53            .iter()
54            .enumerate()
55            .map(|(i, &value)| (i, value as f64))
56            .collect();
57        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Maximize);
58
59        ReductionKnapsackToILP { target }
60    }
61}
62
63#[cfg(feature = "example-db")]
64pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
65    use crate::export::SolutionPair;
66
67    vec![crate::example_db::specs::RuleExampleSpec {
68        id: "knapsack_to_ilp",
69        build: || {
70            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
71                Knapsack::new(vec![1, 3, 4, 5], vec![1, 4, 5, 7], 7),
72                SolutionPair {
73                    source_config: vec![0, 1, 1, 0],
74                    target_config: vec![0, 1, 1, 0],
75                },
76            )
77        },
78    }]
79}
80
81#[cfg(test)]
82#[path = "../unit_tests/rules/knapsack_ilp.rs"]
83mod tests;
problemreductions/rules/knapsack_ilp.rs

problemreductions/rules/
knapsack_ilp.rs
