Certificates of Optimality and Sensitivity Analysis using Generalized Subadditive Generator Functions: A test study on Knapsack Problems

We introduce a family of subadditive functions called Generator Functions for mixed integer linear programs. These functions were previously defined for pure integer programs with non-negative entries by Klabjan [13]. They are feasible in the subadditive dual and we show that they are enough to achieve strong duality. Several properties of the functions are shown. … Read more