Swimmers' Dilemma

One of my colleagues was on a master’s men’s swim team that set a world record in the 400-meter medley. He pointed out how the rules generate the complexities of creating the best team. The team members’ ages must sum to at least 200 years. Assuming each person’s time slows at an accelerating rate, you might think that minimizing the relay team’s time would require having each member be age 50. Yet my colleague is 53, but he is an exceptionally fine swimmer, especially at freestyle, which he swam in the meet. Having him on the team doesn’t slow the total time very much (he’s never the best among masters in any event); but including him allows the team also to include a 47-year-old who has several individual world records.

The programming problem becomes even more complex because each swimmer’s time slows at a different rate in different events. Since teams need time to practice, constructing the optimal team requires taking into account the sum of ages constraint, the current time of each potential team member in each relay leg, and the rate at which times are slowing for each person in each event. (HT: MS)


Tank

"you might think that minimizing the relay team's time would require having each member be age 50."

No one might think that. Other than Professor Hamermesh, of course.

Mark Harrison

This kind of problem is known (in academic IT circles at least) as "NP-Complete", in that adding one extra swimmer to the talent pool makes the calculation more complex at an exponential rate .

Without going into the gory details of what NP-Complete means, it's the kind of thing that modern desktop computers can do very quickly, assuming you have someone able to spend a couple of hours coding, rather than solve "by hand" in a spreadsheet.

Let's make life more complex

- do some swimmers in the target group swim better at certain times of the day (and this is important) relative to each other? If so, you have to optimise based on when the event will be swum.

- do some swimmers perform more consistently than others?

- are there some combinations of swimmers where there is such personal antipathy that one or more might be tempted to perform sub-optimally to deny the other a share in any glory?

- is the nature of swimming at this level such that training together makes a difference? (I suspect less so than for most team sports, but I don't have any data.) If so, what is the response curve for such training, since you'd then need to optimise for not just the selected people but date of announcement of the team.

I suspect that the hard part is actually gathering the data you need to determine the inputs.

Read more...

IcemanCMS

This is a nice example of trying to maximize a certain output under a constraint, just like firms try to maximize their productivity and their profits with a limited amount of resources at hand. In this situation, one tries to minimize the time required to complete the relay race by selecting individuals to perform different parts of the race, while being constrained by the age requirement. With careful analisys one should be able to find the optimal combination, but in larger-scale situations like the operation of a firm there are so many variables that it becomes hard to control. Another example from the sports realm could be managing a football team, which involves finding the ideal position for each player as well as teams of players that work well with each other.

jimi

Now do it again with the C.A.F.E. standards.

Drill-Baby-Drill drill Team

Simply get a 150 year old Turtle named Crush on the roster.

Ian Kemmish

Or, you could just stage a set of qualifying races....

Aaron K.

An objective function and a constraint are not sufficient conditions for a problem to be economics.

Just in case you were trying to take over operations research, or some other related field.

Andrew Wheeler

You don't at any point mention if this team has a maximum or required number of members -- if not, the problem is trivial.

Steneub

Are there an upper- and lower- bounds for how many team members you can or must have?

One 200-year-old or 200 one-year-olds would probably not have a good standing, but can't you field say... ten 20-year-olds or six 33-year-olds?

Somewhere in the middle is your optimum. It might very well hover around 50, but that's not where my first assumption lay.

cirby

You recruit one 200 year old swimmer.

Since he's been doing it for almost two centuries, he must be REALLY good at it by now.

Steve

A medley relay has 4 people.

Miles

Re: 9 -- Steneub: A 400m medley relay is comprised of exactly 4 swimmers, each completing 100m of a single stroke. The backstroker starts and is followed by the breastroker, butterflyer and finally, the freestyler (which has the most lax rules -- any stroke is legal, but the crawl is generally fastest).

Greg

@Mark #2: "it's the kind of thing that modern desktop computers can do very quickly" is almost exactly the *opposite* of what NP-complete means. For an NP-complete problem (or technically speaking an NP-hard problem), even working with a computer very quickly becomes impractical, due to the rapidly increasing time required to solve larger and larger instances.

Nate

@ Drill-Baby-Drill drill Team...

Thanks man, I needed a good laugh!

John

Apologies for piling on comment #2, but the truth is way more interesting than that incorrect post.

The problem is part of a class of problem that is computer scientists call NP-Hard (and if you squint at an NP-Hard problem just right it can also be considered NP-Complete). It's not NP-Complete because it's "exponential". It's NP-Complete because we can show another NP-Complete problem can solve it, and therefore it's at least as hard as that problem. I'm thinking of 0-1 Knapsack for those who know what I'm talking about. http://en.wikipedia.org/wiki/Knapsack_problem

That sounds like a lot of meaningless taxonomy, but knowing what problem class is immediately tells us how not to spend our efforts solving it. A computer will never be able to perfectly solve the problem once it grows beyond very small sizes. A human won't either. The best you can do is make approximations, or change your problem specification. We run into this tough class of problems in all walks of software engineering and computer science: from picking the best trucking lanes to route cargo, to figuring out how to pack those trucks optimally, to even figuring out what the best supplier/buyer relationship is for sourcing the truck parts. NP-Complete problems pop up everywhere, and it takes a vast amount of human brainpower in all corners of industry to come up with acceptable approximation algorithms and other solutions to make inroads on this real-world tough tough problems.

It's really remarkable and humbling that there are so many common 'simple' problems that we can prove we'll never be able to perfectly solve with computers.

Read more...

Mike

Sounds like a job for the Hungarian Algorithm, which of course runs in O(n^3). The advantage is, the algorithm can determine which combination of ages and times per each discipline can produce the best team. It can take into account skill at different strokes.

The trick is, of course, determining a rate of time decline to hypothesize the time for each swimmer in the future.

http://en.wikipedia.org/wiki/Hungarian_algorithm

JoseACMS

In a case like this, there are dozens of elements to take into perspective when choosing the swimmers that will maximize the productivity and outcome of the swimming team as a whole. Essentially, gathering this type of information could take months if not years. Maybe some swimmers swim better than others at different times in the day. Maybe some swimmers are more consistent than others. Some swimmers may even have personal conflicts with each other that cause them to work inefficiently together. Needless to say, you could have a swimmer that is really good at short distances. Such a person could offer you a marginal benefit when swimming 50m. However, the marginal cost of this swimmer could be performing poorly in the 200m medley. What I mean here, is that you have to see which swimmers have a comparative advantage in what type of swimming, and in the end, set the swimmers to swim the style where they have the lowest opportunity cost.

Read more...

M Carroll Benton

What do you attribute the increase in murders in New York City in 2010? It is said it went up by 13%.

Sincerely,

M. Carroll Benton

superpippo

The problem is not that difficult. Given the set of possible candidates to make the team, their speed and their age, you can just solve it as a Linear Integer Program with binary variables. Given that the list of candidates is probably not very large (say 30-40 people at the most?) and that a team is comprised only of 4 members, I suspect that commercial IP solvers will give you the optimal solution within seconds. This could be an exercise in a first undergraduate Operations Research course.

To Mark: the problem as stated is not NP-complete. You only have to select 4 swimmers, so if you have n candidates you could just check all n choose 4 possibilities, which is of order n to the 4th, so polynomial on input size.

Aaron

The author is forgetting the basic rules of correlation versus causation.

The algorithm the author has suggested would require that the age of the swimmer be inextricably tied to the rate of the swimmer's decline in stamina. In the real world these two things are correlated but do not actually cause each other, so there is no possible way to solve the problem posed using that data.

It is entirely possible that the 53 year old swimmer is in much better aerobic shape than me, a 33 year old. But the math the author would expect would not be able to account for that.