2
$\begingroup$

For an upcoming client project, I'm looking to do a 3D variant on the knapsack problem. Basically, there's a bin of dimensions $x,y,z$, and I have $K$ units of an item with dimensions $a,b,c$. (Assuming rectangular prisms for both the bin and the item).

I want to find the max number of units ($\le K$) that will fit in the bin. Are there are any ready-made Python or R packages I could use for this? Answering this question is actually a preparatory step in a larger optimization model, so even if I need to just write the MIP into the overall model that would be OK too.

Improve this question
$\endgroup$
2
  • $\begingroup$ If all items are the same size and the orientation is fixed you can find the solution just by rounding down. $\endgroup$
    – worldsmithhelper
    May 21, 2022 at 17:37
  • $\begingroup$ Orientation isn't fixed. I'll turn the units in whatever way necessary to get the maximum number possible into the bin. Units are all the same size. $\endgroup$
    – Ralph Asher
    May 21, 2022 at 17:57

1 Answer 1

Reset to default
3
$\begingroup$

As the container loading problem is NP-hard in its essence, therefore, using a mixed-integer program might not be efficient to solve this kind of problem, except using advanced techniques like column generation to solve the large-scale instances.

By the way, using CP would be a good choice than the MIP. If you are still willing to use MIP there are many papers that could be easily found by googling. (E.g. this one.).

One possible way to use CP is based on non-overlap constraints. I worked on a 2D loading problem by using this kind of constraint. The result was so effective. It also would be possible to divide the height of the container by the number of equal floors and applying this system to optimize each floor separately. Also, this needs to perform some pre-processing to categorize items by the appropriate height.

Indeed, in the following there are two python packages, one excel package, and one commercial software to solve such a problem that might be helpful:

Improve this answer
$\endgroup$
4
  • $\begingroup$ "As the container loading problem is NP-hard in its essence, therefore, using a mixed-integer program might not be efficient to solve this kind of problem" I don't really agree with this sentence. On the contrary, if the problem weren't NP-hard, there would likely be something else more efficient than a MILP solver. The reason should rather be that there is no "good" MILP models for this problem, that is, models with good relaxation, efficient cuts, or reasonable size. But I don't know if it's actually the case $\endgroup$
    – fontanf
    May 24, 2022 at 8:29
  • $\begingroup$ @fontanf, many thanks for your comment. As far as I know, the simplest problem in this category, like the bin-packing problem, is NP-hard, and to solve the real problem we already need to use a tool like column generation. These days I have worked around a formulation to solve such a problem, but the results are far from the one we can obtain from (e,g.) CP. I have been working on the floor layout problems, 2D and in some cases 3D, and solving such a problem with MILP is defiantly challenging work. I really would appreciate it if anyone can introduce an efficient one. $\endgroup$
    – A.Omidi
    May 24, 2022 at 12:39
  • 1
    $\begingroup$ Indeed, the assignment MILP model for bin packing does not perform very well compared to other methods. Still, there exists better models like the arc-flow formulation which performs pretty decently. In addition, here, the problem is a knapsack problem. For one dimensional knapsack variants, MILP models perform rather well. And this problem has the additional restriction of having a single item type, which might make the resolution easier for a MILP $\endgroup$
    – fontanf
    May 24, 2022 at 13:48
  • 1
    $\begingroup$ I don't known if there is a known good MILP formulation for this problem. I just wouldn't say not to use it giving the reason that the problem is NP-hard, but rather say that there is no good MILP formulation known (if it is the case) $\endgroup$
    – fontanf
    May 24, 2022 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.