A Generic Solver Based on Functional Parallelism for Solving Combinatorial Optimization Problems
Summary :
This paper proposes a new class of parallel branch-and-bound (B&B) schemes. The main idea of the scheme is to focus on the functional parallelism instead of conventional data parallelism, and to support such a heterogeneous and irregular parallelism by using a collection of autonomous agents distributed over the network. After examining several implementation issues, we describe a detail of the prototype system implemented over eight PC's connected by a network. The result of experiments conducted over the prototype system indicates that the proposed parallel processing scheme significantly improves the performance of the underlying B&B scheme by adaptively switching exploring policies adopted by each agent participating to the problem solving.
- Publication
- IEICE TRANSACTIONS on Information Vol.E89-D No.6 pp.1940-1947
- Publication Date
- 2006/06/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1093/ietisy/e89-d.6.1940
- Type of Manuscript
- PAPER
- Category
- Distributed Cooperation and Agents
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
Shigeaki TAGASHIRA, Masaya MITO, Satoshi FUJITA, "A Generic Solver Based on Functional Parallelism for Solving Combinatorial Optimization Problems" in IEICE TRANSACTIONS on Information,
vol. E89-D, no. 6, pp. 1940-1947, June 2006, doi: 10.1093/ietisy/e89-d.6.1940.
Abstract: This paper proposes a new class of parallel branch-and-bound (B&B) schemes. The main idea of the scheme is to focus on the functional parallelism instead of conventional data parallelism, and to support such a heterogeneous and irregular parallelism by using a collection of autonomous agents distributed over the network. After examining several implementation issues, we describe a detail of the prototype system implemented over eight PC's connected by a network. The result of experiments conducted over the prototype system indicates that the proposed parallel processing scheme significantly improves the performance of the underlying B&B scheme by adaptively switching exploring policies adopted by each agent participating to the problem solving.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e89-d.6.1940/_p
Copy
@ARTICLE{e89-d_6_1940,
author={Shigeaki TAGASHIRA, Masaya MITO, Satoshi FUJITA, },
journal={IEICE TRANSACTIONS on Information},
title={A Generic Solver Based on Functional Parallelism for Solving Combinatorial Optimization Problems},
year={2006},
volume={E89-D},
number={6},
pages={1940-1947},
abstract={This paper proposes a new class of parallel branch-and-bound (B&B) schemes. The main idea of the scheme is to focus on the functional parallelism instead of conventional data parallelism, and to support such a heterogeneous and irregular parallelism by using a collection of autonomous agents distributed over the network. After examining several implementation issues, we describe a detail of the prototype system implemented over eight PC's connected by a network. The result of experiments conducted over the prototype system indicates that the proposed parallel processing scheme significantly improves the performance of the underlying B&B scheme by adaptively switching exploring policies adopted by each agent participating to the problem solving.},
keywords={},
doi={10.1093/ietisy/e89-d.6.1940},
ISSN={1745-1361},
month={June},}
Copy
TY - JOUR
TI - A Generic Solver Based on Functional Parallelism for Solving Combinatorial Optimization Problems
T2 - IEICE TRANSACTIONS on Information
SP - 1940
EP - 1947
AU - Shigeaki TAGASHIRA
AU - Masaya MITO
AU - Satoshi FUJITA
PY - 2006
DO - 10.1093/ietisy/e89-d.6.1940
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E89-D
IS - 6
JA - IEICE TRANSACTIONS on Information
Y1 - June 2006
AB - This paper proposes a new class of parallel branch-and-bound (B&B) schemes. The main idea of the scheme is to focus on the functional parallelism instead of conventional data parallelism, and to support such a heterogeneous and irregular parallelism by using a collection of autonomous agents distributed over the network. After examining several implementation issues, we describe a detail of the prototype system implemented over eight PC's connected by a network. The result of experiments conducted over the prototype system indicates that the proposed parallel processing scheme significantly improves the performance of the underlying B&B scheme by adaptively switching exploring policies adopted by each agent participating to the problem solving.
ER -
English
