MoN15: Fifteenth Mathematics of Networks meeting
Jamie Fairbrother (Lancaster) – A network-based integer program for PCI assignment
We have a large number of radio devices, which can be viewed as points in the plane. Each device must be assigned to one of 504 “Physical Cell Identifiers” or PCIs. Two neighbouring devices must not have the same PCI. Moreover, if the PCIs of two neighbouring cells are the same modulo 3 or modulo 6, this can cause interference.
A required feature of the solution to this problem is that it must be distributed. The aim of this work is to benchmark the distributed algorithm, which is typically heuristic in nature. To this end, we formulate this assignment as an integer program on an appropriately defined network of devices. The resultant problem is NP-hard and so to solve this problem for moderately sized instances, we deploy an aggressive preprocessing technique in combination with a multi-layered cutting plane algorithm.
Contact:
Keith Briggs
(
)
or
Richard G. Clegg (richard@richardclegg.org)