Decomposing the Train Scheduling Problem into Integer Optimal Polytopes
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).
Entry Submitted: 05/28/2019
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|