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(
35    transform = exact {
36        num_vars = "num_items",
37        num_constraints = "num_precedences + 1",
38    },
39    unavailable = {
40        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
41    }
42)]
43impl ReduceTo<ILP<bool>> for PartiallyOrderedKnapsack {
44    type Result = ReductionPOKToILP;
45
46    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
47        let n = self.num_items();
48        let mut constraints = Vec::new();
49        let weights = self.weights();
50        let values = self.values();
51        let capacity = self.capacity();
52
53        // Capacity constraint: Σ w_i·x_i ≤ capacity
54        let cap_terms: Vec<(usize, i64)> = weights
55            .iter()
56            .enumerate()
57            .map(|(item, &weight)| (item, weight))
58            .collect();
59        constraints.push(LinearConstraint::le(cap_terms, capacity));
60
61        // Precedence constraints: ∀ (a,b): x_b - x_a ≤ 0
62        for &(a, b) in self.precedences() {
63            constraints.push(LinearConstraint::le(vec![(b, 1), (a, -1)], 0));
64        }
65
66        // Objective: Maximize Σ v_i·x_i
67        let objective = values.iter().copied().enumerate().collect();
68
69        let target = ILP::new(n, constraints, objective, ObjectiveSense::Maximize)
70            .map_err(Self::target_construction)?;
71        Ok(ReductionPOKToILP { target })
72    }
73}
74
75#[cfg(feature = "example-db")]
76pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
77    vec![crate::example_db::specs::RuleExampleSpec {
78        id: "partiallyorderedknapsack_to_ilp",
79        build: || {
80            let source =
81                PartiallyOrderedKnapsack::new(vec![2, 3, 1], vec![3, 4, 2], vec![(0, 1)], 4);
82            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
83        },
84    }]
85}
86
87#[cfg(test)]
88#[path = "../unit_tests/rules/partiallyorderedknapsack_ilp.rs"]
89mod tests;
problemreductions/rules/partiallyorderedknapsack_ilp.rs

problemreductions/rules/
partiallyorderedknapsack_ilp.rs
