Thursday, October 18, 2018
12:00pm-1:00pm
MB 128
Mining Building
Network-based Approximate Linear Programming
Abstract
Discrete optimization is a pivotal tool in the solution of a diverse range of business and engineering applications, with applications in supply chains, vehicle routing, scheduling, and marketing, to name a few. Such formulations typically yield NP-hard problems that are addressed in practice by sophisticated enumerative and decomposition methods. In this context, dynamic programming has played an important role in the development of state-of-the-art exact and approximate discrete optimization methodologies, specifically in combination with mathematical programming.
In this talk we present a new class of relaxations for discrete optimization problems using approximate linear programs (ALPs). Our ALPs are defined on multiple state-space aggregations of dynamic programs, also perceived as networks, that exploit the combinatorial structure of a problem in different ways. Solving this network ALPs is, however, challenging due to its exponential number of constraints – a well-known issue from the approximate linear programming field. We address this problem by formulating a network ALP restriction that incorporates symmetry and admits a polynomial-time solvable extended formulation. We discuss 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 a state-of-the-art mathematical programming solver, a generic aggregation/dissaggregation scheme applied to a single network, and a heuristic that chooses the best bound among individual networks.
Speaker bio
Andre Cire is an Assistant Professor at the Department of Management at University of Toronto Scarborough, cross-appointed with the Operations Management area at Rotman School of Management. His main research interests include discrete optimization, mathematical programming, constraint programming, and practical applications of scheduling and routing. Andre’s recent work focuses on hybrid methods that exploit the interface between operations management and computer science for the purpose of developing computationally efficient methods for hard and large-scale optimization problems.
