BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Daniel Bienstock

Daniel Bienstock appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.OCSystems and ControlData Structures and Algorithmsphysics.soc-phInformation TheoryMachine Learningmath.ITPerformance

Catalog footprint

What is connected

20works
8topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

20 published item(s)

preprint2022arXiv

Cardinality Minimization, Constraints, and Regularization: A Survey

We survey optimization problems that involve the cardinality of variable vectors in constraints or the objective function. We provide a unified viewpoint on the general problem classes and models, and give concrete examples from diverse application fields such as signal and image processing, portfolio selection, or machine learning. The paper discusses general-purpose modeling techniques and broadly applicable as well as problem-specific exact and heuristic solution approaches. While our perspective is that of mathematical optimization, a main goal of this work is to reach out to and build bridges between the different communities in which cardinality optimization problems are frequently encountered. In particular, we highlight that modern mixed-integer programming, which is often regarded as impractical due to commonly unsatisfactory behavior of black-box solvers applied to generic problem formulations, can in fact produce provably high-quality or even optimal solutions for cardinality optimization problems, even in large-scale real-world settings. Achieving such performance typically draws on the merits of problem-specific knowledge that may stem from different fields of application and, e.g., shed light on structural properties of a model or its solutions, or lead to the development of efficient heuristics; we also provide some illustrative examples.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Complexity, Exactness, and Rationality in Polynomial Optimization

We focus on rational solutions or nearly-feasible rational solutions that serve as certificates of feasibility for polynomial optimization problems. We show that, under some separability conditions, certain cubic polynomially constrained sets admit rational solutions. However, we show in other cases that it is NP Hard to detect if rational solutions exist or if they exist of any reasonable size. We extend this idea to various settings including near feasible, but super optimal solutions and detecting rational rays on which a cubic function is unbounded. Lastly, we show that in fixed dimension, the feasibility problem over a set defined by polynomial inequalities is in NP by providing a simple certificate to verify feasibility. We conclude with several related examples of irrationality and encoding size issues in QCQPs and SOCPs.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Principled Deep Neural Network Training through Linear Programming

Deep learning has received much attention lately due to the impressive empirical performance achieved by training algorithms. Consequently, a need for a better theoretical understanding of these problems has become more evident in recent years. In this work, using a unified framework, we show that there exists a polyhedron which encodes simultaneously all possible deep neural network training problems that can arise from a given architecture, activation functions, loss function, and sample-size. Notably, the size of the polyhedral representation depends only linearly on the sample-size, and a better dependency on several other network parameters is unlikely (assuming $P\neq NP$). Additionally, we use our polyhedral representation to obtain new and better computational complexity results for training problems of well-known neural network architectures. Our results provide a new perspective on training problems through the lens of polyhedral theory and reveal a strong structure arising from these problems.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Outer-Product-Free Sets for Polynomial Optimization and Oracle-Based Cuts

This paper introduces cutting planes that involve minimal structural assumptions, enabling the generation of strong polyhedral relaxations for a broad class of problems. We consider valid inequalities for the set $S\cap P$, where $S$ is a closed set, and $P$ is a polyhedron. Given an oracle that provides the distance from a point to $S$, we construct a pure cutting plane algorithm which is shown to converge if the initial relaxation is a polyhedron. These cuts are generated from convex forbidden zones, or $S$-free sets, derived from the oracle. We also consider the special case of polynomial optimization. Accordingly we develop a theory of \emph{outer-product-free} sets, where $S$ is the set of real, symmetric matrices of the form $xx^T$. All maximal outer-product-free sets of full dimension are shown to be convex cones and we identify several families of such sets. These families are used to generate strengthened intersection cuts that can separate any infeasible extreme point of a linear programming relaxation efficiently. Computational experiments demonstrate the promise of our approach.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Stochastic defense against complex grid attacks

We describe defense mechanisms designed to detect sophisticated grid attacks involving both physical actions (including load modification) and sensor output alteration, with the latter performed in a sparse manner and also so as to take into account grid response mechanisms (secondary response). The attacks aim to be both undetectable even under a full AC power flow model, and to hide equipment overload. We demonstrate that such attacks, while perhaps difficult to implement, nevertheless are easily computed even on systems with a large number of installed sensors, and can, in a static setting, successfuly hide large line overloads. Furthermore an attacker that understands the ongoing stochastic nature of sensor signals can extend the attack so as to remain effective for a nontrivial time period. To counteract such "ideal" or "perfect" attacks, we demonstrate a set of data-driven stochastic techniques to thwart the attacker and detect that an attack has taken place.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

LP approximations to mixed-integer polynomial optimization problems

We present a class of linear programming approximations for constrained optimization problems. In the case of mixed-integer polynomial optimization problems, if the intersection graph of the constraints has bounded tree-width our construction yields a class of linear size formulations that attain any desired tolerance. As a result, we obtain an approximation scheme for the "AC-OPF" problem on graphs with bounded tree-width. We also describe a more general construction for pure binary optimization problems where individual constraints are available through a membership oracle; if the intersection graph for the constraints has bounded tree-width our construction is of linear size and exact. This improves on a number of results in the literature, both from the perspective of formulation size and generality.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Robust linear control of nonconvex battery operation in transmission systems

We describe a robust multiperiod transmission plan- ning model including renewables and batteries, where battery output is used to partly offset renewable output deviations from forecast. A central element is a nonconvex battery operation model which is used with a robust model of forecast errors and a linear control scheme. Even though the problem is nonconvex we provide an efficient and theoretically valid algorithm that effectively solves cases on large transmission systems. Index Terms. Batteries, control, robust optimization.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Two-sided linear chance constraints and extensions

We examine the convexity and tractability of the two-sided linear chance constraint model under Gaussian uncertainty. We show that these constraints can be applied directly to model a larger class of nonlinear chance constraints as well as provide a reasonable approximation for a challenging class of quadratic chance constraints of direct interest for applications in power systems. With a view towards practical computations, we develop a second-order cone outer approximation of the two-sided chance constraint with provably small approximation error.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Unit Commitment with N-1 Security and Wind Uncertainty

As renewable wind energy penetration rates continue to increase, one of the major challenges facing grid operators is the question of how to control transmission grids in a reliable and a cost-efficient manner. The stochastic nature of wind forces an alteration of traditional methods for solving day-ahead and look-ahead unit commitment and dispatch. In particular, uncontrollable wind generation increases the risk of random component failures. To address these questions, we present an N-1 Security and Chance-Constrained Unit Commitment (SCCUC) that includes the modeling of generation reserves that respond to wind fluctuations and tertiary reserves to account for single component outages. The basic formulation is reformulated as a mixed-integer second-order cone problem to limit the probability of failure. We develop three different algorithms to solve the problem to optimality and present a detailed case study on the IEEE RTS-96 single area system. The case study assesses the economic impacts due to contingencies and various degrees of wind power penetration into the system and also corroborates the effectiveness of the algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Models for managing the impact of an epidemic

In this paper we consider robust models for emergency staff deployment in the event of a flu pandemic. We focus on managing critical staff levels at organizations that must remain operational during such an event, and develop methodologies for managing emergency resources with the goal of minimizing the impact of the pandemic. We present numerical experiments using realistic data to study the effectiveness of our approach. The underlying methodology is that of robust optimization; we model the problem as an infinite linear program which is approximately solved using a variant of Benders decomposition.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Robust Control of Cascading Power Grid Failures using Stochastic Approximation

Cascading failure of a power transmission system are initiated by an exogenous event that disable a set of elements (e.g., lines) followed by a sequence of interrelated failures (or more precisely, trips) of overloaded elements caused by the combination of physics of power flows in the changed system topology, and controls. Should this sequence accelerate it can lead to a large system failure with significant loss of load. In previous work we have analyzed deterministic algorithms that in an online fashion (i.e., responding to observed data) selectively shed load so as to minimize the amount of lost load at termination of the cascade. In this work we present a rigorous methodology for incorporating noise and model errors, based on the Sample Average Approximation methodology for stochastic optimization.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Vulnerability Analysis of Power Systems

Potential vulnerabilities in a power grid can be exposed by identifying those transmission lines on which attacks (in the form of interference with their transmission capabilities) causes maximum disruption to the grid. In this study, we model the grid by (nonlinear) AC power flow equations, and assume that attacks take the form of increased impedance along transmission lines. We quantify disruption in several different ways, including (a) overall deviation of the voltages at the buses from 1.0 per unit (p.u.), and (b) the minimal amount of load that must be shed in order to restore the grid to stable operation. We describe optimization formulations of the problem of finding the most disruptive attack, which are either nonlinear programing problems or nonlinear bilevel optimization problems, and describe customized algorithms for solving these problems. Experimental results on the IEEE 118-Bus system and a Polish 2383-Bus system are presented.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Efficient Synchronization Stability Metrics for Fault Clearing

Direct methods can provide rapid screening of the dynamical security of large numbers fault and contingency scenarios by avoiding extensive time simulation. We introduce a computationally-efficient direct method based on optimization that leverages efficient cutting plane techniques. The method considers both unstable equilibrium points and the effects of additional relay tripping on dynamical security\cite{01SH}. Similar to other direct methods, our approach yields conservative results for dynamical security, however, the optimization formulation potentially lends itself to the inclusion of additional constraints to reduce this conservatism.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Approximation Algorithms for the Incremental Knapsack Problem via Disjunctive Programming

In the incremental knapsack problem ($\IK$), we are given a knapsack whose capacity grows weakly as a function of time. There is a time horizon of $T$ periods and the capacity of the knapsack is $B_t$ in period $t$ for $t = 1, \ldots, T$. We are also given a set $S$ of $N$ items to be placed in the knapsack. Item $i$ has a value of $v_i$ and a weight of $w_i$ that is independent of the time period. At any time period $t$, the sum of the weights of the items in the knapsack cannot exceed the knapsack capacity $B_t$. Moreover, once an item is placed in the knapsack, it cannot be removed from the knapsack at a later time period. We seek to maximize the sum of (discounted) knapsack values over time subject to the capacity constraints. We first give a constant factor approximation algorithm for $\IK$, under mild restrictions on the growth rate of $B_t$ (the constant factor depends on the growth rate). We then give a PTAS for $\IIK$, the special case of $\IK$ with no discounting, when $T = O(\sqrt{\log N})$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Chance Constrained Optimal Power Flow: Risk-Aware Network Control under Uncertainty

When uncontrollable resources fluctuate, Optimum Power Flow (OPF), routinely used by the electric power industry to re-dispatch hourly controllable generation (coal, gas and hydro plants) over control areas of transmission networks, can result in grid instability, and, potentially, cascading outages. This risk arises because OPF dispatch is computed without awareness of major uncertainty, in particular fluctuations in renewable output. As a result, grid operation under OPF with renewable variability can lead to frequent conditions where power line flow ratings are significantly exceeded. Such a condition, which is borne by simulations of real grids, would likely resulting in automatic line tripping to protect lines from thermal stress, a risky and undesirable outcome which compromises stability. Smart grid goals include a commitment to large penetration of highly fluctuating renewables, thus calling to reconsider current practices, in particular the use of standard OPF. Our Chance Constrained (CC) OPF corrects the problem and mitigates dangerous renewable fluctuations with minimal changes in the current operational procedure. Assuming availability of a reliable wind forecast parameterizing the distribution function of the uncertain generation, our CC-OPF satisfies all the constraints with high probability while simultaneously minimizing the cost of economic re-dispatch. CC-OPF allows efficient implementation, e.g. solving a typical instance over the 2746-bus Polish network in 20 seconds on a standard laptop.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Synchronization-Aware and Algorithm-Efficient Chance Constrained Optimal Power Flow

One of the most common control decisions faced by power system operators is the question of how to dispatch generation to meet demand for power. This is a complex optimization problem that includes many nonlinear, non convex constraints as well as inherent uncertainties about future demand for power and available generation. In this paper we develop convex formulations to appropriately model crucial classes of nonlinearities and stochastic effects. We focus on solving a nonlinear optimal power flow (OPF) problem that includes loss of synchrony constraints and models wind-farm caused fluctuations. In particular, we develop (a) a convex formulation of the deterministic phase-difference nonlinear Optimum Power Flow (OPF) problem; and (b) a probabilistic chance constrained OPF for angular stability, thermal overloads and generation limits that is computationally tractable.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Power Grid Vulnerability to Geographically Correlated Failures - Analysis and Control Implications

We consider power line outages in the transmission system of the power grid, and specifically those caused by a natural disaster or a large scale physical attack. In the transmission system, an outage of a line may lead to overload on other lines, thereby eventually leading to their outage. While such cascading failures have been studied before, our focus is on cascading failures that follow an outage of several lines in the same geographical area. We provide an analytical model of such failures, investigate the model's properties, and show that it differs from other models used to analyze cascades in the power grid (e.g., epidemic/percolation-based models). We then show how to identify the most vulnerable locations in the grid and perform extensive numerical experiments with real grid data to investigate the various effects of geographically correlated outages and the resulting cascades. These results allow us to gain insights into the relationships between various parameters and performance metrics, such as the size of the original event, the final number of connected components, and the fraction of demand (load) satisfied after the cascade. In particular, we focus on the timing and nature of optimal control actions used to reduce the impact of a cascade, in real time. We also compare results obtained by our model to the results of a real cascade that occurred during a major blackout in the San Diego area on Sept. 2011. The analysis and results presented in this paper will have implications both on the design of new power grids and on identifying the locations for shielding, strengthening, and monitoring efforts in grid upgrades.

0 citations0 reviewsNo code linkedOpen access