Let an integer vector be *nice* when it has only two nonzero components, which sum to zero. So (0, 0, 3, 0, -3) and (-1, 0, 1, 0, 0) are examples of nice vectors in $n=5$ dimensions.

Call a lattice *nice* if it is of the form $\mathbb{Z}$-span({$v_1, v_2, \dotsc, v_m$}), where all $v_i$ are nice. (Note: the $v_i$ are not necessarily linearly independent so $m$ could be larger than the dimension; although WOLOG $m \le \tbinom{n}{2}$.)

Is the following decision problem in P?

- INPUT: a nice lattice and a vector $x \in \mathbb{Z}^n$
- QUESTION: does the lattice contain a $y$ such that $y_i \ge x_i$ for all $i=1, \dotsc, n$?

Motivation and background:

- in general lattices, the problem is NP-complete (via the unbounded knapsack problem)
- if this problem lies in P, one can solve an interesting more general problem

A possibly interesting partial result would be to demonstrate any useful structure for nice lattices!

(I posted a flow formulation of the problem on cstheory)