# How is INTEGER linear programming implemented in the Mathematica LinearProgramming function?

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?

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

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