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

Lovis Anderson () and Benjamin Hiller
Additional contact information
Lovis Anderson: Zuse Institute
Benjamin Hiller: Zuse Institute

A chapter in Operations Research Proceedings 2018, 2019, pp 87-93 from Springer

Abstract: Abstract 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 (Linear Algebra Appl 52:69–97, 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.

Date: 2019
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-030-18500-8_12

Ordering information: This item can be ordered from
http://www.springer.com/9783030185008

DOI: 10.1007/978-3-030-18500-8_12

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().