# When does Branch and Bound exactly stop giving solutions for the bin packing problem

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

• "polynomial time" is not the same as getting an output quickly. – Ian Ringrose Apr 21 '16 at 17:09
• "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. – Raphael Apr 21 '16 at 18:49
• @IanRingrose I understand , but time complexity and execution time are related right? – AIri Apr 22 '16 at 7:58
• @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. – AIri Apr 22 '16 at 8:00
• 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)? – Raphael Apr 22 '16 at 9:33