# 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.

## Problem description

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?

## The rules

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.

## Hints

• 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

## Scoreboard

Here you can see the best solutions submitted so far:

#Max valueNameDate
150000000005 Isaac Thu, 30 Jul 2009 20:04:31
250000000008 Isaac Tue, 28 Jul 2009 11:10:41
350000000026 Dimitri et Nicolas Sat, 13 Jun 2009 21:28:23
450000000098 Dimitri et Nicolas Sun, 17 May 2009 17:56:48
550014315032 --------Wed, 13 May 2009 07:23:21
650207601682 --------Mon, 11 May 2009 15:18:14
753749641180 Martin (Greedy solution) Mon, 11 May 2009 13:51:48

## Submission

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.

### Submit here

 Name(s): Check this box if your name should be hidden on the scoreboard: Solution file: Description file: Additional archive file: