Optimization Online


Reformulating Linear Programs with Transportation Constraints -- with Applications to Workforce Scheduling

Oktay Gunluk (oktay***at***watson.ibm.com)
Tolga Cezik (cezik***at***ieor.columbia.edu)

Abstract: We study linear programming models that contain transportation constraints in their formulation. Typically, these models have a multi-stage nature and the transportation constraints together with the associated flow variables are used to achieve consistency between consecutive stages. We describe how to reformulate these models by projecting out the flow variables. The reformulation can be more desirable since it has fewer variables and can be solved faster. We apply these ideas to reformulate two well-known workforce staffing and scheduling problems: the shift scheduling problem and the tour scheduling problem. We also present computational results.

Keywords: Reformulation, Transportation Problem, Workforce Scheduling

Category 1: Combinatorial Optimization

Category 2: Network Optimization

Citation: IBM Research Tech. Report. Jan, 2002

Download: [Postscript]

Entry Submitted: 01/17/2002
Entry Accepted: 01/17/2002
Entry Last Modified: 05/27/2003

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 Programming Society