Elisabeth Gaar, Markus Sinnl,
"Experiments with graph convolutional networks for solving the vertex p-center problem"
, in Online-proceedings of the DSO Workshop at IJCAI, 2021
Experiments with graph convolutional networks for solving the vertex p-center problem
Sprache des Titels:
In the last few years, graph convolutional networks
(GCN) have become a popular research direction
in the machine learning community to tackle NP-
hard combinatorial optimization problems (COPs)
defined on graphs. While the obtained results are
usually still not competitive with problem-specific
solution approaches from the operations research
community, GCNs often lead to improvements
compared to previous machine learning approaches
for classical COPs such as the traveling salesperson
In this work we present a preliminary study on us-
ing GCNs for solving the vertex p-center problem
(pCP), which is another classic COP on graphs.
In particular, we investigate whether a successful
model based on end-to-end training for the TSP can
be adapted to a pCP, which is defined on a similar 2D Euclidean graph input as the usually used
version of the TSP. However, the objective of the
pCP has a min-max structure which could lead to
many symmetric optimal, i.e., ground-truth solutions and other potential difficulties for learning.
Our obtained preliminary results show that indeed
a direct transfer of network architecture ideas does
not seem to work too well. Thus we think that the
pCP could be an interesting benchmark problem for
new ideas and developments in the area of GCNs.