lbf/opt/
lbf_spp.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;
8use jagua_rs::probs::spp::entities::{SPInstance, SPPlacement, SPProblem, SPSolution};
9use log::info;
10use rand::prelude::SmallRng;
11use thousands::Separable;
12
13/// Left-Bottom-Fill (LBF) optimizer for Strip Packing problems.
14pub struct LBFOptimizerSP {
15    pub instance: SPInstance,
16    pub problem: SPProblem,
17    pub config: LBFConfig,
18    /// SmallRng is a fast, non-cryptographic PRNG <https://rust-random.github.io/book/guide-rngs.html>
19    pub rng: SmallRng,
20    pub sample_counter: usize,
21}
22
23impl LBFOptimizerSP {
24    pub fn new(instance: SPInstance, config: LBFConfig, rng: SmallRng) -> Self {
25        assert!(config.n_samples > 0);
26        let problem = SPProblem::new(instance.clone());
27        Self {
28            instance,
29            problem,
30            config,
31            rng,
32            sample_counter: 0,
33        }
34    }
35
36    pub fn solve(&mut self) -> SPSolution {
37        let start = Instant::now();
38
39        'outer: for item_id in item_placement_order(&self.instance) {
40            let item = self.instance.item(item_id);
41            //place all items of this type
42            while self.problem.item_demand_qtys[item_id] > 0 {
43                let placement = match &item.hazard_filter {
44                    None => search(
45                        self.problem.layout.cde(),
46                        item,
47                        &self.config,
48                        &mut self.rng,
49                        &mut self.sample_counter,
50                        &NoHazardFilter,
51                    ),
52                    Some(hf) => search(
53                        self.problem.layout.cde(),
54                        item,
55                        &self.config,
56                        &mut self.rng,
57                        &mut self.sample_counter,
58                        hf,
59                    ),
60                };
61
62                match placement {
63                    Some((d_transf, _)) => {
64                        self.problem.place_item(SPPlacement {
65                            item_id: item.id,
66                            d_transf,
67                        });
68                        info!(
69                            "[LBF] placing item {}/{} with id {} at [{}]",
70                            self.problem.layout.placed_items().len(),
71                            self.instance.total_item_qty(),
72                            item.id,
73                            d_transf,
74                        );
75                        #[allow(clippy::absurd_extreme_comparisons)]
76                        if self.problem.layout.placed_items().len() >= ITEM_LIMIT {
77                            break 'outer;
78                        }
79                    }
80                    None => {
81                        // item does not fit anywhere, increase the strip width
82                        self.problem
83                            .change_strip_width(self.problem.strip.width * 1.1);
84                        info!(
85                            "[LBF] no placement found, extended strip by 10% to {:.3}",
86                            self.problem.strip.width
87                        );
88                    }
89                }
90            }
91        }
92
93        self.problem.fit_strip();
94        info!(
95            "[LBF] fitted strip width to {:.3}",
96            self.problem.strip.width
97        );
98
99        let solution = self.problem.save();
100
101        info!(
102            "[LBF] optimization finished in {:.3}ms ({} samples)",
103            start.elapsed().as_secs_f64() * 1000.0,
104            self.sample_counter.separate_with_commas()
105        );
106
107        info!(
108            "[LBF] solution contains {} items with a density of {:.3}%",
109            solution.layout_snapshot.placed_items.len(),
110            solution.density(&self.instance) * 100.0
111        );
112        solution
113    }
114}
lbf/opt/lbf_spp.rs

lbf/opt/
lbf_spp.rs
