problemreductions/rules/
partiallyorderedknapsack_ilp.rs

1//! Reduction from PartiallyOrderedKnapsack to ILP (Integer Linear Programming).
2//!
3//! Binary variable x_i per item. Capacity constraint Σ w_i·x_i ≤ C.
4//! Precedence constraints: ∀ (a,b): x_b ≤ x_a. Maximize Σ v_i·x_i.
5
6use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
7use crate::models::misc::PartiallyOrderedKnapsack;
8use crate::reduction;
9use crate::rules::traits::{ReduceTo, ReductionResult};
10
11#[derive(Debug, Clone)]
12pub struct ReductionPOKToILP {
13    target: ILP<bool>,
14}
15
16impl ReductionResult for ReductionPOKToILP {
17    type Source = PartiallyOrderedKnapsack;
18    type Target = ILP<bool>;
19
20    fn target_problem(&self) -> &ILP<bool> {
21        &self.target
22    }
23
24    fn extract_solution(
25        &self,
26        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
27    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
28        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
29
30        Ok(target_solution.iter().map(|&value| value == 1).collect())
31    }
32}
33
34#[reduction(transform = {
35    exact {
36        max_constraint_magnitude_bits = "max_weight_bits",
37        num_vars = "num_items",
38        num_constraints = "num_precedences + 1",
39    },
40    upper_bound {
41        num_nonzeros = "num_items * (num_precedences + 1)",
42    },
43})]
44impl ReduceTo<ILP<bool>> for PartiallyOrderedKnapsack {
45    type Result = ReductionPOKToILP;
46
47    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
48        let n = self.num_items();
49        let mut constraints = Vec::new();
50        let weights = self.weights();
51        let values = self.values();
52        let capacity = self.capacity();
53
54        // Capacity constraint: Σ w_i·x_i ≤ capacity
55        let cap_terms: Vec<(usize, i64)> = weights
56            .iter()
57            .enumerate()
58            .map(|(item, &weight)| (item, weight))
59            .collect();
60        constraints.push(LinearConstraint::le(cap_terms, capacity));
61
62        // Precedence constraints: ∀ (a,b): x_b - x_a ≤ 0
63        for &(a, b) in self.precedences() {
64            constraints.push(LinearConstraint::le(vec![(b, 1), (a, -1)], 0));
65        }
66
67        // Objective: Maximize Σ v_i·x_i
68        let objective = values.iter().copied().enumerate().collect();
69
70        let target = ILP::new(n, constraints, objective, ObjectiveSense::Maximize)
71            .map_err(Self::target_construction)?;
72        Ok(ReductionPOKToILP { target })
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: "partiallyorderedknapsack_to_ilp",
80        build: || {
81            let source =
82                PartiallyOrderedKnapsack::new(vec![2, 3, 1], vec![3, 4, 2], vec![(0, 1)], 4);
83            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
84        },
85    }]
86}
87
88#[cfg(test)]
89#[path = "../unit_tests/rules/partiallyorderedknapsack_ilp.rs"]
90mod tests;
problemreductions/rules/partiallyorderedknapsack_ilp.rs

problemreductions/rules/
partiallyorderedknapsack_ilp.rs
