Optimization of Value-at-Risk: computational aspects of MIP formulations
研究了风险价值优化问题中混合整数规划公式的大M常数紧化方法，提出利用最优值上下界改进紧性，并设计两阶段求解方案，实验表明求解时间最多可降低75%。
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 Ms 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 Ms 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.