Refine
Year of publication
Document Type
- ZIB-Report (40)
- In Proceedings (17)
- Article (11)
- In Collection (2)
- Book chapter (1)
- Master's Thesis (1)
Keywords
- constraint integer programming (10)
- cumulative constraint (6)
- mixed integer programming (6)
- constraint programming (5)
- MIP (4)
- Mixed Integer Programming (4)
- branch-and-cut (4)
- integer programming (4)
- Online Optimization (3)
- Pseudo-Boolean (3)
Institute
- Mathematical Optimization (61)
- Mathematical Optimization Methods (28)
- ZIB Allgemein (4)
- Digital Data and Information for Society, Science, and Culture (3)
- KOBV (2)
- Visual Data Analysis (2)
- Visual and Data-centric Computing (2)
- Applied Algorithmic Intelligence Methods (1)
- Computational Systems Biology (1)
- Numerical Mathematics (1)
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.
Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They help to reach optimality faster and provide good feasible solutions early in the solving process. In this paper, we present two new primal heuristics which take into account global structures available within MIP solvers to construct feasible solutions at the beginning of the solving process. These heuristics follow a large neighborhood search (LNS) approach and use global structures to define a neighborhood that is with high probability significantly easier to process while (hopefully) still containing good feasible solutions. The definition of the neighborhood is done by iteratively fixing variables and propagating these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. The neighborhood is solved as a sub-MIP and solutions are transferred back to the original problem. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about every third instance and therewith help to improve the average solving time.
Computing hardware has mostly thrashed out the physical limits for speeding up individual computing cores. Consequently, the main line of progress for new hardware is growing the number of computing cores within a single CPU. This makes the study of efficient parallelization schemes for computation-intensive algorithms more and more important. A natural precondition to achieving reasonable speedups from parallelization is maintaining a high workload of the available computational resources. At the same time, reproducibility and reliability are key requirements for software that is used in industrial applications. In this paper, we present the new parallelization concept for the state-of-the-art MIP solver FICO Xpress-Optimizer. MIP solvers like Xpress are expected to be deterministic. This inevitably results in synchronization latencies which render the goal of a satisfying workload a challenge in itself. We address this challenge by following a partial information approach and separating the concepts of simultaneous tasks and independent threads from each other. Our computational results indicate that this leads to a much higher CPU workload and thereby to an improved, almost linear, scaling on modern high-performance CPUs. As an added value, the solution path that Xpress takes is not only deterministic in a fixed environment, but also, to a certain extent, thread-independent. This paper is an extended version of Berthold et al. [Parallelization of the FICO Xpress-Optimizer, in Mathematical Software – ICMS 2016: 5th International Conference, G.-M. Greuel, T. Koch, P. Paule, and A. Sommere, eds., Springer International Publishing, Berlin, 2016, pp. 251–258] containing more detailed technical descriptions, illustrative examples and updated computational results.
Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They often provide good feasible solutions early and help to reduce the time needed to prove optimality. In this paper, we present a scheme for 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 first as an LP, and then as an auxiliary MIP if the rounded LP solution does not provide a feasible solution already. 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 60 % of the instances and by this, help to improve several performance measures for MIP solvers, including the primal integral and the average solving time.
The Ubiquity Generator (UG) is a general framework for the external parallelization of mixed integer programming (MIP) solvers. In this paper, we present ParaXpress, a distributed memory parallelization of the powerful commercial MIP solver FICO Xpress. Besides sheer performance, an important feature of Xpress is that it provides an internal parallelization for shared memory systems. When aiming for a best possible performance of ParaXpress on a supercomputer, the question arises how to balance the internal Xpress parallelization and the external parallelization by UG against each other. We provide computational experiments to address this question and we show computational results for running ParaXpress on a Top500 supercomputer, using up to 43,344 cores in parallel.
Mit DeepGreen wurde eine Infrastruktur aufgebaut und etabliert, die Zeitschriftenartikel von wissenschaftlichen Verlagen abholt und berechtigten Bibliotheken zur Veröffentlichung in ihren Repositorien sendet. DeepGreen unterstützt Bibliotheken als Dienstleister für Hochschulen, außeruniversitäre Einrichtungen und die dort tätigen Wissenschaftler*innen, Publikationen auf Open-Access-Repositorien frei zugänglich zu machen und fördert das Zusammenspiel von wissenschaftlichen Einrichtungen und Verlagen. DeepGreen wurde von Januar 2016 bis Juni 2021 von der Deutschen Forschungsgemeinschaft gefördert und wird nun vom Kooperativen Bibliotheksverbund Berlin-Brandenburg, von der Bayerischen Staatsbibliothek und von der Universitätsbibliothek Erlangen-Nürnberg in arbeitsteiliger Eigenleistung für zwei Jahre weiterbetrieben. Der vorliegende Beitrag beleuchtet vielfältige Aspekte bei der Realisierung von DeepGreen und geht auf die Perspektiven dieser zentralen Open-Access-Infrastruktur für deutsche Wissenschaftseinrichtungen ein.