Vineet Goyal In this paper, we study the performance of affine policies for two-stage adjustable robust optimization problem with uncertain right hand side belonging to a budgeted uncertainty set. This is an important class of uncertainty sets widely used in practice where we can specify a budget on the adversarial deviations of the uncertain parameters from the … Read more
We consider the problem of designing piecewise affine policies for two-stage adjustable robust linear optimization problems under right-hand side uncertainty. It is well known that a piecewise affine policy is optimal although the number of pieces can be exponentially large. A significant challenge in designing a practical piecewise affine policy is constructing good pieces of … Read more
In this paper, we consider two-stage adjustable robust linear optimization problems under uncertain constraints and study the performance of piecewise static policies. These are a generalization of static policies where we divide the uncertainty set into several pieces and specify a static solution for each piece. We show that in general there is no piecewise … Read more
In this paper, we study the performance of static solutions in two-stage adjustable robust packing linear optimization problem with uncertain constraint coefficients. Such problems arise in many important applications such as revenue management and resource allocation problems where demand requests have uncertain resource requirements. The goal is to find a two-stage solution that maximizes the … Read more
Assortment optimization is an important problem that arises in many practical applications such as retailing and online advertising. In an assortment optimization problem, the goal is to select a subset of items that maximizes the expected revenue in the presence of the substitution behavior of consumers specified by a choice model. In this paper, we … Read more
We consider a two-stage mixed integer stochastic optimization problem and show that a static robust solution is a good approximation to the fully-adaptable two-stage solution for the stochastic problem under fairly general assumptions on the uncertainty set and the probability distribution. In particular, we show that if the right hand side of the constraints is … Read more
We consider a quadratic programming (QP) problem ($\Pi$) of the form $\min x^T C x$ subject to $Ax \ge b$ where $C\in {\mathbb R}^{n\mbox{\tiny\texttimes} n}_+, rank(C)=1$ and $A\in {\mathbb R}^{m\mbox{\tiny\texttimes} n}, b\in {\mathbb R}^m$. We present an FPTAS for this problem by reformulating the QP ($\Pi$) as a parametrized LP and “rounding” the optimal solution. … Read more
In this paper we address the following probabilistic version (PSC) of the set covering problem: $min \{ cx \ |\ {\mathbb P} (Ax\ge \xi) \ge p,\ x_{j}\in \{0,1\}^N\}$ where $A$ is a 0-1 matrix, $\xi$ is a random 0-1 vector and $p\in (0,1]$ is the threshold probability level. We formulate (PSC) as a mixed integer … Read more