Focused Workshop on Combinatorics of Integer Programming

The proposed workshop is inspired by recent developments in tractability of integer programming using combinatorial tools. The workshop will bring together a group of 10-12 researchers with backgrounds in discrete optimization, parameterized complexity, graph theory, polyhedral combinatorics,and matroid theory.

Researchers from these communities are not fully aware of problems and techniques appearing in the other areas. The goal is to further strengthen connections between these areas by identifying additional tools from graph theory and matroid theory that will lead to the design of efficient fixed-parameter algorithms for integer programming.

The scientic aim of the workshop is to get a better understanding of combinatorial properties of integer programming instances that cause their tractability. For instance, various combinatorial notions of structure and complexity of matrices, such as depth parameters or sizes of Graver bases, appear to be vital for the design of efficient algorithms in the context of integer programming.

We aim to further develop the combinatorial theory of structured integer programming, and for this we hope to bring a mixture of researchers with very different backgrounds, and also at various career stages, who do not normally meet at conferences.

Report

The Focused Workshop on Combinatorics of Integer Programming took place at the Erdős Center in the period from August 14 to 25 in association with the Dynasnet 8100115 Project.

Integer programming is an essential tool to solve optimization problems on graphs and networks. Some of the most common problems include finding large cliques in graphs or finding optimal colorings. These problems have many real-world applications ranging from scheduling to production planning.

This workshop, which responded to recent structural and algorithmic developments in tractability of integer programming, was attended by a group of researchers with backgrounds in discrete optimization, parameterized complexity, graph theory, polyhedral combinatorics, and matroid theory and so provided a platform for researchers from these communities, who seldom meet at conferences, to exchange their ideas.

The workshop was attended by the following participants (for at least part of it).

• Kristóf Bérczi (ELTE)

• Marcin Briański (Jagiellonian University, Kraków)

• Péter Csikvári (Rényi Institute)

• Friedrich Eisenbrand (EPFL)

• Tamás Király (ELTE)

• Daniel Kráľ (Masaryk University), organizer

• Alexandra Lassota (MPI Saarbrücken)

• Georg Logo (University of Twente)

• Dániel Marx (CISPA)

• Bento Natura (Georgia Tech)

• Kristýna Pekárková (Masaryk University, Brno)

• Michał Pilipczuk (University of Warsaw), organizer

• Janina Reuter (University of Kiel)

• Lars Rohwedder (Maastricht University)

• Sándor Szabó (University of Pécs)

• László Végh (LSE), organizer

• Bogdán Zaválnij (Rényi Institute)

The scientific discussions held during the workshop focused on getting a better understanding of combinatorial properties of integer programming instances that cause their tractability, relevant matroid theory notions from both the structural and algorithmic point of view, and possible applications of the discussed methods to instances of the clique size problem. The workshop facilitated an exchange of a large number of ideas and led to opening new research collaborations, as outlined further in more detail.

The workshop opened with the following four survey introductory lectures, which took place on Monday August 14, Tuesday August 15 and Friday August 18 (the lecture of Bento Natura was originally scheduled for Wednesday but postponed to Friday):

• Friedrich Eisenbrand: Algorithms for Integer Programming

• ‪Dan Král’: Matroid Algorithms and Decompositions

• Bento Natura: Circuit Imbalances and Linear Programming

• Michał Pilipczuk: Graver Bases and Block-Structured Integer Programming

In addition to these lectures, there were four additional meetings of all participants.

• meeting on Thursday August 17 to discuss applications of the IP methods to instances of the cliques size problem

• meeting on Friday August 18 to discuss progress made during the first week of the workshop

• meeting on Monday August 21 to discuss research problems to be discussed during the second week of the workshop

• meeting on Friday August 25 to discuss progress made during the whole workshop and particularly during its second week

The following specific research topics were discussed during the workshop by different (overlapping) groups of the workshop participants.

• tractability of integer programs whose dual graph is a path

This problem is motivated by the feasibility of integer programs whose dual graph has small tree-depth. Since the tree-depth is functionally bound to the length of the longest path, the resolution of the studied problem would help to better understand the boundary of the tractability of integer programs.

• algorithms for computing contraction^*-depth of matroids

Contraction^*-depth is a matroid parameter closely linked to the tree-depth of dual graphs of integer programs. There are very few algorithms for computing this parameter beyond matroids represented over finite fields. The aim was to obtain a polynomial-time (although not fixed-parameter) algorithm for general matroids and an easy constant-approximation fixed-parameter algorithm.

• matroid parity problem parameterized by contraction^*-depth

Matroid parity problem is a fundamental problem in combinatorial optimization, which can be solved in polynomial time for represented matroids. The problem is computationally hard for general matroids, and it was realized that it remains hard for parameterization by branch-width and positive results were obtained for small values of contraction^*-depth.

• applications of width parameters to the clique size problem

While the workshop focused on advancing mathematical understanding of integer programming, the schedule also included discussing possible applications of width parameters in the setting of the clique size problem, an area of active applied research of some of the workshop participants.

There were additional topics discussed, e.g., straight line complexity of integer programs, during the workshop, however, there was less time allocated to them than the topics listed above.

Partial results have been obtained in regard to the first three topics mentioned above. The first problem was shown to be intractable in general, but there are positive prospects for its full resolution under certain well-motivated assumptions. A possible approach to a polynomial-time algorithm for contraction^*-depth was identified and will be a subject of the subsequent research. Positive results obtained on the third problem for small values of contraction^*-depth indicates good prospects for follow up work. Unfortunately, no promising applications of the discussed techniques in relation to the clique size problems were discovered.

The workshop fulfilled its goals: it brought together researchers from different areas and helped to overcome language barriers between these areas by bringing relevant results to the attention of those coming from other areas. Several new research collaborations have been established and preliminary results obtained (some of them publishable although not in the leading venues). The work on the first three topics mentioned above, which was initiated during this workshop, continues and we expect this work to yield more substantial results in the horizon of 1-2 years.