# LocalSolver vs Gurobi on a Maintenance Scheduling Problem

The ROADEF Challenge is an Operations Research challenge organized by the French Operations Research Society and an industrial partner every two years. The topic of the ROADEF 2020 Challenge was a Maintenance Scheduling Problem arising in the electricity industry. It was posed by RTE, the French transmission system operator. This company is responsible for the operation, maintenance, and development of the French high-voltage transmission system, which is the largest in Europe, with approximately 100,000 kilometers of transmission lines.

Guaranteeing electricity delivery and supply is one of the most important missions of a transmission system operator such as RTE. But such an objective can only be carried out if the grid is correctly maintained. In particular, some maintenance operations on the overhead power lines are live-line works, while others require shutting the power down. When this happens, electricity delivery and supply must be guaranteed, meaning maintenance operations must be planned carefully. The network is resilient enough to endure an unexpected contingency when no maintenance operation exists. However, if several breakdowns occur, the grid might face significant blackouts. In this context, planned outages due to maintenance work must be scheduled cautiously.

## Input data

The instances are given on the Challenge website in three sets A, B, and C. The instances in the A set are small, the ones in the B set are large, and the ones in the C set are huge. Every set contains 15 instances.

## Mathematical models of the Maintenance Scheduling Problem

Writing the different constraints (schedule, resource, disjunctive) is straightforward and detailed in the Challenge subject. The main decision is choosing when to start a given task. We chose boolean decision variables for every task and time to model the problem. Moreover, with boolean decision variables, the different constraints are linear. Calculating the mean risk, the first part of the objective is also linear. The only part of the model that is not naturally written linearly is the quantile value for the expected excess calculation.

### LocalSolver model

**LocalSolver 11.0 **came with a new feature: the `sort `

operator, allowing one to sort an array from its lowest to its highest value. This feature proves to be particularly useful in this model. Indeed, to get the τ-quantile of the scenario’s risks, one only has to sort the array of scenario risk values and take the (τ*nbscenarios)^{th} value of the list.

```
function model() {
// Decision variables
startTime[i in 0..nbInterventions - 1][0..tmax[i]] <- bool();
// Interventions are planned exactly once
for [i in 0..nbInterventions - 1] {
constraint sum[t in 0..tmax[i]](startTime[i][t]) == 1;
}
// Resource constraints
for [c in 0..nbResources - 1] {
for [t in 0..T - 1]{
resourceUsed[c][t] <- sum[i in 0..nbInterventions - 1](sum[t_start in 0..t
: r[c] != nil && r[c][i] != nil && r[c][i][t] != nil
&& r[c][i][t][t_start] != nil]
(r[c][i][t][t_start] * startTime[i][t_start]));
constraint resourceUsed[c][t] <= u[c][t];
constraint l[c][t] <= resourceUsed[c][t];
}
}
// Exclusion constraints
for [e in 0..nbExclusions-1] {
is1Happening <- sum[t_start in 0..t_exclu[e]
: t_start >= t_exclu[e] - delta[i1[e]][t_start] + 1
&& t_start <= tmax[i1[e]]]
(startTime[i1[e]][t_start]);
is2Happening <- sum[t_start in 0..t_exclu[e]
: t_start >= t_exclu[e] - delta[i2[e]][t_start] + 1
&& t_start <= tmax[i2[e]]]
(startTime[i2[e]][t_start]);
constraint is1Happening + is2Happening <= 1;
}
// Risk computation
cumulRisk[t in 0..T - 1][s in 0..card_S[t] - 1] <- sum[i in 0..nbInterventions - 1]
(sum[t_start in 0..t : risk[i][t_start] != nil && risk[i][t_start][t] != nil
&& risk[i][t_start][t][s] != nil]
(risk[i][t_start][t][s] * startTime[i][t_start]));
meanCumulRiskAtT[t in 0..T - 1] <- sum[s in 0..card_S[t] - 1]
(cumulRisk[t][s]) / card_S[t];
obj1 <- sum[t in 0..T - 1](meanCumulRiskAtT[t]) / T;
card_X[t in 0..T - 1] <- ceil(tau * card_S[t]);
Qt_tau[t in 0..T - 1] <- sort(cumulRisk[t])[card_X[t] - 1];
excess[t in 0..T - 1] <- max(0, Qt_tau[t] - meanCumulRiskAtT[t]);
obj2 <- sum[t in 0..T - 1](excess[t]) / T;
obj <- alpha * obj1 + (1 - alpha) * obj2;
minimize(obj);
}
```

### Mixed-Integer Linear Programming (MILP) model

Because of the `sort`

operator, the LocalSolver model is not linear. To compare our results to a MILP solver, we have to write a linear model for the quantile value. We can calculate the quantile value by adding a boolean decision variable

for every scenario `isLowerThanQuantile[s, t]`

`s`

and time step `t`

and a

variable representing the quantile value. We then set the sum over the scenarios of the booleans to τ * nbscenarios, and add a constraint such that`floatQuantile[t]`

`floatQuantile[t]`

`>= isLowerThanQuantile[s, t] * cumulRisk[s, t] – meanCumulRiskAtT[t]`

Then, by minimization, the float quantile will take the value of the actual quantile. The rest of the model is identical to the LocalSolver model.

## LocalSolver and Gurobi results on the Maintenance Scheduling Probem

In this benchmark, we compare the performance of LocalSolver 11.0 and Gurobi 9.5 in 1 and 10 minutes of running time. We display the gap to the best known solutions found so far, among all the challenge participants, in 90 minutes of running time. We ran them on a server equipped with an Intel Core i7-10750H 2.60GHz with 32GB RAM. The three charts below give both solvers’ results on the three sets of instances.

LocalSolver | Gurobi | |||
---|---|---|---|---|

60 sec | 600 sec | 60 sec | 600 sec | |

Nb feasible | 15 | 15 | 15 | 15 |

Nb <5% gap | 14 | 14 | 11 | 15 |

Nb <1% gap | 11 | 11 | 10 | 11 |

LocalSolver | Gurobi | |||
---|---|---|---|---|

60 sec | 600 sec | 60 sec | 600 sec | |

Nb feasible | 15 | 15 | 5 | 14 |

Nb <10% gap | 11 | 15 | 0 | 6 |

Nb <5% gap | 8 | 10 | 0 | 1 |

LocalSolver | Gurobi | |||
---|---|---|---|---|

60 sec | 600 sec | 60 sec | 600 sec | |

Nb feasible | 10 | 14 | 4 | 11 |

Nb <10% gap | 6 | 13 | 0 | 4 |

Nb <5% gap | 5 | 8 | 0 | 1 |

We can observe that both solvers perform equally on small (A) instances, but as the instances get bigger, the LocalSolver’s performance remains good while Gurobi struggles. On the large (B) and huge (C) instances, LocalSolver finds feasible solutions much faster than Gurobi. Moreover, the quality of the solutions is much better with LocalSolver. For 87% of the instances, LocalSolver obtains a gap lower than 10% in 10 minutes of running time. In contrast, Gurobi only reaches a gap below 10% for 33% of the instances within the same running time.

## Conclusion

LocalSolver provides a compact mathematical model for the Transmission Maintenance Scheduling Problem posed by RTE in the context of the 2020 ROADEF Challenge. The `sort `

operator makes the model easy to write and considerably reduces the number of variables. It allows LocalSolver to perform well with large instances, while traditional Mixed-Integer Linear Programming (MILP) solvers like Gurobi struggle to find good solutions when the instances get bigger.

Are you interested in trying it out? Get free trial licenses here. In the meantime, feel free to contact us; we will be glad to exchange about your optimization problems.