jagua_rs/probs/bpp/entities/
problem.rs

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

jagua_rs/probs/bpp/entities/
problem.rs
