Prolog（CLP）的可变装箱问题

Question

我正在尝试使用约束逻辑编程 (CLP) 在 (Swi-) Prolog 中找到 NP-hard 2D Variable Size Bin Packing Problem (2DVSBPP) 的算法。

问题可以这样解释：一些订购的产品需要尽可能有效地包装到一些盒子（箱）中。产品有一些给定的宽度和长度（正方形或矩形，例如 2x3）。有四种不同尺寸的箱子，每种箱子都有给托运人的特定成本（例如，5x5 箱子 4 美元，5x7 箱子 5 美元）。目标是最小化盒子的总成本。

一段时间以来，我一直在寻找这个问题的答案，并阅读了许多其他语言的论文和类似示例。但是，我找不到任何可行的解决方案。我特别纠结于如何处理未知数量的 Boxes (bins)。

---

为了能够找到这个问题的解决方案，我试图适应一个类似的问题，但真的不知道如何处理可变数量的盒子。下面的代码可以选择最便宜的盒子来装所有的产品，只要只需要一个盒子就可以装所有的产品。从我们需要多个盒子的那一刻起，程序就失败了。

盒子和产品：

:- use_module(library(clpfd)).
:- use_module(library(clpr)).
:- expects_dialect(sicstus).


%% These are the possible productsizes that could need packing
% product (id, width, length)
product(1, 2, 2). 
product(2, 1, 2). 
product(2, 2, 1). % repeating product n2 because it can lay horizontal or vertical
product(3, 1, 3). 
product(3, 3, 1). % idem
product(4, 3, 3). % is square so does not need it
product(5, 2, 3). 
product(5, 3, 2). % iden
product(6, 4, 2). 
product(6, 2, 4). % idem

% because it can lay virtically or horizontally in a box
product_either_way(Number, Width, Length) :-
    product(Number, Width, Length).
product_either_way(Number, Width, Length) :-
    product(Number, Length, Width).


%% These are the so called bins from the 2DVSBPP problem
%% There are 4 sizes, but there is an unlimited supply
% box(Width, Length, Cost)
box(4,4,4).
box(4,6,6).
box(5,5,7).
box(9,9,9).

约束条件：

area_box_pos_combined(W_total*H_total,prod(N),X+Y,f(X,Width,Y,Height)) :-
    product_either_way(N, Width, Height), % Getting the width and height (length) of a product
    % Constraint: the product should 'fit' inside the choosen box
    % thus limiting its coordinates (XY)
    X #>= 1,
    X #=< W_total-Width+1,
    Y #>= 1,
    Y #=< H_total-Height+1.

positions_vars([],[]).
positions_vars([X+Y|XYs],[X,Y|Zs]) :-
    positions_vars(XYs,Zs).

area_boxes_positions_(ProductList,Ps,Zs) :-
    box(W, H, Cost), % finding a suitable box with a W & H
    %% minimize(Cost),
    maplist(area_box_pos_combined(W*H),ProductList,Ps,Cs), % Setting up constraints for each product
    disjoint2(Cs), % making sure they dont overlap with other product inside the box
    positions_vars(Ps,Zs).

要求包装 4 个产品（编号 2、1、3 和 5）的可能查询

area_boxes_positions_([prod(2),prod(1),prod(3),prod(5)],Positions,Zs),
labeling([ffc],Zs).

Gives the following as output, one possible way to pack the products:
Positions = [3+1, 1+1, 4+1, 1+3],
Zs = [3, 1, 1, 1, 4, 1, 1, 3] .

但是，当我们有更多产品无法放入一个盒子时，我该如何对多个盒子进行建模？

任何帮助或示例都非常感谢！

Answer 1

我特别为如何处理未知数量的盒子（垃圾箱）而苦苦挣扎。

你可以给盒子的数量设置一个上限：对于 N 个不可分割的元素，你永远不需要超过 N 个盒子。此外，我们可以定义一种特殊的“未使用”类型的盒子，其尺寸为 0，成本为 0。然后我们可以寻求一个解决方案，将项目分配到恰好N 个（或任何其他数量的）个盒子，其中一些可以保持未使用。

以下是对单个盒子的描述，使用析取约束和连接约束关联其种类、大小和成本：

kind_width_length_cost(Kind, Width, Length, Cost) :-
    % unused box
    (Kind #= 0 #/\ Width #= 0 #/\ Length #= 0 #/\ Cost #= 0) #\/
    % small box
    (Kind #= 1 #/\ Width #= 4 #/\ Length #= 4 #/\ Cost #= 4) #\/
    % medium box
    (Kind #= 2 #/\ Width #= 4 #/\ Length #= 6 #/\ Cost #= 6) #\/
    % large box
    (Kind #= 3 #/\ Width #= 5 #/\ Length #= 5 #/\ Cost #= 7) #\/
    % X-large box
    (Kind #= 4 #/\ Width #= 9 #/\ Length #= 9 #/\ Cost #= 9),
    % make sure all variables have finite domains, the above disjunction is
    % not enough for the system to infer this
    Kind in 0..4,
    Width in 0..9,
    Length in 0..9,
    Cost in 0..9.

N 个盒子的集合可以表示为一个术语boxes(Numbers, Kinds, Widths, Lengths, Costs)，其中Numbersare[1, 2, ..., N]和I每个其他列表的第 -th 个元素是 box number 的长度/宽度/成本I：

n_boxes(N, boxes(Numbers, Kinds, Widths, Lengths, Costs)) :-
    numlist(1, N, Numbers),
    length(Kinds, N),
    maplist(kind_width_length_cost, Kinds, Widths, Lengths, Costs).

例如，三个盒子是：

?- n_boxes(3, Boxes).
Boxes = boxes([1, 2, 3], [_G9202, _G9205, _G9208], [_G9211, _G9214, _G9217], [_G9220, _G9223, _G9226], [_G9229, _G9232, _G9235]),
_G9202 in 0..4,
_G9202#=4#<==>_G9257,
_G9202#=3#<==>_G9269,
_G9202#=2#<==>_G9281,
_G9202#=1#<==>_G9293,
_G9202#=0#<==>_G9305,
... a lot more constraints

请注意，这使用了包含列表的术语，而不是包含术语列表的更“常见”的表示box(Num, Width, Length, Cost)。这样做的原因是我们希望使用 索引到这些 FD 变量列表中element/3。此谓词不能用于索引其他术语的列表。

谈到产品，这里是你的析取product_either_way谓词的 FD 版本：

product_either_way_fd(Number, Width, Length) :-
    product_width_length(Number, W, L),
    (Width #= W #/\ Length #= L) #\/ (Width #= L #/\ Length #= W),
    % make sure Width and Length have finite domains
    Width #>= min(W, L),
    Width #=< max(W, L),
    Length #>= min(W, L),
    Length #=< max(W, L).

项目的放置用一个术语表示，该术语box_x_y_w_l包含框的编号、框内的 X 和 Y 坐标以及项目的宽度和长度。放置必须与所选盒子的尺寸兼容：

product_placement(Widths, Lengths, Number, Placement) :-
    product_either_way_fd(Number, W, L),
    Placement = box_x_y_w_l(_Box, _X, _Y, W, L),
    placement(Widths, Lengths, Placement).

placement(Widths, Lengths, box_x_y_w_l(Box, X, Y, W, L)) :-
    X #>= 0,
    X + W #=< Width,
    Y #>= 0,
    Y + L #=< Length, 
    element(Box, Widths, Width),
    element(Box, Lengths, Length).

这是我们使用Widths和LengthsFD 变量列表的地方。所选框的编号本身就是一个 FD 变量，我们将其用作索引以使用element/3约束查找框的宽度和长度。

现在我们必须对不重叠的展示位置进行建模。放置在不同盒子中的两个项目自动不重叠。对于同一个盒子中的两个项目，我们必须检查它们的坐标和大小。这种二元关系必须应用于所有无序的项目对：

placement_disjoint(box_x_y_w_l(Box1, X1, Y1, W1, L1),
                   box_x_y_w_l(Box2, X2, Y2, W2, L2)) :-
    Box1 #\= Box2 #\/
    (Box1 #= Box2 #/\
     (X1 #>= X2 + W2 #\/ X1 + W1 #< X2) #/\
     (Y1 #>= Y2 + L2 #\/ Y1 + L1 #< Y2)).

alldisjoint([]).   
alldisjoint([Placement | Placements]) :-
    maplist(placement_disjoint(Placement), Placements),
    alldisjoint(Placements).

现在我们已准备好将所有内容放在一起。给定产品列表和 N 个盒子（其中一些可能未使用），以下谓词计算盒子中放置的约束、使用的盒子种类、成本和总成本：

placements_(Products, N, Placements, BoxKinds, Costs, Cost) :-
    n_boxes(N, boxes(_BoxNumbers, BoxKinds, Widths, Lengths, Costs)),
    maplist(product_placement(Widths, Lengths), Products, Placements),
    alldisjoint(Placements),
    sum(Costs, #=, Cost).

这构造了一个表示 N 个盒子的术语，计算每个产品的放置约束，确保放置不相交，并设置总成本的计算。就这些！

我正在使用从问题中复制的以下产品。请注意，我已经删除了具有交换宽度/长度的重复项，因为这种交换是product_either_way_fd在需要时完成的。

product_width_length(1, 2, 2).
product_width_length(2, 1, 2).
product_width_length(3, 1, 3).
product_width_length(4, 3, 3).
product_width_length(5, 2, 3).
product_width_length(6, 4, 2).

我们已准备好进行测试。要重现将项目 2、1、3 和 5 放入单个盒子中的示例：

?- placements_([2, 1, 3, 5], 1, Placements, Kinds, Costs, Cost).
Placements = [box_x_y_w_l(1, _G17524, _G17525, _G17526, _G17527), box_x_y_w_l(1, _G17533, _G17534, 2, 2), box_x_y_w_l(1, _G17542, _G17543, _G17544, _G17545), box_x_y_w_l(1, _G17551, _G17552, _G17553, _G17554)],
Kinds = [_G17562],
Costs = [Cost],
_G17524 in 0..8,
_G17524+_G17526#=_G17599,
_G17524+_G17526#=_G17611,
_G17524+_G17526#=_G17623,
...

带标签：

?- placements_([2, 1, 3, 5], 1, Placements, Kinds, Costs, Cost), term_variables(Placements, Variables, [Cost | Costs]), labeling([], Variables).
Placements = [box_x_y_w_l(1, 0, 0, 1, 2), box_x_y_w_l(1, 7, 7, 2, 2), box_x_y_w_l(1, 4, 6, 3, 1), box_x_y_w_l(1, 2, 3, 2, 3)],
Kinds = [4],
Costs = [9],
Cost = 9,
Variables = [0, 0, 1, 2, 7, 7, 4, 6, 3|...] .

（您可能需要仔细检查它的正确性！）所有东西都放在 1 号盒子里，这是 4 号（尺寸 9x9），成本 9。

有没有办法将这些物品放入更便宜的盒子中？

?- Cost #< 9, placements_([2, 1, 3, 5], 1, Placements, Kinds, Costs, Cost), term_variables(Placements, Variables, [Cost | Costs]), labeling([], Variables).
false.

现在，将所有产品放入（最多）6 个盒子中如何？

?- placements_([1, 2, 3, 4, 5, 6], 6, Placements, Kinds, Costs, Cost), term_variables(Placements, Variables, [Cost | Costs]), labeling([], Variables).
Placements = [box_x_y_w_l(1, 0, 0, 2, 2), box_x_y_w_l(1, 3, 3, 1, 2), box_x_y_w_l(1, 5, 6, 1, 3), box_x_y_w_l(2, 0, 0, 3, 3), box_x_y_w_l(2, 4, 4, 2, 3), box_x_y_w_l(3, 0, 0, 2, 4)],
Kinds = [4, 4, 1, 0, 0, 0],
Costs = [9, 9, 4, 0, 0, 0],
Cost = 22,
Variables = [1, 0, 0, 1, 3, 3, 1, 2, 1|...] .

找到的第一个解决方案使用三个盒子，其余三个未使用。我们能便宜点吗？

?- Cost #< 22, placements_([1, 2, 3, 4, 5, 6], 6, Placements, Kinds, Costs, Cost), term_variables(Placements, Variables, [Cost | Costs]), labeling([], Variables).
Cost = 21,
Placements = [box_x_y_w_l(1, 0, 0, 2, 2), box_x_y_w_l(1, 3, 3, 1, 2), box_x_y_w_l(1, 5, 6, 1, 3), box_x_y_w_l(2, 0, 0, 3, 3), box_x_y_w_l(3, 0, 0, 2, 3), box_x_y_w_l(4, 0, 0, 2, 4)],
Kinds = [4, 1, 1, 1, 0, 0],
Costs = [9, 4, 4, 4, 0, 0],
Variables = [1, 0, 0, 1, 3, 3, 1, 2, 1|...] .

是的！此解决方案使用更多的盒子，但总体上稍微便宜一些。我们还能做得更好吗？

?- Cost #< 21, placements_([1, 2, 3, 4, 5, 6], 6, Placements, Kinds, Costs, Cost), term_variables(Placements, Variables, [Cost | Costs]), labeling([], Variables).
% ... takes far too long

我们需要更复杂一点。玩弄盒子的数量，很明显可以使用更少盒子的更便宜的解决方案：

?- Cost #< 21, placements_([1, 2, 3, 4, 5, 6], 2, Placements, Kinds, Costs, Cost), term_variables(Placements, Variables, [Cost | Costs]), labeling([], Variables).
Cost = 18,
Placements = [box_x_y_w_l(1, 0, 0, 2, 2), box_x_y_w_l(1, 3, 3, 1, 2), box_x_y_w_l(1, 5, 6, 1, 3), box_x_y_w_l(2, 0, 6, 3, 3), box_x_y_w_l(2, 6, 4, 3, 2), box_x_y_w_l(2, 4, 0, 2, 4)],
Kinds = [4, 4],
Costs = [9, 9],
Variables = [1, 0, 0, 1, 3, 3, 1, 2, 1|...] .

也许引导搜索首先标记框类型是有用的，因为该up策略本质上会尝试使用尽可能少的框：

?- Cost #< 21, placements_([1, 2, 3, 4, 5, 6], 6, Placements, Kinds, Costs, Cost), term_variables(Placements, Variables, [Cost | Costs]), time(( labeling([], Kinds), labeling([ff], Variables) )).
% 35,031,786 inferences, 2.585 CPU in 2.585 seconds (100% CPU, 13550491 Lips)
Cost = 15,
Placements = [box_x_y_w_l(5, 2, 4, 2, 2), box_x_y_w_l(6, 8, 7, 1, 2), box_x_y_w_l(6, 5, 6, 3, 1), box_x_y_w_l(6, 2, 3, 3, 3), box_x_y_w_l(6, 0, 0, 2, 3), box_x_y_w_l(5, 0, 0, 2, 4)],
Kinds = [0, 0, 0, 0, 2, 4],
Costs = [0, 0, 0, 0, 6, 9],
Variables = [5, 2, 4, 6, 8, 7, 1, 2, 6|...] .

这确实需要ffor ffc，默认leftmost策略不会在合理的时间范围内返回结果。

我们还能做得更好吗？

?- Cost #< 15, placements_([1, 2, 3, 4, 5, 6], 6, Placements, Kinds, Costs, Cost), term_variables(Placements, Variables, [Cost | Costs]), time(( labeling([], Kinds), labeling([ff], Variables) )).
% 946,355,675 inferences, 69.984 CPU in 69.981 seconds (100% CPU, 13522408 Lips)
false.

不！成本为 15 的解决方案是最优的（但不是唯一的）。

但是，我发现 70 秒对于这个非常小的问题规模来说太慢了。是否有一些我们可以利用的对称性？考虑：

?- Cost #= 15, placements_([1, 2, 3, 4, 5, 6], 6, Placements, Kinds, Costs, Cost), term_variables(Placements, Variables, [Cost | Costs]), time(( labeling([], Kinds), labeling([ff], Variables) )).
% 8,651,030 inferences, 0.611 CPU in 0.611 seconds (100% CPU, 14163879 Lips)
Cost = 15,
Placements = [box_x_y_w_l(5, 2, 4, 2, 2), box_x_y_w_l(6, 8, 7, 1, 2), box_x_y_w_l(6, 5, 6, 3, 1), box_x_y_w_l(6, 2, 3, 3, 3), box_x_y_w_l(6, 0, 0, 2, 3), box_x_y_w_l(5, 0, 0, 2, 4)],
Kinds = [0, 0, 0, 0, 2, 4],
Costs = [0, 0, 0, 0, 6, 9],
Variables = [5, 2, 4, 6, 8, 7, 1, 2, 6|...] .

?- Kinds = [4, 2, 0, 0, 0, 0], Cost #= 15, placements_([1, 2, 3, 4, 5, 6], 6, Placements, Kinds, Costs, Cost), term_variables(Placements, Variables, [Cost | Costs]), time(( labeling([], Kinds), labeling([ff], Variables) )).
% 11,182,689 inferences, 0.790 CPU in 0.790 seconds (100% CPU, 14153341 Lips)
Kinds = [4, 2, 0, 0, 0, 0],
Cost = 15,
Placements = [box_x_y_w_l(1, 7, 7, 2, 2), box_x_y_w_l(1, 6, 5, 1, 2), box_x_y_w_l(2, 3, 3, 1, 3), box_x_y_w_l(2, 0, 0, 3, 3), box_x_y_w_l(1, 4, 2, 2, 3), box_x_y_w_l(1, 0, 0, 4, 2)],
Costs = [9, 6, 0, 0, 0, 0],
Variables = [1, 7, 7, 1, 6, 5, 1, 2, 2|...] .

这些不是相同解决方案的排列，而是相同盒子的排列，因此具有相同的成本。我们不需要同时考虑它们！除了Kinds比开始时更智能地标记之外，我们还可以要求Kinds列表单调递增。这排除了许多冗余解决方案并提供了更快的终止，甚至首先使用更好的解决方案：

?- placements_([1, 2, 3, 4, 5, 6], 6, Placements, Kinds, Costs, Cost), term_variables(Placements, Variables, [Cost | Costs]), chain(Kinds, #=<), time(( labeling([], Kinds), labeling([ff], Variables) )).
% 34,943,765 inferences, 2.865 CPU in 2.865 seconds (100% CPU, 12195550 Lips)
Placements = [box_x_y_w_l(5, 2, 4, 2, 2), box_x_y_w_l(6, 8, 7, 1, 2), box_x_y_w_l(6, 5, 6, 3, 1), box_x_y_w_l(6, 2, 3, 3, 3), box_x_y_w_l(6, 0, 0, 2, 3), box_x_y_w_l(5, 0, 0, 2, 4)],
Kinds = [0, 0, 0, 0, 2, 4],
Costs = [0, 0, 0, 0, 6, 9],
Cost = 15,
Variables = [5, 2, 4, 6, 8, 7, 1, 2, 6|...] .

?- Cost #< 15, placements_([1, 2, 3, 4, 5, 6], 6, Placements, Kinds, Costs, Cost), term_variables(Placements, Variables, [Cost | Costs]), chain(Kinds, #=<), time(( labeling([], Kinds), labeling([ff], Variables) )).
% 31,360,608 inferences, 2.309 CPU in 2.309 seconds (100% CPU, 13581762 Lips)
false.

更多的调整是可能的，对于更大的问题可能是必要的。我发现添加bisect最终标签会有所帮助。删除 中的逻辑冗余Box1 #= Box2约束也是如此placement_disjoint/2。最后，考虑chain/2到限制的使用Kinds，我们可以Kinds完全删除初步标记以获得不错的加速！我敢肯定还有更多，但对于原型，我认为它足够合理。

感谢您提出这个有趣的问题！