Optimization Online


Decomposing the Train Scheduling Problem into Integer Optimal Polytopes

Masoud Barah(mbarah***at***vols.utk.edu)
Abbas Seifi(aseifi***at***aut.ac.ir)
Jim Ostrowski(jostrows***at***utk.edu)

Abstract: This paper presents conditions for which the linear relaxation for the train scheduling problem is integer-optimal. These conditions are then used to identify how to partition a general problem's feasible region into integer-optimal polytopes. Such an approach yields an extended formulation that contains far fewer binary variables. Our computational experiments show that this approach results in significant computational savings. Moreover, this approach scales well when the train scheduling problem is modeled using smaller time increments, allowing for higher fidelity models to be solved without significantly increasing the required computational time.

Keywords: Non-periodic Train Scheduling Problem, Space-Time Network, Integer-Optimal Polytopes

Category 1: Applications -- OR and Management Sciences (Transportation )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Combinatorial Optimization (Polyhedra )

Citation: Barah, Masoud, Abbas Seifi, and James Ostrowski. "Decomposing the Train-Scheduling Problem into Integer-Optimal Polytopes." Transportation Science (2019).

Download: [PDF]

Entry Submitted: 05/28/2019
Entry Accepted: 05/28/2019
Entry Last Modified: 05/28/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