Network-Based Approximate Linear Programming for Discrete Optimization

Selvaprabu Nadarajah () and Andre A. Cire ()
Additional contact information
Selvaprabu Nadarajah: College of Business Administration, University of Illinois at Chicago, Chicago, Illinois 60607
Andre A. Cire: Department of Management, University of Toronto Scarborough and Rotman School of Management, Toronto, Ontario M1C 1A4, Canada

Operations Research, 2020, vol. 68, issue 6, 1767-1786

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: discrete optimization; approximate linear programming; state-space aggregation; networks; dynamic programming (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/opre.2019.1953 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:68:y:2020:i:6:p:1767-1786

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().