Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 2 von 2
Zurück zur Trefferliste

A Sweep-Plane Algorithm for the Computation of the Volume of a Union of Polytopes

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-69489
  • 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.

Volltext Dateien herunterladen

Metadaten exportieren

Metadaten
Verfasserangaben:Lovis AndersonORCiD, Benjamin HillerORCiD
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:Disjunctive Programming; Union of Polytopes; Volume Algorithm
MSC-Klassifikation:49-XX CALCULUS OF VARIATIONS AND OPTIMAL CONTROL; OPTIMIZATION [See also 34H05, 34K35, 65Kxx, 90Cxx, 93-XX]
CCS-Klassifikation:G. Mathematics of Computing
PACS-Klassifikation:00.00.00 GENERAL
Veröffentlichende Institution:Zuse Institute Berlin (ZIB)
Datum der Erstveröffentlichung:17.07.2018
Schriftenreihe (Bandnummer):ZIB-Report (18-37)
ISSN:1438-0064
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.