TAU_P_CENTER
------------

This C code can be used in order to optimally solve the discrete version of
the P-center problem, where the set of demand points and the set of
potential service points are the same.

The code is based on the algorithm described in "Relaxation Method for
the Solution of the Minimax Location-Allocation Problem in Euclidean
Space", by R. Chen and G. Y. Handler, Naval Research Logistics, Volume 34,
pages 775-788, 1987.

The algorithm for Set Covering is based on "Set Covering and Involutory
bases", by M. Bellmore and H. D. Ratliff, Management Science, vol. 18,
pages 194-206, 1971.

HOW TO RUN THIS PROGRAM
-----------------------

The straightforward way of running this program is:

   > ./relax filename number_of_service_points

For instance:

   > ./relax distances.txt 3

The text file which is given as the first parameter should be constructed
as follows: It should begin with n, the number of demand points /
potential service points. The rest of the file contains n*n floating point
numbers representing the distances between any two demand points.

THE OUTPUT STRUCTURE
--------------------

The algorithm we use is iterative. At each step we output the value of
candidate solution (until the optimal solution is reached). If you would
like the indices of the candidate solution to be printed at each step, you
need to change the first line of the makefile to:

   OPTS = -DVERBOSE -O3 -Wall -Werror

before compiling the program.

MORE OPTIONS
------------

If you run:

   > ./relax distances.txt 3 40

this means that you want to find 3 service points, and your original upper
bound for the best solution is 40 (rather than infinity).

Running:
   > ./relax distances.txt 3 40 5
means that in addition, whenever you give up on a choice of a relaxation
subproblem, you want your new subproblem to start with 5 demand points (the
default is 4).

Running:
   > ./relax distances.txt 3 40 5 200
means that in addition, you want to give up on a subproblem after you add
200 new constraints (the default is 50). My intuition tells me that a
smaller value (10-50) is good when you are looking for a better guess, and a
greater value (200-1000) is better when you want to prove that your current
guess is optimal.

Running:
   > ./relax distances.txt 3 40 5 200 1
means that you want to solve the 3 service point problem by first solving
the problem for 1 (and then 2) service points.

Finally:
   > ./relax distances.txt 3 40 5 200 1 345834
means you want to use a different seed (345834). The seed affects the random
choice of relaxation subproblems.