Dual-feasible functions for integer programming and combinatorial optimization: Algorithms, characterizations, and approximations

Abstract Within the framework of the superadditive duality theory of integer programming, we study two types of dual-feasible functions of a single real variable (Alves et al., 2016). We introduce software that automates testing piecewise linear functions for maximality and extremality, enabling a computer-based search. We build a connection to cut-generating functions in the Gomory–Johnson and related models, complete the characterization of maximal functions, and prove analogues of the Gomory–Johnson 2-slope theorem and the Basu–Hildebrand–Molinaro approximation theorem.