Going Beyond Primal Treewidth for (M)ILP
Authors: Robert Ganian, Sebastian Ordyniak, M. Ramanujan
AAAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main contribution is the introduction and algorithmic exploitation of two new decompositional parameters for ILP and MILP. The first, torso-width, is specifically tailored to the linear programming setting and is the first decompositional parameter which can also be used for MILP. The latter, incidence treewidth, is a concept which originates from boolean satisfiability but has not yet been used in the ILP setting; here we obtain a full complexity landscape mapping the precise conditions under which incidence treewidth can be used to obtain efficient algorithms. Both of these parameters overcome previous shortcomings of primal treewidth for ILP in unique ways, and consequently push the frontiers of tractability for these important problems. |
| Researcher Affiliation | Academia | Robert Ganian, Sebastian Ordyniak, M. S. Ramanujan Algorithms and Complexity group, TU Wien, Vienna, Austria ({ganian,ordyniak, ramanujan}@ac.tuwien.ac.at) |
| Pseudocode | No | The paper describes algorithms verbally and through mathematical proofs (e.g., 'Sketch of Proof' for Theorem 3 and Lemma 7), but does not include any explicitly labeled pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not contain any statements about making its source code publicly available or links to a code repository. |
| Open Datasets | No | The paper focuses on theoretical algorithm design and complexity analysis for MILP/ILP problems and does not describe experiments that would involve training on specific datasets. Therefore, no information about publicly available training datasets is provided. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments with dataset splits, including validation splits. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm design and complexity. It does not describe any experimental setup that would require hardware specifications. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithm design and complexity. It does not describe any experimental setup that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and complexity analysis. It does not describe any experimental setup details such as hyperparameters or training configurations. |