Enhancing performance on combinatorial optimization algorithms

Abstract

L’optimització combinatòria és un tipus específic d’optimització matemàtica on el domini de les variables és discret. Aquest tipus de problemes d’optimització tenen una gran aplicabilitat degut a la seva capacitat d’optimització sobre objectes unitaris i no divisibles. Més enllà dels algoritmes genèrics, la comunitat investigadora és molt activa proposant algorismes capaços d’abordar problemes d’optimització combinatòria per a problemes específics. L’objectiu d’aquesta tesi és investigar com ampliar l’aplicabilitat d’algorismes d’optimització combinatoria que exploten l’estructura dels problemes a resoldre. Ho fem des de la perspectiva del maquinari d’una computadora, perseguint l’explotació total dels recursos computacionals que ofereix el maquinari actual. Per assolir generalitat treballem amb tres problemes diferents. Primer abordem el problema de generació d’estructures de la coalició (CSGP). Trobem que l’algorisme d’última generació és IDP. Proposem un algoritme optimitzat i paral·lel capaç de resoldre el CSGP. Aconseguim això definint un nou mètode per dur a terme l’operació més crítica -Splitting-, així com definint un nou mètode per dividir l’operació de l’algoritme en els diferent subprocessos. A continuació, estudiem el problema de determinació del guanyador (WDP) per a les subhastes combinades (CA). Trobem que l’escalabilitat dels solucionadors d’avantguarda és limitada. Més concretament, mostrem com millorar la resolució de resultats de relaxació LP per al WDP en subhastes combinables de gran escala mitjançant l’aplicació de l’algoritme AD³. A continuació, contribuïm amb una versió optimitzada d’AD³ que també es pot executar en un escenari paral·lel de memòria compartida. Finalment, estudiem l’aplicació de AD³ per resoldre les relaxacions LP d’un problema més exigent de la computacionalment: El problema de la predició de cadenes laterals (SCP). Presentem una manera optimitzada de resoldre l’operació més crítica, la resol·lució d’un problema quadràtic per a un factor arbitrari. En tots els casos proposem algoritmes optimitzats que es poden escalar de forma paral·lela i que milloren notablement l’estat de la tècnica. Tres ordres de magnitud a IDP, i un ordre de magnitud a AD³. L’objectiu final d’aquest treball és demostrar com un disseny algorisme conscient de maquinari pot conduir a millores de rendiment significatives. Mostrem estratègies exportables a algorismes d’optimització combinatòria similars. Aquestes estratègies ajudaran al dissenyador d’algorismes a assolir més eficiència en les CPU modernes.

La optimización combinatoria es un tipo específico de optimización donde el dominio de las variables es discreto. Este tipo de problemas de optimización tienen una gran aplicabilidad debido a su capacidad de optimización sobre objetos unitarios y no divisibles. Más allá de los algoritmos genéricos, la comunidad investigadora es muy activa proponiendo algoritmos capaces de abordar problemas de optimización combinatoria para problemas específicos. El objetivo de esta tesis es investigar cómo ampliar la aplicabilidad de algoritmos de optimización combinatoria que explotan la estructura de los problemas a resolver. Lo hacemos desde la perspectiva del hardware de una computadora, persiguiendo la explotación total de los recursos computacionales que ofrece el hardware actual. Para alcanzar generalidad trabajamos con tres problemas diferentes. Primero abordamos el problema de generación de estructuras de la coalición (CSGP). Encontramos que el algoritmo de última generación es IDP. Proponemos un algoritmo optimizado y paralelo capaz de resolver el CSGP. Conseguimos esto deniendo un nuevo metodo para llevar a cabo la operacion mas crtica -Splitting-, así como deniendo un nuevo método para dividir la operación del algoritmo en los diferente subprocesos. A continuación, estudiamos el problema de determinación del ganador (WDP) para las subastas combinatorias (CA). Encontramos que la escalabilidad de los solucionadores de vanguardia es limitada. Más concretamente, mostramos cómo mejorar la resolución de resultados de relajación LP para el WDP en subastas combinatorias de gran escala mediante la aplicación del algoritmo AD³. A continuación, contribuimos con una versión optimizada de AD³ que también se puede ejecutar en un escenario paralelo de memoria compartida. Finalmente, estudiamos la aplicación de AD³ para resolver las relajaciones LP de un problema más exigente de la computacionalmente: El problema de la predición de cadenas laterales (SCP). Presentamos una manera optimizada de resolver la operación más crítica, la resolución de un problema cuadrático para un factor arbitrario. En todos los casos proponemos algoritmos optimizados que se pueden escalar de forma paralela y que mejoran notablemente el estado de la técnica. Tres órdenes de magnitud en IDP, y un orden de magnitud en AD³. El objetivo nal de este trabajo es demostrar como un diseño algoritmo consciente de hardware puede conducir a mejoras de rendimiento signicativas. Mostramos estrategias exportables a algoritmos de optimización combinatoria similares. Estas estrategias ayudarán al diseñador de algoritmos lograr más eficiencia en las CPU modernas.

Combinatorial Optimization is a specific type of mathematical optimization where variables' domain is discrete. This kind of optimization problems have an enormous applicability due to its ability to optimize over unitary and non-divisible objects. Beyond generic algorithms, the research community is very active proposing algorithms able to tackle specific combinatorial optimization problems.

The goal of this thesis is to investigate how to widen the applicability of Combinatorial Optimization algorithms that exploit the structure of the problems to solve. We do so from a computer's hardware perspective, pursuing the full exploitation of computational resources offered by today's hardware.

For the sake of generality we work on three different problems. First we tackle the Coalition Structure Generation Problem (CSGP). We find that the state-of-the-art algorithm is IDP. We propose an optimized and parallel algorithm able to solve the CSGP. We reach this by defining a novel method to perform the most critical operation --Splitting-- as well as by defining a novel method to divide the the algorithm's operation in threads.

Then, we study the Winner Determination Problem (WDP) for Combinatorial Auctions (CA), which is very related to the CSGP. We find that state-of-the-art solvers' scalability is limited. More specifically we show how to improve results solving LP relaxations for the WDP in Large Scale Combinatorial Auctions by applying the AD³ algorithm. Then we contribute with an optimized version of AD³ which is also able to run in a shared-memory parallel scenario.

Finally we study the application of AD³ to solve the LP relaxations of a more CPU demanding problem: The Side-Chain Prediction (SCP). We present an optimized way to solve the most critical operation which is solving a Quadratic Problem for an Arbitrary Factor.

In all the cases we propose optimized algorithms that are scalable in parallel and that improve significantly the state-of-the-art. Three orders of magnitude speedup on IDP, one order of magnitude speedup in AD³.

The ultimate purpose of this work is to demonstrate how a hardware-aware algorithmic design can lead to significant speedups. We show strategies that are exportable to similar Combinatorial Optimization algorithms. Such strategies will help the algorithm designer to achieve more efficiency in modern CPUs.