Detail publikačního výsledku

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

ŠEDA, M.

Originální název

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

Anglický název

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

Druh

Článek Scopus

Originální abstrakt

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.

Anglický abstrakt

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.

Klíčová slova

graph colouring, independent set, NP-hard problem, integer programming, GAMS

Klíčová slova v angličtině

graph colouring, independent set, NP-hard problem, integer programming, GAMS

Autoři

ŠEDA, M.

Rok RIV

2024

Vydáno

31.05.2023

Nakladatel

WSEAS

ISSN

1790-2769

Svazek

22

Číslo

May

Strany od

532

Strany do

537

Strany počet

6

URL

https://wseas.com/journals/systems/2023/b085102-033(2023).pdf

Plný text v Digitální knihovně

http://hdl.handle.net/11012/213661

BibTex

@article{BUT183950,
  author="Miloš {Šeda}",
  title="Integer Programming Approach to Graph Colouring Problem and Its Implementation in GAMS",
  year="2023",
  volume="22",
  number="May",
  pages="532--537",
  doi="10.37394/23202.2023.22.53",
  url="https://wseas.com/journals/systems/2023/b085102-033(2023).pdf"
}

Dokumenty

b085102-033(2023)