The goal of this work, in which combinatorial optimization problems are addressed, is to assign values to Boolean variables in order to satisfy as many constraints as possible and, specifically, to maximize the sum of some Boolean functions with non-negative weights. There is considerable practical interest in these problems, such as MAX CUT, as evidenced by the extensive list of references quoted. “Gadgets” are defined in this context as transformations of the constraint functions in order to reduce them to other problems. The authors prove that there are only finitely many essentially different gadgets for a given reduction, and they present a linear programming procedure to find optimal gadgets. This method is then used to improve known results on approximation algorithms and on inapproximability theorems.