Gomory cuts in a hybrid constraint programming approach

Recently, many successful hybrid approaches which use both constraint programming (CP) and operations research (OR) techniques to solve a problem have been proposed. They usually use OR techniques, like cutting planes, which are specific to the problem. In this paper we investigate the use of generic cutting planes (more specifically, Gomory cuts) in a typical CP-OR hybrid approach. This allows us to have a general algorithm to be applied to all problem classes. We will show that our approach is indeed promising: on the class of partial latin square completion problems, the performance of our algorithm is comparable to that of a pure CP algorithmand better in several cases. In particular we will show that the hybrid approach solves many problem instances that the CP approach is not able to solve in a reasonable amount of time.