Ask Your Question

# enumerate integer points in a polytope

This is a followup question to http://ask.sagemath.org/question/2366...

$A$ is a $5 \times 19$ matrix. $S=${-1,0,1}. As suggessted in the solution I compute integral points within a polytope. I have the following code:

eq3=[ (0,6,10,10,6,6,6,3,3,0,3,21,21,0,0,3,3,3,3,3), (0,12,16,15,13,13,14,7,7,2,8,27,27,1,2,7,7,5,4,6), (0,6,13,10,9,9,12,6,6,4,10,14,14,0,1,7,7,6,3,3), (0,0,5,5,0,0,0,0,0,0,0,7,7,0,0,0,0,0,0,0), (0,0,3,2,1,1,2,1,1,1,2,2,2,0,0,1,1,1,0,0)];

ineq3=[ (-lb,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),(ub,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), (-lb,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),(ub,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), (-lb,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),(ub,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), (-lb,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),(ub,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0), (-lb,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0),(ub,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0), (-lb,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0),(ub,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0), (-lb,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0),(ub,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0), (-lb,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0),(ub,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0), (-lb,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0),(ub,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0 ...

edit retag close merge delete

## Comments

it just can be that the number of points you want to enumerate is too big... What you might to is to fix some coordinates to particular values, say to 0, and see how this will go. This would split the computation into parts.

( 2014-08-03 15:42:39 -0500 )edit

You are right. It took one full day for the code to finish running. It gave about 75500 vectors. I found that the problem has another constraint. I am only looking for integer vectors that belong to $S$ and have 4 or less non-zero elements. But $\sum_{i=1}^n |x_i| \leq 4$ is a convex constraint. Polyhedron seems to take only linear equality and inequality constraints.. Is there a way to add the L_1 norm constraint?

( 2014-08-13 13:54:13 -0500 )edit

$\ell_1$-norm constraint can be replaced by a bunch of linear inequalities, in an obvious way. More precisely, you will need $2^n$ inequalities.

( 2014-08-16 14:02:13 -0500 )edit

## 1 answer

Sort by ยป oldest newest most voted

This is probably out of reach for any "generic" point counting:

sage: p
A 14-dimensional polyhedron in QQ^19 defined as the convex hull of 144716 vertices


You can probably use the specifics of your problem since its just a limited range in each variable. E.g. try to find a solution mod 3 and then try to lift it to ZZ.

more

## Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

## Stats

Asked: 2014-08-02 22:48:46 -0500

Seen: 123 times

Last updated: Aug 04 '14