problemreductions/rules/
binpacking_ilp.rs

1//! Reduction from BinPacking to ILP (Integer Linear Programming).
2//!
3//! The Bin Packing problem can be formulated as a binary ILP using
4//! the standard assignment formulation (Martello & Toth, 1990):
5//! - Variables: `x_{ij}` (item i assigned to bin j) + `y_j` (bin j used), all binary
6//! - Constraints: assignment (each item in exactly one bin) + capacity/linking
7//! - Objective: minimize number of bins used
8
9use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
10use crate::models::misc::BinPacking;
11use crate::reduction;
12use crate::rules::ilp_helpers::one_hot_decode_rows;
13use crate::rules::traits::{ReduceTo, ReductionResult};
14
15/// Result of reducing BinPacking to ILP.
16///
17/// Variable layout (all binary):
18/// - `x_{ij}` for i=0..n-1, j=0..n-1: item i assigned to bin j (index: i*n + j)
19/// - `y_j` for j=0..n-1: bin j is used (index: n*n + j)
20///
21/// Total: n^2 + n variables.
22#[derive(Debug, Clone)]
23pub struct ReductionBPToILP {
24    target: ILP<bool>,
25    /// Number of items in the source problem.
26    n: usize,
27}
28
29impl ReductionResult for ReductionBPToILP {
30    type Source = BinPacking<i64>;
31    type Target = ILP<bool>;
32
33    fn target_problem(&self) -> &ILP<bool> {
34        &self.target
35    }
36
37    /// Extract solution from ILP back to BinPacking.
38    ///
39    /// For each item i, find the unique bin j where x_{ij} = 1.
40    fn extract_solution(
41        &self,
42        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
43    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
44        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
45
46        one_hot_decode_rows(target_solution, self.n, self.n, 0)
47    }
48}
49
50#[reduction(
51    transform = exact {
52        num_vars = "num_items * num_items + num_items",
53        num_constraints = "2 * num_items",
54    },
55    unavailable = {
56        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
57    }
58)]
59impl ReduceTo<ILP<bool>> for BinPacking<i64> {
60    type Result = ReductionBPToILP;
61
62    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
63        let n = self.num_items();
64        let num_vars = n * n + n;
65
66        let mut constraints = Vec::with_capacity(2 * n);
67
68        // Assignment constraints: for each item i, sum_j x_{ij} = 1
69        for i in 0..n {
70            let terms: Vec<(usize, i64)> = (0..n).map(|j| (i * n + j, 1)).collect();
71            constraints.push(LinearConstraint::eq(terms, 1));
72        }
73
74        // Capacity + linking constraints: for each bin j,
75        // sum_i w_i * x_{ij} - C * y_j <= 0
76        let cap = *self.capacity();
77        let sizes = self.sizes();
78        for j in 0..n {
79            let mut terms: Vec<(usize, i64)> = sizes
80                .iter()
81                .enumerate()
82                .map(|(i, &weight)| (i * n + j, weight))
83                .collect();
84            // Subtract C * y_j
85            terms.push((n * n + j, -cap));
86            constraints.push(LinearConstraint::le(terms, 0));
87        }
88
89        // Objective: minimize sum_j y_j
90        let objective: Vec<(usize, i64)> = (0..n).map(|j| (n * n + j, 1)).collect();
91
92        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
93            .map_err(Self::target_construction)?;
94
95        Ok(ReductionBPToILP { target, n })
96    }
97}
98
99#[cfg(feature = "example-db")]
100pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
101    use crate::export::SolutionPair;
102
103    vec![crate::example_db::specs::RuleExampleSpec {
104        id: "binpacking_to_ilp",
105        build: || {
106            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
107                BinPacking::new(vec![6, 5, 5, 4, 3], 10).unwrap(),
108                SolutionPair {
109                    source_config: serde_json::json!(vec![2, 1, 0, 0, 2]),
110                    target_config: serde_json::json!(vec![
111                        0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0,
112                        1, 1, 1, 0, 0,
113                    ]),
114                },
115            )
116        },
117    }]
118}
119
120#[cfg(test)]
121#[path = "../unit_tests/rules/binpacking_ilp.rs"]
122mod tests;
problemreductions/rules/binpacking_ilp.rs

problemreductions/rules/
binpacking_ilp.rs
