Problém maximální kliky v grafu, modely celočíselného programování, jejich modifikace, složitost a implementace

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

journal article in Web of Science

en

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.

Problém maximální kliky je problém, který má mnoho podob v optimalizaci a příbuzných problémech teorie grafů a má také mnoho aplikací. Vzhledem k jeho NP-úplnosti (nedeterministický polynomiální čas) vyvstává otázka jeho řešitelnosti pro větší instance. Namísto tradičních přístupů založených na použití přibližných nebo stochastických heuristických metod se zde zaměříme na použití modelů celočíselného programování v prostředí GAMS (General Algebraic Modelling System), které je založeno na exaktních metodách a v něm začleněných sofistikovaných deterministických heuristikách. Navrhujeme modifikace celočíselných modelů, odvozujeme jejich časovou složitost a ukazujeme jejich přímé použití v systému GAMS. GAMS umožňuje nalézt optimální řešení problému maximální kliky pro instance se stovkami vrcholů a tisíci hran během maximálně několika minut. Pro extrémně velké instance jsou dobré aproximace optima dány v rozumném čase. Velkou výhodou tohoto přístupu oproti všem zmíněným algoritmům je, že i když GAMS nenajde nejlepší známé řešení ve zvoleném časovém limitu, zobrazí jeho hodnotu na konci výpočtu jako dosažitelnou hranici.

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.

klika, nezávislá množina, NP-úplný problém, celočíselné programování

clique, independent set;,GAMS, NP-complete problem, integer programming

26.10.2023

MDPI

Basel

2073-8994

15

11

1–16

16