Opened 6 years ago

Closed 6 years ago

#20766 closed enhancement (fixed)

avoid using maxima simplex algo in lattice_polytope

Reported by: chapoton Owned by:
Priority: major Milestone: sage-7.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:

Status badges

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 chapoton

  • Branch set to u/chapoton/20766
  • Commit set to c954f72d1122987151294c2ff92e917b97cde1bc

New commits:

​c954f72avoid using maxima linear programming in lattice polytopes

comment:2 Changed 6 years ago by git

  • Commit changed from c954f72d1122987151294c2ff92e917b97cde1bc to d3a0a1b2c663c396f49871c1ebf0d6199302feb1

Branch pushed to git repo; I updated commit sha1. New commits:

​d3a0a1btrac 20766 remove try except

comment:3 Changed 6 years ago by git

  • Commit changed from d3a0a1b2c663c396f49871c1ebf0d6199302feb1 to b922d16ad3c2563d4224220e504d83c2d11e58fb

Branch pushed to git repo; I updated commit sha1. New commits:

​b922d16trac 20766 correcting the code

comment:4 Changed 6 years ago by git

  • Commit changed from b922d16ad3c2563d4224220e504d83c2d11e58fb to 76cc74d9506298b9db06067fcaf98d86a2e8963b

Branch pushed to git repo; I updated commit sha1. New commits:

​76cc74dtrac 20766 removing maxima imports and specific functions

comment:5 Changed 6 years ago by chapoton

  • Cc rws added
  • Status changed from new to needs_review

ok, ready for review

comment:6 follow-up: Changed 6 years ago by mkoeppe

  • 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 6 years ago by git

  • Commit changed from 76cc74d9506298b9db06067fcaf98d86a2e8963b to 4ce5bce3fd6118832305a6efa90a81f4605ee2e2

Branch pushed to git repo; I updated commit sha1. New commits:

​4ce5bcetrac 20766 using base_ring=QQ

comment:8 in reply to: ↑ 6 Changed 6 years ago by chapoton

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 6 years ago by mkoeppe

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 6 years ago by chapoton

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 6 years ago by mkoeppe

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 6 years ago by git

  • Commit changed from 4ce5bce3fd6118832305a6efa90a81f4605ee2e2 to 4b5be0381886ea21142be12dbcad2be2976ba916

Branch pushed to git repo; I updated commit sha1. New commits:

​4b5be03trac 20766 using continuous variables

comment:13 Changed 6 years ago by git

  • Commit changed from 4b5be0381886ea21142be12dbcad2be2976ba916 to 702134c3c9a152a679ee40a4a073d7fb6c31da23

Branch pushed to git repo; I updated commit sha1. New commits:

​702134ctrac 20766 using integer=False

comment:14 Changed 6 years ago by chapoton

  • Status changed from needs_work to needs_review

ok, thanks for your patience. It should be good now.

comment:15 Changed 6 years ago by mkoeppe 

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 6 years ago by mkoeppe

  • Status changed from needs_review to needs_work

comment:17 Changed 6 years ago by git

  • Commit changed from 702134c3c9a152a679ee40a4a073d7fb6c31da23 to 0c20221d9fe08c14fc4254100a8d0334f49fbebd

Branch pushed to git repo; I updated commit sha1. New commits:

​0c20221trac 20766 removed casting to ZZ (plus added a future import)

comment:18 Changed 6 years ago by chapoton

  • 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 6 years ago by chapoton

patchbot is green

comment:20 Changed 6 years ago by chapoton

ping ?

comment:21 Changed 6 years ago by mkoeppe

  • Reviewers set to Matthias Koeppe
  • Status changed from needs_review to positive_review

Looks good now.

comment:22 Changed 6 years ago by vbraun

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