Lagrangean Decomposition for Mean-Variance Combinatorial Optimization
Lagrangean Decomposition for Mean-Variance Combinatorial Optimization
复制标题
DOI：
10.1007/978-3-319-09174-7_6
复制
发表时间：
2014-03
期刊：
影响因子：
--
通讯作者：
F. Baumann;C. Buchheim;A. Ilyina
中科院分区：
文献类型：
--
作者：
F. Baumann;C. Buchheim;A. Ilyina
我们解决了组合优化问题的鲁棒版本，重点关注不相关椭球体不确定性情况，这对应于所谓的均值方差优化。利用拉格朗日分解得到的下界，给出了一个分支定界算法。这种方法可以将目标函数的不确定性与可行集的组合结构分离开来。我们设计了一种组合算法来有效地解决无限制二进制子问题，而底层的组合优化问题可以用任何黑盒求解器来解决。实验评估表明，当应用于鲁棒最短路径问题和投资组合优化中出现的风险厌恶资本预算问题时，我们的方法明显优于其他均值方差优化方法。
We address robust versions of combinatorial optimization problems, focusing on the uncorrelated ellipsoidal uncertainty case, which corresponds to so-called mean-variance optimization. We present a branch and bound-algorithm for such problems that uses lower bounds obtained from Lagrangean decomposition. This approach allows to separate the uncertainty aspect in the objective function from the combinatorial structure of the feasible set. We devise a combinatorial algorithm for solving the unrestricted binary subproblem efficiently, while the underlying combinatorial optimization problem can be addressed by any black box-solver. An experimental evaluation shows that our approach clearly outperforms other methods for mean-variance optimization when applied to robust shortest path problems and to risk-averse capital budgeting problems arising in portfolio optimization.