Minmax regret combinatorial optimization problems with ellipsoidal uncertainty sets

详细信息    查看全文

• 作者：André ; Chassein^a ; ^{chassein@mathematik.uni-kl.de} ; Marc Goerigk ; ^b ; ^{m.goerigk@lancaster.ac.uk}
• 关键词：Robust optimization ; Minmax regret ; Ellipsoidal uncertainty ; Complexity ; Scenario relaxation
• 刊名：European Journal of Operational Research
• 出版年：2017
• 出版时间：1 April 2017
• 年：2017
• 卷：258
• 期：1
• 页码：58-69
• 全文大小：896 K
• 卷排序：258

文摘

We analyze the minmax regret objective function for ellipsoidal uncertainty sets. The complexity of evaluating a solution and finding the best solution is investigated. We give complexity results for several combinatorial optimization problems. Two different cut generating strategies for an exact solution procedure are defined. Both are applied to unconstrained and shortest path problems in experiments.