Parallel and Random Solving of a Network Design Problem

Contents

Industrial optimization applications must be ``robust,'' i.e., must provide good solutions to problem instances of different size and numerical characteristics, and must continue to work well when side constraints are added. In practice, this translates into problems where no preferred solving techniques exist and where the search tree is so huge that no method is expected to find (and prove) optimal solutions. A network design problem recently made public by France Telecom is a perfect example of this type of problem. It is also a perfect candidate for using two techniques: large neighborhood search and portfolios of algorithms. After a successful first application of these techniques to the problem, attention was focused on improving performance. First, a specializing metaheuristic to reduce speculative work was implemented. Second, the previous implementation was parallelized on a shared memory multiprocessor machine. New issues arose as all methods were difficult to parallelize. Multiple parallelization implementations were tried in order to improve the efficiency of parallel solving with these methods. The result was then shown to outperform all known CP-based methods.