### Refine

#### Document Type

- Preprint (34)
- Article (32)
- Conference Proceeding (5)
- Working Paper (2)
- Doctoral Thesis (1)
- Review (1)

#### Keywords

- Branch-and-cut (2)
- Combinatorial optimization (2)
- Mixed-Integer Nonlinear Optimization (2)
- Network (2)
- Networks (2)
- Semidefinite Programming (2)
- Stochastic Programming (2)
- condition number (2)
- error analysis (2)
- exponential stability (2)

#### Institute

- Friedrich-Alexander-Universität Erlangen-Nürnberg (43)
- Technische Universität Darmstadt (12)
- Technische Universität Berlin (11)
- Weierstraß-Institut für Angewandte Analysis und Stochastik (9)
- Universität Duisburg-Essen (5)
- Zuse-Institut Berlin (ZIB) (5)
- Humboldt-Universität zu Berlin (4)
- Aristotle University of Thessaloniki (1)
- RWTH Aachen University (1)
- Tilburg University (1)

- General Bounds for Incremental Maximization (2017)
- 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.

- A Local-Search Algorithm for Steiner Forest (2017)
- 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.

- Scheduling Maintenance Jobs in Networks (2017)
- 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.

- Algorithmic Results for Potential-Based Flows: Easy and Hard Cases (2017)
- 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.

- Total variation diminishing schemes in optimal control of scalar conservation laws (2017)
- In this paper, optimal control problems subject to a nonlinear scalar conservation law are studied. Such optimal control problems are challenging both at the continuous and at the discrete level since the control-to-state operator poses difficulties as it is, e.g., not differentiable. Therefore discretization of the underlying optimal control problem should be designed with care. Here the discretize-then-optimize approach is employed where first the full discretization of the objective function as well as the underlying PDE is considered. Then, the derivative of the reduced objective is obtained by using an adjoint calculus. In this paper total variation diminishing Runge-Kutta (TVD-RK) methods for the time discretization of such problems are studied. TVD-RK methods, also called strong stability preserving (SSP), are originally designed to preserve total variation of the discrete solution. It is proven in this paper that providing an SSP state scheme, is enough to ensure stability of the discrete adjoint. However requiring SSP for both discrete state and adjoint is too strong. Also approximation properties that the discrete adjoint inherits from the discretization of the state equation are studied. Moreover order conditions are derived. In addition, optimal choices with respect to CFL constant are discussed and numerical experiments are presented.

- Solving Mixed-Integer Nonlinear Programs using Adaptively Refined Mixed-Integer Linear Programs (2017)
- We propose a method for solving mixed-integer nonlinear programs (MINLPs) to global optimality by discretization of occuring nonlinearities. The main idea is based on using piecewise linear functions to construct mixed-integer linear program (MIP) relaxations of the underlying MINLP. In order to find a global optimum of the given MINLP we develope an iterative algorithm which solves MIP relaxations that are adaptively refined. We are able to give convergence results for a wide range of MINLPs requiring only continuous nonlinearities with bounded domains and an oracle computing maxima of the nonlinearities on their domain. Moreover, the practicalness of our approach is shown numerically by an application from the field of gas network optimization.

- Regular solutions of DAE hybrid systems and regularization techniques (2017)
- The solvability and regularity of hybrid differential-algebraic systems (DAEs) is studied, and classical stability estimates are extended to hybrid DAE systems. Different reasons for non-regularity are discussed and appropriate regularization techniques are presented. This includes a generalization of Filippov regularization in the case of so-called chattering. The results are illustrated by several numerical examples.

- Port-Hamiltonian descriptor systems (2017)
- The modeling framework of port-Hamiltonian systems is systematically extended to constrained dynamical systems (descriptor systems, differential-algebraic equations). A new algebraically and geometrically defined system structure is derived. It is shown that this structure is invariant under equivalence transformations, and that it is adequate also for the modeling of high-index descriptor systems. The regularization procedure for descriptor systems to make them suitable for simulation and control is modified to deal with the port-Hamiltonian structure. The relevance of the new structure is demonstrated with several examples.

- On structure preserving model reduction for damped wave propagation in transport networks (2017)
- We consider the discretization and subsequent model reduction of a system of partial differential-algebraic equations describing the propagation of pressure waves in a pipeline network. Important properties like conservation of mass, dissipation of energy, passivity, existence of steady states, and exponential stability can be preserved by an appropriate semi- discretization in space via a mixed finite element method and also during the further dimension reduction by structure preserving Galerkin projection which is the main focus of this paper. Krylov subspace methods are employed for the construction of the reduced models and we discuss modifications needed to satisfy certain algebraic compatibility conditions; these are required to ensure the well-posedness of the reduced models and the preservation of the key properties. Our analysis is based on the underlying infinite dimensional problem and its Galerkin approximations. The proposed algorithms therefore have a direct interpretation in function spaces; in principle, they are even applicable directly to the original system of partial differential-algebraic equations while the intermediate discretization by finite elements is only required for the actual computations. The performance of the proposed methods is illustrated with numerical tests and the necessity for the compatibility conditions is demonstrated by examples.

- Model reduction for systems with inhomogeneous initial conditions (2017)
- We consider the model reduction problem for linear time-invariant dynamical systems having nonzero (but otherwise indeterminate) initial conditions. Building upon the observation that the full system response is decomposable as a superposition of the response map for an unforced system having nontrivial initial conditions and the response map for a forced system having null initial conditions, we develop a new approach that involves reducing these component responses independently and then combining the reduced responses into an aggregate reduced system response. This approach allows greater flexibility and offers better approximation properties than other comparable methods.