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/// Modifiable counterpart of [`BPInstance`].
18/// Items can be placed and removed, bins can be opened and closed.
19#[derive(Clone)]
20pub struct BPProblem {
21    pub instance: BPInstance,
22    pub layouts: SlotMap<LayKey, Layout>,
23    pub item_demand_qtys: Vec<usize>,
24    pub bin_stock_qtys: Vec<usize>,
25}
26
27impl BPProblem {
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    pub fn remove_layout(&mut self, key: LayKey) {
41        self.deregister_layout(key);
42    }
43
44    /// Places an item according to the given `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(
67        &mut self,
68        lkey: LayKey,
69        pik: PItemKey,
70        commit_instant: bool,
71    ) -> BPPlacement {
72        let pi = self.layouts[lkey].remove_item(pik, commit_instant);
73        self.deregister_included_item(pi.item_id);
74        if self.layouts[lkey].is_empty() {
75            //if layout is empty, close it
76            let bin_id = self.layouts[lkey].container.id;
77            self.deregister_layout(lkey);
78            BPPlacement::from_placed_item(BPLayoutType::Closed { bin_id }, &pi)
79        } else {
80            BPPlacement::from_placed_item(BPLayoutType::Open(lkey), &pi)
81        }
82    }
83
84    /// Creates a snapshot of the current state of the problem as a [`BPSolution`].
85    pub fn save(&mut self) -> BPSolution {
86        let layout_snapshots = self
87            .layouts
88            .iter_mut()
89            .map(|(lkey, l)| (lkey, l.save()))
90            .collect();
91
92        let solution = BPSolution {
93            layout_snapshots,
94            time_stamp: Instant::now(),
95        };
96
97        debug_assert!(problem_matches_solution(self, &solution));
98
99        solution
100    }
101
102    /// Restores the state of the problem to the given [`BPSolution`].
103    pub fn restore(&mut self, solution: &BPSolution) {
104        let mut layouts_to_remove = vec![];
105
106        //Check which layouts from the problem are also present in the solution.
107        //If a layout is present we might be able to do a (partial) restore instead of fully rebuilding everything.
108        for (lkey, layout) in self.layouts.iter_mut() {
109            match solution.layout_snapshots.get(lkey) {
110                Some(ls) => match layout.container.id == ls.container.id {
111                    true => layout.restore(ls),
112                    false => layouts_to_remove.push(lkey),
113                },
114                None => {
115                    layouts_to_remove.push(lkey);
116                }
117            }
118        }
119
120        //Remove all layouts that were not present in the solution (or have a different bin)
121        for lkey in layouts_to_remove {
122            self.layouts.remove(lkey);
123        }
124
125        //Create new layouts for all keys present in solution but not in problem
126        for (lkey, ls) in solution.layout_snapshots.iter() {
127            if !self.layouts.contains_key(lkey) {
128                self.layouts.insert(Layout::from_snapshot(ls));
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    }
159
160    pub fn density(&self) -> f32 {
161        let total_bin_area = self
162            .layouts
163            .values()
164            .map(|l| l.container.area())
165            .sum::<f32>();
166
167        let total_item_area = self
168            .layouts
169            .values()
170            .map(|l| l.placed_item_area(&self.instance))
171            .sum::<f32>();
172
173        total_item_area / total_bin_area
174    }
175
176    pub fn item_placed_qtys(&self) -> impl Iterator<Item = usize> {
177        self.item_demand_qtys
178            .iter()
179            .enumerate()
180            .map(|(i, demand)| self.instance.item_qty(i) - demand)
181    }
182
183    pub fn bin_used_qtys(&self) -> impl Iterator<Item = usize> {
184        self.bin_stock_qtys
185            .iter()
186            .enumerate()
187            .map(|(i, stock)| self.instance.bin_qty(i) - stock)
188    }
189
190    /// Returns the total cost of all bins used in the solution.
191    pub fn bin_cost(&self) -> u64 {
192        self.bin_used_qtys()
193            .enumerate()
194            .map(|(id, qty)| self.instance.bins[id].cost * qty as u64)
195            .sum()
196    }
197
198    fn register_layout(&mut self, layout: Layout) -> LayKey {
199        self.open_bin(layout.container.id);
200        layout
201            .placed_items()
202            .values()
203            .for_each(|pi| self.register_included_item(pi.item_id));
204        self.layouts.insert(layout)
205    }
206
207    fn deregister_layout(&mut self, key: LayKey) {
208        let layout = self.layouts.remove(key).expect("layout key not present");
209        self.close_bin(layout.container.id);
210        layout
211            .placed_items()
212            .values()
213            .for_each(|pi| self.deregister_included_item(pi.item_id));
214    }
215
216    fn register_included_item(&mut self, item_id: usize) {
217        self.item_demand_qtys[item_id] -= 1;
218    }
219
220    fn deregister_included_item(&mut self, item_id: usize) {
221        self.item_demand_qtys[item_id] += 1;
222    }
223
224    fn open_bin(&mut self, bin_id: usize) {
225        self.bin_stock_qtys[bin_id] -= 1
226    }
227
228    fn close_bin(&mut self, bin_id: usize) {
229        self.bin_stock_qtys[bin_id] += 1
230    }
231}
232
233#[derive(Clone, Debug, Copy)]
234/// Encapsulates all required information to place an [`Item`](crate::entities::Item) in a [`BPProblem`].
235pub struct BPPlacement {
236    /// Which layout to place the item in
237    pub layout_id: BPLayoutType,
238    /// The id of the item to be placed
239    pub item_id: usize,
240    /// The decomposition of the transformation
241    pub d_transf: DTransformation,
242}
243
244impl BPPlacement {
245    pub fn from_placed_item(layout_id: BPLayoutType, placed_item: &PlacedItem) -> Self {
246        BPPlacement {
247            layout_id,
248            item_id: placed_item.item_id,
249            d_transf: placed_item.d_transf,
250        }
251    }
252}
253
254/// Enum to distinguish between both existing [`Layout`]s, and potentially new ones.
255#[derive(Debug, Clone, Copy, PartialEq, Eq)]
256pub enum BPLayoutType {
257    /// An existing layout
258    Open(LayKey),
259    /// A layout that does not yet exist, but can be created
260    Closed { bin_id: usize },
261}
jagua_rs/probs/bpp/entities/problem.rs

jagua_rs/probs/bpp/entities/
problem.rs
