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

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F19%3A00113717" target="_blank" >RIV/00216224:14330/19:00113717 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.23638/LMCS-15(1:7)2019" target="_blank" >https://doi.org/10.23638/LMCS-15(1:7)2019</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.3390/A12120248" target="_blank" >10.3390/A12120248</a>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2019

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Algorithms

ISSN

1999-4893

e-ISSN

—

Svazek periodika

12

Číslo periodika v rámci svazku

12

Stát vydavatele periodika

CH - Švýcarská konfederace

Počet stran výsledku

14

Strana od-do

1-14

Kód UT WoS článku

000505741500004

EID výsledku v databázi Scopus

2-s2.0-85079682148