IEICE TRANSACTIONS on Information
Extending MaxSAT to Solve the Coalition Structure Generation Problem with Externalities Based on Agent Relations
Summary :
Coalition Structure Generation (CSG) means partitioning agents into exhaustive and disjoint coalitions so that the sum of values of all the coalitions is maximized. Solving this problem could be facilitated by employing some compact representation schemes, such as marginal contribution network (MC-net). In MC-net, the CSG problem is represented by a set of rules where each rule is associated with a real-valued weights, and the goal is to maximize the sum of weights of rules under some constraints. This naturally leads to a combinatorial optimization problem that could be solved with weighted partial MaxSAT (WPM). In general, WPM deals with only positive weights while the weights involved in a CSG problem could be either positive or negative. With this in mind, in this paper, we propose an extension of WPM to handle negative weights and take advantage of the extended WPM to solve the MC-net-based CSG problem. Specifically, we encode the relations between each pair of agents and reform the MC-net as a set of Boolean formulas. Thus, the CSG problem is encoded as an optimization problem for WPM solvers. Furthermore, we apply this agent relation-based WPM with minor revision to solve the extended CSG problem where the value of a coalition is affected by the formation of other coalitions, a coalition known as externality. Experiments demonstrate that, compared to the previous encoding, our proposed method speeds up the process of solving the CSG problem significantly, as it generates fewer number of Boolean variables and clauses that need to be examined by WPM solver.
- Publication
- IEICE TRANSACTIONS on Information Vol.E97-D No.7 pp.1812-1821
- Publication Date
- 2014/07/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E97.D.1812
- Type of Manuscript
- PAPER
- Category
- Information Network
Authors
Xiaojuan LIAO
Kyushu University
Miyuki KOSHIMURA
Kyushu University
Hiroshi FUJITA
Kyushu University
Ryuzo HASEGAWA
Kyushu University
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
Xiaojuan LIAO, Miyuki KOSHIMURA, Hiroshi FUJITA, Ryuzo HASEGAWA, "Extending MaxSAT to Solve the Coalition Structure Generation Problem with Externalities Based on Agent Relations" in IEICE TRANSACTIONS on Information,
vol. E97-D, no. 7, pp. 1812-1821, July 2014, doi: 10.1587/transinf.E97.D.1812.
Abstract: Coalition Structure Generation (CSG) means partitioning agents into exhaustive and disjoint coalitions so that the sum of values of all the coalitions is maximized. Solving this problem could be facilitated by employing some compact representation schemes, such as marginal contribution network (MC-net). In MC-net, the CSG problem is represented by a set of rules where each rule is associated with a real-valued weights, and the goal is to maximize the sum of weights of rules under some constraints. This naturally leads to a combinatorial optimization problem that could be solved with weighted partial MaxSAT (WPM). In general, WPM deals with only positive weights while the weights involved in a CSG problem could be either positive or negative. With this in mind, in this paper, we propose an extension of WPM to handle negative weights and take advantage of the extended WPM to solve the MC-net-based CSG problem. Specifically, we encode the relations between each pair of agents and reform the MC-net as a set of Boolean formulas. Thus, the CSG problem is encoded as an optimization problem for WPM solvers. Furthermore, we apply this agent relation-based WPM with minor revision to solve the extended CSG problem where the value of a coalition is affected by the formation of other coalitions, a coalition known as externality. Experiments demonstrate that, compared to the previous encoding, our proposed method speeds up the process of solving the CSG problem significantly, as it generates fewer number of Boolean variables and clauses that need to be examined by WPM solver.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E97.D.1812/_p
Copy
@ARTICLE{e97-d_7_1812,
author={Xiaojuan LIAO, Miyuki KOSHIMURA, Hiroshi FUJITA, Ryuzo HASEGAWA, },
journal={IEICE TRANSACTIONS on Information},
title={Extending MaxSAT to Solve the Coalition Structure Generation Problem with Externalities Based on Agent Relations},
year={2014},
volume={E97-D},
number={7},
pages={1812-1821},
abstract={Coalition Structure Generation (CSG) means partitioning agents into exhaustive and disjoint coalitions so that the sum of values of all the coalitions is maximized. Solving this problem could be facilitated by employing some compact representation schemes, such as marginal contribution network (MC-net). In MC-net, the CSG problem is represented by a set of rules where each rule is associated with a real-valued weights, and the goal is to maximize the sum of weights of rules under some constraints. This naturally leads to a combinatorial optimization problem that could be solved with weighted partial MaxSAT (WPM). In general, WPM deals with only positive weights while the weights involved in a CSG problem could be either positive or negative. With this in mind, in this paper, we propose an extension of WPM to handle negative weights and take advantage of the extended WPM to solve the MC-net-based CSG problem. Specifically, we encode the relations between each pair of agents and reform the MC-net as a set of Boolean formulas. Thus, the CSG problem is encoded as an optimization problem for WPM solvers. Furthermore, we apply this agent relation-based WPM with minor revision to solve the extended CSG problem where the value of a coalition is affected by the formation of other coalitions, a coalition known as externality. Experiments demonstrate that, compared to the previous encoding, our proposed method speeds up the process of solving the CSG problem significantly, as it generates fewer number of Boolean variables and clauses that need to be examined by WPM solver.},
keywords={},
doi={10.1587/transinf.E97.D.1812},
ISSN={1745-1361},
month={July},}
Copy
TY - JOUR
TI - Extending MaxSAT to Solve the Coalition Structure Generation Problem with Externalities Based on Agent Relations
T2 - IEICE TRANSACTIONS on Information
SP - 1812
EP - 1821
AU - Xiaojuan LIAO
AU - Miyuki KOSHIMURA
AU - Hiroshi FUJITA
AU - Ryuzo HASEGAWA
PY - 2014
DO - 10.1587/transinf.E97.D.1812
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E97-D
IS - 7
JA - IEICE TRANSACTIONS on Information
Y1 - July 2014
AB - Coalition Structure Generation (CSG) means partitioning agents into exhaustive and disjoint coalitions so that the sum of values of all the coalitions is maximized. Solving this problem could be facilitated by employing some compact representation schemes, such as marginal contribution network (MC-net). In MC-net, the CSG problem is represented by a set of rules where each rule is associated with a real-valued weights, and the goal is to maximize the sum of weights of rules under some constraints. This naturally leads to a combinatorial optimization problem that could be solved with weighted partial MaxSAT (WPM). In general, WPM deals with only positive weights while the weights involved in a CSG problem could be either positive or negative. With this in mind, in this paper, we propose an extension of WPM to handle negative weights and take advantage of the extended WPM to solve the MC-net-based CSG problem. Specifically, we encode the relations between each pair of agents and reform the MC-net as a set of Boolean formulas. Thus, the CSG problem is encoded as an optimization problem for WPM solvers. Furthermore, we apply this agent relation-based WPM with minor revision to solve the extended CSG problem where the value of a coalition is affected by the formation of other coalitions, a coalition known as externality. Experiments demonstrate that, compared to the previous encoding, our proposed method speeds up the process of solving the CSG problem significantly, as it generates fewer number of Boolean variables and clauses that need to be examined by WPM solver.
ER -
English
