  Valued constraint satisfaction problems (VCSPs) are a large class of
combinatorial optimisation problems. It is desirable to classify the
computational complexity of VCSPs depending on a fixed set of allowed cost
functions in the input. Recently, the computational complexity of all VCSPs for
finite sets of cost functions over finite domains has been classified in this
sense. Many natural optimisation problems, however, cannot be formulated as
VCSPs over a finite domain. We initiate the systematic investigation of
infinite-domain VCSPs by studying the complexity of VCSPs for piecewise linear
homogeneous cost functions. We show that such VCSPs can be solved in polynomial
time when the cost functions are additionally submodular, and that this is
indeed a maximally tractable class: adding any cost function that is not
submodular leads to an NP-hard VCSP.
