A Sweep-Plane Algorithm for the Computation of the Volume of a Union of Polytopes
- Optimization models often feature disjunctions of polytopes as submodels. Such a disjunctive set is initially at best) relaxed to its convex hull, which is then refined by branching. To measure the error of the convex relaxation, the (relative) difference between the volume of the convex hull and the volume of the disjunctive set may be used. This requires a method to compute the volume of the disjunctive set. We propose a revised variant of an old algorithm by Bieri and Nef (1983) for this purpose. The algorithm uses a sweep-plane to incrementally calculate the volume of the disjunctive set as a function of the offset parameter of the sweep-plane.
Additional Services
| Author: | Lovis AndersonORCiD, Benjamin HillerORCiD |
|---|---|
| Document Type: | In Proceedings |
| Parent Title (English): | Operations Research Proceedings 2018 |
| Volume: | Operations Research Proceedings |
| Year of first publication: | 2019 |
| Preprint: | urn:nbn:de:0297-zib-69489 |
| DOI: | https://doi.org/10.1007/978-3-030-18500-8_12 |
