Chebyshev center¶

Find the center and radius of the smallest sphere that encloses the polyhedron defined by the inequalities $$\left\{ 2 x - y + 2 z \le 2,\quad -x + 2 y + 4 z \le 16,\quad x + 2 y - 2 z \le 8,\quad x \ge 0,\, y \ge 0,\, z \ge 0 \right\}$$

In [1]:
A = [2 -1 2; -1 2 4; 1 2 -2; -1 0 0; 0 -1 0; 0 0 -1];
b = [2; 16; 8; 0; 0; 0]

using JuMP, Clp

m = Model(solver=ClpSolver())
@variable(m, r >= 0)           # radius
@variable(m, x[1:3])           # coordinates of center
for i = 1:size(A,1)
@constraint(m, A[i,:]'*x + r*norm(A[i,:]) <= b[i])
end
@objective(m, Max, r)     # maximize radius

status = solve(m)
center = getvalue(x)

Optimal