avoid using maxima simplex algo in lattice_polytope

[fchapoton]

currently we are using maxima through pexpect in lattice_plytope

let us instead go through the generic MILP setting

CC: @rwst

Component: geometry

Author: Frédéric Chapoton

Branch/Commit: 0c20221

Reviewer: Matthias Koeppe

Issue created by migration from https://trac.sagemath.org/ticket/20766

[fchapoton]

New commits:

c954f72

avoid using maxima linear programming in lattice polytopes

[fchapoton]

Branch: u/chapoton/20766

[fchapoton]

Commit: c954f72

[sagetrac-git]

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

d3a0a1b

trac 20766 remove try except

[sagetrac-git]

Changed commit from c954f72 to d3a0a1b

[sagetrac-git]

Changed commit from d3a0a1b to b922d16

[sagetrac-git]

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

b922d16

trac 20766 correcting the code

[sagetrac-git]

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

76cc74d

trac 20766 removing maxima imports and specific functions

[sagetrac-git]

Changed commit from b922d16 to 76cc74d

[fchapoton]

comment:5

ok, ready for review

[mkoeppe]

comment:6

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.

[sagetrac-git]

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

4ce5bce

trac 20766 using base_ring=QQ

[sagetrac-git]

Changed commit from 76cc74d to 4ce5bce

[fchapoton]

comment:8

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.

[mkoeppe]

comment:9

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.

[fchapoton]

comment:10

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 ?

[mkoeppe]

comment:11

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.

[sagetrac-git]

Changed commit from 4ce5bce to 4b5be03

[sagetrac-git]

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

4b5be03

trac 20766 using continuous variables

[sagetrac-git]

Changed commit from 4b5be03 to 702134c

[sagetrac-git]

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

702134c

trac 20766 using integer=False

[fchapoton]

comment:14

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

[mkoeppe]

comment:15

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.

[sagetrac-git]

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

0c20221

trac 20766 removed casting to ZZ (plus added a future import)

[sagetrac-git]

Changed commit from 702134c to 0c20221

[fchapoton]

comment:18

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.

[fchapoton]

comment:19

patchbot is green

[fchapoton]

comment:20

ping ?

[mkoeppe]

Reviewer: Matthias Koeppe

[mkoeppe]

comment:21

Looks good now.

[vbraun]

Changed branch from u/chapoton/20766 to 0c20221