A Solution Approach to Distributionally Robust Chance-Constrained Assignment
Shanshan Wang (shshwang_bit163.com)
Abstract: We study an assignment problem with chance constraints (CAP) and its distributionally robust counterpart (DR-CAP). For a big-M formulation of DR-CAP, we present a technique that takes advantage of DR chance constraints in the big-M estimations. Next, for a bilinear formulation of CAP, we develop a class of valid inequalities for a 0-1 bilinear knapsack set, as well as multiple bilinear knapsack sets with a binary linear knapsack constraint. These are subsequently extended to DR-CAP. The branch-and-cut approaches combined with the valid inequalities are proposed to solve CAP and DR-CAP, respectively. A computational study for CAP and DR-CAP using data from a hospital operating room is conducted. We find that the incorporation of the big-M calculations and the proposed cuts allow us to solve certain model instances, and reduce computational time for others. The instances requiring a high probability of chance satisfaction remain challenging. We also find that the use of the Wasserstein ambiguity set improves the out-of-sample performance of satisfying the chance constraints. This improvement is more significant that the one possible by increasing the sample size. The DR-CAP model instances can be solved in approximately four times the time required to solve CAP instances.
Keywords: Chance-constrained assignment problem; distributionally robust optimization; bilinear program; branch-and-cut; valid inequalities; operating room planning
Category 1: Applications -- OR and Management Sciences
Category 2: Applications -- OR and Management Sciences (Scheduling )
Category 3: Combinatorial Optimization (Branch and Cut Algorithms )
Citation: Wang, S., Li, J., Mehrotra, S., 2019, A Solution Approach to Distributionally Robust Chance-Constrained Assignment, available at optimization-online.
Entry Submitted: 05/13/2019
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|