{"id":5192,"date":"2014-03-21T09:00:30","date_gmt":"2014-03-21T13:00:30","guid":{"rendered":"https:\/\/blogs.mathworks.com\/pick\/?p=5192"},"modified":"2018-07-05T09:01:12","modified_gmt":"2018-07-05T13:01:12","slug":"packing-santas-sleigh","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/pick\/2014\/03\/21\/packing-santas-sleigh\/","title":{"rendered":"Packing Santa&#8217;s Sleigh"},"content":{"rendered":"<div class=\"content\">\r\n\r\n<!--introduction-->\r\n\r\nKristen's pick this week is <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/45423-packing-santa-s-sleigh\">Packing Santa's Sleigh<\/a> by <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/authors\/76492\">Alfonso Nieto-Castanon<\/a>.\r\n\r\n<em>Hi, my name is Kristen, and this is my first post for the Pick of the Week as a guest blogger. My background is in statistics, <a href=\"https:\/\/www.mathworks.com\/solutions\/machine-learning.html\">machine learning<\/a>, and data science, which are the areas I support as an Education Technical Evangelist at MathWorks. I use MATLAB every day to support faculty and students at universities around the world as they use MATLAB to teach and conduct research. The most exciting part of my job is seeing the diverse problems that are solved with MATLAB! Today, I\u2019m going to talk about one example...<\/em>\r\n\r\nOver the holidays, MathWorks sponsored a <a href=\"http:\/\/www.kaggle.com\/c\/packing-santas-sleigh\">Packing Santa's Sleigh<\/a> competition on <a href=\"http:\/\/www.kaggle.com\">Kaggle<\/a>, a platform for predictive modeling and data analytics competitions. Congratulations to Alfonso, who had the top MATLAB submission and scored second place overall! (Alfonso is no stranger to winning MATLAB contests \u2013 see his MATLAB Programming Contest wins <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/contest\/contests\/34\/players\/74?contest=all\">here<\/a> and number one rank on Cody <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/cody\/players\/1379371-alfonso-nieto-castanon\">here<\/a>.)\r\n\r\n<!--\/introduction-->\r\n<h3>Contents<\/h3>\r\n<div>\r\n<ul>\r\n \t<li><a href=\"#19de6f65-a61e-4219-b772-2ec186f8e54b\">Problem Statement<\/a><\/li>\r\n \t<li><a href=\"#922f7cd4-dac9-486a-9128-a78c7c430c7f\">Evaluation Criteria<\/a><\/li>\r\n \t<li><a href=\"#5e24d009-9ec3-4c4d-a127-0357732e00b2\">Winning MATLAB Solution<\/a><\/li>\r\n \t<li><a href=\"#6e420563-90f7-4c94-9448-0b930010d603\">Want To Try?<\/a><\/li>\r\n<\/ul>\r\n<\/div>\r\n<h4>Problem Statement<a name=\"19de6f65-a61e-4219-b772-2ec186f8e54b\"><\/a><\/h4>\r\nParticipants received the $x$-, $y$-, and $z$-dimensions of an ordered list of one million presents. To solve the problem, they were required to pack the presents onto a 1000 x 1000 sleigh, minimizing the total height of the sleigh and keeping the presents as close to the original order as possible. Presents could be rotated as long as they remained parallel to the $x$-, $y$-, and $z$-axes. (You might recognize this as a holiday version of the three-dimensional bin packing problem.)\r\n<h4>Evaluation Criteria<a name=\"922f7cd4-dac9-486a-9128-a78c7c430c7f\"><\/a><\/h4>\r\nThe solutions were judged on the compactness of packing (minimized height) and present order (delta from original order). The actual evaluation metric $M$ was calculated by\r\n\r\n$M = 2 \\cdot max_{i}(z_{i}) + \\sigma(\\Gamma)$, where\r\n\r\n$z_{i}$ = $z$-coordinate of the $i$th present,\r\n\r\n$\\sigma(\\Gamma) = \\sum_{i=1}^{N_{p}} |i-\\Gamma_{i}|$,\r\n\r\n$\\Gamma$ = order the presents appear, and\r\n\r\n$\\Gamma_{i}$ = the Present ID in the $i$th position.\r\n\r\nThe ideal present order is $\\Gamma_{ideal} = 1,2,3,\\dots,N_{p}$, so that $\\sigma(\\Gamma_{ideal}) = 0$, where $N_p$ is the total number of presents.\r\n<h4>Winning MATLAB Solution<a name=\"5e24d009-9ec3-4c4d-a127-0357732e00b2\"><\/a><\/h4>\r\nA na\u00efve solution might be to simply pack the presents in reverse order from the bottom to the top. Each layer would have a height $H$, the next layer would start at that height, and the process would be repeated until all of the presents are in the sleigh. This would optimize the present order, but leaves much room to reduce the height of the sleigh.\r\n\r\nAlfonso's solution implements a similar layer-based approach, but he adds a creative twist to how individual layers are defined: He divided the presents in each layer into two sets based on their heights, $H_{1}$ (Set 1) and $H_{2}$ (Set 2). His algorithm keeps the original order of the presents by packing from the bottom up and reverses the solution at the end. Figure 1 shows a na\u00efve layering approach (on the left) and a generalization of Alfonso's solution (on the right).\r\n\r\n<img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/pick\/guest\/packing_santa_blog\/sleighheight.png\" alt=\"\" hspace=\"5\" vspace=\"5\" \/>\r\n\r\nAfter the first layer, each layer starts partially occupied by presents from the layer below it. The process for each layer looks like this:\r\n<div>\r\n<ol>\r\n \t<li>Select random $H_{1}$ and $H_{2}$ values, where $H_{2}$ was constrained to be greater than or equal to $H_{1}$, and $H_{1}$ was constrained to be greater than or equal to $H_{2}$ - $H_{1}$ from the previous layer.<\/li>\r\n \t<li>Partition the presents into Set 1 and Set 2. Presents with all sides greater than H1 are put in Set 2. Of the remaining presents, ones that would fit at or below the maximum height are separated into the two sets based on the set for which they minimize the <em>wasted volume<\/em> $^1$.<\/li>\r\n \t<li>Estimate the expected <em>volume density<\/em> $^2$, assuming a given <em>surface density<\/em> $^3$, based on the partitions of the presents. If the expected <em>volume density<\/em> is above the current best solution, implement a 2-d solver to place the presents in the layer. If successfully converged, adaptively increase the <em>surface density<\/em> value; otherwise, decrease the value.<\/li>\r\n \t<li>This process is repeated until there are no longer any combinations of $H_{1}$ and $H_{2}$ that result in a higher <em>volume density<\/em>.<\/li>\r\n<\/ol>\r\n<\/div>\r\nAfter all of the layers are packed, the algorithm compacts them further by attempting to lower each present vertically, if there is room. Finally, the sleigh is flipped upside down to improve the optimal volume density and achieve the optimal order. This got Alfonso his winning score.\r\n\r\n$^{1,2,3}$ Alfonso provides the definitions of these terms, as well as a more detailed description with additional tricks and nice visualization of his solution, on the competition forum. You can see other Kaggle competitions that he's won <a href=\"\">here<\/a>.<br><br>\r\nCongratulations to Alfonso, the other competition winners, and all 362 competing teams!\r\n<br>\r\n&nbsp;\r\n<h4>Want To Try?<a name=\"6e420563-90f7-4c94-9448-0b930010d603\"><\/a><\/h4>\r\nVisit the competition <a href=\"http:\/\/www.kaggle.com\/c\/packing-santas-sleigh\/data\">Data<\/a> page to download the data and sample MATLAB code to get you started. Good luck!\r\n\r\nGive it a try and let us know about your solution <a href=\"https:\/\/blogs.mathworks.com\/pick\/?p=5192#respond\">here<\/a> or leave a <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/45423-packing-santa-s-sleigh#comments\">comment<\/a> for Alfonso!\r\n\r\n<script language=\"JavaScript\"> <!-- \r\n    function grabCode_3d5898a00a7e40bdbd856c8bfd731d69() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='3d5898a00a7e40bdbd856c8bfd731d69 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 3d5898a00a7e40bdbd856c8bfd731d69';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        copyright = 'Copyright 2014 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<\/p>\r\n<p>\r\n<\/p>\r\n<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add copyright line at the bottom if specified.\r\n        if (copyright.length > 0) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\r\n<p>\r\n<\/p>\r\n<p>\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }   \r\n     --> <\/script>\r\n<p style=\"text-align: right; font-size: xx-small; font-weight: lighter; font-style: italic; color: gray;\"><a><span style=\"font-size: x-small; font-style: italic;\">Get\r\nthe MATLAB code<noscript>(requires JavaScript)<\/noscript><\/span><\/a><\/p>\r\nPublished with MATLAB\u00ae R2014a\r\n<p class=\"footer\">Published with MATLAB\u00ae R2014a<\/p>\r\n\r\n<\/div>\r\n<!--\r\n3d5898a00a7e40bdbd856c8bfd731d69 ##### SOURCE BEGIN #####\r\n%%\r\n% Kristen's pick this week is\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/45423-packing-santa-s-sleigh % Packing Santa's Sleigh> by\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/authors\/76492 % Alfonso Nieto-Castanon>.\r\n%\r\n% _Hi, my name is Kristen, and this is my first post for the Pick of the\r\n% Week as a guest blogger. My background is in statistics,\r\n% <https:\/\/www.mathworks.com\/machine-learning\/ machine learning>, and data\r\n% science, which are the areas I support as an Education Technical\r\n% Evangelist at MathWorks. I use MATLAB every day to support faculty and\r\n% students at universities around the world as they use MATLAB to teach and\r\n% conduct research. The most exciting part of my job is seeing the diverse\r\n% problems that are solved with MATLAB! Today, I\u00e2\u20ac&#x2122;m going to talk about one\r\n% example..._\r\n%\r\n% Over the holidays, MathWorks sponsored a\r\n% <http:\/\/www.kaggle.com\/c\/packing-santas-sleigh Packing Santa's Sleigh>\r\n% competition on <http:\/\/www.kaggle.com Kaggle>, a platform for predictive\r\n% modeling and data analytics competitions. Congratulations to Alfonso, who\r\n% had the top MATLAB submission and scored second place overall! (Alfonso\r\n% is no stranger to winning MATLAB contests \u00e2\u20ac\u201c see his MATLAB Programming\r\n% Contest wins\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/contest\/contests\/34\/players\/74?contest=all % here> and number one rank on Cody\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/cody\/players\/1379371-alfonso-nieto-castanon % here>.)\r\n\r\n%% Problem Statement\r\n% Participants received the $x$-, $y$-, and $z$-dimensions of an ordered\r\n% list of one million presents. To solve the problem, they were required to\r\n% pack the presents onto a 1000 x 1000 sleigh, minimizing the total height\r\n% of the sleigh and keeping the presents as close to the original order as\r\n% possible. Presents could be rotated as long as they remained parallel to\r\n% the $x$-, $y$-, and $z$-axes. (You might recognize this as a holiday\r\n% version of the three-dimensional bin packing problem.)\r\n\r\n%% Evaluation Criteria\r\n% The solutions were judged on the compactness of packing (minimized\r\n% height) and present order (delta from original order). The actual\r\n% evaluation metric $M$ was calculated by\r\n%\r\n% $M = 2 \\cdot max_{i}(z_{i}) + \\sigma(\\Gamma)$, where\r\n%\r\n% $z_{i}$ = $z$-coordinate of the $i$th present,\r\n%\r\n% $\\sigma(\\Gamma) = \\sum_{i=1}^{N_{p}} |i-\\Gamma_{i}|$,\r\n%\r\n% $\\Gamma$ = order the presents appear, and\r\n%\r\n% $\\Gamma_{i}$ = the Present ID in the $i$th position.\r\n%\r\n% The ideal present order is $\\Gamma_{ideal} = 1,2,3,\\dots,N_{p}$, so that\r\n% $\\sigma(\\Gamma_{ideal}) = 0$, where $N_p$ is the total number of\r\n% presents.\r\n\r\n%% Winning MATLAB Solution\r\n% A na\u00c3\u00afve solution might be to simply pack the presents in reverse order\r\n% from the bottom to the top. Each layer would have a height $H$, the next\r\n% layer would start at that height, and the process would be repeated until\r\n% all of the presents are in the sleigh. This would optimize the present\r\n% order, but leaves much room to reduce the height of the sleigh.\r\n%\r\n% Alfonso's solution implements a similar layer-based approach, but he adds\r\n% a creative twist to how individual layers are defined: He divided the\r\n% presents in each layer into two sets based on their heights, $H_{1}$ (Set 1)\r\n% and $H_{2}$ (Set 2). His algorithm keeps the original order of the presents\r\n% by packing from the bottom up and reverses the solution at the end.\r\n% Figure 1 shows a na\u00c3\u00afve layering approach (on the left) and a\r\n% generalization of Alfonso's solution (on the right).\r\n%\r\n% <<sleighheight.png>>\r\n%\r\n% After the first layer, each layer starts partially occupied by presents\r\n% from the layer below it. The process for each layer looks like this:\r\n%\r\n% # Select random $H_{1}$ and $H_{2}$ values, where $H_{2}$ was constrained\r\n% to be greater than or equal to $H_{1}$, and $H_{1}$ was constrained to be\r\n% greater than or equal to $H_{2}$ - $H_{1}$ from the previous layer.\r\n% # Partition the presents into Set 1 and Set 2. Presents with all sides\r\n% greater than H1 are put in Set 2. Of the remaining presents, ones that\r\n% would fit at or below the maximum height are separated into the two sets\r\n% based on the set for which they minimize the _wasted volume_ $^1$.\r\n% # Estimate the expected _volume density_ $^2$, assuming a given _surface\r\n% density_ $^3$, based on the partitions of the presents. If the expected\r\n% _volume density_ is above the current best solution, implement a 2-d\r\n% solver to place the presents in the layer. If successfully converged,\r\n% adaptively increase the _surface density_ value; otherwise, decrease the\r\n% value.\r\n% # This process is repeated until there are no longer any combinations of\r\n% $H_{1}$ and $H_{2}$ that result in a higher _volume density_.\r\n%\r\n% After all of the layers are packed, the algorithm compacts them further\r\n% by attempting to lower each present vertically, if there is room.\r\n% Finally, the sleigh is flipped upside down to improve the optimal volume\r\n% density and achieve the optimal order. This got Alfonso his winning\r\n% score.\r\n%\r\n% $^{1,2,3}$ Alfonso provides the definitions of these terms, as well as a\r\n% more detailed description with additional tricks and nice visualization\r\n% of his solution, on the competition Forum\r\n% <https:\/\/www.kaggle.com\/c\/packing-santas-sleigh\/forums\/t\/6934\/how-d-you-do-it\/38414#post38414 % here>. You can see other Kaggle competitions that he's won\r\n% <https:\/\/www.kaggle.com\/users\/8668\/alfonso-nieto-castanon here>.\r\n%\r\n% Congratulations to Alfonso, the other competition winners, and all 362\r\n% competing teams!\r\n\r\n%% Want To Try?\r\n% Visit the competition <http:\/\/www.kaggle.com\/c\/packing-santas-sleigh\/data % Data> page to download the data and sample MATLAB code to get you\r\n% started. Good luck!\r\n%\r\n% Give it a try and let us know about your solution\r\n% <https:\/\/blogs.mathworks.com\/pick\/?p=5192#respond here> or leave a\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/45423-packing-santa-s-sleigh#comments % comment> for Alfonso!\r\n\r\n##### SOURCE END ##### 3d5898a00a7e40bdbd856c8bfd731d69\r\n-->","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img decoding=\"async\"  class=\"img-responsive\" src=\"https:\/\/blogs.mathworks.com\/images\/pick\/guest\/packing_santa_blog\/sleighheight.png\" onError=\"this.style.display ='none';\" \/><\/div><p>\r\n\r\n\r\n\r\nKristen's pick this week is Packing Santa's Sleigh by Alfonso Nieto-Castanon.\r\n\r\nHi, my name is Kristen, and this is my first post for the Pick of the Week as a guest blogger. My background... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/pick\/2014\/03\/21\/packing-santas-sleigh\/\">read more >><\/a><\/p>","protected":false},"author":36,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[16],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/pick\/wp-json\/wp\/v2\/posts\/5192"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/pick\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/pick\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/pick\/wp-json\/wp\/v2\/users\/36"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/pick\/wp-json\/wp\/v2\/comments?post=5192"}],"version-history":[{"count":21,"href":"https:\/\/blogs.mathworks.com\/pick\/wp-json\/wp\/v2\/posts\/5192\/revisions"}],"predecessor-version":[{"id":9914,"href":"https:\/\/blogs.mathworks.com\/pick\/wp-json\/wp\/v2\/posts\/5192\/revisions\/9914"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/pick\/wp-json\/wp\/v2\/media?parent=5192"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/pick\/wp-json\/wp\/v2\/categories?post=5192"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/pick\/wp-json\/wp\/v2\/tags?post=5192"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}