lbf/opt/
lbf_spp.rs

1use anyhow::Result;
2use jagua_rs::Instant;
3
4use crate::ITEM_LIMIT;
5use crate::config::LBFConfig;
6use crate::opt::search::{item_placement_order, search};
7use crate::util::assertions::strip_width_is_in_check;
8use jagua_rs::collision_detection::hazards::filter::{NoFilter, QualityZoneFilter};
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) -> Result<Self> {
26        assert!(config.n_samples > 0);
27        let problem = SPProblem::new(instance.clone())?;
28        Ok(Self {
29            instance,
30            problem,
31            config,
32            rng,
33            sample_counter: 0,
34        })
35    }
36
37    pub fn solve(&mut self) -> Result<SPSolution> {
38        let start = Instant::now();
39
40        'outer: for item_idx in
41            item_placement_order(self.instance.items.iter().map(|(item, _)| item.as_ref()))
42        {
43            let item = self.instance.item(item_idx);
44            //place all items of this type
45            while self.problem.item_demand_qtys()[item_idx] > 0 {
46                let cde = self.problem.layout().cde();
47                let placement = match &item.min_quality() {
48                    None => search(
49                        cde,
50                        item,
51                        &self.config,
52                        &mut self.rng,
53                        &mut self.sample_counter,
54                        &NoFilter,
55                    ),
56                    Some(min_quality) => {
57                        let filter = QualityZoneFilter {
58                            min_quality: *min_quality,
59                        };
60                        search(
61                            cde,
62                            item,
63                            &self.config,
64                            &mut self.rng,
65                            &mut self.sample_counter,
66                            &filter,
67                        )
68                    }
69                };
70
71                match placement {
72                    Some((d_transf, _)) => {
73                        self.problem.place_item(SPPlacement {
74                            item_idx: item.idx(),
75                            d_transf,
76                        });
77                        info!(
78                            "[LBF] placing item {}/{} with id {} at [{}]",
79                            self.problem.layout().placed_items().len(),
80                            self.instance.total_item_qty(),
81                            item.idx(),
82                            d_transf,
83                        );
84                        #[allow(clippy::absurd_extreme_comparisons)]
85                        if self.problem.layout().placed_items().len() >= ITEM_LIMIT {
86                            break 'outer;
87                        }
88                    }
89                    None => {
90                        // item does not fit anywhere, increase the strip width
91                        self.problem
92                            .change_strip_width(self.problem.strip().width * 1.1)?;
93                        info!(
94                            "[LBF] no placement found, extended strip by 10% to {:.3}",
95                            self.problem.strip().width
96                        );
97                        assert!(
98                            strip_width_is_in_check(&self.problem),
99                            " strip width is running away, check if all items fit in the height of the strip"
100                        )
101                    }
102                }
103            }
104        }
105
106        self.problem.fit_strip()?;
107        info!(
108            "[LBF] fitted strip width to {:.3}",
109            self.problem.strip().width
110        );
111
112        let solution = self.problem.save();
113
114        info!(
115            "[LBF] optimization finished in {:.3}ms ({} samples)",
116            start.elapsed().as_secs_f64() * 1000.0,
117            self.sample_counter.separate_with_commas()
118        );
119
120        info!(
121            "[LBF] solution contains {} items with a density of {:.3}%",
122            solution.layout_snapshot().placed_items().len(),
123            solution.density() * 100.0
124        );
125        Ok(solution)
126    }
127}
lbf/opt/lbf_spp.rs

lbf/opt/
lbf_spp.rs
