problemreductions/models/misc/
capacity_assignment.rs

1//! Capacity Assignment problem implementation.
2//!
3//! Capacity Assignment asks for the minimum-cost assignment of capacity levels
4//! to communication links, subject to a delay budget constraint.
5
6use crate::registry::{CreateSpec, ProblemSchemaEntry};
7use crate::traits::Problem;
8use serde::{Deserialize, Serialize};
9
10inventory::submit! {
11    ProblemSchemaEntry {
12        name: "CapacityAssignment",
13        display_name: "Capacity Assignment",
14        aliases: &[],
15        dimensions: &[],
16        category: crate::registry::ProblemCategory::Misc,
17        module_path: module_path!(),
18        description: "Minimize total cost of capacity assignment subject to a delay budget",
19        fields: CapacityAssignmentCreateSpec::FIELDS,
20    }
21}
22
23/// Capacity Assignment optimization problem.
24///
25/// Each variable chooses one capacity index for one communication link.
26/// Costs are monotone non-decreasing and delays are monotone non-increasing
27/// with respect to the ordered capacity list. The objective is to minimize
28/// total cost subject to a delay budget constraint.
29#[derive(Debug, Clone, Serialize, Deserialize)]
30#[serde(try_from = "CapacityAssignmentCreateSpec")]
31pub struct CapacityAssignment {
32    capacities: Vec<i64>,
33    cost: Vec<Vec<i64>>,
34    delay: Vec<Vec<i64>>,
35    delay_budget: i64,
36}
37
38#[derive(Debug, Deserialize, crate::CreateSpec)]
39struct CapacityAssignmentCreateSpec {
40    #[create(codec = "comma-separated")]
41    capacities: Vec<i64>,
42    #[create(codec = "semicolon-separated")]
43    cost: Vec<Vec<i64>>,
44    #[create(codec = "semicolon-separated")]
45    delay: Vec<Vec<i64>>,
46    delay_budget: i64,
47}
48
49impl TryFrom<CapacityAssignmentCreateSpec> for CapacityAssignment {
50    type Error = crate::registry::ConstructionError;
51    fn try_from(spec: CapacityAssignmentCreateSpec) -> Result<Self, Self::Error> {
52        Self::try_new(spec.capacities, spec.cost, spec.delay, spec.delay_budget)
53    }
54}
55
56impl CapacityAssignment {
57    /// Create a new Capacity Assignment instance.
58    pub fn new(
59        capacities: Vec<i64>,
60        cost: Vec<Vec<i64>>,
61        delay: Vec<Vec<i64>>,
62        delay_budget: i64,
63    ) -> Self {
64        Self::try_new(capacities, cost, delay, delay_budget)
65            .unwrap_or_else(|error| panic!("{error}"))
66    }
67
68    fn try_new(
69        capacities: Vec<i64>,
70        cost: Vec<Vec<i64>>,
71        delay: Vec<Vec<i64>>,
72        delay_budget: i64,
73    ) -> Result<Self, crate::registry::ConstructionError> {
74        if capacities.is_empty() {
75            return Err("capacities must be non-empty".into());
76        }
77        if capacities.iter().any(|&capacity| capacity <= 0) {
78            return Err("capacities must be positive".into());
79        }
80        if capacities.windows(2).any(|w| w[0] >= w[1]) {
81            return Err("capacities must be strictly increasing".into());
82        }
83        if cost.len() != delay.len() {
84            return Err("cost and delay must have the same number of links".into());
85        }
86
87        let num_capacities = capacities.len();
88        for (link, row) in cost.iter().enumerate() {
89            if row.len() != num_capacities {
90                return Err(crate::registry::ConstructionError::length_mismatch(
91                    &format!("cost row {link}"),
92                    row.len(),
93                    num_capacities,
94                ));
95            }
96            if row.windows(2).any(|w| w[0] > w[1]) {
97                return Err(format!("cost row {link} must be non-decreasing").into());
98            }
99        }
100        for (link, row) in delay.iter().enumerate() {
101            if row.len() != num_capacities {
102                return Err(crate::registry::ConstructionError::length_mismatch(
103                    &format!("delay row {link}"),
104                    row.len(),
105                    num_capacities,
106                ));
107            }
108            if row.windows(2).any(|w| w[0] < w[1]) {
109                return Err(format!("delay row {link} must be non-increasing").into());
110            }
111        }
112
113        Ok(Self {
114            capacities,
115            cost,
116            delay,
117            delay_budget,
118        })
119    }
120
121    /// Smallest h >= 1 bounding every delay and the delay budget in magnitude strictly by 2^h.
122    pub fn max_delay_bits(&self) -> u64 {
123        crate::types::max_numeric_magnitude_bits(
124            self.delay
125                .iter()
126                .flatten()
127                .copied()
128                .chain(std::iter::once(self.delay_budget)),
129        )
130    }
131
132    /// Number of communication links.
133    pub fn num_links(&self) -> usize {
134        self.cost.len()
135    }
136
137    /// Number of discrete capacity choices per link.
138    pub fn num_capacities(&self) -> usize {
139        self.capacities.len()
140    }
141
142    /// Ordered capacity levels.
143    pub fn capacities(&self) -> &[i64] {
144        &self.capacities
145    }
146
147    /// Cost matrix indexed by link, then capacity.
148    pub fn cost(&self) -> &[Vec<i64>] {
149        &self.cost
150    }
151
152    /// Delay matrix indexed by link, then capacity.
153    pub fn delay(&self) -> &[Vec<i64>] {
154        &self.delay
155    }
156
157    /// Total delay budget.
158    pub fn delay_budget(&self) -> i64 {
159        self.delay_budget
160    }
161
162    fn total_cost_and_delay(
163        &self,
164        config: &[usize],
165    ) -> Result<Option<(i64, i64)>, crate::traits::EvaluationError> {
166        if config.len() != self.num_links() {
167            return Ok(None);
168        }
169
170        let num_capacities = self.num_capacities();
171        let mut total_cost = 0i64;
172        let mut total_delay = 0i64;
173
174        for (link, &choice) in config.iter().enumerate() {
175            if choice >= num_capacities {
176                return Ok(None);
177            }
178            total_cost = total_cost
179                .checked_add(self.cost[link][choice])
180                .ok_or_else(|| {
181                    crate::traits::EvaluationError::IntegerOverflow(
182                        "summing capacity-assignment costs".to_string(),
183                    )
184                })?;
185            total_delay = total_delay
186                .checked_add(self.delay[link][choice])
187                .ok_or_else(|| {
188                    crate::traits::EvaluationError::IntegerOverflow(
189                        "summing capacity-assignment delays".to_string(),
190                    )
191                })?;
192        }
193
194        Ok(Some((total_cost, total_delay)))
195    }
196}
197
198impl Problem for CapacityAssignment {
199    const NAME: &'static str = "CapacityAssignment";
200    type Solution = Vec<usize>;
201    type Value = crate::types::Min<i64>;
202
203    crate::problem_parameters![
204        ("max_delay_bits", max_delay_bits),
205        ("num_capacities", num_capacities),
206        ("num_links", num_links),
207    ];
208
209    fn evaluate(
210        &self,
211        config: &Self::Solution,
212    ) -> Result<crate::types::Min<i64>, crate::traits::EvaluationError> {
213        if config.len() != self.num_links() {
214            return Err(crate::traits::EvaluationError::InvalidConfiguration(
215                "capacity-choice length does not match the links".into(),
216            ));
217        }
218        if config.iter().any(|&choice| choice >= self.num_capacities()) {
219            return Err(crate::traits::EvaluationError::InvalidConfiguration(
220                "capacity assignment contains an out-of-range choice".into(),
221            ));
222        }
223        Ok({
224            let Some((total_cost, total_delay)) = self.total_cost_and_delay(config)? else {
225                return Ok(crate::types::Min(None));
226            };
227            if total_delay <= self.delay_budget {
228                crate::types::Min(Some(total_cost))
229            } else {
230                crate::types::Min(None)
231            }
232        })
233    }
234
235    fn variant() -> Vec<(&'static str, &'static str)> {
236        crate::variant_params![]
237    }
238}
239
240impl crate::solvers::BruteForceProblem for CapacityAssignment {
241    fn dimensions(&self) -> Vec<usize> {
242        vec![self.num_capacities(); self.num_links()]
243    }
244}
245
246crate::declare_variants! {
247    default CapacityAssignment => "num_capacities ^ num_links" create CapacityAssignmentCreateSpec,
248}
249
250crate::register_brute_force! {
251    CapacityAssignment,
252}
253
254#[cfg(feature = "example-db")]
255pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
256    vec![crate::example_db::specs::ModelExampleSpec {
257        id: "capacity_assignment",
258        instance: Box::new(CapacityAssignment::new(
259            vec![1, 2, 3],
260            vec![vec![1, 3, 6], vec![2, 4, 7], vec![1, 2, 5]],
261            vec![vec![8, 4, 1], vec![7, 3, 1], vec![6, 3, 1]],
262            12,
263        )),
264        optimal_config: serde_json::json!(vec![1, 1, 1]),
265        optimal_value: serde_json::json!(9),
266    }]
267}
268
269#[cfg(test)]
270#[path = "../../unit_tests/models/misc/capacity_assignment.rs"]
271mod tests;
problemreductions/models/misc/capacity_assignment.rs

problemreductions/models/misc/
capacity_assignment.rs
