Successive Quadratic Upper-Bounding for Discrete Mean-Risk Minimization and Network Interdiction
Alper Atamtürk, Carlos Deck, Hyemin Jeon
INFORMS Journal on Computing · 2020 · Volume 32 · Issue 2
Abstract
The advances in conic optimization have led to its increased utilization for modeling data uncertainty. In particular, conic mean-risk optimization gained prominence in probabilistic and robust optimization. Whereas the corresponding conic models are solved efficiently over convex sets, their discrete counterparts are intractable. In this paper, we give a highly effective successive quadratic upper-bounding procedure for discrete mean-risk minimization problems. The procedure is based on a reformulation of the mean-risk problem through the perspective of its convex quadratic term. Computational experiments conducted on the network interdiction problem with stochastic capacities show that the proposed approach yields near-optimal solutions in a small fraction of the time required by exact-search algorithms. We demonstrate the value of the proposed approach for constructing efficient frontiers of flow at risk versus interdiction cost for varying confidence levels.
Keywords
risk, polymatroids, conic integer optimization, quadratic optimization, stochastic network interdiction
Enable JavaScript for citation tools and additional paper interactions.