Realignment in the National Football Leagues: did they do it right?

The National Football Leagues (NFL) in the United States expanded to 32 teams in 2002 with the addition of a team in Houston. At that point, the league was realigned into eight divisions, each containing four teams. We describe a branch-and-cut algorithm for minimizing the sum of intradivisional travel distances. We consider first the case where any team can be assigned to any division. We also consider imposing restrictions, such as aligning the AFC (American Football Conference) and the NFC (National Football Conference) separately or maintaining traditional rivalries. We show that the alignment chosen by the NFL does not minimize the sum of intradivisional travel distances, but that it is close to optimal for an alignment that aligns the NFC and AFC separately and imposes some additional restrictions.