0
$\begingroup$

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!

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .