Discrete Nonlinear Optimization by State-Space Decompositions

David Bergman () and Andre A. Cire ()
Additional contact information
David Bergman: Department of Operations and Information Management, University of Connecticut, Stamford, Connecticut 06901
Andre A. Cire: Department of Management, University of Toronto Scarborough, Scarborough, Ontario M1C 1A4, Canada; Rotman School of Management, Toronto, Ontario M5S 3E6, Canad

Management Science, 2018, vol. 64, issue 10, 4700-4720

Abstract: This 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.

Keywords: nonlinear; algorithms; programming; integer; network-graphs; dynamic programming; optimal control; finite state (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://doi.org/10.287/mnsc.2017.2849 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:64:y:2018:i:10:p:4700-4720

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().