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    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, placement: BPPlacement) -> (LayKey, PItemKey) {
46        let lkey = match placement.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
56        let layout = &mut self.layouts[lkey];
57        let item = self.instance.item(placement.item_id);
58        let pik = layout.place_item(item, placement.d_transf);
59
60        self.register_included_item(placement.item_id);
61
62        (lkey, pik)
63    }
64
65    /// Removes an item from a layout. If the layout is empty, it will be closed.
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    /// Returns `true` if any of the layout keys changed (i.e., layouts were added or removed).
99    pub fn restore(&mut self, solution: &BPSolution) -> bool {
100        let mut layout_keys_changed = false;
101        let mut layouts_to_remove = vec![];
102
103        //Check which layouts from the problem are also present in the solution.
104        //If a layout is present we might be able to do a (partial) restore instead of fully rebuilding everything.
105        for (lkey, layout) in self.layouts.iter_mut() {
106            match solution.layout_snapshots.get(lkey) {
107                Some(ls) => match layout.container.id == ls.container.id {
108                    true => layout.restore(ls),
109                    false => layouts_to_remove.push(lkey),
110                },
111                None => {
112                    layouts_to_remove.push(lkey);
113                }
114            }
115        }
116
117        //Remove all layouts that were not present in the solution (or have a different bin)
118        for lkey in layouts_to_remove {
119            layout_keys_changed = true;
120            self.layouts.remove(lkey);
121        }
122
123        //Create new layouts for all keys present in solution but not in problem
124        for (lkey, ls) in solution.layout_snapshots.iter() {
125            if !self.layouts.contains_key(lkey) {
126                self.layouts.insert(Layout::from_snapshot(ls));
127                layout_keys_changed = true;
128            }
129        }
130
131        //Restore the item demands and bin stocks
132        {
133            self.item_demand_qtys
134                .iter_mut()
135                .enumerate()
136                .for_each(|(id, demand)| {
137                    *demand = self.instance.item_qty(id);
138                });
139
140            self.bin_stock_qtys
141                .iter_mut()
142                .enumerate()
143                .for_each(|(id, stock)| {
144                    *stock = self.instance.bin_qty(id);
145                });
146
147            self.layouts.values().for_each(|layout| {
148                self.bin_stock_qtys[layout.container.id] -= 1;
149                layout
150                    .placed_items
151                    .values()
152                    .for_each(|pi| self.item_demand_qtys[pi.item_id] -= 1);
153            });
154        }
155
156        debug_assert!(problem_matches_solution(self, solution));
157        layout_keys_changed
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`](crate::entities::Item) to be placed
239    pub item_id: usize,
240    /// The transformation to apply to the item when placing it
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 already existing [`Layout`]s and new ones.
255#[derive(Debug, Clone, Copy, PartialEq, Eq)]
256pub enum BPLayoutType {
257    /// An existing layout, identified by its key
258    Open(LayKey),
259    /// A layout that does not yet exist, but can be created by 'opening' a new bin
260    Closed { bin_id: usize },
261}
jagua_rs/probs/bpp/entities/problem.rs

jagua_rs/probs/bpp/entities/
problem.rs
