Groupe d’études et de recherche en analyse des décisions

Very large scale covering location problems in the design of advanced metering infrastructure

Ivana Ljubic ESSEC, Grande École de Commerce, France

Smart metering is currently replacing simple billing with intelligent metering services of tremendous value to both utility companies and end users. According to Gartner, a typical family home could contain more than 500 smart devices by 2022. For covering this exceedingly increasing demand, wireless communications will be inevitable when it comes to designing and planning of the advanced metering infrastructure (AMI). In this talk we address the deployment of access points in the design of AMI. We embed a notion of proximity (or coverage radius) that specifies whether a given smart meter (representing a demand point, e.g., a household) can be served or "covered'' by a potential access point location (also referred to as potential facility location). A demand point is then said to be covered by an access point location if it lies within its coverage radius. Typically, a relatively small number of potential facility locations can be considered, while the number of demand points can run in the thousands or even millions. As such, finding the optimal placement of access points in the design of AMI remained out of reach for modern MIP solvers.

In this talk we address two optimization problems relevant for the design of AMI: the maximal covering location problem (MCLP), which requires choosing a subset of facilities that maximize the demand covered while respecting a budget constraint on the cost of the facilities and the partial set covering location problem (PSCLP) which minimizes the cost of the open facilities while forcing a certain amount of demand to be covered. We propose an effective decomposition approach based on the branch-and-Benders-cut reformulation. We also draw a connection between Benders and submodular cuts. The results of our computational study demonstrate that, thanks to this decomposition technique, optimal solutions can be found very quickly, even for benchmark instances involving up to twenty million demand points.

The talk is based on a joint work with J.F. Cordeau and F. Furini.

15h30-15h45: Come meet the speaker and other researchers over drinks and snacks
15h45-17h00: Presentation

Do not forget to confirm your attendance: