1
$\begingroup$

I wrote a branch and bound algorithm for the bin packing problem and now I would like to know when exactly it stops giving solutions in a polynomial time.

I have N items (each item i has a volume Vi) and each bin has a volume V.

I tested the output of the algorithm and the execution time while varying the number of items N , the total volume of items Vtotal and the bin's volume V too.

What I noticed is that the termination criterion of the B&B algorithm does not depend only on N , it also depends on Vtotal and V .

For instance, if I have:

N = 18

Vtotal = 18

V = 8

The algorithm works fine and I get the output I want in a polynomial time (few milliseconds)

But , If I have :

N = 18

Vtotal = 18

V = 14

I don't get an output.

same for this test instance:

N = 18

Vtotal = 21

V = 14

(If Vtotal = 25 I get a solution in few milliseconds)

What I need to know is : Is there a way (for example, assemble the three parameters in one formula) to know when exactly I don't get a solution in a polynomial time?

Thank you

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ "polynomial time" is not the same as getting an output quickly. $\endgroup$ – Ian Ringrose Apr 21 '16 at 17:09
  • 1
    $\begingroup$ "Is there a way to know when exactly I don't get a solution in a polynomial time?" -- probably not. Intuitively, this is the same level of insight you'd need to settel P?=NP. $\endgroup$ – Raphael♦ Apr 21 '16 at 18:49
  • $\begingroup$ @IanRingrose I understand , but time complexity and execution time are related right? $\endgroup$ – AIri Apr 22 '16 at 7:58
  • $\begingroup$ @Raphael Yes that's what I know, but my supervisor keeps telling me to search for the exact value! I have been testing instances for months now. I really don't know what to do. $\endgroup$ – AIri Apr 22 '16 at 8:00
  • $\begingroup$ What "value"? Maybe I don't understand the task correctly, but assuming I do: is your supervisor clear about the fact that they want you do characterise bin-packing instances that are hard (for your algorithm)? $\endgroup$ – Raphael♦ Apr 22 '16 at 9:33

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.