Exact and Heuristic Solution Techniques for Mixed-Integer Quantile Minimization Problems
研究了混合整数线性分位数最小化问题，针对电力网络维护规划和投资组合优化两个实际场景，提出了有效不等式、重叠交替方向法和自适应场景聚类方法，并在大规模实例上验证了效果。
We consider mixed-integer linear quantile minimization problems that yield large-scale problems that are very hard to solve for real-world instances. We motivate the study of this problem class by two important real-world problems: a maintenance planning problem for electricity networks and a quantile-based variant of the classic portfolio optimization problem. For these problems, we develop valid inequalities and present an overlapping alternating direction method. Moreover, we discuss an adaptive scenario clustering method for which we prove that it terminates after a finite number of iterations with a global optimal solution. We study the computational impact of all presented techniques and finally show that their combination leads to an overall method that can solve the maintenance planning problem on large-scale real-world instances provided by the ROADEF/EURO challenge 2020 1 and that they also lead to significant improvements when solving a quantile-version of the classic portfolio optimization problem. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by the Deutsche Forschungsgemeinschaft [CRC TRR 154], Fonds De La Recherche Scientifique [PDR T0098.18], and Bundesministerium für Bildung und Forschung. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.0105 .