Refine
Year of publication
- 2020 (224) (remove)
Document Type
- Article (122)
- In Proceedings (35)
- ZIB-Report (30)
- Master's Thesis (9)
- Book chapter (7)
- Book (4)
- Doctoral Thesis (4)
- Other (4)
- In Collection (3)
- Bachelor's Thesis (2)
Keywords
Institute
- Modeling and Simulation of Complex Processes (71)
- Numerical Mathematics (67)
- Visual and Data-centric Computing (37)
- Visual Data Analysis (36)
- Applied Algorithmic Intelligence Methods (33)
- Computational Nano Optics (32)
- Mathematical Optimization (32)
- Mathematical Algorithmic Intelligence (30)
- Distributed Algorithms and Supercomputing (27)
- AI in Society, Science, and Technology (19)
It is well understood that Bayesian decision theory and average case analysis are essentially identical. However, if one is interested in performing uncertainty quantification for a numerical task, it can be argued that the decision-theoretic framework is neither appropriate nor sufficient. To this end, we consider an alternative optimality criterion from Bayesian experimental design and study its implied optimal information in the numerical context. This information is demonstrated to differ, in general, from the information that would be used in an average-case-optimal numerical method. The explicit connection to Bayesian experimental design suggests several distinct regimes in which optimal probabilistic numerical methods can be developed.
Price-and-verify: a new algorithm for recursive circle packing using Dantzig–Wolfe decomposition
(2020)
Packing rings into a minimum number of rectangles is an optimization problem which appears naturally in the logistics operations of the tube industry. It encompasses two major difficulties, namely the positioning of rings in rectangles and the recursive packing of rings into other rings. This problem is known as the Recursive Circle Packing Problem (RCPP). We present the first dedicated method for solving RCPP that provides strong dual bounds based on an exact Dantzig–Wolfe reformulation of a nonconvex mixed-integer nonlinear programming formulation. The key idea of this reformulation is to break symmetry on each recursion level by enumerating one-level packings, i.e., packings of circles into other circles, and by dynamically generating packings of circles into rectangles. We use column generation techniques to design a “price-and-verify” algorithm that solves this reformulation to global optimality. Extensive computational experiments on a large test set show that our method not only computes tight dual bounds, but often produces primal solutions better than those computed by heuristics from the literature.