I'm looking at a problem I believe is combinatorial. Find all possible solutions $\mathbf{x}$ to: $$\mathbf{a} = [a_1, a_2, ..., a_n], a_k \in \mathbb{N^+}$$ $$\mathbf{l} = [l_1, l_2, ..., l_n], l_k \in \mathbb{N}$$ $$\sum a_k \cdot x_k = B, x_k \le l_k, x_k \in \mathbb{N}$$
$\mathbf{a}$, $\mathbf{l}$ (limit) and $B$ are given constants.
A few trivial examples would be:
Example 1) $$\mathbf{a}=[2, 3, 5, 7], \mathbf{l}=[2,1,0,1]$$ $B=15$ gives no solutions, $\mathbf{x} \in []$
$B=10$ gives 1 solution, $\mathbf{x} \in [[0,1,0,1]]$
$B=5$ gives 1 solution, $\mathbf{x} \in [[1,1,0,0]]$
Example 2) $$\mathbf{a}=[2, 3, 5, 7], \mathbf{l}=[3,3,3,3]$$ $B=15$ gives 4 solutions, $\mathbf{x} \in [[0, 0, 3, 0], [0, 1, 1, 1], [1, 1, 2, 0], [3, 3, 0, 0]]$
$B=10$ gives 3 solutions, $\mathbf{x} \in [[0, 0, 2, 0], [1, 1, 1, 0], [2, 2, 0, 0]]$
$B=5$ gives 2 solutions, $\mathbf{x} \in [[1,1,0,0], [0,0,1,0]]$
NOTE: I solved above equations by hand so please keep it in mind in case I missed something. In the examples $\mathbf{a}$ contains the 4 first entries from the prime numbers. This is not a feature of the problem but just to give an example. The numbers are however unique in $\mathbf{a}$ but it could equally well be: $\mathbf{a}=[1,2,7,10,22], \mathbf{l}=[...], B=123$
In the problem domain where I want to apply this the dimensionality of $\mathbf{a}$ will be around 25-30 or so, but it is the same formulation of the problem as above.
Does anyone know if efficient solver(s) exists for this, or do I have to roll my own?
