integer programming??? I have a math problem and I would like to solve it, but I'm not sure what area to look under. 
Basically given $x \in \mathbb{R}^k$ (for my purposes, $x \in \mathbb{Q}^k$ since I am using a computer) and $L \geq 0 $, we want to find $n \in \mathbb{N}^k$ such that $n^Tx \geq L$ and $n$ is "minimal". Here minimal means that if $m^Tx \geq L$, then $|n| \leq |m|$ where $|n| = \sum_{i=1}^kn_i$. (this is not "minimal" in the traditional sense since there is no partial order due to a lack of anti-symmetry, but I couldn't think of another word to use)
So would this fall under integer programming where we want to minimize $\sum_{i=1}^kn_i$ under the constraint $\sum_{i=1}^k x_i n_i \geq L$, or would this not count as integer programming since $x \in \mathbb{R}^k$?
Anyways, does this sound familiar to anyone? I just need a direction to google. 
 A: Solutions to the equation $y^Tx\geq L$ for $y\in \mathbb{R}^k$ is a half space $H$ with the vector $Lx/(x^Tx)$ lying on the boundary, with the interior of the half space in the normal direction $x$ from there.  A difficulty in this situation is how the boundary of the half space sits with respect to the integer lattice... since you are allowing $x$ to have real coefficients, it may potentially avoid all integer points!
One approach would be to approximate $x$ by a vector of $\mathbb{Q}^k$, giving an actual integer linear program once one clears out the denominators.  Either you can do this for a sequence of better approximations and stop once the minimal solution seems good enough, or it might be possible to calculate how good of a solution one would need to guarantee the approximated half space contains exactly the same points of $\mathbb{N}^k$.  I have not read it, but this thesis appears to have quite a lot about these sorts of approximations: Vaughan Clarkson, "Approximation of Linear Forms by Lattice Points".  One keyword appears to be "simultaneous Diophantine approximation."
There is a chance that your $x$ is already in $\mathbb{Q}^k$, for instance if you are on a computer with a floating-point representation of the vector, in which case approximation might not be necessary.

I'm going to leave here my own attempt at a solution.  First of all, the $L=0$ case has the minimal solution $n=0$, so we may assume $L>0$ and then divide $x$ through by $L$ to simplify the problem to $y^Tx\geq 1$.  Let $f(n)=\sum_{i=1}^kn_i$ be your objective function, which of course is $f(n)=\mathbf{1}^Tn$ with $\mathbf{1}$ the all-ones vector.
The next observation is that we can assume $x_i>0$ for each $i$.  If not, then by taking any solution to $n^Tx\geq 1$ we can get another solution by setting $n_i$ to $0$, possibly decreasing $f(n)$ in the process, and then removing dimension $i$ from the problem.
Suppose $e\in \mathbb{R}^k_{\geq 0}$ is a vector of non-negative entries.  The inequality $n^T(x+e)\geq 1$ has all the solutions to $n^Tx\geq 1$ plus possibly some more.  Given an integer $N\geq 1$, we can form the rational approximation $x^N\in\mathbb{Q}^k_{>0}$ given by $x^N_i=\lceil Nx_i\rceil/N\geq x_i$, hence $n^Tx^N\geq 1$ has all the solutions to $n^Tx\geq 1$.
Let $i$ be such that $x_i$ is largest, and let $M=\lceil 1/x_i\rceil$.  We can see there is an $f$-minimal solution within the set $\{0,1,2,\dots,M\}^k$, since $n$ given by $n_i=M$ and $n_j=0$ for $j\neq i$ is a solution with $f(n)=M$.  So, there are at most $(M+1)^k$ solutions to consider.  Finiteness implies that there is some large enough $N$ such that $n^Tx^N\geq 1$ has the same solutions as $n^Tx\geq 1$, when restricted to $n\in \{0,1,2,\dots,M\}^k$.  In particular, the sets $S_N\subseteq \{0,1,2,\dots,M\}^k$ of solutions to $n^Tx^N\geq 1$ satisfy $S_1\supseteq S_2\supseteq S_3\supseteq\cdots$, so it must eventually stabilize.
Since $x^N_i-x_i<\frac{1}{N}$, we have for a minimal solution $n$ that
\begin{align}
n^Tx^N &= \sum_{i=1}^k n_i x_i^N\\
&< \sum_{i=1}^k n_i (x_i+\frac{1}{N}) \\
&= \sum_{i=1}^k n_i x_i + \frac{1}{N}\sum_{i=1}^k n_i \\
&= n^Tx + \frac{1}{N} f(n)\\
&\leq n^Tx + \frac{M}{N}.
\end{align}
So $n^Tx^N\geq 1$ implies $n^Tx\geq 1-\frac{M}{N}$.  This new inequality defines a half space $H_N\supset H$; letting $S'_N=H_N\cap\{0,1,2,\dots,M\}^k$, we have
$\require{AMScd}$
\begin{CD}
S_1 @>\supseteq>> S_2 @>\supseteq>>\cdots \\
@VV\subseteq V @VV\subseteq V \\
S_1' @>\supseteq>> S_2' @>\supseteq>>\cdots
\end{CD}
If we can estimate some $N$ such that $S'_N = H\cap \{0,1,2,\dots,M\}^k$, which is a point from which the bottom sequence stabilizes, then the top sequence has stabilized as well.  (Geometrically, inside of $\mathbb{R}^k_{\geq 0}$, we have that the boundary of rational approximation half space lies between the boundaries of $H$ and $H_N$.)
This is where I got stuck: we need to know some $\epsilon>0$ distance we can translate $H$ in the $-x$ direction without its boundary colliding with the integer lattice within $\mathbb{R}^k_{\geq 0}$.  Once we have such an $\epsilon$, we can calculate a sufficient $N$ and then do integer programming with the corresponding rational approximation of the inequality.
There is still an algorithm here, however.  Choose an $N$, do the corresponding integer program to get a preliminary solution $n'$.  If $n'$ does not satisfy $(n')^Tx\geq 1$, then increase $N$ to a value where $n'$ does not satisfy $(n')^Tx^N\geq 1$ and repeat.  Eventually $n'$ will be a solution to the unapproximated problem.  Since $n'$ is $f$-minimal for $n^Tx^N\geq 1$, it is $f$-minimal for $n^Tx\geq 1$ as well.  Without the $\epsilon$ estimate, though, the algorithm is merely guaranteed to terminate.
By the way, it is conceivable that there is a method that could use less-good approximations of the inequality with a smaller $N$ by somehow taking more advantage of the particular objective function.
A: It was pointed out to me that there is a much better solution than anything outlined in my other answer, though perhaps not a solution you intended.
Consider a solution $n^Tx\geq L$, and suppose that $i$ is such that $x_i\geq x_j$ for all $j$; by rearranging let us assume $i=1$.  As it was pointed out, we can assume $x_1>0$.  Then, there is a corresponding solution $n'=(\sum_i n_i,0,0,\dots,0)$ with the same value of the objective function.  Since $(\lceil L/x_1\rceil,0,0,\dots,0)$ is also a solution, we can conclude that $\lceil L/x_1\rceil$ is the minimum value for the objective function, and furthermore that $(\lceil L/x_1\rceil, 0,0,\dots,0)$ is a minimizing solution.
I'm leaving the other answer up because it might help in the case of multiple inequalities or different (linear) objective functions.
