MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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

share|cite|improve this answer

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|cite|improve this answer

Your Answer


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.