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        max_processing_time_bits = "1",
60        num_tasks = "num_vertices + num_edges",
61        num_precedences = "2 * num_edges",
62    }
63)]
64impl ReduceTo<SequencingToMinimizeWeightedCompletionTime>
65    for OptimalLinearArrangement<SimpleGraph>
66{
67    type Result = ReductionOLAToSequencingToMinimizeWeightedCompletionTime;
68
69    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
70        let graph = self.graph();
71        let num_vertices = graph.num_vertices();
72        let edges = graph.edges();
73        let max_degree = (0..num_vertices)
74            .map(|v| graph.degree(v))
75            .max()
76            .unwrap_or(0);
77        let max_degree = i64::try_from(max_degree).map_err(|_| {
78            crate::rules::ReductionError::integer_overflow::<
79                OptimalLinearArrangement<SimpleGraph>,
80                SequencingToMinimizeWeightedCompletionTime,
81            >("converting the maximum degree to i64")
82        })?;
83
84        let mut lengths = Vec::with_capacity(num_vertices + edges.len());
85        let mut weights = Vec::with_capacity(num_vertices + edges.len());
86        let mut precedences = Vec::with_capacity(2 * edges.len());
87
88        for vertex in 0..num_vertices {
89            let degree = i64::try_from(graph.degree(vertex)).map_err(|_| {
90                crate::rules::ReductionError::integer_overflow::<
91                    OptimalLinearArrangement<SimpleGraph>,
92                    SequencingToMinimizeWeightedCompletionTime,
93                >("converting a vertex degree to i64")
94            })?;
95            lengths.push(1);
96            weights.push(max_degree - degree);
97        }
98
99        for (edge_index, &(u, v)) in edges.iter().enumerate() {
100            let edge_task = num_vertices + edge_index;
101            lengths.push(0);
102            weights.push(2);
103            precedences.push((u, edge_task));
104            precedences.push((v, edge_task));
105        }
106
107        Ok(ReductionOLAToSequencingToMinimizeWeightedCompletionTime {
108            target: SequencingToMinimizeWeightedCompletionTime::new(lengths, weights, precedences),
109            num_vertices,
110        })
111    }
112}
113
114#[cfg(feature = "example-db")]
115pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
116    use crate::example_db::specs::assemble_rule_example;
117    use crate::export::SolutionPair;
118    use crate::solvers::BruteForce;
119
120    vec![crate::example_db::specs::RuleExampleSpec {
121        id: "optimallineararrangement_to_sequencingtominimizeweightedcompletiontime",
122        build: || {
123            let source =
124                OptimalLinearArrangement::new(SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]));
125            let reduction =
126                ReduceTo::<SequencingToMinimizeWeightedCompletionTime>::reduce_to(&source)
127                    .expect("reduction should succeed");
128            let target_config = BruteForce::new()
129                .solve(reduction.target_problem())
130                .expect("canonical target evaluation must succeed")
131                .expect("canonical example must be solvable");
132            let source_config = reduction.extract_solution(&target_config).unwrap();
133            assemble_rule_example(
134                &source,
135                reduction.target_problem(),
136                vec![SolutionPair {
137                    source_config: serde_json::to_value(source_config)
138                        .expect("solution serialization must succeed"),
139                    target_config: serde_json::to_value(target_config)
140                        .expect("solution serialization must succeed"),
141                }],
142            )
143        },
144    }]
145}
146
147#[cfg(test)]
148#[path = "../unit_tests/rules/optimallineararrangement_sequencingtominimizeweightedcompletiontime.rs"]
149mod tests;
problemreductions/rules/optimallineararrangement_sequencingtominimizeweightedcompletiontime.rs

problemreductions/rules/
optimallineararrangement_sequencingtominimizeweightedcompletiontime.rs
