We study the best OSPF style routing problem in telecommunication networks, where weight management is employed to get a routing configuration with the minimum oblivious ratio. We consider polyhedral demand uncertainty: the set of traffic matrices is a polyhedron defined by a set of linear constraints, and the performance of each routing is assessed on … Read more
This paper extends the Log-robust portfolio management approach to the case with short sales, i.e., the case where the manager can sell shares he does not yet own. We model the continuously compounded rates of return, which have been established in the literature as the true drivers of uncertainty, as uncertain parameters belonging to polyhedral … Read more
Assigning products to and retrieving them from proper storage locations in a unit-load warehouse are crucial in minimizing its operating cost. The problem becomes intractable when the warehouse faces uncertain demand in a dynamic setting. We assume a factor-based demand model in which demand for each product in each period is affinely dependent on some … Read more
In this paper, single stage stochastic programs with ambiguous distributions for the involved random variables are considered. Though the true distribution is unknown, existence of a reference measure P enables the construction of non-parametric ambiguity sets as Kantorovich balls around P. The resulting robustified problems are infinite optimization problems and can therefore not be solved … Read more
To minimize or upper-bound the value of a function “robustly”, we might instead minimize or upper-bound the “epsilon-robust regularization”, defined as the map from a point to the maximum value of the function within an epsilon-radius. This regularization may be easy to compute: convex quadratics lead to semidefinite-representable regularizations, for example, and the spectral radius … Read more
The submodular knapsack set is the discrete lower level set of a submodular function. The modular case reduces to the classical linear 0-1 knapsack set. One motivation for studying the submodular knapsack polytope is to address 0-1 programming problems with uncertain coefficients. Under various assumptions, a probabilistic constraint on 0-1 variables can be modeled as … Read more
The traditional decision-making framework for newsvendor models is to assume a distribution of the underlying demand. However, the resulting optimal policy is typically sensitive to the choice of the distribution. A more conservative approach is to assume that the distribution belongs to a set parameterized by a few known moments. An ambiguity-averse newsvendor would choose … Read more
In this paper, we derive exponential bounds on probabilities of large deviations for “light tail” martingales taking values in finite-dimensional normed spaces. Our primary emphasis is on the case where the bounds are dimension-independent or nearly so. We demonstrate that this is the case when the norm on the space can be approximated, within an … Read more
We consider a general worst-case robust convex optimization problem, with arbitrary dependence on the uncertain parameters, which are assumed to lie in some given set of possible values. We describe a general method for solving such a problem, which alternates between optimization and worst-case analysis. With exact worst-case analysis, the method is shown to converge … Read more
The Minimum Capacity s-t Cut Problem (Min Cut) is an intensively studied problem in combinatorial optimization. In this paper, we study Min Cut when arc capacities are uncertain but known to exist in pre-specified intervals. This framework can be used to model many real-world applications of Min Cut under data uncertainty such as in open-pit … Read more