We present Branch-and-Check, a hybrid framework integrating Mixed Integer Programming and Constraint Logic Programming, which encapsulates the traditional Benders Decomposition and Branch-and-Bound as special cases. In particular we describe its relation to Benders and the use of nogoods and linear relaxations.We give two examples of how problems can be modelled and solved using Branch-and-Check and present computational results demonstrating more than order-of-magnitude speedup compared to previous approaches.We also mention important future research issues such as hierarchical, dynamic and adjustable linear relaxations.