TitleEnhancing Performance on Combinatorial Optimization Algorithms
Publication TypeThesis
Year of Publication2018
AuthorsCruz F
Number of Pages146

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 prob- lems 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 Combinato- rial 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 Auc- tions by applying the AD3 algorithm. Then we contribute with an optimized version of AD3 which is also able to run in a shared-memory parallel scenario.

Finally we study the application of AD3 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 AD3.

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.