Exploiting Submodularity in Integer Programming

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

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.