Opened 2 years ago

Closed 2 years ago

#23326 closed defect (fixed)

Polyhedron from inexact MIP is broken

Reported by: mforets Owned by:
Priority: major Milestone: sage-8.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) 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 2 years ago by mforets

  • Branch set to u/mforets/23326
  • Commit set to 9dc381e2d05944b6aacd25c1b481584c7bae8f4b

two obvious ways would be:

  • in MIP's def polyhedron, cast the floats to RDF before passing to Polyhedron constructor
  • in def Polyhedra at parent.py, add checks like .. is RDF or float

i tried the second one; it works with this ticket but it triggers other things :

File "src/sage/numerical/mip.pyx", line 669, in sage.numerical.mip.MixedIntegerLinearProgram.base_ring
Failed example:
    d = polytopes.dodecahedron()

so it doesn't seem to be a good idea.


New commits:

9dc381eadd doctest in mip

comment:2 Changed 2 years ago by mforets

  • Component changed from PLEASE CHANGE to numerical

comment:3 Changed 2 years ago by dimpase

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 2 years ago by tmonteil

  • Branch changed from u/mforets/23326 to u/tmonteil/23326

comment:5 Changed 2 years ago by tmonteil

  • 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 non-predictive: 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 non-integral Python float entries.

comment:6 Changed 2 years ago by dimpase

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 follow-up: Changed 2 years ago by 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

comment:8 in reply to: ↑ 7 Changed 2 years ago by mforets

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 2 years ago by mforets

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 2 years ago by mforets

  • Dependencies set to #22605

comment:11 Changed 2 years ago by mforets

  • 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:

83bf93223345: conversions from Fraction to Rational
ce7fb2523345: make it faster
e238c9eaddress reviewer's comments
e80700aMerge branch 't/23345/23345' into t/22605/22605
6be64b1fix docstring for int
128235econvert UCF and QQbar to AA in permutahedron
579e33ftransform to QQ ring for reflection groups
6f6d0f3fix behaviour with QQbar and simplify it
af03de8fix indentation issue, and simplify
1c604ddMerge branch 't/22605/22605' into t/mforets/23326

comment:12 Changed 2 years ago by mforets

  • Authors set to Marcelo Forets, Thierry Monteil

.. filling the authors field

comment:13 Changed 2 years ago by mforets

  • Milestone changed from sage-8.0 to sage-8.1

comment:14 Changed 2 years ago by vdelecroix

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 2 years ago by mforets

is it the same as git checkout t/mforets/23326 followed by a git merge develop?

comment:16 follow-up: Changed 2 years ago by vdelecroix

No. Just do

$ git checkout t/mforets/23326
$ git reset --hard develop      # reset the branch on top of develop
$ git cherry-pick `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 2 years ago by git

  • Commit changed from 1c604ddcbe70c131c1b55eabb47befa87a3c477d to 0f60749043b0d1b809456890e433f6a44eddf313

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

0f60749add doctest in mip

comment:18 in reply to: ↑ 16 Changed 2 years ago by mforets

great! that worked, thanks.

comment:19 Changed 2 years ago by vdelecroix

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to positive_review

comment:20 Changed 2 years ago by vbraun

  • Branch changed from u/mforets/23326 to 0f60749043b0d1b809456890e433f6a44eddf313
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.