jagua_rs/probs/bpp/entities/
problem.rs

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

jagua_rs/probs/bpp/entities/
problem.rs
