problemreductions/models/misc/
bin_packing.rs

1//! Bin Packing problem implementation.
2//!
3//! The Bin Packing problem asks for an assignment of items to bins
4//! that minimizes the number of bins used while respecting capacity constraints.
5
6use crate::registry::{FieldInfo, ProblemSchemaEntry};
7use crate::traits::{OptimizationProblem, Problem};
8use crate::types::{Direction, SolutionSize, WeightElement};
9use serde::{Deserialize, Serialize};
10
11inventory::submit! {
12    ProblemSchemaEntry {
13        name: "BinPacking",
14        module_path: module_path!(),
15        description: "Assign items to bins minimizing number of bins used, subject to capacity",
16        fields: &[
17            FieldInfo { name: "sizes", type_name: "Vec<W>", description: "Item sizes s_i for each item" },
18            FieldInfo { name: "capacity", type_name: "W", description: "Bin capacity C" },
19        ],
20    }
21}
22
23/// The Bin Packing problem.
24///
25/// Given `n` items with sizes `s_1, ..., s_n` and bin capacity `C`,
26/// find an assignment of items to bins such that:
27/// - For each bin `j`, the total size of items assigned to `j` does not exceed `C`
28/// - The number of bins used is minimized
29///
30/// # Representation
31///
32/// Each item has a variable in `{0, ..., n-1}` representing its bin assignment.
33/// The worst case uses `n` bins (one item per bin).
34///
35/// # Type Parameters
36///
37/// * `W` - The weight type for sizes and capacity (e.g., `i32`, `f64`)
38///
39/// # Example
40///
41/// ```
42/// use problemreductions::models::misc::BinPacking;
43/// use problemreductions::{Problem, Solver, BruteForce};
44///
45/// // 4 items with sizes [3, 3, 2, 2], capacity 5
46/// let problem = BinPacking::new(vec![3, 3, 2, 2], 5);
47/// let solver = BruteForce::new();
48/// let solution = solver.find_best(&problem);
49/// assert!(solution.is_some());
50/// ```
51#[derive(Debug, Clone, Serialize, Deserialize)]
52pub struct BinPacking<W> {
53    /// Item sizes.
54    sizes: Vec<W>,
55    /// Bin capacity.
56    capacity: W,
57}
58
59impl<W: Clone> BinPacking<W> {
60    /// Create a Bin Packing problem from item sizes and capacity.
61    pub fn new(sizes: Vec<W>, capacity: W) -> Self {
62        Self { sizes, capacity }
63    }
64
65    /// Get the item sizes.
66    pub fn sizes(&self) -> &[W] {
67        &self.sizes
68    }
69
70    /// Get the bin capacity.
71    pub fn capacity(&self) -> &W {
72        &self.capacity
73    }
74
75    /// Get the number of items.
76    pub fn num_items(&self) -> usize {
77        self.sizes.len()
78    }
79}
80
81impl<W> Problem for BinPacking<W>
82where
83    W: WeightElement + crate::variant::VariantParam,
84    W::Sum: PartialOrd,
85{
86    const NAME: &'static str = "BinPacking";
87    type Metric = SolutionSize<i32>;
88
89    fn variant() -> Vec<(&'static str, &'static str)> {
90        crate::variant_params![W]
91    }
92
93    fn dims(&self) -> Vec<usize> {
94        let n = self.sizes.len();
95        vec![n; n]
96    }
97
98    fn evaluate(&self, config: &[usize]) -> SolutionSize<i32> {
99        if !is_valid_packing(&self.sizes, &self.capacity, config) {
100            return SolutionSize::Invalid;
101        }
102        let num_bins = count_bins(config);
103        SolutionSize::Valid(num_bins as i32)
104    }
105}
106
107impl<W> OptimizationProblem for BinPacking<W>
108where
109    W: WeightElement + crate::variant::VariantParam,
110    W::Sum: PartialOrd,
111{
112    type Value = i32;
113
114    fn direction(&self) -> Direction {
115        Direction::Minimize
116    }
117}
118
119/// Check if a configuration is a valid bin packing (all bins within capacity).
120fn is_valid_packing<W: WeightElement>(sizes: &[W], capacity: &W, config: &[usize]) -> bool
121where
122    W::Sum: PartialOrd,
123{
124    if config.len() != sizes.len() {
125        return false;
126    }
127    let n = sizes.len();
128    // Check all bin indices are in range
129    if config.iter().any(|&b| b >= n) {
130        return false;
131    }
132    // Compute load per bin
133    let cap_sum = capacity.to_sum();
134    let mut bin_load: Vec<W::Sum> = vec![W::Sum::default(); n];
135    for (i, &bin) in config.iter().enumerate() {
136        bin_load[bin] += sizes[i].to_sum();
137    }
138    // Check capacity constraints
139    bin_load.iter().all(|load| *load <= cap_sum)
140}
141
142/// Count the number of distinct bins used in a configuration.
143fn count_bins(config: &[usize]) -> usize {
144    let mut used = vec![false; config.len()];
145    for &bin in config {
146        if bin < used.len() {
147            used[bin] = true;
148        }
149    }
150    used.iter().filter(|&&u| u).count()
151}
152
153crate::declare_variants! {
154    BinPacking<i32> => "2^num_items",
155    BinPacking<f64> => "2^num_items",
156}
157
158#[cfg(test)]
159#[path = "../../unit_tests/models/misc/bin_packing.rs"]
160mod tests;
problemreductions/models/misc/bin_packing.rs

problemreductions/models/misc/
bin_packing.rs
