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::traits::{ReduceTo, ReductionResult};
13
14/// Result of reducing BinPacking to ILP.
15///
16/// Variable layout (all binary):
17/// - `x_{ij}` for i=0..n-1, j=0..n-1: item i assigned to bin j (index: i*n + j)
18/// - `y_j` for j=0..n-1: bin j is used (index: n*n + j)
19///
20/// Total: n^2 + n variables.
21#[derive(Debug, Clone)]
22pub struct ReductionBPToILP {
23    target: ILP<bool>,
24    /// Number of items in the source problem.
25    n: usize,
26}
27
28impl ReductionResult for ReductionBPToILP {
29    type Source = BinPacking<i32>;
30    type Target = ILP<bool>;
31
32    fn target_problem(&self) -> &ILP<bool> {
33        &self.target
34    }
35
36    /// Extract solution from ILP back to BinPacking.
37    ///
38    /// For each item i, find the unique bin j where x_{ij} = 1.
39    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
40        let n = self.n;
41        let mut assignment = vec![0usize; n];
42        for i in 0..n {
43            for j in 0..n {
44                if target_solution[i * n + j] == 1 {
45                    assignment[i] = j;
46                    break;
47                }
48            }
49        }
50        assignment
51    }
52}
53
54#[reduction(
55    overhead = {
56        num_vars = "num_items * num_items + num_items",
57        num_constraints = "2 * num_items",
58    }
59)]
60impl ReduceTo<ILP<bool>> for BinPacking<i32> {
61    type Result = ReductionBPToILP;
62
63    fn reduce_to(&self) -> Self::Result {
64        let n = self.num_items();
65        let num_vars = n * n + n;
66
67        let mut constraints = Vec::with_capacity(2 * n);
68
69        // Assignment constraints: for each item i, sum_j x_{ij} = 1
70        for i in 0..n {
71            let terms: Vec<(usize, f64)> = (0..n).map(|j| (i * n + j, 1.0)).collect();
72            constraints.push(LinearConstraint::eq(terms, 1.0));
73        }
74
75        // Capacity + linking constraints: for each bin j,
76        // sum_i w_i * x_{ij} - C * y_j <= 0
77        let cap = *self.capacity() as f64;
78        for j in 0..n {
79            let mut terms: Vec<(usize, f64)> = self
80                .sizes()
81                .iter()
82                .enumerate()
83                .map(|(i, w)| (i * n + j, *w as f64))
84                .collect();
85            // Subtract C * y_j
86            terms.push((n * n + j, -cap));
87            constraints.push(LinearConstraint::le(terms, 0.0));
88        }
89
90        // Objective: minimize sum_j y_j
91        let objective: Vec<(usize, f64)> = (0..n).map(|j| (n * n + j, 1.0)).collect();
92
93        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize);
94
95        ReductionBPToILP { target, n }
96    }
97}
98
99#[cfg(test)]
100#[path = "../unit_tests/rules/binpacking_ilp.rs"]
101mod tests;
problemreductions/rules/binpacking_ilp.rs

problemreductions/rules/
binpacking_ilp.rs
