  Discrete optimisation problems arise in many different areas and are studied
under many different names. In many such problems the quantity to be optimised
can be expressed as a sum of functions of a restricted form. Here we present a
unifying theory of complexity for problems of this kind. We show that the
complexity of a finite-domain discrete optimisation problem is determined by
certain algebraic properties of the objective function, which we call weighted
polymorphisms. We define a Galois connection between sets of rational-valued
functions and sets of weighted polymorphisms and show how the closed sets of
this Galois connection can be characterised.
  These results provide a new approach to studying the complexity of discrete
optimisation. We use this approach to identify certain maximal tractable
subproblems of the general problem, and hence derive a complete classification
of complexity for the Boolean case.
