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::{ConstructionError, FieldInfo, ProblemSchemaEntry, VariantDimension};
7use crate::traits::Problem;
8use crate::types::{Min, WeightElement};
9use num_traits::Zero;
10use serde::{Deserialize, Serialize};
11
12inventory::submit! {
13    ProblemSchemaEntry {
14        name: "BinPacking",
15        display_name: "Bin Packing",
16        aliases: &[],
17        dimensions: &[VariantDimension::new("weight", "i64", &["i64", "f64"])],
18        category: crate::registry::ProblemCategory::Misc,
19        module_path: module_path!(),
20        description: "Assign items to bins minimizing number of bins used, subject to capacity",
21        fields: &[
22            FieldInfo { name: "sizes", type_name: "Vec<W>", description: "Item sizes s_i for each item" },
23            FieldInfo { name: "capacity", type_name: "W", description: "Bin capacity C" },
24        ],
25    }
26}
27
28/// The Bin Packing problem.
29///
30/// Given `n` items with sizes `s_1, ..., s_n` and bin capacity `C`,
31/// find an assignment of items to bins such that:
32/// - For each bin `j`, the total size of items assigned to `j` does not exceed `C`
33/// - The number of bins used is minimized
34///
35/// # Representation
36///
37/// Each item has a variable in `{0, ..., n-1}` representing its bin assignment.
38/// The worst case uses `n` bins (one item per bin).
39///
40/// # Type Parameters
41///
42/// * `W` - The weight type for sizes and capacity (e.g., `i64`, `f64`)
43///
44/// # Example
45///
46/// ```
47/// use problemreductions::models::misc::BinPacking;
48/// use problemreductions::{Problem, BruteForce};
49///
50/// // 4 items with sizes [3, 3, 2, 2], capacity 5
51/// let problem = BinPacking::new(vec![3, 3, 2, 2], 5).unwrap();
52/// let solver = BruteForce::new();
53/// let solution = solver.solve(&problem).unwrap();
54/// assert!(solution.is_some());
55/// ```
56#[derive(Debug, Clone, Serialize)]
57pub struct BinPacking<W> {
58    /// Item sizes.
59    sizes: Vec<W>,
60    /// Bin capacity.
61    capacity: W,
62}
63
64#[derive(Deserialize)]
65struct BinPackingData<W> {
66    sizes: Vec<W>,
67    capacity: W,
68}
69
70impl<'de, W> Deserialize<'de> for BinPacking<W>
71where
72    W: WeightElement + Deserialize<'de>,
73{
74    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
75    where
76        D: serde::Deserializer<'de>,
77    {
78        let data = BinPackingData::deserialize(deserializer)?;
79        Self::new(data.sizes, data.capacity).map_err(serde::de::Error::custom)
80    }
81}
82
83impl<W: WeightElement> BinPacking<W> {
84    /// Create a Bin Packing problem from item sizes and capacity.
85    pub fn new(sizes: Vec<W>, capacity: W) -> Result<Self, ConstructionError> {
86        for (index, size) in sizes.iter().enumerate() {
87            size.validate_element(&format!("item size at index {index}"))?;
88        }
89        capacity.validate_element("bin capacity")?;
90        Ok(Self { sizes, capacity })
91    }
92
93    /// Get the item sizes.
94    pub fn sizes(&self) -> &[W] {
95        &self.sizes
96    }
97
98    /// Get the bin capacity.
99    pub fn capacity(&self) -> &W {
100        &self.capacity
101    }
102
103    /// Get the number of items.
104    pub fn num_items(&self) -> usize {
105        self.sizes.len()
106    }
107
108    /// Smallest h >= 1 bounding the magnitudes of item sizes and capacity by 2^h
109    /// (strictly). For floating weights, this measures magnitude, not precision.
110    pub fn max_numeric_magnitude_bits(&self) -> u64 {
111        crate::types::max_numeric_magnitude_bits(
112            self.sizes
113                .iter()
114                .chain(std::iter::once(&self.capacity))
115                .map(W::to_sum),
116        )
117    }
118}
119
120impl<W> Problem for BinPacking<W>
121where
122    W: WeightElement + crate::variant::VariantParam,
123    W::Sum: PartialOrd,
124{
125    const NAME: &'static str = "BinPacking";
126    type Solution = Vec<usize>;
127    type Value = Min<i64>;
128
129    crate::problem_parameters![
130        ("max_numeric_magnitude_bits", max_numeric_magnitude_bits),
131        ("num_items", num_items),
132    ];
133
134    fn variant() -> Vec<(&'static str, &'static str)> {
135        crate::variant_params![W]
136    }
137
138    fn evaluate(
139        &self,
140        config: &Self::Solution,
141    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
142        let n = self.sizes.len();
143        if config.len() != n {
144            return Err(crate::traits::EvaluationError::InvalidConfiguration(
145                "bin assignment length does not match the items".into(),
146            ));
147        }
148        if config.iter().any(|&bin| bin >= n) {
149            return Err(crate::traits::EvaluationError::InvalidConfiguration(
150                "bin assignment contains an out-of-range bin".into(),
151            ));
152        }
153        Ok({
154            if !is_valid_packing(&self.sizes, &self.capacity, config)? {
155                return Ok(Min(None));
156            }
157            let num_bins = count_bins(config);
158            Min(Some(i64::try_from(num_bins).map_err(|_| {
159                crate::traits::EvaluationError::IntegerOverflow(
160                    "converting used-bin count to i64".into(),
161                )
162            })?))
163        })
164    }
165}
166
167impl<W> crate::solvers::BruteForceProblem for BinPacking<W>
168where
169    W: WeightElement + crate::variant::VariantParam,
170    W::Sum: PartialOrd,
171{
172    fn dimensions(&self) -> Vec<usize> {
173        let n = self.sizes.len();
174        vec![n; n]
175    }
176}
177
178/// Check if a configuration is a valid bin packing (all bins within capacity).
179fn is_valid_packing<W: WeightElement>(
180    sizes: &[W],
181    capacity: &W,
182    config: &[usize],
183) -> Result<bool, crate::traits::EvaluationError>
184where
185    W::Sum: PartialOrd,
186{
187    if config.len() != sizes.len() {
188        return Ok(false);
189    }
190    let n = sizes.len();
191    // Check all bin indices are in range
192    if config.iter().any(|&b| b >= n) {
193        return Ok(false);
194    }
195    // Compute load per bin
196    let cap_sum = capacity.to_sum();
197    let mut bin_load: Vec<W::Sum> = vec![W::Sum::zero(); n];
198    for (i, &bin) in config.iter().enumerate() {
199        bin_load[bin] = W::checked_add_to_sum(
200            bin_load[bin].clone(),
201            sizes[i].to_sum(),
202            "summing bin loads",
203        )?;
204    }
205    // Check capacity constraints
206    Ok(bin_load.iter().all(|load| *load <= cap_sum))
207}
208
209/// Count the number of distinct bins used in a configuration.
210fn count_bins(config: &[usize]) -> usize {
211    let mut used = vec![false; config.len()];
212    for &bin in config {
213        if bin < used.len() {
214            used[bin] = true;
215        }
216    }
217    used.iter().filter(|&&u| u).count()
218}
219
220crate::declare_variants! {
221    default BinPacking<i64> => "2^num_items",
222    BinPacking<f64> => "2^num_items",
223}
224
225crate::register_brute_force! {
226    BinPacking<i64>,
227    BinPacking<f64>,
228}
229
230#[cfg(feature = "example-db")]
231pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
232    vec![crate::example_db::specs::ModelExampleSpec {
233        id: "bin_packing",
234        // 3 items of sizes [3,3,4], capacity 7 → optimal 2 bins
235        instance: Box::new(BinPacking::<i64>::new(vec![3, 3, 4], 7).unwrap()),
236        optimal_config: serde_json::json!(vec![0, 1, 0]),
237        optimal_value: serde_json::json!(2),
238    }]
239}
240
241#[cfg(test)]
242#[path = "../../unit_tests/models/misc/bin_packing.rs"]
243mod tests;
problemreductions/models/misc/bin_packing.rs

problemreductions/models/misc/
bin_packing.rs
