problemreductions/models/misc/
dynamic_storage_allocation.rs

1//! Dynamic Storage Allocation problem implementation.
2//!
3//! Given items each with arrival time, departure time, and size, plus a
4//! memory size D, determine whether each item can be assigned a starting
5//! address such that every item fits within [0, D-1] and no two
6//! time-overlapping items share memory addresses.
7
8use crate::registry::{FieldInfo, ProblemSchemaEntry};
9use crate::traits::Problem;
10use crate::types::Or;
11use serde::de::Error as _;
12use serde::{Deserialize, Deserializer, Serialize};
13
14inventory::submit! {
15    ProblemSchemaEntry {
16        name: "DynamicStorageAllocation",
17        display_name: "Dynamic Storage Allocation",
18        aliases: &[],
19        dimensions: &[],
20        category: crate::registry::ProblemCategory::Misc,
21        module_path: module_path!(),
22        description: "Assign starting addresses for items with time intervals and sizes within bounded memory",
23        fields: &[
24            FieldInfo { name: "items", type_name: "Vec<(usize, usize, usize)>", description: "Items as (arrival, departure, size) tuples" },
25            FieldInfo { name: "memory_size", type_name: "usize", description: "Total memory size D" },
26        ],
27    }
28}
29
30/// Dynamic Storage Allocation problem.
31///
32/// Each item `a` has arrival time `r(a)`, departure time `d(a)`, and size `s(a)`.
33/// The goal is to find a starting address `σ(a) ∈ {0, ..., D - s(a)}` for each item
34/// such that time-overlapping items do not overlap in memory.
35#[derive(Debug, Clone, Serialize)]
36pub struct DynamicStorageAllocation {
37    items: Vec<(usize, usize, usize)>,
38    memory_size: usize,
39}
40
41impl DynamicStorageAllocation {
42    fn validate_inputs(
43        items: &[(usize, usize, usize)],
44        memory_size: usize,
45    ) -> Result<(), crate::registry::ConstructionError> {
46        if items.is_empty() {
47            return Err("DynamicStorageAllocation requires at least one item"
48                .to_string()
49                .into());
50        }
51        if memory_size == 0 {
52            return Err("DynamicStorageAllocation requires a positive memory_size"
53                .to_string()
54                .into());
55        }
56        for (i, &(arrival, departure, size)) in items.iter().enumerate() {
57            if size == 0 {
58                return Err(format!("Item {i} has zero size; all sizes must be >= 1").into());
59            }
60            if departure <= arrival {
61                return Err(format!(
62                    "Item {i} has departure ({departure}) <= arrival ({arrival}); departure must be strictly greater"
63                ).into());
64            }
65            if size > memory_size {
66                return Err(format!(
67                    "Item {i} has size ({size}) > memory_size ({memory_size}); every item must fit in memory"
68                ).into());
69            }
70        }
71        Ok(())
72    }
73
74    /// Try to create a new `DynamicStorageAllocation` instance.
75    pub fn try_new(
76        items: Vec<(usize, usize, usize)>,
77        memory_size: usize,
78    ) -> Result<Self, crate::registry::ConstructionError> {
79        Self::validate_inputs(&items, memory_size)?;
80        Ok(Self { items, memory_size })
81    }
82
83    /// Create a new `DynamicStorageAllocation` instance.
84    ///
85    /// # Panics
86    ///
87    /// Panics if any item has zero size, departure <= arrival, or size > memory_size.
88    pub fn new(items: Vec<(usize, usize, usize)>, memory_size: usize) -> Self {
89        Self::try_new(items, memory_size).unwrap_or_else(|message| panic!("{message}"))
90    }
91
92    /// The items as `(arrival, departure, size)` tuples.
93    pub fn items(&self) -> &[(usize, usize, usize)] {
94        &self.items
95    }
96
97    /// The total memory size D.
98    pub fn memory_size(&self) -> usize {
99        self.memory_size
100    }
101
102    /// The number of items.
103    pub fn num_items(&self) -> usize {
104        self.items.len()
105    }
106}
107
108#[derive(Deserialize)]
109struct DynamicStorageAllocationData {
110    items: Vec<(usize, usize, usize)>,
111    memory_size: usize,
112}
113
114impl<'de> Deserialize<'de> for DynamicStorageAllocation {
115    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
116    where
117        D: Deserializer<'de>,
118    {
119        let data = DynamicStorageAllocationData::deserialize(deserializer)?;
120        Self::try_new(data.items, data.memory_size).map_err(D::Error::custom)
121    }
122}
123
124impl Problem for DynamicStorageAllocation {
125    const NAME: &'static str = "DynamicStorageAllocation";
126    type Solution = Vec<usize>;
127    type Value = Or;
128
129    crate::problem_parameters![("memory_size", memory_size), ("num_items", num_items),];
130
131    fn variant() -> Vec<(&'static str, &'static str)> {
132        crate::variant_params![]
133    }
134
135    fn evaluate(&self, config: &Self::Solution) -> Result<Or, crate::traits::EvaluationError> {
136        Ok({
137            Or({
138                if config.len() != self.num_items() {
139                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
140                        "allocation length does not match the number of items".into(),
141                    ));
142                }
143
144                // Check each item fits within memory
145                for (i, &(_, _, size)) in self.items.iter().enumerate() {
146                    let start = config[i];
147                    if start + size > self.memory_size {
148                        return Ok(Or(false));
149                    }
150                }
151
152                // Check all pairs of time-overlapping items for memory non-overlap
153                for (i, &(r_i, d_i, s_i)) in self.items.iter().enumerate() {
154                    let sigma_i = config[i];
155                    for (j, &(r_j, d_j, s_j)) in self.items.iter().enumerate().skip(i + 1) {
156                        // Time overlap: r_i < d_j AND r_j < d_i
157                        if r_i < d_j && r_j < d_i {
158                            let sigma_j = config[j];
159                            // Memory overlap: NOT (sigma_i + s_i <= sigma_j OR sigma_j + s_j <= sigma_i)
160                            let no_memory_overlap =
161                                sigma_i + s_i <= sigma_j || sigma_j + s_j <= sigma_i;
162                            if !no_memory_overlap {
163                                return Ok(Or(false));
164                            }
165                        }
166                    }
167                }
168                true
169            })
170        })
171    }
172}
173
174impl crate::solvers::BruteForceProblem for DynamicStorageAllocation {
175    fn dimensions(&self) -> Vec<usize> {
176        self.items
177            .iter()
178            .map(|&(_, _, s)| self.memory_size - s + 1)
179            .collect()
180    }
181}
182
183crate::declare_variants! {
184    default DynamicStorageAllocation => "(memory_size + 1)^num_items",
185}
186
187crate::register_brute_force! {
188    DynamicStorageAllocation,
189}
190
191#[cfg(feature = "example-db")]
192pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
193    vec![crate::example_db::specs::ModelExampleSpec {
194        id: "dynamic_storage_allocation",
195        instance: Box::new(DynamicStorageAllocation::new(
196            vec![(0, 3, 2), (0, 2, 3), (1, 4, 1), (2, 5, 3), (3, 5, 2)],
197            6,
198        )),
199        optimal_config: serde_json::json!(vec![0, 2, 5, 2, 0]),
200        optimal_value: serde_json::json!(true),
201    }]
202}
203
204#[cfg(test)]
205#[path = "../../unit_tests/models/misc/dynamic_storage_allocation.rs"]
206mod tests;
problemreductions/models/misc/dynamic_storage_allocation.rs

problemreductions/models/misc/
dynamic_storage_allocation.rs
