...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >Complexity of min–max–min robustness for combinatorial optimization under discrete uncertainty
【24h】

Complexity of min–max–min robustness for combinatorial optimization under discrete uncertainty

机译：在离散不确定性下，MIN-MAX-MIN组合优化的鲁棒性的复杂性

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We consider combinatorial optimization problems with uncertain linear objective functions. In the min–max–min robust optimization approach, a fixed number?kof feasible solutions is computed such that the respective best of them is optimal in the worst case. The idea is to calculate the set of candidate solutions in a potentially expensive preprocessing phase and then select the best solution out of this set in real-time, once the actual scenario is known. In this paper, we investigate the complexity of the resulting min–max–min problem in the case of discrete uncertainty, as well as its connection to the classical min–max robust counterpart, for many classical combinatorial optimization problems. Essentially, it turns out that the min–max–min problem is not harder to solve than the min–max problem, while producing much better solutions in general for largerk. In particular, this approach may mitigate the so-called price of robustness, making it an attractive alternative to the classical robust optimization approach in many practical applications.
机译：我们考虑使用不确定的线性目标函数的组合优化问题。在MIN-MAX-MIN的鲁棒优化方法中，计算了固定数量？KOF可行的解决方案，使得它们在最坏情况下最佳最佳。该想法是在潜在的昂贵的预处理阶段计算一组候选解决方案，然后一旦知道实际场景，就可以实时选择了在该设置中的最佳解决方案。在本文中，我们研究了在离散的不确定性的情况下产生的最小MAX-min问题的复杂性，以及其与古典最大稳健对方的连接，对于许多经典组合优化问题。从本质上讲，事实证明，Min-Max-min问题比Min-Max问题更难解决，同时为Qualkr提供更好的解决方案。特别地，这种方法可能会降低所谓的稳健性价格，使其在许多实际应用中具有典型鲁棒优化方法的有吸引力的替代方案。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号