Optimization Online


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

Alper Atamturk(atamturk***at***berkeley.edu)
Carlos Deck(cgdeck***at***berkeley.edu)
Hyemin Jeon(hyemin.jeon***at***berkeley.edu)

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 solutions within 1-2% of optimality 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 vs. interdiction cost for varying confidence levels.

Keywords: Risk, polymatroids, conic integer optimization, quadratic optimization, stochastic network interdiction

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Robust Optimization

Citation: BCOL Research Report 17.05, IEOR, UC Berkeley

Download: [PDF]

Entry Submitted: 12/30/2018
Entry Accepted: 12/30/2018
Entry Last Modified: 12/30/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society