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.

  • 2
    $\begingroup$ Exhaustive search. $\endgroup$ – Yuval Filmus Jun 3 '20 at 12:48
  • $\begingroup$ Thanks. But better than that. I need without exponential memory. $\endgroup$ – Sanu Jun 3 '20 at 12:56
  • $\begingroup$ 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 $\endgroup$ – nir shahar Jun 3 '20 at 12:57
  • $\begingroup$ And this will take $O(n)$ memory overall $\endgroup$ – nir shahar Jun 3 '20 at 12:59
  • $\begingroup$ Yes, but time is 2^n in that case. Better than this. So we need polynomial memory and better than exhaustive search. $\endgroup$ – Sanu Jun 3 '20 at 13:09

There is in general not likely to be any algorithm for this problem that will take polynomial time (and polynomial space); the problem is NP-hard, and thus not believed to allow an efficient algorithm. If you just want polynomial space, then exhaustive search works. You're not likely to find any algorithm that uses polynomial space and is guaranteed to be faster than exhaustive search; that would contradict the strong exponential-time hypothesis. All existing methods are heuristics that might work well on some instances but not others.

  • $\begingroup$ Thanks. Will you kindly refer some heuristics? $\endgroup$ – Sanu Jun 4 '20 at 4:22

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.