I have a system of under-determined linear equations Ax = b (i.e. more unknowns than equations) that I would like so solve in matlab.
I know that this would usually mean an infinite number of solutions, but I also know the solutions should be positive integers and less than a certain number. Can I find all the solutions that meet those additional requirements?
This problem come from having an unknown matrix where I know the sum of each row and column.
e.g. unknown matrix to find
0 3 2 0
0 2 4 1
2 1 0 0
Row sums known
5
7
3
Column Sums know
2 6 6 1
I've tried the lsqnonneg(A,b) function which gives only one valid solution
0 0 5 0
0 6 0 1
2 0 1 0
percusse :
What you have is often called integer-linear programming and it is known to be NP-hard (which means don't hold your breath until a solution comes out). \n\nIf you want to solve it without the integerness, you have a linear program and hence can use linprog. If you think of your unknown matrix as vector of unknown entries then column sum is just \n\ncol_sum = kron(eye(4),[1,1,1]);\n\ncol_sum =\n\n 1 1 1 0 0 0 0 0 0 0 0 0\n 0 0 0 1 1 1 0 0 0 0 0 0\n 0 0 0 0 0 0 1 1 1 0 0 0\n 0 0 0 0 0 0 0 0 0 1 1 1\n\n\nSimilarly, row sum is \n\nrow_sum = repmat(eye(3),1,4);\n\nrow_sum =\n\n 1 0 0 1 0 0 1 0 0 1 0 0\n 0 1 0 0 1 0 0 1 0 0 1 0\n 0 0 1 0 0 1 0 0 1 0 0 1\n\n\nThese are your equality constraints also you have the inequality constraints but only to bound the unknown values. linprog can bound them as extra arguments. However you don't have an objective function which you can make up something like sum of all unknowns minimized or one of them or any other linear objective would do or you can leave it empty and you get any feasible result. \n\nAeq = [col_sum;row_sum]\nbeq = [2 6 6 1 5 7 3]';\n\nX = linprog([],[],[],Aeq,beq,zeros(12,1),10*ones(12,1))% 0 <= vars <= 10\n\nX = reshape(X,3,4)\n\nX =\n\n 0.6550 2.0160 2.0160 0.3130\n 1.1192 2.5982 2.5982 0.6845\n 0.2258 1.3859 1.3859 0.0025\n\n\n>> sum(X,1)\n\nans =\n\n 2.0000 6.0000 6.0000 1.0000\n\n>> sum(X,2)\n\nans =\n\n 5.0000\n 7.0000\n 3.0000\n\n\nIf you have certain entries that are guaranteed to be zero etc. Then it might be possible that all solutions are forced to be integers. Otherwise you need to have nonconvex specific integer programming solvers for example given here ",
2016-09-06T14:55:18