Refine
Year of publication
Document Type
- ZIB-Report (26)
- Article (13)
- In Proceedings (11)
- Bachelor's Thesis (1)
- Book chapter (1)
- Doctoral Thesis (1)
- Master's Thesis (1)
Is part of the Bibliography
- no (54)
Keywords
Existing planning approaches for onshore wind farm siting and network integration often do not meet minimum cost solutions or social and environmental considerations. In this paper, we develop an approach for the multi-objective optimization of turbine locations and their network connection using a Quota Steiner tree problem. Applying a novel transformation on a known directed cut formulation, reduction techniques, and heuristics, we design an exact solver that makes large problem instances solvable and outperforms generic MIP solvers. Although our case studies in selected regions of Germany show large trade-offs between the objective criteria of cost and landscape impact, small burdens on one criterion can significantly improve the other criteria. In addition, we demonstrate that contrary to many approaches for exclusive turbine siting, network integration must be simultaneously optimized in order to avoid excessive costs or landscape impacts in the course of a wind farm project. Our novel problem formulation and the developed solver can assist planners in decision making and help optimize wind farms in large regions in the future.
The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems—by using mathematical programming techniques. The main focus lies on sparse problem instances, although also dense ones can be solved. We enhance several algorithmic components such as reduction techniques and cutting-plane separation algorithms, and combine them in an exact branch-and-cut solver. Furthermore, we provide a parallel implementation. The new solver is shown to significantly outperform existing state-of-the-art software for sparse maximum-cut and quadratic unconstrained binary optimization instances. Furthermore, we improve the best known bounds for several instances from the 7th DIMACS Challenge and the QPLIB, and solve some of them (for the first time) to optimality.
On the state of QUBO solving
(2023)
It is regularly claimed that quantum computers will bring breakthrough progress in solving challenging combinatorial
optimization problems relevant in practice. In particular, Quadratic Unconstrained Binary Optimization
(QUBO) problems are said to be the model of choice for use in (adiabatic) quantum systems during the noisy intermediate-
scale quantum (NISQ) era. Even the first commercial quantum-based systems are advertised to solve
such problems. Theoretically, any Integer Program can be converted into a QUBO. In practice, however, there are
some caveats, as even for problems that can be nicely modeled as a QUBO, this might not be the most effective
way to solve them. We review the state of QUBO solving on digital and quantum computers and provide insights
regarding current benchmark instances and modeling.
The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. The focus of this article is on the role of the SCIP Optimization Suite in supporting research. SCIP’s main design principles are discussed, followed by a presentation of the latest performance improvements and developments in version 8.0, which serve both as examples of SCIP’s application as a research tool and as a platform for further developments. Furthermore, this article gives an overview of interfaces to other programming and modeling languages, new features that expand the possibilities for user interaction with the framework, and the latest developments in several extensions built upon SCIP.
This paper introduces an implementation for solving the single-source shortest path problem on distributed-memory machines. It is tailored to power-law graphs and scales to trillions of edges.
The new implementation reached 2nd and 10th place in the latest Graph500 benchmark in June 2022 and handled the largest and second-largest graphs among all participants.