problemreductions/rules/
optimallineararrangement_sequencingtominimizeweightedcompletiontime.rs

1//! Reduction from OptimalLinearArrangement to SequencingToMinimizeWeightedCompletionTime.
2//!
3//! Lawler's construction uses one unit-length job per vertex and one
4//! zero-length job per edge. Vertex job `v` gets weight `d_max - deg(v)`,
5//! edge job `{u, v}` gets weight 2, and the edge job must follow both
6//! endpoint jobs.
7//!
8//! The source OLA model uses 0-indexed positions, while completion times
9//! in the scheduling model are 1-indexed because each vertex job has unit
10//! length. The resulting additive shift is still
11//! `d_max * n * (n + 1) / 2`: the `+1` offset is already accounted for by
12//! completion times, so no extra correction term is needed.
13
14use crate::models::graph::OptimalLinearArrangement;
15use crate::models::misc::SequencingToMinimizeWeightedCompletionTime;
16use crate::reduction;
17use crate::rules::traits::{ReduceTo, ReductionResult};
18use crate::topology::{Graph, SimpleGraph};
19
20/// Result of reducing OptimalLinearArrangement to SequencingToMinimizeWeightedCompletionTime.
21#[derive(Debug, Clone)]
22pub struct ReductionOLAToSequencingToMinimizeWeightedCompletionTime {
23    target: SequencingToMinimizeWeightedCompletionTime,
24    num_vertices: usize,
25}
26
27impl ReductionResult for ReductionOLAToSequencingToMinimizeWeightedCompletionTime {
28    type Source = OptimalLinearArrangement<SimpleGraph>;
29    type Target = SequencingToMinimizeWeightedCompletionTime;
30
31    fn target_problem(&self) -> &Self::Target {
32        &self.target
33    }
34
35    fn extract_solution(
36        &self,
37        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
38    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
39        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
40
41        Ok({
42            let mut arrangement = vec![0usize; self.num_vertices];
43            let mut next_position = 0usize;
44
45            for &task in target_solution {
46                if task < self.num_vertices {
47                    arrangement[task] = next_position;
48                    next_position += 1;
49                }
50            }
51
52            arrangement
53        })
54    }
55}
56
57#[reduction(
58    transform = exact {
59        num_tasks = "num_vertices + num_edges",
60    },
61    unavailable = {
62        num_precedences = "the exact target parameter is not represented by this reduction's symbolic transform",
63    }
64)]
65impl ReduceTo<SequencingToMinimizeWeightedCompletionTime>
66    for OptimalLinearArrangement<SimpleGraph>
67{
68    type Result = ReductionOLAToSequencingToMinimizeWeightedCompletionTime;
69
70    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
71        let graph = self.graph();
72        let num_vertices = graph.num_vertices();
73        let edges = graph.edges();
74        let max_degree = (0..num_vertices)
75            .map(|v| graph.degree(v))
76            .max()
77            .unwrap_or(0);
78        let max_degree = i64::try_from(max_degree).map_err(|_| {
79            crate::rules::ReductionError::integer_overflow::<
80                OptimalLinearArrangement<SimpleGraph>,
81                SequencingToMinimizeWeightedCompletionTime,
82            >("converting the maximum degree to i64")
83        })?;
84
85        let mut lengths = Vec::with_capacity(num_vertices + edges.len());
86        let mut weights = Vec::with_capacity(num_vertices + edges.len());
87        let mut precedences = Vec::with_capacity(2 * edges.len());
88
89        for vertex in 0..num_vertices {
90            let degree = i64::try_from(graph.degree(vertex)).map_err(|_| {
91                crate::rules::ReductionError::integer_overflow::<
92                    OptimalLinearArrangement<SimpleGraph>,
93                    SequencingToMinimizeWeightedCompletionTime,
94                >("converting a vertex degree to i64")
95            })?;
96            lengths.push(1);
97            weights.push(max_degree - degree);
98        }
99
100        for (edge_index, &(u, v)) in edges.iter().enumerate() {
101            let edge_task = num_vertices + edge_index;
102            lengths.push(0);
103            weights.push(2);
104            precedences.push((u, edge_task));
105            precedences.push((v, edge_task));
106        }
107
108        Ok(ReductionOLAToSequencingToMinimizeWeightedCompletionTime {
109            target: SequencingToMinimizeWeightedCompletionTime::new(lengths, weights, precedences),
110            num_vertices,
111        })
112    }
113}
114
115#[cfg(feature = "example-db")]
116pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
117    use crate::example_db::specs::assemble_rule_example;
118    use crate::export::SolutionPair;
119    use crate::solvers::BruteForce;
120
121    vec![crate::example_db::specs::RuleExampleSpec {
122        id: "optimallineararrangement_to_sequencingtominimizeweightedcompletiontime",
123        build: || {
124            let source =
125                OptimalLinearArrangement::new(SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]));
126            let reduction =
127                ReduceTo::<SequencingToMinimizeWeightedCompletionTime>::reduce_to(&source)
128                    .expect("reduction should succeed");
129            let target_config = BruteForce::new()
130                .solve(reduction.target_problem())
131                .expect("canonical target evaluation must succeed")
132                .expect("canonical example must be solvable");
133            let source_config = reduction.extract_solution(&target_config).unwrap();
134            assemble_rule_example(
135                &source,
136                reduction.target_problem(),
137                vec![SolutionPair {
138                    source_config: serde_json::to_value(source_config)
139                        .expect("solution serialization must succeed"),
140                    target_config: serde_json::to_value(target_config)
141                        .expect("solution serialization must succeed"),
142                }],
143            )
144        },
145    }]
146}
147
148#[cfg(test)]
149#[path = "../unit_tests/rules/optimallineararrangement_sequencingtominimizeweightedcompletiontime.rs"]
150mod tests;
problemreductions/rules/optimallineararrangement_sequencingtominimizeweightedcompletiontime.rs

problemreductions/rules/
optimallineararrangement_sequencingtominimizeweightedcompletiontime.rs
