Enhancing PC Cluster-Based Parallel Branch-and-Bound Algorithms for the Graph Coloring Problem
Summary :
A branch-and-bound algorithm (BB for short) is the most general technique to deal with various combinatorial optimization problems. Even if it is used, computation time is likely to increase exponentially. So we consider its parallelization to reduce it. It has been reported that the computation time of a parallel BB heavily depends upon node-variable selection strategies. And, in case of a parallel BB, it is also necessary to prevent increase in communication time. So, it is important to pay attention to how many and what kind of nodes are to be transferred (called sending-node selection strategy). In this paper, for the graph coloring problem, we propose some sending-node selection strategies for a parallel BB algorithm by adopting MPI for parallelization and experimentally evaluate how these strategies affect computation time of a parallel BB on a PC cluster network.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E91-A No.4 pp.1140-1149
- Publication Date
- 2008/04/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1093/ietfec/e91-a.4.1140
- Type of Manuscript
- Special Section PAPER (Special Section on Selected Papers from the 20th Workshop on Circuits and Systems in Karuizawa)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Satoshi TAOKA, Daisuke TAKAFUJI, Toshimasa WATANABE, "Enhancing PC Cluster-Based Parallel Branch-and-Bound Algorithms for the Graph Coloring Problem" in IEICE TRANSACTIONS on Fundamentals,
vol. E91-A, no. 4, pp. 1140-1149, April 2008, doi: 10.1093/ietfec/e91-a.4.1140.
Abstract: A branch-and-bound algorithm (BB for short) is the most general technique to deal with various combinatorial optimization problems. Even if it is used, computation time is likely to increase exponentially. So we consider its parallelization to reduce it. It has been reported that the computation time of a parallel BB heavily depends upon node-variable selection strategies. And, in case of a parallel BB, it is also necessary to prevent increase in communication time. So, it is important to pay attention to how many and what kind of nodes are to be transferred (called sending-node selection strategy). In this paper, for the graph coloring problem, we propose some sending-node selection strategies for a parallel BB algorithm by adopting MPI for parallelization and experimentally evaluate how these strategies affect computation time of a parallel BB on a PC cluster network.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e91-a.4.1140/_p
Copy
@ARTICLE{e91-a_4_1140,
author={Satoshi TAOKA, Daisuke TAKAFUJI, Toshimasa WATANABE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Enhancing PC Cluster-Based Parallel Branch-and-Bound Algorithms for the Graph Coloring Problem},
year={2008},
volume={E91-A},
number={4},
pages={1140-1149},
abstract={A branch-and-bound algorithm (BB for short) is the most general technique to deal with various combinatorial optimization problems. Even if it is used, computation time is likely to increase exponentially. So we consider its parallelization to reduce it. It has been reported that the computation time of a parallel BB heavily depends upon node-variable selection strategies. And, in case of a parallel BB, it is also necessary to prevent increase in communication time. So, it is important to pay attention to how many and what kind of nodes are to be transferred (called sending-node selection strategy). In this paper, for the graph coloring problem, we propose some sending-node selection strategies for a parallel BB algorithm by adopting MPI for parallelization and experimentally evaluate how these strategies affect computation time of a parallel BB on a PC cluster network.},
keywords={},
doi={10.1093/ietfec/e91-a.4.1140},
ISSN={1745-1337},
month={April},}
Copy
TY - JOUR
TI - Enhancing PC Cluster-Based Parallel Branch-and-Bound Algorithms for the Graph Coloring Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1140
EP - 1149
AU - Satoshi TAOKA
AU - Daisuke TAKAFUJI
AU - Toshimasa WATANABE
PY - 2008
DO - 10.1093/ietfec/e91-a.4.1140
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E91-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 2008
AB - A branch-and-bound algorithm (BB for short) is the most general technique to deal with various combinatorial optimization problems. Even if it is used, computation time is likely to increase exponentially. So we consider its parallelization to reduce it. It has been reported that the computation time of a parallel BB heavily depends upon node-variable selection strategies. And, in case of a parallel BB, it is also necessary to prevent increase in communication time. So, it is important to pay attention to how many and what kind of nodes are to be transferred (called sending-node selection strategy). In this paper, for the graph coloring problem, we propose some sending-node selection strategies for a parallel BB algorithm by adopting MPI for parallelization and experimentally evaluate how these strategies affect computation time of a parallel BB on a PC cluster network.
ER -
English
