Hexaly vs Gurobi on a Maintenance Scheduling Problem

Benchmark Energy Workforce Scheduling

Thomas Optimization Scientist May 2, 2022

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.

Hexaly model

Hexlay Optimizer 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 Hexaly 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 Hexaly model.

Hexaly and Gurobi results on the Maintenance Scheduling Problem

In this benchmark, we compare the performance of Hexaly 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.

We can observe that both solvers perform equally on small (A) instances, but as the instances get bigger, Hexaly’s performance remains good while Gurobi struggles. On the large (B) and huge (C) instances, Hexaly finds feasible solutions much faster than Gurobi. Moreover, the quality of the solutions is much better with Hexaly. For 87% of the instances, Hexaly 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

Hexaly 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 Hexaly 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 discuss your optimization problems.