{"id":94,"date":"2018-07-02T13:45:09","date_gmt":"2018-07-02T13:45:09","guid":{"rendered":"http:\/\/paradysz.pl\/?p=94"},"modified":"2019-12-05T13:58:17","modified_gmt":"2019-12-05T13:58:17","slug":"an-unusual-case-of-bin-packing-problem","status":"publish","type":"post","link":"https:\/\/paradysz.pl\/index.php\/2018\/07\/02\/an-unusual-case-of-bin-packing-problem\/","title":{"rendered":"An unusual case of bin packing problem"},"content":{"rendered":"<p style=\"text-align: justify;\">Some time ago I had met at my work with an interesting problem. I was working for\u00a0a construction company, in the warehouses, managers order different size tubes which are divided into smaller parts called panels. Panels have different lengths as well but always less than a length of tubes. To construct a building, the company needs to create a lot of panels which are obtained by cutting tubes. The leftover tubes cannot\u00a0be combined with each other, hence, the rest of the used tube will be less than the smaller required panel it must be thrown away (so-called a scrap). Utilization of scrap is costly, so production\u00a0excessive scrap is\u00a0unfavorable.<\/p>\n<p><img loading=\"lazy\" class=\"aligncenter wp-image-118 size-full\" src=\"http:\/\/paradysz.pl\/wp-content\/uploads\/2018\/02\/BP-1.png\" alt=\"\" width=\"882\" height=\"494\" srcset=\"https:\/\/paradysz.pl\/wp-content\/uploads\/2018\/02\/BP-1.png 882w, https:\/\/paradysz.pl\/wp-content\/uploads\/2018\/02\/BP-1-300x168.png 300w, https:\/\/paradysz.pl\/wp-content\/uploads\/2018\/02\/BP-1-768x430.png 768w\" sizes=\"(max-width: 882px) 100vw, 882px\" \/><\/p>\n<h2>What are the problems?<\/h2>\n<ul>\n<li>What length of tubes do managers need to order so that scrap amount will be as low as possible?<\/li>\n<li>How to cut ordered tubes to get all the required panels?<\/li>\n<\/ul>\n<p style=\"text-align: justify;\">Perhaps you guessed it! The problem is strongly related to the &#8216;bin packing problem&#8217; but with a significant\u00a0difference &#8211; containers (bins) can have a variable\u00a0size. Unfortunately, the problem is not easy to fix, moreover, it belongs to <a href=\"https:\/\/en.wikipedia.org\/wiki\/NP-hardness\">NP-hardness<\/a> class of problem.<\/p>\n<p>How can it be resolved?\u00a0I think there are many solutions, some are effective, others are time-consuming. I will try to quickly describe several of them.<\/p>\n<h3><strong>Deep learning<\/strong><\/h3>\n<p>One of the solutions is described <a href=\"https:\/\/arxiv.org\/abs\/1702.04415\">here<\/a>.<\/p>\n<h3><strong>Heuristics<\/strong><\/h3>\n<ul>\n<li>J.Kang, S.Park, <em>Algorithms for the variable sized bin packing problem<\/em><\/li>\n<li>M.Maiza, A.Labed M.S. Radjef, <em>Efficient algorithms for the offline variable sized bin-packing problem<br \/>\n<\/em><\/li>\n<\/ul>\n<h3><strong>A simple case using only one length of the tube<\/strong><\/h3>\n<p>If we choose only one length of tube (preferable, the longest), an unusual bin packing problem will start to occur with one exception &#8211; the last packing phase will select the shortest possible tube.<\/p>\n<p>I recommend\u00a0trying to implement one of above solution and test it using cases where usual bin packing algorithm does not return\u00a0optimal results.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Some time ago I had met at my work with an interesting problem. I was working for\u00a0a construction company, in the warehouses, managers order different size tubes which are divided into smaller parts called panels. Panels have different lengths as well but always less than a length of tubes. To construct a building, the company [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":280,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[5,6,3],"tags":[],"_links":{"self":[{"href":"https:\/\/paradysz.pl\/index.php\/wp-json\/wp\/v2\/posts\/94"}],"collection":[{"href":"https:\/\/paradysz.pl\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/paradysz.pl\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/paradysz.pl\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/paradysz.pl\/index.php\/wp-json\/wp\/v2\/comments?post=94"}],"version-history":[{"count":23,"href":"https:\/\/paradysz.pl\/index.php\/wp-json\/wp\/v2\/posts\/94\/revisions"}],"predecessor-version":[{"id":453,"href":"https:\/\/paradysz.pl\/index.php\/wp-json\/wp\/v2\/posts\/94\/revisions\/453"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/paradysz.pl\/index.php\/wp-json\/wp\/v2\/media\/280"}],"wp:attachment":[{"href":"https:\/\/paradysz.pl\/index.php\/wp-json\/wp\/v2\/media?parent=94"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/paradysz.pl\/index.php\/wp-json\/wp\/v2\/categories?post=94"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/paradysz.pl\/index.php\/wp-json\/wp\/v2\/tags?post=94"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}