Optimization of Value-at-Risk: computational aspects of MIP formulations. Issue 5 (4th May 2018) - Pavlikov, Konstantin; Veremyev, Alexander; Pasiliao, Eduardo L.
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.