The Maximum Clique Problem and Integer Programming Models, Their Modifications, Complexity and Implementation
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
The Maximum Clique Problem and Integer Programming Models, Their Modifications, Complexity and Implementation
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10102 - Applied mathematics
Result continuities
Project
—
Continuities
S - Specificky vyzkum na vysokych skolach
Others
Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Symmetry
ISSN
2073-8994
e-ISSN
—
Volume of the periodical
15
Issue of the periodical within the volume
11
Country of publishing house
CH - SWITZERLAND
Number of pages
16
Pages from-to
1-16
UT code for WoS article
001118292400001
EID of the result in the Scopus database
2-s2.0-85178131174