Solution of the P-Centre problem


August 13, 2012

Solution of the P-Centre problem

Project for Operational Research II course. The assigned  project  required a solution obtained through column generation.

The p-centre problem, or minimax location-allocation problem in location theory terminology, is the following: given n demand points on the plane and a weight associated with each demand point, find p new facilities on the plane that minimize the maximum weighted Euclidean distance between each demand point and its closest new facility.

The soultion developed was split in 2 parts:

  • a C++ program which implemented the Dijkstra algorithm and generated random graphs formatted for CPLEX
  • a IMB ILO CPLEX model
The final report about the P-Centre problem was changed into a report about the new IMB ILO object oriented sintax for future use as a documented example on professor’s demand.
Here’s the PCENTRI code and the final report Relazione OPL (italian).