lbf/opt/
lbf_bpp.rs

1use std::time::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::NoHazardFilter;
7use jagua_rs::entities::{Instance, 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_id in item_placement_order(&self.instance) {
43            let item = self.instance.item(item_id);
44            //place all items of this type
45            'inner: while self.problem.item_demand_qtys[item_id] > 0 {
46                //find a position and insert it
47                let placement = search_layouts(
48                    &self.problem,
49                    item,
50                    &self.config,
51                    &mut self.rng,
52                    &mut self.sample_counter,
53                );
54
55                match placement {
56                    Some(i_opt) => {
57                        let l_index = self.problem.place_item(i_opt);
58                        info!(
59                            "[LBF] placing item {}/{} with id {} at [{}] in Layout {:?}",
60                            self.problem.item_placed_qtys().sum::<usize>(),
61                            self.instance.total_item_qty(),
62                            i_opt.item_id,
63                            i_opt.d_transf,
64                            l_index
65                        );
66                        #[allow(clippy::absurd_extreme_comparisons)]
67                        if self.problem.item_placed_qtys().sum::<usize>() >= ITEM_LIMIT {
68                            break 'outer;
69                        }
70                    }
71                    None => break 'inner, // items of this type do not fit anywhere
72                }
73            }
74        }
75
76        let solution = self.problem.save();
77
78        info!(
79            "[LBF] optimization finished in {:.3}ms ({} samples)",
80            start.elapsed().as_secs_f64() * 1000.0,
81            self.sample_counter.separate_with_commas()
82        );
83
84        info!(
85            "[LBF] solution contains {} items with a density of {:.3}%",
86            solution
87                .layout_snapshots
88                .values()
89                .map(|ls| ls.placed_items.len())
90                .sum::<usize>(),
91            solution.density(&self.instance) * 100.0
92        );
93        solution
94    }
95}
96
97fn search_layouts(
98    problem: &BPProblem,
99    item: &Item,
100    config: &LBFConfig,
101    rng: &mut impl Rng,
102    sample_counter: &mut usize,
103) -> Option<BPPlacement> {
104    //search all existing layouts and closed bins with remaining stock
105    let open_layouts = problem.layouts.keys().map(BPLayoutType::Open);
106    let bins_with_stock = problem
107        .bin_stock_qtys
108        .iter()
109        .enumerate()
110        .filter_map(|(bin_id, qty)| match *qty > 0 {
111            true => Some(BPLayoutType::Closed { bin_id }),
112            false => None,
113        });
114
115    //sequential search until a valid placement is found
116    for layout_id in open_layouts.chain(bins_with_stock) {
117        debug!("searching in layout {layout_id:?}");
118        let cde = match layout_id {
119            BPLayoutType::Open(lkey) => problem.layouts[lkey].cde(),
120            BPLayoutType::Closed { bin_id } => problem.instance.container(bin_id).base_cde.as_ref(),
121        };
122
123        let placement = match &item.hazard_filter {
124            None => search(cde, item, config, rng, sample_counter, &NoHazardFilter),
125            Some(hf) => search(cde, item, config, rng, sample_counter, hf),
126        };
127
128        if let Some((d_transf, _)) = placement {
129            return Some(BPPlacement {
130                layout_id,
131                item_id: item.id,
132                d_transf,
133            });
134        }
135    }
136    None
137}
lbf/opt/lbf_bpp.rs

lbf/opt/
lbf_bpp.rs
