General properties of staircase and convex dual feasible functions

Abstract

Dual feasible functions have been used successfully to compute lower bounds and valid inequalities for different combinatorial optimization problems. In this paper, we show that some maximal dual feasible functions proposed in the literature are dominated by others under weak prerequisites. Furthermore, we explore the relation between superadditivity and convexity, and we derive new results for the case where dual feasible functions are convex. Computational results are reported to illustrate the results presented in this paper.