Refine
Year of publication
Document Type
- ZIB-Report (103)
- Article (72)
- In Proceedings (30)
- Book chapter (13)
- ZIB-Annual (4)
- Other (4)
- In Collection (3)
- Book (2)
- Doctoral Thesis (2)
- Report (2)
Keywords
- Mixed Integer Programming (10)
- Integer Programming (6)
- IP (5)
- branch-and-cut (5)
- linear programming (5)
- mixed integer programming (5)
- Open Access (4)
- UMTS (4)
- branch-and-bound (4)
- mixed-integer programming (4)
Institute
- Mathematical Optimization (120)
- Applied Algorithmic Intelligence Methods (67)
- Mathematical Optimization Methods (45)
- ZIB Allgemein (22)
- Mathematical Algorithmic Intelligence (18)
- Digital Data and Information for Society, Science, and Culture (10)
- Energy Network Optimization (7)
- AI in Society, Science, and Technology (6)
- KOBV (4)
This paper describes how we solved 12 previously unsolved mixed-integer program-
ming (MIP) instances from the MIPLIB benchmark sets. To achieve these results we
used an enhanced version of ParaSCIP, setting a new record for the largest scale MIP
computation: up to 80,000 cores in parallel on the Titan supercomputer. In this paper
we describe the basic parallelization mechanism of ParaSCIP, improvements of the
dynamic load balancing and novel techniques to exploit the power of parallelization
for MIP solving. We give a detailed overview of computing times and statistics for
solving open MIPLIB instances.
SCIP-JACK is a customized, branch-and-cut based solver for Steiner tree and related problems. ug [SCIP-JACK, MPI] extends SCIP-JACK to a massively par- allel solver by using the Ubiquity Generator (UG) framework. ug [SCIP-JACK, MPI] was the only solver that could run on a distributed environment at the (latest) 11th DIMACS Challenge in 2014. Furthermore, it could solve three well-known open instances and updated 14 best known solutions to instances from the bench- mark libary STEINLIB. After the DIMACS Challenge, SCIP-JACK has been con- siderably improved. However, the improvements were not reflected on ug [SCIP- JACK, MPI]. This paper describes an updated version of ug [SCIP-JACK, MPI], especially branching on constrains and a customized racing ramp-up. Furthermore, the different stages of the solution process on a supercomputer are described in detail. We also show the latest results on open instances from the STEINLIB.
Current linear energy system models (ESM) acquiring to provide sufficient detail and reliability frequently bring along problems of both high intricacy and increasing scale. Unfortunately, the size and complexity of these problems often prove to be intractable even for commercial state-of-the-art linear programming solvers. This article describes an interdisciplinary approach to exploit the intrinsic structure of these large-scale linear problems to be able to solve them on massively parallel high-performance computers. A key aspect are extensions to the parallel interior-point solver PIPS-IPM originally developed for stochastic optimization problems. Furthermore, a newly developed GAMS interface to the solver as well as some GAMS language extensions to model block-structured problems will be described.
In the transition towards a pure hydrogen infrastructure, repurposing the existing natural gas infrastructure is considered. In this study, the maximal technically feasible injection of hydrogen into the existing German natural gas transmission network is analysed with respect to regulatory limits regarding the gas quality. We propose a transient tracking model based on the general pooling problem including linepack. The analysis is conducted using real-world hourly gas flow data on a network of about 10,000 km length.
This article discusses the Length-Constrained Cycle Partition Problem (LCCP), which constitutes a new generalization of the Travelling Salesperson Problem (TSP). Apart from nonnegative edge weights, the undirected graph in LCCP features a nonnegative critical length parameter for each vertex. A cycle partition, i.e., a vertex-disjoint cycle cover, is a feasible solution for LCCP if the length of each cycle is not greater than the critical length of each vertex contained in it. The goal is to find a feasible partition having a minimum number of cycles. Besides analyzing theoretical properties and developing preprocessing techniques, we propose an elaborate heuristic algorithm that produces solutions of good quality even for large-size instances. Moreover, we present two exact mixed-integer programming formulations (MIPs) for LCCP, which are inspired by well-known modeling approaches for TSP. Further, we introduce the concept of conflict hypergraphs, whose cliques yield valid constraints for the MIP models. We conclude with a discussion on computational experiments that we conducted using (A)TSPLIB-based problem instances. As a motivating example application, we describe a routing problem where a fleet of uncrewed aerial vehicles (UAVs) must patrol a given set of areas.
The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. While often a strong relationship between different Steiner tree problem variants can be observed, solution approaches employed so far have been prevalently problem specific. In contrast, this paper introduces a general purpose solver that can be used to solve both the classical Steiner tree problem and many of its variants without modification. This is achieved by transforming various problem variants into a general form and solving them using a state-of-the-art MIP-framework. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances.
In 2011, important priorities were set to realize green publications in the open access movement in Germany. With financial support from the German Research Foundation (DFG), libraries negotiated Alliance licenses with publishers that guarantee extensive open access rights. Authors of institutions, that have therewith access to licensed journals, can freely publish their articles immediately or after a short embargo period in a repository of their choice. However, authors hesitantly use these open access rights. Also libraries – as managers of institutional and subject based repositories and thus legitimated representatives for the authors – only rarely make use of these rights. The aim of DeepGreen is to make the majority of those publications available online. Together with publishers of the Alliance licenses, the project consortium wants to develop a nearly fully automated workflow that covers both the delivery of data, including the full texts, of the publishers, as well as the data transformation to the necessary import formats and the loading process into the repositories. An intermediate “publication router” will serve as a distribution platform. The DeepGreen metadata schema contains metadata properties describing a wide range of deliverable bibliographic metadata from the Alliance license publishers (most common standards are JATS and CrossRef XML) as well as its compliance with technical, quality and metadata standards of the repositories. The schema includes required metadata elements and optional properties providing additional information.The metadata schema is aligned to the OCLC repository best practices (“Best Practices for CONTENTdm and other OAI-PMH compliant repositories: creating sharable metadata”, URL: http://www.oclc.org/content/dam/support/wcdigitalcollectiongateway/MetadataBestPractices.pdf). The current version of the schema is subject to changes as the functional requirements and workflow practices are evolving during the project experiences and prototype production.
KOBV Jahresbericht 2015-2016
(2017)
Mit dem DFG-geförderten Projekt DeepGreen soll eine automatisierte, rechtssichere Lösung entwickelt werden, um Artikeldaten von wissenschaftlichen Verlagen abzuholen und anschließend, nach Ablauf etwaiger lizenzrechtlicher Embargofristen, an berechtigte Repositorien zu verteilen und somit in den Open Access zu überführen. Dabei liegt der Fokus auf den DFG-geförderten und überregional verhandelten Allianz-Lizenzen, mit spezieller Open-Access-Komponente.
Die vorliegende Handreichung richtet sich speziell an die Betreiber institutioneller Repositorien und stellt Empfehlungen und einen Workflow bereit, um eine erfolgreiche Veröffentlichung, der durch die DeepGreen-Datendrehscheibe zugeordneten Artikel, zu ermöglichen. Die Handreichung basiert auf den bisherigen Erfahrungen der DeepGreen-Projektbeteiligten.
Questionnaire for effective exchange of bibliographic metadata – current status of publishing houses
(2016)
The project DeepGreen aims to realise better usage of green open access publication rights with regard to Alliance Licenses in Germany (https://www.nationallizenzen.de/open-access). Together with publishers who offer Alliance Licenses and authorized libraries, the project group intends to develop a prototype of a nearly fully automated workflow that covers the delivery of data from the publishers, including the article full texts, as well as the process of loading data into the institutional repositories of licensees. Further information about the project can be found within ZIB-Report 15-58, urn:nbn:de:0297-zib-56799.
In order to become acquainted with publishers’ processes for exchanging documents and metadata, the project group developed a questionnaire for an online survey. The publishing of this questionnaire is intended to demonstrate relevant aspects of the issue (e. g. methods of data exchange, protocols and interfaces) and to foster reuse of valuable questionnaire elements. The XML-file can be reused as a template, the PDF-file reproduces the original survey layout.