Opened 4 years ago
Closed 4 years ago
#23326 closed defect (fixed)
Polyhedron from inexact MIP is broken
Reported by:  mforets  Owned by:  

Priority:  major  Milestone:  sage8.1 
Component:  numerical  Keywords:  optimization, polyhedron 
Cc:  dimpase, mkoeppe  Merged in:  
Authors:  Marcelo Forets, Thierry Monteil  Reviewers:  Vincent Delecroix 
Report Upstream:  N/A  Work issues:  
Branch:  0f60749 (Commits, GitHub, GitLab)  Commit:  0f60749043b0d1b809456890e433f6a44eddf313 
Dependencies:  #22605  Stopgaps: 
Description
Creating a polyhedron
defined by a MixedIntegerLinearProgram
seems to be broken if the MIP's base ring is real double field; it raises AttributeError: type object 'float' has no attribute 'is_exact'
.
Reported in ask.sage.
Change History (20)
comment:1 Changed 4 years ago by
 Branch set to u/mforets/23326
 Commit set to 9dc381e2d05944b6aacd25c1b481584c7bae8f4b
comment:2 Changed 4 years ago by
 Component changed from PLEASE CHANGE to numerical
comment:3 Changed 4 years ago by
I think one of the bugs is here, line 707 of sage/rings/real_double.pyx
.
self._value = float(x)
Indeed, float()
is Python float, it's not RDF
.
More bugs(?) like this are in MixedIntegerLinearProgram
, where float
is used for no good reason, IMHO.
comment:4 Changed 4 years ago by
 Branch changed from u/mforets/23326 to u/tmonteil/23326
comment:5 Changed 4 years ago by
 Commit changed from 9dc381e2d05944b6aacd25c1b481584c7bae8f4b to c4b7a619fca34156d50e2ec66d8258c50b8ad283
I just suggested a fix to be discussed (based upon Marcelo's branch), i guess it is consistent with the current logic of both the Polyhedron
constructor and MILP
behaviour.
That said, there are two things i do not like with those logics:
Regarding the Polyhedron
constructor, (part of) the current logic is: if the ring of all the entries is one of ZZ
, QQ
, RDF
, then make it the base ring, otherwise, try to turn the entries into integers (if it succeeds, then the base ring is ZZ
or QQ
), otherwise the base ring is RDF
. In particular, if the entries are Python floats corresponding to integers, then the base ring will be ZZ
or QQ
. But if the entries are RDF
elements corresponding to integers, then the base ring will be RDF
. It also makes something nonpredictive: imagine that the user wants to construct tons of float polytopes, but one of them has integer entries for no good reason, its base ring will be different than the others polytopes.
Regarding MILP
, constraints are considered as floats, whatever the type of constraints defined by the user. I do understand that solvers might require that, but if MILP
is built from integer or rational entries, it should remind about that and postprocess the output of the solvers to be consistent with the user input.
Also, both "features" are linked so that the current mixture works (i.e. if the MILP is made of integer entries, then it will lead to a rational polytope), but i do not find it very secure: the MILP outputs floats even if it knows that the polytope is rational, then the polyhedron constructor guesses that the polytope has to be rational. Again, what happens when the user defines a float MILP, and that by some rounding coincidence, it turns out that the constraints are integers ?
New commits:
c4b7a61  #23326 : allow constructing polyhedra from nonintegral Python float entries.

comment:6 Changed 4 years ago by
Practically speaking, if one wants to study the polyhedron of an (MI)LP, then an appropriate (MI)LP backend should should be used: e.g. for rational inequalities one should use ppl
backend, which does exact computations over QQ
, and so the polyhedron constructed will be over QQ
; there is also a backend that understands exact algebraic numbers, etc.
Constructing an LP over floats/RDF and then investigating the underlying polyhedron is obviously not a very safe undertaking.
comment:7 followup: ↓ 8 Changed 4 years ago by
Hi Marcelo, Thierry,
Did you have a look at #22605? Of course it breaks some doctests in MIP but the polyhedron constructor gets much better.
Vincent
comment:8 in reply to: ↑ 7 Changed 4 years ago by
Replying to vdelecroix:
Hi Marcelo, Thierry,
Did you have a look at #22605? Of course it breaks some doctests in MIP but the polyhedron constructor gets much better.
Vincent
Thanks for pointing it out. I've pulled and tried #22605. Indeed, that fixes this ticket but MIP's polyhedra
existent doctests now fail because it always returns RDF polyhedra.
So I understand that the thing to be fixed here is some processing at MIP's polyhedron
as suggested in Thierry's comment:5
comment:9 Changed 4 years ago by
Then if #22605 gets in, here we can just adapt the backend, p = MixedIntegerLinearProgram(solver='ppl')
, in the doctests that involve rationals, while keeping the one i added with solver='GLPK'
. Does it make sense?
comment:10 Changed 4 years ago by
 Dependencies set to #22605
comment:11 Changed 4 years ago by
 Branch changed from u/tmonteil/23326 to u/mforets/23326
 Commit changed from c4b7a619fca34156d50e2ec66d8258c50b8ad283 to 1c604ddcbe70c131c1b55eabb47befa87a3c477d
 Status changed from new to needs_review
Last 10 new commits:
83bf932  23345: conversions from Fraction to Rational

ce7fb25  23345: make it faster

e238c9e  address reviewer's comments

e80700a  Merge branch 't/23345/23345' into t/22605/22605

6be64b1  fix docstring for int

128235e  convert UCF and QQbar to AA in permutahedron

579e33f  transform to QQ ring for reflection groups

6f6d0f3  fix behaviour with QQbar and simplify it

af03de8  fix indentation issue, and simplify

1c604dd  Merge branch 't/22605/22605' into t/mforets/23326

comment:13 Changed 4 years ago by
 Milestone changed from sage8.0 to sage8.1
comment:14 Changed 4 years ago by
Would be simpler and cleaner to just rebase your 5 lines commit on the latest beta (8.1.beta3) which contains #22605.
comment:15 Changed 4 years ago by
is it the same as git checkout t/mforets/23326
followed by a git merge develop
?
comment:16 followup: ↓ 18 Changed 4 years ago by
No. Just do
$ git checkout t/mforets/23326 $ git reset hard develop # reset the branch on top of develop $ git cherrypick `9dc381e` # just pick the one commit needed
An additional merge introduces plenty of complications.
After that you will need to force push on the trac server. That is provide the option f
$ git push trac f HEAD:u/mforets/23326
comment:17 Changed 4 years ago by
 Commit changed from 1c604ddcbe70c131c1b55eabb47befa87a3c477d to 0f60749043b0d1b809456890e433f6a44eddf313
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
0f60749  add doctest in mip

comment:18 in reply to: ↑ 16 Changed 4 years ago by
great! that worked, thanks.
comment:19 Changed 4 years ago by
 Reviewers set to Vincent Delecroix
 Status changed from needs_review to positive_review
comment:20 Changed 4 years ago by
 Branch changed from u/mforets/23326 to 0f60749043b0d1b809456890e433f6a44eddf313
 Resolution set to fixed
 Status changed from positive_review to closed
two obvious ways would be:
def polyhedron
, cast the floats to RDF before passing toPolyhedron
constructordef Polyhedra
atparent.py
, add checks like.. is RDF or float
i tried the second one; it works with this ticket but it triggers other things :
so it doesn't seem to be a good idea.
New commits:
add doctest in mip