Partial Optimality in the Linear Ordering Problem
Authors: David Stein, Bjoern Andres
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We examine the effectiveness and efficiency of these conditions and algorithms empirically, on two data sets. In this section, we analyze the algorithms defined in Section 5 empirically on two collections of instances of the linear ordering problem. |
| Researcher Affiliation | Academia | 1Faculty of Computer Science, TU Dresden, Germany 2Center for Scalable Data Analytics and AI Dresden/Leipzig. |
| Pseudocode | Yes | Algorithm 1 Seeded Component Growing |
| Open Source Code | Yes | The complete c++ code for reproducing these experiments is provided in Stein (2024). URL https://github.com/ dsteindd/partial-optimality-in-thelinear-ordering-problem. |
| Open Datasets | Yes | Next, we consider the instances of the classes IO, Spec and SGB from LOLIB (Mart ı et al., 2012). |
| Dataset Splits | No | The paper mentions using synthetic instances and LOLIB benchmark datasets, but does not provide specific details on training, validation, or test splits (percentages, counts, or explicit standard split citations for their usage in this paper). |
| Hardware Specification | Yes | All experiments are conducted on a single core of a Ryzen 9 7900X equipped with 64 GB of RAM. |
| Software Dependencies | Yes | using the state-of-the-art integer programming software Gurobi (Gurobi Optimization, LLC, 2023). In our code, we solve these by means of a c++ implementation of the push-relabel algorithm of Goldberg & Tarjan (1988). |
| Experiment Setup | Yes | For a systematic study, we synthesize instances of the linear ordering problem with |A| between 5 and 200, w.r.t. a given order < on A, and w.r.t. a parameter α [0, 1]. Costs cab of pairs ab are drawn from two normal distributions with means 1 + α and 1 α and standard deviation σ = 0.2, depending on whether a < b or b < a. |