Optimization and Inference for Physical Flows on Networks (17w5165)
Michael Chertkov (Los Alamos National Laboratory)
Daniel Bienstock (Columbia University)
Anatoly Zlotnik (Los Alamos National Laboratory)
Sidhant Misra (Los Alamos National Laboratory)
Marc Vuffray (Los Alamos National Laboratory)
The focus will be placed on inference,learning and optimization problems involving physical processes that occur over network systems. Some of the problems that we consider, such as optimization of electric power systems, are themselves mature fields under active investigation, while others are in an exploratory stage and have not yet been addressed by the mathematically oriented research community. All of the problems have important common features. They are (a) stated on large graphs/networks; (b) conditioned by physics-related constraints that are expressed through algebraic equations, ordinary or partial differential equations, or a mix; (c) require re-formulation to facilitate optimization; (d) depend on practical algorithmic solutions such as approximations or relaxations with analytical guarantees.
We expect that the workshop will result in discovery of new connections between the mathematical areas of dynamical systems, network science, control theory, optimization, and applied probability. Moreover, the purpose is to foster long-term collaborations that will result in scalable algorithms for practical problems that are motivated by very timely real-world engineering applications related to physics-governed flows on networks. We will give more specific views of the open problems and applications to be considered, and conclude by describing the anticipated interfaces of interaction among the mathematical fields.
Nonlinear Optimization of Uncertain Network Flows
The optimal allocation of flows and transport over networks has been studied from theoretical and computational perspectives for many decades. Universal objectives include the maximal utilization of capacity and minimization of economic cost, and the resulting network flow algorithms are prominent in operations research, with particular importance for transport problems. These problems often possess mathematical features that make it very challenging to design optimization algorithms that scale well with the size of the network, which we categorize broadly into i) large scale non-convex problems, ii) problems with a mix of discrete and continuous degrees of freedom or control, and iii) robust and stochastic optimization problems.
Recent advances in algorithms and software for non-linear optimization have enabled the solution of very large non-convex optimization problems. However, techniques for general non-linear optimization fail to take advantage of the special mathematical structures characteristic to particular problems. For example, the equations that represent physical network flows consist of the classical linear nodal conservation of mass, appended by additional physical (possibly non-linear) relations governing the flows on edges, which depend on the phenomena being modeled. For example, it has been shown recently special examples of such network flows, such as the AC power flow equations in a restricted domain or natural gas flows, allows for a variational representation in the form of an energy function. This guarantees that the network flow equations have a unique solution, but also one that can also be computed efficiently through convex optimization related methods. However, the use of an energy function to create an optimization algorithm in this way is still unexplored.
Open Problem: What properties of physical network flows allow for variational representation? When do they have unique and efficiently computable solution?
Open Problem: How to exploit the variational representation to obtain efficient algorithms for optimization problems involving physical networks?
Moreover, and as shown most recently by Krishnamurthy Dvijotham, Steven Low and co-authors, even when the energy function approach does not apply a very prominent technique from the monotone operator theory allows to characterize domains in the space of network flows or nodal potentials where power flow solutions are feasible. Open Problems: What is the largest domain, or set of domains, of the physical flow monotonicity? How to find these efficiently? What are other useful features that generalize or complement the notion of energy function or monotonicity? Discrete variables appear in physical network flow optimization problems that have discrete controls such as switches, as well as in expansion planning problems where the objective is to find the most economic addition of components and edges such that the resulting network satisfies some required criteria. The objective function and constraints can have sparsity patterns that obey the underlying graph of the network. Attempts have been made in the literature to exploit this property via the so-called optimization hierarchies such as the Semi-Definite Programming (SDP) hierarchy. Techniques inspired by statistical physics exist to cope with the computational complexity that arises in optimization problems on large graphical models that represent networks. These techniques are based on sophisticated mean-field approximations such as the TAP free energy or the belief-propagation (BP) algorithm. The latter is exact on tree networks, and for general loopy networks it enables us to design a hierarchy of linear programs with increasing complexity but better accuracy. These methods are relatively well understood and have been successfully applied by Marc Mezard and co-authors to solve discrete problems on graphs. However even if we can formally write the belief-propagation equations for problems with a mix of continuous and discrete variables, converting them into efficient implementable algorithms remains a challenge. Further, it may be possible to exploit properties of the flow network, including the underlying graph structure, to improve existing algorithms for mixed integer optimization for such systems.
Open Problem: Can we create systematic methods to solve Mixed-Integer-Non-Linear-Programming (MINLP) problems over flow networks by using Linear Programming-Belief Propagation (LP-BP) hierarchy?
Open Problem: Is it possible to exploit the natural separation of variables that exists in network expansion planning problems to accelerate classical Mixed Integer Programming algorithms such as Bender's Decomposition?
Open Problem: Can non-linear programming techniques be incorporated as heuristics to accelerate mixed integer program solution of network flow optimization problems with physical constraints?
Stochastic and robust optimization problems over physical network flows introduce an additional layer of complexity to the problems discussed above. The solution to a robust optimization problem must satisfy constraints characterized by a set of parameters that may take values in an uncertainty interval. This complexity can be described mathematically as the addition of a continuum of constraints to the non-robust version of the problem. Significant advances in the area of robust optimization have been made in the last couple of decades. General approaches rely on analytic reformulations when the objective and constraints have special algebraic structure (such as linear or quadratic), or on sampling/scenario based methods. Physical network flows possess a richer set of properties that may be exploited to obtain tractable reformulations for robust optimization problems. Recent results on the so-called dissipative flow networks have shown that such networks satisfy a certain monotone ordering property that enables a greatly simplified representation of robust maximal utilization problems. In stochastic optimization, complexity arises due to the difficulty of evaluating probabilities and the addition of further possibly non-convex constraints. Methods for evaluating probabilities of desired events over graphs are very well-explored, and MCMC/Gibbs sampling, numerical integration, and BP are some of the most prominent. Sophisticated variants of these exist to exploit network structure and analytic properties. The challenge arises in incorporating these advanced techniques into optimization algorithms, and there has been much less exploration in this direction in the published literature. For a given network, it is desirable to identify the models of noise and the optimization metrics that result in convex stochastic constraints. Recent work on the OPF problem by Dan Bienstock and collaborators explores this direction. It may be possible to use similar methods for more general physical network flows.
Open Problem: What properties of physical network flows enable simplification of robust optimization problems?
Open Problem: How can algorithms for computation of probabilities over graphs be efficiently incorporated within optimization problems?
Open Problem: What models for noise and optimization metrics preserve convexity of stochastic constraints?
Optimal Control of Dynamic Flows on Networks
The analytical and computational difficulty of network flow problems is amplified when the flows are unbalanced, i.e., when commodity inflows at origins and outflows at destinations are time-dependent. This introduces memory, or path-dependence into the physical description of controlled flows, which must be described using dynamic modeling with differential equations rather than purely algebraic ones. The resulting continuous mathematical models are described by ordinary and/or partial differential equations (ODEs or PDEs) that represent fluid flow or approximate the aggregated motion of discrete particles, and algebraic equations and integer variables may be involved as well. In particular, we propose to examine the control of large systems of nonlinear hyperbolic PDEs evolving on a collection of distributed domains connected in a network structure, which are coupled by Neumann-Kirchhoff boundary conditions, and are characterized by a large collection of time-dependent parameter and control input functions. The control policy may require a model-predictive aspect in order to ensure that box constraints on the state or control variables are satisfied, and should minimize a (possibly highly nonlinear) cost functional. Such PDE-constrained optimization over a highly multi-dimensional function space is in general is analytically intractable and computationally very challenging.
Recent studies by Pascal Van Hentenryck and co-authors have proposed computational solutions to such very large scale control problems for dynamic network flows, which involve spatial and temporal discretization to create a nonlinear program (NLP) with a finite decision space. The large networks in question are represented by weighted graphs with e.g. hundreds of nodes and edges, where the weights corresponds to edge length. The spatial discretization required to resolve the distributed (space-dependent) nature of the nonlinear dynamics on edges depends on the time-scales of interest, and could involve pseudospectral approximation. Consequently, the number of constraints and decision variables in the NLP depends on the temporal complexity of the parameter functions, such as those corresponding to commodity inflows and outflows.
Open problem: What model reductions or spatiotemporal discretizations of very large-scale PDE-constrained dynamic network flow optimization problems makes them tractable for fast computational solution, while retaining physical meaning and accuracy?
Open problem: In what ways can solution of the resulting NLP be accelerated by exploiting the network structure or relaxing certain constraints, while guaranteeing that the physical (dynamic PDE) constraints are satisfied exactly?
A further challenge to computational tractability arises through uncertainty or stochastic variability in the time-dependent commodity inflows and outflows, which constitute time-varying system parameters. It is desirable for flow control or routing policies to be feasible for any instance under such uncertainty. In the case of continuous dynamic flows, uncertainty in time-varying parameters requires adjoining a continuum of constraints to ensure feasibility of the optimization solution. The challenge then becomes to show that satisfaction for a finite number of appropriate scenarios will guarantee feasibility for an entire such uncountable ensemble of constraints.
Recent work by Munther Dahleh, Giacomo Como and co-authors suggested approaches to controlling uncertain network flows that sidestep the need for global optimization over a possibly non-convex landscape to control nonlinear dynamical flows by examining stability and robustness of distributed routing solutions that use local information. The methodology in these studies was enabled by demonstrating that the network flow dynamics in question were monotone control systems. Such so-called cooperative systems, which possess monotonicity properties with respect to certain input variables, have been investigated in the context of ordinary differential equation theory. We will investigate conditions to establish monotonicity properties for various classes of dynamic flows on networks described by coupled ODEs and/or or hyperbolic PDEs, as well as other (yet to be discovered) properties. The purpose is to reduce formulations for optimal control under uncertainty to the solution of simpler, deterministic problems.
Open problem: What properties do various models and formulations of dynamic flows on networks possess that can be leveraged to simplify optimal control problems for these systems?
Open problem: Can insight from robust optimization methods for steady-state network optimization problems be exploited to implement solutions for dynamic network flow optimization problems under uncertainty?
Inference and Learning for Dynamic Networks
Efficient inference and learning for complex interacting graphical models from large data sets is a long-standing problem in machine learning and statistical physics. These fields take fundamentally different approaches to predicting the properties or behaviors of these large systems. While machine learning techniques are characterized by an active use of the training data to learn correlations and model parameters for subsequent behavioral predictions using sampling from the examined model, a classical approach in physics consists in finding an appropriate reduced representation of the model and using it as an approximation scheme for describing the behavior of the system. There have been significant recent advances in theory and algorithms for machine learning, and with the advent of very large databases, the focus has shifted to developing algorithms that are scalable and efficiently utilize the data in its entirety. Usually, less emphasis is laid on simplifying/reducing the model representing the system, which in contrast has been at the core of the physics of complex systems.
Large scale physical flow networks give rise to inference and learning problems that call for combining both approaches. As an illustrative example, consider the problem of learning the response behavior of an ensemble of loads in electric distribution networks. Meaningful models with greatly reduced complexity may be obtained by physics based model-reduction methods. The modeling can and should also be made aware of the analytic properties that make them more amenable to algorithms from machine learning. Other such examples include learning the state of a transient gas pipeline network from discrete spatio-temporal measurements, and inferring the topology of electric distribution networks from sparse phase angle measurements.
Open Problem: How to develop model reduction techniques from physics for physical network flows and algorithms from machine learning in a combined way that leverages the strengths of both approaches?
Open problem: How does the introduction of time-dependence in the form of discrete-time difference or continuous differential dynamics influence the inference and learning on flow networks?
Points of Interaction
Addressing open nonlinear optimization problems for network flows under uncertainty requires perspectives from researchers in a broad variety of fields, including graph theory, optimization, and computer science. When the problem is extended to dynamic conditions, insight from specialists in applied mathematics (particularly PDE theory), dynamical systems, numerical analysis, optimization, and control theory is required. When learning and inference are included, the fields of machine learning, statistical physics, and applied probability are in play.
All of the above are mature fields with well-developed mathematical theory and computational algorithms in use for associated applications. However, no single approach is capable of addressing the above broadly posed open problems, which rather require reformulation and new mathematical tools to develop the interfaces along which the involved mathematical fields interact. For example, solutions for optimal control of network flows with edge dynamics governed by PDEs cannot be developed based on traditional numerical PDE techniques alone, or by using established optimization algorithms. Instead, the solutions will arise within the scope of dynamical systems and control theory, where these two usually separate mathematical areas may intersect.
In this workshop, we will address a number of applications within the framework of physical flow networks. In addition to long-standing problems in flow management of vehicle traffic and routing of information in telecommunications networks, there are several emerging challenges in gas transmission networks and the electric power grid that are receiving growing attention in the last several years. We provide one illustrative example for each system. The optimal control of dynamic flows of natural gas through large-scale transmission pipeline system, called the Dynamic Optimal Gas Flow (DOGF) problem, is motivated by the growing use of natural gas to fuel electrical power generators in North America and elsewhere, which has made securely maintaining reliable fuel supplies a pressing concern. The problem poses a unique combination of non-linear PDE governed dynamics and an underlying network structure that requires a jointly developed physics-based model reduction and non-linear network optimization algorithm. Increasing renewable penetration in the electric power grid within the last decade has significantly increased the intermittency and stochasticity of the system and ensuring system safety under uncertainty is a priority. The Chance Constrained Optimal Power Flow Problem (CC-OPF) which is a stochastic optimization problem that incorporates probabilistic system safety constraints into an economic generation dispatch problem is designed to address this issue. While the problem has been studied for linearized models of the power system and simple affine control policies, generalization to non-linear models such as the AC Power Flow model and general non-affine control policies requires new methods for computing marginal probabilities and optimization algorithms that can handle limits on the computed probabilities as constraints.
We expect that discussion of the above applied problems and the associated challenges will inspire new directions of investigation in the described areas of pure and applied mathematics.