{"id":8867,"date":"2016-08-21T12:00:12","date_gmt":"2016-08-21T16:00:12","guid":{"rendered":"http:\/\/mat.tepper.cmu.edu\/blog\/?p=8867"},"modified":"2016-08-21T12:00:12","modified_gmt":"2016-08-21T16:00:12","slug":"touring-the-rio-olympics","status":"publish","type":"post","link":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/2016\/08\/21\/touring-the-rio-olympics\/","title":{"rendered":"Touring the Rio Olympics"},"content":{"rendered":"

I’m a sportswriter who is bound for the Olympics, and I’m writing an article about maximizing the number of events I see in a particular day.<\/p>\n

I thought the input of a mathematician with expertise in these matters would be helpful to the story.<\/p><\/blockquote>\n

This was an interesting start to day a month ago. \u00a0I received this email from\u00a0New York Times\u00a0<\/em>reporter Victor Mather<\/a> via University of Waterloo prof Bill Cook<\/a>. \u00a0Victor had contacted Bill since Bill is the world’s foremost expert on the Traveling Salesman Problem (he has a must-read book aimed at the general public called\u00a0In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation<\/a><\/em>). \u00a0The TSP involves visiting a number of sites while traveling the minimum distance. \u00a0While Victor’s task will have some aspects of the TSP, \u00a0there are scheduling aspects that I work on so Bill recommended me (thanks Bill!).<\/p>\n

Victor’s plan was to visit as many Olympic events in Rio as he could in a single day. \u00a0This was part of a competition with another reporter, Sarah Lyall<\/a>. \u00a0Victor decided to optimize his day; Sarah would simply go where her heart took her. \u00a0Who would see more events?<\/p>\n

Victor initially just wanted to talk about how optimization would work (or at least he made it seem so) but I knew from the first moment that I would be optimizing his day if he would let me. \u00a0He let me. \u00a0He agreed to get me data, and I would formulate and run a model that would find his best schedule.<\/p>\n

On the day they chose (Monday, August 15), there were 20 events being held. \u00a0\"rio-2016\"<\/a>The map shows that the venues are all spread out across Rio (a dense, somewhat chaotic, city not known for its transportation infrastructure). \u00a0So we would have to worry about travel distance. \u00a0Victor provided an initial distance matrix, with times in minutes (OLY times<\/a>). \u00a0As we will see, this matrix must have been created by someone who had a few too many caipirinhas on Copacabana Beach: \u00a0it did not exactly match reality.<\/p>\n

So far the problem does look like a TSP: just minimize the distance to see 20 sites. \u00a0The TSP on 20 sites is pretty trivial (see a previous blog post<\/a> for how hard solving TSPs are in practice) so simply seeing the sites would be quite straightforward. \u00a0However, not surprisingly Victor actually wanted to see the events happening. \u00a0For that, we needed a schedule of the events, which Victor promptly provided:<\/p>\n

Badminton 8:30 am \u2013 10:30 am \/\/ 5:30 pm -7
\nBasketball 2:15 pm \u2013 4:15 pm\/\/ 7 pm -9 pm \/\/ 10:30 pm – midnite
\nBeach Volleyball 4 p.m.-6 p.m. \/\/ 11pm \u2013 1 am
\nBoxing 11 am-1:30 pm, 5 pm \u2013 7:30 pm
\nCanoeing 9 am \u2013 10:30 am
\nCycling: 10 a.m. \u2013 11 am \/\/\/ 4 pm \u2013 5:30
\nDiving 3:15 pm -4:30
\nEquestrian 10 am- 11 am
\nField Hockey 10 am \u2013 11:30 am \/\/ 12:30 \u20132 \/\/ 6-7:30 pm \/\/ 8:30 pm -10
\nGymnastics 2 pm -3 pm
\nHandball: 9:30 am- 11 am\/\/ 11:30 \u2013 1pm \/\/2:40 -4 \/\/4:40 \u2013 6 pm \/\/ 7:50 \u2013 9:10 pm \/\/ 9:50 pm -11:10
\nOpen water Swimming 9 am \u2013 10 am
\nSailing 1 pm \u2013 2 pm
\nSynchronized swimming: 11 am- 12:30
\nTable tennis 10 am -11 am \/\/ 3pm -4:30 \/\/ 7:30pm – 9
\nTrack 9:30 am -11:30 am \/\/ 8:15pm -10 pm
\nVolleyball 9:30 am- 10:30 am \/\/ 11:30 \u2013 12:30 \/\/ 3pm \u2013 4 pm \/\/ 5 pm \u2013 6 pm \/\/ 8:30 pm -9:30 \/\/ 1030 pm -11:30
\nWater polo 2:10 pm \u2013 3 pm \/\/ 3:30 -4:20 \/\/6:20 -7:10 \/\/ 7:40 \u2013 8:30
\nWeightlifting 3:30 \u2013 4:30 pm \/\/ 7 pm- 8 pm
\nWrestling 10 am \u2013 noon \/\/ 4 pm- 6 pm<\/p><\/blockquote>\n

Many events have multiple sessions: \u00a0Victor only had to see one session at each event, and decided that staying for 15 minutes was enough to declare that he had “seen” the event. \u00a0It is these “time windows” that make the problem hard(er).<\/p>\n

With the data, I promptly sat down and modeled the problem as an mixed-integer program. \u00a0I had variables for the order in which the events were seen, the time of arrival at each event, and the session seen for each event (the first, second, third or so on). \u00a0There were constraints to force the result to be a path through the sites (we didn’t worry about where Victor started or ended: travel to and from his hotel was not a concern) and constraints to ensure that when he showed up at an event, there was sufficient time for him to see the event before moving on.<\/p>\n

The objective was primarily to see as many events as possible. \u00a0 With this data, it is possible to see all 20 events. \u00a0At this point, if you would like to see the value of optimization, you might give it a try: \u00a0can you see all 20 events just by looking at the data? \u00a0I can’t!<\/p>\n

But there may be many ways to see all the events. \u00a0So, secondarily, I had the optimization system minimize the distance traveled. \u00a0The hope was that spending less time on the buses between events would result in a more robust schedule.<\/p>\n

I put my model in the amazing modeling system AIMMS<\/a>. \u00a0AIMMS lets me input data, variables, constraints, and objectives incredibly quickly and intuitively, so I was able to get a working system together in a couple of hours (most of which was just mucking about with the data). \u00a0AIMMS then generates the integer program which is sent to Gurobi<\/a> software (very fast effective mixed-integer programming solution software) and an hour later I had a schedule.<\/p>\n\n\n<\/colgroup>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
start<\/td>\nArrival<\/td>\nNext travel time<\/td>\n<\/tr>\n
canoe<\/td>\n9:00<\/td>\n20<\/td>\n<\/tr>\n
open swimming<\/td>\n9:35<\/td>\n45<\/td>\n<\/tr>\n
equestrian<\/td>\n10:35<\/td>\n35<\/td>\n<\/tr>\n
wrestling<\/td>\n11:25<\/td>\n10<\/td>\n<\/tr>\n
synchro<\/td>\n12:15<\/td>\n30<\/td>\n<\/tr>\n
sailing<\/td>\n13:00<\/td>\n30<\/td>\n<\/tr>\n
gymnastics<\/td>\n14:00<\/td>\n10<\/td>\n<\/tr>\n
handball<\/td>\n14:40<\/td>\n10<\/td>\n<\/tr>\n
basketball<\/td>\n15:05<\/td>\n10<\/td>\n<\/tr>\n
diving<\/td>\n15:30<\/td>\n10<\/td>\n<\/tr>\n
cycling<\/td>\n17:00<\/td>\n30<\/td>\n<\/tr>\n
beach volleyball<\/td>\n17:45<\/td>\n30<\/td>\n<\/tr>\n
badminton<\/td>\n18:40<\/td>\n5<\/td>\n<\/tr>\n
boxing<\/td>\n19:00<\/td>\n5<\/td>\n<\/tr>\n
weightlifting<\/td>\n19:20<\/td>\n5<\/td>\n<\/tr>\n
table tennis<\/td>\n19:40<\/td>\n10<\/td>\n<\/tr>\n
water polo<\/td>\n20:05<\/td>\n35<\/td>\n<\/tr>\n
hockey<\/td>\n20:55<\/td>\n35<\/td>\n<\/tr>\n
track<\/td>\n21:45<\/td>\n20<\/td>\n<\/tr>\n
volley<\/td>\n22:30<\/td>\n<\/td>\n<\/tr>\n
end<\/td>\n22:45<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

This schedule has 385 minutes on the bus.<\/p>\n

I discussed this problem with my colleague Willem van Hoeve<\/a>, who spent about five minutes implementing a constraint programming model (also in AIMMS) to confirm this schedule. \u00a0He had a access to a newer version of the software, which could find and prove optimality within minutes. \u00a0Unfortunately my version of the software could not prove optimality overnight, so I kept with my MIP model through the rest of the process (while feeling I was driving a Model T, while a F1 racecar was sitting just up the hallway). \u00a0CP looks to be the right way to go about this problem.<\/p>\n

I spent some time playing around with these models to see whether I could get something that would provide Victor with more flexibility. \u00a0For instance, could he stay for 20 minutes at each venue? \u00a0No: the schedule is too tight for that. \u00a0So that was the planned schedule.<\/p>\n

But then Victor got to Rio and realized that the planned transportation times were ludicrously off. \u00a0There was no way he could make some of those trips in the time planned. \u00a0So he provided another transportation time matrix (olympics3<\/a>) with longer times. \u00a0Unfortunately, with the new times, he could not plan for all 20: the best solution only allows for seeing 19 events.<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
Event<\/td>\n<\/td>\nArrival<\/td>\nNext Travel<\/td>\nSlack<\/td>\n<\/tr>\n
canoe<\/td>\n<\/td>\n9:00<\/td>\n30<\/td>\n<\/td>\n<\/tr>\n
track<\/td>\n<\/td>\n9:45<\/td>\n45<\/td>\n<\/td>\n<\/tr>\n
equestrian<\/td>\n<\/td>\n10:45<\/td>\n35<\/td>\n<\/td>\n<\/tr>\n
synchro<\/td>\n<\/td>\n11:35<\/td>\n60<\/td>\n0:10<\/td>\n<\/tr>\n
sailing<\/td>\n<\/td>\n13:00<\/td>\n60<\/td>\n<\/td>\n<\/tr>\n
gymnastics<\/td>\n14:15<\/td>\n15<\/td>\n<\/td>\n<\/tr>\n
water polo<\/td>\n14:45<\/td>\n15<\/td>\n<\/td>\n<\/tr>\n
diving<\/td>\n<\/td>\n15:15<\/td>\n15<\/td>\n0:25<\/td>\n<\/tr>\n
cycling<\/td>\n<\/td>\n16:10<\/td>\n15<\/td>\n<\/td>\n<\/tr>\n
handball<\/td>\n<\/td>\n16:40<\/td>\n15<\/td>\n<\/td>\n<\/tr>\n
wrestling<\/td>\n<\/td>\n17:10<\/td>\n25<\/td>\n<\/td>\n<\/tr>\n
boxing<\/td>\n<\/td>\n17:50<\/td>\n15<\/td>\n<\/td>\n<\/tr>\n
badminton<\/td>\n18:20<\/td>\n15<\/td>\n0:10<\/td>\n<\/tr>\n
weightlifting<\/td>\n19:00<\/td>\n15<\/td>\n0:35<\/td>\n<\/tr>\n
table tennis<\/td>\n20:05<\/td>\n25<\/td>\n<\/td>\n<\/tr>\n
basketball<\/td>\n<\/td>\n20:45<\/td>\n35<\/td>\n0:10<\/td>\n<\/tr>\n
hockey<\/td>\n<\/td>\n21:45<\/td>\n45<\/td>\n0:30<\/td>\n<\/tr>\n
volley<\/td>\n<\/td>\n23:15<\/td>\n30<\/td>\n<\/td>\n<\/tr>\n
beach volleyball<\/td>\n0:00<\/td>\n<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

So that is the schedule Vincent started with. \u00a0I certainly had some worries. \u00a0Foremost was the travel uncertainty. \u00a0Trying to minimize time on the bus is a good start, but we did not handle uncertainty as deeply as we could have. \u00a0But more handling of uncertainty would have led to a more complicated set of rules and it seemed that a single schedule would be more in keeping with the challenge. \u00a0The morning in particularly looked risky, so I suggested that Victor be certain to get to gymnastics no later than 2:15 in order to take advantage of the long stretch of close events that follow. \u00a0Sailing in particular, looked to be pretty risky to try to get to.<\/p>\n

I had other worries: \u00a0for instance, what if Victor arrived during half-time of an event, or between two games in a single session? \u00a0Victor probably wouldn’t count that as seeing the event, but I did not have the detailed data (nor an idea of the accuracy of such data if it did exist), so we had to hope for the best. \u00a0I did suggest to Victor that he try to keep to the ordering, leaving an event as soon as 15 minutes are up, hoping to get a bit more slack when travel times worked out better than planned (as-if!).<\/p>\n

So what happened? \u00a0Victor’s full story is here<\/a>\u00a0and it makes great reading (my school’s PR guy says Victor is “both a reporter and a writer”, which is high praise). \u00a0Suffice it to say, things didn’t go according to plan. The article starts out:<\/p>\n

\n

There are 20 [events] on the schedule on Monday. \u00a0Might an intrepid reporter get to all of them in one day? \u00a0I decide to find out, although it doesn’t take long to discover just how difficult that will be.<\/p>\n

The realization comes while I am stranded at a bus stop in Copacabana, two and a half hours into my journey. \u00a0The next bus isn’t scheduled for three hours. \u00a0And I’ve managed to get to exactly one event, which I could barely see.<\/p>\n<\/blockquote>\n

I had given him some rather useless advice in this situation:<\/p>\n

\n

“Something goes wrong, you reoptimize,” Professor Trick had cheerfully said. \u00a0This is hard to do sitting on a bus with the computing power of a pen and a pad at my disposal.<\/p>\n<\/blockquote>\n

Fortunately, he got back in time for the magical sequence of events in the afternoon and early evening. \u00a0One of my worries did happen, but Victor agilely handled the situation:<\/p>\n

\n

Professor Trick urged me in his instructions to “keep the order!” \u00a0So it is with some trepidation that I go off-program. \u00a0Wrestling is closer to where I am than handball, and it looks like I will land at the handball arena between games. \u00a0So I switch them. \u00a0It’s the ultimate battle of man and machine — and it pays off. \u00a0I hope the professor approves of my use of this seat-of-the-pants exchange heuristic.<\/p>\n<\/blockquote>\n

I do approve, and I very much like the accurate use of the phrase “exchange heuristic”.<\/p>\n

At the end Victor sees 14 events. \u00a019 was probably impossible, but a few more might have been seen with better data. \u00a0I wish I had used the optimization code to give Victor some more “what-ifs”, and perhaps some better visualizations so his “pen and pad optimization” might have worked out better. \u00a0But I am amazed he was able to see this many in one day!<\/p>\n

And what happened to Sarah, the reporter who would just go as she pleased? \u00a0Check out her report<\/a>, where she saw five events. \u00a0If Victor went a little extreme getting a university professor to plan his day, Sarah went a little extreme the other way in not even looking at a map or a schedule.<\/p>\n

This was a lot of fun, and I am extremely grateful to Victor for letting me do this with him (and to Bill for recommending me, and to Willem for providing the CP model that gave me confidence in what I was doing).<\/p>\n

I’ll be ready for Tokyo 2020!<\/p>\n

\n","protected":false},"excerpt":{"rendered":"

I’m a sportswriter who is bound for the Olympics, and I’m writing an article about maximizing the number of events I see in a particular day. I thought the input of a mathematician with expertise in these matters would be helpful to the story. This was an interesting start to day a month ago. \u00a0I … Continue reading “Touring the Rio Olympics”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[39,41,51],"tags":[],"class_list":["post-8867","post","type-post","status-publish","format-standard","hentry","category-or-in-the-press","category-personal","category-sports"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/8867","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=8867"}],"version-history":[{"count":0,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/8867\/revisions"}],"wp:attachment":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=8867"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=8867"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=8867"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}