Branch and infer: a unifying framework for integer and finite domain constraint programming

We introduce branch and infer, a unifying framework for integer linear programming and finite domain constraint programming. We use this framework to compare the two approaches with respect to their modeling and solving capabilities, to introduce symbolic constraint abstractions into integer programming, and to discuss possible combinations of the two approaches. C ombinatorial problems are ubiquitous in many real world applications like scheduling, planning, transportation, as-signment, and many others. Besides special purpose algo-rithms to compute exact or approximate solutions, there exist also general approaches to solve this kind of problem. We are interested here in two such approaches: • Integer linear programming (ILP) • Finite domain constraint programming (CP(FD)) Integer linear programming has a long tradition in opera-tions research and has produced a large number of impres-sive results during the last 40 years, see for example [37, 30]. Finite domain constraint programming is a promising new approach for solving complex combinatorial problems, which combines recent progress in programming language design, like constraint logic programming[29] or concurrent constraint programming,[42] with efficient constraint solving techniques from mathematics, artificial intelligence, and op-erations research, see for example [49, 50]. The aim of this paper is to develop a unifying framework for integer linear programming and finite domain constraint programming. On the one hand, we want to clarify the relationship between these two approaches and identify (some of) their strengths and weaknesses. On the other hand, we want to show how each of the two approaches may profit from the other and indicate possible ways to-wards their integration. This continues our previous work i