Skip to main content
Dual-feasible functions for integer programming and combinatorial optimization: Algorithms, characterizations, and approximations
Published Web Location
https://doi.org/10.1016/j.dam.2019.11.021Abstract
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.
Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.