  In this paper we study the interactions between so-called fractional
relaxations of the integer programs (IPs) which encode homomorphism and
isomorphism of relational structures. We give a combinatorial characterization
of a certain natural linear programming (LP) relaxation of homomorphism in
terms of fractional isomorphism. As a result, we show that the families of
constraint satisfaction problems (CSPs) that are solvable by such linear
program are precisely those that are closed under an equivalence relation which
we call Weisfeiler-Leman invariance. We also generalize this result to the much
broader framework of Promise Valued Constraint Satisfaction Problems, which
brings together two well-studied extensions of the CSP framework. Finally, we
consider the hierarchies of increasingly tighter relaxations of the
homomorphism and isomorphism IPs obtained by applying the Sherali-Adams and
Weisfeiler-Leman methods respectively. We extend our combinatorial
characterization of the basic LP to higher levels of the Sherali-Adams
hierarchy, and we generalize a well-known logical characterization of the
Weisfeiler-Leman test from graphs to relational structures.
