The article describes a generalization of a constraint satis-
faction problem and its max-min relaxation. The general
problem is defined in terms of a commutative semiring
and considers a special case of semirings with idempotent
operations. The concept of polymorphism is generalized
for this special case and the polynomial time algorithm
for problems with a majority polymorphism is described.