6
$\begingroup$

I was surprised to see that, for d = 1000, b = 800, Mathematica solves an integer linear (LP) program such as

LinearProgramming[w, A, Table[1.0,{b}], Table[{0,1}, d], Integers]

almost as fast as it takes to solve the linear program

LinearProgramming[w, A, Table[1.0,{b}] ]

for a sparse b x d matrix A, with entries 0 or 1. The linear program did not have an integral solution. I have been unable to trace in the documentation the method by which integer LP is implemented.

Does anyone know?

$\endgroup$
  • $\begingroup$ This integer LP problem is Minimum Weight Set Cover, which is NP hard. $\endgroup$ – Richard Darling Jan 14 '17 at 0:48
  • 3
    $\begingroup$ COIN-CLP is used under the hood, IIRC. $\endgroup$ – J. M. will be back soon Jan 14 '17 at 15:55
  • $\begingroup$ Yes, COIN-CLP is invoked by LinearProgramming. $\endgroup$ – Daniel Lichtblau Jan 14 '17 at 16:09
3
$\begingroup$

According to the comments, COIN-CBC is used by LinearProgramming for integer problems.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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