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 ) 。 在这种算法环境中,反复要求放松时间来评估分支变量的质量和生成界限。 但是,有益的放松必须在其质量和计算时间上保持平衡。 我们提出的两个放松包括了来自不确定性的情景,根据搜索过程中收集的最新信息不断调整考虑的情景集。我们用选择、分配和跑道排期问题作为测试台,展示了我们发现的影响。