2025 Theses Doctoral

Robust and Tractable Policies for Resource Allocation under Uncertainty.

Foussoul, Ayoub

Decision-making under uncertainty is a central challenge in many resource planning and allocation problems including inventory planning, order fulfillment, supply chain management, revenue management, scheduling, and matching. Effectively addressing this challenge requires careful modeling of uncertainty based on available information and a tailored design of solution methods adapted to the specific recourse mechanisms involved. In this dissertation, we study fundamental resource allocation problems under uncertainty.

Chapters 1 and 2 focus on inventory planning and allocation under demand uncertainty. Specifically, in Chapter 1, we consider a multi-product setting where the decision-maker first sets initial inventory levels for each product. Then, after demand is realized, they are allowed to order more inventory, typically at a higher cost. The decision maker has access to an uncertainty set of possible customer demand scenarios and seeks to minimize costs in the face of the worst-case scenario of demand. This is modeled through a two-stage robust optimization problem for which we develop an LP-based approximation with provable guarantees that nearly match the hardness of the problem. Our approximation is also shown to be significantly faster than state-of-the-art solution methods. Our approximation leverages an interesting connection between the two-stage robust problem and disjoint bilinear programming and is closely related to the widely used affine policies.

In Chapter 2, we study a multi-location inventory problem where the decision maker first plans inventory allocation across multiple locations and subsequently decides how to fulfill sequentially realizing customer demand. The decision maker has only access to moment information about the cross-location customer demand and seeks to minimize costs under the worst-case demand distribution consistent with the moment information. We develop and analyze a policy that significantly extends the seminal solution of Scarf (1957) to the multi-location setting. Our solution methodology introduces a novel hierarchical clustering of metric spaces which may be of independent interest in robust and distributionally robust multi-location inventory management under uncertainty. We establish theoretical guarantees for our policy’s performance and demonstrate its empirical effectiveness through extensive numerical experiments.

In Chapter 3, we study the load balancing problem in an adversarial setting where jobs arrive and depart arbitrarily from a set of machines. Recourse actions (job reassignments) are allowed and the goal is to maintain a small maximum load using a small number of reassignments. This arises in many practical applications including task-machine assignments in data centers and bike-sharing systems. We propose a constant competitive algorithm with constant amortized recourse under bounded job degrees. This improves upon the previously known bounds for the problem which are logarithmic in the number of jobs.

In Chapter 4, we study the problem of assigning students to schools in which students and/or school seats often enter and leave the market after an initial stable matching is decided. The goal is to choose an initial stable matching that, in addition to being of high-quality, allows for adaptations with minimal changes after uncertainty is revealed. We study the problem in a two-stage stochastic framework and design a (pseudo)-polynomial algorithm.