Optimization of Value-at-Risk: computational aspects of MIP formulations. Issue 5 (4th May 2018)

• Record Type: Journal Article
• Authors: Pavlikov, Konstantin; Veremyev, Alexander; Pasiliao, Eduardo L.
• Is Part Of: Journal of the Operational Research Society. Volume 69:Issue 5(2018)
• Page Start: 676
• Page End: 690
• Publication Date: 2018-05-04
• Subjects: Chance-constrained programming -- percentile minimization -- combinatorial optimization -- Value-at-Risk -- Conditional Value-at-Risk; Operations research -- Periodicals; 658.4034
• DOI: 10.1057/s41274-017-0197-4
• Languages: English
• ISSNs: 0160-5682

Abstract

Abstract: Optimization of Value-at-Risk is an important problem both from theoretical and practical standpoints. It can be represented through a class of chance-constrained optimization problems, which are generally hard to solve. Mixed integer problem formulations with big M constants is a standard way to approach such problems, where tightness of these constants is a crucial factor for good performance of a solver. This study aims to improve the tightness of existing big M s by explicitly incorporating bounds on the optimal value of VaR into the problem formulation. Moreover, the lower bound is demonstrated to play an especially important role in obtaining tight big M constants, and a procedure to lift this bound is discussed. Finally, a "two-stage" solution approach is proposed, where the first stage solely deals with tightening the bounds, and the second stage employs improved bounds to redefine big M s and solves the problem to optimality. Numerical experiments suggest that proposed solution methods can decrease solution time by up to 75% compared to the most recent benchmark, which may allow to handle larger problem instances while using the same hardware.