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// Rows copy item sizes and capacity (up to sign). Binary endpoints require only one bit.
51#[reduction(transform = {
52    exact {
53        num_vars = "num_items * num_items + num_items",
54        num_constraints = "2 * num_items",
55    },
56    upper_bound {
57        max_constraint_magnitude_bits = "max_numeric_magnitude_bits",
58        num_nonzeros = "(num_items * num_items + num_items) * (2 * num_items)",
59    },
60})]
61impl ReduceTo<ILP<bool>> for BinPacking<i64> {
62    type Result = ReductionBPToILP;
63
64    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
65        let n = self.num_items();
66        let num_vars = n * n + n;
67
68        let mut constraints = Vec::with_capacity(2 * n);
69
70        // Assignment constraints: for each item i, sum_j x_{ij} = 1
71        for i in 0..n {
72            let terms: Vec<(usize, i64)> = (0..n).map(|j| (i * n + j, 1)).collect();
73            constraints.push(LinearConstraint::eq(terms, 1));
74        }
75
76        // Capacity + linking constraints: for each bin j,
77        // sum_i w_i * x_{ij} - C * y_j <= 0
78        let cap = *self.capacity();
79        let sizes = self.sizes();
80        for j in 0..n {
81            let mut terms: Vec<(usize, i64)> = sizes
82                .iter()
83                .enumerate()
84                .map(|(i, &weight)| (i * n + j, weight))
85                .collect();
86            // Subtract C * y_j
87            terms.push((n * n + j, -cap));
88            constraints.push(LinearConstraint::le(terms, 0));
89        }
90
91        // Objective: minimize sum_j y_j
92        let objective: Vec<(usize, i64)> = (0..n).map(|j| (n * n + j, 1)).collect();
93
94        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
95            .map_err(Self::target_construction)?;
96
97        Ok(ReductionBPToILP { target, n })
98    }
99}
100
101#[cfg(feature = "example-db")]
102pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
103    use crate::export::SolutionPair;
104
105    vec![crate::example_db::specs::RuleExampleSpec {
106        id: "binpacking_to_ilp",
107        build: || {
108            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
109                BinPacking::new(vec![6, 5, 5, 4, 3], 10).unwrap(),
110                SolutionPair {
111                    source_config: serde_json::json!(vec![2, 1, 0, 0, 2]),
112                    target_config: serde_json::json!(vec![
113                        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,
114                        1, 1, 1, 0, 0,
115                    ]),
116                },
117            )
118        },
119    }]
120}
121
122#[cfg(test)]
123#[path = "../unit_tests/rules/binpacking_ilp.rs"]
124mod tests;
problemreductions/rules/binpacking_ilp.rs

problemreductions/rules/
binpacking_ilp.rs
