Network-Based Approximate Linear Programming for Discrete Optimization
将离散优化问题转化为高维动态规划，用线性规划近似求解，结合状态空间聚合、网络和完美图理论，在分支定界框架下显著优于商业求解器和聚合启发式方法。
Several prescriptive tasks in business and engineering as well as prediction in machine learning entail the solution of challenging discrete optimization problems. We recast the typical optimization formulation of these problems as high-dimensional dynamic programs and approach their approximation via linear programming. We develop tractable approximate linear programs with supporting theory by bringing together tools from state-space aggregations, networks, and perfect graphs (i.e., graph completions). We embed these models in a simple branch-and-bound scheme to solve applications in marketing analytics and the maintenance of energy or city-owned assets. We find that the resulting technique substantially outperforms a state-of-the-art commercial solver as well as aggregation-heuristics in terms of both solution quality and time. Our results motivate further consideration of networks and graph theory in approximate linear programming for solving deterministic and stochastic discrete optimization problems.