The Maximum Clique Problem and Integer Programming Models, Their Modifications, Complexity and Implementation

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F23%3APU149254" target="_blank" >RIV/00216305:26210/23:PU149254 - isvavai.cz</a>

Výsledek na webu

<a href="https://www.mdpi.com/2073-8994/15/11/1979" target="_blank" >https://www.mdpi.com/2073-8994/15/11/1979</a>

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

The Maximum Clique Problem and Integer Programming Models, Their Modifications, Complexity and Implementation

Popis výsledku v původním jazyce

The maximum clique problem is a problem that takes many forms in optimization and related graph theory problems, and also has many applications. Because of its NP-completeness (nondeterministic polynomial time), the question arises of its solvability for larger instances. Instead of the traditional approaches based on the use of approximate or stochastic heuristic methods, we focus here on the use of integer programming models in the GAMS (General Algebraic Modelling System) environment, which is based on exact methods and sophisticated deterministic heuristics incorporated in it. We propose modifications of integer models, derive their time complexities and show their direct use in GAMS. GAMS makes it possible to find optimal solutions to the maximum clique problem for instances with hundreds of vertices and thousands of edges within minutes at most. For extremely large instances, good approximations of the optimum are given in a reasonable amount of time. A great advantage of this approach over all the mentioned algorithms is that even if GAMS does not find the best known solution within the chosen time limit, it displays its value at the end of the calculation as a reachable bound.

Název v anglickém jazyce

The Maximum Clique Problem and Integer Programming Models, Their Modifications, Complexity and Implementation

Popis výsledku anglicky

The maximum clique problem is a problem that takes many forms in optimization and related graph theory problems, and also has many applications. Because of its NP-completeness (nondeterministic polynomial time), the question arises of its solvability for larger instances. Instead of the traditional approaches based on the use of approximate or stochastic heuristic methods, we focus here on the use of integer programming models in the GAMS (General Algebraic Modelling System) environment, which is based on exact methods and sophisticated deterministic heuristics incorporated in it. We propose modifications of integer models, derive their time complexities and show their direct use in GAMS. GAMS makes it possible to find optimal solutions to the maximum clique problem for instances with hundreds of vertices and thousands of edges within minutes at most. For extremely large instances, good approximations of the optimum are given in a reasonable amount of time. A great advantage of this approach over all the mentioned algorithms is that even if GAMS does not find the best known solution within the chosen time limit, it displays its value at the end of the calculation as a reachable bound.

Druh

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

CEP obor

—

OECD FORD obor

10102 - Applied mathematics

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2023

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

Symmetry

ISSN

2073-8994

e-ISSN

—

Svazek periodika

15

Číslo periodika v rámci svazku

11

Stát vydavatele periodika

CH - Švýcarská konfederace

Počet stran výsledku

16

Strana od-do

1-16

Kód UT WoS článku

001118292400001

EID výsledku v databázi Scopus

2-s2.0-85178131174