Successive Quadratic Upper-Bounding for Discrete Mean-Risk Minimization and Network Interdiction

Alper Atamtürk (), Carlos Deck () and Hyemin Jeon ()
Additional contact information
Alper Atamtürk: Department of Industrial Engineering and Operations Research, University of California, Berkeley, Berkeley, California 94720
Carlos Deck: Department of Industrial Engineering and Operations Research, University of California, Berkeley, Berkeley, California 94720
Hyemin Jeon: Department of Industrial Engineering and Operations Research, University of California, Berkeley, Berkeley, California 94720

INFORMS Journal on Computing, 2020, vol. 32, issue 2, 346-355

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 (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0870 (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:orijoc:v:32:y:2020:i:2:p:346-355

Access Statistics for this article

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