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!

$\endgroup$

2 Answers 2

1
$\begingroup$

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

$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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