Exploiting Submodularity in Integer Programming

在整数规划中利用子模性

• 批准号: 1129871
• 负责人: Shabbir Ahmed
• 金额: $ 25万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-08-15 至 2016-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1129871&HistoricalAwards=false
• 关键词: Exploiting; Submodularity; Integer; Programming

The research objective of this project is to develop mixed integer linear programming (MILP)approaches for mixed integer nonlinear programming (MINLP) problems involving nonlinear functions of binary variables by exploiting submodularity of the nonlinear functions. Existing MINLP approaches for these problems ignore the discreteness of the binary variables when dealing with the nonlinearity of the underlying functions. On the other hand, combinatorial algorithms designed specifically for dealing with submodular functions are inapplicable because of the various additional problem-specific side constraints present in these problems. Our approach will address the nonlinearity directly in the space of the binary variables by developing strong MILP reformulations of the nonlinear functions by exploiting submodularity along with other problem specific structure. The developed MILP schemes will be enhanced by integrating specialized combinatorial algorithms for submodular optimization. The proposed approaches will be specialized and tested on various classes of stochastic combinatorial optimization problems involving risk averse objectives where submodularity arises naturally from the concavity of risk aversion. If successful, the results from this research will advance the general area of MINLP by providing tools for effective linearization of nonlinear functions of binary variables. These tools can be embedded in modeling and solution software and hence impact various application areas including capital budgeting, combinatorial auctions, revenue management, and machine learning, that give rise to problems with submodular substructures. The project will require close integration of integer programming, submodular optimization, stochastic programming, and convex optimization methods; and new developments at the interface of these areas are anticipated. Specifically, new algorithmic techniques for various classes of stochastic programming models in combinatorial settings will be developed. More generally, results from this project can establish a novel framework for integrating specialized algorithms for combinatorial optimization problems within MILP approaches for general problems where the specific combinatorial problems arise as substructures.

本计画的研究目标是利用非线性函数的次模性，发展混合整数线性规划（MILP）方法，以解决包含二元非线性函数的混合整数非线性规划（MINLP）问题。现有的MINLP方法在处理底层函数的非线性时忽略了二元变量的离散性。另一方面，专门设计用于处理次模函数的组合算法是不适用的，因为在这些问题中存在各种额外的特定问题的侧约束。我们的方法将解决直接在二进制变量的空间中的非线性，通过开发强大的MILP重新制定的非线性函数，利用子模块沿着与其他问题的具体结构。开发的MILP计划将通过集成专门的组合算法子模块优化。所提出的方法将专门和测试各类随机组合优化问题，涉及风险厌恶的目标，其中子模块化自然产生的风险厌恶。如果成功的话，从这项研究的结果将推进MINLP的一般领域提供有效的线性化的二进制变量的非线性函数的工具。这些工具可以嵌入到建模和解决方案软件中，从而影响各种应用领域，包括资本预算，组合拍卖，收入管理和机器学习，这些应用领域会产生子模块子结构的问题。该项目将需要整数规划，子模块优化，随机规划和凸优化方法的紧密结合，并预计在这些领域的接口的新发展。具体而言，新的算法技术，各类随机规划模型的组合设置将开发。更一般地说，从这个项目的结果可以建立一个新的框架，集成专门的算法组合优化问题的MILP方法的一般问题，其中出现的具体组合问题的子结构。