## ZIB-Report

### Refine

#### Year of publication

#### Document Type

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

#### Keywords

- integer programming (33)
- KOBV (28)
- optimal control (27)
- Kooperativer Bibliotheksverbund Berlin-Brandenburg (24)
- mixed integer programming (23)
- Bibliotheksverbund (20)
- Integer Programming (17)
- Mixed Integer Programming (14)
- column generation (13)
- combinatorial optimization (12)

#### Institute

- ZIB Allgemein (909)
- Mathematical Optimization (342)
- Numerical Mathematics (175)
- Mathematics of Transportation and Logistics (57)
- Computational Medicine (55)
- Visual Data Analysis (55)
- Scientific Information (49)
- Mathematical Optimization Methods (35)
- Distributed Algorithms and Supercomputing (31)
- Computational Molecular Design (15)

18-05

The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. Although the different Steiner tree problem variants are usually strongly related, solution approaches employed so far have been prevalently problem-specific. Against this backdrop, the solver SCIP-Jack was created as a general-purpose framework that can be used to solve the classical Steiner tree problem and 11 of its variants. This versatility is achieved by transforming various problem variants into a general form and solving them by using a state-of-the-art MIP-framework. Furthermore, SCIP-Jack includes various newly developed algorithmic components such as preprocessing routines and heuristics. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances. After the introduction of SCIP-Jack at the 2014 DIMACS Challenge on Steiner problems, the overall performance of the solver has considerably improved. This article provides an overview on the current state.

18-03

We consider the use of randomised forward models and log-likelihoods within the Bayesian approach to inverse problems. Such random approximations to the exact forward model or log-likelihood arise naturally when a computationally expensive model is approximated using a cheaper stochastic surrogate, as in Gaussian process emulation (kriging), or in the field of probabilistic numerical methods. We show that the Hellinger distance between the exact and approximate Bayesian posteriors is bounded by moments of the difference between the true and approximate log-likelihoods. Example applications of these stability results are given for randomised misfit models in large data applications and the probabilistic solution of ordinary differential equations.

18-01

An algorithm based on a delayed constraint generation method for solving semi-infinite programs
for constructing minimax optimal designs for nonlinear models is proposed. The outer optimization level of the minimax
optimization problem is solved using a semidefinite programming based approach that requires
the design space be discretized. A nonlinear programming solver is then used to solve the inner program
to determine the combination of the parameters that yields the worst-case value of the design criterion.
The proposed algorithm is applied to find minimax optimal designs for the logistic model, the flexible 4-parameter
Hill homoscedastic model and the general nth order consecutive reaction model, and shows that it
(i) produces designs that compare well with minimax $D-$optimal designs obtained from semi-infinite programming method in the literature;
(ii) can be applied to semidefinite representable optimality criteria, that include the common A-, E-,G-, I- and D-optimality criteria;
(iii) can tackle design problems with arbitrary linear constraints on the weights; and
(iv) is fast and relatively easy to use.

18-02

We propose (Mixed Integer) Second Order Cone Programming formulations to find approximate and exact $D-$optimal designs for $2^k$
factorial experiments for Generalized Linear Models (GLMs). Locally optimal designs are addressed with Second Order Cone Programming
(SOCP) and Mixed Integer Second Order Cone Programming (MISOCP) formulations.
The formulations are extended for scenarios of parametric uncertainty employing the Bayesian framework for
\emph{log det} $D-$optimality criterion. A quasi Monte-Carlo sampling procedure based
on the Hammersley sequence is used for integrating the optimality criterion in the parametric region. The problems are solved in \texttt{GAMS}
environment using \texttt{CPLEX} solver. We demonstrate the application of the algorithm with the logistic, probit and complementary log-log models
and consider full and fractional factorial designs.

17-61

This article describes new features and enhanced algorithms made available in version 5.0 of the SCIP Optimization Suite. In its central component, the constraint integer programming solver SCIP, remarkable performance improvements have been achieved for solving mixed-integer linear and nonlinear programs. On MIPs, SCIP 5.0 is about 41 % faster than SCIP 4.0 and over twice as fast on instances that take at least 100 seconds to solve. For MINLP, SCIP 5.0 is about 17 % faster overall and 23 % faster on instances that take at least 100 seconds to solve. This boost is due to algorithmic advances in several parts of the solver such as cutting plane generation and management, a new adaptive coordination of large neighborhood search heuristics, symmetry handling, and strengthened McCormick relaxations for bilinear terms in MINLPs. Besides discussing the theoretical background and the implementational aspects of these developments, the report describes recent additions for the other software packages connected to SCIP, in particular for the LP solver SoPlex, the Steiner tree solver SCIP-Jack, the MISDP solver SCIP-SDP, and the parallelization framework UG.

17-73

Gas Network Benchmark Models
(2017)

The simulation of gas transportation networks becomes increasingly more important as its use-cases broadens to more complex applications. Classically, the purpose of the gas network was the transportation of predominantly natural gas from a supplier to the consumer for long-term scheduled volumes. With the rise of renewable energy sources, gas-fired power plants are often chosen to compensate for the fluctuating nature of the renewables, due to their on-demand power generation capability. Such an only short-term plannable supply and demand setting requires sophisticated simulations of the gas network prior to the dispatch to ensure the supply of all customers for a range of possible scenarios and to prevent damages to the
gas network. In this work we describe the modelling of gas networks and present benchmark systems to test implementations and compare new or extended models.

17-77

The identification of meaningful reaction coordinates plays a key role in the study of complex molecular systems whose essential dynamics is characterized by rare or slow transition events. In a recent publication, the authors identified a condition under which such reaction coordinates exist - the existence of a so-called transition manifold - and proposed a numerical method for their point-wise computation that relies on short bursts of MD simulations. This article represents an extension of the method towards practical applicability in computational chemistry. It describes an alternative computational scheme that instead relies on more commonly available types of simulation data, such as single long molecular trajectories, or the push-forward of arbitrary canonically-distributed point clouds. It is based on a Galerkin approximation of the transition manifold reaction coordinates, that can be tuned to individual requirements by the choice of the Galerkin ansatz functions. Moreover, we propose a ready-to-implement variant of the new scheme, that computes data-fitted, mesh-free ansatz functions directly from the available simulation data. The efficacy of the new method is demonstrated
on a realistic peptide system.

17-74

Given a time-dependent stochastic process with trajectories x(t) in a space $\Omega$, there may be sets such that the corresponding trajectories only very rarely cross the boundaries of these sets. We can analyze such a process in terms of metastability or coherence. Metastable sets M are defined in space $M\subset\Omega$, coherent sets $M(t)\subset\Omega$ are defined in space and time. Hence, if we extend the space by the time-variable t, coherent sets are metastable sets in $\Omega\times[0,\infty]$. This relation can be exploited, because there already exist spectral algorithms for the identification of metastable sets. In this article we show that these well-established spectral algorithms (like PCCA+) also identify coherent sets of non-autonomous dynamical systems. For the identification of coherent sets, one has to compute a discretization (a matrix T) of the transfer operator of the process using a space-timediscretization scheme. The article gives an overview about different time-discretization schemes and shows their applicability in two different fields of application.

17-69

The analysis of infeasibility plays an important role in solving satisfiability problems (SAT) and mixed integer programs (MIPs). In mixed integer programming, this procedure is called conflict analysis. So far, modern MIP solvers use conflict analysis only for propagation and improving the dual bound, i.e., fathoming nodes that cannot contain feasible solutions. In this short paper, we present a new approach which uses conflict information to improve the primal bound during a MIP solve. To derive new improving primal solutions we use a conflict driven diving heuristic called conflict diving that uses the information obtained by conflict analysis. Conflict diving pursues a twofold strategy. By using conflict information the new diving approach is guided into parts of the search space that are usually not explored by other diving heuristics. At the same time, conflict diving has a fail-fast-strategy to reduce the time spent if it cannot find a new primal solution. As a byproduct, additional valid conflict constraints can be derived, from which a MIP solver can gain benefit to improve the dual bound as well. To show the added-value of conflict diving within a MIP solver, conflict diving has been implemented within the non-commercial MIP solver SCIP. Experiments are carried out on general MIP instances from standard public test sets, like MIPLIB2010 or Cor@l.