MPI C++ parallel search combinatorial optimisation

Keyword: C++, MPI, combinatorial optimization, routing problem, PBSpro, doxygen Intel Compiler, boost library. Phase I: The goal of this mpich project is to document (in term of graph) the behavior of several random searches. The searches are used to find the optimal solution to a routing problem (vehicle routing problem with time windows). Understanding this problem is not mandatory to complete this project since solutions are already generated by provided mechanism. Example, you have a depot numbered 0 and a set of customer 1,2,3 with required time period of delivery. A solution might be 0,1,2,3,0 thus requiring 1 vehicle that returns to the depot, an other one might be 0,1,0,2,3,0, thus requiring two vehicles with a higher cost in number of vehicle and probably travel distance as well. An arc is defined by a travel from one node to another, ie 1-2 or 0-1. The simple algorithm is: 1) Each search generates in parallel a random solution (of different quality value) to the problem. (implemented). 2) They send their solution to a central repository that keeps only the best one (implemented). 3) The central repository looks at pattern of arcs in the best and worst solutions and sends arcs to be fixed or prohibit in each search to constrain their search or to diversify them. (to be completed). 5 different simple strategies will be tested for fixing and prohibiting arcs on different number of processors (2,4,8,16,32) The present project is missing the serialization mechanism to fix or prohibit arcs to each search. The rest of the code is already implemented. Current code will be provided to the chosen bidder. Phase I will be paid 25% of the project upon completion Phase II: add other already implemented search methods tabu search and genetic algorithm to this new framework and incorporate the new serialized fixing and prohibiting arc mechanism for theses methods as well. ## Deliverables 0) Scripts to perform run for all test problems on pbs The actual run Excel Graph for each run test Documentation in doxygen (already in place) or other type if not possible short readme for installing and running the scripts 1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done. 2) Deliverables must be in ready-to-run condition, as follows (depending on the nature of the deliverables): a) For web sites or other server-side deliverables intended to only ever exist in one place in the Buyer's environment--Deliverables must be installed by the Seller in ready-to-run condition in the Buyer's environment. b) For all others including desktop software or software the buyer intends to distribute: A software installation package that will install the software in ready-to-run condition on the platform(s) specified in this bid request. 3) All deliverables will be considered "work made for hire" under U.S. Copyright law. Buyer will receive exclusive and complete copyrights to all work purchased. (No GPL, GNU, 3rd party components, etc. unless all copyright ramifications are explained AND AGREED TO by the buyer on the site per the coder's Seller Legal Agreement). * * *This broadcast message was sent to all bidders on Tuesday Oct 18, 2005 3:05:36 PM: The bid has been extended to 22h00 pm for code review. The current code of the project can be downloaded at: ftp://[login to view URL] user: ftp password: omega2005! ## Platform Win32, linux with boost library. The awarded coder will be given access to a linux cluster to run the tests. Coder with MPI and C++ experience intereseted in bidding can request the current code of this project that we will upload to your ftp site. Here is the current version of the CODE: ftp://[login to view URL] user: <ftp@[login to view URL]> password: omega2005!