Multistage robust optimization problems can be interpreted as two-person zero-sum games between two players. We exploit this game-like nature and utilize a game tree search in order to solve quantified integer programs (QIPs). In this algorithmic environment relaxations are repeatedly called to asses the quality of a branching variable and for the generation of bounds. A useful relaxation, however, must be well balanced with regard to its quality and its computing time. We present two relaxations that incorporate scenarios from the uncertainty set, whereby the considered set of scenarios is continuously adapted according to the latest information gathered during the search process. Using selection, assignment, and runway scheduling problems as a testbed, we show the impact of our findings.


翻译:多阶段强力优化问题可以被解释为两个玩家之间的双人零和游戏。 我们利用这种游戏般的自然,利用游戏树搜索来解决量化整数程序(QIPs QIPs ) 。 在这种算法环境中,反复要求放松时间来评估分支变量的质量和生成界限。 但是,有益的放松必须在其质量和计算时间上保持平衡。 我们提出的两个放松包括了来自不确定性的情景,根据搜索过程中收集的最新信息不断调整考虑的情景集。我们用选择、分配和跑道排期问题作为测试台,展示了我们发现的影响。

0
下载
关闭预览

相关内容

Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
【NeurIPS 2019的主要趋势】Key trends from NeurIPS 2019
专知会员服务
11+阅读 · 2019年12月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
鲁棒机器学习相关文献集
专知
8+阅读 · 2019年8月18日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
目标检测中的Consistent Optimization
极市平台
6+阅读 · 2019年4月23日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
计算机类 | 国际会议信息7条
Call4Papers
3+阅读 · 2017年11月17日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
Arxiv
0+阅读 · 2021年8月25日
Local Relation Networks for Image Recognition
Arxiv
4+阅读 · 2019年4月25日
Efficient and Effective $L_0$ Feature Selection
Arxiv
5+阅读 · 2018年8月7日
VIP会员
相关资讯
鲁棒机器学习相关文献集
专知
8+阅读 · 2019年8月18日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
目标检测中的Consistent Optimization
极市平台
6+阅读 · 2019年4月23日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
计算机类 | 国际会议信息7条
Call4Papers
3+阅读 · 2017年11月17日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
Top
微信扫码咨询专知VIP会员