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(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),
108                SolutionPair {
109                    source_config: vec![2, 1, 0, 0, 2],
110                    target_config: 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
