Monotonicity of Dissipative Flow Networks Renders Robust Maximum Profit Problem Tractable: General Analysis and Application to Natural Gas Flows

We consider general, steady, balanced flows of a commodity over a network where an instance of the network flow is characterized by edge flows and nodal potentials. Edge flows in and out of a node are assumed to be conserved, thus representing standard network flow relations. The remaining freedom in the flow distribution over the network is constrained by potentials so that the difference of potentials at the head and the tail of an edge is expressed as a nonlinear function of the edge flow. We consider networks with nodes divided into three categories: sources that inject flows into the network for a certain cost, terminals which buy the flow at a fixed price and internal customers each withdrawing an uncertain amount of flow, which has a priority and thus it is not priced. Our aim is to operate the network such that the profit, i.e. amount of flow sold to terminals minus cost of injection, is maximized, while maintaining the potentials within prescribed bounds. We also require that the operating point is robust with respect to the uncertainty of customers withdrawals. In this setting we prove that potentials are monotonic functions of the withdrawals. This observation enables us to replace in the maximum profit optimization infinitely many nodal constraints, each representing a particular value of withdrawal uncertainty, by only two constraints representing the cases where all nodes with uncertainty consume their minimum and maximum amounts respectively. We illustrate this general result on example of the natural gas transmission network. In this enabling example gas withdrawals by consumers are assumed uncertain, the potentials are gas pressures squared, the potential drop functions are bilinear in the flow and its intensity with an added tunable factor representing compression.

Learning Planar Ising Models

Inference and learning of graphical models are both well-studied problems in statistics and machine learning that have found many applications in science and engineering. However, exact inference is intractable in general graphical models, which suggests the problem of seeking the best approximation to a collection of random variables within some tractable family of graphical models. In this paper, we focus on the class of planar Ising models, for which exact inference is tractable using techniques of statistical physics. Based on these techniques and recent methods for planarity testing and planar embedding, we propose a simple greedy algorithm for learning the best planar Ising model to approximate an arbitrary collection of binary random variables (possibly from sample data). Given the set of all pairwise correlations among variables, we select a planar graph and optimal planar Ising model defined on this graph to best approximate that set of correlations. We demonstrate our method in simulations and for the application of modeling senate voting records.

Linear Programming based Detectors for Two-Dimensional Intersymbol Interference Channels

We present and study linear programming based detectors for two-dimensional intersymbol interference channels. Interesting instances of two-dimensional intersymbol interference channels are magnetic storage, optical storage and Wyners cellular network model. We show that the optimal maximum a posteriori detection in such channels lends itself to a natural linear programming based sub-optimal detector. We call this the Pairwise linear program detector. Our experiments show that the Pairwise linear program detector performs poorly. We then propose two methods to strengthen our detector. These detectors are based on systematically enhancing the Pairwise linear program. The first one, the Block linear program detector adds higher order potential functions in an {em exhaustive} manner, as constraints, to the Pairwise linear program detector. We show by experiments that the Block linear program detector has performance close to the optimal detector. We then develop another detector by {em adaptively} adding frustrated cycles to the Pairwise linear program detector. Empirically, this detector also has performance close to the optimal one and turns out to be less complex then the Block linear program detector.

Learning Planar Ising Models

Inference and learning of graphical models are both well-studied problems in statistics and machine learning that have found many applications in science and engineering. However, exact inference is intractable in general graphical models, which suggests the problem of seeking the best approximation to a collection of random variables within some tractable family of graphical models. In this paper, we focus our attention on the class of planar Ising models, for which inference is tractable using techniques of statistical physics [Kac and Ward; Kasteleyn]. Based on these techniques and recent methods for planarity testing and planar embedding [Chrobak and Payne], we propose a simple greedy algorithm for learning the best planar Ising model to approximate an arbitrary collection of binary random variables (possibly from sample data). Given the set of all pairwise correlations among variables, we select a planar graph and optimal planar Ising model defined on this graph to best approximate that set of correlations. We demonstrate our method in some simulations and for the application of modeling senate voting records.

A Majorization-Minimization Approach to Design of Power Transmission Networks

We propose an optimization approach to design cost-effective electrical power transmission networks. That is, we aim to select both the network structure and the line conductances (line sizes) so as to optimize the trade-off between network efficiency (low power dissipation within the transmission network) and the cost to build the network. We begin with a convex optimization method based on the paper ``Minimizing Effective Resistance of a Graph [Ghosh, Boyd & Saberi]. We show that this (DC) resistive network method can be adapted to the context of AC power flow. However, that does not address the combinatorial aspect of selecting network structure. We approach this problem as selecting a subgraph within an over-complete network, posed as minimizing the (convex) network power dissipation plus a non-convex cost on line conductances that encourages sparse networks where many line conductances are set to zero. We develop a heuristic approach to solve this non-convex optimization problem using: (1) a continuation method to interpolate from the smooth, convex problem to the (non-smooth, non-convex) combinatorial problem, (2) the majorization-minimization algorithm to perform the necessary intermediate smooth but non-convex optimization steps. Ultimately, this involves solving a sequence of convex optimization problems in which we iteratively reweight a linear cost on line conductances to fit the actual non-convex cost. Several examples are presented which suggest that the overall method is a good heuristic for network design. We also consider how to obtain sparse networks that are still robust against failures of lines and/or generators.

Orbit-Product Representation and Correction of Gaussian Belief Propagation

We present a new view of Gaussian belief propagation (GaBP) based on a representation of the determinant as a product over orbits of a graph. We show that the GaBP determinant estimate captures totally backtracking orbits of the graph and consider how to correct this estimate. We show that the missing orbits may be grouped into equivalence classes corresponding to backtrackless orbits and the contribution of each equivalence class is easily determined from the GaBP solution. Furthermore, we demonstrate that this multiplicative correction factor can be interpreted as the determinant of a backtrackless adjacency matrix of the graph with edge weights based on GaBP. Finally, an efficient method is proposed to compute a truncated correction factor including all backtrackless orbits up to a specified length.

Exactness of Belief Propagation for Some Graphical Models with Loops

It is well known that an arbitrary graphical model of statistical inference defined on a tree, i.e. on a graph without loops, is solved exactly and efficiently by an iterative Belief Propagation (BP) algorithm convergent to unique minimum of the so-called Bethe free energy functional. For a general graphical model on a loopy graph the functional may show multiple minima, the iterative BP algorithm may converge to one of the minima or may not converge at all, and the global minimum of the Bethe free energy functional is not guaranteed to correspond to the optimal Maximum-Likelihood (ML) solution in the zero-temperature limit. However, there are exceptions to this general rule, discussed in cite{05KW} and cite{08BSS} in two different contexts, where zero-temperature version of the BP algorithm finds ML solution for special models on graphs with loops. These two models share a key feature: their ML solutions can be found by an efficient Linear Programming (LP) algorithm with a Totally-Uni-Modular (TUM) matrix of constraints. Generalizing the two models we consider a class of graphical models reducible in the zero temperature limit to LP with TUM constraints. Assuming that a gedanken algorithm, g-BP, funding the global minimum of the Bethe free energy is available we show that in the limit of zero temperature g-BP outputs the ML solution. Our consideration is based on equivalence established between gapless Linear Programming (LP) relaxation of the graphical model in the $Tto 0$ limit and respective LP version of the Bethe-Free energy minimization.

Reducing the Error Floor

We discuss how the loop calculus approach of [Chertkov, Chernyak 06], enhanced by the pseudo-codeword search algorithm of [Chertkov, Stepanov 06] and the facet-guessing idea from [Dimakis, Wainwright 06], improves decoding of graph based codes in the error-floor domain. The utility of the new, Linear Programming based, decoding is demonstrated via analysis and simulations of the model $[155,64,20]$ code.