Hard Instances, Improved Algorithms and New Interdiction Models for Robust Optimization

Robust combinatorial optimization seeks solutions that remain effective across all possible realizations of an uncertainty set, making the choice of this set a crucial factor in both the complexity and practical applicability of robust models. A key challenge in this field is striking a balance between computational tractability and solution quality, particularly when dealing with large uncertainty sets. This dissertation advances the field of robust optimization by addressing three central themes: (i) methods for generating hard instances and establishing a benchmark library, (ii) high-quality exact solution methods and approximation algorithms, and (iii) the modeling of uncertainty sets and their impact on problem complexity. The absence of a benchmark library for robust optimization problems makes it difficult to conduct fair and effective comparisons of different solution methods. As a result, researchers often rely on randomly generated instances, which may hinder meaningful evaluations. To address this issue, this work develops optimization-based and heuristic methods for generating challenging instances of robust problems. Additionally, to facilitate more consistent and insightful comparisons of solution algorithms with minimal effort, we introduce a standardized benchmark library for use by the research community. To tackle the computational challenges posed by large uncertainty sets, this dissertation proposes scenario reduction techniques specifically designed for robust optimization. These methods aim to reduce the size of the uncertainty set while preserving the objective value as accurately as possible. Unlike traditional clustering approaches, this formulation treats scenario reduction as an optimization problem independent of the underlying decision-making model, enabling structured reductions with theoretical performance guarantees. Experimental results demonstrate that this approach produces solutions of comparable or superior quality compared to those obtained through general-purpose clustering techniques. Building on this framework, we further refine scenario reduction by incorporating information about the structure of feasible solutions. While previous reduction methods focused exclusively on the uncertainty set, we show that integrating knowledge of feasible solutions leads to improved uncertainty sets and more accurate robust models. Through a combination of theoretical analysis and computational experiments, we establish the effectiveness of this approach in enhancing both tractability and solution quality in robust combinatorial optimization. Finally, we introduce a novel variant of discrete budgeted uncertainty for cardinality-based constraints or objectives, incorporating a weight vector into the budget constraint. Our theoretical analysis reveals that while the adversarial problem can be solved in linear time, the robust problem becomes NP-hard and non-approximable. Nonetheless, we propose and evaluate alternative modeling approaches that demonstrate promising scalability in practice. This dissertation contributes to robust optimization by offering new perspectives on uncertainty modeling, algorithmic techniques for scenario reduction, and complexity analyses of key robust problems. The proposed methods provide both theoretical guarantees and practical advancements, paving the way for more efficient and scalable robust optimization models.

Level thesis:degree_level

thesis.doctoral

Grantor dc:publisher

Universität Passau

Year

2025

Author dc:creator

• Khosravi, Mohammad

Contributors dc:contributor

• Goerigk, Marc

Statement dc:rights

• Standardbedingung laut Einverständniserklärung

Repository record source_url

https://opus4.kobv.de/opus4-uni-passau/frontdoor/index/index/docId/2039

OAI identifier oai:identifier

oai:kobv.de-opus4-uni-passau:2039