We develop a new class of approximate linear programs (ALPs) that project the high-dimensional value function of dynamic programs onto a class of basis functions, each defined as a network that represents aggregrations over the state space. The resulting ALP is a minimum-cost flow problem over an extended variable space that synchronizes flows across multiple networks. Its solution provides a value function approximation that can be used to obtain feasible solutions and optimistic bounds. Such bounds from multiple networks are weakly stronger than their counterparts from a single network. We present a scheme for iteratively constructing a finite sequence of network ALPs with improving optimistic bounds that converge to the optimal solution value of the original problem. In addition, we provide a tractable approximation of a network ALP based on the chordalization of an auxiliary graph. We assess the performance of the ALP bounds and feasible solutions using a branch-and-bound scheme to obtain optimal solutions. We apply this scheme to challenging bilinear and routing problems arising in marketing analytics and preemptive maintenance. Numerical results show that the network ALP significantly outperforms a state-of-the-art mathematical programming solver both in solution quality and time.
Citation
Working Paper, 2017, College of Business Administration, University of Illinois at Chicago, Chicago, Illinois 60607, and Dept. of Management, University of Toronto Scarborough and Rotman School of Management, Toronto, Ontario M1C-1A4
Article
View Network-based Approximate Linear Programming for Discrete Optimization