forum.polymake.org

Posted: **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;

Posted: **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.

Posted: **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)

Posted: **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.

forum.polymake.org

Computing one interior lattice points of possibly unbounded polytopes

Computing one interior lattice points of possibly unbounded polytopes

Re: Computing one interior lattice points of possibly unbounded polytopes

Re: Computing one interior lattice points of possibly unbounded polytopes

Re: Computing one interior lattice points of possibly unbounded polytopes