Global Optimization

Invited Session

Time Slot: Wednesday Morning

Room: AUD_B

Chair: Fabio Schoen

A global optimization framework for resilient water distribution networks

Time: 9:00

Filippo Pecci (Imperial College London), Stoianov Ivan

Resilience and sustainability are key objectives for critical infrastructure systems, which society relies upon for water, energy, and food supply. Optimization has the potential to play a vital role in supporting the design and operation of next generation infrastructure systems, improving resilience, reducing CO2 emissions, and efficiently integrating renewable energy sources. The complexity of these large interconnected systems has grown to the level that modelling and optimization are needed to improve their resilience and sustainability in face of climate change, urbanisation, and fast growing population. This is especially relevant for optimal design-for-control of nonlinear network systems, where the flow through the network is driven by a potential, and the potential loss across a link is a nonlinear function of the flow rate. These optimization problems combine continuous decision variables (e.g. pipe flow rates), with discrete decision variables (e.g. location of control actuators). Together with nonconvex constraints modelling systems dynamics, they result in large-scale Mixed Integer Nonlinear Programs (MINLPs). Despite significant progress in optimization algorithms and availability of computational power, it is still not possible to solve most MINLPs that arise when considering large and complex nonlinear network systems.Water distribution networks (WDNs) are critical infrastructure facing unprecedented challenges due to increasing water demand, climate change, and more stringent economic and environmental constraints. The main operational objectives for water utilities include the reduction of water leaks, and the reduction of probability of pipe bursts. These objectives are achieved through pressure management, which is implemented by installing and operating pressure control valves. To benefit from advances in technological, modelling, and control solutions, it is necessary to simultaneously optimize both valve locations and their operational settings. The problem of optimal placement and operation of pressure control valves in WDNs belongs to the framework of optimal design-for-control of non-linear network systems. Hence, it poses significant computational challenges to optimization solvers. The results reported in this work show that off-the-shelf global optimization solvers can fail to compute feasible solutions for this optimal design-for-control problem. Therefore, we propose a tailored branch and bound algorithm relying on polyhedral relaxations of the potential loss constraints, optimization-based bound-tightening, and heuristics to generate good quality feasible solutions with bounds on their level of sub-optimality. The developed algorithm is implemented to optimally place and operate PCVs to minimize different operational objectives, including Average Zone Pressure (AZP) and Pressure Variability with the Zone (PVZ). The tailored branch and bound algorithm enables the joint optimization of location and operational settings of pressure control valves in WDNs. This allows water utilities to implement integrated and efficient schemes for pressure management, in order to minimize leakage and probability of pipe bursts. Finally, we discuss further work and possible extensions to the framework of multiobjective optimization and water quality management.

Fast Cluster Detection in Networks by First Order Optimization

Time: 9:20

Immanuel Bomze (University of Vienna), Rinaldi Francesco, Zeffiro Damiano

Cluster detection plays a fundamental role in the analysis of data. In this paper, we focus on the use of -defective clique models for network-based cluster detection and propose a nonlinear optimization approach that efficiently handles those models in practice. In particular, we introduce an equivalent continuous formulation for the problem under analysis, and we analyze some tailored variants of the Frank–Wolfe algorithm that enable us to quickly find maximal -defective cliques. The good practical behavior of those algorithmic tools, which is closely connected to their support identification properties, makes them very appealing in practical applications. The reported numerical results clearly show the effectiveness of the proposed approach.

Sharp and fast bounds for the Celis-Dennis-Tapia problem

Time: 9:40

Marco Locatelli (Università degli Studi di Parma), Consolini Luca

In the Celis-Dennis-Tapia (CDT) problem a quadratic function is minimized over a region defined by two strictly convex quadratic constraints. Recently, it has been proved that the problem can be solved in polynomial time. However, all known polynomial-time algorithms are computationally expensive, since the degree of the polynomial in the complexity results is rather high. Moerover, differently from other quadratic problems such as the classical trust region problem or the trust region problem with an additional linear inequality, no exact convex relaxation for the CDT problem is known. In this work we re-derive a necessary and sufficient optimality condition for the exactness of the dual Lagrangian bound (equivalent to the Shor relaxation bound in this case). Starting from such condition, we propose to strengthen the dual Lagrangian bound by adding one or two linear cuts to the Lagrangian relaxation. Such cuts are obtained from supporting hyperplanes of one of the two constraints. Thus, they are redundant for the original problem, but they are not for the Lagrangian relaxation. For the case of a single cut we also propose a procedure to detect the best possible cut, i.e., the one delivering the best possible bound. Interestingly, such best bound is computationally equivalent to the SOC-RLT bound proposed in [1], although up to now we do not have a theoretical proof of equivalence.The computational experiments show that the new bounds are effective and require limited computing times. In particular, one of the proposed bounds is exact for all but one of the 212 hard instances of the CDT problem presented in [1].

[1] S.Burer, K.M. Anstreicher, Second-oder-cone constraints for extended trust-region subproblems, SIAM J. Optim., 23(1), 432–451 (2013)

Random projections for semidefinite programming

Time: 10:00

Leo Liberti (LIX CNRS Ecole Polytechnique, Institut Polytechnique de Paris), Benedetto Manca, Pierre-Louis Poirion, Antoine Oustry

Random projections can reduce the dimensionality of point sets while keeping approximate congruence. Applying random projections to optimization problems raises many theoretical and computational issues. Most of the theoretical issues in the application of random projections to conic programming were addressed in [1]. This paper focuses on semidefinite programming.