My current research is focused on the design of efficient algorithms with analyzed performance for fundamental stochastic optimization models, arising in the context of supply chain and revenue management, as well as logistics. These fundamental multi-stage stochastic models are typically very hard to solve to optimality, both theoretically and in practice. We construct efficient heuristics that provide provably near-optimal policies for these hard models. In doing so we develop novel techniques that are applicable in a broad class of models.
I am also interested in modern LP-based approximation techniques applied to deterministic models in the above domains.
In addition, I am interested in stochastic optimization, combinatorical optimization and mathematical programming in their broad definition, and especially in their intersection with problems that arise in the context of real life applications.
In several papers with Martin Pal, Robin Roundy, David Shmoys and Van Anh Troung, we have considered fundamental single item stochastic inventory models with stochastic, correlated demands and dynamic forecasts updates. We have provided the first computationally efficient policies with worst-case performance guarantees for the uncapacitated and capacitated models, as well as to multi-echelon models. Our work is based on a novel marginal cost accounting approach and cost balancing techniques. In joint work with Gavin Hurley, Peter Jackson, Robin Roundy and David Shmoys, we have demostrated that these new policies outer perform existing heuristics in most typical real-life scenarios. Finally, in joint work with Ganesh Janakiranan and mahesh Nagarajan, we have considered inventory models with lost sales. These models have challenged researchers for over 50 years, as very little is known in regards to the structure of optimal policies, and computing good solutions seem to be very difficult even in the simplest settings. In particular, we have constructed the first policies for thesemodels that have worst-case guarantees.
In several joint papers with Robin Roundy and David Shmoys we have considered these fundamental and well-studied inventory models under the assumption that the explicit demand distributions are not known. Instead, what available is a set of independent samples that are drawn from the true demand distributions (e.g. historical data). We have then introduced sampling-based policies that are computed only based on the samples without any access to the demand distributions. Moreover, we have established bounds on the number of samples required to guarantee that, with high probability, the expected cost of our sampling-based policies is arbitrarily close to the optimal expected cost that is defined with respect to the true demand distributions. These bounds are general, easy to compute and surprisingly do not depend on the specific demand distributions.
In several joint papers with Robin Roundy, David Shmoys and Maxim Sviridenko we were able to design novel optimization and approximation algorithms for several classical deterministic inventory models such as the single-item lot-sizing, joint replenishment, assembly, one-warehouse-multi-retailers. These algorithms provide worst-case guarantees that hold under very general assumptions on the cost structure and outer perform previously known results. In addition, they present interesting new algorithmic ideas. In a joint work with David Shmoys and Chaitanya Swamy, we considered variants of the facility location problem, which better model real life applications. In particular, we provided the first LP-based constant factor approximation algorithm for a special case of the facility location problem with hard capacities.