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<i64>`.
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<i64>,
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
32impl ReductionResult for ReductionSTMWCTToILP {
33    type Source = SequencingToMinimizeWeightedCompletionTime;
34    type Target = ILP<i64>;
35
36    fn target_problem(&self) -> &ILP<i64> {
37        &self.target
38    }
39
40    fn extract_solution(
41        &self,
42        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
43    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
44        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
45
46        Ok({
47            let mut schedule: Vec<usize> = (0..self.num_tasks).collect();
48            schedule.sort_by_key(|&task| (target_solution[task], task));
49            schedule
50        })
51    }
52}
53
54#[reduction(
55    transform = exact {
56        num_vars = "num_tasks + num_tasks * (num_tasks - 1) / 2",
57        num_constraints = "2 * num_tasks + 3 * num_tasks * (num_tasks - 1) / 2 + num_precedences",
58    },
59    unavailable = {
60        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
61    }
62)]
63impl ReduceTo<ILP<i64>> for SequencingToMinimizeWeightedCompletionTime {
64    type Result = ReductionSTMWCTToILP;
65
66    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
67        let num_tasks = self.num_tasks();
68
69        let total_processing_time = self.lengths().iter().try_fold(0i64, |total, &length| {
70            total.checked_add(length).ok_or_else(|| {
71                crate::rules::ReductionError::integer_overflow::<
72                    SequencingToMinimizeWeightedCompletionTime,
73                    ILP<i64>,
74                >("summing task processing times")
75            })
76        })?;
77        let lengths = self.lengths();
78        let weights = self.weights();
79        let num_order_vars = num_tasks * (num_tasks.saturating_sub(1)) / 2;
80        let num_vars = num_tasks + num_order_vars;
81
82        let order_var = |i: usize, j: usize| -> usize {
83            debug_assert!(i < j);
84            num_tasks + i * (2 * num_tasks - i - 1) / 2 + (j - i - 1)
85        };
86
87        let mut constraints = Vec::new();
88
89        for (task, &length) in lengths.iter().enumerate() {
90            constraints.push(LinearConstraint::ge(vec![(task, 1)], length));
91            constraints.push(LinearConstraint::le(vec![(task, 1)], total_processing_time));
92        }
93
94        for i in 0..num_tasks {
95            for j in (i + 1)..num_tasks {
96                let order = order_var(i, j);
97                let completion_i = i;
98                let completion_j = j;
99                let length_i = lengths[i];
100                let length_j = lengths[j];
101
102                constraints.push(LinearConstraint::le(vec![(order, 1)], 1));
103
104                // If y_{i,j} = 1, then task i is before task j: C_j - C_i >= l_j.
105                constraints.push(LinearConstraint::ge(
106                    vec![
107                        (completion_j, 1),
108                        (completion_i, -1),
109                        (order, -total_processing_time),
110                    ],
111                    length_j - total_processing_time,
112                ));
113
114                // If y_{i,j} = 0, then task j is before task i: C_i - C_j >= l_i.
115                constraints.push(LinearConstraint::ge(
116                    vec![
117                        (completion_i, 1),
118                        (completion_j, -1),
119                        (order, total_processing_time),
120                    ],
121                    length_i,
122                ));
123            }
124        }
125
126        for &(pred, succ) in self.precedences() {
127            constraints.push(LinearConstraint::ge(
128                vec![(succ, 1), (pred, -1)],
129                lengths[succ],
130            ));
131        }
132
133        let objective = weights.iter().copied().enumerate().collect();
134
135        Ok(Self::Result {
136            target: ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
137                .map_err(Self::target_construction)?,
138            num_tasks,
139        })
140    }
141}
142
143#[cfg(feature = "example-db")]
144pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
145    vec![crate::example_db::specs::RuleExampleSpec {
146        id: "sequencingtominimizeweightedcompletiontime_to_ilp",
147        build: || {
148            let source =
149                SequencingToMinimizeWeightedCompletionTime::new(vec![2, 1], vec![3, 5], vec![]);
150            crate::example_db::specs::rule_example_via_ilp::<_, i64>(source)
151        },
152    }]
153}
154
155#[cfg(test)]
156#[path = "../unit_tests/rules/sequencingtominimizeweightedcompletiontime_ilp.rs"]
157mod tests;
problemreductions/rules/sequencingtominimizeweightedcompletiontime_ilp.rs

problemreductions/rules/
sequencingtominimizeweightedcompletiontime_ilp.rs
