Computing one interior lattice points of possibly unbounded polytopes

Questions and problems about using polymake go here.
ren
Posts: 38
Joined: 03 May 2011, 15:21

Computing one interior lattice points of possibly unbounded polytopes

Postby ren » 09 Mar 2020, 16:58

Sorry for the possibly stupid question, but is there a fast way to compute a single interior lattice point of a possibly unbounded polyhedron in polymake? Preferably of small (ideally minimal) L1-norm.

I know that I can
1. make it bounded by intersecting it with a dilated cube,
2. enumerate all interior lattice points using ->INTERIOR_LATTICE_POINTS,
but that can take quite some time in high ambient dimension and if the bound is not chosen wisely.

For example, the following code is trying to find an interior point of $lsc33, which yields a plane tropical curve of bi-degree (3,3) dual to a honeycomb subdivision with prescribed edge lengths.

Code: Select all

application "fan"; $M33 = new Matrix([[1,0,0],[1,1,0],[1,2,0],[1,3,0], [1,0,1],[1,1,1],[1,2,1],[1,3,1], [1,0,2],[1,1,2],[1,2,2],[1,3,2], [1,0,3],[1,1,3],[1,2,3],[1,3,3]]); $C33 = new Array<Set<Int>>([[0,1,4],[1,2,5],[2,3,6], [1,4,5],[2,5,6],[3,6,7], [4,5,8],[5,6,9],[6,7,10], [5,8,9],[6,9,10],[7,10,11], [8,9,12],[9,10,13],[10,11,14], [9,12,13],[10,13,14],[11,14,15]]); $HC33 = new SubdivisionOfPoints(POINTS=>$M33, MAXIMAL_CELLS=>$C33); # honeycomb $sc33 = $HC33->secondary_cone(); $Rh = zero_vector($sc33->N_RAYS)|$sc33->RAYS; $Rh = unit_vector($Rh->cols,0)/$Rh; $Lh = zero_vector($sc33->LINEALITY_DIM)|$sc33->LINEALITY_SPACE; $sc33 = new Polytope(POINTS=>$Rh, INPUT_LINEALITY=>$Lh); # homogenized sc33 $l = new Matrix([[1, 0, 0,-1, 0, 0, 1, 1, 0, 0,-1, 0, 0, 0, 0, 0, 0], [3, 0, 0, 0, 0, 0, 1,-1, 0,-1, 1, 0, 0, 0, 0, 0, 0], [5, 0, 0, 0, 0, 0,-1, 1, 0, 0, 1,-1, 0, 0, 0, 0, 0], [2, 0, 0, 0, 0, 0, 0,-1, 0, 0, 1, 1, 0, 0,-1, 0, 0], [6, 0, 0, 0, 0, 0, 0, 1,-1, 0,-1, 1, 0, 0, 0, 0, 0]]); $L = new Polytope(INEQUALITIES=>[], EQUATIONS=>$l); # encodes fixed edge lengths $lsc33 = intersection($sc33,$L); $bsc33 = intersection($lsc33,scale(Polytope::cube($lsc33->AMBIENT_DIM),9)); print $bsc33->N_INTERIOR_LATTICE_POINTS;

User avatar
joswig
Main Author
Posts: 279
Joined: 24 Dec 2010, 11:10

Re: Computing one interior lattice points of possibly unbounded polytopes

Postby joswig » 09 Mar 2020, 17:36

polymake 4.0 comes with a new function which solves your very problem!

Code: Select all

fan > print $HC33->MIN_WEIGHTS; polymake: used package scip SCIP - Solving Constraint Integer Programs SCIP is a solver for Mixed Integer Linear and Nonlinear Problems that allows for an easy integration of arbitrary constraints. https://scip.zib.de/index.php 5 2 1 2 2 0 0 2 1 0 1 4 2 2 4 8
As you can see this requires SCIP to be configured.

ren
Posts: 38
Joined: 03 May 2011, 15:21

Re: Computing one interior lattice points of possibly unbounded polytopes

Postby ren » 09 Mar 2020, 17:44

That is wonderful! This will be so incredibly useful when trying to get easiest possible lifts!!!

But is this also available for polytopes? Because I am not looking for any lift of a given subdivision, but one whose dual tropical curve T has edges of certain prescribed lengths. (This is because we want to look at algebraic curves which tropical to T and our chosen edge lengths will make studying them much easier)

User avatar
joswig
Main Author
Posts: 279
Joined: 24 Dec 2010, 11:10

Re: Computing one interior lattice points of possibly unbounded polytopes

Postby joswig » 09 Mar 2020, 18:02

Via SCIP (and tosimplex) polymake can solve arbitrary (mixed) integer linear programs.
Please look at the code for MIN_WEIGHTS in apps/fan/rules/subdivision.rules for an example which you can modify to your needs.


Return to “Helpdesk”