Abstract | ||
---|---|---|
AbstractThis paper investigates a decomposition approach for binary optimization problems with nonlinear objectives and linear constraints. Our methodology relies on the partition of the objective function into separate low-dimensional dynamic programming DP models, each of which can be equivalently represented as a shortest-path problem in an underlying state-transition graph. We show that the associated transition graphs can be related by a mixed-integer linear program MILP so as to produce exact solutions to the original nonlinear problem. To address DPs with large state spaces, we present a general relaxation mechanism that dynamically aggregates states during the construction of the transition graphs. The resulting MILP provides both lower and upper bounds to the nonlinear function, and it may be embedded in branch-and-bound procedures to find provably optimal solutions. We describe how to specialize our technique for structured objectives e.g., submodular functions and consider three problems arising in revenue management, portfolio optimization, and healthcare. Numerical studies indicate that the proposed technique often outperforms state-of-the-art approaches by orders of magnitude in these applications.Data and the online appendix are available at https://doi.org/10.1287/mnsc.2017.2849. This paper was accepted by Yinyu Ye, optimization. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1287/mnsc.2017.2849 | Periodicals |
Keywords | Field | DocType |
nonlinear,algorithms,programming,integer,network-graphs,dynamic programming,optimal control,finite state | Dynamic programming,Economics,Mathematical optimization,Optimal control,Nonlinear system,Nonlinear programming,Submodular set function,Linear programming,Partition (number theory),State space | Journal |
Volume | Issue | ISSN |
64 | 10 | 0025-1909 |
Citations | PageRank | References |
2 | 0.35 | 29 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
David Bergman | 1 | 37 | 7.54 |
André A. Ciré | 2 | 94 | 12.87 |