DIAMANT Intercity Event: Integer Programming Day Department of Mathematics TU Eindhoven (TU/e) Friday, January 27, 2006 13:00-17:00 www: http://www.win.tue.nl/diamant/ www: http://www.win.tue.nl/~gwoegi/diamant-ip/

When and where

When: January 27. 13:00-17:00.
Where: Campus of TU/e.   Room AUD.7 in Auditorium (building AUD on the map).

13:00-13:45	Alexander Bockmayr (FU Berlin)   www Integer programming, constraint programming, and their combination. Abstract. Integer programming (IP) and constraint programming (CP) are two complementary approaches for modeling and solving discrete optimization problems. While some of the underlying concepts are similar, there exist also a number of important differences between the two approaches. Both CP and IP generate a branching tree. Both use inference methods that take advantage of problem structure: cutting planes in the case of IP, and domain filtering algorithms in the case of CP. A major difference, however, is that CP associates each constraint with an algorithm that operates on the solution space so as to remove infeasible solutions. This allows CP to exploit substructure in the problem in a way that IP cannot, while IP benefits from strong continuous relaxations that are unavailable in CP. In this talk, we compare and contrast the basic concepts underlying CP and IP in order to clarify their relationship, and to better understand the strengths and weaknesses of the two approaches. In addition, we will discuss some possible ways of integration.
14:00-14:45	Friedrich Eisenbrand (MPI Saarbruecken)   www Integer programming: Algorithms and applications. Abstract. The purpose of this talk is to present an introduction to integer programming and to illuminate its relation to algorithmic number theory. In particular, I present algorithms for integer programming in fixed dimension. One algorithm matches the complexity of the Euclidean algorithm if the number of constraints is also fixed. The other algorithm is an optimal algorithm for integer programming in the plane.
15:15-16:00	Monique Laurent (CWI Amsterdam)   www Semidefinite programming bounds for codes and coloring. Abstract. We investigate semidefinite programming approximations for the stability number and the coloring number of a graph and, in particular, how they apply to Hamming graphs. Our bounds improve the classic theta number of Lovasz (corresponding to Delsarte bound) as well as the recent bound of Schrijver for codes. Their computation relies on exploiting symmetries and using the block-diagonalization of the Terwilliger algebra.
16:15-17:00	Alexander Martin (TU Darmstadt)   www Hard Mixed Integer Programs in Practice. Abstract. Mixed Integer Programming deals with the solution of optimizing a linear objective function subject to a system of linear inequalities, where part or all of the variables must be integer. Many real-world problems can be formulated as mixed integer programs. We will give three challenging examples of this kind, one from a facility location problem in telecommunication, one from a network optimization problem in energy management and one from a scheduling problem in public mass transport. We will show the success and the limits of mixed integer programming techniques for the solution of these real-world problems.
17:00-17:30	Reception

Participation is for free, and there is no official registration.

All further questions to: Karen Aardal or Gerhard Woeginger

Modified on January 22, 2006.