How do I find the k'th best solution to the 1-0 knapsack problem without finding the Top-k solutions? Is there any mathematical research that deals with the k'th best solutions to the mixed integer programming problems?

  • $\begingroup$ Are you expecting a poly time result? If not,then many of the traditional techniques such as cutting planes, branch and bound would seem applicable, where eahc is run until the optimal is found and then we trim off the optimal, repeating this k-1 times. $\endgroup$ – frogeyedpeas Sep 28 '15 at 8:06
  • $\begingroup$ Polynomial in the size of the problem and faster than linear in k. Ideally, the complexity would not depend on k. $\endgroup$ – vkrouglov Sep 28 '15 at 10:09
  • $\begingroup$ If the complexity didn't depend on k and it was poly time in the size (#of bits) to represent the problem then you would solve P = NP, by setting k = 1, if it truly doesn't impact the running time $\endgroup$ – frogeyedpeas Sep 28 '15 at 21:56
  • $\begingroup$ Your comment is legitimate and I am not sure how to formally define my question. It is more of a philosophical question - how to find the k'th best solution directly without exploring the full search space or the Top k solutions. For example in the standard approach via dynamic programming we are cutting off big chunks of search space that cannot be in the optimal solution. Is it possible to do the same for the k'th best solution? $\endgroup$ – vkrouglov Oct 2 '15 at 10:52

Your Answer

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

Browse other questions tagged or ask your own question.