Many fundamental combinatorial problems exhibit characteristic structures. Such properties can be exploited for deriving efficient algorithms and, moreover, are often helpful for solving general integer programs with binary variables. A good example are the various known inequalities for the stable set polytope.

The investigation of integer generalizations of such basic problems aims at the identification of similar structures and their application for solving general integer programs. In this project, we in particular study stable multi-sets as an appropriate extension of stable sets.

StableMultiSets

Integer generalizations of basic 0-1 problems

Many fundamental combinatorial problems exhibit characteristic structures. Such properties can be exploited for deriving efficient algorithms and, moreover, are often helpful for solving general integer programs with binary variables. A good example are the various known inequalities for the stable set polytope. The investigation of integer generalizations of such basic problems aims at the identification of similar structures and their application for solving general integer programs. In this project, we in particular study stable multi-sets as an appropriate extension of stable sets.

  

Description

The study of the combinatorial structure of several 0-1 problems has been very fruitful for solving general integer programs with binary variables. An indicative example is given by stable sets in graphs. A stable set is a set of pairwise non-adjacent vertices of a graph. The investigation of the stable set polytope yielded different classes of inequalities which are also valid for various other integer programs. For instance, the separation of clique inequalities is standard in state-of-the-art solvers. However, similar structures for general integer programs are far less studied.

Project objective

We consider integer generalizations of fundamental 0-1 problems. In particular for stable sets, an appropriate extension is given by stable multi-sets. Instead of a binary decision, vertices can be chosen multiple times in stable multi-sets as long as given bounds on edges and vertices of the graph are not exceeded. In terms of the linear program, integer variables replace the binary ones used for stable sets. The theoretical analysis of the stable multi-set polytope aims at deriving further classes of generic inequalities. For example, integer variants of the inequalities for cycles and certain cliques have been identified (cf. Koster and Zymolka 2002). Moreover, a polynomial time separation algorithm for the cycle inequalities (cf. Koster and Zymolka 2003) allows for their beneficial use in solution algorithms as documented by a computational study.

Publications