Principled Modeling of the Google Hash Code Problems for Meta-Heuristics

Abstract

Combinatorial Optimization problems are ubiquitous in real-world scenarios.To solve these, there are a wide range of methods described in the literaturefrom which we highlight exact and meta-heuristic methods. Exact methods canfind optimal solutions. However, they are often infeasible in practice due to theNP-Hard nature of most combinatorial optimization problems. On the otherhand, meta-heuristics often cannot provably find optimal solutions, but canfind solutions that are of ”good” quality, which motivates the growing interestin their use for combinatorial problems.There has been growing interest in the development of a general-purpose frame-work for the development of black-box meta-heuristic methods that separatesproblem-specific from approach-specific details. In this work, we build uponthis idea and expand on previous work that has looked into the developmentof a framework for constructive and local search meta-heuristic approaches.In particular we give a general framework and corresponding Python imple-mentation that encompasses both search approaches, and implement severalcommon algorithms under this framework.In addition, there is a growing interest in the community in developing a suiteof benchmark problems for accessing the quality of meta-heuristics strategies.The Google hash code problems, being combinatorial problems in nature andmodelled after real-world scenarios pose themselves as interesting candidatesfor this purpose. In this work, we analyze all Google Hash Code problems, andimplement several models for two of the problems under our general frameworkto show that it allows for the development of models that give very competitiveresults in practice.

Os problemas de Otimização Combinatória são ubíquos em cenários da vida real. Para resolver estes problemas, existe uma grande variedade de métodos descritos na literatura, nos quais se destacam métodos exatos e métodos meta-heurísticos. Embora os métodos exatos consigam encontrar soluções ótimas, estes, na prática, são frequentemente inviáveis devido à natureza NP-Difícil da maioria dos problemas de otimização combinatória. Por outro lado, meta-heurísticas são tipicamente incapazes de encontrar soluções ótimas, no entanto, conseguem encontrar soluções de “boa” qualidade, o que motiva o crescente interesse na sua utilização em problemas combinatórios. Tem existido crescente interesse no desenvolvimento de uma plataforma para o desenvolvimento de métodos meta-heurísticos de caixa preta que separam detalhes específicos do problema de detalhes específicos da abordagem. Neste trabalho, construímos sobre essa ideia e expandimos trabalhos anteriores que investigaram o desenvolvimento de uma plataforma para abordagens meta-heurísticas de procura construtiva e local. Em particular, desenvolvemos uma plataforma em Python que reúne ambas as abordagens de procura e implementamos também vários algoritmos que seguem esta abordagem. Para além disso, há também um crescente interesse na comunidade em desenvolver um conjunto de problemas de referência para avaliar a qualidade das estratégias meta-heurísticas. Os problemas do Google Hash Code, por serem problemas combinatórios e baseados em cenários do mundo real, apresentam-se como candidatos interessantes para esta análise. Neste trabalho, analisamos todos os problemas do Google Hash Code e implementamos vários modelos para dois desses problemas, demonstrando que a nossa framework permite o desenvolvimento de modelos que proporcionam resultados muito competitivos na prática.