Minimum Covering Sphere problem
AnsweredHi,
I have n-dimensional vectors, each called points in R^n space. (Lets call them ai, i from 1 to m)
I want to find minimal n-sphere which covers all those points.
Let scalar S be the square of the radius of a sphere centered at point X in R^n.
I want to find S and X which minimizes S, s.t. S >= (ai-X)'(ai-X), i = 1..m where ' means transpose.
In my problem, m=200 and n=21.
Can Gurobi solve this kind of problem?
Thank you,
Fide.
-
Official comment
This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support. -
Yes, Gurobi can solve this problem. In Python, the most straightforward implementation uses Gurobi's matrix-friendly interface. Here is some example Python code:
import gurobipy as gp
from gurobipy import GRB
import numpy as np
m = 200
n = 21
# Generate m random vectors in [0,ub]^n
ub = 10
a = ub * np.random.rand(m, n)
model = gp.Model()
s = model.addMVar(shape=(1,), name="s")
x = model.addMVar(shape=(n,), ub=ub, name="x")
for i in range(m):
model.addConstr(s >= (x - a[i]) @ (x - a[i]), name=f"cover[{i}]")
model.setObjective(s, GRB.MINIMIZE)
model.optimize()
print("s^2 =", s.X)
print("x =", x.X)This problem has a \(m\) second-order cone constraints, which sometimes poses numerical challenges for solvers. If Gurobi encounters numerical issues while solving, you could try playing with parameters like NumericFocus and BarHomogeneous. Setting PreDual to 1 (\(\texttt{model.params.PreDual = 1}\)) seems to work well for this problem.
For additional matrix-friendly Python API examples, see matrix1.py and matrix2.py.
1 -
Hi Eli,
This is really great, I will look at it closer.
Thank you very much,
Fide.
0
Post is closed for comments.
Comments
3 comments