This repository contains Julia scripts implementing the algorithms proposed to solve the max k-multicover problem introduced in the following publication: "Siting Renewable Power Generation Assets with Combinatorial Optimisation", Mathias Berger et al., Optimization Letters, 2021. DOI: https://doi.org/10.1007/s11590-021-01795-0
The following algorithms are available in this repository:
- Direct solution of integer programming (IP) formulation of max k-multicover via branch-and-bound/cut (via JuMP and Gurobi 9.1)
- Direct solution of mixed-integer programming relaxation of IP via branch-and-bound/cut (via JuMP and Gurobi 9.1)
- Greedy algorithm with randomised tie-breaking
- Greedy algorithm with randomised partial enumeration and tie-breaking
- Simulated annealing local search algorithm
- Algorithm combining 2) and 5)
- Algorithm combining 4) and 5)
The src directory includes three scripts, namely:
- algorithms.jl, which implements algorithms 1. - 7.
- utilities.jl, which includes useful auxiliary functions
- main.jl, from which algorithms can be run
The data directory includes some toy data on which the algorithms can be tested. The data come from a renewable power plant siting application, where a user-specified number of onshore wind sites (k) must be selected out of 3609 candidate sites in Europe so as to minimise the occurrence of simultaneous low electricity production events relative to a user-specified threshold (e.g., such that at least c sites produce simultaneously). Hourly-sampled wind speed data from the ERA5 database were transformed into so-called capacity factor data (reflecting the amount of electricity that each candidate site may produce during each hour, based on the type of power generation technology that may be deployed there). In total, capacity factor data are available for 744 hours (one month) and each candidate site. These data are stored in capacity_factors_matrix.p, which is a pickled file (the data can be extracted with functions provided in the utilities.jl script). Electricity demand data are stored in demand_vector.p, while technical potential (i.e., the maximum amount of capacity that may be deployed at a given site) data are stored in potential.p. The capacity factor, electricity demand and technical potential data are used to construct the D matrix, which is used in the MIP formulations of max k-multicover and is also used to compute the objective value in other algorithms.
Please feel free to email any requests or comments to mathias.berger@alumni.duke.edu.