Using Clustering to Strengthen Decision Diagram Bounds for Discrete Optimization
Authors: Mohsen Nafar, Michael Römer
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In a set of computational experiments with different knapsack and scheduling problems, we show that our approach generally outperforms the classical generic approach, and often achieves drastically better bounds both with respect to the size of the DD and the time used for compiling the DD. |
| Researcher Affiliation | Academia | Mohsen Nafar, Michael R omer Management Science and Business Analytics department, Bielefeld University mohsen.nafar@uni-bielefeld.de, michael.roemer@uni-bielefeld.de |
| Pseudocode | Yes | Algorithm 1: Generic Top-Down compilation algorithm |
| Open Source Code | Yes | We implemented the approach in the Julia programming language (code is available here https://github.com/mnafar/ aaai2024_clustering_DD) |
| Open Datasets | Yes | The experiments are run on 100 KP instances with 200 items per instance taken from (Pisinger 2005). All experiments are run on 10 MKP instances where each of them is a 5-dimensional MKP with 100 items (taken from (Chu and Beasley 1998), which are publicly available in ORLIBRARY at http://people.brunel.ac.uk/ mastjjb/jeb/orlib/ mknapinfo.html). The instances we ran the experiments on are from the set wt100 that is publicly available from the OR-LIBRARY (http://people.brunel.ac.uk/ mastjjb/jeb/info.html). |
| Dataset Splits | No | The paper describes using instances for computational experiments but does not specify a train/validation/test split for these instances in the typical machine learning sense. |
| Hardware Specification | Yes | We ran all the experiments on a Windows machine with processor 11th Gen Intel(R) Core(TM) i7-11800H @ 2.30GHz, 2.30 GHz and 16GB RAM. |
| Software Dependencies | No | The paper mentions 'Julia programming language' and 'the implementation of the k-means algorithm from the Clustering package in Julia' but does not provide specific version numbers for Julia or the Clustering package. |
| Experiment Setup | Yes | For the clustering part of the algorithm we use the implementation of the k-means algorithm from the Clustering package in Julia, setting the number of iterations to 50. |