# 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

## 1 Answer

I think (tell me if I'm wrong) that the aim of transforming your optimisation problem into solving a linear system equation is precisely simplifying the problem. One can solve a linear system, this is pure algebra whereas solving an optimization problem is quite more difficult in the sense that this is less obvious to check if a solution works.

Thus why don't you just consider linear system equation algorithms solvers such as :

Gauss, Cholesky, Jacobi, gradient methods or even probabilistic methods ?

PS : I know this is not a suitable answer for the policy of the website, this is a real question, not a suggestion, and I would have put it as a comment but I can't.

• Thanks. In essence, the problem can be described as a linear without simplifications or concessions. The only problem is that the parameter estimations should be non-negative integers, and I would like to know if there is a least squares variation that can solve this; calculating gradients or jacobians would be very expensive. – Gijs Peters Aug 8 '17 at 14:15
• Oh I see now, my mistake, the algorithms I mentionned would certainly not give you non-negative integers. That's my fault, even if I read carefuly, this was still not enough carefuly. – ThanhKim Aug 11 '17 at 7:40