The Baseball Scheduling Problem

Came upon this ESPN video at random the other day.

http://www.grantland.com/story/_/id/9930115/our-latest-30-30-documentary-short-tells-story-how-husband-wife-ended-creating-schedule-mlb

For years I had assumed that baseball (and all professional sports) had used computers to determine their season schedules, but apparently the scheduling problem was so difficult and so complex, human beings did Major League Baseball's schedule by hand until 2004.  The couple highlighted in the video did it for about 20 years.  Apparently multiple companies and research universities (MIT, Stanford, Carnegie Mellon, IBM are mentioned) failed to come up w/ schedules in the 80s and 90s.  In some cases, it was not failed to come up with "good schedules", but apparently failed to come up with a schedule at all.

The scheduling problem seems mighty complex.  The scheduling conditions below are from the video and my own knowledge of baseball.

• 30 baseball teams, each plays 162 games (2430 games total)
• The schedule is unbalanced, teams in the NL or AL play within their league more often than the other (15 teams per league).
• Teams within divisions play each other more often than other divisions in the league (5 teams per division).
• Teams cannot play any other team in the other leagues (interleague play) but only specific ones in certain divisions.
• Cities w/ two teams (Chicago, NY, etc.) must not be in the city at the same time on specific days (especially weekends and such)
• Special games are scheduled in for specific rivalries.  e.g. New York Yankees and New York Mets will play each other each year no matter what.
• For ratings/ticket sales, specific rivalries (intra division or otherwise) must be scheduled at specific times. e.g. intra-division battles almost always must be scheduled at the end of the year in September.  e.g. Boston vs NY or St. Louis vs Chicago games should almost always be on weekends.
• A specific number of rest days are mandated for each team.  They must be distributed evenly throughout the year (i.e. not back to back).
• Rest days must be scheduled in when long travel occurs (e.g. west coast teams going to east coast).
• Traveling must not be unbearable (e.g. you can't schedule team to play in NY, then LA, then Miami back to back to back).
• Each team has special requests to be home/away on certain dates b/c of special occasions or city specific events.  For example the SF Giants may not want to be in town during Fleet Week.
• Scheduling must be fair and equitable for holidays.  For example, it would be unfair to never allow a team to have a home game during the July 4th weekend.  In addition, you must handle Canadian holidays.
• Some teams may share their stadium with other professional sports teams, so that must be handled.  Although this constraint certainly existed in the past, it may not exist anymore (off the top of my head, St. Louis, San Diego, San Francisco, and Houston used to share their stadiums but no longer do).  Although I'm sure special case handling probably still exists (e.g. state championships, conventions, etc.).

I'm sure there are even more constraints that they don't mention and I can't think of.