lbf/opt/
lbf_bpp.rs

1use jagua_rs::Instant;
2
3use crate::ITEM_LIMIT;
4use crate::config::LBFConfig;
5use crate::opt::search::{item_placement_order, search};
6use jagua_rs::collision_detection::hazards::filter::{NoFilter, QualityZoneFilter};
7use jagua_rs::entities::Item;
8use jagua_rs::probs::bpp::entities::{
9    BPInstance, BPLayoutType, BPPlacement, BPProblem, BPSolution,
10};
11use log::{debug, info};
12use rand::Rng;
13use rand::prelude::SmallRng;
14use thousands::Separable;
15
16/// Left-Bottom-Fill (LBF) optimizer for Bin Packing problems.
17pub struct LBFOptimizerBP {
18    pub instance: BPInstance,
19    pub problem: BPProblem,
20    pub config: LBFConfig,
21    /// SmallRng is a fast, non-cryptographic PRNG <https://rust-random.github.io/book/guide-rngs.html>
22    pub rng: SmallRng,
23    pub sample_counter: usize,
24}
25
26impl LBFOptimizerBP {
27    pub fn new(instance: BPInstance, config: LBFConfig, rng: SmallRng) -> Self {
28        assert!(config.n_samples > 0);
29        let problem = BPProblem::new(instance.clone());
30        Self {
31            instance,
32            problem,
33            config,
34            rng,
35            sample_counter: 0,
36        }
37    }
38
39    pub fn solve(&mut self) -> BPSolution {
40        let start = Instant::now();
41
42        'outer: for item_idx in
43            item_placement_order(self.instance.items.iter().map(|(item, _)| item.as_ref()))
44        {
45            let item = self.instance.item(item_idx);
46            //place all items of this type
47            'inner: while self.problem.item_demand_qtys()[item_idx] > 0 {
48                //find a position and insert it
49                let placement = search_layouts(
50                    &self.problem,
51                    item,
52                    &self.config,
53                    &mut self.rng,
54                    &mut self.sample_counter,
55                );
56
57                match placement {
58                    Some(i_opt) => {
59                        let l_index = self.problem.place_item(i_opt);
60                        info!(
61                            "[LBF] placing item {}/{} with id {} at [{}] in Layout {:?}",
62                            self.problem.item_placed_qtys().sum::<usize>(),
63                            self.instance.total_item_qty(),
64                            i_opt.item_idx,
65                            i_opt.d_transf,
66                            l_index
67                        );
68                        #[allow(clippy::absurd_extreme_comparisons)]
69                        if self.problem.item_placed_qtys().sum::<usize>() >= ITEM_LIMIT {
70                            break 'outer;
71                        }
72                    }
73                    None => break 'inner, // items of this type do not fit anywhere
74                }
75            }
76        }
77
78        let solution = self.problem.save();
79
80        info!(
81            "[LBF] optimization finished in {:.3}ms ({} samples)",
82            start.elapsed().as_secs_f64() * 1000.0,
83            self.sample_counter.separate_with_commas()
84        );
85
86        info!(
87            "[LBF] solution contains {} items with a density of {:.3}%",
88            solution
89                .layout_snapshots()
90                .values()
91                .map(|ls| ls.placed_items().len())
92                .sum::<usize>(),
93            solution.density() * 100.0
94        );
95        solution
96    }
97}
98
99fn search_layouts(
100    problem: &BPProblem,
101    item: &Item,
102    config: &LBFConfig,
103    rng: &mut impl Rng,
104    sample_counter: &mut usize,
105) -> Option<BPPlacement> {
106    //search all existing layouts and closed bins with remaining stock
107    let open_layouts = problem.layouts().keys().map(BPLayoutType::Open);
108    let bins_with_stock =
109        problem
110            .bin_stock_qtys()
111            .iter()
112            .enumerate()
113            .filter_map(|(bin_id, qty)| match *qty > 0 {
114                true => Some(BPLayoutType::Closed { bin_id }),
115                false => None,
116            });
117
118    //sequential search until a valid placement is found
119    for layout_id in open_layouts.chain(bins_with_stock) {
120        debug!("searching in layout {layout_id:?}");
121        let cde = match layout_id {
122            BPLayoutType::Open(lkey) => problem.layouts()[lkey].cde(),
123            BPLayoutType::Closed { bin_id } => problem.instance().bins[bin_id]
124                .container
125                .base_cde()
126                .as_ref(),
127        };
128
129        let placement = match &item.min_quality() {
130            None => search(cde, item, config, rng, sample_counter, &NoFilter),
131            Some(min_quality) => {
132                let filter = QualityZoneFilter {
133                    min_quality: *min_quality,
134                };
135                search(cde, item, config, rng, sample_counter, &filter)
136            }
137        };
138
139        if let Some((d_transf, _)) = placement {
140            return Some(BPPlacement {
141                layout_id,
142                item_idx: item.idx(),
143                d_transf,
144            });
145        }
146    }
147    None
148}
lbf/opt/lbf_bpp.rs

lbf/opt/
lbf_bpp.rs
