Quantum Bridge Analytics II: Network Optimization and Combinatorial Chaining for Asset Exchange

Quantum Bridge Analytics relates to methods and systems for hybrid classical-quantum computing, and is devoted to developing tools for bridging classical and quantum computing to gain the benefits of their alliance in the present and enable enhanced practical application of quantum computing in the future. This is the second of a two-part tutorial that surveys … Read more

Autonomous traffic at intersections: an optimization-based analysis of possible time, energy, and CO2 savings

In the growing field of autonomous driving, traffic-light controlled intersections as the nodes of large traffic networks are of special interest. We want to analyze how much an optimized coordination of vehicles and infrastructure can contribute to a more efficient transit through these bottlenecks. In addition, we are interested in sensitivity of the results with … 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

Robust location-transportation problems with integer-valued demand

A Location-Transportation (LT) problem concerns designing a company’s distribution network consisting of one central warehouse with ample stock and multiple local warehouses for a long but finite time horizon. The network is designed to satisfy the demands of geographically dispersed customers for multiple items within given delivery time targets. The company needs to decide on … Read more

An integrated planning model in centralized power systems

In the context of centralized electricity markets, we propose an integrated planning model for power pricing and network expansion, which endogenizes the scaling costs from power losses. While the substitutability pattern between pricing and expansion has been overlooked in the power flow optimization literature, this becomes particularly relevant in centralized electricity markets (where the headquarters … Read more

A Solution Framework for Linear PDE-Constrained Mixed-Integer Problems

We present a general numerical solution method for control problems with PDE-defined state variables over a finite set of binary or continuous control variables. We show empirically that a naive approach that applies a numerical discretization scheme to the PDEs (and if necessary a linearization scheme) to derive constraints for a mixed-integer linear program (MILP) … 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

A Fast Max Flow Algorithm

In 2013, Orlin proved that the max flow problem could be solved in $O(nm)$ time. His algorithm ran in $O(nm + m^{1.94})$ time, which was the fastest for graphs with fewer than $n^{1.06}$ arcs. If the graph was not sufficiently sparse, the fastest running time was an algorithm due to King, Rao, and Tarjan. We … Read more

Casting light on the hidden bilevel combinatorial structure of the k-Vertex Separator problem

Given an undirected graph, we study the capacitated vertex separator problem which asks to find a subset of vertices of minimum cardinality, the removal of which induces a graph having a bounded number of pairwise disconnected shores (subsets of vertices) of limited cardinality. The problem is of great importance in the analysis and protection of … Read more

On Integer and Bilevel Formulations for the k-Vertex Cut Problem

The family of Critical Node Detection Problems asks for finding a subset of vertices, deletion of which minimizes or maximizes a predefined connectivity measure on the remaining network. We study a problem of this family called the k-vertex cut problem. The problems asks for determining the minimum weight subset of nodes whose removal disconnects a … Read more