The objective of this project is to develop new models for parallel branch and bound algorithms. These methods are used for solving NP hard problems like the travelling salesman, for relatively small instances. These new models would be applied to NP hard graph problems. Finding new methods to achieving efficiency in distributing the processing is another objective of this project.
In this research these questions would be addressed:
1. How to develop new models for parallel branch and bound algorithm?
2. How to achieve efficiency in distributing processing load?
3. How to apply parallel branch and bound method to NP hard graph problems?
4. Solving large instance of NP hard problems using parallel models?
A.H. Land introduced the branch and bound algorithm for solving optimization problems [Land, 1960]. This method has been used for solving several NP-hard problems like TSP [Volgenant, 1982], Integer Programming [Zhang, 2013] and many others. However the size of problem was rather small. There have been some tries to solve this problem [AitZai, 2012], but all of them trying to restrict the search space with some methods like heuristic functions. The aim of this project is to find the most efficient distribution of processing load to find a model for parallel branch and bound algorithm.
The goal of this project is to find new models for paralleling processing in nodes according to the properties of graph problems. These new models of parallel branch and bound algorithms would be tested for several NP hard problems. We can use artificial intelligence methods like machine learning, neural networks and etc to select smart nodes for the processing
References:
[Land, 1960] A. H. Land and A. G. Doig (1960). "An automatic method of solving discrete programming problems". Econometrica 28 (3): pp. 497–520. doi:10.2307/1910129.
[Volgenant, 1982] T. Volgenant and R. Jonker. "A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation". European Journal of Operational Research. Volume 9. Issue 1. January 1982. Pages 83-89.
[Zhang, 2013] L.Zhang. W.Tan and X.Huang. "Optimized load distributed of power plant units based on branch and bound method". Applied Mechanics and Materials Vols. 2013.
[AitZai, 2012] A. AitZai and M.Boudhar. "Parallel branch–and–bound and parallel PSO algorithms for job shop scheduling problem with blocking". International Journal of Operational Research. 2012.