problemreductions/rules/
sequencingtominimizeweightedcompletiontime_ilp.rs

1//! Reduction from SequencingToMinimizeWeightedCompletionTime to ILP.
2//!
3//! The reduction uses integer completion-time variables `C_j` and integer
4//! order variables `y_{i,j}` constrained to `{0, 1}` within `ILP<i32>`.
5//! For each unordered pair `{i, j}`, a pair of big-M constraints forces one
6//! task to finish before the other starts.
7
8use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
9use crate::models::misc::SequencingToMinimizeWeightedCompletionTime;
10use crate::reduction;
11use crate::rules::traits::{ReduceTo, ReductionResult};
12
13#[derive(Debug, Clone)]
14pub struct ReductionSTMWCTToILP {
15    target: ILP<i32>,
16    num_tasks: usize,
17}
18
19impl ReductionSTMWCTToILP {
20    #[cfg(test)]
21    pub(crate) fn completion_var(&self, task: usize) -> usize {
22        task
23    }
24
25    #[cfg(test)]
26    pub(crate) fn order_var(&self, i: usize, j: usize) -> usize {
27        assert!(i < j, "order_var expects i < j");
28        self.num_tasks + i * (2 * self.num_tasks - i - 1) / 2 + (j - i - 1)
29    }
30
31    fn encode_schedule_as_lehmer(schedule: &[usize]) -> Vec<usize> {
32        let mut available: Vec<usize> = (0..schedule.len()).collect();
33        let mut config = Vec::with_capacity(schedule.len());
34        for &task in schedule {
35            let digit = available
36                .iter()
37                .position(|&candidate| candidate == task)
38                .expect("schedule must be a permutation");
39            config.push(digit);
40            available.remove(digit);
41        }
42        config
43    }
44}
45
46impl ReductionResult for ReductionSTMWCTToILP {
47    type Source = SequencingToMinimizeWeightedCompletionTime;
48    type Target = ILP<i32>;
49
50    fn target_problem(&self) -> &ILP<i32> {
51        &self.target
52    }
53
54    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
55        let mut schedule: Vec<usize> = (0..self.num_tasks).collect();
56        schedule.sort_by_key(|&task| (target_solution.get(task).copied().unwrap_or(0), task));
57        Self::encode_schedule_as_lehmer(&schedule)
58    }
59}
60
61#[reduction(overhead = {
62    num_vars = "num_tasks + num_tasks * (num_tasks - 1) / 2",
63    num_constraints = "2 * num_tasks + 3 * num_tasks * (num_tasks - 1) / 2 + num_precedences",
64})]
65impl ReduceTo<ILP<i32>> for SequencingToMinimizeWeightedCompletionTime {
66    type Result = ReductionSTMWCTToILP;
67
68    fn reduce_to(&self) -> Self::Result {
69        let num_tasks = self.num_tasks();
70        let max_ilp_value = i32::MAX as u64;
71        let max_exact_f64_integer = 1u64 << 53;
72        assert!(
73            self.lengths().iter().all(|&length| length <= max_ilp_value),
74            "task lengths must fit in ILP<i32> variable bounds"
75        );
76
77        let total_processing_time_u64 = self.total_processing_time();
78        assert!(
79            total_processing_time_u64 <= max_ilp_value,
80            "total processing time must fit in ILP<i32> variable bounds"
81        );
82
83        let total_weight = self
84            .weights()
85            .iter()
86            .try_fold(0u64, |acc, &weight| acc.checked_add(weight))
87            .expect("weighted completion objective must fit exactly in f64");
88        assert!(
89            total_processing_time_u64 == 0
90                || total_weight <= max_exact_f64_integer / total_processing_time_u64,
91            "weighted completion objective must fit exactly in f64"
92        );
93
94        let total_processing_time = total_processing_time_u64 as f64;
95        let num_order_vars = num_tasks * (num_tasks.saturating_sub(1)) / 2;
96        let num_vars = num_tasks + num_order_vars;
97
98        let order_var = |i: usize, j: usize| -> usize {
99            debug_assert!(i < j);
100            num_tasks + i * (2 * num_tasks - i - 1) / 2 + (j - i - 1)
101        };
102
103        let mut constraints = Vec::new();
104
105        for (task, &length) in self.lengths().iter().enumerate() {
106            constraints.push(LinearConstraint::ge(vec![(task, 1.0)], length as f64));
107            constraints.push(LinearConstraint::le(
108                vec![(task, 1.0)],
109                total_processing_time,
110            ));
111        }
112
113        for i in 0..num_tasks {
114            for j in (i + 1)..num_tasks {
115                let order = order_var(i, j);
116                let completion_i = i;
117                let completion_j = j;
118                let length_i = self.lengths()[i] as f64;
119                let length_j = self.lengths()[j] as f64;
120
121                constraints.push(LinearConstraint::le(vec![(order, 1.0)], 1.0));
122
123                // If y_{i,j} = 1, then task i is before task j: C_j - C_i >= l_j.
124                constraints.push(LinearConstraint::ge(
125                    vec![
126                        (completion_j, 1.0),
127                        (completion_i, -1.0),
128                        (order, -total_processing_time),
129                    ],
130                    length_j - total_processing_time,
131                ));
132
133                // If y_{i,j} = 0, then task j is before task i: C_i - C_j >= l_i.
134                constraints.push(LinearConstraint::ge(
135                    vec![
136                        (completion_i, 1.0),
137                        (completion_j, -1.0),
138                        (order, total_processing_time),
139                    ],
140                    length_i,
141                ));
142            }
143        }
144
145        for &(pred, succ) in self.precedences() {
146            constraints.push(LinearConstraint::ge(
147                vec![(succ, 1.0), (pred, -1.0)],
148                self.lengths()[succ] as f64,
149            ));
150        }
151
152        let objective = self
153            .weights()
154            .iter()
155            .enumerate()
156            .map(|(task, &weight)| (task, weight as f64))
157            .collect();
158
159        Self::Result {
160            target: ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize),
161            num_tasks,
162        }
163    }
164}
165
166#[cfg(feature = "example-db")]
167pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
168    vec![crate::example_db::specs::RuleExampleSpec {
169        id: "sequencingtominimizeweightedcompletiontime_to_ilp",
170        build: || {
171            let source =
172                SequencingToMinimizeWeightedCompletionTime::new(vec![2, 1], vec![3, 5], vec![]);
173            crate::example_db::specs::rule_example_via_ilp::<_, i32>(source)
174        },
175    }]
176}
177
178#[cfg(test)]
179#[path = "../unit_tests/rules/sequencingtominimizeweightedcompletiontime_ilp.rs"]
180mod tests;
problemreductions/rules/sequencingtominimizeweightedcompletiontime_ilp.rs

problemreductions/rules/
sequencingtominimizeweightedcompletiontime_ilp.rs
