## ZIB-Report

### Refine

#### Year of publication

#### Document Type

- ZIB-Report (1493)
- Doctoral Thesis (10)
- Habilitation (10)

#### Keywords

- KOBV (27)
- Bibliotheksverbund (20)
- Kooperativer Bibliotheksverbund Berlin-Brandenburg (17)
- integer programming (17)
- integer programming (16)
- mixed integer programming (16)
- optimal control (15)
- optimal control (12)
- branch-and-bound (10)
- Integer Programming (9)

#### Institute

- ZIB Allgemein (909)
- Mathematical Optimization (324)
- Numerical Mathematics (166)
- Mathematics of Transportation and Logistics (56)
- Computational Medicine (53)
- Visual Data Analysis (52)
- Scientific Information (48)
- Mathematical Optimization Methods (32)
- Distributed Algorithms and Supercomputing (29)
- Computational Molecular Design (15)

- 17-43
- Exploring the Numerics of Branch-and-Cut for Mixed Integer Linear Optimization (2017)
- We investigate how the numerical properties of the LP relaxations evolve throughout the solution procedure in a solver employing the branch-and-cut algorithm. The long-term goal of this work is to determine whether the effect on the numerical conditioning of the LP relaxations resulting from the branching and cutting operations can be effectively predicted and whether such predictions can be used to make better algorithmic choices. In a first step towards this goal, we discuss here the numerical behavior of an existing solver in order to determine whether our intuitive understanding of this behavior is correct.

- 17-44
- Integrating Lipschitzian Dynamical Systems using Piecewise Algorithmic Differentiation (2017)
- In this article we analyze a generalized trapezoidal rule for initial value problems with piecewise smooth right hand side \(F:R^n \to R^n\) based on a generalization of algorithmic differentiation. When applied to such a problem, the classical trapezoidal rule suffers from a loss of accuracy if the solution trajectory intersects a nondifferentiability of \(F\). The advantage of the proposed generalized trapezoidal rule is threefold: Firstly, we can achieve a higher convergence order than with the classical method. Moreover, the method is energy preserving for piecewise linear Hamiltonian systems. Finally, in analogy to the classical case we derive a third order interpolation polynomial for the numerical trajectory. In the smooth case the generalized rule reduces to the classical one. Hence, it is a proper extension of the classical theory. An error estimator is given and numerical results are presented.

- 17-40
- Structure-based Decomposition for Pattern-Detection for Railway Timetables (2017)
- We consider the problem of pattern detection in large scale railway timetables. This problem arises in rolling stock optimization planning in order to identify invariant sections of the timetable for which a cyclic rotation plan is adequate. We propose a dual reduction technique which leads to an decomposition and enumeration method. Computational results for real world instances demonstrate that the method is able to produce optimal solutions as fast as standard MIP solvers.

- 17-42
- Four good reasons to use an Interior Point solver within a MIP solver (2017)
- ``Interior point algorithms are a good choice for solving pure LPs or QPs, but when you solve MIPs, all you need is a dual simplex.'' This is the common conception which disregards that an interior point solution provides some unique structural insight into the problem at hand. In this paper, we will discuss some of the benefits that an interior point solver brings to the solution of difficult MIPs within FICO Xpress. This includes many different components of the MIP solver such as branching variable selection, primal heuristics, preprocessing, and of course the solution of the LP relaxation.

- 17-39
- Benefits and Limitations of Simplified Transient Gas Flow Formulations (2017)
- Although intensively studied in recent years, the optimization of the transient (time-dependent) control of large real-world gas networks is still out of reach for current state-of-the-art approaches. For this reason, we present further simplifications of the commonly used model, which lead to a linear description of the gas flow on pipelines. In an empirical analysis of real-world data, we investigate the properties of the involved quantities and evaluate the errors made by our simplification.

- 17-41
- Generic Construction and Efficient Evaluation of Network DAEs and Their Derivatives in the Context of Gas Networks (2017)
- We present a concept that provides an efficient description of differential-algebraic equations (DAEs) describing flow networks which provides the DAE function f and their Jacobians in an automatized way such that the sparsity pattern of the Jacobians is determined before their evaluation and previously determined values of f can be exploited. The user only has to provide the network topology and local function descriptions for each network element. The approach uses automatic differentiation (AD) and is adapted to switching element functions via the abs-normal-form (ANF).

- 17-38
- Demand-Driven Line Planning with Selfish Routing (2017)
- Bus rapid transit systems in developing and newly industrialized countries are often operated at the limits of passenger capacity. In particular, demand during morning and afternoon peaks is hardly or even not covered with available line plans. In order to develop demand-driven line plans, we use two mathematical models in the form of integer programming problem formulations. While the actual demand data is specified with origin-destination pairs, the arc-based model considers the demand over the arcs derived from the origin-destination demand. In order to test the accuracy of the models in terms of demand satisfaction, we simulate the optimal solutions and compare number of transfers and travel times. We also question the effect of a selfish route choice behavior which in theory results in a Braess-like paradox by increasing the number of transfers when system capacity is increased with additional lines.

- 17-36
- A Hypergraph Network Simplex Algorithm (2017)
- We describe a network simplex algorithm for the minimum cost flow problem on graph-based hypergraphs which are directed hypergraphs of a particular form occurring in railway rotation planning. The algorithm is based on work of Cambini, Gallo, and Scutellà who developed a hypergraphic generalization of the network simplex algorithm. Their main theoretical result is the characterization of basis matrices. We give a similar characterization for graph-based hypergraphs and show that some operations of the simplex algorithm can be done combinatorially by exploiting the underlying digraph structure.

- 17-35
- On the performance of NLP solvers within global MINLP solvers (2017)
- Solving mixed-integer nonlinear programs (MINLPs) to global optimality efficiently requires fast solvers for continuous sub-problems. These appear in, e.g., primal heuristics, convex relaxations, and bound tightening methods. Two of the best performing algorithms for these sub-problems are Sequential Quadratic Programming (SQP) and Interior Point Methods. In this paper we study the impact of different SQP and Interior Point implementations on important MINLP solver components that solve a sequence of similar NLPs. We use the constraint integer programming framework SCIP for our computational studies.

- 17-33
- Rational Solutions of Underdetermined Polynomial Equations (2017)
- In this paper we report on an application of computer algebra in which mathematical puzzles are generated of a type that had been widely used in mathematics contests by a large number of participants worldwide. The algorithmic aspect of our work provides a method to compute rational solutions of single polynomial equations that are typically large with 10^2 ... 10^5 terms and that are heavily underdetermined. It was possible to obtain this functionality by adding a number of new modules for a new type of splitting of equations to the existing package CRACK that is normally used to solve polynomial algebraic and differential systems of equations.