## PGMO Seminars 2015

**17 Septembre 2015**

**Jonas Schweiger**(CPLEX Optimization, IBM Italy) "Operation and Optimization of Gas Transmission Networks"

Gas transmission networks are complex structures that consist of passive pipes and active, controllable elements such as valves and compressors. Operating a large-scale gas network is a challenging task: Find settings for all active elements such that a nominated amount of gas can be transmitted through the network, without violating physical or operational constraints. In this talk, we present a nonlinear mixed-integer model taking into account continuous (like pressure and flow) and discrete decisions (like the configuration of active devices). As investments in the infrastructure are very cost-intensive and long-living, network extensions should not only focus on one bottleneck scenario, but should increase the flexibility to fulfill different demand scenarios. We formulate a model for the network extension problem for multiple demand scenarios and propose two solution strategies.

**Ivana Ljubic**(ESSEC Business School of Paris, France) "On optimal design of charging stations for electric vehicles"

A company running its operations based on an fleet of electric vehicles (EVs), be it a logistic company or an e-car provider, faces a difficult decision problem of planning the underlying charging infrastructure.

Due to expensive EV batteries and their limited range, a stable and robust charging infrastructure is crucial for running the business in a sustainable fashion.

Since building and/or renting charging stations is expensive, logistic companies or e-car providers are interested in minimizing the number of charging stations

whilst enabling travels between specific locations. Furthermore, in some metropolises (including Stockholm, Gothenburg and Singapore) congestion taxing or congestion charging mechanisms are implemented.

In this talk I will present the Network Design Problem with Relays (NDPR) which gives answers to some important strategic design questions in context of e-mobility.

Given a family of origin-destination pairs EVs need to travel, and given the existing links that can be traversed:

1. What are the optimal locations for placing the charging stations and how many of them are needed?

2. Could the available infrastructure be enhanced by including additional links (shortcuts), to reduce the travel distances?

In contrast to previous work on the NDPR which mainly focused on heuristic approaches, we discuss exact approaches based on different mixed integer linear programming formulations for the problem. We develop Branch-and-Price and Branch-Price-and-Cut algorithms that build upon models with an exponential number of constraints and variables. In a computational study, we analyze the performance of these approaches for instances with different characteristics.

*Joint work with Markus Leitner, Martin Riedler, Mario Ruthmair (Vienna)*

#### 16 Juin 2015

**Vincent Leclere**(Ecole des Ponts CERMICS) "Safe elimination of variables and applications"

For various reasons (stability, interpretability of the result), we can wish for a sparse solution of an optimization problem. One common way of obtaining sparsity of the solution consists in penalizing the L1 norm of the decision vector. We review a few cases of such optimization problems where we know beforehand that the value of some coordinate of the optimal solution is zero. In other words, we can reduce the size of the optimization problem addressed.

We will present an application to the intraday optimization problem.

#### 7 Avril 2015

**Jeff Linderoth**(University of Wisconsin-Madison, USA) "A cycle-based formulation and valid inequalities for DC power transmission problems with switching"

It is well-known that optimizing network topology by switching on and off transmission lines improves the efficiency of power delivery in electrical networks. Many authors have studied the problem of determining an optimal set of transmission lines to switch off to minimize the cost of meeting a given power demand under the direct current (DC) model of power flow. This problem is known in the literature as the Direct-Current Optimal Transmission Switching Problem (DC-OTS). Most research on DC-OTS has focused on heuristic algorithms for generating quality solutions or on the application of DC-OTS to crucial operational and strategic problems. The mathematical theory of the DC-OTS problem is less well-developed. In this work, we formally establish that DC-OTS is NP-Hard, even if the power network is a series-parallel graph with at most one load/demand pair. Inspired by Kirchoff's Voltage Law, we give a cycle-based formulation for DC-OTS, and we use the new formulation to build a cycle-induced relaxation. We characterize the convex hull of the cycle-induced relaxation, and the characterization provides strong valid inequalities that can be used in a cutting-plane approach to solve the DC-OTS. We give details of a practical implementation, and we show promising computational results on standard benchmark instances.

*This is joint work with: Burak Kocuk, Santanu Dey, Andy Sun (Georgia Tech), Hyemin Jeon, and Jim Luedtke (Wisconsin)*

**René Aid**(EDF R&D deputy head of the osiris department) "An optimal trading problem in intraday electricity markets"

We consider the problem of optimal trading for a power producer in the context of intraday electricity markets. The aim is to minimize the imbalance cost induced by the random residual demand in electricity, i.e. the consumption from the clients minus the production from renewable energy. For a simple linear price impact model and a quadratic criterion, we explicitly obtain approximate optimal strategies in the intraday market and thermal power generation, and exhibit some remarkable properties of the trading rate. Furthermore, we study the case when there are jumps on the demand forecast and on the intraday price, typically due to error in the prediction of wind power generation. Finally, we solve the problem when taking into account delay constraints in thermal power production.

#### 17 Mars 2015

**Faisal Wahid**(Ecole Polytechnique and University of Auckland New Zealand) "Solving the stochastic hydro-bidding problem using a mixed integer dynamic approximation scheme"

#### 27 Janvier 2015

**Nelson Maculan**(Professor Emeritus, Federal University of Rio de Janeiro, Brazil) "Two Applications of Mixed Integer Nonlinear Programming (MINLP) in Rn: the Euclidean Steiner Tree Problem and Covering a Solid with Different Spheres"

1-The Euclidean Steiner tree problem (ESTP) in Rn consists of finding a tree of minimal Euclidean length that spans a given set of points in Rn, using or not additional points. Only a few papers consider the exact solution for the ESTP in Rn (n>2) and there are just two works that considered a mathematical programming formulation for the ESTP. One of them presented a convex mixedinteger formulation that could be implemented in a Branch and Bound (B&B) algorithm. This work presents techniques to improve the performance of the B&B algorithm in order to implement this formulation.

2-We present a mathematical programming model for the problem of covering solids by spheres of different radii. Given a set of spheres, possibly with different diameters, and a solid, the goal is to locate the spheres in such a way their union forms a coverage for this solid, using the smallest possible number of spheres of this set. This problem has an application in the radio-surgical treatment planning known as Gamma Knife and can be formulated as a non-convex optimization problem with quadratic constraints and a linear objective function.