Solving Hard Stable Matching Problems via Local Search and Cooperative Parallelization
Authors: Danny Munera, Daniel Diaz, Salvador Abreu, Francesca Rossi, Vijay Saraswat, Philippe Codognet
AAAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We address this problem using a local search technique, based on Adaptive Search and present experimental evidence that this approach is much more efficient than state-of-the-art exact and approximate methods. Moreover, parallel versions (particularly versions with communication) improve performance so much that very large and hard instances can be solved quickly. |
| Researcher Affiliation | Collaboration | Danny Munera University Paris 1/CRI danny.munera@malix.univ-paris1.fr Daniel Diaz University Paris 1/CRI daniel.diaz@univ-paris1.fr Salvador Abreu University of Evora/CENTRIA/CRI spa@di.uevora.pt Francesca Rossi University of Padova/Harvard University frossi@math.unipd.it Vijay Saraswat IBM TJ Watson Research Center vsaraswa@us.ibm.com Philippe Codognet JFLI-CNRS/UPMC University of Tokyo codognet@is.s.u-tokyo.ac.jp |
| Pseudocode | Yes | Algorithm 1: Function to compute BP error, Algorithm 2: Function to evaluate a marriage, Algorithm 3: Reset procedure to escape local minima. |
| Open Source Code | Yes | Both the source code and problem instances are available at http://cri-hpc1.univ-paris1.fr/smti/ |
| Open Datasets | Yes | For the evaluation, we used the random problem generator described in (Gent and Prosser 2002) which takes three parameters: the size (n), the probability of incompleteness (p1) and the probability of ties (p2). |
| Dataset Splits | No | The paper describes generating problem instances for evaluation ('For each (p1, p2) pair, we solved 100 instances and averaged the results'), but it does not specify explicit train/validation/test dataset splits as typically found in machine learning contexts. |
| Hardware Specification | Yes | All parallel experiments have been carried out on a cluster of 16 machines, each with 4 16core AMD Opteron 6376 CPUs running at 2.3 GHz and 128 GB of RAM. The nodes are interconnected with Infini Band FDR 4 (i.e. 56 GBPS.) |
| Software Dependencies | No | The paper states that its implementation uses 'X10' and compares against 'Mc Dermid's method (MD)' and the 'Chaff solver' for SAT, but it does not provide specific version numbers for these software components. |
| Experiment Setup | Yes | The best settings were found to be R = 50, U = 100 ( U /R = 2 being the best ratio), |EP| = 4 and p Adopt = 1. |