Titulo Estágio
Principled modelling of the Google Hash Code problems for meta-heuristics
Áreas de especialidade
Sistemas Inteligentes
Engenharia de Software
Local do Estágio
DEI-FCTUC
Enquadramento
Google Hash Code is a programming competition where teams are asked to solve a challenging engineering problem using their computers, programming languages and tools of their choice. A collection of 15 problem statements from past competitions is publicly available from the Hash Code website. Hash Code challenges are typically modelled after problems arising in real-world situations, such as scheduling drone deliveries or self-driving cars, city planning and Wi-Fi router placement, for example. They are posed as “open” problems that admit many feasible solutions, but are too large for provably optimal solutions to be determined in a reasonable amount of time. In fact, most if not all Hash Code problems are combinatorial optimisation problems. The competition scoring rules define how the quality of solutions is computed.
Meanwhile, there is growing interest in the scientific community in the development of a suite of combinatorial optimisation benchmark problems that are relevant in practice and approachable from a theoretical perspective. It can be argued that the Hash Code problems have some potential in this context. On the one hand, they must be sufficiently simple to describe and implement for teams to be able to solve them (to some extent) in a few hours. On the other hand, they are illustrative of the problems that arise in industry by design. Since all of those problems have already been solved by many teams (thousands of teams for the qualification rounds, and tens of the best teams in the case of the final rounds) from Europe, the Middle East and Africa, there is also plenty of empirical data on the best solutions that have been achieved, even if under severe time constraints.
Finally, there is also great interest in how to make meta-heuristic algorithms, including evolutionary algorithms, more easily available to practitioners. One important aspect is the perception that combinatorial optimisation problems can be structurally very different from one another, which makes it difficult to write general-purpose heuristic solver software. This work focuses on the modelling the Hash Code problems in software in a principled way so that they can be solved directly by meta-heuristic solvers in a black-box fashion.
Objetivo
The main objective of this work is the development, implementation and evaluation of heuristic and meta-heuristic solution approaches for the Hash Code problems. However, rather than developing a custom solver for each problem, a clear separation between the problems and the solvers will be established to the extent that exactly the same solver implementation can be effectively applied to several different problems, not only in a technical sense, but also concerning the quality of the results.
Another very important objective is a critical discussion of the merits and shortcomings of the envisaged approach to problem modelling and solver development for all parties potentially involved: meta-heuristic researchers, software developers, and practitioners. Performance dimensions to be considered will include problem modelling and solver development effort, computational performance of the implemented software, and the quality of the solutions achieved.
Plano de Trabalhos - Semestre 1
1. Familiarisation with the Hash Code competition challenges, and selection of a small number of different problems for further consideration.
2. Modelling of the selected Hash Code problems as constructive-search problems (ground set, construction rules, objective function, bounds).
3. Proof-of-concept implementation of software models of the chosen problems, as well as of a simple constructive-search algorithm.
4. Intermediate report writing.
Plano de Trabalhos - Semestre 2
1. Modelling and implementation of additional Hash Code problems, both as constructive search problems and as local search problems, to extend the benchmark suite.
2. Implementation of state-of-the-art meta-heuristic constructive-search and local-search algorithms.
3. Experimental study.
4. Evaluation and discussion of the methodology adopted and of the results achieved.
5. Dissertation writing.
Condições
Very good background in evolutionary computation, algorithms and data structures. The work will be carried out in the CISUC AC laboratories. A compute server is available to support the development and evaluation of the algorithms developed.
This project is NOT supported by Google or the Google Hash Code Team in any way, and will be carried out independently. Use of the Hash Code problems for practising and discussion is permitted by Google.
Observações
Co-orientador: Carlos M. Fonseca - cmfonsec@dei.uc.pt
Orientador
Alexandre Daniel Borges de Jesus
ajesus@dei.uc.pt 📩