Optimsation of a linear problem with only non-negative integers

I have an optimisation problem that can be described as a simple set of linear equations in dot product form as $\mathbf{b}=\mathbf{x} \cdot A$, where vector $\mathbf{b}$ and matrix $A$ are known and vector $\mathbf{x}$ has to be estimated. Normally, this can be easily solved with linear least squares. However, both $\mathbf{b}$ and $A$ contain only non-negative integer values, and the estimated vector $\mathbf{x}$ also needs to consist only of non-negative integers.

The dimensions are $\mathbf{b} \in \Bbb{N}^{352}$, $\mathbf{x} \in \Bbb{N}^{24010}$, and $A \in \Bbb{N}^{24010 \times 352}$, where $\Bbb{N}$ also includes $0$.

The search space is rather large, which means I would rather not opt for gradient or stochastic search algorithms to find a global optimum. Is there an algebraic or statistic method to solve such optimisation problems, or am I looking for a free lunch?

• How many unknowns do you have, that is , dimension of $x$? This can be formulated as as (mixed) integer linear programming problem, or, since you mention least squares, a mixed integer quadratic programming problem. See cran.r-project.org/web/views/Optimization.html – kjetil b halvorsen Aug 8 '17 at 14:50
• The dimension of x is rather large, i.e. 24010, and may in future applications even be larger. I've tried to get an impression of (pure) integer programming, however, I am completely new to the subject. I've found some articles mentioning branch-and-cut or combinations with tabu search, any idea whether there feasible algorithms (preferably already available as python library) for a problem this size (the dimension of $b$ is 352)? A nod in the right direction would be wonderful. – Gijs Peters Aug 10 '17 at 9:59
• can you give all the dimensions? will come back – kjetil b halvorsen Aug 10 '17 at 10:24
• $\mathbf{b} \in \Bbb{N}^{352}$, $\mathbf{x} \in \Bbb{N}^{24010}$, and $A \in \Bbb{N}^{24010 \times 352}$, where $\Bbb{N}$ also includes $0$. – Gijs Peters Aug 10 '17 at 14:34
• To ask the obvious: Can you please tell us what have you tried so far? :) For example have you tried the "obvious heuristic" approach of simply solving the OLS with non-negative constraints and then discretising the solution? (BTW, the dimensions mentioned are not something mortifying - a $24K \times 352$ design matrix is nothing to write home about for a standard LS task - granted there might be some subtleties we do not know) – usεr11852 Aug 10 '17 at 21:19