On integrating constraint propagation and linear programming for combinatorial optimization

Linear programming and constraint propagation are comple-mentary techniques with the potential for integration to ben-efit the solution of combinatorial optimization problems. At-tempts to combine them have mainly focused on incorporat-ing either technique into the framework of the other — tradi-tional models have been left intact. We argue that a rethinking of our modeling traditions is necessary to achieve the great-est benefit of such an integration. We propose a declarative modeling framework in which the structure of the constraints indicates how LP and CP can interact to solve the problem