subadditive duality

Generator Subadditive Functions for Mixed-Integer Programs

  • Gustavo Angulo
  • Burak Kocuk
  • Diego Moran Ramirez
    • Categories (Mixed) Integer Nonlinear Programming, Cone Programming, Integer Programming Tags , , , ,

    For equality-constrained linear mixed-integer programs (MIP) defined by rational data, it is known that the subadditive dual is a strong dual and that there exists an optimal solution of a particular form, termed generator subadditive function. Motivated by these results, we explore the connection between Lagrangian duality, subadditive duality and generator subadditive functions for general … Read more

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

  • Kevin Cheung
  • Babak Moazzez
    • Categories (Mixed) Integer Linear Programming Tags , , , , , ,

    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