Ask Your Question

enumerate integer points in a polytope

asked 2014-08-03 05:48:46 +0200

arunayyar gravatar image

This is a followup question to

$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 ... (more)

edit retag flag offensive close merge delete


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.

Dima gravatar imageDima ( 2014-08-03 22:42:39 +0200 )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?

arunayyar gravatar imagearunayyar ( 2014-08-13 20:54:13 +0200 )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.

Dima gravatar imageDima ( 2014-08-16 21:02:13 +0200 )edit

1 Answer

Sort by ยป oldest newest most voted

answered 2014-08-04 18:00:51 +0200

Volker Braun gravatar image

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.

edit flag offensive delete link more

Your Answer

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

Add Answer

Question Tools

1 follower


Asked: 2014-08-03 05:48:46 +0200

Seen: 463 times

Last updated: Aug 04 '14