2
$\begingroup$

I am solving a 2D bin packing problem, however, there is an additional constraint where some items must be in the same bin. The problem is at industry scale (up to 1000 items and ~200 bins of different sizes) so I am looking to write a heuristic for it as ILP solvers won't be useful here.

For example, the 1000 items really represent 500 orders where each order consists of 2 items, and the items in an order must go in the same bin.

Has anyone come across a bin packing problem/heuristic with a similar constraint?

$\endgroup$
4
  • $\begingroup$ If you're already creating "orders" from the items that need to go together, then why not just use those orders to fill up the bins and use heuristics like First-Fit Decreasing or Best-Fit Decreasing? $\endgroup$
    – EhsanK
    Commented Jan 25 at 17:43
  • $\begingroup$ An order is just a set of items. It says nothing about how they are packed in the bin, just that the items in an order need to be in the same bin. I was just wondering if this was a variant of bin packing with some literature behind it that I cannot find... $\endgroup$ Commented Jan 25 at 17:47
  • $\begingroup$ This is a tough constraint. It is known in the literature as "complete shipment" constraint. A similar constraint appears when solving a bin packing problem with a branch-and-price algorithm in the knapsack subproblem. In one dimension, it is trivial to handle since items can be easily merged, but not in two dimensions. The difficulty and the approach to choose will depend on the number of items in bins, the number of bins in the solution, and the filing rate of the bins $\endgroup$
    – fontanf
    Commented Jan 26 at 8:38
  • $\begingroup$ @or-researcherOR, is it possible to pre-determined these some items which must be in the same bin? $\endgroup$
    – A.Omidi
    Commented Jan 27 at 7:31

2 Answers 2

0
$\begingroup$

You could try approaching this similarly to a cutting stock problem. The master problem will contain one binary variable for each of a fixed set of feasible bin loadings (where feasibility here includes the requirement that eith both halves or neither half of an order be in the loading). Master problem constraints include not using more loadings for each bin size than there are bins available and ensuring that for each order the number of selected loadings including that order equals 1.

Then you need a subproblem to generate feasible loadings. This would be a 2D knapsack problem with the side constraint that you not include only half of an order.

The solution process starts with you finding an initial set of loadings to populate the master problem. Relax the master problem to an LP, solve and use the shadow prices (dual variables) as the rewards for including orders in the loading-generating subproblem. Generate a new loading, add to the master problem, rinse and repeat. When you fail to find a new loading, restore the integrality restrictions in the master problem and solve it.

If you have trouble generating the initial set of loadings, you might populate the master with a few to start, relax the "include every order once" constraint to "include very order at most once", change the objective to minimizing the number of excluded orders, and apply the iteration scheme until you have enough loadings that a feasible solution covering every order exists. Then revert to the original objective and forge ahead.

$\endgroup$
1
  • $\begingroup$ Thanks for the suggestion! I'll think on it. $\endgroup$ Commented Jan 25 at 22:06
0
$\begingroup$

@prubin suggested an approach based on a Dantig-Wolfe decomposition. Here is another idea based on a Benders decomposition.

  • Solve the one-dimensional version of the problem. In this case, each order might be merged into a single item which size is the sum of the sizes of each item from the order. It is a smaller and easier to solve one-dimensional bin packing problem. You can try the various classical methods to solve it (assignment MILP model, arc-flow MILP model, Dantzig-Wolfe decomposition, heuristics).

  • Check if the one-dimensional bins generated are feasible with the two-dimensional constraints. That is, solve multiple two-dimensional packing problems with a single bin where the goal is to pack all input items in the bin.

  • If all checks pass, then stop

  • Otherwise, for each bin which check failed

    • Either add a cut (constraint) to the one-dimensional problem to forbid the corresponding assignment. This will likely take a very long time to converge on large problems
    • Or increase the size of the orders assigned to the bin in the one-dimensional packing problem such that this assignment just becomes infeasible
$\endgroup$

Your Answer

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

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