Minimum Covering Sphere problem

回答済み

Mehmet Fide

2023年05月03日 15:04

Hi,

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.

0

コメント

2件のコメント

Eli Towle

Gurobi Staff

2023年05月03日 16:59
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
Mehmet Fide

2023年05月03日 20:42
Hi Eli,

This is really great, I will look at it closer.

Thank you very much,

Fide.
0

サインインしてコメントを残してください。