Skip to main content

LUP Student Papers

LUND UNIVERSITY LIBRARIES

Graph-Neural-Network-Based Combinatorial Optimization under Natural Language Soft Constraints

Rydén, Karl (2025)
Department of Automatic Control
Abstract
The development of 6G network management technology relies on the solution of large-scale combinatorial optimization (CO) problems on graphs. Many of these problems are NP-hard and must be solved approximately in practice. Despite decades of research and development, classical heuristics and approximation algorithms still struggle with accuracy and the computational demands of scaling to large problem instances.
Recent advances in machine learning introduce the use of generative models that are able to outperform classical solvers after being trained to maximize taskspecific reward functions on example problem instances. This reward function often has many modes, mirroring the tendency of CO problems to have multiple diverse solution... (More)
The development of 6G network management technology relies on the solution of large-scale combinatorial optimization (CO) problems on graphs. Many of these problems are NP-hard and must be solved approximately in practice. Despite decades of research and development, classical heuristics and approximation algorithms still struggle with accuracy and the computational demands of scaling to large problem instances.
Recent advances in machine learning introduce the use of generative models that are able to outperform classical solvers after being trained to maximize taskspecific reward functions on example problem instances. This reward function often has many modes, mirroring the tendency of CO problems to have multiple diverse solution candidates. In network management, one might prefer certain solutions over others and want to specify that preference in natural language rather than by redefining the CO problem.
In this thesis, we investigate the possibility of guiding one such generative solver toward desirable regions of the solution space of maximal independent set problems by incorporating soft constraints expressed in text. Although results ultimately fall short, we investigate sources of error to motivate several promising directions for future improvement. (Less)
Please use this url to cite or link to this publication:
author
Rydén, Karl
supervisor
organization
year
type
H3 - Professional qualifications (4 Years - )
subject
keywords
6G, network management, internet of things, graph combinatorial optimization, graph neural networks, generative flow networks, multi-modal learning, large language models, maximal independent set
report number
TFRT-6284
other publication id
0280-5316
language
English
id
9207177
date added to LUP
2025-06-30 10:37:00
date last changed
2025-06-30 10:37:00
@misc{9207177,
  abstract     = {{The development of 6G network management technology relies on the solution of large-scale combinatorial optimization (CO) problems on graphs. Many of these problems are NP-hard and must be solved approximately in practice. Despite decades of research and development, classical heuristics and approximation algorithms still struggle with accuracy and the computational demands of scaling to large problem instances.
 Recent advances in machine learning introduce the use of generative models that are able to outperform classical solvers after being trained to maximize taskspecific reward functions on example problem instances. This reward function often has many modes, mirroring the tendency of CO problems to have multiple diverse solution candidates. In network management, one might prefer certain solutions over others and want to specify that preference in natural language rather than by redefining the CO problem.
 In this thesis, we investigate the possibility of guiding one such generative solver toward desirable regions of the solution space of maximal independent set problems by incorporating soft constraints expressed in text. Although results ultimately fall short, we investigate sources of error to motivate several promising directions for future improvement.}},
  author       = {{Rydén, Karl}},
  language     = {{eng}},
  note         = {{Student Paper}},
  title        = {{Graph-Neural-Network-Based Combinatorial Optimization under Natural Language Soft Constraints}},
  year         = {{2025}},
}