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

Has anyone encountered scalable solutions to a binary linear optimization problem of the form:

\min \sum_{i=1}^n x_i s.t x_i \in {0,1} Ax=b

where, x=(x_1,x_2,...,x_n)^t, b=(b_1, b_2,...,b_m)^t, b_i is positive integer and A is a very sparse matrix with entries 0 or 1.

By scalable I mean solution that handle large values of n and multiple constraints (m).

Thank you!

share|improve this question
add comment

2 Answers

If the matrix A is totally unimodular, the LP-relaxation has an integer solution. In general, the problem is NP-hard.

share|improve this answer
add comment

When vector b is all-one, this problem is called Set Partioning. Positive weights can be used in the objective funtion, and this has applications e.g. in airline crew scheduling problems. The problem is NP-hard. You can find more information on this page.

share|improve this answer
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.