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

lbf/opt/
lbf_spp.rs
