Efficient Representation of Constraints and Propagation of Variable-Value Symmetries in Distributed Constraint Reasoning
スポンサーリンク
概要
- 論文の詳細を見る
In this paper, we discuss variable and value symmetries in distributed constraint reasoning and efficient methods to represent and propagate them in distributed environments. Unlike commonly used centralised methods which detect symmetries according to their global definition, we suggest here to define them at the individual constraint level, then define operations on those symmetries in order to propagate them through the depth-first search tree that is generated in efficient distributed constraint reasoning algorithms. In our algorithm, we represent constraints (or utility functions) by a list of costs: while the usual representation lists one cost for one assignation, we drastically reduce the size of that list by keeping only one cost for one class of equivalence of assignations. In practice, for a constraint with n symmetric variables defined on a domain of n symmetric values, this approach cuts down the size of the list of costs from nn to p(n) (partition function of n), i.e., from 1010 to 42 when n=10. We henceforth devised algorithms to process the sparse representations of utility functions and to propagate them along with symmetry information among distributed agents. We implemented this new representation of constraints and tested it with the DPOP algorithm on distributed graph colouring problems, rich in symmetries. Our evaluation shows that in 19% of execution instances we cut down 10 times the volume of communication spent, while no significant overhead appears in non symmetrical executions. These results open serious perspectives on a possible bounding of memory and communication bandwidth consumption in some subclass of distributed constraint reasoning problems.
- 2011-05-15
著者
-
Nagamochi Hiroshi
Kyoto Univ.
-
Hiroshi Nakashima
ACCMS, Kyoto University
-
Xavier Olive
Kyoto University
-
Hiroshi Nakashima
Kyoto University
関連論文
- Constant Time Generation of Trees with Degree Bounds
- A Memory-Efficient Algorithm and Its Implementation of Variable-Size All-to-All Communication
- k-Edge and 3-Vertex Connectivity Augmentation in an Arbitrary Multigraph
- Augmenting Edge-Connectivity and Vertex-Connectivity Simultaneously
- Enumerating Colored and Rooted Outerplanar Graphs
- BI-CRITERIA FOOD PACKING BY DYNAMIC PROGRAMMING(the 50th Anniversary of the Operations Research Society of Japan)
- APPROXIMATING MINIMUM COST MULTIGRAPHS OF SPECIFIED EDGE-CONNECTIVITY UNDER DEGREE BOUNDS(the 50th Anniversary of the Operations Research Society of Japan)
- An Efficient Vector Transfer for Sparse Matrix-Vector Multiplication on Distributed Memory Systems
- Orthogonal Drawings for Plane Graphs with Specified Face Areas
- Efficient Representation of Constraints and Propagation of Variable-Value Symmetries in Distributed Constraint Reasoning
- Symmetry Breaking by Dominance Detection in Distributed Environments
- Around the Constructive Orbit Problem in Distributed Constraint Programming
- The Next-to-Shortest Path in Undirected Graphs with Nonnegative Weights
- FOREWORD (Special Section on Discrete Mathematics and Its Applications)
- GRAPH ALGORITHMS FOR NETWORK CONNECTIVITY PROBLEMS(Network Design, Control and Optimization)
- Accelerating A* algorithms by sweeping out small-degree nodes
- CONSTANT FACTOR APPROXIMATION ALGORITHMS FOR REPETITIVE ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS
- A Simulation-Based Analysis for Worst Case Delay of Single and Multiple Interruptions
- Multilingualization Based on RPC for Job-level Parallel Script Language, Xcrypt
- Breadth-first Search Approach to Enumeration of Tree-like Chemical Compounds
- Breadth-first Search Approach to Enumeration of Tree-like Chemical Compounds
- CONSTANT FACTOR APPROXIMATION ALGORITHMS FOR REPETITIVE ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS