An Exact Method for Nonlinear Network Flow Interdiction Problems

We study network flow interdiction problems with nonlinear and nonconvex flow models. The resulting model is a max-min bilevel optimization problem in which the follower’s problem is nonlinear and nonconvex. In this game, the leader attacks a limited number of arcs with the goal to maximize the load shed and the follower aims at minimizing … Read more

Deciding the Feasibility of a Booking in the European Gas Market is coNP-hard

We show that deciding the feasibility of a booking (FB) in the European entry-exit gas market is coNP-hard if a nonlinear potential-based flow model is used. The feasibility of a booking can be characterized by polynomially many load flow scenarios with maximum potential-difference, which are computed by solving nonlinear potential-based flow models. We use this … Read more

Combinatorial Acyclicity Models for Potential-based Flows

Potential-based flows constitute a basic model to represent physical behavior in networks. Under natural assumptions, the flow in such networks must be acyclic. The goal of this paper is to exploit this property for the solution of corresponding optimization problems. To this end, we introduce several combinatorial models for acyclic flows, based on binary variables … Read more

Computing Technical Capacities in the European Entry-Exit Gas Market is NP-Hard

As a result of its liberalization, the European gas market is organized as an entry-exit system in order to decouple the trading and transport of natural gas. Roughly summarized, the gas market organization consists of four subsequent stages. First, the transmission system operator (TSO) is obliged to allocate so-called maximal technical capacities for the nodes … Read more

Deciding Feasibility of a Booking in the European Gas Market on a Cycle is in P for the Case of Passive Networks

We show that the feasibility of a booking in the European entry-exit gas market can be decided in polynomial time on single-cycle networks that are passive, i.e., do not contain controllable elements. The feasibility of a booking can be characterized by solving polynomially many nonlinear potential-based flow models for computing so-called potential-difference maximizing load flow … Read more

Algorithmic Results for Potential-Based Flows: Easy and Hard Cases

Potential-based flows are an extension of classical network flows in which the flow on an arc is determined by the difference of the potentials of its incident nodes. Such flows are unique and arise, for example, in energy networks. Two important algorithmic problems are to determine whether there exists a feasible flow and to maximize … Read more