# scalable binary linear optimization

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!

-

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

-

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.

-