Polyhedral combinatorics

The group of Vladimir Bondarenko, D.Sc.

The group also includes:

It is known that almost any problem of combinatorial optimization can be reduced to the linear programming problem on the corresponding polytope. However, as a rule, such polytope is overly complex structure: an exponential number of facets and exponentially large coefficients in the linear constraints. Moreover, for the most problems complete description of the corresponding polytopes has not been found yet. An alternative approach is to reduce the combinatorial optimization problems to the problem of integer programming on so-called relaxation polytopes. Unlike the classical polytopes of combinatorial problems, external description of relaxation polytopes requires only a polynomial number of linear inequalities. In this case the relaxation polytope partially retain the structure of the original polytope (integer vertices), and some important properties of its face lattice (eg, the clique number of the polytope graph). The main objective here is to research the properties and characteristics of non-integer vertices.

Within the research group it’s planned to study the relaxation’s hierarchy of the polytope associated with the basic NP-complete problems, among them the problem of finding a maximum cut in a graph. Its relaxation of the lower level is the well-known rooted semimetric polytope — considered in Bondarenko, Padberg, Deza and Laurent. Relaxations of higher levels, obtained by imposing additional linear constraints, have been studied by Bondarenko, Nikolaev and Uryvaev. The focus of the research is directed to
• finding additional linear constraints for higher level cut polytope relaxations;
• description of non-integer vertices of the relaxations and their properties;
• construction of algorithms for integer programming and integer recognition on these polytopes with polynomial time complexity.

You can find more information about group research by the link (in Russian).