Opened 6 years ago
Closed 5 years ago
#20766 closed enhancement (fixed)
avoid using maxima simplex algo in lattice_polytope
Reported by:  chapoton  Owned by:  

Priority:  major  Milestone:  sage7.3 
Component:  geometry  Keywords:  
Cc:  rws  Merged in:  
Authors:  Frédéric Chapoton  Reviewers:  Matthias Koeppe 
Report Upstream:  N/A  Work issues:  
Branch:  0c20221 (Commits, GitHub, GitLab)  Commit:  0c20221d9fe08c14fc4254100a8d0334f49fbebd 
Dependencies:  Stopgaps: 
Description
currently we are using maxima through pexpect in lattice_plytope
let us instead go through the generic MILP setting
Change History (22)
comment:1 Changed 6 years ago by
 Branch set to u/chapoton/20766
 Commit set to c954f72d1122987151294c2ff92e917b97cde1bc
comment:2 Changed 6 years ago by
 Commit changed from c954f72d1122987151294c2ff92e917b97cde1bc to d3a0a1b2c663c396f49871c1ebf0d6199302feb1
Branch pushed to git repo; I updated commit sha1. New commits:
d3a0a1b  trac 20766 remove try except

comment:3 Changed 6 years ago by
 Commit changed from d3a0a1b2c663c396f49871c1ebf0d6199302feb1 to b922d16ad3c2563d4224220e504d83c2d11e58fb
Branch pushed to git repo; I updated commit sha1. New commits:
b922d16  trac 20766 correcting the code

comment:4 Changed 6 years ago by
 Commit changed from b922d16ad3c2563d4224220e504d83c2d11e58fb to 76cc74d9506298b9db06067fcaf98d86a2e8963b
Branch pushed to git repo; I updated commit sha1. New commits:
76cc74d  trac 20766 removing maxima imports and specific functions

comment:5 Changed 6 years ago by
 Cc rws added
 Status changed from new to needs_review
ok, ready for review
comment:6 followup: ↓ 8 Changed 5 years ago by
 Status changed from needs_review to needs_work
Should use an LP for this, not an IP.
Also, since input is exact, consider requesting an exact LP solver by using base_ring=QQ
when you set up the MixedIntegerLinearProgram
.
comment:7 Changed 5 years ago by
 Commit changed from 76cc74d9506298b9db06067fcaf98d86a2e8963b to 4ce5bce3fd6118832305a6efa90a81f4605ee2e2
Branch pushed to git repo; I updated commit sha1. New commits:
4ce5bce  trac 20766 using base_ring=QQ

comment:8 in reply to: ↑ 6 Changed 5 years ago by
Replying to mkoeppe:
Should use an LP for this, not an IP.
Not sure what you mean. So far, I have not thought about what this is doing, but only on how to redo what that there before without using maxima.
If you have precise suggestions, please make them as explicit as possible.
comment:9 Changed 5 years ago by
The old code, using Maxima, calls the simplex method to solve an LP.
Your code uses new_variable(integer=True, ...)
to solve an IP.
There's a fundamental difference between an LP and and IP.
comment:10 Changed 5 years ago by
ok, please pardon my dumb ignorance, but what does IP stands for ? LP is for linear program, right ?
Are you saying that I should use something else than MILP ? If so, what ?
comment:11 Changed 5 years ago by
LP = Linear Program = all variables real (continuous) I(L)P = Integer (Linear) Program = all variables integer MI(L)P = Mixed Integer (Linear) Program = some variables integer, some variables real.
I'm saying that you should use new_variable
with continuous=True
if you want to imitate whatever it was that the Maxima simplex algorithm did.
comment:12 Changed 5 years ago by
 Commit changed from 4ce5bce3fd6118832305a6efa90a81f4605ee2e2 to 4b5be0381886ea21142be12dbcad2be2976ba916
Branch pushed to git repo; I updated commit sha1. New commits:
4b5be03  trac 20766 using continuous variables

comment:13 Changed 5 years ago by
 Commit changed from 4b5be0381886ea21142be12dbcad2be2976ba916 to 702134c3c9a152a679ee40a4a073d7fb6c31da23
Branch pushed to git repo; I updated commit sha1. New commits:
702134c  trac 20766 using integer=False

comment:14 Changed 5 years ago by
 Status changed from needs_work to needs_review
ok, thanks for your patience. It should be good now.
comment:15 Changed 5 years ago by
x = [ZZ(k) for k in MIP.get_values(w).values()[:n]]
I think the results will be rational, can't just coerce to ZZ
.
comment:16 Changed 5 years ago by
 Status changed from needs_review to needs_work
comment:17 Changed 5 years ago by
 Commit changed from 702134c3c9a152a679ee40a4a073d7fb6c31da23 to 0c20221d9fe08c14fc4254100a8d0334f49fbebd
Branch pushed to git repo; I updated commit sha1. New commits:
0c20221  trac 20766 removed casting to ZZ (plus added a future import)

comment:18 Changed 5 years ago by
 Status changed from needs_work to needs_review
I removed the cast to ZZ.
And also I added from __future__ import absolute_import
, to help transition to py3.
All the imports in the file are ready for this, so this is safe.
comment:19 Changed 5 years ago by
patchbot is green
comment:20 Changed 5 years ago by
ping ?
comment:21 Changed 5 years ago by
 Reviewers set to Matthias Koeppe
 Status changed from needs_review to positive_review
Looks good now.
comment:22 Changed 5 years ago by
 Branch changed from u/chapoton/20766 to 0c20221d9fe08c14fc4254100a8d0334f49fbebd
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
avoid using maxima linear programming in lattice polytopes