It is well known that the performance of the classical Markowitz model for portfolio optimization is extremely sensitive to estimation errors on the expected asset returns. Robust optimization mitigates this issue. We focus on ellipsoidal uncertainty sets around a point estimate of the expected asset returns. An important issue is the choice of the parameters … Read more
This paper studies effective scenarios in Distributionally Robust Optimization (DRO) problems defined on a finite number of realizations (also called scenarios) of the uncertain parameters. Effective scenarios are critical scenarios in DRO in the sense that their removal from the support of the considered distributions alters the optimal value. Ineffective scenarios are those whose removal … Read more
We provide a correction to the sufficient conditions under which closed-form expressions for the optimal Lagrange multiplier are provided in Subramanyam (2022). We first present a simple counterexample where the original conditions are insufficient, highlight where the original proof fails, and then provide modified conditions along with a correct proof of their validity. Finally, although … Read more
Distributionally robust optimization (DRO) studies decision problems under uncertainty where the probability distribution governing the uncertain problem parameters is itself uncertain. A key component of any DRO model is its ambiguity set, that is, a family of probability distributions consistent with any available structural or statistical information. DRO seeks decisions that perform best under the … Read more
Understanding the variation of the optimal value with respect to change in the data is an old problem of mathematical optimisation. This paper focuses on the linear problem f(λ) = min ctx such that (A+λD)x ≤ b, where λ is an unknown parameter that varies within an interval and D is a matrix modifying the … Read more
This paper considers the robust phase retrieval, which can be cast as a nonsmooth and nonconvex optimization problem. We propose two first-order algorithms with adaptive step sizes: the subgradient algorithm (AdaSubGrad) and the inexact proximal linear algorithm (AdaIPL). Our contribution lies in the novel design of adaptive step sizes based on quantiles of the absolute … Read more
In the realm of robust optimization the k-adaptability approach is one promising method to derive approximate solutions for two-stage robust optimization problems. Instead of allowing all possible second-stage decisions, the k-adaptability approach aims at calculating a limited set of k such decisions already in the first-stage before the uncertainty reveals. The parameter k can be … Read more
The Appointment Scheduling Problem (ASP) involves scheduling a finite number of customers with uncertain service times, served consecutively by a single server, aiming to minimize the weighted costs of waiting time, idle time, and overtime. Previous studies using stochastic programming were limited to small instances. We introduce a Robust Optimization (RO) approach that considers service … Read more
The b-matching problem is a well-known generalization of the classical matching problem with various applications in operations research and computer science. Given an undirected graph, each vertex v has a capacity b(v), indicating the maximum number of times it can be matched, while edges can also be used multiple times. The problem is solvable in … Read more
We present an algorithm for finding near-optimal solutions to robust combinatorial optimization problems with knapsack constraints under interdiction uncertainty. We incorporate a heuristic for generating feasible solutions in a standard row generation approach. Experimental results are presented for set covering, simple plant location, and min-knapsack problems under a discrete-budgeted interdiction uncertainty set introduced in this … Read more