J 2019

Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions: A Survey

GANIAN, Robert and Sebastian ORDYNIAK

Basic information

Original name

Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions: A Survey

Authors

GANIAN, Robert (203 Czech Republic, guarantor, belonging to the institution) and Sebastian ORDYNIAK (276 Germany)

Edition

Algorithms, 2019, 1999-4893

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Switzerland

Confidentiality degree

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

References:

RIV identification code

RIV/00216224:14330/19:00113717

Organization unit

Faculty of Informatics

DOI

UT WoS

000505741500004

Keywords in English

Parameterized Complexity
Změněno: 14/5/2020 10:41, Mgr. Michal Petr

Abstract

V originále

Integer Linear Programming (ILP) is among the most successful and general paradigms for solving computationally intractable optimization problems in computer science. ILP is NP-complete, and until recently we have lacked a systematic study of the complexity of ILP through the lens of variable-constraint interactions. This changed drastically in recent years thanks to a series of results that together lay out a detailed complexity landscape for the problem centered around the structure of graphical representations of instances. The aim of this survey is to summarize these recent developments, put them into context and a unified format, and make them more approachable for experts from many diverse backgrounds.