Real-world optimization problems often consist of several NP-hard combinatorial optimization problems that interact with each other.
Such multi-component optimization problems are difficult to solve not only because of the contained hard optimization problems, but in particular,
because of the interdependencies between the different components.
Interdependence complicates a decision making by forcing each sub-problem to influence the quality and feasibility of solutions of the other sub-problems.
This influence might be even stronger when one sub-problem changes the data used by another one through a solution construction process.
Examples of multi-component problems are vehicle routing problems under loading constraints, the maximizing material utilization while respecting a production schedule,
and the relocation of containers in a port while minimizing idle times of ships.
The goal of this competition
is to provide a platform for researchers in
computational intelligence working on multi-component optimization problems.
The main focus of this competition is on the combination of TSP and Knapsack problems.
However, we plan to extend this competition format to more complex combinations of problems (that have typically been dealt with individually in the past decades) in the upcoming years.
The set of benchmarks used in this competition follows the idea of the "Travelling Thief Problem" (Mohammad Reza Bonyadi, Zbigniew Michalewicz, Luigi Barone:
The travelling thief problem: The first step in the transition from theoretical problems to realistic problems.
IEEE Congress on Evolutionary Computation 2013: 1037-1044).
Eucledian 2D Traveling Salesperson instances are combined with 0-1-Knapsack instances in such a way that it reflects aspects of problems from the real-world;
for example, the total weight of the items in the knapsack influences the travel speed of a traveller.
This introduced interdependence sets our benchmarks apart from capacitated vehicle routing problem instances, where this interdependence does not exist.
For technical details on how the benchmarks were created, please see the
manual (GECCO 2014 article).
A range of sample instances is available for researchers to experiment with before the final submission.
The samples will include instances with few/many cities, with uncorrelated/correlated profits and weights, and instances with further characteristics.
In order to encourage researchers during the weeks before the submission deadline, we invite them to submit solutions for the sample instances.
These results will be displayed online (without a reference to the authors) and then will serve as performance indications for other researchers.
These files will be run on our state of the art Linux servers. The evaluation criteria is the final solution quality after a fixed budget of computation time 10 minutes.
We do this in order to mimic the importance of "deadlines"; in addition, 10 minutes are a short amount of time that a decision maker might be willing to invest for different what-if analyses.
In 2015, the water network optimisation software company
Optimatics provides the total amount of
AUD 1,000 in cash.
Optimatics provides the water industry's most powerful water planning decision support tools and processes to enable optimal water services.
The company enables decision makers to optimize the planning, operations and management of their water and wastewater networks with Optimatics' proprietary software, consulting and distributed computing solutions.
While we do not require this, we strongly encourage the participants to register for CEC 2015 due to the advantages.
We encourage the entrants to write papers on their methods and to submit those to CEC 2015.
For example, depending on your used approach, the special sessions SS11 or SS20 might fit well.
Technical Details
Please note:
- Your algorithm needs to be executable from the command line and it should only take the instance file as a parameter, e.g.,
java thisIsMyAlgorithm instances/a280_n279_bounded-strongly-corr_02.ttp
- You can assume to have at least 16 GB of RAM at your disposal.
- We will stop you program after 10 minutes. This means that your algorithm needs to write the best result to a file
before the 10 minutes are over.
Note that you can of course try to write out the results frequently (overwriting the very same file), but since we will potentially execute your code in parallel (not mixed with other competitors!), it is in your own interest that you do not overload the file system with very frequent writes.
- Output: the file with the result for a single iteration should follow the following naming convention: <ttpfile>.<algorithmname>.<systemtime>, e.g.,
a280_n279_bounded-strongly-corr_02.ttp.thisIsMyAlgorithm.12345678912
- The file needs to contain the following information as comma-separated values in square brackets: the permutation of the cities in the first line (note: the first city is "1", do not print the "1" at the end), and the list of packed items in the second line (the numbering of the items starts with "1"). For example:
[1,5,4,2,3]
[20,113]
which means that only the items with the numbers 20 and 113 are picked, and the sequence of visited cities is <1,5,4,2,3,1>. Note that this format can easily be achieved in Java with the function Arrays.toString(...). The provided Java package provides all necessary helper function, but you might decide to implement your own internal representation for the optimisation.
Submission
Please submit your code
via email.
Your submission needs to include a README.txt that will help us to run your code.
For example, it needs to contain an example of how we can execute the code on the command line of our Linux machines.
We have Matlab, Java, and Mono installed in case you are using our Matlab/Java/C# code. If you intend to submit code in a different language, please check with us first.
We can help just little with debugging, so if you have tested your code thoroughly, chances are that we will enjoy the organisational part more.
Online Leaderboard
We are currently developing an online leaderboard that will allow all participants to continuously compare their performances.
Potentially, this system will replace your submission via email - we will inform you in time.
August 2014: instances and code online
19 April 2015, 11:59pm (Hawaii-ean time): submission deadline for algorithms
Please contact us if you want to receive notifications via email.
COMPETITION CANCELLED
We regret that we have to inform you: the competition was cancelled due to an insufficient number of submissions.