GANIAN, Robert, M.S. RAMANUJAN and Sebastian ORDYNIAK. Going Beyond Primal Treewidth for {(M)ILP}. Online. In Satinder P. Singh; Shaul Markovitch. Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA. USA: AAAI, 2017, p. 815-821. ISBN 978-1-57735-781-0.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Going Beyond Primal Treewidth for {(M)ILP}
Authors GANIAN, Robert (203 Czech Republic, guarantor, belonging to the institution), M.S. RAMANUJAN (356 India) and Sebastian ORDYNIAK (40 Austria).
Edition USA, Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA, p. 815-821, 7 pp. 2017.
Publisher AAAI
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10200 1.2 Computer and information sciences
Country of publisher United States of America
Confidentiality degree is not subject to a state or trade secret
Publication form electronic version available online
WWW URL
RIV identification code RIV/00216224:14330/17:00100547
Organization unit Faculty of Informatics
ISBN 978-1-57735-781-0
ISSN 2374-3468
UT WoS 000485630700114
Keywords in English primal treewidth; ILP
Tags core_A, firank_1
Tags International impact, Reviewed
Changed by Changed by: RNDr. Pavel Šmerk, Ph.D., učo 3880. Changed: 1/6/2022 12:43.
Abstract
Integer Linear Programming (ILP) and its mixed variant (MILP) are archetypical examples of NP-complete optimization problems which have a wide range of applications in various areas of artificial intelligence. However, we still lack a thorough understanding of which structural restrictions make these problems tractable. Here we focus on structure captured via so-called decompositional parameters, which have been highly successful in fields such as boolean satisfiability and constraint satisfaction but have not yet reached their full potential in the ILP setting. In particular, primal treewidth (an established decompositional parameter) can only be algorithmically exploited to solve ILP under restricted circumstances. 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.
PrintDisplayed: 19/9/2024 02:16