ZIB-Report
Refine
Year of publication
- 2017 (76) (remove)
Document Type
- ZIB-Report (76)
Keywords
- maximum-weight connected subgraph (2)
- metastability (2)
- mixed-integer programming (2)
- reaction coordinate (2)
- transfer operator (2)
- transition manifold (2)
- 2D distance map (1)
- Adaptive Importance Sampling (1)
- Algorithm Analysis (1)
- Amira (1)
Institute
- Mathematical Optimization (35)
- Numerical Mathematics (22)
- Mathematical Optimization Methods (14)
- Visual Data Analysis (13)
- Visual and Data-centric Computing (13)
- Mathematics of Transportation and Logistics (7)
- Computational Medicine (5)
- Digital Data and Information for Society, Science, and Culture (5)
- Energy Network Optimization (4)
- Therapy Planning (4)
17-60
Mixed integer linear programming (MIP) is a general form to model combinatorial optimization problems and has many industrial applications. The performance of MIP solvers has improved tremendously in the last two decades and these solvers have been used to solve many real-word problems. However, against the backdrop of modern computer technology, parallelization is of pivotal importance. In this way, ParaSCIP is the most successful parallel MIP solver in terms of solving previously unsolvable instances from the well-known benchmark instance set MIPLIB by using supercomputers. It solved two instances from MIPLIB2003 and 12 from MIPLIB2010 for the first time to optimality by using up to 80,000 cores on supercomputers. ParaSCIP has been developed by using the Ubiquity Generator (UG) framework, which is a general software package to parallelize any state-of-the-art branch-and-bound based solver. This paper discusses 7 years of progress in parallelizing branch-and-bound solvers with UG.
17-58
PIPS-SBB is a distributed-memory parallel solver with a scalable data distribution paradigm. It is designed to solve MIPs with a dual-block angular structure, which is characteristic of deterministic-equivalent Stochastic Mixed-Integer Programs (SMIPs). In this paper, we present two different parallelizations of Branch & Bound (B&B), implementing both as extensions of PIPS-SBB, thus adding an additional layer of parallelism. In the first of the proposed frameworks, PIPS-PSBB, the coordination and load-balancing of the different optimization workers is done in a decentralized fashion. This new framework is designed to ensure all available cores are processing the most promising parts of the B&B tree. The second, ug[PIPS-SBB,MPI], is a parallel implementation using the Ubiquity Generator (UG), a universal framework for parallelizing B&B tree search that has been successfully applied to other MIP solvers. We show the effects of leveraging multiple levels of parallelism in potentially improving scaling performance beyond thousands of cores.
17-57
Generalized preprocessing techniques for Steiner tree and maximum-weight connected subgraph problems
(2017)
This article introduces new preprocessing techniques for the Steiner tree problem in graphs and one of its most popular relatives, the maximum-weight connected subgraph problem. Several of the techniques generalize previous results from the literature. The correctness of the new methods is shown, but also their NP-hardness is demonstrated. Despite this pessimistic worst-case complexity, several relaxations are discussed that are expected to allow for a strong practical efficiency of these techniques in strengthening both exact and heuristic solving approaches.
17-56
Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They often provide good feasible solutions early in the solving process and help to solve instances to optimality faster. In this paper, we present a scheme for primal start heuristics that can be executed without previous knowledge of an LP solution or a previously found integer feasible solution. It uses global structures available within MIP solvers to iteratively fix integer variables and propagate these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. If sufficiently many variables can be fixed that way, the resulting problem is solved as an LP and the solution is rounded. If the rounded solution did not provide a feasible solution already, a sub-MIP is solved for the neighborhood defined by the variable fixings performed in the first phase. The global structures help to define a neighborhood that is with high probability significantly easier to process while (hopefully) still containing good feasible solutions. We present three primal heuristics that use this scheme based on different global structures. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about three out of five instances and therewith help to improve several performance measures for MIP solvers, including the primal integral and the average solving time.
17-54
Open Access ist Grundlage und Voraussetzung für die Nachnutzbarkeit, Transparenz und freie Zugänglichkeit zu wissenschaftlichen Informationen, Forschungsergebnissen und Daten des kulturellen Erbes. Mit Bezug auf die vom Senat Berlin 2015 verabschiedete Open-Access-Strategie empfiehlt der Kooperative Bibliotheksverbund Berlin-Brandenburg (KOBV) seinen Bibliotheken praktische Maßnahmen zur Umsetzung von Open Access in den eigenen Einrichtungen und benennt Maßnahmen der KOBV-Zentrale zur Unterstützung seiner Mitgliedsbibliotheken im Zuge dieses Transformationsprozesses.
17-55
In this paper, we propose a new method for optimizing the blue noise characteristics of point sets. It is based on Procrustes analysis, a technique for adjusting shapes to each other by applying optimal elements of an appropriate transformation group. We adapt this technique to the problem at hand and introduce a very simple, efficient and provably convergent point set optimizer.
17-52
The article surveys and extends variational formulations of the thermodynamic free
energy and discusses their information-theoretic content from the perspective of mathematical statistics. We revisit the well-known Jarzynski equality for nonequilibrium free energy sampling within the framework of importance sampling and Girsanov change-of-measure transformations. The implications of the different variational formulations for designing efficient stochastic optimization and nonequilibrium simulation algorithms for computing free energies are discussed and illustrated.
17-51
In gradient-based methods for parabolic optimal control problems, it is necessary to solve both the state equation and a backward-in-time adjoint equation in each iteration of the optimization method. In order to facilitate fully parallel gradient-type and nonlinear conjugate gradient methods for the solution of such optimal control problems, we discuss the application of the parallel-in-time method PFASST to adjoint gradient computation. In addition to enabling time parallelism, PFASST provides high flexibility for handling nonlinear equations, as well as potential extra computational savings from reusing previous solutions in the optimization loop. The approach is demonstrated here for a model reaction-diffusion optimal control problem.
17-49
We investigate metastable dynamical systems subject to non-stationary forcing as they appear in molecular dynamics for systems driven by external fields. We show, that if the strength of the forcing is inversely proportional to the length of the slow metastable time scales of the unforced system, then the effective behavior of the forced system on slow time scales can be described by a low-dimensional reduced master equation. Our construction is explicit and uses the multiscale perturbation expansion method called two-timing, or method of multiple scales. The reduced master equation—a Markov state model—can be assembled by constructing two equilibrium Markov state models; one for the unforced system, and one for a slightly perturbed one.
17-48
Real world routing problems, e.g., in the airline industry or in public and rail transit, can feature complex non-linear cost functions. An important case are costs for crossing regions, such as countries or fare zones. We introduce the shortest path problem with crossing costs (SPPCC) to address such situations; it generalizes the classical shortest path problem and variants such as the resource constrained shortest path problem and the minimum label path problem. Motivated by an application in flight trajectory optimization with overflight costs, we focus on the case in which the crossing costs of a region depend only on the nodes used to enter or exit it. We propose an exact Two-Layer-Dijkstra Algorithm as well as a novel cost-projection linearization technique that approximates crossing costs by shadow costs on individual arcs, thus reducing the SPPCC to a standard shortest path problem. We evaluate all algorithms’ performance on real-world flight trajectory optimization instances, obtaining very good à posteriori error bounds.