We present a new tool for generating cutting planes for NP-hard combinatorial optimisation problems. It is based on the concept of gadgets — small subproblems that are “glued” together to form hard problems — which we borrow from the literature on computational complexity. Using gadgets, we are able to derive huge (exponentially large) new families of strong (and sometimes facet-defining) cutting
planes, accompanied by efficient separation algorithms. We illustrate the power of this approach on the asymmetric traveling salesman, stable set and clique partitioning problems.