00.00.00 GENERAL
Refine
Year of publication
- 2018 (3) (remove)
Document Type
- ZIB-Report (3)
Has Fulltext
- yes (3)
Keywords
- Clinch number (1)
- Combinatorial optimization (1)
- Disjunctive Programming (1)
- Elimination number (1)
- Integer programming (1)
- Linienplanung (1)
- Round-robin tournament (1)
- Sports league (1)
- Tiebreaking criteria (1)
- Union of Polytopes (1)
Institute
Calculation of clinch and elimination numbers for sports leagues with multiple tiebreaking criteria
(2018)
The clinch (elimination) number is a minimal number of future wins (losses) needed to clinch (to be eliminated from) a specified place in a sports league. Several optimization models and computational results are shown in this paper for calculating clinch and elimination numbers in the presence of predefined multiple tiebreaking criteria. The main subject of this paper is to provide a general algorithmic framework based on integer programming with utilizing possibly multilayered upper and lower bounds.
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.