Robust Optimization techniques have turned into a standard toolset for solving Mixed-Integer Optimization problems in real world applications. This includes, in particular, cost-robust and demand-robust network optimization problems. We therefore focus on the more challenging problems arising when structural robustness is required. For problems with a well-defined robustness requirement we will present a reformulation approach preserving much of the combinatorial structure but employing a relaxed notion of feasibility due to Adjiashvili et al. Alternatively, a stochastic view on robustness may be taken, leading to (multistage) stochastic optimization problems. We propose a generic method to reformulate them as mixed-integer linear programs by bundling equivalent scenarios, avoiding scenario sampling. The approach makes use of binary decision diagrams to store a cover of the scenario space, and uses them to derive an inequality system for computing scenario probabilities conditioned on the lower-level decisions. As an application we significantly improve upon the scenario space partitioning approach for the pre-disaster network strengthening problem and discuss applicability to other network reliability improvement problems.

We present a series of investment models for power systems with high penetration of renewable generation. The first models determine the optimal expansion plan of stochastic generating units to maximize the profit of a power producer participating in electricity markets. The second set of models provide the optimal generation and transmission expansion plan of a central planner aiming at minimizing the sum of operating and investment costs. The main contribution of these models is the consideration of forecast errors of stochastic production through the modeling of a day-ahead and a balancing market. Additionally, we investigate the impact of the market design on the optimal expansion planning of both profit-maximizing power producers and cost-minimizing central planners. The main features of the proposed models are demonstrated through illustrative examples and larger case studies.

The Hydro Unit Commitment is a well known and interesting problem that has been studied since decades. Nevertheless, it still represent a challenge for several reasons, for example the wish of better model physical and strategic constraints. In this talk, we'll focus on some of the challenges arising in the deterministic Hydro Unit Commitment context and present mathematical programming methods to tackle them.

We discuss the Swiss2Grid project, a pilot and demonstration project for the evaluation of demand management policies in micro grids. The increasing diffusion of decentralised energy generation (Photovoltaics) the imminent massive diffusion of plug in Electrice Vehicles (EVs), can lead to imbalances on the electric grid and the associated huge capital investments in grid infrastructures to meet the increasing energy flows. In the Swiss2Grid project we propose a fully decentralized approach to load management in the local low-voltage grid. Single households, or even single devices, use a local control algorithm that uses local data to infer the current status of the low-voltage grid. The algorithm forecasts the status of the grid in the imminent future and exploits the optionally available level of freedom in shifting loads or using locally stored energy (e.g., in stationary batteries). We present the overall results of the project. We first describe the pilot set-up in Mendrisio, a city in Southern Switzerland, we describe the algorithm principles, we detail the forecast modules and finally we present results obtained in a comprehensive simulation environment.
As a second contribution, we study how different levels of communication pervasiveness affect system performance. We developed a realistic micro-simulation environment accounting for the behavior of residents, dispatchable and non-dispatchable household loads, and the effects on the distribution network. We considered a generic model of communication among household controllers, not tied to any specific technology, and based on the partitioning of the households in a number of groups (neighborhoods). Controllers within the same neighborhood enjoy full connectivity, but cannot interact with controllers outside of their neighborhood. Through extensive simulation experiments, we observed that even communication neighborhoods constituted by as few as 3/4 households are sufficient to effectively stabilize the aggregate network load profile, with minimal bandwidth consumption. Increasing the neighborhood size leads to comparatively negligible performance improvements. We conclude that effective load flattening can be achieved with minimal requirements.

The study of the interactions between the economy (at national, global and local levels), the energy sector and the corresponding impacts on the environment inherently involves multiple axes of evaluation of distinct policies. Input-output (IO) analysis offers a consistent framework for developing multiobjective models for assessing the trade-offs associated with those policies. The analytical framework of IO analysis enables to model the interactions between the whole economy and the energy sector, thus identifying the energy required for the provision of goods and services in an economy and also quantifying the corresponding pollutant emissions. This lecture is aimed at reviewing the different modelling approaches available in the scientific literature based on coupling IO analysis with multiobjective models that can be particularly useful for policy decision-makers to assess the trade-offs between the energy-environment-economy (E3) pillars of sustainable development, particularly relevant in the current sluggish economic context.

Constraints matrices with block-angular structures are pervasive in Optimization. They appear in many fields, for instance, logistics, telecommunications, energy or big-data. Interior-point methods have shown to be competitive for these structured problems by exploiting the linear algebra. One of these approaches solves the normal equations using sparse Cholesky factorizations for the block constraints, and a preconditioned conjugate gradient (PCG) for the linking constraints, which relies on a particular preconditioner. In this talk we will discuss an efficient solver based on this algorithm for linearly constrained convex separable problems (linear, quadratic or nonlinear). The solver has been hooked to SML, a structured conveying modelling language based on the popular AMPL modeling language. Computational results will be reported for some large and difficult instances in the literature. In the largest instances tested, of up to 25 millions of variables and 300000 constraints, this approach was from two to three 3 orders of magnitude faster than state-of-the-art linear and quadratic commercial optimization solvers.

The use of regenerative braking is a key factor to reduce the energy consumption of a metro line. In the case where no device can store the energy produced during braking, only the metros that are accelerating at the same time can benefit from it. Maximizing the power transfers between accelerating and braking metros thus provides a simple strategy to benefit from regenerative energy without any other hardware device.
In this paper, we use a mathematical timetable model to classify various metro energy optimization problems studied in the literature and prove their NP-hardness by polynomial reductions of SAT. We then focus on the problem of minimizing the global energy consumption of a metro timetable by modifying the dwell times in stations. We present a greedy heuristic algorithm which aims at locally synchronizing braking trains along the timetable with accelerating trains in their time neighbourhood, using a non-linear approximation of energy transfers. On a benchmark of six small size timetables, we show that our greedy heuristics performs better than CPLEX using a MILP formulation of the problem with a linear approximation of the objective function.
We also show that it runs ten times faster than a state-of-the-art evolutionary algorithm, called the covariance matrix adaptation evolution strategy (CMA-ES), using the same non-linear objective function on these small size instances. On real data leading to 10000 decision variables on which both MILP and CMA-ES do not provide solutions, our dedicated algorithm computes solutions with a reduction of energy consumption ranging from 5% to 9%.

One of the great and difficult problems that EU is facing today consists of the estimation of timing for having a clean power generation technologies and electricity free transmission expansion network at a pan-European level in a long term (e.g., 30 years time horizon). EU has established aggressive pollutant emission reduction targets: a 20% reduction in greenhouse gases with respect to 1990 levels by 2020 (most of the member countries are still far away from that target) and endorsing an objective of 80% reductions by 2050. Mathematical optimization models and algorithms for problem solving to address the above challenges are essential computerized tools for helping in the decision making for estimating the appropriate feasible mix of power generation sources (ranging from less coal, nuclear and combined cycle gas turbine to more renewable sources: hydroelectric, wind, solar, photovoltaic and biomass), the power generation plant / farm locations and dimensions , and the location and capacity of new lines in the transmission network, so that the solution satisfies the electricity demand from main focal points in the European region. Additionally, the tools should help to maximize different types of utility criteria at pan-European level, and quantifying the benefits of using cleaner, safer and efficient (cheaper) energy accessible to all the consumption nodes from perhaps far away power generation sites in the network. In this work a stochastic multiperiod mixed integer optimization model is presented as well as some hints on the different algorithmic approaches for that gigantic problem solving. The main parameters are uncertain, so, a set of scenarios should be generated for: fuels prices, electricity demand and prices at the network nodes of the energy system, operating hours per period of power generation technologies, CO2 emission permits and Green Certificates prices and allowed bounds, power generation cost of different technologies, electricity loss of new transmission technologies, characteristics (i.e., maximum energy flow and reactance) of cable types on new energy transmission lines, user-driven investment allocation bounds on cost of total power generation and energy transmission technologies, etc. There is not a unique function-criterion to consider. Rather it is a multicriteria problem, since the model must consider the maximization of the NPV of expected investment and consumer stakeholders goals over the scenarios along the time horizon subject to some risk reduction of the negative impact of non- wanted scenarios on different types of utility objectives and stakeholders at European level, such as maximizing power share of cleaner, safer and efficient energy accessible to all consumption nodes, cost investment from private and public institutions, generation and transmission network reliability, EC directives on environmental issues and others, EU governments, etc. Additionally, the maximization of the NPV of the expected global profit in the proposed model is subject to time stochastic dominance constraints for a set of profiles for each function (including the objective one) , such that each profile is given by the 4-tupla: threshold on the objective function value and maximum shortfall allowed for each scenario group at selected time periods as well as related target bounds on the probability of failure on reaching the threshold and expected shortfall. The gigantic problem cannot be solved up to optimality such that a realistic approach consists of a combination of sample scenario schemes, inexact scenario (scenario groups) decomposition algorithms and high performance computing.

We propose a new « primal-dual framework » to deal with European day-ahead electricity auctions, which has applications in both the algorithmic and economic modelling fields. Those auctions are at the core of the Price Coupling of Regions project and the corresponding coupling algorithm EUPHEMIA (see [e]), aimed at building a fully integrated Pan-European exchange platform for electricity traders in such day-ahead markets (coupling most of European power exchanges). They include products rendering the auction clearing problem a non-linear non-convex optimization problem with integer constraints. In such contexts where classical strong duality results fail, most of the time no market equilibrium with uniform prices exists. The relaxation from a perfect equilibrium with uniform prices adopted in European markets is to allow for paradoxically rejected orders, which are orders earning money at the computed market clearing prices, but nonetheless rejected, incurring opportunity costs to some bidders. The objective function in practice is to optimize welfare, an optimization problem considered in [a,c]. However, practitioners and stakeholders have in the past been interested in knowing what could be ‘in theory’ the minimum opportunity costs possible, or the minimum number of those paradoxically rejected orders, while still satisfying European market clearing rules [b]. It should be noted that computed prices depend in particular on the combination of block and complex orders selected according to the chosen objective, the admissible selections themselves depending on prices. This is why [d] proposes the term of “price-based decisions” for this kind of problems.

Contribution

We briefly review with toy examples the core ideas relevant for market clearing with uniform prices and corresponding issues in the presence of indivisibilities. Then we propose the new ‘primal-dual framework’ which essentially extends previous results [a,b] and enables to derive efficient (state-of-the-art) algorithmic approaches to the classical welfare optimization problem [a] or to consider economic issues of interest for stakeholders, such as the minimization of opportunity costs of paradoxically rejected block orders [b]. We also present numerical results to compare different tradeoffs which occur in those non-convex auctions (welfare, opportunity costs, traded volume).

Bibliography

[a] “A new formulation of the European day-ahead electricity market problem and its algorithmic consequences”, Mehdi Madani and Mathieu Van Vyve , CORE Discussion Paper 2013/74, December 2013, Louvain-La-Neuve. URL: http://www.uclouvain.be/cps/ucl/doc/core/documents/coredp2013_74web.pdf (revised version accepted for publication available soon)
[b] “Minimizing opportunity costs of paradoxically rejected block orders in European day-ahead electricity markets”, Mehdi Madani and Mathieu Van Vyve, European Energy Market (EEM), 2014 11th International Conference on the, 2014. DOI: http://dx.doi.org/10.1109/EEM.2014.6861237
[c] “Strict linear prices in non-convex European day-ahead electricity markets”, Alexander Martin, Johannes C. Müller, Sebastian Pokutta, 2013, Optimization Methods and Software Vol 29 Issue 1. DOI: http://dx.doi.org/10.1080/10556788.2013.823544
[d] “Modeling price-based decisions in advanced electricity markets”, Zak et. all, European Energy Market (EEM), 2012 9th International Conference on the, 2012, DOI: http://dx.doi.org/10.1109/EEM.2012.6254813
[e] PCR: http://www.epexspot.com/en/market-coupling/pcr. EUPHEMIA: http://static.epexspot.com/document/27917/Euphemia%3A%20Public%20description%20-%20Nov%202013.pdf

We consider a Large-Scale Unit Commitment Problem (LSUCP) arising in the strategic planning of energy networks, as a joint project with a major industrial research centre in Italy.
The aim of the project is to simulate optimal production schedules for a set of thermal and hydroelectric plants, located in one or more countries, over a time horizon spanning from a few months to one year, with a hour-by-hour resolution.
We propose two mixed-integer linear programming (MILP) formulations for our LSUCP. The first one involves a number of variables and constraints that is polynomial in the instance size (compact formulation in the remainder). The second one is obtained by reformulation through the Dantzig-Wolfe decomposition principle, and includes a number of variables that grows combinatorially in the number of thermal plants (extended formulation in the remainder).
Due to the size of real-world instances and the level of detail of our models, the direct optimization of these formulations via general-purpose solvers is impractical.
Therefore, we first review and improve our matheuristic, based on the compact formulation, which exploits aggregation, continuous relaxations and a spatial decompositions to obtain high quality approximated solutions in affordable time.
Then we propose an exact algorithm in which the continuous relaxation of the extended formulation is solved by means of column generation techniques. At each column generation iteration, the size of the set of columns potentially belonging to an optimal integer solution is estimated during pricing. If such a size is limited enough, these columns are enumerated using constraint programming techniques, and the resulting MILP is solved. Otherwise, column generation is iterated.
To effectively solve the pricing subproblems, we propose both MILP formulations and ad-hoc dynamic programming algorithms, extending those from the literature.
Finally, we compare the performances of our methods with a hybrid algorithm working on the compact formulation: starting with its continuous relaxation, a core set of critical variables is selected, integrality conditions are restored on the variables in the core, and the resulting MILP is solved; if the solution is integral, then global optimality is reached; otherwise, the core is enlarged and the process iterated.
Experimental results on a real-world dataset, drawn from the Italian energy network, reveal that our framework is consistently effective.

In many optimization problems over urban distribution networks, the decision maker faces the combined challenge of nonlinear constraints, system parameters affected by uncertainty, and the scale of the underlying network. However, such problems also exhibit structure, notably sparsity, which can be exploited in order to improve the scalability of polynomial optimization solvers. On challenging problems including AC optimal power flow and pressure management in water networks, we demonstrate an approach, which exploits sparsity and strengthened low-order instances of SDP hierarchies.