In the Mathematical Programming Community (consisting mainly of mathematicians and operations researchers) Integer Programming (IP) started flourishing in the maximize cT x (IPP) subject to Ax b x integer where c and b are n- and m-dimensional vectors, respectively, and A is an m by n matrix of rational numbers. Refinements and hybrids of both techniques led to powerful algorithms for IPP as well as combinatorial optimization problems with linear objective function (COP) maximize eF ce subject to FF where for a finite set E a collection of subsets F 2E defines the feasible solutions. Prominent successes are, e.g., the most powerful software packages for the traveling salesman problem.

In the Artificial Intelligence Community (consisting mainly of logicians and computer scientists) Constraint Programming (CP) started flourishing in the 1980's after constraint satisfaction problems had been a focus of research in the 1970's. Today's state of the art includes several systems that support programming language constructs whose expressive power goes far beyond linear equations and inequalities to include logical and higher-order constraints, global constraints, as well as specific support for scheduling and resource allocation problems. These languages also let users to specify and control a search procedure appropriate for a given application. Prominent successes are, e.g., in the area of production scheduling.

Many areas of applications of constraint programming techniques are beyond the scope of integer programming techniques, but Integer Programming and Constraint Programming are complementary techniques for combinatorial optimization problems of the form COP. Depending on the problem, one or the other technique is more appropriate.

Software for general integer programming, and special purpose software for structured problems such as the traveling salesman problem or the max cut problem, almost always depends on the formulation (IPP). Common features of the algorithms are a priori preprocessing, enumeration in which the bounds provided by linear programming play a crucial role in pruning the enumeration tree, and cutting planes that are used to tighten the linear programming bounds, and push the linear programming solution closer to integrality.

Using an IPP formulation is an advantage in terms of generality, but as concerns flexibility,

1. modeling certain simple situations/expressions may require a very large number of variables,
2. the preprocessor must maintain an IPP formulation, and therefore only a restricted set of transformations can be carried out,
3. certain IPP formulations have very weak linear programming relaxations so the bounds provided are useless, and
4. the choice of how to branch is also restricted by the IPP formulation.

CP is also based on enumeration, but typically has a richer language to represent a problem, allowing for more refined preprocessing and branching. The basic idea behind CP systems is to enforce some consistency notions on the constraints (e.g., arc-consistency) at each node of the search tree. These consistency notions define in fact relaxations of the problem. In general, these relaxations are specific to classes of applications (e.g. edge finder in scheduling) and are used to reduce the set of possible values that the decision variables can take. In so doing, they also produce lower bounds for optimization problems. However, CP systems have not exploited so far the wealth of results provided by linear programming relaxations and their associated cuts.

Only very recently, first scientific links between IP and CP were installed, but still, both subjects develop independently to a large extent. Reasons include the different scientific contexts in which the two disciplines developed. This results in language barriers. Integer programmers use mathematical concepts that are unfamiliar to constraint programmers who in turn use computer science concepts that are unfamiliar to integer programmers. The organizers are convinced that combinations of IP and CP techniques will have an increasing impact on combinatorial problems solving, and that the potential of joint efforts is largely unexplored. In the first half of this Dagstuhl seminar we would like to overcome the language barriers by asking prominent researchers to give introductions for the other community into the most relevant topics. This first half requires a thorough preparation of the lectures and will be planned in advance (which is unusual for a Dagstuhl seminar). The second half of the seminar will follow the usual scheme: We expect that after the first half common interests among the two communities will have been identified and further workshop topics will result from this naturally. Also in the second half, lectures on advanced topics of common interest will be given by appropriate participants.