Plan Max Manfrin

History (past work)

http://iridia.ulb.ac.be/wiki/index.php/History_Max_Manfrin

Plan (future work)

Parallelization of ACO algorithms

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 - completly-connected
        • each colony identifies the best bsf and grab it
        • the colony with the worst bsf grab the best bsf
      • Multicolony - ring
      • Multicolony - hypercube
      • Single colony, multi local search
    • Async
      • Multicolony - completly-connected
        • each colony identifies the best bsf and grab it
        • the colony with the worst bsf grab the best bsf
      • Multicolony - ring
      • Multicolony - hypercube
      • Single colony, multi local search
• Paper submission to ANTS 2006 of "explicit parallelization of ACOTSP"

Milestone II : Apr - Jun 2006

• Evolve practical experience in explicit parallelization on ACO algorithms
  • Start from sequential ILK-H and parallelize it with MPI, calling it within parallel ACOTSP
• 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"
• Paper on "hybridization of parallel ACOTSP and ILK-H"

Milestone III : Jul - Sep 2006

• Transfer the knowledge and experience on TSP to other problems
  • Move to Vehicle Routing Problem
  • Collaboration with Marco Caserta on parallel ACO for Set Covering Problem

Milestone IV : Oct - Dec 2006

• Add complexity to the VRP problem moving into Rich VRP

Milestone V : Jan - Mar 2007

Milestone VI : Apr - Jun 2007

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	Real deadline
Study MPI	Nov 14, 2005		ongoing process	In progress
Explicit parallelization of ACOTSP using MPI	Nov 14, 2005	Jan 8, 2006	~9 weeks	done	Jan 24, 2006
Synch version of "One colony - many LS (3-opt)"	Nov 14, 2005	Dec 5, 2005	~26 days	done	Jan 24, 2006
Synch version of "Many homogeneous colonies - all-all"	Dec 10, 2005	Dec 22, 2005	~13 days	done	Jan 24, 2006
--= DISCUSSION WITH MARCO, MAURO, THOMAS =--	Jan 30, 2006
Profile sequential ACOTSP code with instaces (1000 < size < 2000)	Jan 30, 2006		1 day	done
Implement Asynch versions
Experiments on TSP instances (1000 < size < 6000)		Feb 26, 2006		in progress
Abstract submission for ANTS 2006		Mar 12, 2006
Submission of paper for ANTS 2006		Mar 19, 2006

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

Weekly planning

Description	Start date	Deadline	Completion date	status	Note
1.0 Patch the algorithms in such a way that they use only globabl best in pheromone update and they use quadrant nearest neighbour	Feb 16	Feb 21		in progress
1.0.1 Sync - Multicolony - all-all	Feb 16	Feb 21	Feb 19	completed	experiments finished
1.0.2 Sync - Multicolony - replace-worst	Feb 19	Feb 21	Feb 19	experiments running
1.1 Patch the 3 following algorithms in such a way that they write the output on /tmp (local to the node) instead of /home (NFS mounted)	Feb 21	Feb 28		in progress	Will have to do also for completly-connected and replace-worst
1.1.0 Disable cron jobs on nodes r05, r07, r19, r32	Feb 21			done	RE-ENABLE cron scripts after finishing experiments
1.1.3 Sync - MultiLS	Feb 19	Feb 21	Feb 21		development completed, test before launching experiments
1.1.4 Sync - Multicolony - ring		Feb 21
1.1.5 Sync - Multicolony - 3D hypercube		Feb 21
2.1 Send to Thomas and Mauro a list of all paper that deals with Parallel ACO for TSP that contains experimental results in order to check what the others have been doing	Feb 19	Feb 21	Feb 19	done
2.2 Read the paper: M. Middendorf, F. Reischle, and H. Schmeck. Multi colony ant algorithms. Journal of Heuristics, 8(3):305–320, May 2002.	Feb 20	Feb 21	Feb 20	done
3 Implement async versions					In case of problem try to get help from Anders
3.1 Async - Multicolony - all-all
3.2 Async - Multicolony - replace-worst
3.3 Async - Multicolony - ring
3.4 Async - Multicolony - 3D hypercube
3.5 Asynch - MultiLS

Seminars participation

Title	Author	Location	Dates
2nd BEGrid tutorial	-	ULB	Feb 21, 2006

Events participation

Event	Location	Dates

Papers to write

Title	Journal/Conference targeted	Start date	Submission deadline
A Survey of Parallel ACO algorithms	N.A.	N.A.	N.A.
Process-level parallelization of ACOTSP	Ants 2006 international workshop	N.A.	Mar 12, 2006
Thread-level parallelization of ACOTSP	N.A.	N.A.	N.A.

Referee activities

International journals

Journal	# papers	paper received on	review to submit before
European Journal of Operational Research	1	Dec 21, 2005	Jan 31, 2006

International conferences

Conference	# papers	paper received on	review to submit before
GECCO 2006	5	Feb 6, 2006	Mar 20, 2006
WSC11	3-4 (estimation)	May/June 2006 (estimation)	30 Jun 2006

IRIDIA chores

Chore	assigned	status
Update Dorigo website with Master, DEA, and PhD thesis data	Feb 2, 2006
Update Dorigo website with new portoguese interview	Feb 19, 2006