Network-Based Approximate Linear Programming for Discrete Optimization

• 成果类型: Article
• 署名作者: Nadarajah, Selvaprabu; Cire, Andre A.
• 署名单位: University of Illinois System; University of Illinois Chicago; University of Illinois Chicago Hospital; University of Toronto; University Toronto Scarborough; University of Toronto
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2019.1953
• 发表日期: 2020
• 页码: 1767-1786
• 关键词: discrete optimization; approximate linear programming; state-space aggregation; networks; dynamic programming

摘要

We present relaxations for discrete optimization problems using approximate linear programs (ALPs) defined on multiple networks that represent different state-space aggregations. Our network ALP leverages information across these networks using a piecewise-constant value function approximation, and its optimistic bound is theoretically guaranteed to weakly improve upon the bounds from the individual networks used in its construction. Solving network ALPs is challenging because of its large number of constraints-a well-known issue when employing approximate linear programming. We sidestep this issue by using a clique-based graph representation to design a network ALP restriction that admits a polynomial-time solvable extended formulation, which we show to also deliver a weakly better bound than individual networks. We execute a computational study on a challenging bilinear problem arising in marketing analytics and a routing application encountered in the preemptive maintenance of energy or city-owned assets. When used within a branch-and-bound scheme, the network ALP restriction significantly outperforms in both solution quality and time the following benchmarks: a state-of-the-art mathematical programming solver, a generic aggregation/disaggregation scheme applied to a single network, and a heuristic that chooses the best bound among individual networks.