IPCOS lab: Integer Programming, Combinatorial Optimization and Structures

Members

Research Activities

Our research aims at the development of efficient computational methods for problems in the areas of combinatorial optimization, integer programming and combinatorial structures, their theory and applications.
Combinatorial optimization and integer programming deals with many practically important optimization problems which are combinatorial in nature. Some examples of such problems include the design of reliable communication networks, fast printed circuit board production, scheduling problems and routing problems.
The study of combinatorial structures includes the arrangement of discrete objects in a very balanced or tightly restricted way. Combinatorial structures like graphs and combinatorial designs model several problems arising in information technology, including problems in communications and security, software testing and bioinformatics.

Our research focuses towards the following aspects of integer programming, combinatorial optimization and combinatorial structures:

• Travelling Salesman Problem
• Combinatorial Designs and Hypergraphs
• Design and Analysis of Algorithms
• Polyhedral Combinatorics
• Combinatorial Generation
• Symmetry in Integer Programming
• Network Design
• Software Testing, Network Testing

Current Projects

• Applying new parallel decomposition method within cutting plane approach to solve sub-tour elimination relaxation of the traveling salesman problem.
• Testing approximation algorithm for the Steiner tree problem.
• New integrality gap results for small traveling salesman problems.
• Solving symmetrical integer programming problems by branch-and-cut.
• Covering arrays: construction methods and applications to network and software testing.
• Isomorph-free exhaustive generation of combinatorial objects.