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(&self, target_solution: &[usize]) -> Vec<usize> {
25        target_solution.to_vec()
26    }
27}
28
29#[reduction(
30    overhead = {
31        num_vars = "num_items",
32        num_constraints = "num_precedences + 1",
33    }
34)]
35impl ReduceTo<ILP<bool>> for PartiallyOrderedKnapsack {
36    type Result = ReductionPOKToILP;
37
38    fn reduce_to(&self) -> Self::Result {
39        let n = self.num_items();
40        let mut constraints = Vec::new();
41
42        // Capacity constraint: Σ w_i·x_i ≤ capacity
43        let cap_terms: Vec<(usize, f64)> = self
44            .weights()
45            .iter()
46            .enumerate()
47            .map(|(i, &w)| (i, w as f64))
48            .collect();
49        constraints.push(LinearConstraint::le(cap_terms, self.capacity() as f64));
50
51        // Precedence constraints: ∀ (a,b): x_b - x_a ≤ 0
52        for &(a, b) in self.precedences() {
53            constraints.push(LinearConstraint::le(vec![(b, 1.0), (a, -1.0)], 0.0));
54        }
55
56        // Objective: Maximize Σ v_i·x_i
57        let objective: Vec<(usize, f64)> = self
58            .values()
59            .iter()
60            .enumerate()
61            .map(|(i, &v)| (i, v as f64))
62            .collect();
63
64        let target = ILP::new(n, constraints, objective, ObjectiveSense::Maximize);
65        ReductionPOKToILP { target }
66    }
67}
68
69#[cfg(feature = "example-db")]
70pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
71    vec![crate::example_db::specs::RuleExampleSpec {
72        id: "partiallyorderedknapsack_to_ilp",
73        build: || {
74            let source =
75                PartiallyOrderedKnapsack::new(vec![2, 3, 1], vec![3, 4, 2], vec![(0, 1)], 4);
76            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
77        },
78    }]
79}
80
81#[cfg(test)]
82#[path = "../unit_tests/rules/partiallyorderedknapsack_ilp.rs"]
83mod tests;
problemreductions/rules/partiallyorderedknapsack_ilp.rs

problemreductions/rules/
partiallyorderedknapsack_ilp.rs
