Faster algorithms for min-max-min robustness for combinatorial problems with budgeted uncertainty

André B. Chassein, Marc Goerigk, Jannis Kurtz, Michael PossEur. J. Oper. Res 2019 · OpenReview

TL;DR

This paper tackles a robust optimization problem where decision-makers prepare a small set of "k" potential solutions in advance, choosing the best one once the true costs are revealed. They introduce efficient algorithms that significantly outperform previous methods, solving previously intractable problems in minutes.

What Problem Does This Paper Address?

In real-world decision-making, uncertainty is a constant challenge. Robust optimization aims to find solutions that perform well even under the worst-case scenarios. A specific variant, "min-max-min robustness with budgeted uncertainty," addresses situations where a decision-maker can prepare a limited number of "k" potential solutions before the exact costs are known. Upon learning the true costs, they can then select the best among these pre-prepared options. This is particularly relevant for problems where significant groundwork or preparation is needed in advance, such as disaster management or logistics planning. The challenge lies in efficiently finding these "k" robust solutions, especially when the number of possible scenarios is large and the underlying combinatorial problem is complex.

Methods

The authors propose three main algorithmic approaches:

  • Heuristic based on Dualized Non-Linear Reformulation: This method uses an alternating optimization strategy to find a good, though not necessarily optimal, solution for any value of "k."
  • Exact Spatial Branch-and-Bound Algorithm: Specifically designed for the case where "k=2," this algorithm leverages strong lower bounds to efficiently find the optimal solution.
  • Enumeration Algorithm: This approach enumerates "k-tuples" (sets of "k" solutions) and uses clever bounds to avoid a complete, exhaustive search, making it practical for small values of "k" (typically 2 or 3).

These algorithms are tailored for the "budgeted uncertainty set," a specific type of uncertainty model that has proven effective in various applications.

Datasets

The paper evaluates its algorithms on two types of instances:

  • Shortest Path Instances: These are taken from previous literature (Hanasusanto et al., 2015) and are characterized by the number of nodes, the number of candidate solutions "k," and the uncertainty budget "Γ."
  • Knapsack Instances: These are randomly generated instances for a minimization version of the knapsack problem, described by the number of items, "k," and "Γ."

Key Insights and Ideas

  • The Power of Pre-prepared Options: The "k-adaptability" framework, where a small set of solutions is prepared in advance, offers a practical way to handle uncertainty in scenarios requiring upfront preparation.
  • Budgeted Uncertainty as a Sweet Spot: The "budgeted uncertainty set" strikes a balance between tractability and realism, allowing for efficient algorithms while still capturing meaningful uncertainty.
  • Specialization for k=2 is Key: The development of a dedicated branch-and-bound algorithm for "k=2" proves highly effective, demonstrating that tailored approaches can yield significant performance gains.
  • Bounds are Crucial for Pruning: The effectiveness of the enumeration algorithm hinges on strong lower bounds that allow for significant pruning of the search space, avoiding the need to evaluate every possible combination.
  • Heuristics for Scalability: While exact methods struggle with larger "k," the proposed heuristic provides near-optimal solutions quickly, making it valuable for practical applications where optimality is not strictly required.

Key Results

The proposed algorithms significantly outperform previous approaches on shortest path instances. Previously unsolved problems that took hours are now solved in minutes, often seconds. For "k=2," the exact algorithms (EA and BB) are orders of magnitude faster than existing methods, with EA being particularly efficient. The heuristic algorithm also performs well, providing good quality solutions for larger "k" values. For knapsack problems, the cost reductions are smaller but still notable, and the exact algorithms generally perform well, though EA struggles with larger instances due to memory constraints.

Limitations and Future Work

  • Scalability for Larger k: The exact algorithms, particularly EA, face challenges with larger values of "k" due to the combinatorial explosion of the search space.
  • Memory Requirements for EA: The enumeration algorithm (EA) can be memory-intensive, as observed with large instances of the shortest path problem.
  • Future Directions: The authors plan to develop algorithms that can solve problems exactly for larger "k" and more general uncertainty sets. They suggest exploring strong integer programming tools and extended formulations, as preliminary results indicate promising linear programming relaxations.

Summary updated

Abstract

Highlights•Prepare k solutions and choose the best of them upon knowledge of the true costs.•We provide fast exact algorithms for the problem for k=2.•Our heuristic yields close to optimal solutions for larger k.•Unsolved shortest path instances from the literature are now solved in minutes.
BibTeX
@article{chassein2019faster,
  author = {André B. Chassein and Marc Goerigk and Jannis Kurtz and Michael Poss},
  title = {{Faster algorithms for min-max-min robustness for combinatorial problems with budgeted uncertainty}},
  journal = {Eur. J. Oper. Res.},
  year = {2019},
  url = {https://openreview.net/forum?id=d21JdkLA4v},
}
Figure