带有Prolog的可变装箱问题(CLP)

Question

我试图用约束逻辑编程(CLP)来解决(Swi-)Prolog中的NP硬2D变尺寸Bin hard问题(2 2DVSBPP)。

问题可以这样解释:一些订购的产品需要尽可能高效地打包到一些 be (回收箱)中。产品有一定的宽度和长度(方形或矩形，如2x3)。有四种不同大小的箱子，每个箱子都有一个给定的成本给托运人(比如5x5箱4美元，5x7箱5美元)。目标是最小化盒子的总成本。

我一直在寻找这个问题的答案已经有一段时间了，并阅读了许多其他语言的论文和类似的例子。但是，我找不到任何可行的解决办法。我特别想知道如何处理未知数量的盒子(回收箱)。

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

盒子和产品：

:- 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)，其中Numbers是[1, 2, ..., N]，其他列表的I-th元素是框号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)的“通常”表示形式。原因是我们希望使用element/3索引到这些FD变量列表中。此谓词不能用于对其他术语列表进行索引。

关于产品，这里是您的析取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).

这就是我们使用FD变量的Widths和Lengths列表的地方。所选框的数量本身就是一个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|...] .

(您可能需要仔细检查这是否正确！)所有的东西都放在第一个盒子里，它是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|...] .

这确实需要ff或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会有所帮助。移除placement_disjoint/2中逻辑冗余的placement_disjoint/2约束也是如此。最后，考虑到使用chain/2来限制Kinds，我们可以完全删除Kinds的初步标记以获得一个很好的加速比！我相信还有更多，但对于一个原型，我认为它是足够合理的。

谢谢你的这个有趣的问题！

Answer 2

在您的部分解决方案中存在一些冗余，可能是由于过早的优化造成的。

首先，由于您有一个产品_way_way/3，所以不应该更改您的输入规范，添加具有相同id和交换尺寸的产品。毕竟，在现实世界中，宽度和高度是不能任意交换的属性，而且您已经生成了一个处理此问题的谓词，因此我已经开始删除这些重复项。

第二，不相交/2的目的是计算一组矩形的位置，因此您的area_box_pos_组合/4和pos_vars/2几乎毫无用处。

以下是我如何处理这个问题的方法。首先，编写一个谓词，给出一个产品列表和一个框，将尽可能多的产品放入其中，并“返回”那些不合适的产品。例如

fill_box([P|Ps],W,H,Placed,Rs) :-
    (   product(P,W_i,H_i)
    ;   product(P,H_i,W_i)
    ),
    W_p #= W - W_i,
    H_p #= H - H_i,
    X_i in 0..W_p,
    Y_i in 0..H_p,
    U=[p(X_i, W_i, Y_i, H_i)|Placed],
    disjoint2(U),
    fill_box(Ps,W,H,U,Rs).
fill_box(Rs,_,_,_,Rs).

它有点问题，因为它会停止在第一个产品，它不能放置，但可能有更多的可选择。但重要的是，考虑到与CLP(FD)关键概念的交互，现在我们可以开始测试它是否有效。不相交/2工作在有界的变量上，因此需要X_i和Y_i的域声明。

?- fill_box([1,1],4,2,[],R).
R = [] .

?- fill_box([1,1],3,2,[],R).
R = [1] .

现在我们可以提供一个司机，也许就像

products_placed_cost([],0).
products_placed_cost(Ps,C) :-
    box(W,H,C0),
    fill_box(Ps,W,H,[],Rs),
    Ps\=Rs,
    products_placed_cost(Rs,C1),
    C #= C0+C1.

然后让Prolog生成尽可能多的解决方案，只需通过库(序列)按成本排序：

?- order_by([asc(C)],products_placed_cost([1,1],C)).
C = 4 ;
C = 4 ;
C = 4 ;
C = 4 ;
C = 6 ;
...

但我们不知道已经产生了哪些位置。我们必须添加带有信息的论据。然后

products_placed_cost([],[],0).
products_placed_cost(Ps,[box(W,H,C0,Q)|Qs],C) :-
    box(W,H,C0),
    fill_box(Ps,W,H,[],Rs,Q),
    Ps\=Rs,
    products_placed_cost(Rs,Qs,C1),
    C #= C0+C1.

fill_box([P|Ps],W,H,Placed,Rs,[P|Qs]) :-
    (   product(P,W_i,H_i)
    ;   product(P,H_i,W_i)
    ),
    W_p #= W - W_i,
    H_p #= H - H_i,
    X_i in 0..W_p,
    Y_i in 0..H_p,
    U=[p(X_i, W_i, Y_i, H_i)|Placed],
    disjoint2(U),
    fill_box(Ps,W,H,U,Rs,Qs).
fill_box(Rs,_,_,_,Rs,[]).

诚然，库(Clpfd)只是作为商品使用，但与(纯) Prolog的搜索功能相结合，我们可以得到一个简短的声明性解决方案。

有关更好的方法，请参见库的具体文件 (clpBNR)。