{"id":"arxiv/2610.24867","url":"https://arxiv.org/abs/2610.24867","tags":["math.OC"],"score":0,"title":"A Partial Duty Formulation for Crew Scheduling","domain":"math.OC","source":"arxiv","authors":["Twan Dollevoet","Bart van Rossum","Remy Spliet"],"reviews":0,"subject":"math.OC","summary":"We consider a crew scheduling problem with a break, working time, and duty length constraint. It is common to solve crew scheduling problems with a diving heuristic, using column generation to solve the LP relaxation of a set partitioning formulation where variables correspond with duties. We prove that computing the LP bound of this formulation is weakly NP-hard, and propose an alternative formulation based on partial duties, whose LP bound can be computed in polynomial time. We prove the same complexity results for the corresponding pricing problems. However, the partial duty formulation…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-17","reactions":{}}