# The annulus problem in linear programming

I do not know if the following question is a question about Sagemath or a question about my incapacity to use MixedIntegerLinearProgram

The problem is to find the smallest annulus for a set of points. Here is a reference https://www.ti.inf.ethz.ch/ew/courses/CG12/lecture/Chapter%2011%20and%2012.pdf

# list of point
lis=[(4,1),(5,6),(2,2),(3,4),(6,3.2),(2.6,2.5),(5.8, 2.4),(2,3.4),(4.2,4),(5.6,1)]
from sage.plot.circle import Circle
# Evaluation of the norm of each point
d = [sqrt(lis[i]^2+lis[i]^2) for i in range(len(lis)-1)]
anmin = MixedIntegerLinearProgram(maximization=True, solver = "GLPK")# création du programme
nvar=len(lis)-1 # nombre de variables
x = anmin.new_variable(integer=False, indices=[0..nvar-1],nonnegative=True) # les nouvelles variables sont x ... x
anmin.set_objective(x-x)# fixe l’objectif

# Constraints
for i in range(nvar) :
anmin.add_constraint(x+ 2*(lis[i]*x+lis[i]*x), min=0, max=n(d[i]^2, digits = 2))
for i in range(nvar) :
anmin.add_constraint(x+ 2*(lis[i]*x+lis[i]*x), min=n(d[i]^2, digits = 2), max=oo)

anmin.show()
anmin.solve()
xx=anmin.get_values(x)
show(xx)


The result is obviously false. It would be great if somebody helps me find the good answer.

edit retag close merge delete