On Integrating Constraint Propagation and Linear Programming for Combinatorial Optimization

John N. Hooker, Carnegie Mellon University; Greger Ottosson, Uppsala University; Erlendur S. Thorsteinsson and Hak-Jin Kim, Carnegie Mellon University

Linear programming and constraint propagation are complementary techniques with the potential for integration to benefit the solution of combinatorial optimization problems. Attempts to combine them have mainly focused on incorporating either technique into the framework of the other -- traditional models have been left intact. We argue that a rethinking of our modeling traditions is necessary to achieve the greatest 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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.