The annulus problem in linear programming

asked 2019-12-01 16:58:04 +0100

Cyrille gravatar image

updated 2023-05-19 21:58:58 +0100

FrédéricC gravatar image

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][0]^2+lis[i][1]^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[0] ... x[3]
anmin.set_objective(x[0]-x[1])# fixe l’objectif

# Constraints
for i in range(nvar) :
    anmin.add_constraint(x[0]+ 2*(lis[i][0]*x[2]+lis[i][1]*x[3]), min=0, max=n(d[i]^2, digits = 2)) 
for i in range(nvar) :
    anmin.add_constraint(x[1]+ 2*(lis[i][0]*x[2]+lis[i][1]*x[3]), 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 flag offensive close merge delete

Comments

Can you draw a picture to show the solution is wrong? Also can you try different algorithms? Also you can directly use scipy to solve the problem.

ablmf gravatar imageablmf ( 2019-12-11 23:46:09 +0100 )edit