Optimization Online


Network-based Approximate Linear Programming for Discrete Optimization

Selvaprabu Nadarajah(selvan***at***uic.edu)
Andre Augusto Cire(acire***at***utsc.utoronto.ca)

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

Keywords: discrete optimization, approximate linear programming, networks

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 2: Other Topics (Dynamic Programming )

Category 3: Integer Programming ((Mixed) Integer Nonlinear Programming )

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

Download: [PDF]

Entry Submitted: 12/03/2017
Entry Accepted: 12/03/2017
Entry Last Modified: 12/03/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society