Promise Valued CSP (PVCSP) for target structures $A$ and $B$ is an optimization problem where we are given a number $q$ and an objective function such as
\[ 4\cdot R(x,y)+7\cdot S(x,x,z)+1\cdot R(z,z), \]
where the functions $R$ and $S$ have different meaning in $A$ and in $B$. In addition, the structure $B$ more relaxed than $A$ (there is a mapping from $A$ to $B$ that does not increase costs).
Our task is to decide between two possibilities: In “Yes” instances there exists an assignment of values from $A$ to the variables such that the objective function evaluates to at most $q$. In “No” instances there is no such assignment even in the (more relaxed) structure $B$.
It is known that minion homomorphisms give very natural complexity reductions between (P)CSPs (Barto, Bulín, Opršal, Krokhin, 2019). We will explore how to translate these techniques into the PVCSP situation. Convex geometry will make an appearance.