  An instance of the Valued Constraint Satisfaction Problem (VCSP) is given by
a finite set of variables, a finite domain of labels, and a sum of functions,
each function depending on a subset of the variables. Each function can take
finite values specifying costs of assignments of labels to its variables or the
infinite value, which indicates infeasible assignments. The goal is to find an
assignment of labels to the variables that minimizes the sum.
  We study (assuming that P $\ne$ NP) how the complexity of this very general
problem depends on the set of functions allowed in the instances, the so-called
constraint language. The case when all allowed functions take values in
$\{0,\infty\}$ corresponds to ordinary CSPs, where one deals only with the
feasibility issue and there is no optimization. This case is the subject of the
Algebraic CSP Dichotomy Conjecture predicting for which constraint languages
CSPs are tractable and for which NP-hard. The case when all allowed functions
take only finite values corresponds to finite-valued CSP, where the feasibility
aspect is trivial and one deals only with the optimization issue. The
complexity of finite-valued CSPs was fully classified by Thapper and
\v{Z}ivn\'y.
  An algebraic necessary condition for tractability of a general-valued CSP
with a fixed constraint language was recently given by Kozik and Ochremiak. As
our main result, we prove that if a constraint language satisfies this
algebraic necessary condition, and the feasibility CSP corresponding to the
VCSP with this language is tractable, then the VCSP is tractable. The algorithm
is a simple combination of the assumed algorithm for the feasibility CSP and
the standard LP relaxation. As a corollary, we obtain that a dichotomy for
ordinary CSPs would imply a dichotomy for general-valued CSPs.

Computational Complexity;Discrete Mathematics