On the extremality of maximal dual feasible functions

Dual feasible functions have been used with notable success to compute fast lower bounds and valid inequalities for various combinatorial optimization problems. In this paper, we analyze the theoretical properties of some of the best (and more complex) functions proposed in the literature. Additionally, we report on new results for composed functions. In particular, we describe under which conditions all these functions are extremal. These results are important since they allow to improve the computation of both lower bounds and valid inequalities