Ocean's 10 - Discrete Optimization contest
Welcome to the website of the Ocean's 10 optimization contest of the Discrete Optimization Group.
All students attending to the lectures Optimization 2009 and
Introduction to Discrete Optimization 2009 are allowed to participate.
The student (or group of students) submitting the best solution wins a cash price of 300 CHF.
If several students (or groups) submit equally good solutions, the earlier submission wins.
Should you have any questions, don't hesitate to ask.
A group of 10 gangsters breaks into the vault of the Bellagio hotel in Las Vegas and manages to steal 100 suitcases with valuable content.
They are extremely lucky because the total value of the goods is 500 billon $ (500,000,000,000 $). The guys are afraid to get caught and decide never to see each other again.
Therefore they want to split up the goods evenly among each other.
They know the value of each suitcase. The suitcases have very strong locks that the guys can't break right now, thus they can not split the contents of a single suitcase.
They decide to distribute the suitcases as evenly as possible.
On average, each guy gets goods worth 50 billon $. The guys can't bear if someone gets much more than the average. Thus they want to distribute
the suitcases in such a way that the maximum value assigned to one guy is minimized.
The guys are smart and know that the problem of finding the optimal distribution is NP-hard,
and thus they are already satisfied with a "good" solution.
The values of the 100 suitcases can be found here.
Can you help them?
Your objective is to find an assignment of the 100 suitcases to the 10 guys such that the maximum value of goods that are assigned to one guy is minimized.
You are not expected to find the optimal solution, the person submitting the best solution wins. If there are several equally good solutions, the
earlierst submission wins. You are expected to explain how you found your solution. Your solution must be reproducible. In particular, if you use randomized algorithms, you have to give the seed for your random number generators. You are allowed to submit several solutions, the best submission counts. Details on the submission can be found here.
You are encouraged to write programs to help finding solutions.
You are allowed to use other software and libraries (e.g. lp_solve), provided that
the software is available on the web for free. You need to state every software you have used when submitting your solution.
You are not allowed to use any commercial software (e.g. cplex)
The deadline for the contest is Friday, 31 July 2009.
- Note that some of the suitcase values are too big to be stored in a 32bit integer variable. In C/C++ you can use 64bit integer types such as long long.
- A very simple approach to solve the problem would be to assign the suitcases successively to the guy who has the least value so far. But you can do better!
- More hints might appear later
Here you can see the best solutions submitted so far:
||Thu, 30 Jul 2009 20:04:31|
||Tue, 28 Jul 2009 11:10:41|
||Dimitri et Nicolas
||Sat, 13 Jun 2009 21:28:23|
||Dimitri et Nicolas
||Sun, 17 May 2009 17:56:48|
||--------||Wed, 13 May 2009 07:23:21|
||--------||Mon, 11 May 2009 15:18:14|
||Martin (Greedy solution)
||Mon, 11 May 2009 13:51:48|
You can submit your solution online here.
Your submission has to include the following:
- Your solution, i.e. for each guy a list of suitcases assigned to it. The solution has to be submitted as a textfile. The file has to contain 10 lines,
each line containing the indexes of the suitcases assigned to him. The first suitcase has an index of 0, the last suitcase has an index of 99. An example for a solution file can be found here.
- A description how you found the solution (What techniques did you apply, which software did you use, what kind of programs have you written yourself? Seed of random number generator?).
The description has to be given as a file in some standard format (TXT, PDF, ODT, DOC).
- If you have written any programs to help finding your solution, please submit the source code (Archive in ZIP,TAR or GZIP format) as an additional archive file.