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

problemreductions/models/misc/
capacity_assignment.rs
