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).