Applying Max-Sum to Asymmetric Distributed Constraint Optimization
Authors: Roie Zivan, Tomer Parash, Yarden Naveh
IJCAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We compared the performance of Max-sum versions when solving ADCOPs in comparison to their performance when solving symmetric DCOPs and to the most successful local search algorithms, previously proposed for ADCOPs. Moreover, we demonstrate the advantage of using a non-standard ICO (PIO) when solving ADCOPs with Max-sum ADVP. The first set of experiments was performed on different benchmarks that are commonly used for evaluating DCOP algorithms: uniform random, scale free networks and meeting scheduling. In each of these we first generated ADCOP instances and then, their equivalent DCOPs. The experiments on uniform problems included ADCOPs with 50 agents, each agent holding exactly one variable with ten values in its domain. Constraints were generated randomly in each experiment by selecting the probability p1 for a constraint among any pair of agents/variables. Figure 3 presents the costs of the solutions found by the five algorithms when solving problems of relatively low density (p1 = 0.2). |
| Researcher Affiliation | Academia | Roie Zivan and Tomer Parash and Yarden Naveh Industrial Engineering and Management Department Ben-Gurion University of the Negev Beer-Sheva, Israel {zivanr,parasht,navehya}@bgu.ac.il |
| Pseudocode | No | The paper describes the Max-sum algorithm using textual explanations and mathematical formulas, but it does not include a distinct pseudocode block or an algorithm box. |
| Open Source Code | No | The paper does not provide any statement or link indicating that the source code for the described methodology is publicly available. |
| Open Datasets | No | The experiments on uniform problems included ADCOPs with 50 agents, each agent holding exactly one variable with ten values in its domain. Constraints were generated randomly in each experiment by selecting the probability p1 for a constraint among any pair of agents/variables. The paper mentions using 'uniform random, scale free networks and meeting scheduling' as benchmarks, but for these, it states that ADCOP instances were 'generated randomly' or refers to concepts like 'scale free nets [Barab asi, 2003]' without providing concrete access details (links, citations to specific datasets) for public download or replication of the exact generated data. |
| Dataset Splits | No | The paper does not explicitly provide details about training, validation, or test dataset splits (e.g., percentages, sample counts, or references to predefined splits). |
| Hardware Specification | No | The paper does not provide any specific details about the hardware (e.g., GPU/CPU models, memory) used to run the experiments. |
| Software Dependencies | No | The paper does not provide specific software dependency details, such as library names with version numbers. |
| Experiment Setup | Yes | Each algorithm solved the same 50 ADCOPs and their equivalent DCOPs. The phase lengths in each of them was 100 iterations (the longest possible path in the DAG, in case the graph has a chain structure). In all the versions of Max-sum we used random personal preferences for breaking ties as suggested in [Farinelli et al., 2008]. We ran the algorithms for 5000 iterations each, to allow all algorithms to converge (if possible). The experiments on uniform problems included ADCOPs with 50 agents, each agent holding exactly one variable with ten values in its domain. Constraints were generated randomly in each experiment by selecting the probability p1 for a constraint among any pair of agents/variables. Figure 3 presents the costs of the solutions found by the five algorithms when solving problems of relatively low density (p1 = 0.2). Similar results were obtained for uniform problems with higher density (p1 = 0.6). |