Implementation continuous p-median problem

Support
1

Good day,

I’m using amplpy and planning to solve the attached continuous problem in 3D. Could someone give me some hints as to the modelling? I’m planning to solve this using SNOPT and randomly generated starting points in a cube.

N_o = N_d fyi, one could just use N instead of two different sets.

Thank you very much in advance!!

Screenshot 18.12.2025 um 13.04.35 PM
Screenshot 18.12.2025 um 13.04.35 PM920×450 11.3 KB

1 Like
2

Some more information will be helpful here:

  • Is it correct to assume that X_j are the decision variables of this problem, and that w_i and D are parameters of the problem?
  • You mention a “continuous problem” with “starting points in a cube.” Does this imply that the X_j are continuous, and that they are constrained by 0 \leq X_j \leq 1?
  • What is the meaning of d_i(X_j)? Specifically, given the value for X_j, how would the value of d_i(X_j) be determined?
1 Like
3

Hello,

  • X_j is the decision variable, w_i and D are fixed beforehand
  • yes, I was trying to say that the locations for X_j can be chosen in the cube freely (continuous)
  • d_i(X_j) is supposed to be the Euclidian distance between the points N and the locations X_j

Please see the model I have implemented this far:

set J;
set I;

param xc{i in I};
param yc{i in I};
param zc{i in I};
param w{i in I};

param D;

var x{j in J} >= 0, <= 1;
var y{j in J} >= 0, <= 1;
var z{j in J} >= 0, <= 1;

minimize objective: sum{i in I} w[i] * min{j in J} sqrt((x[j]-xc[i])^2 + (y[j]-yc[i])^2 + (z[j]-zc[i])^2);

subject to mindistance{i in I, j in J}: sqrt((x[j]-xc[i])^2 + (y[j]-yc[i])^2 + (z[j]-zc[i])^2) >= D;

Please let me know if this would work, or if you need more information.

Thank you!!

4

Your AMPL model is valid. The SNOPT solver is designed for functions that are smooth (having all derivatives continuous), which \rm min is definitely not. However, in a few tests on small random data (|{\rm I}| = 20 and |{\rm J}| = 5) and random starting points, SNOPT ran to completion (local optimality) without reporting any errors, and returned what looked to me like reasonable solutions.

So, it appears you can use this AMPL model with SNOPT to search for good solutions. Of course, it’s always a good idea to take a close look at some of the solutions, to be sure that your model is a correct formulation of the problem that you want to solve.