Historique: report-januschowski

Aperçu de cette version: 1 (courant)

During the STSM a fruitful collaboration with Prof Marc Pfetsch (TU Braunschweig) took place. The subject of the collabortion is a problem in combinatorial optimization: the maximum k-colorable subgraph problem. This problem arises in the design of optical networks for example and an efficient algorithmic solution is desireable.

Algorithms to solve the maximum k-colorable subgraph problem suffer from the deterioating effect of symmetry. Symmetry in this problem arises due to the underlying graph structure and due to a choice of modelling. In order to guarantee an efficient solving, both types of symmetries need to be handled. We propose to handle graph symmetry by hybridising methods from Constraint Programming and Integer Programming and we handle the model symmetry with a polyhedral approach. Our approach has been implemented within an algorithmic suite for solving the maximum k-colorable subgraph problem. During the STSM, we successfully worked on the following aspects.

We implemented linearised symmetry breaking constraints for general graph symmetry. Initial computational effects show their effectiveness by leading to significantly improved solving times. Next, we provided theorectical results that ensure the safe combinations of these constraints with other, similar constraints. Unfortunately, the combination of these constraints does not seem to provide improvements in computing times.

Furthermore, we invested considerable efforts into presolving techniques for the maximum k-colorable subgraph problem in order to obtain faster overall performance of the code. One outcome of preliminary computational experiments is that standard Integer Programming presolving techniques can be made much more efficient by gearing them towards the maximum k-colorable subgraph problems.

Throughout the STSM, the contact with other researchers in Mathematical Programming at ZIB Berlin made the STSM more productive. Collaboration with Marc Pfetsch continues.


Information Version
mer. 13 de Apr, 2011 14h46 uendriss 1