problemreductions/models/misc/
sequencing_to_minimize_maximum_cumulative_cost.rs

1//! Sequencing to Minimize Maximum Cumulative Cost problem implementation.
2//!
3//! Given a set of tasks with integer costs and precedence constraints, find
4//! a valid one-machine schedule that minimizes the maximum cumulative cost
5//! over all prefixes.
6
7use crate::registry::{CreateSpec, ProblemSchemaEntry};
8use crate::traits::Problem;
9use serde::de::Error as _;
10use serde::{Deserialize, Serialize};
11
12inventory::submit! {
13    ProblemSchemaEntry {
14        name: "SequencingToMinimizeMaximumCumulativeCost",
15        display_name: "Sequencing to Minimize Maximum Cumulative Cost",
16        aliases: &[],
17        dimensions: &[],
18        category: crate::registry::ProblemCategory::Misc,
19        module_path: module_path!(),
20        description: "Schedule tasks with precedence constraints to minimize the maximum cumulative cost prefix",
21        fields: SequencingCumulativeCostCreateSpec::FIELDS,
22    }
23}
24
25/// Sequencing to Minimize Maximum Cumulative Cost.
26///
27/// Given a set of tasks `T`, a cost `c(t) in Z` for each task, and a partial
28/// order on the tasks, find a schedule that respects the precedences and
29/// minimizes the maximum cumulative cost over all prefixes.
30///
31/// # Representation
32///
33/// Configurations use Lehmer-code dimensions `[n, n-1, ..., 1]` to encode a
34/// permutation of the task indices.
35#[derive(Debug, Clone, Serialize)]
36pub struct SequencingToMinimizeMaximumCumulativeCost {
37    costs: Vec<i64>,
38    precedences: Vec<(usize, usize)>,
39}
40
41#[derive(Debug, Deserialize, crate::CreateSpec)]
42struct SequencingCumulativeCostCreateSpec {
43    /// Task costs.
44    #[create(codec = "comma-separated")]
45    costs: Vec<i64>,
46    /// Precedence arcs; omitted means no constraints.
47    #[create(codec = "arc-list")]
48    precedences: Option<Vec<(usize, usize)>>,
49}
50
51impl TryFrom<SequencingCumulativeCostCreateSpec> for SequencingToMinimizeMaximumCumulativeCost {
52    type Error = crate::registry::ConstructionError;
53    fn try_from(spec: SequencingCumulativeCostCreateSpec) -> Result<Self, Self::Error> {
54        let precedences = spec.precedences.unwrap_or_default();
55        if let Some(message) = precedence_validation_error(&precedences, spec.costs.len()) {
56            return Err(message.into());
57        }
58        Ok(Self {
59            costs: spec.costs,
60            precedences,
61        })
62    }
63}
64
65#[derive(Debug, Deserialize)]
66struct SequencingToMinimizeMaximumCumulativeCostUnchecked {
67    costs: Vec<i64>,
68    precedences: Vec<(usize, usize)>,
69}
70
71impl SequencingToMinimizeMaximumCumulativeCost {
72    /// Create a new instance.
73    ///
74    /// # Panics
75    ///
76    /// Panics if any precedence endpoint is out of range.
77    pub fn new(costs: Vec<i64>, precedences: Vec<(usize, usize)>) -> Self {
78        validate_precedences(&precedences, costs.len());
79        Self { costs, precedences }
80    }
81
82    /// Return the task costs.
83    pub fn costs(&self) -> &[i64] {
84        &self.costs
85    }
86
87    /// Return the precedence constraints.
88    pub fn precedences(&self) -> &[(usize, usize)] {
89        &self.precedences
90    }
91
92    /// Smallest h >= 1 bounding every task cost in magnitude strictly by 2^h.
93    pub fn max_cost_bits(&self) -> u64 {
94        crate::types::max_numeric_magnitude_bits(self.costs.iter().copied())
95    }
96
97    /// Return the number of tasks.
98    pub fn num_tasks(&self) -> usize {
99        self.costs.len()
100    }
101
102    /// Return the number of precedence constraints.
103    pub fn num_precedences(&self) -> usize {
104        self.precedences.len()
105    }
106
107    fn decode_schedule(&self, config: &[usize]) -> Option<Vec<usize>> {
108        super::decode_permutation(config, self.num_tasks())
109    }
110}
111
112impl<'de> Deserialize<'de> for SequencingToMinimizeMaximumCumulativeCost {
113    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
114    where
115        D: serde::Deserializer<'de>,
116    {
117        let unchecked =
118            SequencingToMinimizeMaximumCumulativeCostUnchecked::deserialize(deserializer)?;
119        if let Some(message) =
120            precedence_validation_error(&unchecked.precedences, unchecked.costs.len())
121        {
122            return Err(D::Error::custom(message));
123        }
124        Ok(Self {
125            costs: unchecked.costs,
126            precedences: unchecked.precedences,
127        })
128    }
129}
130
131fn validate_precedences(precedences: &[(usize, usize)], num_tasks: usize) {
132    if let Some(message) = precedence_validation_error(precedences, num_tasks) {
133        panic!("{message}");
134    }
135}
136
137fn precedence_validation_error(precedences: &[(usize, usize)], num_tasks: usize) -> Option<String> {
138    for &(pred, succ) in precedences {
139        if pred >= num_tasks {
140            return Some(format!(
141                "predecessor index {} out of range (num_tasks = {})",
142                pred, num_tasks
143            ));
144        }
145        if succ >= num_tasks {
146            return Some(format!(
147                "successor index {} out of range (num_tasks = {})",
148                succ, num_tasks
149            ));
150        }
151    }
152    None
153}
154
155impl Problem for SequencingToMinimizeMaximumCumulativeCost {
156    const NAME: &'static str = "SequencingToMinimizeMaximumCumulativeCost";
157    type Solution = Vec<usize>;
158    type Value = crate::types::Min<i64>;
159
160    crate::problem_parameters![
161        ("max_cost_bits", max_cost_bits),
162        ("num_precedences", num_precedences),
163        ("num_tasks", num_tasks),
164    ];
165
166    fn variant() -> Vec<(&'static str, &'static str)> {
167        crate::variant_params![]
168    }
169
170    fn evaluate(
171        &self,
172        config: &Self::Solution,
173    ) -> Result<crate::types::Min<i64>, crate::traits::EvaluationError> {
174        let n = self.num_tasks();
175        if config.len() != n {
176            return Err(crate::traits::EvaluationError::InvalidConfiguration(
177                "schedule length does not match the tasks".into(),
178            ));
179        }
180        if config.iter().any(|&task| task >= n) {
181            return Err(crate::traits::EvaluationError::InvalidConfiguration(
182                "schedule contains an out-of-range task".into(),
183            ));
184        }
185        Ok({
186            let Some(schedule) = self.decode_schedule(config) else {
187                return Ok(crate::types::Min(None));
188            };
189
190            let mut positions = vec![0usize; self.num_tasks()];
191            for (position, &task) in schedule.iter().enumerate() {
192                positions[task] = position;
193            }
194            for &(pred, succ) in &self.precedences {
195                if positions[pred] >= positions[succ] {
196                    return Ok(crate::types::Min(None));
197                }
198            }
199
200            let mut cumulative = 0i64;
201            let mut max_cumulative = 0i64;
202            for &task in &schedule {
203                cumulative = cumulative.checked_add(self.costs[task]).ok_or_else(|| {
204                    crate::traits::EvaluationError::IntegerOverflow(
205                        "summing sequencing cumulative costs".into(),
206                    )
207                })?;
208                if cumulative > max_cumulative {
209                    max_cumulative = cumulative;
210                }
211            }
212            crate::types::Min(Some(max_cumulative))
213        })
214    }
215}
216
217impl crate::solvers::BruteForceProblem for SequencingToMinimizeMaximumCumulativeCost {
218    fn dimensions(&self) -> Vec<usize> {
219        super::lehmer_dims(self.num_tasks())
220    }
221}
222
223crate::declare_variants! {
224    default SequencingToMinimizeMaximumCumulativeCost => "factorial(num_tasks)" create SequencingCumulativeCostCreateSpec,
225}
226
227crate::register_brute_force! {
228    SequencingToMinimizeMaximumCumulativeCost decode |problem: &SequencingToMinimizeMaximumCumulativeCost, indices: Vec<usize>| super::decode_lehmer(&indices, problem.num_tasks()).expect("enumerated Lehmer digits are valid"),
229}
230
231#[cfg(feature = "example-db")]
232pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
233    vec![crate::example_db::specs::ModelExampleSpec {
234        id: "sequencing_to_minimize_maximum_cumulative_cost",
235        instance: Box::new(SequencingToMinimizeMaximumCumulativeCost::new(
236            vec![2, -1, 3, -2, 1, -3],
237            vec![(0, 2), (1, 2), (1, 3), (2, 4), (3, 5), (4, 5)],
238        )),
239        optimal_config: serde_json::json!(vec![1, 0, 3, 2, 4, 5]),
240        optimal_value: serde_json::json!(3),
241    }]
242}
243
244#[cfg(test)]
245#[path = "../../unit_tests/models/misc/sequencing_to_minimize_maximum_cumulative_cost.rs"]
246mod tests;
problemreductions/models/misc/sequencing_to_minimize_maximum_cumulative_cost.rs

problemreductions/models/misc/
sequencing_to_minimize_maximum_cumulative_cost.rs
