Ask Your Question
1

Computing polyhedron from MIP

asked 2016-06-14 07:09:09 -0500

mforets gravatar image

updated 2017-06-26 06:27:58 -0500

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 08:02:58 -0500 )edit

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

mforets gravatar imagemforets ( 2016-06-15 10:38:44 -0500 )edit

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

tmonteil gravatar imagetmonteil ( 2017-06-26 06:28:51 -0500 )edit

@tmonteil : great, thanks.

mforets gravatar imagemforets ( 2017-06-26 08:42:27 -0500 )edit

1 answer

Sort by ยป oldest newest most voted
0

answered 2016-06-14 16:02:14 -0500

tmonteil gravatar image

updated 2016-06-14 16:04:07 -0500

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 flag offensive delete link more

Comments

Nice workaround!

mforets gravatar imagemforets ( 2016-06-15 10:39:13 -0500 )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 07:09:09 -0500

Seen: 51 times

Last updated: Jun 14 '16