Argonne National Laboratory

Kibaek Kim wins Nemhauser Best Student Paper Prize

November 11, 2014

Kibaek Kim, a new postdoctoral researcher working in Argonne’s Mathematics and Computer Science Division, was awarded the Nemhauser Prize for the Best Student Paper. The prize, established in 2008, is annually given to the best student paper by the Industrial Engineering and Management Sciences (IEMS) Department at Northwestern University, where Kim recently obtained his Ph.D. this summer. The award includes $1,000 cash prize and an invitation to give a presentation at the quarterly IEMS seminar hosted by Northwestern University, held this year in October.

In the award-winning paper, Kim and his colleague presented an integrated staffing and scheduling model for nurse management. The model was formulated as a two-stage stochastic integer program. In a major theoretical contribution the paper shows that the second stage mixed-integer programming formulation of schedules can be convexified by adding a set of parametric mixed integer rounding (MIR) inequalities.  They showed that the parametric MIR inequalities are valid for the entire problem regardless of the value of first stage decision variable.  This central result dramatically decreases the difficulty of the problem as the integrality requirement of the second stage variables can be dropped after adding the parametric MIR inequalities.  Further algorithmic enhancements are made in the L-shaped method, branching strategies, and parallelization. The solution, tested by using 3.5 years of patient volume data from Northwestern Memorial Hospital, show that the stochastic programming-based solutions could save the cost of hiring at least three full-time nurses, compared with typical approaches used to generate schedules. The solved problems have 1,347,913 general integer variables and over four billion continuous variables.

For the full paper, see Kibaek Kim and Sanjay Mehrotra, “A Two-Stage Stochastic Integer Programming Approach to Integrated Staffing and Scheduling with Application to Nurse Management.”