Opened 3 years ago

Last modified 3 years ago

#19365 needs_info defect

Bug in lattice_polytope.positive_integer_relations

Reported by: tmonteil Owned by:
Priority: major Milestone: sage-6.10
Component: geometry Keywords:
Cc: vdelecroix, chapoton, mkoeppe, rws Merged in:
Authors: Vincent Delecroix Reviewers: Andrey Novoseltsev, Thierry Monteil
Report Upstream: N/A Work issues:
Branch: public/19365 (Commits) Commit: 651684a41026bee07a49be83b238b059e72693bc
Dependencies: Stopgaps:

Description (last modified by vdelecroix)

Reported on this ask question:

sage: vertices = [(1,1,-1,-1,-1),(-1,-1,1,1,-1),(1,-1,-1,-1,1),(-1,1,1,1,1),(1,-1,1,-1,-1)]
sage: p = LatticePolytope(vertices)
sage: lattice_polytope.positive_integer_relations(p.vertices().column_matrix())
TypeError: unable to make sense of Maxima expression '"Problemnotfeasible!"' in Sage

Note that there is a non-negative nontrivial integer relation:

sage: p.vertices().column_matrix().right_kernel()
Free module of degree 5 and rank 1 over Integer Ring
Echelon basis matrix:
[1 1 1 1 0]

Change History (13)

comment:1 Changed 3 years ago by kcrisman

See also #19367, which however I think is, if not orthogonal, at least not spanned by this question.

comment:2 Changed 3 years ago by vdelecroix

  • Cc vdelecroix added
  • Description modified (diff)
  • Milestone changed from sage-6.9 to sage-6.10

... changed a missing ) in the description...

comment:3 Changed 3 years ago by vdelecroix

  • Authors set to Vincent Delecroix
  • Branch set to public/19365
  • Commit set to 6f9c08689431553677b73a19f1319add1470af5c
  • Status changed from new to needs_review

Simple solution.


New commits:

6f9c086Trac 19365: fix positive_integer_relations

comment:4 follow-up: Changed 3 years ago by kcrisman

-        if x.str() == r'?Problem\not\feasible\!':
-            raise ValueError("cannot find required relations")

Why wasn't this triggered in the old code?

I suggest you run some timing on this code too, and see what it reports when there isn't a relation, etc. I wonder why this non-generic code was used?

comment:5 in reply to: ↑ 4 Changed 3 years ago by vdelecroix

Replying to kcrisman:

-        if x.str() == r'?Problem\not\feasible\!':
-            raise ValueError("cannot find required relations")

Why wasn't this triggered in the old code?

I suggest you run some timing on this code too, and see what it reports when there isn't a relation, etc. I wonder why this non-generic code was used?

Timing against what? The old code crashes on most examples...

comment:6 follow-up: Changed 3 years ago by novoselt

  • Status changed from needs_review to needs_work

The new version obviously has a different return type.

There is also some helper Maxima method that can be removed if it is not used anymore.

Timings against the old code are indeed irrelevant - that was just something that I managed to get into a working code back when I was young ;-)

comment:7 Changed 3 years ago by git

  • Commit changed from 6f9c08689431553677b73a19f1319add1470af5c to 651684a41026bee07a49be83b238b059e72693bc

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

51e2751Trac 19365: fix return type
651684aTrac 19365: deprecate sage->maxima helper

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

  • Status changed from needs_work to needs_review

Replying to novoselt:

The new version obviously has a different return type.

Right. Fixed.

There is also some helper Maxima method that can be removed if it is not used anymore.

Right. Deprecated.

comment:9 Changed 3 years ago by novoselt

  • Reviewers set to Andrey Novoseltsev
  • Status changed from needs_review to positive_review

comment:10 Changed 3 years ago by tmonteil

  • Reviewers changed from Andrey Novoseltsev to Andrey Novoseltsev, Thierry Monteil
  • Status changed from positive_review to needs_work

The example provided in the doc is:

      sage: points = [(1,1,-1,-1,-1), (-1,-1,1,1,-1), (1,-1,-1,-1,1),
      ....:           (-1,1,1,1,1), (1,-1,1,-1,-1)]
      sage: positive_integer_relations(points)
      [(1, 0, 0, 1, 0)]

Could you explain how (1,1,-1,-1,-1) + (-1,1,1,1,1) == 0 ?

The result should be [(1, 1, 1, 1, 0)], see the ask question for the expected answer.

Given a list of tuples, is it more natural to interpret it as a list of vectors, or as a list of rows of a matrix whose columns are vectors ? We might argue that the doc says that the points "are given as columns of a matrix". But when the doc writes points = [(1,1,-1,-1,-1), (-1,-1,1,1,-1), (1,-1,-1,-1,1), (-1,1,1,1,1), (1,-1,1,-1,-1)], should the user consider this as a natural way to define the vectors [(1, -1, 1, -1, 1), (1, -1, -1, 1, -1), (-1, 1, -1, 1, 1), (-1, 1, -1, 1, -1), (-1, -1, 1, 1, -1)] ?

It could be even worse if the user explicitely writes points = [vector([1,1,-1,-1,-1]), vector([-1,-1,1,1,-1]), vector([1,-1,-1,-1,1]), vector([-1,1,1,1,1]), vector([1,-1,1,-1,-1])] so that no ambiguity appears on her side, but the first line of the code M = matrix(points), silently forgot all this information.

comment:11 Changed 3 years ago by novoselt

Good point. The old code would break right away on anything but the matrix and it looked at first as a good idea to have matrix constructor built in, but apparently it is not. I agree that both input and output formats of this function are not the best possible ones, but that's what it has been for ages (like since 2006/7), so let's keep it. Those who want to use this function have to do the conversion or write a new one and deprecate this one.

Interestingly, it is not used anywhere in Sage (I thought that somewhere in toric code it may be handy) but I am pretty sure I used it at some point in my worksheets.

comment:12 Changed 3 years ago by mkoeppe

  • Cc chapoton mkoeppe added

This method was changed in #20766. Dup?

comment:13 Changed 3 years ago by mkoeppe

  • Cc rws added
  • Status changed from needs_work to needs_info

After #20766, the example in the description gives:

sage: vertices = [(1,1,-1,-1,-1),(-1,-1,1,1,-1),(1,-1,-1,-1,1),(-1,1,1,1,1),(1,-1,1,-1,-1)]
sage: p = LatticePolytope(vertices)
sage: lattice_polytope.positive_integer_relations(p.vertices().column_matrix())
MIPSolverException: PPL : There is no feasible solution
Note: See TracTickets for help on using tickets.