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

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
Integer Programming Approach to Graph Colouring Problem and Its Implementation in GAMS
Original language description
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.
Czech name
—
Czech description
—

Type
J<sub>SC</sub> - Article in a specialist periodical, which is included in the SCOPUS database
CEP classification
—
OECD FORD branch
10102 - Applied mathematics

Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)