Going Beyond Primal Treewidth for {(M)ILP}

D 2017

Going Beyond Primal Treewidth for {(M)ILP}

GANIAN, Robert, M.S. RAMANUJAN a Sebastian ORDYNIAK

Základní údaje

Originální název

Going Beyond Primal Treewidth for {(M)ILP}

Autoři

GANIAN, Robert (203 Česká republika, garant, domácí), M.S. RAMANUJAN (356 Indie) a Sebastian ORDYNIAK (40 Rakousko)

Vydání

USA, Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA, od s. 815-821, 7 s. 2017

Nakladatel

AAAI

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10200 1.2 Computer and information sciences

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Odkazy

URL

Kód RIV

RIV/00216224:14330/17:00100547

Organizační jednotka

Fakulta informatiky

ISBN

978-1-57735-781-0

ISSN

UT WoS

000485630700114

Klíčová slova anglicky

primal treewidth; ILP

Štítky

core_A, firank_1

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 1. 6. 2022 12:43, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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.

Citovat

GANIAN, Robert, M.S. RAMANUJAN a 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, s. 815-821. ISBN 978-1-57735-781-0.

@inproceedings{1414038,
   author = {Ganian, Robert and Ramanujan, M.S. and Ordyniak, Sebastian},
   address = {USA},
   booktitle = {Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA},
   editor = {Satinder P. Singh; Shaul Markovitch},
   keywords = {primal treewidth; ILP},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {USA},
   isbn = {978-1-57735-781-0},
   pages = {815-821},
   publisher = {AAAI},
   title = {Going Beyond Primal Treewidth for {(M)ILP}},
   url = {https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14272},
   year = {2017}
}

TY  - JOUR
ID  - 1414038
AU  - Ganian, Robert - Ramanujan, M.S. - Ordyniak, Sebastian
PY  - 2017
TI  - Going Beyond Primal Treewidth for {(M)ILP}
PB  - AAAI
CY  - USA
SN  - 9781577357810
KW  - primal treewidth
KW  - ILP
UR  - https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14272
N2  - 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.
ER  -

GANIAN, Robert, M.S. RAMANUJAN a Sebastian ORDYNIAK. Going Beyond Primal Treewidth for $\{$(M)ILP$\}$. Online. In Satinder P. Singh; Shaul Markovitch. \textit{Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA}. USA: AAAI, 2017, s.~815-821. ISBN~978-1-57735-781-0.

Podrobný výpis o publikaci