Parallel and Random Solving of a Network Design Problem

Date Added: Apr 2010
Format: PDF

Parallel and Random Solving of a Network Design Problem Applications for industrial optimization have to be "Robust". They must provide effective solutions to problems of varying sizes and numerical characteristics. These applications should continue to remain effective and work well even after the addition of side constraints. In practice, this refers to problems for which no preferred hard fast solving techniques are known. The situation is further complicated by the fact that the search tree takes a huge form and hence prohibits the validity of any potential solution. No method can be expected to find optimized solutions. Recently, a network design problem exhibited by France Telecom is one such instance. This is also an ideal example for employing two techniques: large neighborhood search and portfolios of algorithms. Firstly, application of mentioned techniques was accomplished and then attention was turned on improving the performance. First, the implementation of a specializing Metaheuristic is done with the aim to minimize speculative work. Second, the parallelization of previous implementation was done by using a shared memory multiprocessor. New issues came to light as all methods proved to be difficult to parallelize. Trial of Multiple parallelization implementations was done to improve parallel solving efficiency. Then, the result was shown to outperform every known CP-based method.