Scholarlink

<p>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 <i>generator subadditive function</i>. Motivated by these results, we explore the connection between Lagrangian duality, subadditive duality and generator subadditive functions for general equality-constrained MIPs where the vector of variables is constrained to be in a monoid. We show that strong duality holds via generator subadditive functions under certain conditions. For the case when the monoid is defined by the set of all mixed-integer points contained in a convex cone, we show that strong duality holds under milder conditions and over a more restrictive set of dual functions. Finally, we provide some examples of applications of our results.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Generator subadditive functions for mixed-integer programs

  • 期刊论文

  • 发表日期：

    2025年6月9日

查看全文
  • Gustavo Angulo,
  • Burak Kocuk,
  • Diego A. Moran Ramirez

摘要

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 equality-constrained MIPs where the vector of variables is constrained to be in a monoid. We show that strong duality holds via generator subadditive functions under certain conditions. For the case when the monoid is defined by the set of all mixed-integer points contained in a convex cone, we show that strong duality holds under milder conditions and over a more restrictive set of dual functions. Finally, we provide some examples of applications of our results.