jagua_rs/probs/bpp/entities/
problem.rs

1use crate::Instant;
2use crate::entities::Layout;
3use crate::entities::{PItemKey, PlacedItem};
4use crate::geometry::DTransformation;
5use crate::probs::bpp::entities::BPInstance;
6use crate::probs::bpp::entities::BPSolution;
7use crate::probs::bpp::util::assertions::problem_matches_solution;
8use itertools::Itertools;
9use slotmap::{SecondaryMap, SlotMap, new_key_type};
10
11new_key_type! {
12    /// Unique key for each [`Layout`] in a [`BPProblem`] and [`BPSolution`]
13    pub struct LayKey;
14}
15
16/// Dynamic counterpart of [`BPInstance`].
17#[derive(Clone)]
18pub struct BPProblem {
19    pub(crate) instance: BPInstance,
20    pub(crate) layouts: SlotMap<LayKey, Layout>,
21    /// Source bin index for each open layout.
22    pub(crate) layout_bins: SecondaryMap<LayKey, usize>,
23    pub(crate) item_demand_qtys: Vec<usize>,
24    pub(crate) bin_stock_qtys: Vec<usize>,
25}
26
27impl BPProblem {
28    #[must_use]
29    pub fn new(instance: BPInstance) -> Self {
30        let item_demand_qtys = instance.items.iter().map(|(_, qty)| *qty).collect_vec();
31        let bin_stock_qtys = instance.bins.iter().map(|bin| bin.stock).collect_vec();
32
33        Self {
34            instance,
35            layouts: SlotMap::with_key(),
36            layout_bins: SecondaryMap::new(),
37            item_demand_qtys,
38            bin_stock_qtys,
39        }
40    }
41
42    /// Removes a layout from the problem. The bin used by the layout will be closed and all items placed inside it will be deregistered.
43    pub fn remove_layout(&mut self, key: LayKey) {
44        self.deregister_layout(key);
45    }
46
47    /// Places an item according to the provided [`BPPlacement`] in the problem.
48    /// Panics if the item's demand or the selected bin's stock is exhausted.
49    pub fn place_item(&mut self, placement: BPPlacement) -> (LayKey, PItemKey) {
50        assert!(
51            self.item_demand_qtys[placement.item_idx] > 0,
52            "item demand exhausted"
53        );
54        let lkey = match placement.layout_id {
55            BPLayoutType::Open(lkey) => lkey,
56            BPLayoutType::Closed { bin_id } => {
57                //open a new layout
58                let bin = &self.instance.bins[bin_id];
59                let layout = Layout::new(bin.container.clone());
60                self.register_layout(layout, bin_id)
61            }
62        };
63
64        let layout = &mut self.layouts[lkey];
65        let item = self.instance.item(placement.item_idx);
66        let pik = layout.place_item(item, placement.d_transf);
67
68        self.register_included_item(placement.item_idx);
69
70        (lkey, pik)
71    }
72
73    /// Removes an item from a layout. If the layout is empty, it will be closed.
74    pub fn remove_item(&mut self, lkey: LayKey, pik: PItemKey) -> BPPlacement {
75        let pi = self.layouts[lkey].remove_item(pik);
76        self.deregister_included_item(pi.item.idx);
77        if self.layouts[lkey].is_empty() {
78            //if layout is empty, close it
79            let bin_id = self.layout_bins[lkey];
80            self.deregister_layout(lkey);
81            BPPlacement::from_placed_item(BPLayoutType::Closed { bin_id }, &pi)
82        } else {
83            BPPlacement::from_placed_item(BPLayoutType::Open(lkey), &pi)
84        }
85    }
86
87    /// Creates a snapshot of the current state of the problem as a [`BPSolution`].
88    #[must_use]
89    pub fn save(&self) -> BPSolution {
90        let layout_snapshots = self
91            .layouts
92            .iter()
93            .map(|(lkey, l)| (lkey, l.save()))
94            .collect();
95
96        let solution = BPSolution {
97            layout_snapshots,
98            layout_bins: self.layout_bins.clone(),
99            time_stamp: Instant::now(),
100        };
101
102        debug_assert!(problem_matches_solution(self, &solution));
103
104        solution
105    }
106
107    /// Restores the state of the problem to the given [`BPSolution`].
108    /// Returns `true` if any of the layout keys changed (i.e., layouts were added or removed).
109    /// Recreated layouts receive new keys; snapshot keys are not preserved for them.
110    pub fn restore(&mut self, solution: &BPSolution) -> bool {
111        let mut layout_keys_changed = false;
112        let mut layouts_to_remove = vec![];
113
114        //Check which layouts from the problem are also present in the solution.
115        //If a layout is present we might be able to do a (partial) restore instead of fully rebuilding everything.
116        for (lkey, layout) in &mut self.layouts {
117            match solution.layout_snapshots.get(lkey) {
118                Some(ls) => {
119                    self.layout_bins[lkey] = solution.layout_bins[lkey];
120                    // A saved layout may refer to a different bin.
121                    if layout.restore(ls).is_err() {
122                        *layout = Layout::from_snapshot(ls);
123                    }
124                }
125                _ => {
126                    layouts_to_remove.push(lkey);
127                }
128            }
129        }
130
131        //Remove all layouts that were not present in the solution
132        for lkey in layouts_to_remove {
133            layout_keys_changed = true;
134            self.layouts.remove(lkey);
135            self.layout_bins.remove(lkey);
136        }
137
138        //Create new layouts for all keys present in solution but not in problem
139        for (lkey, ls) in &solution.layout_snapshots {
140            if !self.layouts.contains_key(lkey) {
141                let new_key = self.layouts.insert(Layout::from_snapshot(ls));
142                self.layout_bins.insert(new_key, solution.layout_bins[lkey]);
143                layout_keys_changed = true;
144            }
145        }
146
147        //Restore the item demands and bin stocks
148        {
149            self.item_demand_qtys
150                .iter_mut()
151                .enumerate()
152                .for_each(|(idx, demand)| {
153                    *demand = self.instance.item_qty(idx);
154                });
155
156            self.bin_stock_qtys
157                .iter_mut()
158                .enumerate()
159                .for_each(|(id, stock)| {
160                    *stock = self.instance.bin_qty(id);
161                });
162
163            self.layouts.iter().for_each(|(key, layout)| {
164                self.bin_stock_qtys[self.layout_bins[key]] -= 1;
165                layout
166                    .placed_items
167                    .values()
168                    .for_each(|pi| self.item_demand_qtys[pi.item.idx] -= 1);
169            });
170        }
171
172        debug_assert!(problem_matches_solution(self, solution));
173        layout_keys_changed
174    }
175
176    #[must_use]
177    pub fn instance(&self) -> &BPInstance {
178        &self.instance
179    }
180
181    #[must_use]
182    pub fn layouts(&self) -> &SlotMap<LayKey, Layout> {
183        &self.layouts
184    }
185
186    #[must_use]
187    pub fn layout_bins(&self) -> &SecondaryMap<LayKey, usize> {
188        &self.layout_bins
189    }
190
191    #[must_use]
192    pub fn item_demand_qtys(&self) -> &[usize] {
193        &self.item_demand_qtys
194    }
195
196    #[must_use]
197    pub fn bin_stock_qtys(&self) -> &[usize] {
198        &self.bin_stock_qtys
199    }
200
201    #[must_use]
202    pub fn density(&self) -> f32 {
203        let total_bin_area = self
204            .layouts
205            .values()
206            .map(|l| l.container.area())
207            .sum::<f32>();
208
209        let total_item_area = self
210            .layouts
211            .values()
212            .map(Layout::placed_item_area)
213            .sum::<f32>();
214
215        total_item_area / total_bin_area
216    }
217
218    pub fn item_placed_qtys(&self) -> impl Iterator<Item = usize> {
219        self.item_demand_qtys
220            .iter()
221            .enumerate()
222            .map(|(i, demand)| self.instance.item_qty(i) - demand)
223    }
224
225    pub fn bin_used_qtys(&self) -> impl Iterator<Item = usize> {
226        self.bin_stock_qtys
227            .iter()
228            .enumerate()
229            .map(|(i, stock)| self.instance.bin_qty(i) - stock)
230    }
231
232    /// Returns the total cost of all bins used in the solution.
233    #[must_use]
234    pub fn bin_cost(&self) -> u64 {
235        self.bin_used_qtys()
236            .enumerate()
237            .map(|(id, qty)| self.instance.bins[id].cost * qty as u64)
238            .sum()
239    }
240
241    fn register_layout(&mut self, layout: Layout, bin_idx: usize) -> LayKey {
242        self.open_bin(bin_idx);
243        layout
244            .placed_items
245            .values()
246            .for_each(|pi| self.register_included_item(pi.item.idx));
247        let key = self.layouts.insert(layout);
248        self.layout_bins.insert(key, bin_idx);
249        key
250    }
251
252    fn deregister_layout(&mut self, key: LayKey) {
253        let layout = self.layouts.remove(key).expect("layout key not present");
254        let bin_idx = self
255            .layout_bins
256            .remove(key)
257            .expect("layout must have a source bin");
258        self.close_bin(bin_idx);
259        layout
260            .placed_items
261            .values()
262            .for_each(|pi| self.deregister_included_item(pi.item.idx));
263    }
264
265    fn register_included_item(&mut self, item_idx: usize) {
266        self.item_demand_qtys[item_idx] -= 1;
267    }
268
269    fn deregister_included_item(&mut self, item_idx: usize) {
270        self.item_demand_qtys[item_idx] += 1;
271    }
272
273    fn open_bin(&mut self, bin_id: usize) {
274        assert!(self.bin_stock_qtys[bin_id] > 0, "bin stock exhausted");
275        self.bin_stock_qtys[bin_id] -= 1;
276    }
277
278    fn close_bin(&mut self, bin_id: usize) {
279        self.bin_stock_qtys[bin_id] += 1;
280    }
281
282    #[must_use]
283    pub fn n_placed_items(&self) -> usize {
284        self.layouts.values().map(|l| l.placed_items.len()).sum()
285    }
286}
287
288#[derive(Clone, Debug, Copy)]
289/// Encapsulates all required information to place an [`Item`](crate::entities::Item) in a [`BPProblem`].
290pub struct BPPlacement {
291    /// Which [`Layout`] to place the item in
292    pub layout_id: BPLayoutType,
293    /// The index of the [`Item`](crate::entities::Item) to be placed
294    pub item_idx: usize,
295    /// The transformation to apply to the item when placing it
296    pub d_transf: DTransformation,
297}
298
299impl BPPlacement {
300    #[must_use]
301    pub fn from_placed_item(layout_id: BPLayoutType, placed_item: &PlacedItem) -> Self {
302        BPPlacement {
303            layout_id,
304            item_idx: placed_item.item.idx,
305            d_transf: placed_item.d_transf,
306        }
307    }
308}
309
310/// Enum to distinguish between already existing [`Layout`]s and new ones.
311#[derive(Debug, Clone, Copy, PartialEq, Eq)]
312pub enum BPLayoutType {
313    /// An existing layout, identified by its key
314    Open(LayKey),
315    /// A layout that does not yet exist, but can be created by 'opening' a new bin
316    Closed { bin_id: usize },
317}
jagua_rs/probs/bpp/entities/problem.rs

jagua_rs/probs/bpp/entities/
problem.rs
