We develop an algorithm for minimax problems that arise in robust optimization in the absence of objective function derivatives. The algorithm utilizes an extension of methods for inexact outer approximation in sampling a potentially infinite-cardinality uncertainty set. Clarke stationarity of the algorithm output is established alongside desirable features of the model-based trust-region subproblems encountered. We … Read more
Two-stage robust optimization problems, in which decisions are taken both in anticipation of and in response to the observation of an unknown parameter vector from within an uncertainty set, are notoriously challenging. In this paper, we develop convergent hierarchies of primal (conservative) and dual (progressive) bounds for these problems that trade off the competing goals … Read more
We focus on the discretization approach to distributionally robust optimization (DRO) problems and propose a numerical scheme originated from the primal-dual hybrid gradient (PDHG) method that recently has been well studied in convex optimization area. Specifically, we consider the cases where the ambiguity set of the discretized DRO model is defined through the moment condition … Read more
In this paper, we investigate optimal policies of distributionally robust (risk averse) inventory models. We demonstrate that if the respective risk measures are not strictly monotone, then there may exist infinitely many optimal policies which are not base-stock and not time consistent. This is in a sharp contrast with the risk neutral formulation of the … Read more
Given an originally robust optimal decision and allowing perturbation parameters of the linear programming problem to run through a maximum uncertainty set controlled by a variable of perturbation radius, we do robust sensitivity analysis for the robust linear programming problem in two scenarios. One is to keep the original decision still robust optimal, the other … Read more
We study in this paper min max robust combinatorial optimization problems for an uncertainty polytope that is defined by knapsack constraints, either in the space of the optimization variables or in an extended space. We provide exact and approximation algorithms that extend the iterative algorithms proposed by Bertismas and Sim (2003). We also study the … Read more
In this paper, we propose new constraint generation algorithms for solving the two-stage robust minimum cost flow problem, a problem that arises from various applications such as transportation and logistics. In order to develop efficient algorithms under general polyhedral uncertainty set, we repeatedly exploit the network-flow structure to reformulate the two-stage robust minimum cost flow … Read more
In this survey, we discuss the state-of-the-art of robust combinatorial optimization under uncertain cost functions. We summarize complexity results presented in the literature for various underlying problems, with the aim of pointing out the connections between the different results and approaches, and with a special emphasis on the role of the chosen uncertainty sets. Moreover, … Read more
This paper jointly addresses two major challenges in power system operations: i) dealing with non-convexity in the power flow equations, and ii) systematically capturing uncertainty in renewable power availability and in active and reactive power consumption at load buses. To overcome these challenges, this paper proposes a two-stage adaptive robust optimization model for the multi-period … Read more
The simple integer recourse (SIR) function of a decision variable is the expectation of the integer round-up of the shortage/surplus between a random variable with a known distribution and the decision variable. It is the integer analogue of the simple (continuous) recourse function in two stage stochastic linear programming. Structural properties and approximations of SIR … Read more