Network-Based Approximate Linear Programming for Discrete Optimization
Selvaprabu Nadarajah, Andre A. Cire
Operations Research · 2020 · Volume 68 · Issue 6
Abstract
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 side-step 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.
Keywords
decision analysis: sequential, dynamic programming: deterministic, networks/graphs: heuristics, programming: integer: algorithms, programming: integer: nonlinear, programming: large scale systems, Optimization, discrete optimization, approximate linear programming, state-space aggregation, networks, dynamic programming
Enable JavaScript for citation tools and additional paper interactions.