# Plan (future work)

## Milestone I: Jan - Mar 2006

• Acquire practical experience in explicit parallelization on ACO algorithms
• Start from sequential ACOTSP and implement various MPI variants
• Sync
• Multicolony - fully-connected
• colony 0 identifies the best colony; best colony broadcast its bsf solution
• colony 0 identifies the best colony and the worst colony; best colony send its bsf solution to worst colony
• Multicolony - ring
• unidirectional ring
• Multicolony - hypercube
• 3D hypercube
• Single colony, multi local search
• Async
• Multicolony - completly-connected
• colony 0 identifies the best colony; best colony broadcast its bsf solution
• colony 0 identifies the best colony and the worst colony; best colony send its bsf solution to worst colony
• Multicolony - ring
• unidirectional ring
• Multicolony - hypercube
• 3D hypercube
• Paper submission to ANTS 2006 of "explicit parallelization of ACOTSP"
• By end of March decision if and how to extend the paper for possible Journal article
• By end of March decision if proceed with MPI version of ILK-H + ACOTSP
• Find the sentence that explain what the PhD thesis is about (what is the contribution of this thesis?)
• 1. Parallelization of ACO on multi-core architectures ?
• 2. Parallelization of ACO on collection of interesting problems?

## Milestone II: Apr - Jun 2006

• Development and empirical test of different communication schemes among colonies
```The i.a.k identify how often we do communication among colonies.

The law used to generate the periods is SQRT[(10)^(i+1)], so
i = 1 --> T = 10
i = 2 --> T = 31
i = 3 --> T = 100
i = 4 --> T = 316
i = 5 --> T = 1000
i = 6 --> T = 3162
i = 7 --> T = 10000
i = 8 --> T = 31622
i = 9 --> T = 100000

The jth exchange happens at iteration

T * (1 - 0.a^j)/(1 - 0.a)  IF (int)[x_j - x_(j-1)] > k
x_j =
k                          OTHERWISE
```
• Start from sequential ACOTSP and implement various MPI variants
• Sync
• Multicolony - ring
• unidirectional ring
• 4.8.10
• 4.9.10
• 5.8.10
• 5.9.10
• 6.8.10
• 6.9.10
• 7.6.10
• 7.7.10
• Transfer the knowledge and experience on TSP to other problems
• Collaboration with Marco Caserta on parallel ACO for Set Covering Problem
• he doesn't use ACO for SCP, but I've helped him anyway to parallelize his own primal-dual algorithm
• Collaboration with Daniele Catanzaro on parallel ACO for phylogeny reconstruction
• Start from sequential ACO algorithm and implemented MPI variant
• Sync
• Multicolony - fully-connected
• colony 0 identifies the best colony; best colony broadcast its bsf solution
• Identify possible problems for which IRIDIA has expertise and state-of-the-art ACO algo as starting points (Scheduling: Blum, QAP: Thomas)
• QAP: start from sequential MMASQAP and implement various MPI variants (in total we consider 72 algo)
• Factor 1: Connection topology
• Multicolony - fully-connected
• colony 0 identifies the best colony; best colony broadcast its bsf solution
• colony 0 identifies the best colony and the worst colony; best colony send its bsf solution to worst colony
• Multicolony - ring
• unidirectional ring
• Multicolony - hypercube
• 3D hypercube
• Factor 2: Communication schema
• Sync
• 1.x.10 (constant gap of 10 iterations)
• 2.9.10
• 2.8.10
• 2.7.10
• 2.6.10
• 3.9.10
• 3.8.10
• 3.7.10
• 3.6.10
• Factor 3: Local Search
• 2-opt
• tabu search

## Milestone III: Jul - Sep 2006

• Tech Report on TSP and QAP experiments
• decision if and how to extend the paper for possible journal article
• Literature survey on parallel ACO algorithms (version 3)
• Acquire practical experience in implicit parallelization on ACO algorithms
• Start from sequential ACOTSP and implement various OpenMP variants
• Sync ( i.e. implicit barrier in for directives)
• Async (i.e use of the nowait clause)
• ? Paper on "implicit vs explicit parallelization of ACOTSP"

## Milestone VII: Jul - Sep 2007

• Write PhD thesis

# Goals

• Investigate the effect of parallelization on Ant Colony Optimization algorithms
• Acquire practical experience in parallelization on ACO algorithms (both explicit and implicit parallelism)
• Implicit parallelism is the new trend (multi core CPUs), not much work has been done on them yet

# Things to do

Description Start date Deadline Time required status
Study OpenMP Jan 9, 2005 ongoing process In progress
Implicit parallelization of ACOTSP using OpenMP - - - Need a compiler
Parallel ACO survey v3 Jul 1, 2006 Aug 31, 2006

## Weekly planning

Description Start date Deadline Completion date status Note

# Seminars participation

Title Author Location Dates
IRIDIA Optimization meeting Ch. 4 of the book to present Apr 27, 2006

# Events participation

Event Location Dates

# Papers to write

A Survey of Parallel ACO algorithms N.A. N.A.
Thread-level parallelization of ACOTSP N.A. N.A.

# Referee activities

## International journals

Journal # papers paper received on review to submit before

## International conferences

Conference # papers paper received on review to submit before

# IRIDIA chores

Chore assigned status
Update Dorigo website with Master, DEA, and PhD thesis data Feb 2, 2006 done
Create a Wiki page with list of all the software we have for the Mac with #licenses and where they are installed Apr 21, 2006