6948
eng
reportzib
0
--
2018-07-17
--
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. Naively, this can be done via
inclusion/exclusion and leveraging the existing code for the volume
of polytopes. However, this is often inefficient.
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.
1438-0064
urn:nbn:de:0297-zib-69489
Lovis Anderson
Lovis Anderson
Benjamin Hiller
ZIB-Report
18-37
eng
uncontrolled
Disjunctive Programming
eng
uncontrolled
Volume Algorithm
eng
uncontrolled
Union of Polytopes
Mathematics of Computing
GENERAL
CALCULUS OF VARIATIONS AND OPTIMAL CONTROL; OPTIMIZATION [See also 34H05, 34K35, 65Kxx, 90Cxx, 93-XX]
Mathematical Optimization
Hiller, Benjamin
MODAL-GasLab
Anderson, Lovis
TRR154-A04
MODAL-Gesamt
Zuse Institute Berlin (ZIB)
https://opus4.kobv.de/opus4-zib/files/6948/ZR-18-37.pdf