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
109impl<W> Problem for BinPacking<W>
110where
111    W: WeightElement + crate::variant::VariantParam,
112    W::Sum: PartialOrd,
113{
114    const NAME: &'static str = "BinPacking";
115    type Solution = Vec<usize>;
116    type Value = Min<i64>;
117
118    crate::problem_parameters![("num_items", num_items),];
119
120    fn variant() -> Vec<(&'static str, &'static str)> {
121        crate::variant_params![W]
122    }
123
124    fn evaluate(
125        &self,
126        config: &Self::Solution,
127    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
128        let n = self.sizes.len();
129        if config.len() != n {
130            return Err(crate::traits::EvaluationError::InvalidConfiguration(
131                "bin assignment length does not match the items".into(),
132            ));
133        }
134        if config.iter().any(|&bin| bin >= n) {
135            return Err(crate::traits::EvaluationError::InvalidConfiguration(
136                "bin assignment contains an out-of-range bin".into(),
137            ));
138        }
139        Ok({
140            if !is_valid_packing(&self.sizes, &self.capacity, config)? {
141                return Ok(Min(None));
142            }
143            let num_bins = count_bins(config);
144            Min(Some(i64::try_from(num_bins).map_err(|_| {
145                crate::traits::EvaluationError::IntegerOverflow(
146                    "converting used-bin count to i64".into(),
147                )
148            })?))
149        })
150    }
151}
152
153impl<W> crate::solvers::BruteForceProblem for BinPacking<W>
154where
155    W: WeightElement + crate::variant::VariantParam,
156    W::Sum: PartialOrd,
157{
158    fn dimensions(&self) -> Vec<usize> {
159        let n = self.sizes.len();
160        vec![n; n]
161    }
162}
163
164/// Check if a configuration is a valid bin packing (all bins within capacity).
165fn is_valid_packing<W: WeightElement>(
166    sizes: &[W],
167    capacity: &W,
168    config: &[usize],
169) -> Result<bool, crate::traits::EvaluationError>
170where
171    W::Sum: PartialOrd,
172{
173    if config.len() != sizes.len() {
174        return Ok(false);
175    }
176    let n = sizes.len();
177    // Check all bin indices are in range
178    if config.iter().any(|&b| b >= n) {
179        return Ok(false);
180    }
181    // Compute load per bin
182    let cap_sum = capacity.to_sum();
183    let mut bin_load: Vec<W::Sum> = vec![W::Sum::zero(); n];
184    for (i, &bin) in config.iter().enumerate() {
185        bin_load[bin] = W::checked_add_to_sum(
186            bin_load[bin].clone(),
187            sizes[i].to_sum(),
188            "summing bin loads",
189        )?;
190    }
191    // Check capacity constraints
192    Ok(bin_load.iter().all(|load| *load <= cap_sum))
193}
194
195/// Count the number of distinct bins used in a configuration.
196fn count_bins(config: &[usize]) -> usize {
197    let mut used = vec![false; config.len()];
198    for &bin in config {
199        if bin < used.len() {
200            used[bin] = true;
201        }
202    }
203    used.iter().filter(|&&u| u).count()
204}
205
206crate::declare_variants! {
207    default BinPacking<i64> => "2^num_items",
208    BinPacking<f64> => "2^num_items",
209}
210
211crate::register_brute_force! {
212    BinPacking<i64>,
213    BinPacking<f64>,
214}
215
216#[cfg(feature = "example-db")]
217pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
218    vec![crate::example_db::specs::ModelExampleSpec {
219        id: "bin_packing",
220        // 3 items of sizes [3,3,4], capacity 7 → optimal 2 bins
221        instance: Box::new(BinPacking::<i64>::new(vec![3, 3, 4], 7).unwrap()),
222        optimal_config: serde_json::json!(vec![0, 1, 0]),
223        optimal_value: serde_json::json!(2),
224    }]
225}
226
227#[cfg(test)]
228#[path = "../../unit_tests/models/misc/bin_packing.rs"]
229mod tests;
problemreductions/models/misc/bin_packing.rs

problemreductions/models/misc/
bin_packing.rs
