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

Our members are also part of The Ottawa-Carleton Discrete Mathematics Group, where we collaborate and organize joint events.

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.

Research Facilities

The IPCOS lab is sharing a powerful computing infrastructure with the Bioinformatics Research Group (BORG) and Computational Laboratory in Coding and Cryptography (CLICC). It consists of:

a work-group server (SUN Fire V880) which is multi-user, multi-processor (8) server with large central memory (32 Gbytes), large disk capacity (0.5 Tbytes) and high throughput disk access.
a work-group server (SUN Fire V480) 4-way 64 bit microprocessor used to execute CPU and memory intensive applications;
15+ workstations (15 SUN Blade workstations; IBM PC/Linux); and some network printers.

Using Sun Microsystems' GridEngine allows us to integrate workstations and servers together, and provide the researchers with an additional 15+ processors. Several commercial software packages are essential to the success of these projects. These include ILOG Parallel CPLEX library, Magma computer algebra package, and several other open source software for combinatorial algorithms research.