Optimization Online


A Solution Approach to Distributionally Robust Chance-Constrained Assignment

Shanshan Wang (shshwang_bit***at***163.com)
Jinlin Li (jinlinli***at***bit.edu.cn)
Sanjay Mehrotra (mehrotra***at***iems.northwestern.edu)

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.

Download: [PDF]

Entry Submitted: 05/13/2019
Entry Accepted: 05/14/2019
Entry Last Modified: 08/12/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society