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(&self, target_solution: &[usize]) -> Vec<usize> {
36        let schedule = crate::models::misc::decode_lehmer(target_solution, self.target.num_tasks())
37            .expect("target solution must be a valid Lehmer code");
38        let mut arrangement = vec![0usize; self.num_vertices];
39        let mut next_position = 0usize;
40
41        for task in schedule {
42            if task < self.num_vertices {
43                arrangement[task] = next_position;
44                next_position += 1;
45            }
46        }
47
48        arrangement
49    }
50}
51
52#[reduction(overhead = {
53    num_tasks = "num_vertices + num_edges",
54})]
55impl ReduceTo<SequencingToMinimizeWeightedCompletionTime>
56    for OptimalLinearArrangement<SimpleGraph>
57{
58    type Result = ReductionOLAToSequencingToMinimizeWeightedCompletionTime;
59
60    fn reduce_to(&self) -> Self::Result {
61        let graph = self.graph();
62        let num_vertices = graph.num_vertices();
63        let edges = graph.edges();
64        let max_degree = (0..num_vertices)
65            .map(|v| graph.degree(v))
66            .max()
67            .unwrap_or(0) as u64;
68
69        let mut lengths = Vec::with_capacity(num_vertices + edges.len());
70        let mut weights = Vec::with_capacity(num_vertices + edges.len());
71        let mut precedences = Vec::with_capacity(2 * edges.len());
72
73        for vertex in 0..num_vertices {
74            lengths.push(1);
75            weights.push(max_degree - graph.degree(vertex) as u64);
76        }
77
78        for (edge_index, &(u, v)) in edges.iter().enumerate() {
79            let edge_task = num_vertices + edge_index;
80            lengths.push(0);
81            weights.push(2);
82            precedences.push((u, edge_task));
83            precedences.push((v, edge_task));
84        }
85
86        ReductionOLAToSequencingToMinimizeWeightedCompletionTime {
87            target: SequencingToMinimizeWeightedCompletionTime::new(lengths, weights, precedences),
88            num_vertices,
89        }
90    }
91}
92
93#[cfg(feature = "example-db")]
94pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
95    use crate::example_db::specs::assemble_rule_example;
96    use crate::export::SolutionPair;
97    use crate::solvers::BruteForce;
98
99    vec![crate::example_db::specs::RuleExampleSpec {
100        id: "optimallineararrangement_to_sequencingtominimizeweightedcompletiontime",
101        build: || {
102            let source =
103                OptimalLinearArrangement::new(SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]));
104            let reduction =
105                ReduceTo::<SequencingToMinimizeWeightedCompletionTime>::reduce_to(&source);
106            let target_config = BruteForce::new()
107                .find_witness(reduction.target_problem())
108                .expect("canonical example must be solvable");
109            let source_config = reduction.extract_solution(&target_config);
110            assemble_rule_example(
111                &source,
112                reduction.target_problem(),
113                vec![SolutionPair {
114                    source_config,
115                    target_config,
116                }],
117            )
118        },
119    }]
120}
121
122#[cfg(test)]
123#[path = "../unit_tests/rules/optimallineararrangement_sequencingtominimizeweightedcompletiontime.rs"]
124mod tests;
problemreductions/rules/optimallineararrangement_sequencingtominimizeweightedcompletiontime.rs

problemreductions/rules/
optimallineararrangement_sequencingtominimizeweightedcompletiontime.rs
