Abstract
This work investigates the min-max-min robust optimization and k-adaptability problems for binary combinatorial problems under cost uncertainty. While classical robust optimization seeks a single solution that performs well in the worst case, the min-max-min approach calculates a set of $k$ solutions, implementing the best one once the specific scenario is revealed. Historically, this problem was known to be tractable when $k$ equals the problem dimension ($n$) and NP-hard for small $k$. This paper addresses the "intermediate" case, providing the first approximation algorithms with provable guarantees. We demonstrate that these problems are solvable in oracle-polynomial time under certain conditions even when $k < n$. Empirical evaluations on knapsack and shortest path problems confirm that our algorithms achieve near-optimal solutions in seconds.
Introduction
In classical Robust Optimization (RO), decision-makers seek a single solution that minimizes the maximum possible cost across all potential scenarios. While this provides a safety net, it often leads to "conservative" solutions—strategies that perform poorly in likely scenarios just to mitigate a single, unlikely worst-case event.
To introduce flexibility, researchers developed the min-max-min robust optimization framework. Instead of committing to one solution, the decision-maker selects a set of $k$ feasible solutions. After the uncertainty (the actual cost scenario) is revealed, the best of these $k$ solutions is implemented. This framework is particularly relevant in two-stage decision processes where some flexibility remains after initial planning.
The Complexity of the "Intermediate" Case
The computational complexity of min-max-min problems depends heavily on $k$.
- $k=1$: This is standard robust optimization, which is NP-hard for many combinatorial problems.
- $k \ge n$: If the number of solutions is at least the dimension of the problem, the problem becomes efficiently solvable by treating it as a continuous convex optimization over the convex hull of feasible solutions.
- $1 < k < n$: This intermediate range has long been a theoretical "no-man's land." It was known to be NP-hard, but its approximability and the transition of its complexity as $k$ approaches $n$ remained unknown.
Proposed Methodology
This paper introduces Algorithm 1, a two-step approximation strategy designed to bridge this gap:
- Convex Relaxation: The algorithm first solves the "easy" version of the problem where $k=n$. This involves finding an optimal convex combination of solutions that minimizes the worst-case cost.
- Filtering and Selection: From the resulting optimal convex combination, the algorithm selects the $k$ solutions with the largest weights ($\lambda$).
Additionally, the paper proposes a Sparsity Variant that more aggressively searches for the best $k$ solutions within the convex hull, offering tighter bounds at a higher computational cost. These methods are also extended to the k-adaptability problem, a two-stage robust framework where some decisions are fixed upfront and others are selected from a set of $k$ policies post-uncertainty.
Theoretical Insights
The most significant contribution is the proof that the approximation error converges to zero as $k$ approaches $n$. The gap between the approximation and the true optimum is bounded by a factor related to $(n-k)/(k+1)$.
Furthermore, the paper establishes Oracle-Polynomial Tractability: if $k = n - l$ for some fixed constant $l$, the problem can be solved to within any $\epsilon$ accuracy in polynomial time. This suggests that the "hard" region of the problem is significantly smaller than previously assumed. These guarantees are problem-specific; for structures like Spanning Trees or Matchings on complete graphs, the approximation bounds are particularly robust.
Experimental Results
The algorithms were tested on several classic combinatorial benchmarks, including the Minimum Knapsack Problem (KP) and the Shortest Path Problem (SPP).
- Knapsack Performance: For KP instances with 50-100 items, the optimality gap was remarkably small. Even with $k=4$, the gap was less than 1.5%. For $k \ge 10$, the algorithm frequently identified the exact optimal solution.
- Shortest Path Performance: The SPP proved more challenging for very small $k$, but the algorithm reached near-optimality as $k$ approached 20. The Sparsity Variant significantly outperformed the basic filtering method in these instances.
- Computational Efficiency: Across all tests, the algorithms calculated solutions in seconds, providing a viable alternative to exact solvers which often struggle with these dimensions.
Conclusion and Future Work
This research provides a new theoretical foundation for multi-solution robust optimization. By proving that the intermediate $k$ range is highly approximable, it opens the door for more flexible risk management in logistics and network design.
Future research will address constraint uncertainty, where the feasibility of a solution (not just its cost) depends on the scenario. While the current work focuses on objective uncertainty, extending these approximation guarantees to uncertain constraints remains a significant challenge in the field.
Summary updated