Exploiting Submodularity in 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.