# Binary integer programming problem without exponential memory

Consider binary integer programming problem with n variables.
I think the branch and cut algorithm takes exponential memory. What are existing algorithms without much memory? Please suggest.

• Exhaustive search. – Yuval Filmus Jun 3 at 12:48
• Thanks. But better than that. I need without exponential memory. – Sanu Jun 3 at 12:56
• This is the best. you need to somehow keep in memory a solution (so you can verify and return it). going over all solutions will not increase the memory as its just equivelant to changing the current solution – nir shahar Jun 3 at 12:57
• And this will take $O(n)$ memory overall – nir shahar Jun 3 at 12:59
• Yes, but time is 2^n in that case. Better than this. So we need polynomial memory and better than exhaustive search. – Sanu Jun 3 at 13:09