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

problemreductions/models/misc/
bin_packing.rs
