Elisabeth Gaar

Elisabeth Gaar, Sara Joosten, Markus Sinnl

In this work, we introduce and study the $p$-$α$-closest-center problem ($pα$CCP), which generalizes the $p$-second-center problem, a recently emerged variant of the classical $p$-center problem. In the $pα$CCP, we are given sets of customers and potential facility locations, distances between each customer and potential facility location as well as two integers $p$ and $α$. The goal is to open facilities at $p$ of the potential facility locations, such that the maximum $α$-distance between each customer and the open facilities is minimized. The $α$-distance of a customer is defined as the sum of distances from the customer to its $α$ closest open facilities. If $α$ is one, the $pα$CCP is the $p$-center problem, and for $α$ being two, the $p$-second-center problem is obtained, for which the only existing algorithm in literature is a variable neighborhood search (VNS). We present four mixed-integer programming (MIP) formulations for the $pα$CCP, strengthen them by adding valid and optimality-preserving inequalities and conduct a polyhedral study to prove relationships between their linear programming relaxations. Moreover, we present iterative procedures for lifting some valid inequalities to improve initial lower bounds on the optimal objective function value of the $pα$CCP and characterize the best lower bounds obtainable by this iterative lifting approach. Based on our theoretical findings, we develop a branch-and-cut algorithm (B&C) to solve the $pα$CCP exactly. We improve its performance by a starting and a primal heuristic, variable fixings and separating inequalities. In our computational study, we investigate the effect of the various ingredients of our B&C on benchmark instances from related literature. Our B&C is able to prove optimality for 17 of the 40 instances from the work on the VNS heuristic.

Elisabeth Gaar, Markus Sinnl

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 problem (TSP). In this work we present a preliminary study on using 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.