서브메뉴
검색
Robust and Tractable Policies for Resource Allocation under Uncertainty
Robust and Tractable Policies for Resource Allocation under Uncertainty
상세정보
- 자료유형
- 학위논문 서양
- 최종처리일시
- 20260202104713
- ISBN
- 9798288808197
- DDC
- 519
- 저자명
- Foussoul, Ayoub.
- 서명/저자
- Robust and Tractable Policies for Resource Allocation under Uncertainty
- 발행사항
- [Sl] : Columbia University, 2025
- 발행사항
- Ann Arbor : ProQuest Dissertations & Theses, 2025
- 형태사항
- 245 p
- 주기사항
- Source: Dissertations Abstracts International, Volume: 87-01, Section: A.
- 주기사항
- Advisor: Goyal, Vineet.
- 학위논문주기
- Thesis (Ph.D.)--Columbia University, 2025.
- 초록/해제
- 요약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 Scarf's seminal solution 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 de- part 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.
- 일반주제명
- Applied mathematics
- 기타저자
- Columbia University Operations Research
- 기본자료저록
- Dissertations Abstracts International. 87-01A.
- 전자적 위치 및 접속
- 로그인 후 원문을 볼 수 있습니다.
MARC
008260126s2025 us c eng d■001000017358515
■00520260202104713
■006m o d
■007cr#unu||||||||
■020 ▼a9798288808197
■035 ▼a(MiAaPQ)AAI32119242
■040 ▼aMiAaPQ▼cMiAaPQ
■0820 ▼a519
■1001 ▼aFoussoul, Ayoub.
■24510▼aRobust and Tractable Policies for Resource Allocation under Uncertainty
■260 ▼a[Sl]▼bColumbia University▼c2025
■260 1▼aAnn Arbor▼bProQuest Dissertations & Theses▼c2025
■300 ▼a245 p
■500 ▼aSource: Dissertations Abstracts International, Volume: 87-01, Section: A.
■500 ▼aAdvisor: Goyal, Vineet.
■5021 ▼aThesis (Ph.D.)--Columbia University, 2025.
■520 ▼aDecision-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 Scarf's seminal solution 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 de- part 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.
■590 ▼aSchool code: 0054.
■650 4▼aApplied mathematics
■653 ▼aFully-dynamic load balancing
■653 ▼aMulti-location newsvendor
■653 ▼aTwo-stage robust optimization
■653 ▼aTwo-stage stochastic stable matching
■653 ▼aResource planning
■690 ▼a0796
■690 ▼a0454
■690 ▼a0364
■71020▼aColumbia University▼bOperations Research.
■7730 ▼tDissertations Abstracts International▼g87-01A.
■790 ▼a0054
■791 ▼aPh.D.
■792 ▼a2025
■793 ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17358515▼nKERIS▼z이 자료의 원문은 한국교육학술정보원에서 제공합니다.
