Ask Your Question
2

Computing polyhedron from MIP

asked 2016-06-14 14:09:09 +0100

mforets gravatar image

updated 2023-01-10 00:01:11 +0100

tmonteil gravatar image

I want to run the following code (I'm using SAGE v6.10 release version 2015-12-18):

P = MixedIntegerLinearProgram()
x = P.new_variable()
A = random_matrix(RR, 3, 2); 
P.add_constraint(A*x <= [2.1,1.5,0.4]) 
P.polyhedron()

However, it outputs the error message:

AttributeError: type object 'float' has no attribute 'fraction_field'

I noticed that if instead of using real variables I use only integer variables, then it works fine. For instance:

P = MixedIntegerLinearProgram()
x = P.new_variable()
A = random_matrix(ZZ, 3, 2); 
P.add_constraint(A*x <= [2,1,0]) 
P.polyhedron()

outputs:

A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex and 2 rays

What do you suggest to overcome this problem?

Thanks

edit retag flag offensive close merge delete

Comments

About 2 years ago (not sure which version of Sage that was), the polyhedron worked. But, it appears to be an issue now.

calc314 gravatar imagecalc314 ( 2016-06-15 15:02:58 +0100 )edit

Thanks. Anyway, I should try installing sagemath v7.2.

mforets gravatar imagemforets ( 2016-06-15 17:38:44 +0100 )edit

Adding confirmed_bug tag, and a link to trac ticket 23326.

tmonteil gravatar imagetmonteil ( 2017-06-26 13:28:51 +0100 )edit

@tmonteil : great, thanks.

mforets gravatar imagemforets ( 2017-06-26 15:42:27 +0100 )edit
1

It is fixed in 8.0

sage: P = MixedIntegerLinearProgram()
sage: x = P.new_variable()
sage: A = random_matrix(ZZ, 3, 2); 
sage: P.add_constraint(A*x <= [2,1,0]) 
sage: P.polyhedron()
A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 3 vertices
vdelecroix gravatar imagevdelecroix ( 2017-12-16 16:59:53 +0100 )edit

1 Answer

Sort by ยป oldest newest most voted
2

answered 2016-06-14 23:02:14 +0100

tmonteil gravatar image

updated 2018-09-17 21:23:22 +0100

A workaround ould be the following. Thanks to linearity, you can:

  • approximate all the real numbers by closest rational, for example QQ(1.2) results in 6/5
  • find a common denominator of each entry (using the gcd function an the denominator method for rational numbers)
  • make an integer program out of this
  • construct the polyhedron as wanted
  • rescale the polyhedron : if P is a polyhedron and q is an integer, the fraction P/q is well defined in Sage and will result into a rescaled polyhedron.

EDIT: note that with recent versions of Sage the polyhedron method works again for floating-point linear programs:

sage: P = MixedIntegerLinearProgram()
....: x = P.new_variable()
....: A = random_matrix(RR, 3, 2); 
....: P.add_constraint(A*x <= [2.1,1.5,0.4]) 
....: P.polyhedron()
....: 
A 2-dimensional polyhedron in RDF^2 defined as the convex hull of 2 vertices and 2 rays
edit flag offensive delete link more

Comments

Nice workaround!

mforets gravatar imagemforets ( 2016-06-15 17:39:13 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2016-06-14 14:09:09 +0100

Seen: 439 times

Last updated: Sep 17 '18