Refine
Keywords
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 the flow between two designated nodes. We show that these problems can be solved for the single source and sink case by reducing the network to a single arc. However, if we additionally consider switches that allow to force the flow to 0 and decouple the potentials, these problems are NP-hard. Nevertheless, for particular series-parallel networks, one can use algorithms for the subset sum problem. Moreover, applying network presolving based on generalized series-parallel structures allows to significantly reduce the size of realistic energy networks.
In this paper, we study the transient optimization of gas networks, focusing in particular on maximizing the storage capacity of the network. We include nonlinear gas physics and active elements such as valves and compressors, which due to their switching lead to discrete decisions. The former is described by a model derived from the Euler equations that is given by a coupled system of nonlinear parabolic partial differential equations (PDEs). We tackle the resulting mathematical optimization problem by a first-discretize-then-optimize approach. To this end, we introduce a new discretization of the underlying system of parabolic PDEs and prove well-posedness for the resulting nonlinear discretized system. Endowed with this discretization, we model the problem of maximizing the storage capacity as a non-convex mixed-integer nonlinear problem (MINLP). For the numerical solution of the MINLP, we algorithmically extend a well-known relaxation approach that has already been used very successfully in the field of stationary gas network optimization. This method allows us to solve the problem to global optimality by iteratively solving a series of mixed-integer problems (MIPs). Finally, we present two case studies that illustrate the applicability of our approach.
We study a simplistic model of instationary gas flows consisting of a sequence of k stationary gas flows. We present efficiently solvable cases and NP-hardness results, establishing complexity gaps between stationary and instationary gas flows (already for k=2) as well as between instationary gas s-t-flows and instationary gas b-flows.
We investigate the problem of scheduling the maintenance
of edges in a network, motivated by the goal of minimizing outages in
transportation or telecommunication networks. We focus on maintaining
connectivity between two nodes over time; for the special case of path
networks, this is related to the problem of minimizing the busy time of
machines.
We show that the problem can be solved in polynomial time in arbitrary
networks if preemption is allowed. If preemption is restricted to integral
time points, the problem is NP-hard and in the non-preemptive case
we give strong non-approximability results. Furthermore, we give tight
bounds on the power of preemption, that is, the maximum ratio of the
values of non-preemptive and preemptive optimal solutions.
Interestingly, the preemptive and the non-preemptive problem can be
solved efficiently on paths, whereas we show that mixing both leads to a
weakly NP-hard problem that allows for a simple 2-approximation.
In the
Steiner Forest
problem, we are given a graph and a collection of source-sink
pairs, and the
goal is to find a subgraph of minimum total length such that all
pairs are connected. The problem is
APX-Hard and can be
2
-approximated by, e.g., the elegant primal-dual algorithm
of Agrawal, Klein, and
Ravi from 1995.
We give a local-search-based constant-factor approximati
on for the problem. Local search brings in
new techniques to an area that has for long not seen any improv
ements and might be a step towards
a combinatorial algorithm for the more general survivable n
etwork design problem. Moreover, local
search was an essential tool to tackle the dynamic MST/Stein
er Tree problem, whereas dynamic Steiner
Forest is still wide open.
It is easy to see that any constant factor local search algori
thm requires steps that add/drop many edges
together. We propose natural local moves which, at each step
, either (a) add a shortest path in the current
graph and then drop a bunch of inessential edges, or (b) add a s
et of edges to the current solution. This
second type of moves is motivated by the potential function w
e use to measure progress, combining the
cost of the solution with a penalty for each connected compon
ent. Our carefully-chosen local moves and
potential function work in tandem to eliminate bad local min
ima that arise when using more traditional
local moves.
Our analysis first considers the case where the local optimum
is a single tree, and shows optimality w.r.t.
moves that add a single edge (and drop a set of edges) is enough
to bound the locality gap. For the
general case, we show how to “project” the optimal solution o
nto the different trees of the local optimum
without incurring too much cost (and this argument uses opti
mality w.r.t. both kinds of moves), followed
by a tree-by-tree argument. We hope both the potential funct
ion, and our analysis techniques will be
useful to develop and analyze local-search algorithms in ot
her contexts.
We propose a theoretical framework to capture incremental s
olutions to cardinality con-
strained maximization problems. The defining characterist
ic of our framework is that the
cardinality/support of the solution is bounded by a value
k
∈
N
that grows over time, and
we allow the solution to be extended one element at a time. We i
nvestigate the best-possible
competitive ratio of such an incremental solution, i.e., th
e worst ratio over all
k
between the
incremental solution after
k
steps and an optimum solution of cardinality
k
. We define a
large class of problems that contains many important cardin
ality constrained maximization
problems like maximum matching, knapsack, and packing/cov
ering problems. We provide a
general 2
.
618-competitive incremental algorithm for this class of pr
oblems, and show that no
algorithm can have competitive ratio below 2
.
18 in general.
In the second part of the paper, we focus on the inherently inc
remental greedy algorithm
that increases the objective value as much as possible in eac
h step. This algorithm is known
to be 1
.
58-competitive for submodular objective functions, but it
has unbounded competitive
ratio for the class of incremental problems mentioned above
. We define a relaxed submod-
ularity condition for the objective function, capturing pr
oblems like maximum (weighted)
(
b
-)matching and a variant of the maximum flow problem. We show t
hat the greedy algo-
rithm has competitive ratio (exactly) 2
.
313 for the class of problems that satisfy this relaxed
submodularity condition.
Note that our upper bounds on the competitive ratios transla
te to approximation ratios
for the underlying cardinality constrained problems.
We study a natural generalization of the maximum weight
many-to-one matching problem. We are given an undirected bipartite
graph G = (A∪P,E) with weights on the edges in E, and with lower and
upper quotas on the vertices in P. We seek a maximum weight many-to-one
matching satisfying two sets of constraints: vertices in A are incident
to at most one matching edge, while vertices in P are either unmatched or
they are incident to a number of matching edges between their lower and
upper quota. This problem, which we call maximum weight many-to-one
matching with lower and upper quotas (wmlq), has applications to the
assignment of students to projects within university courses, where there
are constraints on the minimum and maximum numbers of students that
must be assigned to each project.
In this paper, we provide a comprehensive analysis of the complexity
of wmlq from the viewpoints of classical polynomial time algorithms,
fixed-parameter tractability, as well as approximability. We draw the
line between NP-hard and polynomially tractable instances in terms of
degree and quota constraints and provide efficient algorithms to solve
the tractable ones. We further show that the problem can be solved in
polynomial time for instances with bounded treewidth; however, the corresponding
runtime is exponential in the treewidth with the maximum
upper quota u_max as basis, and we prove that this dependence is necessary
unless FPT = W[1]. The approximability of wmlq is also discussed:
we present an approximation algorithm for the general case with performance
guarantee umax + 1, which is asymptotically best possible unless
P = NP. Finally, we elaborate on how most of our positive results carry
over to matchings in arbitrary graphs with lower quotas.