Optimal VDS Team - Hardcore (Here be Math)

VDS for Math Nuts

This is going to be a funky post about maximizing VDS teams. It is going to delve into esoteric programming techniques and show how the VDS system is an example of a generally hard problem. Here there be equations. No apologies. You can skip to the end to see the results. Amazingly Open Office and Excel have just the tools we need to solve these. We do live in days of miracle and wonder!

I drive up to Stevens Point Wisconsin in December to run in the Frostbite race there with a bunch of teachers (retired as they now always point out). Every year is a different kind of year with that type. One year was the "math is everywhere" year. This is one example.

What is the problem? Well we want to answer questions like
What is the best possible VDS team right now?
How about that with Contador?
What about if I had had Andy Schleck, what is the best I could be doing?

and questions like that. It looks simple but it isn't. To get the feel, at every rider point change there is a new sub-problem if you will, say we go from Alberto Contador to Phillip Gilbert. That is a 4 point cost difference. So we have to figure out if PG + the best 122 point 24 rider team beats AC + best 118 point 24 rider team.

Ok here we are diving in to the math hard ...
This is called a Linear Programming problem. An Integer Linear programming problem in fact. Even more it is a Boolean Integer Programming problem. Here is what it looks like.

There are  961 possible riders or variables if you will.

For each rider we have a cost in points. Lets list from highest cost to lowest cost riders. There are 10 costing between 24-32 points, 11 between 18-22 points. So we will have three things for each rider on the list: a Cost, call it C_n for the n'th rider on the list. A Point Total, call it P_n for the n'th rider on the list, and a variable that is either 1 if the rider is on the team or 0 if he is not on the team. Call this x_n for the nth rider on the list. Hey! We are finally able to actually state our problem now:

We want to maximize the points. That is, the sum of the P_n * x_n over all n from 1 to 961.
semi-symbolically the Max of

961
SUM x_n * P_n
n=1

subject to the following constraints:

The sum of all the x_n's has to be less than equal to 25:
961
SUM x_n = 25
n=1

The sum of the costs of the selected riders (C_n * x_n) has to be less than or equal 150
961
SUM x_n * C_n <= 150
n=1

If we sort from highest cost to lowest then the sum of the first 10 most costly riders has to be 1. That is we can only have 1 selection from the top 10 riders (24 and above cost)
10
SUM x_n <= 1
n=1

We can only have three riders from the most costly 21 (those with cost 18 and up).
21
SUM x_n <= 3
n=1

There you go, a wonderful Integer programming problem in 961 variables. Actually it is a very interesting problem. Looked at naively it seem impossible because of the number of combinations. But really this is where a technique called dynamic programming comes into play. This is a divide and conquer thing. Look at it this way. The best 4 point cost team is either the best 3 point and best 1 point of those left, or the two best 2 point teams (or the best 1 point team and then the best 3 point team left. The 1-3 cases are the same but the margin is too small ...) At every point cost level this is true so you only really need to evaluate a logarithmic function of the total number of possible team combinations. And there are nice pruning methods to use too. So overall you only need a few 10's of millions of comparisons. That is a snap with a modern computer.

Both Excel and Open Office calc have decent "Solver" modules.

So as of right as I post after stage 1 Romandie, the best possible team is

Philippe Gilbert
Tom Boonen
Joaquin Rodriguez Oliver
Oscar Freire Gomez
Luca Paolini
Juan Antonio Flecha
Ryder Hesjedal
Maxim Iglinskiy
Björn Leukemans
Chris Horner
Roger Hammond
Bernhard Eisel
George Hincapie
Paul Martens
David Millar
Bert De Waele
Igor Anton Hernandez
Enrico Gasparotto
Theo Bos
Jens Keukeleire
Sacha Modolo
Bobbie Traksel
Sep Vanmarcke
Peter Sagan
Francesco Ginanni

With 12262 points

Best team with Alberto Contador is

Alberto Contador Velasco
Tom Boonen
Joaquin Rodriguez Oliver
Oscar Freire Gomez
Luca Paolini
Juan Antonio Flecha
Ryder Hesjedal
Maxim Iglinskiy
Björn Leukemans
Chris Horner
Roger Hammond
Bernhard Eisel
George Hincapie
Paul Martens
David Millar
Igor Anton Hernandez
Enrico Gasparotto
Jens Keukeleire
Sacha Modolo
Bobbie Traksel
Sep Vanmarcke
Peter Sagan
Francesco Ginanni
Beñat Intxausti Elorriaga
Kris Boeckmans

with 11755 points and I could go on with others. These are NOT necessarily unique. There could be others with the same point total. I have the spreadsheet (Open Office version) which I will make available somewhere with explanation. If you any any particular questions I could see if I can get an answer and give it. It looks like there are other people here who can also run these.