Set-Partitioning Integer Programs and Integrality Gaps

Support

Swiss National Science Foundation (SNSF)

Members

Friedrich Eisenbrand

Nicolai Hähnle

Gennady Shmonin

Description

Many combinatorial optimization problems can be modelled as a partitioning of a set into the minimum number of smaller subsets. Although these problems are typically NP-hard, the corresponding integer programs often appear to be tractable in practice. In particular, this is mainly the case for the problems on which we intend to focus in the proposed project: bin-packing and edge-colouring

Those are set partitioning problems with exponentially many subsets of a special structure. The common technique to tackle such problems in practice is by means of so-called column-generation methods. Efficiency of these methods depends on three issues: (1) the running time of an associated algorithm for generating a required subset, (2) the running time of an associated algorithm for solving the linear programming relaxation, and (3) the tightness of the lower bound provided by the linear programming relaxation.

The project intends to advance the state of the art in the above-mentioned topics. In particular, we investigate:

• Integrality gaps of set-partitioning problems: additive integrality gaps of set-covering integer programs, including bin-packing, edge-colouring and general-form integer programs; testing additive integrality gap properties.
• Algorithms for set-partitioning problems: algorithms for bin-packing and general-form set-partitioning integer programs.
• The complexity of computing integer programming gaps if the number of rows of the partitioning integer program is fixed.

Publications