Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have the following problem:

$A x = b$

where $A, b$ - $m \times n$-maxtrix and $m$-vector of nonnegative intgers (respectivelly).

$x \in \{0,1\}^n $ - vector of binary variables, which need to be found.

Investigation shows it's known NP-complete problem. But special case of this problem ($m = 1$) is Subset sum problem, which also is NP-complete but has good pseudo-polynomial dynamic programming solution. For my problem coefficients in $A, b$ are bounded and not very big ($A_{i,j}, b_i \leq S $), but $m$ can be quite large, so it will be unacceptable to have $O(n \times S^m)$ solution. But may be there is something better? Optionally, if it's significantly easier, method which gives only one solution instead of all, also will be helpful.

Could someone point me to good method for solving such kind of problems?

share|improve this question
    
You should make it clear what constitutes a solution. I guess you want to find the 0-1 vector x, but it is unclear. If you do want x, there is a straightforward O(mn2^n) algorithm, where by certain backtracking you can cut down on the m factor in practice. In particular, I would try solving for b_1, and then with the subset of solutions see which of those solve for b_2, etc. You could also try a pseudoinverse C of A and look for 0-1 vectors near Cb. Gerhard "Ask Me About System Design" Paseman, 2012.03.28 –  Gerhard Paseman Mar 28 '12 at 18:22
    
Thank you for you comment. But, if straightforward algorithm were worked good enough, I wouldn't trying to find pseudo-polynomial. O(m n 2^n) it's too much for me. Especially, because in most cases m << n. –  Wisdom's Wind Mar 28 '12 at 19:22
    
This is a special case of integer programming, which is linear programming with all variables restricted to integers. The usual way to solve such problems is with the branch-and-bound algorithm. Of course, since the problem is NP-hard in general, the branch-and-bound algorithm does not come with any speed guarantees that are better than exponential. But it does tend to converge quickly for many practical problems. Is there anything special about the structure of your problem that might give us a clue to a better algorithm? –  Carl Feynman Mar 28 '12 at 19:45
    
Actually, it's very special case of IP, because I haven't objective function and I haven't inequalities. That's why I hoped for some more effective solution. I familiar with IP, and "brunch and cut" algorithms for MIP, it's very complicated methods. In this question I wondering: is there some methods for such system in general, cause if it is, it will help me in many ways. For particular problem which I trying to solve right now, please check this question: mathoverflow.net/questions/92504/… –  Wisdom's Wind Mar 28 '12 at 20:42
1  
Sometimes Minion <minion.sourceforge.net/>; can solve problems like this fast enough for practical use. It is easy to use and worth a try. –  Brendan McKay Mar 28 '12 at 22:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.