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, France’s 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 be carried out only 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. In this benchmark, we compare the results of LocalSolver 11.0 and Gurobi 9.5 in 1 and 10 minutes to the best known solutions for these instances.

Mathematical model 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 to sort an array from its lowest to its highest value. This feature proves to be particularly useful in this model because 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 isLowerThanQuantile[s, t] for every scenario s and time step t and a floatQuantile[t] 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] >= 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

The results are presented for 3 sets of instances. The ones 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. The gap is calculated to the best known solution found so far, among all the participants of the challenge, in 90 minutes of running time. The instances were run using LocalSolver 11.0 and Gurobi 9.5 on an Intel Core i7-10750H 2.60GHz with 32GB RAM.

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
Results on the 15 small instances of the A set.
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
Results on the 15 large instances of the B set.
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
Results on the 15 huge instances of the C set.

We can observe that both solvers perform equally on small (A) instances, but as the instances get bigger, the performance of LocalSolver 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, whereas for only 33% of the instances, Gurobi reaches a gap lower than 10% 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.

We are at your disposal to accompany you in the discovery of LocalSolver. Don’t hesitate to contact us for any further information or support.

Share