Branch-and-Bound based Algorithms on Parallel Computing Environments

• General Backtracking methods
  • Combinatorial problem(s) involved in the implementation: 0/1-knapsack problem, 15-puzzle, search for Golomb rulers, search for transition tables of cellular automata, and game tree search.
  • The motivation for parallelism: 1. Backtracking is time consuming. 2. In principle easy to parallelize. 3. Load balancing is an interesting challenge.
  • The type of hardware and number of processors used: MIMD computers from workstation networks through machines with 1024 processors: transputers, IBM SP. SIMD computer MasPar MP-1 with 16384 processors.
  • Often almost linear speedup over the non-parallel version.
  • Availability of the software: The reusable library PIGSeL is available upon request.
  • More information is available at this page or contact Peter Sanders .
  • Address: University of Karlsruhe, Dept. of Computer Science, Chair for Informatics in Science and Engineering, Germany.

  ---

• General (Mixed) Integer Programming:
  • Combinatorial problems(s) involved in the implementation: unknown.
  • The motivation fro parallelism: Speed-up in commercial problems, i.e. reducing times to solve some problems from perhaps overnight to being able to do a couple of runs per day. Important in scenario analysis in many industries.
  • Type of hardware used: UNIX workstations + Windows 3.1/Win95/WinNT PCs.
  • How results compare with the non-parallel version: Machines 4 x RS6K/390s
    • Model Serial Time Computers Parallel Time Speed Up
    • SPLY 4440 4 x 390 540 8.22
    • BPOR 3545 4 x 390 461 7.69
    • NPSOX 660 4 x 390 245 2.69
    • Slaves Elapsed Time (secs) Speedup
    • 0 (serial) 515 1.00
    • 1 552 0.93
    • 2 319 1.61
    • 3 232 2.22
    • 4 181 2.85
    • 5 135 3.81
    • 6 124 4.15
  • The software is commercial.
  • To get more infor about it check this page , or contact: Bob Daniel, Dash Associates, Blisworth House, Blisworth, Northants NN7 3BX, UK.
• A parallel synchronized Branch and Bound.