Maximizing a class of submodular utility functions with constraints

• 成果类型: Article
• 署名作者: Yu, Jiajin; Ahmed, Shabbir
• 署名单位: University System of Georgia; Georgia Institute of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-1033-3
• 发表日期: 2017
• 页码: 145-164
• 关键词: expected utility

摘要

Motivated by stochastic 0-1 integer programming problems with an expected utility objective, we study the mixed-integer nonlinear set: where N is a positive integer, is a concave function, are nonnegative vectors, d is a real number and B is a positive real number. We propose a family of inequalities for the convex hull of P by exploiting submodularity of the function over and the knapsack constraint . Computational effectiveness of the proposed inequalities within a branch-and-cut framework is illustrated using instances of an expected utility capital budgeting problem.