**********************************
Title: Ant colony optimization for the variable sized bin packing problem
Master Specialization: Algorithms and Programming
Orientation: Research
Thesis advisor(s): Dr. Christian Blum
Ponent: not required
Contact: cblum@lsi.upc.edu
Student: open
Thesis Description
Ant colony optimization (ACO) is a swarm intelligence technique inspired by the shortest path finding capabilities of real ant colonies. When searching for food, ants initially explore the area surrounding their nest in a random manner. While moving, they leave a chemical pheromone trail on the ground. Ants can smell pheromone. When choosing their way, they tend to choose, in probability, paths marked by strong pheromone concentrations. As soon as an ant finds a food source, it carries some of the food back to the nest. During the return trip, the quantity of pheromone that an ant leaves on the ground may depend on the quantity and quality of the food. The pheromone trails will guide other ants to the food source. This indirect communication between the ants via pheromone trails---known as stigmergy---enables them to find shortest paths between their nest and food sources. The ACO metaheuristic uses this behaviour for solving combinatorial optimization problems.
The aim of this thesis is to develop one ore more variants of the ACO metaheuristic to solve the variable sized bin packing problem (VSBPP), which is a combinatorial optimization problem. The VSBPP is a variant of the well-known one-dimensional bin packing problem.
Comments for the Academic Comission
None
Requirements
Programming in C++, some knowledge of heuristic methods, prior knowledge on ant colony optimization is not required
Needed resources
A computer with a C++ compiler.
The cluster of the PCs of the ALBCOM research group will be available for the experimentation.
==================================================
Title: A Library for Spatial and Metric Algorithms and Data Structures
Master Specialization: Algorithmics and Programming
Orientation: research
Thesis advisor(s): Salvador Roura
Contact: mercep@gmail.com, roura@lsi.upc.edu
Student: Merc? Pons Crespo
Thesis Description
The purpose of this thesis is to develop and implement an efficient library of
generic metric and spatial data structures and algorithms in the spirit of C++
Standard Template Library. The components of the library must be robust,
flexible and must be throughly tested for performance tuning, providing
ready-to-use solutions to common problems in the area, like nearest neighbor
search or orthogonal range search, using state-of-the-art algorithms and data
structures.
Besides the implementation of the library itself, careful computational
experiments must be conducted to establish the practical performance of its
components, with systematic comparisons when the library provides alternative
solutions to a given problem. The experiments should also serve to find variants
and heuristics of the standard data structures and algorithms which improve the
performance, e.g., simple criteria to order the exploration of a hierarchical
index in a nearest neighbor search.
This thesis could build upon the ideas laid down in the SMTL (Spatial and Metric
Template Library), which was designed a few years ago by Guillem Marpons for his
Final Project. Unfortunately, only a very small part of the SMTL was actually
implemented, but it proposed a coherent and homogeneous framework for the kind
of library that we want to develop for the present Master Thesis proposal.
Requirements
Very good programming skills, good knowledge of C++, a strong background in
algorithms and data structures, good knowledge of statistical techniques and of
analysis of algorithms. A good level for reading and writing in English is a
must, and knowledge of LaTeX is also desirable.
Needed resources
Carrying out the computational experiments requires access to high performance
computers. For the rest of the tasks, implementation, documentation, etc. a
standard computer with access to Internet and common tools (editors, compilers,
statistical and plotting packages, ...) should be enough. Access to the research
literature and to the University library is also necessary.
=========================================================
Title: The Hiring Problem: An Analytic and Experimental Study
Master Specialization: Algorithmics and Programming
Orientation: research
Thesis advisor(s): Conrado Martínez
Contact: conrado@lsi.upc.edu
Student: Ahmed Helmi (ahelmi@lsi.upc.edu)
Thesis Description The hiring problem is a simple model for
on-line decision making under uncertainty. A company sequentially
interviews candidates and for each one an irrevocable
decision (hire or discard) must be taken based on the "quality"
or score of the candidate and that of previous candidates, with
no knowledge of the future. The problem is realted to the well
known secretary problem and was very recently introduced by
Broder et al. (SODA 2008). Archibald and Martínez (FPSAC 2009)
have proposed an alternative model for the hiring problem which
allows the use of combinatorial and analytic techniques to
investigate this problem. In their work they have been able to
prove several general theorems applying to large families of
hiring strategies, and used them to derive very precise
probabilistic analysis of a few particular important strategies.
The thesis is a follow-up of the work of Archibald and Martínez, with two
main concerns. On the one hand, the development of tools and programs (most likely in C++ and Matlab) that
allows us to perform simulations of different hiring strategies and variations
of the original hiring problem. These tools will be very useful to validate the theoretical models, but most importantly, for exploratory
work. Part of the thesis will report the experimental work done with such tools.
The other main concern will be the analytic research on this problem. Here, the goal is to provide general results for some new parameters and analyze their behavior in particular important strategies:
- Time of the last hiring - Distance between the two last hirings
- Score the best candidate not hired
Another part will be devoted to the analysis of a variant of the problem where it is
possible to fire candidates. In particular, one goal is to analyze an important family of strategies called "replacement strategies"; these achieve optimal quality
at the expense of firing candidates. Hence, a parameter of upmost importance for these strategies is the number of firings, which will be analyzed in the thesis.
Other possible extensions include the analysis of multicriteria hiring, when
there are k concepts and each candidate has k scores, one for each concept.
Comments for the Academic Comission
Requirements
- Good mathematical skills, specially in combinatorics, discrete mathematics and probability. - Good background in algorithmics
- Good knowledge of programming, proficiency in C++ and/or other programming languages and some computer algebra system (e.g., Maple, Matlab, Mathematica); knowldege of Unix/Linux operating system
Needed resources
- A computer to do the programming, experiments, computations, etc. with all
the necessary software (which is either free or the UPC has already licenses)
- Access to Internet and to bibliographic resources
- Access to the LCLSI resources and services (printers, scanner, disks, ...)
===========================================================