How do I find the k'th best solution to the 10 knapsack problem without finding the Topk solutions? Is there any mathematical research that deals with the k'th best solutions to the mixed integer programming problems?
Asked
Viewed
119 times

$\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 k1 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