|
|
|
|
|
A Parallel Branch and Bound Algorithm for Solving Large Scale Integer Programming Problems |
|
PP: 1691-1698 |
|
Author(s) |
|
Mahmoud M. Ismail,
Osama abd el-raoof,
Waiel F. Abd EL-Wahed,
|
|
Abstract |
|
Branch and Bound technique is commonly used for intelligent search in finding a set of integer solutions within a space of
interest. The corresponding binary tree structure provides a natural parallelism allowing concurrent evaluation of subproblems using
parallel computing technology. While the master-worker paradigm is successfully used in many parallel applications as a common
framework to implement parallel applications, it has drawbacks when a large number of computing resources are connected via WAN.
A supervisor-master-sub-master-worker algorithm has been proposed. From the solved benchmark example this algorithm proved
to provide a considerable save of time. Results show that a consistently better efficiency can be achieved in solving integer equations,
providing reduction of time. The hierarchical supervisor-master-sub-master-worker algorithm sustains good performance revealed from
the knapsack problem solved as a benchmark example. |
|
|
|
|
|