Integer Programming Approach to Graph Colouring Problem and Its Implementation in GAMS

Kód výsledku v IS VaVaI

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

Výsledek na webu

<a href="https://wseas.com/journals/systems/2023/b085102-033(2023).pdf" target="_blank" >https://wseas.com/journals/systems/2023/b085102-033(2023).pdf</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.37394/23202.2023.22.53" target="_blank" >10.37394/23202.2023.22.53</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Integer Programming Approach to Graph Colouring Problem and Its Implementation in GAMS

Popis výsledku v původním jazyce

The graph colouring problem is one of the most studied combinatorial optimisation problems, one with many applications, e. g., in timetabling, resource assignment, team-building problems, network analysis, and cartography. Because of its NP-hardness, 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 direct use of an integer programming model in the GAMS environment. This environment makes it possible to solve instances much larger than in the past. Neither does it require complex parameter settings or statistical evaluation of the results as in the case of stochastic heuristics because the computational core of software tools, nested in GAMS, is deterministic in nature.

Název v anglickém jazyce

Integer Programming Approach to Graph Colouring Problem and Its Implementation in GAMS

Popis výsledku anglicky

The graph colouring problem is one of the most studied combinatorial optimisation problems, one with many applications, e. g., in timetabling, resource assignment, team-building problems, network analysis, and cartography. Because of its NP-hardness, 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 direct use of an integer programming model in the GAMS environment. This environment makes it possible to solve instances much larger than in the past. Neither does it require complex parameter settings or statistical evaluation of the results as in the case of stochastic heuristics because the computational core of software tools, nested in GAMS, is deterministic in nature.

Druh

J_SC - Článek v periodiku v databázi SCOPUS

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

WSEAS Transactions on Systems

ISSN

1790-2769

e-ISSN

—

Svazek periodika

22

Číslo periodika v rámci svazku

May

Stát vydavatele periodika

GR - Řecká republika

Počet stran výsledku

6

Strana od-do

532-537

Kód UT WoS článku

—

EID výsledku v databázi Scopus

2-s2.0-85164618622