Obtaining the combinations of a vector array to satisfy lineal constrains.

1 view (last 30 days)
Bernardo Castro Valerio
Bernardo Castro Valerio on 27 May 2022
I am trying to figure out if there is a way to obtain all the integer combinations of elements in a vector array that follows lineal constrains such as: A*x=b. Where 0<=x<=9 and A is a matrix of [n X a] and x is a column vectors of n length and b is a column vetor of a length. A , b and a are all constant in all iterations. For example such that it creates the following equations.
Thank you.

Answers (2)

John D'Errico
John D'Errico on 27 May 2022
Edited: John D'Errico on 27 May 2022
Is it possible? Of course. Exhaustive enumeration. Just try all combinations, saving those that work. Is that easy? OF COURSE NOT! Is it even doable in some circumstances? Of course not, if the size of the problem happens to be large enough. You give no information at all about the actual size of your problem, which always is a hint that your real problem will be unreasonably large.
Is it possible to find ONE solution of the problem? Trivial, as long as you understand how to formulate this as an integer inear programming problem, so just a call to intlinprog. If a solution exists, it will find one. But not all. And you cannot tell intlinprog to return all solutions, or even more than one solution.
For example, consider the following simple problem.
A = 1:100;
b = 1000;
So now your problem reduces to finding ALL sets of solutions as integer partitions of the number 1000, such that they are sums of the integers 1:100, where no element enters into the sum more than 9 times (since you said that 0<=x<=9.) I would guess there are a whole pile of such solutions. And if it turns out that problem is doable in a finite amount of time on your computer, just make it a little larger, and it won't be. And that has only one linear equality constraint. Things will be more complicated if there are multiple such constraints.
If you really expect good help, then you need to promise that your problem is MUCH smaller, and even then accept that the only viable solution may be exhaustive enumeration in some form. For example, my own code, partitions (found on the FEX for free download) can solve that simple problem in theory. It uses recursive calls to search for all solutions, but still effectively exhaustive enumeration. And that code cannot handle the more general problem where you have more than one equality constraint.
Could I write a code that uses intlinprog to find ONE solution, then search for a next solution, based on the nullspace of A? Well yes, I probably could do so. With some effort and care about the numerical analysis, one could write a code that could effectively search through the set of all solutions. It would take some effort to write and to do it well. Doing all of this in floating point double precision arithmetic would carry its own nasty problems too. UGH. Depending on your vaguely specified problem, it might be easier to just write an exhaustive search code using a tool like ndgrid or the equivalent.

Sign in to comment.

Bruno Luong
Bruno Luong on 27 May 2022
See this thread (14 year ago) with simlar question, the technique using gcd can help to reduce the search




Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by